Difference between revisions of "Godel's First Incompleteness Theorem"
Duck master (talk | contribs) (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). | ||
Revision as of 17:17, 31 July 2020
Gödel's First Incompleteness Theorem is a theorem that asserts that any axiomatic theory 
, 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 
).
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 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 is consistent (i.e. it can prove any statement using only its axioms). Then there is a Turing machine 
that, given (an encoding of) some Turing machine 
and some input 
, (effectively) searches through every valid proof or disproof in , of which there are only countably many, until it finds a proof or disproof of ('s version of) the statement " eventually halts on input ". But we know that, since the halting problem is undecidable by Turing machines, there is some valid input 
on which cannot halt, and so the statement "
eventually halts on input 
" is unprovable in , and we are done.
