Abstract

We generalize a result on True Arithmetic by Lachlan and Soare to certain other completions of Peano Arithmetic. If $\mathscr{T}$ is a completion of $\mathscr{PA}$, then Rep denotes the family of sets $X \subseteq \omega$ for which there exists a formula $\varphi$ such that for all $n \in \omega$, if $n \in X$, then $\mathscr{T} \vdash \varphi})$ ) and if $n \not\in X$, then $\mathscr{T} \vdash \neg\varphi})$. We show that if $\mathscr{S,J} \subseteq \mathscr{P}$ 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{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 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 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.