https://artofproblemsolving.com/wiki/index.php?title=Godel%27s_First_Incompleteness_Theorem&feed=atom&action=historyGodel's First Incompleteness Theorem - Revision history2024-03-29T07:32:41ZRevision history for this page on the wikiMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=Godel%27s_First_Incompleteness_Theorem&diff=130059&oldid=prevMag1c: or trivial2020-07-31T22:17:10Z<p>or trivial</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 22:17, 31 July 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Gödel's First Incompleteness Theorem is a [[theorem]] that asserts that any axiomatic theory <math>F</math>, which can prove anything that [[Peano arithmetic]] can, is either inconsistent (i.e. it can both prove and disprove any given statement) or incomplete (i.e. there is a statement that it cannot prove nor disprove using the axioms only).</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Gödel's First Incompleteness Theorem is a [[theorem]] that asserts that any axiomatic theory <math>F</math>, which can prove anything that [[Peano arithmetic]] can, is either inconsistent (i.e. it can both prove and disprove any given statement) or incomplete (i.e. there is a statement that it cannot prove nor disprove using the axioms only<ins class="diffchange diffchange-inline">), or trivial (like <math>0=1=\infty</math></ins>).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The theorem is closely related to both [[Godel's Completeness Theorem]] (that a theory is consistent iff it has a model) and [[Godel's Second Incompleteness Theorem]] (that a consistent theory cannot prove its own consistency).</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The theorem is closely related to both [[Godel's Completeness Theorem]] (that a theory is consistent iff it has a model) and [[Godel's Second Incompleteness Theorem]] (that a consistent theory cannot prove its own consistency).</div></td></tr>
</table>Mag1chttps://artofproblemsolving.com/wiki/index.php?title=Godel%27s_First_Incompleteness_Theorem&diff=128353&oldid=prevDuck master: created page w/ proof of theorem2020-07-15T17:32:25Z<p>created page w/ proof of theorem</p>
<p><b>New page</b></p><div>Gödel's First Incompleteness Theorem is a [[theorem]] that asserts that any axiomatic theory <math>F</math>, which can prove anything that [[Peano arithmetic]] can, is either inconsistent (i.e. it can both prove and disprove any given statement) or incomplete (i.e. there is a statement that it cannot prove nor disprove using the axioms only).<br />
<br />
The theorem is closely related to both [[Godel's Completeness Theorem]] (that a theory is consistent iff it has a model) and [[Godel's Second Incompleteness Theorem]] (that a consistent theory cannot prove its own consistency).<br />
<br />
== Proof ==<br />
<br />
Firstly, suppose that <math>F</math> is inconsistent; i.e. it proves a [[contradiction]]. Then, by <i>ex falso quodlibet</i>, we can use that contradiction to prove any statement.<br />
<br />
Now suppose that <math>F</math> is consistent (i.e. it can prove any statement using only its axioms). Then there is a [[Turing machine]] <math>T</math> that, given (an encoding of) some Turing machine <math>T'</math> and some input <math>x</math>, (effectively) searches through every valid proof or disproof in <math>F</math>, of which there are only [[countable|countably many]], until it finds a proof or disproof of (<math>F</math>'s version of) the statement "<math>T'</math> eventually halts on input <math>x</math>". But we know that, since the [[halting problem]] is undecidable by Turing machines, there is some valid input <math>(T^*, x^*)</math> on which <math>T'</math> cannot halt, and so the statement "<math>T^*</math> eventually halts on input <math>x^*</math>" is unprovable in <math>F</math>, and we are done.<br />
<br />
== See also ==<br />
*[[Turing machine]]<br />
*[[Proof]]</div>Duck master