Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Godel's First Incompleteness Theorem"

(created page w/ proof of theorem)
 
(or trivial)
 
Line 1: Line 1:
−
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).
+
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), or trivial (like <math>0=1=\infty</math>).
  
 
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).
 
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).

Latest revision as of 18:17, 31 July 2020

Gödel's First Incompleteness Theorem is a theorem that asserts that any axiomatic theory $F$, 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), or trivial (like $0=1=\infty$).

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).

Proof

Firstly, suppose that $F$ is inconsistent; i.e. it proves a contradiction. Then, by ex falso quodlibet, we can use that contradiction to prove any statement.

Now suppose that $F$ is consistent (i.e. it can prove any statement using only its axioms). Then there is a Turing machine $T$ that, given (an encoding of) some Turing machine $T'$ and some input $x$, (effectively) searches through every valid proof or disproof in $F$, of which there are only countably many, until it finds a proof or disproof of ($F$'s version of) the statement "$T'$ eventually halts on input $x$". But we know that, since the halting problem is undecidable by Turing machines, there is some valid input $(T^*, x^*)$ on which $T'$ cannot halt, and so the statement "$T^*$ eventually halts on input $x^*$" is unprovable in $F$, and we are done.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Godel%27s_First_Incompleteness_Theorem&oldid=130059"