# 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 (categorize this paper)
DOI 10.2307/2586727
Options
 Save to my reading list Follow the author(s) My bibliography Export citation Find it on Scholar Edit this record Mark as duplicate Revision history Request removal from index

 PhilPapers Archive Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 22,660 External links 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) Through your library Sign in / register and configure your affiliation(s) to use this tool.Configure custom resolver
References found in this work BETA
M. Lerman (1985). Upper Bounds for the Arithmetical Degrees. Annals of Pure and Applied Logic 29 (3):225-254.
Citations of this work BETA
Similar books and articles

2009-01-28

2 ( #728,540 of 1,938,823 )