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)
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
 
Download options
PhilPapers Archive


Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 11,399
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

No references found.

Citations of this work BETA

No citations found.

Similar books and articles
Analytics

Monthly downloads

Sorry, there are not enough data points to plot this chart.

Added to index

2009-01-28

Total downloads

1 ( #446,540 of 1,102,965 )

Recent downloads (6 months)

1 ( #297,509 of 1,102,965 )

How can I increase my downloads?

My notes
Sign in to use this feature


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