FOM: 20:Proof Theoretic Degrees

[V. Yu. Shavrukov]

Dear Professor Friedman,


In FOM: 20:Proof Theoretic Degrees you posed some questions.


>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.

A.Mostowski, Fund.Math.49(1961)205-232  appears to be a good bet.


>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}?

These questions are indeed open apart from the fact that  PA[pi-0-1]
is not isomorphic to  PA[pi-0-(n+2)].
This is because for any sigma-0-1 sentences  x  and  y,
if  PA proves  x v y,  then  PA proves x  or  PA proves y.
The same property does not hold for sigma-0-(n+2).

It is also known that  PA[pi-0-n]  is not isomorphic to  PA[sigma-0-n]:
C.Bennet, Proc.Amer.Math.Soc.97(1986)323-327.


>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.
...
>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.

Theorem 1 is apparently old and folklore.  It is mentioned without proof
in e.g. C.Bennet, op.cit.
For the pi-0-1 case a stronger version can, I beleive, be found in
D.Misercque, C.R.Acad.Sci.(Paris)290-A(1980)571-573,
although this reference is unavailable to me at the moment.

The sentences equivalent to  not x,  where  x  satisfies the property
in Theorem 2,  are known as  pi-0-1-conservative sentences.
Sentences  x  in  PA[pi-0-1]  s.t.  not x  is or is not
pi-0-1-conservative are constructed and investigated in
D.Guaspari, Trans.Amer.Math.Soc.254(1979)47-68.
(See also  P.Lindstr"om, Proc.Amer.Math.Soc.91(1984)436-443, and
P.Lindstr"om. Aspects of Incompleteness. Springer(1997))
Similar constructions also work for  PA[pi-0-n] with any  n>0.


>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.
...
>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
...
>Has anybody seen Theorem 3 or Corollary 4 in print?

Theorem 3 is typically referred to as 'the X principle', where for X various
authors substitute various nonempty subsets of {Friedman,Goldfarb,Harrington}.
One of its earlier appearances is in
C.Smory'nski, Notre Dame J.Formal Logic 22(1981)357-374.

Corollary 4, although essentially known, has, to my best knowledge,
never been explicitly stated in print.


I would greatly appreciate it if you could comment on the following
proposition:

Questions like
>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}?
only have any intellectual signficance in as much as they provide
background to the problem
'Why is everything important linearly ordered?'


sincerely yours,
Volodya Shavrukov