<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@e8613217517a44bc8d664fe0547e77bd" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="VerticalStudentView">
<h2 class="hd hd-2 unit-title">Size Comparisons</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@d50cb5627f564633aa2e503d597c066d">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@d50cb5627f564633aa2e503d597c066d" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Here is a useful piece of notation. If <span class="math inline">\(A\)</span> is a set, we will use <span class="math inline">\(|A|\)</span> to talk about the size, or <strong>cardinality</strong>, of <span class="math inline">\(A\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">In some of the problems of the previous lecture we verified that bijections are reflexive, symmetrical and transitive. This means that the relation <span class="math inline">\(|A| = |B|\)</span> is itself reflexive, symmetrical and transitive. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">In other words, for any sets <span class="math inline">\(A\)</span>, <span class="math inline">\(B\)</span> and <span class="math inline">\(C\)</span> we have:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Reflexivity</strong></span><br /><span style="font-family: 'book antiqua', palatino;">\(|A|=|A|\)</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Symmetry</strong><span style="font-size: 1em; line-height: 1.6em;"><br /></span>If \(|A|= |B|\), then \(|B|=|A|\)</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Transitivity</strong></span><br /><span style="font-family: 'book antiqua', palatino;">If \(|A|=|B|\) and \(|B|=|C|\), then \(|A|=|C|\)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">A reflexive, symmetric and transitive relation is said to be an <strong>equivalence relation</strong>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">By relying on the fact that <span class="math inline">\(|A| = |B|\)</span> is an equivalence relation, we can provide a beautifully succinct summary of the results so far: <span class="math display">\[|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}^{\geq 0}| = |\mathbb{Q}|\]</span> </span></p>
<p><span style="font-family: 'book antiqua', palatino;">These results make it tempting to suppose that any infinite set has the same cardinality as any other. But we’ll soon see that this is not so: <em>there are infinite sets with different cardinalities</em>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">We’ll see, in particular, that the set of real numbers, <span class="math inline">\(\mathbb{R}\)</span> has a greater cardinality than the set of natural numbers: <span class="math display">\[|\mathbb{N}| < |\mathbb{R}|\]</span> </span></p>
<p><span style="font-family: 'book antiqua', palatino;">In order to prepare for these results, however, we’ll need to get clear about what it means to say that one cardinality is greater than another. Recall that our understanding of <em>sameness</em> of cardinality is based on the Bijection Principle, which I restate here using our new notation:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>The Bijection Principle</strong></span><br /><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(|A| = |B|\)</span> if and only if there is a bijection from <span class="math inline">\(A\)</span> to <span class="math inline">\(B\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">How might we extend this idea to explain what it takes for the cardinality of <span class="math inline">\(B\)</span> is greater than the cardinality of <span class="math inline">\(A\)</span> (in symbols: <span class="math inline">\(|A| < |B|\)</span>). We’ll start by addressing a closely related question: what does it take for the cardinality of <span class="math inline">\(B\)</span> to be <em>at least as great</em> as the cardinality of <span class="math inline">\(A\)</span> (in symbols: <span class="math inline">\(|A| \leq |B|\)</span>)? </span></p>
<p><span style="font-family: 'book antiqua', palatino;">The answer we will be working with here is based on the following principle:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>The Injection Principle</strong></span><br /><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(|A| \leq |B|\)</span> if and only if there is a bijection from <span class="math inline">\(A\)</span> to a subset of <span class="math inline">\(B\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Why call it the Injection Principle? Because an <strong>injection</strong> from <span class="math inline">\(A\)</span> to <span class="math inline">\(B\)</span> is a bijection from <span class="math inline">\(A\)</span> to a subset of <span class="math inline">\(B\)</span>. Notice, moreover, that the Injection Principle makes intuitive sense. Intuitively, the only way for <span class="math inline">\(A\)</span> to have just as many elements as a subset of <span class="math inline">\(B\)</span> is for <span class="math inline">\(B\)</span> to have at least as many elements as <span class="math inline">\(A\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">(If you'd like some additional help making sense of injections, there's a useful video <a href="https://www.khanacademy.org/math/linear-algebra/matrix-transformations/inverse-transformations/v/surjective-onto-and-injective-one-to-one-functions" target="[object Object]">here</a>. If you watch the video, keep in mind that a bijective function is a function that is both injective and surjective.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Together, the Bijection and Injection Principles give us everything we need to make cardinality comparisons between infinite sets. This is because <span class="math inline">\(|A| < |B|\)</span> can be defined in terms of <span class="math inline">\(|A| = |B|\)</span> and <span class="math inline">\(|A| \leq |B|\)</span>: <span class="math display">\[|A| < |B| \leftrightarrow_{df} |A| \leq |B| \text{ and } |A| \neq |B|\]</span> (I use “<span class="math inline">\(\leftrightarrow_{df}\)</span>” to indicate that the sentence to the left of the biconditional is to be defined in terms of the sentence to its right.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Note that our definition makes intuitive sense. Intuitively, if the cardinality of <span class="math inline">\(B\)</span> is at least as great as the cardinality of <span class="math inline">\(A\)</span>, and if the cardinalities are not the same, then the cardinality of <span class="math inline">\(B\)</span> must be greater than the cardinality of <span class="math inline">\(A\)</span>.</span></p>
<table>
<thead>
<tr class="header"><th align="center"><span style="font-family: 'book antiqua', palatino;"><strong>Notation</strong></span></th><th align="center"><span style="font-family: 'book antiqua', palatino;"><strong>How it’s defined</strong></span></th><th align="center"><span style="font-family: 'book antiqua', palatino;"><strong>Informal notion</strong></span></th></tr>
</thead>
<tbody>
<tr class="odd">
<td align="center"><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|A| = |B|\)</span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;">bijection from <span class="math inline">\(A\)</span> to <span class="math inline">\(B\)</span></span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;">just as many elements in <span class="math inline">\(A\)</span> as in <span class="math inline">\(B\)</span></span></td>
</tr>
<tr class="even">
<td align="center"><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|A| \leq |B|\)</span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;">injection from <span class="math inline">\(A\)</span> to <span class="math inline">\(B\)</span></span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;">at most as many elements in <span class="math inline">\(A\)</span> as in <span class="math inline">\(B\)</span></span></td>
</tr>
<tr class="odd">
<td align="center"><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|A| < |B|\)</span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(|A| \leq~|B|\)</span> and <span class="math inline">\(|A| \neq |B|\)</span></span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;">fewer elements in <span class="math inline">\(A\)</span> than in <span class="math inline">\(B\)</span></span></td>
</tr>
<tr class="even">
<td align="center"><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|A| \geq |B|\)</span></td>
<td align="center"><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|B| \leq |A|\)</span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;">at least as many elements in <span class="math inline">\(A\)</span> as in <span class="math inline">\(B\)</span></span></td>
</tr>
<tr class="odd">
<td align="center"><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|A| > |B|\)</span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(|A| \geq |B|\)</span> and <span class="math inline">\(|A| \neq |B|\)</span></span></td>
<td align="center"><span style="font-family: 'book antiqua', palatino;">more elements in <span class="math inline">\(A\)</span> than in <span class="math inline">\(B\)</span></span></td>
</tr>
</tbody>
</table>
<p><span style="font-family: 'book antiqua', palatino;">One of the reasons Injection Principle is so attractive is that <span class="math inline">\(\leq\)</span> is a <strong>partial order</strong>. In other words, <span class="math inline">\(\leq\)</span> satisfies the following principles, for any sets <span class="math inline">\(A\)</span>, <span class="math inline">\(B\)</span> and <span class="math inline">\(C\)</span>:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Reflexivity</strong></span><br /><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|A|\leq |A|\)</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Anti-symmetry</strong></span><br /><span style="font-family: 'book antiqua', palatino;">If <span class="math inline">\(|A|\leq |B|\)</span> and <span class="math inline">\(|B|\leq |A|\)</span>, then <span class="math inline">\(|A|= |B|\)</span></span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Transitivity</strong></span><br /><span style="font-family: 'book antiqua', palatino;">If <span class="math inline">\(|A|\leq |B|\)</span> and <span class="math inline">\(|B|\leq |C|\)</span>, then <span class="math inline">\(|A|\leq |C|\)</span></span></p>
<p><span style="font-family: 'book antiqua', palatino;">We'll have a go at proving the first and third of these principles in the exercises below. The second principle requires a lengthy proof, which we won’t reconstruct here. It is sometimes referred to as the <strong>Cantor-Schroeder-Bernstein Theorem</strong>, and it is easy to learn more about it <a href="https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem">online</a>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">There is a fourth principle which is intuitively correct, and which we’d very much like to be able to prove:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Totality</strong></span><br /><span style="font-family: 'book antiqua', palatino;">For any sets <span class="math inline">\(A\)</span> and <span class="math inline">\(B\)</span>, either <span class="math inline">\(|A|\leq |B|\)</span> or <span class="math inline">\(|B|\leq |A|\)</span></span></p>
<p><span style="font-family: 'book antiqua', palatino;">Unfortunately, one can only prove Totality if one assumes a controversial set-theoretic axiom: the Axiom of Choice. I'll have a lot more to say about the Axiom of Choice later on. (We'll come across it again in Lecture 3, and I'll offer a more thorough discussion in Lecture 7.)</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@14a22c109b46423fa61ba908e93e0aa0">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@14a22c109b46423fa61ba908e93e0aa0" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;"><strong><span style="font-family: book antiqua,palatino;">Some notation</span><br /></strong></span></h4>
<p><span style="font-family: 'book antiqua', palatino;">Earlier I mentioned that bijections go by many names. The same is true of injections. (And I'm afraid I sometimes use other names in the videos associated with this course; the videos were shot several years ago!). Here is a translation-manual:<br /></span></p>
<center>
<table style="width: 731px;" height="487">
<thead>
<tr><th style="text-align: center;"><span style="font-family: book antiqua,palatino;">Notation in text</span></th><th style="text-align: center;"><span style="font-family: book antiqua,palatino;">Notation in videos<br /></span></th></tr>
</thead>
<tbody>
<tr>
<td style="text-align: center;"><span style="font-family: 'book antiqua', palatino;">\(f\) is an injection from \(A\) to \(B\)</span><span style="font-family: 'book antiqua', palatino;"><span style="font-family: 'book antiqua', palatino;"></span></span></td>
<td style="text-align: center;"><span style="font-family: 'book antiqua', palatino;"><span style="font-family: 'book antiqua', palatino;"></span></span><span style="font-family: 'book antiqua', palatino;"><span style="font-family: 'book antiqua', palatino;"><span style="font-family: 'book antiqua', palatino;"><span style="font-family: 'book antiqua', palatino;"><span style="font-family: 'book antiqua', palatino;">\(f\)</span> is a one-one function from \(A\) <strong>into</strong> \(B\)</span></span></span></span><span style="font-family: 'book antiqua', palatino;"></span></td>
</tr>
<tr>
<td style="text-align: center;"><span style="font-family: 'book antiqua', palatino;">\(f\) is a bijection from \(A\) to \(B\)</span></td>
<td style="text-align: center;"><span style="font-family: 'book antiqua', palatino;">\(f\) is a one-one function from \(A\) <strong>onto</strong> \(B\)<br />or<br />\(f\) is a one-one correspondence between \(A\) and \(B\)</span></td>
</tr>
</tbody>
</table>
</center>
<p></p>
<p></p>
<p></p>
<p></p>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@46a255e9fde342878dda3cfd7678e6aa">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@46a255e9fde342878dda3cfd7678e6aa" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: at least as great</h3>
<div
id="video_46a255e9fde342878dda3cfd7678e6aa"
class="video closed"
data-metadata='{"end": 0.0, "speed": null, "ytTestTimeout": 1500, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@46a255e9fde342878dda3cfd7678e6aa/handler/publish_completion", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "streams": "1.00:bc-QooRaUP0", "poster": null, "saveStateEnabled": false, "start": 0.0, "completionPercentage": 0.95, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@46a255e9fde342878dda3cfd7678e6aa/handler/transcript/available_translations", "autoplay": false, "transcriptLanguages": {"en": "English"}, "autohideHtml5": false, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@46a255e9fde342878dda3cfd7678e6aa/handler/transcript/translation/__lang__", "ytMetadataEndpoint": "", "generalSpeed": 1.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "autoAdvance": false, "completionEnabled": false, "savedVideoPosition": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@46a255e9fde342878dda3cfd7678e6aa/handler/xmodule_handler/save_user_state", "captionDataDir": null, "sources": [], "transcriptLanguage": "en", "recordedYoutubeIsAvailable": true, "prioritizeHls": false, "duration": 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="46a255e9fde342878dda3cfd7678e6aa"></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_46a255e9fde342878dda3cfd7678e6aa">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_46a255e9fde342878dda3cfd7678e6aa">
<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@46a255e9fde342878dda3cfd7678e6aa/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@46a255e9fde342878dda3cfd7678e6aa/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@f1befea7387b4a059b4b57dfd86a2cff">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@f1befea7387b4a059b4b57dfd86a2cff" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_f1befea7387b4a059b4b57dfd86a2cff" class="problems-wrapper" role="group"
aria-labelledby="f1befea7387b4a059b4b57dfd86a2cff-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@f1befea7387b4a059b4b57dfd86a2cff" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@f1befea7387b4a059b4b57dfd86a2cff/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="1.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="f1befea7387b4a059b4b57dfd86a2cff-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@f1befea7387b4a059b4b57dfd86a2cff-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@f1befea7387b4a059b4b57dfd86a2cff-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">A function \(f\) from \(A\) to \(B\) is an injection (as defined above) if and only if \(f\) assigns a differet element of \(B\) to each element of \(A\).</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">True or False?</span>
</p>
<div class="inputtype option-input ">
<select name="input_f1befea7387b4a059b4b57dfd86a2cff_2_1" id="input_f1befea7387b4a059b4b57dfd86a2cff_2_1" aria-describedby="status_f1befea7387b4a059b4b57dfd86a2cff_2_1">
<option value="option_f1befea7387b4a059b4b57dfd86a2cff_2_1_dummy_default">Select an option</option>
<option value="True"> True</option>
<option value="False"> False</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_f1befea7387b4a059b4b57dfd86a2cff_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_f1befea7387b4a059b4b57dfd86a2cff_2_1"/>
</div><div class="solution-span">
<span id="solution_f1befea7387b4a059b4b57dfd86a2cff_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 1" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_f1befea7387b4a059b4b57dfd86a2cff" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_f1befea7387b4a059b4b57dfd86a2cff">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="f1befea7387b4a059b4b57dfd86a2cff-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="f1befea7387b4a059b4b57dfd86a2cff-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="f1befea7387b4a059b4b57dfd86a2cff-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@93924840c18944df9218984e2483788d">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@93924840c18944df9218984e2483788d" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_93924840c18944df9218984e2483788d" class="problems-wrapper" role="group"
aria-labelledby="93924840c18944df9218984e2483788d-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@93924840c18944df9218984e2483788d" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@93924840c18944df9218984e2483788d/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="1.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="93924840c18944df9218984e2483788d-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@93924840c18944df9218984e2483788d-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@93924840c18944df9218984e2483788d-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">For \(f\) to be a <em>surjection</em> from \(A\) to \(B\) is for there to be no element of \(B\) to which \(f\) fails to assign some element of \(A\). Now consider the following proposition:</span>
</p>
<p>
<blockquote>
<span style="font-family: 'book antiqua', palatino;">\(f\) is a bijection from \(A\) to \(B\) if and only if \(f\) is both an injection from \(A\) to \(B\) and a surjection from \(A\) to \(B\).</span>
</blockquote>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">Is it true or false?</span>
</p>
<div class="inputtype option-input ">
<select name="input_93924840c18944df9218984e2483788d_2_1" id="input_93924840c18944df9218984e2483788d_2_1" aria-describedby="status_93924840c18944df9218984e2483788d_2_1">
<option value="option_93924840c18944df9218984e2483788d_2_1_dummy_default">Select an option</option>
<option value="True"> True</option>
<option value="False"> False</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_93924840c18944df9218984e2483788d_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_93924840c18944df9218984e2483788d_2_1"/>
</div><div class="solution-span">
<span id="solution_93924840c18944df9218984e2483788d_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 2" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_93924840c18944df9218984e2483788d" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_93924840c18944df9218984e2483788d">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="93924840c18944df9218984e2483788d-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="93924840c18944df9218984e2483788d-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="93924840c18944df9218984e2483788d-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-5" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@188b86c694b74b21a7d3502721bab41c">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@188b86c694b74b21a7d3502721bab41c" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_188b86c694b74b21a7d3502721bab41c" class="problems-wrapper" role="group"
aria-labelledby="188b86c694b74b21a7d3502721bab41c-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@188b86c694b74b21a7d3502721bab41c" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@188b86c694b74b21a7d3502721bab41c/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="1.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="188b86c694b74b21a7d3502721bab41c-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@188b86c694b74b21a7d3502721bab41c-problem-progress" tabindex="-1">
Problem 3
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@188b86c694b74b21a7d3502721bab41c-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">Which of the following, if any, is true of \( \leq \) (injections)?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_188b86c694b74b21a7d3502721bab41c_2_1">
<fieldset aria-describedby="status_188b86c694b74b21a7d3502721bab41c_2_1">
<div class="field">
<input type="checkbox" name="input_188b86c694b74b21a7d3502721bab41c_2_1[]" id="input_188b86c694b74b21a7d3502721bab41c_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="188b86c694b74b21a7d3502721bab41c_2_1-choice_0-label" for="input_188b86c694b74b21a7d3502721bab41c_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_188b86c694b74b21a7d3502721bab41c_2_1">
<p style="padding-left: 30px;">
<span style="font-family: 'book antiqua', palatino;">
<strong> Reflexivity </strong>
</span>
<br/>
<span style="font-family: 'book antiqua', palatino;"> For any set \(A\), \(|A| \leq |A|\). </span>
</p>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_188b86c694b74b21a7d3502721bab41c_2_1[]" id="input_188b86c694b74b21a7d3502721bab41c_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="188b86c694b74b21a7d3502721bab41c_2_1-choice_1-label" for="input_188b86c694b74b21a7d3502721bab41c_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_188b86c694b74b21a7d3502721bab41c_2_1">
<p style="padding-left: 30px;">
<span style="font-family: 'book antiqua', palatino;">
<strong> Symmetry </strong>
</span>
<br/>
<span style="font-family: 'book antiqua', palatino;"> For any sets \(A\) and \(B\), if \(|A| \leq |B|\), then \(|B| \leq |A|\). </span>
</p>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_188b86c694b74b21a7d3502721bab41c_2_1[]" id="input_188b86c694b74b21a7d3502721bab41c_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="188b86c694b74b21a7d3502721bab41c_2_1-choice_2-label" for="input_188b86c694b74b21a7d3502721bab41c_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_188b86c694b74b21a7d3502721bab41c_2_1">
<p style="padding-left: 30px;">
<span style="font-family: 'book antiqua', palatino;">
<strong> Transitivity </strong>
</span>
<br/>
<span style="font-family: 'book antiqua', palatino;"> For any sets \(A\), \(B\), and \(C\), if \(|A| \leq |B|\), and \(|B| \leq |C|\), then \(|A| \leq |C|\). </span>
</p>
</label>
</div>
<span id="answer_188b86c694b74b21a7d3502721bab41c_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_188b86c694b74b21a7d3502721bab41c_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_188b86c694b74b21a7d3502721bab41c_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_188b86c694b74b21a7d3502721bab41c" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_188b86c694b74b21a7d3502721bab41c">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="188b86c694b74b21a7d3502721bab41c-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="188b86c694b74b21a7d3502721bab41c-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="188b86c694b74b21a7d3502721bab41c-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-6" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@372ac32de0e14a1b92c42dbec286e984">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@372ac32de0e14a1b92c42dbec286e984" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="True" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_372ac32de0e14a1b92c42dbec286e984" class="problems-wrapper" role="group"
aria-labelledby="372ac32de0e14a1b92c42dbec286e984-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@372ac32de0e14a1b92c42dbec286e984" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@372ac32de0e14a1b92c42dbec286e984/handler/xmodule_handler"
data-problem-score="0.0"
data-problem-total-possible="1.0"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="372ac32de0e14a1b92c42dbec286e984-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@372ac32de0e14a1b92c42dbec286e984-problem-progress" tabindex="-1">
Problem 4
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@372ac32de0e14a1b92c42dbec286e984-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">If <span class="math inline">\(|A| &lt; |B|\)</span> and <span class="math inline">\(|B| \leq |C|\)</span>, then <span class="math inline">\(|A| &lt; |C|\)</span>.</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">True or False?</span>
</p>
<div class="inputtype option-input ">
<select name="input_372ac32de0e14a1b92c42dbec286e984_2_1" id="input_372ac32de0e14a1b92c42dbec286e984_2_1" aria-describedby="status_372ac32de0e14a1b92c42dbec286e984_2_1">
<option value="option_372ac32de0e14a1b92c42dbec286e984_2_1_dummy_default">Select an option</option>
<option value="True"> True</option>
<option value="False"> False</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_372ac32de0e14a1b92c42dbec286e984_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_372ac32de0e14a1b92c42dbec286e984_2_1"/>
</div><p>
<span style="font-family: 'book antiqua', palatino;">(If it's true, have a go at proving it. If it's false, produce a counterexample.) </span>
</p>
<div class="solution-span">
<span id="solution_372ac32de0e14a1b92c42dbec286e984_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 4" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_372ac32de0e14a1b92c42dbec286e984" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_372ac32de0e14a1b92c42dbec286e984">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="372ac32de0e14a1b92c42dbec286e984-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="372ac32de0e14a1b92c42dbec286e984-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="372ac32de0e14a1b92c42dbec286e984-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@b88f383d7f3f4d53a5f9d78eff79135f" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="VerticalStudentView">
<h2 class="hd hd-2 unit-title">Finite Sequences of Natural Numbers</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@c7ce4c46165243d095d855d74e9191b9">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@c7ce4c46165243d095d855d74e9191b9" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-request-token="48d26aaa017911ef8f77026cc65ec0d9" data-has-score="False" data-runtime-version="1" data-init="XBlockToXModuleShim">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">In this section we will verify that the set of finite sequences of natural numbers (<span class="math inline">\(\mathfrak{F}\)</span>) has the same cardinality as the set of natural numbers. In other words: <span class="math inline">\(|\mathbb{N}| = |\mathfrak{F}|\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">(The set of finite sequences of natural numbers <span class="math inline">\(\mathfrak{F}\)</span> was defined <a href="/courses/course-v1:MITx+24.118x+2T2020/jump_to_id/ed626d205ac44ba89e47aebe2774fda6">here</a>. So, for example, six different members of <span class="math inline">\(\mathfrak{F}\)</span> are: <span class="math inline">\(\langle 17, 1, 1, 6, 35324 \rangle, \langle 54 \rangle\), \(\langle 54, 54 \rangle\), \(\langle 22, 16 \rangle\), \(\langle 16, 22 \rangle\), and \(\langle 9999, 1, 16, 234, 754, 235345546334, 2343, 1 \rangle\)</span>.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We could, if we wanted, try to prove this result directly, by defining a bijection from <span class="math inline">\(\mathbb{N}\)</span> to <span class="math inline">\(\mathfrak{F}\)</span>. But I’d like to tell you about a trick, which makes the proof a lot easier. Rather than trying to define a bijection from <span class="math inline">\(\mathbb{N}\)</span> to <span class="math inline">\(\mathfrak{F}\)</span>, we’ll verify each of the following:</span></p>
<ol>
<li>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|\mathbb{N}| \leq |\mathfrak{F}|\)</span></p>
</li>
<li>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(|\mathfrak{F}| \leq |\mathbb{N}|\)</span></p>
</li>
</ol>
<p><span style="font-family: 'book antiqua', palatino;">Then we'll use the Cantor-Schroeder-Bernstein Theorem to conclude <span class="math inline">\(|\mathbb{N}| = |\mathfrak{F}|\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">To verify <span class="math inline">\(|\mathbb{N}| \leq |\mathfrak{F}|\)</span>, we need an injective function from <span class="math inline">\(\mathbb{N}\)</span> to <span class="math inline">\(\mathfrak{F}\)</span>. But this is totally straightforward, since one such function is the function that maps each natural number <span class="math inline">\(n\)</span> to the one-membered sequence <span class="math inline">\(\langle n\rangle\)</span>. To verify <span class="math inline">\(|\mathfrak{F}| \leq |\mathbb{N}|\)</span>, we need an injective function <span class="math inline">\(f\)</span> from <span class="math inline">\(\mathfrak{F}\)</span> to <span class="math inline">\(\mathbb{N}\)</span>. Here is one way of doing so:</span></p>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math display">\[f(\langle n_1,n_2,\dots,n_k \rangle) = p_1^{n_1+1} \cdot p_2^{n_2+1} \cdot \dots \cdot p_k^{n_k+1}\]</span> where <span class="math inline">\(p_i\)</span> is the <span class="math inline">\(i\)</span>th prime number. For example: <span class="math display">\[\begin{array}{ccccccccccccccc} f(\langle 4,0,1\rangle) &= &2^{4+1} &\cdot &3^{0+1} &\cdot &5^{1+1} \\ \ &= &32 &\cdot &3 &\cdot &25 &= &2400 \end{array}\]</span> Our function <span class="math inline">\(f\)</span> function certainly succeeds in assigning a natural number to each finite sequence of natural numbers. And it is guaranteed to be injective, because of the following important result:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Fundamental Theorem of Arithmetic</strong></span><br /><span style="font-family: 'book antiqua', palatino;">Every positive integer greater than 1 has a unique decomposition into primes.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We have now verified <span class="math inline">\(|\mathbb{N}| \leq |\mathfrak{F}|\)</span> and <span class="math inline">\(|\mathfrak{F}| \leq |\mathbb{N}|\)</span>. So the Cantor-Schroeder-Bernstein Theorem gives us <span class="math inline">\(|\mathbb{N}| = |\mathfrak{F}|\)</span>. This concludes our proof!</span></p>
</div>
</div>
</div>
</div>
© All Rights Reserved