Completions of PA: Models and enumerations of representable sets

Journal of Symbolic Logic 63 (3):1063-1082 (1998)
We generalize a result on True Arithmetic (TA) by Lachlan and Soare to certain other completions of Peano Arithmetic (PA). If T is a completion of PA, then Rep(T) denotes the family of sets $X \subseteq \omega$ for which there exists a formula φ(x) such that for all n ∈ ω, if n ∈ X, then $\mathscr{T} \vdash \varphi(S^{(n)})$ (0)) and if $n \not\in X$ , then $\mathscr{T} \vdash \neg\varphi(S^{(n)}(0))$ . We show that if $\mathscr{S,J} \subseteq \mathscr{P}(\omega)$ such that S is a Scott set, J is a jump ideal, $\mathscr{S} \subset \mathscr{J}$ and for all X ∈ J, there exists C ∈ S such that C is a "coding" set for the family of subtrees of 2 $^{ computable in X, and if T is a completion of PA such that Rep(T) = S, then there exists a model A of T such that J is the Scott set of A and no enumeration of Rep(T) is computable in A. The model A of T is obtained via a new notion of forcing. Before proving our main result, we demonstrate the existence of uncountably many different pairs (S,J) satisfying the conditions of our theorem. This involves a new characterization of 1-generic sets as coding sets for the computable subtrees of 2 $^{ . In particular, $C \subseteq \omega$ is a coding set for the family of subtrees of 2 $^{ computable in X if and only if for all trees T $\subseteq 2^{ computable in X, if χ C is a path through T, then there exists σ ∈ T such that $\sigma \subset \chi_C$ and every extension of σ is in T. Jockusch noted a connection between 1-generic sets and coding sets for computable subtrees of 2 $^{ . We show they are identical
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2586727
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 30,719
Through your library
References found in this work BETA
Upper Bounds for the Arithmetical Degrees.M. Lerman - 1983 - Annals of Pure and Applied Logic 29 (3):225-254.

Add more references

Citations of this work BETA
1998-99 Annual Meeting of the Association for Symbolic Logic.Sam Buss - 1999 - Bulletin of Symbolic Logic 5 (3):395-421.

Add more citations

Similar books and articles
The Reals in Core Models.Philip Welch - 1987 - Journal of Symbolic Logic 52 (1):64-67.
Covering Analytic Sets by Families of Closed Sets.Slawomir Solecki - 1994 - Journal of Symbolic Logic 59 (3):1022-1031.
Almost Weakly 2-Generic Sets.Stephen A. Fenner - 1994 - Journal of Symbolic Logic 59 (3):868-887.
Cohen-Stable Families of Subsets of Integers.Miloš S. Kurilić - 2001 - Journal of Symbolic Logic 66 (1):257-270.
Existence of Some Sparse Sets of Nonstandard Natural Numbers.Renling Jin - 2001 - Journal of Symbolic Logic 66 (2):959-973.
Solovay's Theorem Cannot Be Simplified.Andrew Arana - 2001 - Annals of Pure and Applied Logic 112 (1):27-41.
Added to PP index

Total downloads
2 ( #797,632 of 2,197,306 )

Recent downloads (6 months)
1 ( #299,047 of 2,197,306 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature