Enumerations of Turing ideals with applications.
David E. Marker · Notre Dame Journal of Formal Logic · 1990
We examine enumerations of ideals in the Turing degrees and give several applications to the model theory of first-and second-order arithmetic.A Turing ideal is a collection of subsets of ω closed under Turing reducibility and join.If / is a countable Turing ideal we say that E is an enumeration of / if and only if / = {E n :n Eω] where E n -{m:(n,m) G E}. Enumerations of Turing ideals play an important role in the study of degrees coding recursively saturated models of Peano Arithmetic (see [5]).Our goal in this paper is to point out some simple facts about enumerations of Turing ideals and examine their consequences in the model theory of first-and second-order arithmetic. ^-incompleteness theoremsWe consider three subsystems of second-order arithmetic, RCA 0 , ACA 0 , and WKL 0 .RCA 0 is axiomatized by P~~ (Peano Arithmetic without the induction axioms), the axiom of extensionality and the schemas of Σ?-induction and recursive comprehension.WKL Q is obtained from RCA 0 by adding an axiom saying every infinite subtree of 2 <ω has an infinite path.ACA 0 is obtained from RCA 0 by adding the schema of arithmetic comprehension.For further information on these theories the reader should consult [7].Our recent interest in this subject was motivated by considering the following incompleteness theorem of Steel.Let T be an ^-consistent arithmetic extension of ACA 0 .There is an ω-model M of Tsuch that M ( = "there is no ω-model of T".Thus even in ω-logic T does not prove its own ω-consistency.Steel's result is actually much stronger.Suppose M = (ω,X) and N = (ω, Y) are models of RCAQ.We say that M » N if and only if there is E G X an enumeration of 7. If M N "there is an ω-model of T", then there is an E G X such that N =