[FOM] Consistency strength order

[Robert M. Solovay]

  	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