[FOM] Explaining Some Goedel

[Harvey Friedman]

This concerns state of the art formulations of Goedel's First and
Second Incompleteness Theorems. It has only been in recent years that,
in my view, these theorems have even been stated properly - especially
the Second. You will find that some of this is known, and I have
discussed essentially all of this already on the FOM. But I think this
is now in a clearer unified form.

i find that increasing age is an advantage in clarifying Goedel.

FIRST INCOMPLETENESS THEOREM

SPECIAL. Let pi be an interpretation of EFA (exponential function
arithmetic) in the consistent first order system T with finitely many
axioms. Then pi of some Diophantine problem is neither provable nor
refutable in T.

GENERAL. Let pi be an interpretation of EFA in the consistent first
order system T in a finite language with a recursively enumerable set
of axioms. Then the set of Diophantine problems whose interpretation
pi is provable (refutable) in T is not recursive.

EFA is exponential function arithmetic, a very weak fragment of PA.

Formulations of the above in which EFA is reduced may be problematic
using Diophantine problems, but are fine using more general universal
and existential sentences. These use the weaker system Q = Raphael
Robinson arithmetic.

NOTE: The assumption that T uses only finitely many symbols is in a
sense not necessary, but additional care is needed to formulate the
theorem properly - and this can be done.

SECOND INCOMPLETENESS THEOREM

The usual formulations have an unpleasant feature. The consistency
statement cannot be pleasantly given, and so one depends on the usual
understanding of how one would go about constructing it, without
actually constructing it or displaying it. There are new clever ways
of finessing this issue using interpretations.

FOR PRA, PA, Z_n, RTT, Z(C), ZF(C). None of these systems are
interpretable in any of its theorems. RTT is Russell Type Theory
(modern form).

PA BASED. Let pi be an interpretation of PA in the consistent first
order system T. Then T is not interpretable in any sentence of PA
whose pi is provable in T.

PRA BASED. Let pi be an interpretation of PRA in the consistent first
order system T. Then T is not interpretable in any universal sentence
of PRA whose pi is provable in T.

SEFA BASED. (SEFA is super exponential arithmetic). Let pi be an
interpretation of SEFA in the consistent first order system T. Then T
is not interpretable in any universal sentence of EFA whose pi is
provable in T.

EFA BASED. Let pi be an interpretation of EFA in the consistent first
order system T. Then T is not interpretable in any universal sentence
in 0,S,+,dot,<, whose pi is provable in T.

NOTE: We do not need to assume that T is finitely axiomatizable, or
even that T is recursively axiomatizable.

Harvey Friedman