Completions of PA: Models and Enumerations of Representable Sets
McAllister, Alex M.
J. Symbolic Logic, Tome 63 (1998) no. 1, p. 1063-1082 / Harvested from Project Euclid
We generalize a result on True Arithmetic ($\mathscr{TA}$) by Lachlan and Soare to certain other completions of Peano Arithmetic ($\mathscr{PA}$). If $\mathscr{T}$ is a completion of $\mathscr{PA}$, then Rep($\mathscr{T}$) denotes the family of sets $X \subseteq \omega$ for which there exists a formula $\varphi$(x) such that for all $n \in \omega$, if $n \in 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 $\mathscr{S}$ is a Scott set, $\mathscr{J}$ is a jump ideal, $\mathscr{S} \subset \mathscr{J}$ and for all $X \in \mathscr{J}$, there exists $C \in \mathscr{S}$ such that C is a "coding" set for the family of subtrees of 2$^{<\omega}$ computable in X, and if $\mathscr{T}$ is a completion of $\mathscr{PA}$ such that Rep($\mathscr{T}$) = $\mathscr{S}$, then there exists a model $\mathscr{A}$ of $\mathscr{T}$ such that $\mathscr{J}$ is the Scott set of $\mathscr{A}$ and no enumeration of Rep($\mathscr{T}$) is computable in $\mathscr{A}$. The model $\mathscr{A}$ of $\mathscr{T}$ is obtained via a new notion of forcing. Before proving our main result, we demonstrate the existence of uncountably many different pairs ($\mathscr{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$^{<\omega}$. In particular, $C \subseteq \omega$ is a coding set for the family of subtrees of 2$^{<\omega}$ computable in X if and only if for all trees T $\subseteq 2^{<\omega}$ computable in X, if $\chi_C$ is a path through T, then there exists $\sigma \in T$ such that $\sigma \subset \chi_C$ and every extension of $\sigma$ is in T. Jockusch noted a connection between 1-generic sets and coding sets for computable subtrees of 2$^{<\omega}$. We show they are identical.
Publié le : 1998-09-14
Classification: 
@article{1183745581,
     author = {McAllister, Alex M.},
     title = {Completions of PA: Models and Enumerations of Representable Sets},
     journal = {J. Symbolic Logic},
     volume = {63},
     number = {1},
     year = {1998},
     pages = { 1063-1082},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745581}
}
McAllister, Alex M. Completions of PA: Models and Enumerations of Representable Sets. J. Symbolic Logic, Tome 63 (1998) no. 1, pp.  1063-1082. http://gdmltest.u-ga.fr/item/1183745581/