Systems for which Gödel Theorems are Provable

Anil Mitra, December 2013—May  2015

Home

To have a Gödel theorem be provable for a system, the system must have such structure as to be able to describe a statement of the system that refers to itself as an unprovable (Gödel) statement.

Then, if the Gödel statement were false it could be proved and so must be true; therefore, since the statement says it is unprovable it must be unprovable—(if the system is consistent); and adding it as a axiom does not get around the problem because then another Gödel statement can be found.

Roughly, the two Gödel theorems are (1) Sufficiently rich and consistent systems cannot be complete (as above) and (2) The consistency of such systems cannot be proved within the system.

Arithmetic with multiplication, addition, and first order logic is rich enough to have a Gödel theorem; Presburger arithmetic (no multiplication, but multiplication can be simulated by additions) and Euclidean Geometry are seemingly not rich enough.

It was an achievement of Gödel he found a way to encode the theorems of arithmetic as formulas of arithmetic and then to encode a liar paradox like statement in arithmetic, creating a well-formed mathematical statement that referred to itself as an unprovable statement.

There are elementary ways to resolve the liar paradox. One is to recognize that not every apparently well formed declarative sentence must have a truth value. It does not seem that there is a similar way to defuse Gödel sentences since they refer to their provability rather than truth.

It is interesting that while the simpler (than standard elementary arithmetic) Presburger arithmetic is complete, the apparently more complex (than as above) elementary algebra is also complete. I suggest that Gödel theorem type limits arise when expressive power for a system exceeds its representational power. For more on this see the essential version of the way of being.