<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@ba8de91630ba4907a1432f2c878fe076" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="ee3998df01d211ef9cf216fff75c5923">
<h2 class="hd hd-2 unit-title">Cantor's Theorem</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@799bbdddb09e475d8f1540d1e2c0becb">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@799bbdddb09e475d8f1540d1e2c0becb" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-has-score="False" data-graded="False" data-request-token="ee3998df01d211ef9cf216fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video: Introduction to Cantor's Theorem</h3>
<div
id="video_799bbdddb09e475d8f1540d1e2c0becb"
class="video closed"
data-metadata='{"speed": null, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@799bbdddb09e475d8f1540d1e2c0becb/handler/publish_completion", "streams": "1.00:GQiGCJUOhC4", "prioritizeHls": false, "completionEnabled": false, "autoAdvance": false, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "recordedYoutubeIsAvailable": true, "showCaptions": "true", "completionPercentage": 0.95, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@799bbdddb09e475d8f1540d1e2c0becb/handler/xmodule_handler/save_user_state", "ytMetadataEndpoint": "", "duration": 0.0, "autohideHtml5": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": [], "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@799bbdddb09e475d8f1540d1e2c0becb/handler/transcript/available_translations", "savedVideoPosition": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@799bbdddb09e475d8f1540d1e2c0becb/handler/transcript/translation/__lang__", "saveStateEnabled": false, "ytTestTimeout": 1500, "poster": null, "autoplay": false, "generalSpeed": 1.0, "start": 0.0, "end": 85.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="799bbdddb09e475d8f1540d1e2c0becb"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_799bbdddb09e475d8f1540d1e2c0becb">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_799bbdddb09e475d8f1540d1e2c0becb">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@799bbdddb09e475d8f1540d1e2c0becb/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@799bbdddb09e475d8f1540d1e2c0becb/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@52596001bd4b42e796932f4d10182bab">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@52596001bd4b42e796932f4d10182bab" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="ee3998df01d211ef9cf216fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">We have succeeded in identifying two different sizes of infinity: a smaller one, which corresponds to the size of the natural numbers and the rational numbers, and a bigger one, which corresponds to the size of the real numbers. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Could there be infinities of other sizes? Yes! We have:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Cantor's Theorem</strong></span><br /><span style="font-family: 'book antiqua', palatino;">A set always has more subsets than it has members.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">This result entails that there are more subsets of real numbers than there are real numbers, and more subsets of subsets of real numbers than there are subsets of real numbers, and so forth. In other words: <em>there are infinitely many sizes of infinity!</em></span></p>
<p><span style="font-family: 'book antiqua', palatino;">Cantor's Theorem is, of course, named in honor of Georg Cantor who proved this result, along with all of the other main results in this lecture.</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@643be8c848b34ae6be3de1cb623225a3" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="ee3998df01d211ef9cf216fff75c5923">
<h2 class="hd hd-2 unit-title">A Proof of Cantor's Theorem</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@15c9f5cc8f8f4a7e86ce24d63a97ff9c">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@15c9f5cc8f8f4a7e86ce24d63a97ff9c" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="ee3998df01d211ef9cf216fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Let us refer to the set of <span class="math inline">\(A\)</span>’s subsets as <span class="math inline">\(A\)</span>’s <strong>powerset</strong>; in symbols: <span class="math inline">\(\mathscr{P}(A)\)</span>. Cantor’s Theorem can then be restated as follows:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Cantor's Theorem</strong></span><br /><span style="font-family: 'book antiqua', palatino;">For any set <span class="math inline">\(A\)</span>, <span class="math inline">\(|A| < |\mathscr{P}(A)|\)</span></span></p>
<p><span style="font-family: 'book antiqua', palatino;">In order to prove this result, we’ll need to verify each of the following two statements:</span></p>
<ol>
<li>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|A| \leq |\mathscr{P}(A)|\)</span></p>
</li>
<li>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|A| \neq |\mathscr{P}(A)|\)</span></p>
</li>
</ol>
<p><span style="font-family: 'book antiqua', palatino;">The first of these statements is straightforward, since the function <span class="math inline">\(f(x) = \{x\}\)</span> is an injection from <span class="math inline">\(A\)</span> to <span class="math inline">\(\mathscr{P}(A)\)</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">So what we really need to verify is the second statement: <span class="math inline">\(|A| \neq |\mathscr{P}(A)|\)</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Our proof of <span class="math inline">\(|A| \neq |\mathscr{P}(A)|\)</span> will proceed by <em>reductio</em>. We will assume the negation of what we wish to prove, and use this assumption to prove a contradiction. Since we want to prove <span class="math inline">\(|A| \neq |\mathscr{P}(A)|\)</span>, this means that we will assume <span class="math inline">\(|A| = |\mathscr{P}(A)|\)</span>. We will assume, in other words, that there is a bijection <span class="math inline">\(f\)</span> from <span class="math inline">\(A\)</span> to <span class="math inline">\(\mathscr{P}(A)\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Note that for each <span class="math inline">\(a\)</span> in <span class="math inline">\(A\)</span>, <span class="math inline">\(f(a)\)</span> is a member of <span class="math inline">\(\mathscr{P}(A)\)</span>, and therefore a subset of <span class="math inline">\(A\)</span>. So we can consider the question of whether <span class="math inline">\(a\)</span> is a member of <span class="math inline">\(f(a)\)</span>. In symbols: <span class="math display">\[\text{$a \in f(a)$?}\]</span> Note that this question will be answered negatively for whichever <span class="math inline">\(a \in A\)</span> is mapped by <span class="math inline">\(f\)</span> to the empty set. Notice, moreover, that (if <span class="math inline">\(A\)</span> is non-empty) the question will be answered positively for whichever member of <span class="math inline">\(A\)</span> is mapped by <span class="math inline">\(f\)</span> to <span class="math inline">\(A\)</span> itself.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(D\)</span> be the set of members of <span class="math inline">\(A\)</span> for which the question is answered negatively. In other words: <span class="math display">\[D = \{x \in A : x \notin f(x)\}\]</span> Since <span class="math inline">\(D\)</span> is a subset of <span class="math inline">\(A\)</span>, <span class="math inline">\(f\)</span> must map some <span class="math inline">\(d\)</span> in <span class="math inline">\(A\)</span> to <span class="math inline">\(D\)</span>. Now consider the following question: <span class="math display">\[\text{$d \in D$?}\]</span> The definition of <span class="math inline">\(D\)</span> tells us that <span class="math inline">\(d\)</span> is a member of <span class="math inline">\(D\)</span> if and only if <span class="math inline">\(d\)</span> is not a member of <span class="math inline">\(f(d)\)</span>. In symbols: <span class="math display">\[d \in D \leftrightarrow d \notin f(d)\]</span> But the definition of <span class="math inline">\(d\)</span> tells us that <span class="math inline">\(f(d) = D\)</span>. So we have: <span class="math display">\[d \in D \leftrightarrow d \notin D\]</span> That statement is a contradiction: it tells us that something is the case if and only if it is not the case. So we have concluded our proof. We have assumed <span class="math inline">\(|A| = |\mathscr{P}(A)|\)</span>, and used it to prove a contradiction. From this it follows that <span class="math inline">\(|A| = |\mathscr{P}(A)|\)</span> is false, and therefore that <span class="math inline">\(|A| \neq |\mathscr{P}(A)|\)</span> is true.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Cantor’s Theorem is an amazing result. It shows that regardless of how many individuals there are in a set <span class="math inline">\(A\)</span>, and regardless of whether <span class="math inline">\(A\)</span> is finite or infinite <span class="math inline">\(A\)</span>, there must be even more individuals in <span class="math inline">\(A\)</span>’s power set. So there are infinitely many sizes of infinity!</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@bb8f362da5734a6db6d51c185ef6931a">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@bb8f362da5734a6db6d51c185ef6931a" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-has-score="False" data-graded="False" data-request-token="ee3998df01d211ef9cf216fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">VideoVideo Review: Proving Cantor's Theorem</h3>
<div
id="video_bb8f362da5734a6db6d51c185ef6931a"
class="video closed"
data-metadata='{"speed": null, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@bb8f362da5734a6db6d51c185ef6931a/handler/publish_completion", "streams": "1.00:HJGCO9LCoqQ", "prioritizeHls": false, "completionEnabled": false, "autoAdvance": false, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "recordedYoutubeIsAvailable": true, "showCaptions": "true", "completionPercentage": 0.95, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@bb8f362da5734a6db6d51c185ef6931a/handler/xmodule_handler/save_user_state", "ytMetadataEndpoint": "", "duration": 0.0, "autohideHtml5": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": [], "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@bb8f362da5734a6db6d51c185ef6931a/handler/transcript/available_translations", "savedVideoPosition": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@bb8f362da5734a6db6d51c185ef6931a/handler/transcript/translation/__lang__", "saveStateEnabled": false, "ytTestTimeout": 1500, "poster": null, "autoplay": false, "generalSpeed": 1.0, "start": 0.0, "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="bb8f362da5734a6db6d51c185ef6931a"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
</div>
</div>
</div>
</div>
</div>
© All Rights Reserved