[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.)
Sincerely,
Dmytro Taranovsky
More information about the FOM
mailing list