FOM: 20:Proof Theoretic Degrees

V. Yu. Shavrukov vys1 at mcs.le.ac.uk
Thu Aug 20 07:34:42 EDT 1998


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





More information about the FOM mailing list