<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@8d7ff90e50364f90acfcb2c1b07e4537" 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="bdfea436018f11ef9cd816fff75c5923">
<h2 class="hd hd-2 unit-title">The Power Set of Natural Numbers</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@d6204a3d7e1a400b9976f3d01b5da270">
<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@d6204a3d7e1a400b9976f3d01b5da270" 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="bdfea436018f11ef9cd816fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">We have now proved two important results about the relative sizes of infinite sets. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">First, we saw that there are more real numbers than natural numbers: <span class="math inline">\(|\mathbb{N}| < |\mathbb{R}|\)</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Then we proved Cantor’s Theorem, from which it follows that there are more subsets of natural numbers than natural numbers: <span class="math inline">\(|\mathbb{N}| < |\mathscr{P}(\mathbb{N})|\)</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">These results entail that <span class="math inline">\(\mathscr{P} (\mathbb{N})\)</span> and <span class="math inline">\(\mathbb{R}\)</span> both have cardinalities greater than <span class="math inline">\(\mathbb{N}\)</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">But they do not settle the relative sizes of <span class="math inline">\(\mathscr{P}(\mathbb{N})\)</span> and <span class="math inline">\(\mathbb{R}\)</span>. As it turns out, the two sets have exactly the same size: <span class="math display">\[|\mathscr{P}(\mathbb{N})| = |\mathbb{R}|\]</span> I find this is a deeply satisfying result, so I’d like to end this chapter by showing you how to prove it.</span></p>
<p></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@3c0696ab12ef4faebd089f7a9bdea3db" 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="bdfea436018f11ef9cd816fff75c5923">
<h2 class="hd hd-2 unit-title">Binary Notation</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@9a9d4311969940bbafee413ca2e215f6">
<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@9a9d4311969940bbafee413ca2e215f6" 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="bdfea436018f11ef9cd816fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Our proof will rely on representing real numbers in binary notation. In particular, we will be using <strong>binary expansions</strong> of the form "<span class="math inline">\(0.b_1b_2b_3\ldots,\)"</span> where each digit <span class="math inline">\(b_i\)</span> is either a zero or a one. (For instance, \(0.00100100001\dots\))</span></p>
<p><span style="font-family: 'book antiqua', palatino;">It will be useful start by saying a few worlds about binary expansions. The way to tell which binary expansion corresponds to which number is to apply the following recipe:<span class="math display">\[\text{the binary name “}0.b_1b_2b_3\ldots\text{” represents the number: } \frac{b_1}{2^1}+\frac{b_2}{2^2}+\frac{b_3}{2^3}+\ldots\]</span> Consider, for example, the binary expansion "<span class="math inline">\(0.001(0)\)"</span> (i.e. "<span class="math inline">\(0.00100000000\dots\)"</span>). It is a name for the number <span class="math inline">\(1/8\)</span>, since according to our recipe: <span class="math display">\[\text{the binary name “}0.001(0)\text{” represents the number } \frac{0}{2^1}+\frac{0}{2^2}+\frac{1}{2^3}+\sum_{n=4}^{\infty} \left(\frac{0}{2^n}\right) =\frac{1}{8}\]</span></span></p>
<p><span style="font-family: 'book antiqua', palatino;">As you’ll be asked to prove in the exercises below, every real number in <span class="math inline">\([0,1]\)</span> is named by some binary expansion of the form "<span class="math inline">\(0.b_1b_2b_3\ldots,\)"</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">It is also worth noting that binary notation shares some important features with decimal notation. In particular, the binary expansions of <em>rational</em> numbers are always periodic: they end with an infinitely repeating string of digits. And the binary expansions of <em>irrational</em> numbers are never periodic. Also, some real numbers are named by more than one binary expansion. For instance, <span class="math inline">\(1/8\)</span> is represented not just by "<span class="math inline">\(0.001(0)\)"</span>, but also by "<span class="math inline">\(0.000(1)\)"</span>, since <span class="math display">\[\text{the binary name “0.000(1)" represents the number } \frac{0}{2^1}+\frac{0}{2^2}+\frac{0}{2^3}+\sum_{n=4}^{\infty} \left(\frac{1}{2^n}\right) =\frac{1}{8}\]</span> Fortunately, the only real numbers with multiple names are those named by binary expansions that end in an infinite sequence of 1s. Such numbers always have exactly two binary names: one ending in an infinite sequence of 1s and one ending in an infinite sequence of 0s. Since only rational numbers have periodic binary expansions, this means that there are only countably many real numbers with more than one binary name.</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9c4e6f5334a643b09b8e5df30515e13d">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9c4e6f5334a643b09b8e5df30515e13d" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="bdfea436018f11ef9cd816fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_9c4e6f5334a643b09b8e5df30515e13d" class="problems-wrapper" role="group"
aria-labelledby="9c4e6f5334a643b09b8e5df30515e13d-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9c4e6f5334a643b09b8e5df30515e13d" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@9c4e6f5334a643b09b8e5df30515e13d/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="9c4e6f5334a643b09b8e5df30515e13d-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@9c4e6f5334a643b09b8e5df30515e13d-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@9c4e6f5334a643b09b8e5df30515e13d-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;">Identify the two binary expansions of <span class="math inline">\(11/16\)</span>.</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_9c4e6f5334a643b09b8e5df30515e13d_2_1">
<fieldset aria-describedby="status_9c4e6f5334a643b09b8e5df30515e13d_2_1">
<div class="field">
<input type="checkbox" name="input_9c4e6f5334a643b09b8e5df30515e13d_2_1[]" id="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="9c4e6f5334a643b09b8e5df30515e13d_2_1-choice_0-label" for="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_9c4e6f5334a643b09b8e5df30515e13d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(0.1011(0)\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_9c4e6f5334a643b09b8e5df30515e13d_2_1[]" id="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="9c4e6f5334a643b09b8e5df30515e13d_2_1-choice_1-label" for="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_9c4e6f5334a643b09b8e5df30515e13d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(0.1011(1)\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_9c4e6f5334a643b09b8e5df30515e13d_2_1[]" id="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="9c4e6f5334a643b09b8e5df30515e13d_2_1-choice_2-label" for="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_9c4e6f5334a643b09b8e5df30515e13d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(0.1010(1)\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_9c4e6f5334a643b09b8e5df30515e13d_2_1[]" id="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="9c4e6f5334a643b09b8e5df30515e13d_2_1-choice_3-label" for="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_9c4e6f5334a643b09b8e5df30515e13d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(0.1010(0)\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_9c4e6f5334a643b09b8e5df30515e13d_2_1[]" id="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="9c4e6f5334a643b09b8e5df30515e13d_2_1-choice_4-label" for="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_9c4e6f5334a643b09b8e5df30515e13d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(0.1000(1)\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_9c4e6f5334a643b09b8e5df30515e13d_2_1[]" id="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="9c4e6f5334a643b09b8e5df30515e13d_2_1-choice_5-label" for="input_9c4e6f5334a643b09b8e5df30515e13d_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_9c4e6f5334a643b09b8e5df30515e13d_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(0.1111(0)\)</span>
</span>
</label>
</div>
<span id="answer_9c4e6f5334a643b09b8e5df30515e13d_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_9c4e6f5334a643b09b8e5df30515e13d_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_9c4e6f5334a643b09b8e5df30515e13d_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_9c4e6f5334a643b09b8e5df30515e13d" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_9c4e6f5334a643b09b8e5df30515e13d">
<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="9c4e6f5334a643b09b8e5df30515e13d-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="9c4e6f5334a643b09b8e5df30515e13d-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="9c4e6f5334a643b09b8e5df30515e13d-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-2" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@eb7e2940b0cd488db8aa64ca079a620f">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@eb7e2940b0cd488db8aa64ca079a620f" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="bdfea436018f11ef9cd816fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_eb7e2940b0cd488db8aa64ca079a620f" class="problems-wrapper" role="group"
aria-labelledby="eb7e2940b0cd488db8aa64ca079a620f-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@eb7e2940b0cd488db8aa64ca079a620f" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@eb7e2940b0cd488db8aa64ca079a620f/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="eb7e2940b0cd488db8aa64ca079a620f-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@eb7e2940b0cd488db8aa64ca079a620f-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@eb7e2940b0cd488db8aa64ca079a620f-problem-progress"></div>
<div class="problem">
<div>
<p>
<span style="font-family: 'book antiqua', palatino;">Does every real number in <span class="math inline">\([0,1]\)</span> have a name in binary notation?</span>
</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<select name="input_eb7e2940b0cd488db8aa64ca079a620f_2_1" id="input_eb7e2940b0cd488db8aa64ca079a620f_2_1" aria-describedby="status_eb7e2940b0cd488db8aa64ca079a620f_2_1">
<option value="option_eb7e2940b0cd488db8aa64ca079a620f_2_1_dummy_default">Select an option</option>
<option value="Yes"> Yes</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_eb7e2940b0cd488db8aa64ca079a620f_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_eb7e2940b0cd488db8aa64ca079a620f_2_1"/>
</div><p>
<span style="font-family: 'book antiqua', palatino;">(If the answer is yes, try to prove it. If the answer is no, find a counterexample.)</span>
</p>
<div class="solution-span">
<span id="solution_eb7e2940b0cd488db8aa64ca079a620f_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_eb7e2940b0cd488db8aa64ca079a620f" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_eb7e2940b0cd488db8aa64ca079a620f">
<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="eb7e2940b0cd488db8aa64ca079a620f-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="eb7e2940b0cd488db8aa64ca079a620f-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="eb7e2940b0cd488db8aa64ca079a620f-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-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@a307fcbb9c6644b18d0be323077e61d4" 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="bdfea436018f11ef9cd816fff75c5923">
<h2 class="hd hd-2 unit-title">The Proof</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@969708d567c94b0e87306a1840c3df02">
<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@969708d567c94b0e87306a1840c3df02" 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="bdfea436018f11ef9cd816fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Now for our proof of <span class="math inline">\(|\mathscr{P}(\mathbb{N})| = |\mathbb{R}|\)</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">What we will actually prove is <span class="math inline">\(|\mathscr{P}(\mathbb{N})| = |[0,1]|\)</span>, but this suffices to give us what we want because we know that <span class="math inline">\(|\mathbb{R}| = |[0,1]|\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Notice, first, that if <span class="math inline">\(A\)</span> is a subset of <span class="math inline">\(\mathbb{N}\)</span>, one can represent <span class="math inline">\(A\)</span> as an infinite sequence of 1s and 0s; namely: the sequence that contains a 1 in the <span class="math inline">\(n\)</span>th position if <span class="math inline">\(n\)</span> is a member of <span class="math inline">\(A\)</span>, and a 0 in the <span class="math inline">\(n\)</span>th position otherwise. So, for instance, the set of odd numbers is represented by the sequence <span class="math inline">\(\langle 0,1,0,1,0,1,\dots\rangle\)</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Notice, moreover, that each such sequence can be used to characterize a different binary expansion in <span class="math inline">\([0,1]\)</span>; namely: the expansion that starts with "0.", and is followed by digits corresponding to the members of that sequence. So, for instance, the sequence <span class="math inline">\(\langle 0,1,0,1,0,1,0,\ldots\rangle \)</span> yields the binary expansion "<span class="math inline">\(0.0101010\ldots\)"</span>, which names the number <span class="math inline">\(1/3\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">This gives us a bijection from <span class="math inline">\(\mathscr{P}(\mathbb{N}\)</span>) to the set <span class="math inline">\(B_0\)</span> of binary expansions of the form "<span class="math inline">\(0.b_1b_2\dots\)"</span>. So all we need to complete the proof is a bijection from <span class="math inline">\([0,1]\)</span> to <span class="math inline">\(B_0\)</span>. This final step would be trivial if every number in <span class="math inline">\([0,1]\)</span> was named by exactly one binary expansion in <span class="math inline">\(B_0\)</span>. But we have seen that some numbers in <span class="math inline">\([0,1]\)</span> are named by two binary expansions in <span class="math inline">\(B_0\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Fortunately, there is a nice way of getting around the problem. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Recall that there are only countably many members of <span class="math inline">\([0,1]\)</span> with more than one name in <span class="math inline">\(B_0\)</span>, since only rational numbers have multiple names. And we know from the <a href="https://courses.edx.org/courses/course-v1:MITx+24.118x+1T2018/courseware/dbf2c57bdee34ad3b0e9908b4e5fa1ad/36b5df6de2f447c5a0bf9fad342cc774/3?activate_block_id=block-v1%3AMITx%2B24.118x%2B1T2018%2Btype%40vertical%2Bblock%40a6cdec50a4714f2791e83091d29327bb">No Countable Difference Principle</a> that adding countably many members to an infinite set doesn’t change the set’s cardinality. So there must be a bijection from <span class="math inline">\([0,1]\)</span> to <span class="math inline">\(B_0\)</span>.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We have established that there is a bijection from <span class="math inline">\(\mathscr{P}(\mathbb{N}\)</span>) to <span class="math inline">\(B_0\)</span>, and that there is a bijection from <span class="math inline">\([0,1]\)</span> to <span class="math inline">\(B_0\)</span>. So it follows from the symmetry and transitivity of bijections that there must be a bijection from <span class="math inline">\(\mathscr{P}(\mathbb{N}\)</span>) to <span class="math inline">\([0,1]\)</span>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">This completes the proof.</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@f412067976564187b05f8dfd6b5134a9">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@f412067976564187b05f8dfd6b5134a9" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="bdfea436018f11ef9cd816fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_f412067976564187b05f8dfd6b5134a9" class="problems-wrapper" role="group"
aria-labelledby="f412067976564187b05f8dfd6b5134a9-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@f412067976564187b05f8dfd6b5134a9" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@f412067976564187b05f8dfd6b5134a9/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="f412067976564187b05f8dfd6b5134a9-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@f412067976564187b05f8dfd6b5134a9-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@f412067976564187b05f8dfd6b5134a9-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;">In the text above I gave a relatively informal proof for the claim that there is a bijection from <span class="math inline">\([0,1]\)</span> to <span class="math inline">\(B_0\)</span>. Give a more rigorous version of the proof.</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_f412067976564187b05f8dfd6b5134a9_2_1">
<fieldset aria-describedby="status_f412067976564187b05f8dfd6b5134a9_2_1">
<div class="field">
<input type="checkbox" name="input_f412067976564187b05f8dfd6b5134a9_2_1[]" id="input_f412067976564187b05f8dfd6b5134a9_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="f412067976564187b05f8dfd6b5134a9_2_1-choice_0-label" for="input_f412067976564187b05f8dfd6b5134a9_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_f412067976564187b05f8dfd6b5134a9_2_1">
<span style="font-family: 'book antiqua', palatino;">Done</span>
</label>
</div>
<span id="answer_f412067976564187b05f8dfd6b5134a9_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_f412067976564187b05f8dfd6b5134a9_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_f412067976564187b05f8dfd6b5134a9_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_f412067976564187b05f8dfd6b5134a9" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_f412067976564187b05f8dfd6b5134a9">
<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="f412067976564187b05f8dfd6b5134a9-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="f412067976564187b05f8dfd6b5134a9-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="f412067976564187b05f8dfd6b5134a9-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-2" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@18d72c2b1378495797195230e92cfc3d">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@18d72c2b1378495797195230e92cfc3d" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="bdfea436018f11ef9cd816fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_18d72c2b1378495797195230e92cfc3d" class="problems-wrapper" role="group"
aria-labelledby="18d72c2b1378495797195230e92cfc3d-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@18d72c2b1378495797195230e92cfc3d" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@18d72c2b1378495797195230e92cfc3d/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="18d72c2b1378495797195230e92cfc3d-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@18d72c2b1378495797195230e92cfc3d-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@18d72c2b1378495797195230e92cfc3d-problem-progress"></div>
<div class="problem">
<div>
<p>
<span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(F\)</span> be the set of functions from natural numbers to natural numbers.</span>
</p>
<p>
<span style="font-family: 'book antiqua', palatino;">Is it the case that <span class="math inline">\(|\mathbb{N}| &lt; |F|\)</span>?</span>
</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<select name="input_18d72c2b1378495797195230e92cfc3d_2_1" id="input_18d72c2b1378495797195230e92cfc3d_2_1" aria-describedby="status_18d72c2b1378495797195230e92cfc3d_2_1">
<option value="option_18d72c2b1378495797195230e92cfc3d_2_1_dummy_default">Select an option</option>
<option value="Yes"> Yes</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_18d72c2b1378495797195230e92cfc3d_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_18d72c2b1378495797195230e92cfc3d_2_1"/>
</div><p>
<span style="font-family: 'book antiqua', palatino;">(If it's true, show why. If it's false, explain why not.)</span>
</p>
<div class="solution-span">
<span id="solution_18d72c2b1378495797195230e92cfc3d_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_18d72c2b1378495797195230e92cfc3d" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_18d72c2b1378495797195230e92cfc3d">
<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="18d72c2b1378495797195230e92cfc3d-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="18d72c2b1378495797195230e92cfc3d-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="18d72c2b1378495797195230e92cfc3d-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>
© All Rights Reserved