[FOM] Consistency strength order
Robert M. Solovay
solovay at Math.Berkeley.EDU
Wed May 7 03:31:47 EDT 2008
Here is the proof of my theorem concerning the various notions of
consistency strength. (Note that I need a slightly stronger theory to
prove that theta is true then I asserted in my previous letter.)
Let me introduce the theory T in which the proof will be carried
out.
T has two extensions to ZFC:
1) ZFC + I is consistent. (I is the proposition "There is a strongly
inaccessible cardinal".)
2) ZFC has an omega model.
The theorem concerns a certain sentence theta [which we will
explicitly construct]:
Main Theorem(T)
1) theta;
2) Suppose sigma is one of theta or not theta; suppose alpha is
[the translation into set theory of] an arithmetic sentence. Suppose that
ZFC proves "sigma implies alpha". Then ZFC proves alpha.
3) The following is provable in PRA (primitive recursive arithmetic):
Con(ZFC + theta) iff Con(ZFC + "there is an inaccessible cardinal")
**************************************************************************
We turn to the proof. Let A be the set of Godel numbers of true arithmetic
sentences. We shall presently describe a certain function g: omega ->
omega which is primitive recursive in A. It will be evident from the
description [and ZFC can prove]:
(a) If g(n) is > 0 then g(n+1) = g(n).
Hence the limit of g(n) as n tends to infinity exists. Call it L.
theta is the statement "L is even". [Take this as asserting as well that
the limit in question exists.]
Though this is not key, it will also be clear that L <= 2.
During the definition of g, we shall need to refer to theta. This apparant
circularity is handled using a suitable variant of the recursion theorem.
So let's start the definiton of g. We set g(0) = 0 and precede to define
g(n) by induction on n. So suppose that g(n) has been defined.
If g(n) > 0 set g(n+1) = g(n).
If g(n) = 0, we set g(n+1) = 0 unless an event happened at time n.
There are two sorts of events:
(a) n is the Godel number of a proof in ZFC of "There is no inaccessible
cardinal"[NIC]. Then we set g(n+1) = 1.
(b) n is the Godel number of a proof in ZFC of an implication of the form
"alpha implies beta" where alpha is a **true** arithmetic sentence and
beta is one of theta or "not theta". [We use the oracle A to determine
whether or not an arithmetic sentence is true.]
There are two subcases:
(b1) beta is theta. Then we set g(n+1) = 1;
(b2) beta is "not theta". Then we set g(n+1) = 2.
This completes the definiton of g. It remains to see that theta
has the desired properties.
I take it as evident that cases (a) and (b) can't both occur for
the same n.
Before turning to the detailed proof we make some remarks about
the intuitions. Case (a) is devoted to insuring the equiconsistency result
in (3) of our theorem. Case (b) has two purposes. We are taking actions to
insure that case (b) does not arise. So if we can prove theta from ZFC +
"True arithmetic", we take action to make theta false; and if we can prove
not theta from the stated theory, we make theta true. Also, case (b) will
help us prove claim 2 of the theorem.
It will eventually turn out that g is identically zero. But we can
only prove that in T [and not in ZFC].
Although I am not relying on the results of that paper, the
methods of the current proof are very similar to those of my paper
"Provability Interpretations of Modal Logic".
The following lemma is provable in PRA. Notice that it just asserts
that for each integer n, a certain sentence psi(\textbf{n}) is provable in
ZFC. It is definitely not true that ZFC proves "for all n in omega,
psi(n)".
Main Lemma (PRA). Let n in omega.
If for no m <= n is m the Godel number of a proof in ZFC of NIC
then ZFC proves "g(\textbf{n+1}) = 0.
If for some m <= n, m is the Godel number of a proof in ZFC of
NIC then ZFC proves "g(textbf{n+1}) = 1".
Remark. Of course, with the usual presentations of ZFC, there are no terms
other than variables and certainly no numerals. Instead, one constructs a
sequence of formulas chi_n such that chi_n(x) expresses "x = \testbf{n}".
Then one expresses psi(\textbf{n}) as "(forall x) (chi_n(x) ==> psi(x))".
The proof splits into a number of cases, most of which are trivial. We
consider two of the cases.
Case A. n is the Godel number of a proof of NIC in ZFC. For no m < n is m
the Godel number of a proof of NIC in ZFC.
Then using our induction hypothesis, there is a proof in ZFC of
"g(\textbf{n}) = 0". There is also a proof in ZFC of the "primitive
recursive fact" that n is the Godel number of a proof of "there is no
inaccessible cardinal" in ZFC. Putting these together with the definition of
g we easily get a proof in ZFC of g(\textbf{n+1}) = 1.
Case B. n is the Godel number of a proof in ZFC of a sentence of the form
"alpha implies beta" where alpha is an arithmetic sentence and beta is one
of theta and "not theta".
We shall show that there is a proof in ZFC of "not alpha". Granted
this, we can put together proofs in ZFC of "g(\textbf{n}) = 0" (provided
by our induction hypothesis), of "n is the Godel number of a proof ..."
and "not alpha" to get a proof (using the definition
of g) that g(\textbf{n+1}) = 0.
We work in ZFC + "alpha" and derive a contradiction. The proof
splits into two entirely similar cases according to whether beta is theta
or "not theta". We consider just the subcase where beta is theta.
We work in "ZFC + alpha". First n itself gives a proof in "ZFC +
alpha" of theta. Next since "ZFC + alpha" thinks alpha is true, we can see
[using our inductive hypothesis that ZFC proves g(\textbf{n}) = 0] that
g(\textbf{n+1}) = 1. But from this it easily follows that "not theta". We
have our desired contradiction from ZFC + "alpha". This completes our
discussion of the proof of the Main Lemma.
We extract a corollary from the proof which we will need later.
Corollary(PRA). Suppose that m is an integer and that for no n <= m is the
n the Godel number of a proof in ZFC of NIC. Suppose that m is the Godel
number of a proof in ZFC of a sentence of the form "alpha implies beta"
where alpha is arithmetic and beta is one of theta, "not theta". Then ZFC
proves "not alpha".
It is now easy to complete the proof of our theorem. First
consider part 3. We work in PRA.
First assume that ZFC proves NIC. Let m be the least Godel number
of such a proof. By the main lemma, ZFC proves g(\textbf{m+1}) = 1. Hence
ZFC proves "not theta".
Next suppose that ZFC proves "not theta". Let m be the least Godel
number of a proof in ZFC of "0=0 implies (not theta)". We have to show
that "ZFC + I" is inconsistent. If there is a proof in ZFC of NIC with
Godel number less than m, then we are done. If not, by the corollary, ZFC
proves "not 0 = 0". Hence, ZFC (and a fortiori ZFC + I) is inconsistent.
Part 2 of the theorem follows immediately from the Corollary by
taking contrapositives.
We turn to Part 1. We shall show, in fact that g is identically
zero. This will imply, of course, that L = 0 and hence theta is true.
We argue in T. We know that ZFC + I is consistent. Hence, by the
main lemma, for all n, ZFC proves "g(n) = 0". But T can prove the
soundness of ZFC for statements of this form. (This follows from
assumption 2) about T.) So really, g is identically 0.
We remark that it follows from part 2 of the theorem that any
Boolean combination of theta and arithmetic sentences which is provable in
ZFC is provable as well when theta is replace by any other sentence sigma.
We omit the easy proof which uses the fact that arithmetic sentences are
closed under Boolean combinations. And all we used about
Con(ZFC +I) is that it is a Pi^0_1 sentence which implies (in PRA)
Con(ZFC).
--Bob Solovay
More information about the FOM
mailing list