FOM: 20:Proof Theoretic Degrees

[Harvey Friedman]

This is the 20th in a series of self contained postings to fom
covering a wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98 10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM
19:Long Sequences  7/31/98  9:42AM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of self contained postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

The main point of this posting is Corollary 4, which establishes the
incomparability of logical strengths. Recall the discussion of the apparent
comparability of naturally occurring logical strengths as one of the great
mysteries of f.o.m.

We use PA = Peano Arithmetic as the base theory. A quasi ordering <= is a
reflexive transitive relation on a set. There is an assocaited equivalence
relation x wiggle y if and only if x <= y & y <= x.

We first consider the quasi ordering of sentences of PA under derivability
within PA. I.e., A <= B if and only if PA proves B implies A. (Some authors
may wish to use PA proves A implies B instead). Then <= has a well known
characterization which is unique up to isomorphism:
	i) the equivalence classes under wiggle are countably infinite;
	ii) >= mod wiggle is a countable atomless Boolean algebra.

We let PA[pi-0-n] be the quasi ordering of pi-0-n sentences of PA under
derivability within PA, where n >= 1. As far as I know, a characterization
of PA[pi-0-n] is an open question. However, some information is known.

Obviously, there is a minimum element (0 = 0) and a maximum element (1 =
0). It is known that there is an infinite sequence of pi-0-n sentences of
PA none of which is derivable in PA from the remaining. In fact, it is
known that there is an infinite sequence of pi-0-n sentences of PA such
that no nontrivial Boolean combination of these sentences is provable in
PA. In fact, this can be done over any consistent r.e. extension of, say,
PA.

I recall that this was rediscovered several times, and even appears in
print several times. Does anybody know who really published this or proved
this first? I know Myhill has a paper with a proof, but I'm not sure that
he is first.

Here are some questions which I believe are open.

1. Are PA[pi-0-n] and PA[pi-0-m] isomorphic?
2. Is there a nontrivial automorphism of PA[pi-0-n]?
3. Is the first order theory of PA[pi-0-n] decidable?
4. Is PA[pi-0-n] isomorphic to some {x: x >= y}?

Here is an elementary result about PA[pi-0-n]. Has anybody seen this before?

THEOREM 1. PA[pi-0-n] is dense in the sense that for all x < y there exists
z such that x < z < y.

Proof: Consider T = PA + x + noty. Then T is consistent. By Rosser's
Theorem over T, let w be neither provable nor refutable from T, where w is
pi-0-1. Set z = x & (y or w). Then z is pi-0-n. If PA + x proves z then PA
+ x + noty proves w, which is impossible. If PA + z proves y then PA + x +
w proves y, and so PA + x + noty proves notw, which is also impossible. QED

THEOREM 2. The following holds in PA[pi-0-1]. There exists x,y which are
neither minimum nor maximum such that there is no automorphism of
PA[pi-0-1] sending x to y. In fact, we can find x such that (forall z)((x
or z) provable in PA implies z is provable in PA), and we can find y such
that this fails.

Proof: Let x = Con(PA), and let PA prove (x or z). Then PA + notz proves x.
Since z is pi-0-1, obviously PA + notz proves x and "PA proves notz." Hence
PA + notz proves Con(PA + notz), and so by Godel's 2nd incompleteness
theorem, PA + notz is inconsistent. Hence PA proves z. This establishes the
first part of the final claim.

For the second part of the final claim, let y be a Rosser sentence over PA.
I.e., PA proves that y is equivalent to "every proof in PA of y has a
smaller proof in PA of noty."

On the other hand, let y' = "every proof in PA of noty has a smaller proof
in PA of y." This is an explicit definition of y', and not another self
referential construction. We claim that PA proves (y or y'). To see this,
suppose y is false. Then there is a proof in PA of y with no smaller proof
in PA of noty. Let n be the least length of a proof in PA of y. Since every
proof in PA of noty is of size >= n, every proof in PA of noty must be of
size > n. So y' follows. Finally, we claim that PA does not prove y'. To
see this, suppose PA proves y'. Note that PA + y + y' proves Con(PA). Hence
PA + y proves Con(PA). But Rosser proved that PA + Con(PA) proves Con(PA +
y). Hence PA + y proves Con(PA + y), and so PA proves noty, which is a
contradiction. QED

We now come to the consistency quasi ordering. Let PA(Con) be the quasi
ordering of setnences of PA where x <= y if and only if PA + Con(PA + y)
implies Con(PA + x). The factoring under wiggle is called the consistency
degrees (over PA). How does PA(Con) relate to PA[pi-0-1]?

THEOREM 3. Let A be any pi-0-1 sentence in PA such that PA proves A implies
Con(PA). Then there is a pi-0-1 sentence B such that PA proves that A is
equivalent to Con(PA + B). Thus the consistency degrees are isomorphic to
the pi-0-1 derivability degrees at or above Con(PA) and to the consistency
degrees of pi-0-1 sentences.

Proof: Let A be as given. By self reference, let PA prove that B is
equivalent to "every counterexample to A has a smaller proof in PA of
notB." Note that B is pi-0-1. We claim that A and Con(PA + B) are
equivalent over PA. Suppose A holds. Then Con(PA). To see that Con(PA + B),
suppose PA proves notB. Let n be the size of a proof in PA of notB. Since
there is no counterexample to A that is <= n, we see that B is provable in
PA. Hence PA is inconsistent, which is a contradiction. On the other hand,
suppose A fails. Let m be a counterexample to A. If there is a smaller
proof in PA of notB then obviously notCon(PA + B). If there is no smaller
proof in PA of notB then we have refuted B in PA, and hence also notCon(PA
+ B). QED

COROLLARY 4. There is an infinite set of incomparable consistency degrees
(of pi-0-1 sentences). Furthermore, they can be taken to all lie above any
given consistency degree below the maximum.

Proof: Since the consistency degrees (of pi-0-1 sentences) are isomorphic
to the pi-0-1 derivability degrees >= Con(PA), we merely quote the known
result that we can find an infinite set of incomparable pi-0-1 derivability
degrees over PA + Con(PA). QED

NOTE: We can, of course, replace PA throughout by anything subject to the
Godel phenomena.

Has anybody seen Theorem 3 or Corollary 4 in print? I have known them for a
long time, but did not publish them.