[FOM] Question on Pi-0-1 Degrees

Dmytro Taranovsky dmytro at mit.edu
Wed Feb 8 18:36:48 EST 2012

If T is a recursive consistent theory extending PA and L is a 
recursively enumerable distributive lattice, is L recursively embeddable 
in Pi-0-1 degrees for T?

The Godel-Rosser incompleteness theorem guarantees one non-trivial 
Pi-0-1 degree, so the question arises how rich is the structure of 
Pi-0-1 degrees and whether in a sense it is the richest possible.

Note on terminology: A Pi-0-1 statement A has greater Pi-0-1 degree than 
B for T if T proves that A->B but does not prove B->A.  A lattice is a 
partially ordered set with every pair having the least upper bound (lub) 
and the greatest lower bound (glb); it is recursively enumerable if the 
partial order, lub, and glb are recursively enumerable; an element may 
have multiple representations (for example, every Pi-0-1 statement is a 
representation of its Pi-0-1 degree), and equality is not required to be 
recursive.  A lattice is distributive if forall a,b,c ( lub(a,glb(b,c)) 
= glb(lub(a,b),lub(a,c)) and glb(a,lub(b,c)) = lub(glb(a,b),glb(a,c)) 
).   Embeddings are required to preserve the partial order structure 
(including incomparability), lub and glb.

We can also define a jump operator: j("A") = "T is consistent with A", 
and for Sigma-0-1 sound recursive T (extending PA), ask about the 
structure of Pi-0-1 degrees with the jump, including whether every 
recursively enumerable distributive lattice with (recursively 
enumerable) monotonic glb-preserving function j with forall A (j(A)>A)  
is recursively embeddable in Pi-0-1 degrees for T with the jump. (j is 
glb-preserving because, provably in T, Con(T and (A or B)) <--> Con(T 
and A) or Con(T and B).)
I would also be interested in partial results such as existence of a 
Pi-0-1 formula A such that A(0) is true and for all n, PA (Peano 
Arithmetic) proves "A(n)->Consistency(PA and A(n+1))".  (However, PA 
cannot prove "forall n (A(n)->Consistency(PA and A(n+1)))", since 
otherwise PA with thereis n A(n) would prove its own consistency.)

Dmytro Taranovsky

More information about the FOM mailing list