[FOM] FOM: 20:Proof Theoretic Degrees

V. Yu. Shavrukov vshavruk at science.uva.nl
Wed Mar 19 17:49:46 EDT 2008

On Aug 2, 1998, at 22:37, Harvey Friedman wrote:

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

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

A negative answer to question 3 is now contained in a preliminary  
version of

"Effectively inseparable Boolean algebras in lattices of sentences"

found at  http://staff.science.uva.nl/~vshavruk/

best wishes,
Volodya Shavrukov

More information about the FOM mailing list