# Completions of PA: Models and enumerations of representable sets

Journal of Symbolic Logic 63 (3):1063-1082 (1998)
 Abstract 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 Logic and Philosophy of Logic (categorize this paper) DOI 10.2307/2586727 Options Save to my reading list Follow the author(s) Edit this record My bibliography Export citation Mark as duplicate Request removal from index
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 30,719

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
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.
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.
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.