Subsets coded in elementary end extensions (Q403405)

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}\).