Difference between revisions of "Godel's Incompleteness Theorems"
(Made changes to make this more precise.) |
m (sp "Arithmetic" (still bored)) |
||
| Line 8: | Line 8: | ||
Recursively enumerable (r.e.) theories are theories that can be written down in a mechanical way. The restriction to recursively enumerable theories is required, since it is easy to construct non-r.e. theories that are complete--for example, the theory that contains exactly all true statements of number theory is complete, but cannot be written down in a mechanical way. | Recursively enumerable (r.e.) theories are theories that can be written down in a mechanical way. The restriction to recursively enumerable theories is required, since it is easy to construct non-r.e. theories that are complete--for example, the theory that contains exactly all true statements of number theory is complete, but cannot be written down in a mechanical way. | ||
| − | The first incompleteness theorem is itself a theorem of Peano | + | The first incompleteness theorem is itself a theorem of Peano Arithmetic. A corollary of this fact, noted independently by [[John von Neumann]] and Godel, is the: |
'''Godel's Second Incompleteness Theorem''': If T is any consistent, sound, recursively enumerable first-order theory containing the axioms of Peano Arithmetic, then T cannot prove its own consistency. In particular, Peano Arithmetic cannot prove its own consistency. This means that the consistency of the axioms of Peano Arithmetic and stronger mathematical theories must be justified in other ways, usually by appealing to the fact that the axioms are obviously true or by appealing to the fact that no one has yet derived an inconsistency. | '''Godel's Second Incompleteness Theorem''': If T is any consistent, sound, recursively enumerable first-order theory containing the axioms of Peano Arithmetic, then T cannot prove its own consistency. In particular, Peano Arithmetic cannot prove its own consistency. This means that the consistency of the axioms of Peano Arithmetic and stronger mathematical theories must be justified in other ways, usually by appealing to the fact that the axioms are obviously true or by appealing to the fact that no one has yet derived an inconsistency. | ||
[[category:mathematics]] | [[category:mathematics]] | ||
Revision as of 03:37, January 27, 2008
Gödel's Incompleteness Theorems are two theorems published in 1931 by Kurt Gödel that show that all sufficiently strong first-order theories can never yield answers to all mathematical questions--they are incomplete.
Godel's First Incompleteness Theorem: If T is any consistent, sound, recursively enumerable first-order theory containing the axioms of Peano Arithmetic, there is a sentence G_T such that T cannot prove G_T and such that T cannot prove ~G_T. This means that T is not complete: there is some statement (G_T) that cannot be proved or refuted in the theory T.
The statement G_T says "G_T is not provable in T". This statement is encoded in number theory--symbols of first-order logic are assigned numbers in such a way so that statements in logic can be viewed as statements about numbers. Further, this statement refers to itself; that this is possible is the key to Godel's argument.
Recursively enumerable (r.e.) theories are theories that can be written down in a mechanical way. The restriction to recursively enumerable theories is required, since it is easy to construct non-r.e. theories that are complete--for example, the theory that contains exactly all true statements of number theory is complete, but cannot be written down in a mechanical way.
The first incompleteness theorem is itself a theorem of Peano Arithmetic. A corollary of this fact, noted independently by John von Neumann and Godel, is the:
Godel's Second Incompleteness Theorem: If T is any consistent, sound, recursively enumerable first-order theory containing the axioms of Peano Arithmetic, then T cannot prove its own consistency. In particular, Peano Arithmetic cannot prove its own consistency. This means that the consistency of the axioms of Peano Arithmetic and stronger mathematical theories must be justified in other ways, usually by appealing to the fact that the axioms are obviously true or by appealing to the fact that no one has yet derived an inconsistency.
