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)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
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
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.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

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

Recent downloads (6 months)

1 ( #458,338 of 1,938,823 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.