<div class="xblock xblock-public_view xblock-public_view-vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@6532fcf56b3d47f1aff475acfbe6bd29" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<h2 class="hd hd-2 unit-title">An arithmetical language</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@199f35b3e76f42dfa25ed33aad932d39">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@199f35b3e76f42dfa25ed33aad932d39" data-has-score="False" data-runtime-version="1" data-block-type="html" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">The first step in our proof of Gödel’s Theorem is to get clear about the language we’ll be working with. That will be the aim of the present section.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">An <strong>arithmetical language</strong> is a language in which one can talk about the natural numbers and their two basic operations, addition and multiplication. Here we will be working with an especially simple arithmetical language, <span class="math inline">\(L\)</span>, which is (nearly) as simple as it can be while still being rich enough for Gödel’s Theorem to hold. The basic ingredients of <span class="math inline">\(L\)</span> are symbols of three different kinds:</span></p>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math display">\[\begin{array}{cc} \text{Arithmetical Symbol} &\text{Meaning} \\ \hline \text{ 0} & \text{ names the number zero} \\ \text{ 1} & \text{ names the number one} \\ \text{ $+$} & \text{ expresses addition} \\ \text{ $\times$} & \text{ expresses multiplication} \\ \text{ $\wedge$} & \text{ expresses exponentiation} \\ & & \\ \text{Logical Symbol} &\text{Meaning} \\ \hline \text{ $=$} & \text{ expresses identity} \\ \text{ $\neg$} & \text{ expresses negation} \\ \text{ $\&$} & \text{ expresses conjunction} \\ \text{ $\forall$} & \text{ expresses universal quantification} \\ \text{ $x_n$ (for $n \in \mathbb{N}$)} & \text{ [variable]} \\ & & \\ \text{Auxiliary Symbol} & \text{Name} \\ \hline \text{ $($} &\text{ left parenthesis}\\ \text{ $)$} &\text{ right parenthesis} \end{array}\]</span></span></p>
<p></p>
<p><span style="font-family: 'book antiqua', palatino;">(One way in which <span class="math inline">\(L\)</span> is not as simple as it could be is that the exponentiation symbol “<span class="math inline">\(\wedge\)</span>” is not necessary to prove the result. Gödel showed that, with some effort, exponentiation can be defined using “<span class="math inline">\(+\)</span>” and “<span class="math inline">\(\times\)</span>”. I include the exponentiation symbol here because it makes things much simpler.)</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@b6badeb26f874c909a0073d38fe030bd" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<h2 class="hd hd-2 unit-title">Arithmetical Symbols</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@3f08cdfd860e4f4393a170c39828fe23">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@3f08cdfd860e4f4393a170c39828fe23" data-has-score="False" data-runtime-version="1" data-block-type="html" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">The arithmetical symbols “<span class="math inline">\(0\)</span>", “<span class="math inline">\(1\)</span>", “<span class="math inline">\(+\)</span>", “<span class="math inline">\(\times\)</span>" and “<span class="math inline">\(\wedge\)</span>" work exactly as you’d expect: “<span class="math inline">\(0\)</span>" and “<span class="math inline">\(1\)</span>" name the numbers zero and one, respectively, and “<span class="math inline">\(+\)</span>", “<span class="math inline">\(\times\)</span>" and “<span class="math inline">\(\wedge\)</span>" express addition, multiplication and exponentiation, respectively. (To improve readability I will usually write “<span class="math inline">\(n^m\)"</span> instead of “<span class="math inline">\(n\wedge m\)</span>". )</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Our arithmetical symbols can be combined to form complex symbols. For instance, one can construct the complex symbols “<span class="math inline">\(0+1\)</span>” and “<span class="math inline">\((1+1) \times (1+1)\)</span>”, which name the numbers one and four, respectively. For this reason, <span class="math inline">\(L\)</span> has the expressive resources to name every natural number. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Here is a partial list:</span></p>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math display">\[\begin{array}{ccc} \text{Expression} &\text{Abbreviation} &\text{Refers to} \\ \hline \text{ $0$} & \text{ -} & \text{ number zero} \\ \text{ $1$} & \text{ -} & \text{ number one} \\ \text{ $(1+1)$} & \text{ $2$} & \text{ number two}\\ \text{ $((1+1) +1)$} & \text{ $3$} & \text{ number three}\\ \text{ $(((1+1) +1) + 1)$} & \text{ $4$} & \text{ number four}\\ \vdots & \vdots & \vdots \end{array}\]</span> Note the abbreviations in the middle column of the table above. They are not officially part of our language. Instead, they should be thought of as short-hand for the complex symbols to their left. And they’ll make a big difference. For instance, they’ll allow us to write “12” instead of the much more cumbersome: <span class="math display">\[(((((((((((1+1)+1)+1)+1)+1)+1)+1)+1)+1)+1) + 1)\]</span></span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@328899e5499a49cca712a5d62707f82a" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<h2 class="hd hd-2 unit-title">Logical Symbols</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@a2c7f28c2d64467f8ec5fd61fda76c13">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@a2c7f28c2d64467f8ec5fd61fda76c13" data-has-score="False" data-runtime-version="1" data-block-type="html" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">The arithmetical symbols we’ve discussed so far allow us to name numbers. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">But we do not yet have the resources to express any <em>claims</em> about numbers: we are not yet able to express any thoughts capable of being true or false. One cannot, for example, express the thought that two times one equals one times two. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Once the identity symbol, “=”, is in place, however, we can express the thought that two times one equals one times two as “<span class="math inline">\(2\times 1 = 1\times 2\)</span>". We can also express false thoughts; for example, “<span class="math inline">\(2=3\)</span>".</span></p>
<p><span style="font-family: 'book antiqua', palatino;">The logical operators “<span class="math inline">\(\neg\)</span>" and “<span class="math inline">\(\&\)</span>" allow us to build complex claims out of simpler ones:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">“<span class="math inline">\(\neg\)</span>" is read “It is not the case that", and can be used to formulate sentences like:</span></p>
<blockquote>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(\neg (1=2)\)</span><br /><span style="font-family: 'book antiqua', palatino;"> (<em>Read:</em> “It is not the case that one equals two")</span></p>
</blockquote>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">“<span class="math inline">\(\&\)</span>" is read “and", and can be used to formulate sentences like:</span></p>
<blockquote>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\((1+2=3) \ \& \ (2+1=3)\)</span><br /><span style="font-family: 'book antiqua', palatino;"> (<em>Read:</em> “One plus two equals three, and two plus one equals three").</span></p>
</blockquote>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">None of the symbols we have discussed so far enables us to express generality. For example, we are in a position to express commutativity claims about particular numbers (e.g. “<span class="math inline">\(2\times 1 = 1\times 2\)</span>"), but we are unable to state the the fact that multiplication is commutative <em>in general</em>. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">We cannot say:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;">For <em>any</em> numbers <span class="math inline">\(n\)</span> and <span class="math inline">\(m\)</span>, the product of <span class="math inline">\(n\)</span> and <span class="math inline">\(m\)</span> equals the product of <span class="math inline">\(m\)</span> and <span class="math inline">\(n\)</span>.</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">To express general claims of this kind in <span class="math inline">\(L\)</span> we need the quantifier-symbol “<span class="math inline">\(\forall\)</span>" and the variables “<span class="math inline">\(x_0\)</span>", “<span class="math inline">\(x_1\)</span>", “<span class="math inline">\(x_2\)</span>", …. The quantifier symbol “<span class="math inline">\(\forall\)</span>" expresses universal generalization, and is read “every number is such that". Each variable “<span class="math inline">\(x_i\)</span>" works like a name that is yet to be assigned a particular referent, and is read “it". When quantifiers and variables are combined, they allow us to say all sorts of interesting things. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">For instance:</span></p>
<blockquote>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(\forall x_0 (x_0 = x_0)\)</span><br /><span style="font-family: 'book antiqua', palatino;"> (<em>Read:</em> “every number is such that it is identical to it")</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">It is important to have variables with different indices to avoid ambiguity. Consider, for example, the sentence:</span></p>
<blockquote>
<p><span class="math inline" style="font-family: 'book antiqua', palatino;">\(\forall x_1\forall x_2(x_1\times x_2 = x_2\times x_1)\)</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">If the different variables weren’t indexed, we’d be forced to read this sentence as:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;">every number is such that every number is such that it times it equals it times it</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">which can be read in different ways, depending on what one takes the various “it”s to refer to. With indices in place, however, we avoid ambiguity by saying:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;">every number (call it <span class="math inline">\(x_1\)</span>) is such that every number (call it <span class="math inline">\(x_2\)</span>) is such that it (i.e. <span class="math inline">\(x_1\)</span>) times it (i.e. <span class="math inline">\(x_2\)</span>) equals it (i.e. <span class="math inline">\(x_2\)</span>) times it (i.e. <span class="math inline">\(x_1\)</span>)</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">or more succinctly:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;">every number <span class="math inline">\(x_1\)</span> and every number <span class="math inline">\(x_2\)</span> are such that <span class="math inline">\(x_1\)</span> times <span class="math inline">\(x_2\)</span> equals <span class="math inline">\(x_2\)</span> times <span class="math inline">\(x_1\)</span></span></p>
</blockquote>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@816802a310c94952931b8e9963a04207">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@816802a310c94952931b8e9963a04207" data-has-score="False" data-runtime-version="1" data-block-type="video" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: The Basics of L</h3>
<div
id="video_816802a310c94952931b8e9963a04207"
class="video closed"
data-metadata='{"ytTestTimeout": 1500, "autohideHtml5": false, "generalSpeed": 1.0, "sources": [], "end": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@816802a310c94952931b8e9963a04207/handler/xmodule_handler/save_user_state", "speed": null, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@816802a310c94952931b8e9963a04207/handler/transcript/available_translations", "completionEnabled": false, "transcriptLanguage": "en", "streams": "1.00:Gj6QaYyyy4A", "captionDataDir": null, "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "showCaptions": "true", "ytMetadataEndpoint": "", "autoplay": false, "recordedYoutubeIsAvailable": true, "savedVideoPosition": 0.0, "transcriptLanguages": {"en": "English"}, "poster": null, "autoAdvance": false, "prioritizeHls": false, "start": 5.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@816802a310c94952931b8e9963a04207/handler/transcript/translation/__lang__", "completionPercentage": 0.95, "duration": 0.0, "saveStateEnabled": false, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@816802a310c94952931b8e9963a04207/handler/publish_completion"}'
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="816802a310c94952931b8e9963a04207"></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_816802a310c94952931b8e9963a04207">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_816802a310c94952931b8e9963a04207">
<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@816802a310c94952931b8e9963a04207/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@816802a310c94952931b8e9963a04207/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@83bcdf62ecbb45bcabdfe80ed75526d6" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<h2 class="hd hd-2 unit-title">Abbreviations</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@cfdeb5550a0a443e85724043112b4bb8">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@cfdeb5550a0a443e85724043112b4bb8" data-has-score="False" data-runtime-version="1" data-block-type="html" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Our language <span class="math inline">\(L\)</span> is constructed on the basis of a very restricted set of symbols. But that doesn’t mean that we’re not allowed to define new notation within <span class="math inline">\(L\)</span>. Recall that we earlier introduced “<span class="math inline">\(3\)</span>” as an abbreviation for “<span class="math inline">\(((1+ 1) + 1)\)</span>”. In doing so, we didn’t really add new symbols to our language. All we did is introduce a notational <em>shortcut</em> to make it easier for us to keep track of certain strings of symbols on our original list.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Although abbreviations are avoidable in principle, they are very hard to do without in practice. In the remainder of this section I’ll mention a few additional abbreviations that will be useful in proving Gödel’s Theorem. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Here are three additions to our logical vocabulary:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>The Existential Quantifier Symbol, <span class="math inline">\(\exists\)</span></strong></span><br /><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(L\)</span> can be used to express existential statements of the form “there exists a number such that…". This is because of a happy equivalence between “there exists a number such that so-and-so" and “it is not the case that every number is such that it is not the case that so-and-so" is true. (For example, “there exists a prime number” is equivalent to “not every number is not prime”.) Accordingly, we can introduce “<span class="math inline">\(\exists x_i\)</span>” (read “there exists a number <span class="math inline">\(x_i\)</span> such that’) as an abbreviation for “<span class="math inline">\(\neg \forall x_i \neg\)</span>".</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>The Disjunction Symbol, <span class="math inline">\(\vee\)</span></strong></span><br /><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(L\)</span> can be used to express disjunctive statements of the form “either <span class="math inline">\(A\)</span> is the case or <span class="math inline">\(B\)</span> is the case (or both)". This is because of a happy equivalence between “either <span class="math inline">\(A\)</span> is the case or <span class="math inline">\(B\)</span> is the case (or both)" and “it is not the case that (not-<span class="math inline">\(A\)</span> and not-<span class="math inline">\(B\)</span>)”. (For example, “every number is even or odd (or both)” is equivalent to “every number is not such that it is both not even and not odd”.) Accordingly, we can introduce “<span class="math inline">\(A\vee B\)</span>" (read “<span class="math inline">\(A\)</span> or <span class="math inline">\(B\)</span> (or both)") as an abbreviation for “<span class="math inline">\(\neg(\neg A \ \& \ \neg B)\)</span>".</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>The Conditional Symbol, <span class="math inline">\(\supset\)</span></strong></span><br /><span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(L\)</span> can be used to express conditional statements of the form “if <span class="math inline">\(A\)</span> then <span class="math inline">\(B\)</span>". This is because of a happy equivalence (within mathematical contexts) between “if <span class="math inline">\(A\)</span> then <span class="math inline">\(B\)</span>" and “either not-<span class="math inline">\(A\)</span> or <span class="math inline">\(B\)</span>". (For instance, “if <span class="math inline">\(a\)</span> is even, then <span class="math inline">\(a\)</span> is divisible by two” is equivalent to “either <span class="math inline">\(a\)</span> is not even or <span class="math inline">\(a\)</span> is divisible by two".) Accordingly, we can introduce “<span class="math inline">\(A\supset B\)</span>" (read “if <span class="math inline">\(A\)</span> then <span class="math inline">\(B\)</span>") as an abbreviation for “<span class="math inline">\(\neg A \vee B\)</span>".</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We can also use syntactic abbreviations to enrich our arithmetical vocabulary. Suppose, for example, that we wish to introduce the less-than symbol “<span class="math inline">\(<\)</span>”. Again, we can do so by taking advantage of a happy equivalence. In general, if <span class="math inline">\(a\)</span> and <span class="math inline">\(b\)</span> are natural numbers, <span class="math inline">\(a\)</span> is smaller than <span class="math inline">\(b\)</span> if and only if <span class="math inline">\(b = a + c\)</span>, for some natural number <span class="math inline">\(c\)</span> distinct from 0. So “<span class="math inline">\(x_i < x_j\)</span>” can be defined as follows: <span class="math display">\[x_i < x_j \ \leftrightarrow_{df} \ \exists x_k( (x_j = x_i + x_k) \ \& \ \neg(x_k = 0))\]</span> Two observations:</span></p>
<ol>
<li>
<p><span style="font-family: 'book antiqua', palatino;">The symbol “<span class="math inline">\(\leftrightarrow_{df}\)</span>” is not part of <span class="math inline">\(L\)</span>. I use it to indicate that the expression to its left is to be treated as a syntactic abbreviation for the expression to its right.</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">You’ll notice that I’ve used letters rather than numbers as variable-indices. These letters should be replaced by numbers when the abbreviation is used as part of a sentence. Any numbers will do, as long as they are distinct from one another, and as long as they do not already occur as indices in the context where the abbreviation is embedded.</span></p>
</li>
</ol>
<p><span style="font-family: 'book antiqua', palatino;">Let me mention an additional example. Suppose we want to enrich <span class="math inline">\(L\)</span> with an expression “Prime(<span class="math inline">\(x_i\)</span>)” which is true of <span class="math inline">\(x_i\)</span> if and only if <span class="math inline">\(x_i\)</span> is a prime number. In general, <span class="math inline">\(a\)</span> is prime if and only if: <span class="math inline">\((i)\)</span> <span class="math inline">\(a\)</span> is greater than 1, and <span class="math inline">\((ii)\)</span> <span class="math inline">\(a\)</span> is only be the product of <span class="math inline">\(b\)</span> and <span class="math inline">\(c\)</span> if <span class="math inline">\(a = b\)</span> or <span class="math inline">\(a = c\)</span>. So “<span class="math inline">\(\text{Prime}(x_i)\)</span>” can be defined as follows: <span class="math display">\[\text{Prime}(x_i) \ \leftrightarrow_{df}(1< x_i) \ \&\ \forall x_j\forall x_k((x_i = x_j\times x_k)\supset(x_i=x_j\vee x_i=x_k))\]</span> I’ll ask you to introduce further abbreviations of this kind in the exercises below.</span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@3f6c7679405746c1af552f46ac9f4cee">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@3f6c7679405746c1af552f46ac9f4cee" data-has-score="False" data-runtime-version="1" data-block-type="video" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Defining Things in L</h3>
<div
id="video_3f6c7679405746c1af552f46ac9f4cee"
class="video closed"
data-metadata='{"ytTestTimeout": 1500, "autohideHtml5": false, "generalSpeed": 1.0, "sources": [], "end": 0.0, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3f6c7679405746c1af552f46ac9f4cee/handler/xmodule_handler/save_user_state", "speed": null, "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3f6c7679405746c1af552f46ac9f4cee/handler/transcript/available_translations", "completionEnabled": false, "transcriptLanguage": "en", "streams": "1.00:hnYYdU4tbQk", "captionDataDir": null, "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "showCaptions": "true", "ytMetadataEndpoint": "", "autoplay": false, "recordedYoutubeIsAvailable": true, "savedVideoPosition": 0.0, "transcriptLanguages": {"en": "English"}, "poster": null, "autoAdvance": false, "prioritizeHls": false, "start": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3f6c7679405746c1af552f46ac9f4cee/handler/transcript/translation/__lang__", "completionPercentage": 0.95, "duration": 0.0, "saveStateEnabled": false, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3f6c7679405746c1af552f46ac9f4cee/handler/publish_completion"}'
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="3f6c7679405746c1af552f46ac9f4cee"></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_3f6c7679405746c1af552f46ac9f4cee">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_3f6c7679405746c1af552f46ac9f4cee">
<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@3f6c7679405746c1af552f46ac9f4cee/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@3f6c7679405746c1af552f46ac9f4cee/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@7a620ac3f64347c38e0438ac92b4cace">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@7a620ac3f64347c38e0438ac92b4cace" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_7a620ac3f64347c38e0438ac92b4cace" class="problems-wrapper" role="group"
aria-labelledby="7a620ac3f64347c38e0438ac92b4cace-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@7a620ac3f64347c38e0438ac92b4cace" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@7a620ac3f64347c38e0438ac92b4cace/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="5"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="7a620ac3f64347c38e0438ac92b4cace-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@7a620ac3f64347c38e0438ac92b4cace-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@7a620ac3f64347c38e0438ac92b4cace-problem-progress"></div>
<div class="problem">
<div>
<p>
<span style="font-family: 'book antiqua', palatino;">The problems below all have at least one answer, but they may have more than one. Make sure you check all right answers. (You may avail yourself of any abbreviations previously defined.)</span>
</p>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">Introduce an abbreviation &#8220;<span class="math inline">\(x_i | x_j\)</span>&#8221;, by finding a formula of <span class="math inline">\(L\)</span> that is true of <span class="math inline">\(x_i\)</span> and <span class="math inline">\(x_j\)</span> if and only if <span class="math inline">\(x_i\)</span> divides <span class="math inline">\(x_j\)</span>, with no remainder.</span>
</p>
</blockquote>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_7a620ac3f64347c38e0438ac92b4cace_2_1">
<fieldset aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_2_1">
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_2_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="7a620ac3f64347c38e0438ac92b4cace_2_1-choice_0-label" for="input_7a620ac3f64347c38e0438ac92b4cace_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_2_1">
<span style="font-family: 'book antiqua', palatino;">\(x_i | x_j \leftrightarrow_{df} (x_j + x_i = 0)\)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_2_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="7a620ac3f64347c38e0438ac92b4cace_2_1-choice_1-label" for="input_7a620ac3f64347c38e0438ac92b4cace_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(x_i | x_j \leftrightarrow_{df} \exists x_k (x_k \times x_i = x_j)\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_2_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="7a620ac3f64347c38e0438ac92b4cace_2_1-choice_2-label" for="input_7a620ac3f64347c38e0438ac92b4cace_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_2_1">
<span style="font-family: 'book antiqua', palatino;">\(x_i | x_j \leftrightarrow_{df} \exists x_k (x_k \times x_i = x_j + x_k)\)</span>
</label>
</div>
<span id="answer_7a620ac3f64347c38e0438ac92b4cace_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_7a620ac3f64347c38e0438ac92b4cace_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">Introduce an abbreviation &#8220;<span class="math inline">\(x_i \leq x_j\)</span>&#8221;, by finding a formula of <span class="math inline">\(L\)</span> that is true of <span class="math inline">\(x_i\)</span> and <span class="math inline">\(x_j\)</span> if and only if <span class="math inline">\(x_i\)</span> is smaller than or equal to <span class="math inline">\(x_j\)</span>.</span>
</p>
</blockquote>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_7a620ac3f64347c38e0438ac92b4cace_3_1">
<fieldset aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_3_1">
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_3_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="7a620ac3f64347c38e0438ac92b4cace_3_1-choice_0-label" for="input_7a620ac3f64347c38e0438ac92b4cace_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_3_1">
<span style="font-family: 'book antiqua', palatino;">\(x_i \leq x_j \leftrightarrow_{df} (x_i &lt; x_j \ \&amp; \ x_i = x_j)\)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_3_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="7a620ac3f64347c38e0438ac92b4cace_3_1-choice_1-label" for="input_7a620ac3f64347c38e0438ac92b4cace_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_3_1">
<span style="font-family: 'book antiqua', palatino;">\(x_i \leq x_j \leftrightarrow_{df} (x_i &lt; x_j \supset x_i = x_j)\)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_3_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="7a620ac3f64347c38e0438ac92b4cace_3_1-choice_2-label" for="input_7a620ac3f64347c38e0438ac92b4cace_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_3_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(x_i \leq x_j \leftrightarrow_{df} (x_i &lt; x_j \vee x_i = x_j)\)</span>
</span>
</label>
</div>
<span id="answer_7a620ac3f64347c38e0438ac92b4cace_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_7a620ac3f64347c38e0438ac92b4cace_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">Introduce an abbreviation &#8220;<span class="math inline">\(\text{Even}(x_i)\)</span>&#8221;, by finding a formula of <span class="math inline">\(L\)</span> that is true of <span class="math inline">\(x_i\)</span> if and only if <span class="math inline">\(x_i\)</span> is an even natural number.</span>
</p>
</blockquote>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_7a620ac3f64347c38e0438ac92b4cace_4_1">
<fieldset aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_4_1">
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_4_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_4_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="7a620ac3f64347c38e0438ac92b4cace_4_1-choice_0-label" for="input_7a620ac3f64347c38e0438ac92b4cace_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_4_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(\mbox{Even}(x_i) \leftrightarrow_{df} \exists x_j(x_i = 2\times x_j)\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_4_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_4_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="7a620ac3f64347c38e0438ac92b4cace_4_1-choice_1-label" for="input_7a620ac3f64347c38e0438ac92b4cace_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_4_1">
<span style="font-family: 'book antiqua', palatino;">\(\mbox{Even}(x_i) \leftrightarrow_{df} x_i | 2\)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_4_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_4_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="7a620ac3f64347c38e0438ac92b4cace_4_1-choice_2-label" for="input_7a620ac3f64347c38e0438ac92b4cace_4_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_4_1">
<span style="font-family: 'book antiqua', palatino;">\(\mbox{Even}(x_i) \leftrightarrow_{df} 2 | x_i\)</span>
</label>
</div>
<span id="answer_7a620ac3f64347c38e0438ac92b4cace_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_7a620ac3f64347c38e0438ac92b4cace_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">Introduce an abbreviation &#8220;<span class="math inline">\(\text{Odd}(x_i)\)</span>&#8221;, by finding a formula of <span class="math inline">\(L\)</span> that is true of <span class="math inline">\(x_i\)</span> if and only if <span class="math inline">\(x_i\)</span> is an uneven natural number.</span>
</p>
</blockquote>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_7a620ac3f64347c38e0438ac92b4cace_5_1">
<fieldset aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_5_1">
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_5_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_5_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="7a620ac3f64347c38e0438ac92b4cace_5_1-choice_0-label" for="input_7a620ac3f64347c38e0438ac92b4cace_5_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_5_1">
<span style="font-family: 'book antiqua', palatino;">\(\mbox{Odd}(x_i) \leftrightarrow_{df} \neg (2 | x_i)\)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_5_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_5_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="7a620ac3f64347c38e0438ac92b4cace_5_1-choice_1-label" for="input_7a620ac3f64347c38e0438ac92b4cace_5_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_5_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(\mbox{Odd}(x_i) \leftrightarrow_{df} \exists x_j(\text{Even}(x_j) \ \&amp; \ x_i = (x_j + 1))\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_5_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_5_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="7a620ac3f64347c38e0438ac92b4cace_5_1-choice_2-label" for="input_7a620ac3f64347c38e0438ac92b4cace_5_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_5_1">
<span style="font-family: 'book antiqua', palatino;">\(\mbox{Odd}(x_i) \leftrightarrow_{df} \neg \exists x_j(\text{Even}(x_j))\)</span>
</label>
</div>
<span id="answer_7a620ac3f64347c38e0438ac92b4cace_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_7a620ac3f64347c38e0438ac92b4cace_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">For a given formula <span class="math inline">\(\phi(x_i)\)</span>, find an abbreviation &#8220;<span class="math inline">\(\exists ! x_i (\phi(x_i))\)</span>&#8221; by finding a sentence of <span class="math inline">\(L\)</span> which is true if and only if there is exactly one number <span class="math inline">\(n\)</span> such that <span class="math inline">\(\phi(n)\)</span> is the case.</span>
</p>
</blockquote>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 5" role="group"><div class="choicegroup capa_inputtype" id="inputtype_7a620ac3f64347c38e0438ac92b4cace_6_1">
<fieldset aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_6_1">
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_6_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_6_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="7a620ac3f64347c38e0438ac92b4cace_6_1-choice_0-label" for="input_7a620ac3f64347c38e0438ac92b4cace_6_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_6_1">
<span style="font-family: 'book antiqua', palatino;">\(\exists ! x_i (\phi(x_i)) \leftrightarrow_{df} \exists x_i (\phi(x_i)) \ \&amp; \ \forall x_j \forall x_k ((\phi(x_j) \&amp; \phi(x_k)) \supset x_j = x_k)\)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_6_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_6_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="7a620ac3f64347c38e0438ac92b4cace_6_1-choice_1-label" for="input_7a620ac3f64347c38e0438ac92b4cace_6_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_6_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math display">\(\exists ! x_i (\phi(x_i)) \leftrightarrow_{df} \exists x_i (\phi(x_i) \ \&amp; \ \forall x_j (\phi(x_j) \supset x_j = x_i))\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_7a620ac3f64347c38e0438ac92b4cace_6_1[]" id="input_7a620ac3f64347c38e0438ac92b4cace_6_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="7a620ac3f64347c38e0438ac92b4cace_6_1-choice_2-label" for="input_7a620ac3f64347c38e0438ac92b4cace_6_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_7a620ac3f64347c38e0438ac92b4cace_6_1">
<span style="font-family: 'book antiqua', palatino;">\(\exists ! x_i (\phi(x_i)) \leftrightarrow_{df} \exists x_i (\phi(x_i)) \ \&amp; \ \neg \exists x_j (\phi(x_j))\)</span>
</label>
</div>
<span id="answer_7a620ac3f64347c38e0438ac92b4cace_6_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_7a620ac3f64347c38e0438ac92b4cace_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</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_7a620ac3f64347c38e0438ac92b4cace" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_7a620ac3f64347c38e0438ac92b4cace">
<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="7a620ac3f64347c38e0438ac92b4cace-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="7a620ac3f64347c38e0438ac92b4cace-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="7a620ac3f64347c38e0438ac92b4cace-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-3" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@71d24ddb7c284e959de4003686cddcf3">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@71d24ddb7c284e959de4003686cddcf3" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_71d24ddb7c284e959de4003686cddcf3" class="problems-wrapper" role="group"
aria-labelledby="71d24ddb7c284e959de4003686cddcf3-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@71d24ddb7c284e959de4003686cddcf3" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@71d24ddb7c284e959de4003686cddcf3/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="71d24ddb7c284e959de4003686cddcf3-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@71d24ddb7c284e959de4003686cddcf3-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@71d24ddb7c284e959de4003686cddcf3-problem-progress"></div>
<div class="problem">
<div>
<p>
<span style="font-family: 'book antiqua', palatino;">Express each of the following claims in <span class="math inline">\(L\)</span>. As before, problems all have at least one answer, but they may have more than one. Make sure you check all right answers. (You may avail yourself of any abbreviations previously defined.)</span>
</p>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">There is at least one prime number.</span>
</p>
</blockquote>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_71d24ddb7c284e959de4003686cddcf3_2_1">
<fieldset aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_2_1">
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_2_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="71d24ddb7c284e959de4003686cddcf3_2_1-choice_0-label" for="input_71d24ddb7c284e959de4003686cddcf3_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_2_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(\exists x_1 (\text{Prime}(x_1))\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_2_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="71d24ddb7c284e959de4003686cddcf3_2_1-choice_1-label" for="input_71d24ddb7c284e959de4003686cddcf3_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_2_1">
<span style="font-family: 'book antiqua', palatino;">\(\exists x_1 (x_1 | x_1 \ \&amp; \ \neg(2 | x_1)) \)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_2_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="71d24ddb7c284e959de4003686cddcf3_2_1-choice_2-label" for="input_71d24ddb7c284e959de4003686cddcf3_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_2_1">
<span style="font-family: 'book antiqua', palatino;">\(\exists x_1 (1 &lt; x_1 \ \&amp; \ \forall x_2 (x_2 | x_1 \supset (x_2 = 1 \vee x_2 = x_1)))\)</span>
</label>
</div>
<span id="answer_71d24ddb7c284e959de4003686cddcf3_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_71d24ddb7c284e959de4003686cddcf3_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">Every number is even or odd.</span>
</p>
</blockquote>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_71d24ddb7c284e959de4003686cddcf3_3_1">
<fieldset aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_3_1">
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_3_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="71d24ddb7c284e959de4003686cddcf3_3_1-choice_0-label" for="input_71d24ddb7c284e959de4003686cddcf3_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_3_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(\forall x_1 (\text{Even}(x_1) \vee \text{Odd}(x_1))\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_3_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="71d24ddb7c284e959de4003686cddcf3_3_1-choice_1-label" for="input_71d24ddb7c284e959de4003686cddcf3_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_3_1">
<span style="font-family: 'book antiqua', palatino;">\(\forall x_1 (2 | x_1 \vee \neg(2 |x_1))\)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_3_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="71d24ddb7c284e959de4003686cddcf3_3_1-choice_2-label" for="input_71d24ddb7c284e959de4003686cddcf3_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_3_1">
<span style="font-family: 'book antiqua', palatino;">\(\forall x_1 (2 | x_1 \vee x_1|2)\)</span>
</label>
</div>
<span id="answer_71d24ddb7c284e959de4003686cddcf3_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_71d24ddb7c284e959de4003686cddcf3_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">Every even number greater than two is the sum of two primes. (Goldbach's Conjecture)</span>
</p>
</blockquote>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_71d24ddb7c284e959de4003686cddcf3_4_1">
<fieldset aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_4_1">
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_4_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_4_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="71d24ddb7c284e959de4003686cddcf3_4_1-choice_0-label" for="input_71d24ddb7c284e959de4003686cddcf3_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_4_1">
<span style="font-family: 'book antiqua', palatino;">\(\exists x_1 ((\mbox{Even}(x_1) \ \&amp; \ 2 &lt; x_1) \ \supset \ \forall x_2 \forall x_3 (\mbox{Prime}(x_2) \ \&amp; \ \mbox{Prime}(x_3) \ \&amp;\ x_1 = x_2 + x_3)\)</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_4_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_4_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="71d24ddb7c284e959de4003686cddcf3_4_1-choice_1-label" for="input_71d24ddb7c284e959de4003686cddcf3_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_4_1">
<span style="font-family: 'book antiqua', palatino;">
<span class="math inline">\(\forall x_1 ((\mbox{Even}(x_1) \ \&amp; \ 2 &lt; x_1) \ \supset \ \exists x_2 \exists x_3 (\mbox{Prime}(x_2) \ \&amp; \ \mbox{Prime}(x_3) \ \&amp;\ x_1 = x_2 + x_3)\)</span>
</span>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_71d24ddb7c284e959de4003686cddcf3_4_1[]" id="input_71d24ddb7c284e959de4003686cddcf3_4_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="71d24ddb7c284e959de4003686cddcf3_4_1-choice_2-label" for="input_71d24ddb7c284e959de4003686cddcf3_4_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_71d24ddb7c284e959de4003686cddcf3_4_1">
<span style="font-family: 'book antiqua', palatino;">\(\forall x_1 ((\mbox{Even}(x_1) \ \&amp; \ 2 &lt; x_1) \ \supset \ \forall x_2 \forall x_3 (\mbox{Prime}(x_2) \ \&amp; \ \mbox{Prime}(x_3) \ \&amp;\ x_1 = x_2 + x_3)\)</span>
</label>
</div>
<span id="answer_71d24ddb7c284e959de4003686cddcf3_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_71d24ddb7c284e959de4003686cddcf3_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</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_71d24ddb7c284e959de4003686cddcf3" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_71d24ddb7c284e959de4003686cddcf3">
<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="71d24ddb7c284e959de4003686cddcf3-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="71d24ddb7c284e959de4003686cddcf3-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="71d24ddb7c284e959de4003686cddcf3-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-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@2749e3650fb445d19ee671e1194f1e9e" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<h2 class="hd hd-2 unit-title">Simple, yet mighty</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@0c76a7f3bf69492c8d14ef3c6f868920">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:MITx+24.118x+2T2020" data-runtime-class="LmsRuntime" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@0c76a7f3bf69492c8d14ef3c6f868920" data-has-score="False" data-runtime-version="1" data-block-type="html" data-request-token="e6416f18edae11eeb4571299a322540b" data-graded="False">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Our language <span class="math inline">\(L\)</span> turns out to be extraordinarily powerful. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">It can be used to formulate not only mundane arithmetical claims like “<span class="math inline">\(2 + 3 = 5\)</span>”, but also claims that have taken us hundreds of years to prove, like Fermat’s Last Theorem, and hypotheses that are yet to be proved, like Goldbach’s Conjecture. (Remember that formulating a hypothesis is not the same as proving the hypothesis, and that all we are talking about here is the fact that complex mathematical claims can be <em>formulated</em> in <span class="math inline">\(L\)</span>.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">The fact that <span class="math inline">\(L\)</span> is such an expressive language guarantees that if we were able to construct a Turing Machine that outputted every truth of <span class="math inline">\(L\)</span> (and no falsehoods), we would have succeeded in concentrating a huge wealth of mathematical knowledge in a finite list of lines of code. Implicit in our program would be not just all the arithmetic we learned in school, but also remarkable mathematical results. If we had a machine that outputted all and only the true sentences in <span class="math inline">\(L\)</span>, then—since we can express, for example, Goldbach’s Conjecture in <span class="math inline">\(L\)</span>—it would give us way of knowing for certain whether Goldbach’s Conjecture is true. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Alas, Gödel’s Theorem shows that the dream of constructing such a machine is not to be.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Gödel’s Theorem is a pretty robust result, which doesn’t depend on the details of one’s arithmetical language. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">All that is required to prove the theorem is that one’s language be rich enough for the following lemma to be provable:</span></p>
<p style="padding-left: 30px;"><span style="font-family: 'book antiqua', palatino;"><strong>Lemma</strong></span><br /><span style="font-family: 'book antiqua', palatino;">The language contains a formula (abbreviated “<span class="math inline">\(\mbox{Halt}(k)\)</span>") which is true if and only if the <span class="math inline">\(k\)</span>th Turing Machine halts on input <span class="math inline">\(k\)</span>.</span></p>
<p></p>
<p><span style="font-family: 'book antiqua', palatino;">In an Appendix at the end of this chapter I show that our simple language <span class="math inline">\(L\)</span> is indeed rich enough for the lemma to hold.</span></p>
<p></p>
</div>
</div>
</div>
</div>
© All Rights Reserved