Changes

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

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

'''Gödel's First Incompleteness Theorem''':  If T is any [[consistency|consistent]], [[sound]], [[recursion|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.

'''Gödel's First Incompleteness Theorem''':  If T is any [[consistency|consistent]], [[sound]], [[recursion|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 language|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.

The statement G_T says "G_T is not provable in T".  This statement is encoded in [[number theory]]—symbols of [[first-order language|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.

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 Gödel, is the:

The first incompleteness theorem is itself a theorem of Peano Arithmetic.  A corollary of this fact, noted independently by [[John von Neumann]] and Gödel, is the: