Let \(M\) be a model of Peano arithmetic, let \(N\) be an elementary end extension of \(M\), and let \(\mathfrak X\) be the sets of subsets of \(M\) which are coded in \(N\). Then, \(\mathfrak X\) satisfies two natural conditions: it contains all definable subsets of \(M\), and \((M, {\mathfrak X})\) is a model of \(\mathrm{WKL}_0^*=\Delta^0_1\text{-}\mathrm{CA}+\mathrm{I}\Sigma_0\)+Weak König's Lemma. The main theorem of the paper includes the following converse. Let \(\mathfrak X\) be a set of subsets of a model \(M\) of PA. Then the following are equivalent: {\parindent=6mm\begin{itemize}\item[(1)] \(\mathfrak X\) is countably generated, contains all definable subsets of \(M\), and \((M,{\mathfrak X})\models \mathrm{WKL}_0^*\); \item[(2)] there is a countably generated elementary end extension \(N\) of \(M\) such that \(\mathfrak X\) is the set of subsets of \(M\) coded in \(N\); \item[(3)] there is a finitely generated elementary end extension \(N\) of \(M\) such that \(\mathfrak X\) is the set of subsets of \(M\) coded in \(N\). \end{itemize}} If \(M\) is countable then the condition (3) can be strengthened to: there is a superminimal elementary end extension \(N\) of \(M\) such that \(\mathfrak X\) is the set of subsets of \(M\) coded in \(N\). The theorem is in a sense an ultimate version of the MacDowell-Specker theorem and it generalizes earlier results from [\textit{R. Kossak} and \textit{J. B. Paris}, Arch. Math. Logic 32, No. 1, 65--73 (1992; Zbl 0786.03027)]. It also allows to confirm a few conjectures from that paper, in particular, using a recent result by \textit{H. Towsner} from [``On maximum conservative extensions, \url{arXiv:1302.1488}], the present author shows that for every \(n\geq 1\), every countable nonstandard model \(M\) of PA has an elementary end extension \(N\) such that \(M\) together with the set of subsets coded in \(N\) is a model of \(\mathrm{I}\Sigma_n+\lnot \mathrm{B}\Sigma_{n+1}\).
- A note on a theorem of Kanovei
- Corrigendum to: ``On the strength of Ramsey's theorem for pairs
- Formalizing forcing arguments in subsystems of second-order arithmetic
- scientific article; zbMATH DE number 440479 (Why is no real title available?)
- scientific article; zbMATH DE number 1222924 (Why is no real title available?)
- scientific article; zbMATH DE number 3437141 (Why is no real title available?)
- scientific article; zbMATH DE number 3204609 (Why is no real title available?)
- On maximum conservative extensions
- On the strength of Ramsey's theorem for pairs
- Subsets of models of arithmetic
- Subsystems of second order arithmetic
- The structure of models of Peano arithmetic
- Unifying the model theory of first-order and second-order arithmetic via \(\mathrm{WKL}_0^\ast\)
- Minimal elementary end extensions
- scientific article; zbMATH DE number 1222924 (Why is no real title available?)
- Neutrally expandable models of arithmetic
- Marginalia on a theorem of Woodin
- The lattice problem for models of \(\mathsf{PA}\)
This page was built for publication: Subsets coded in elementary end extensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403405)
