11
$\begingroup$

Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so.


The standard system of a nonstandard model $M$ of PA is the set of sets of natural numbers coded by elements of $M$: $$SS(M)=\{X\subseteq\omega: \exists a\in M\forall x\in\mathbb{N}(x\in X\iff p_x\vert a)\}.$$ (Here "$p_i$" denotes the $i$th prime.) An easy overspill argument shows that $SS(M)$ is always a Scott set,$^1$ and Scott proved that every countable Scott set is the standard system of some nonstandard model.$^2$

We can define an analogous notion$^3$ of standard system with $\mathbb{N}$ replaced with more general initial segments: if $M\subsetneq_{end} N$ are models of PA, then we let $SS_M(N)$ be the set of elements of $M$ coded by elements of $N$: $$SS_M(N)=\{X\subseteq M: \exists a\in N\forall x\in M(x\in X\iff p_x\vert a)\}.$$ (Here "$p_i$" denotes the $i$th prime in the sense of $N$, or equivalently in this case of $M$.) The same overspill argument shows that the second-order structure $(M, SS_M(N))$ is a model of WKL.

My question is whether the analogue of Scott's theorem holds, at least for countable $M$:

Question. Suppose $M$ is a countable model of PA and $\mathcal{X}$ is a countable family of subsets of $M$ such that $(M, \mathcal{X})\models$ WKL. Is there an $N\supsetneq_{end} M$ such that $SS_M(N)=\mathcal{X}$?

The problem here is that in the usual case, we don't need to worry about $\subseteq$ versus $\subseteq_{end}$, whereas that poses a real problem here.


$^1$A set of sets of natural numbers closed under join and Turing reducibility such that for every infinite binary tree in the set, an infinite path through that tree is also in the set. Equivalently, the second-order part of an $\omega$-model of WKL.

$^2$The generalization of Scott's theorem to uncountable Scott sets is wildly open. Knight and Nadel generalized Scott's theorem to Scott systems of cardinality $\aleph_1$, thus solving the problem under the assumption of CH, but their argument breaks down immediately for models of cardinality $\aleph_2$ or greater. Meanwhile, Gitman has recently shown that the question has an affirmative answer for a class of Scott sets characterized in terms of forcing, assuming the set-theoretic hypothesis PFA (which contradicts CH); however, my understanding is that her arguments really only apply to that particular class of Scott sets and that the hypothesis of PFA is currently necessary.

$^3$I've had trouble finding much literature on this, especially compared to the usual notion of a standard system, but Kossak and Schmerl's book does contain some information about them (especially in Chapter $7$).

$\endgroup$
  • $\begingroup$ Side note: there is a wiki for models of PA! $\endgroup$ – Noah Schweber May 21 '18 at 20:37
9
$\begingroup$

The question has a positive answer, not only when $M$ is a model of $PA$, but even when $M$ is a model of the fragment $I\Sigma_1$ of $PA$.

The positive answer alluded to above follows from Tanaka's self-embedding theorem, which states that if $(M,\cal{X})$ is a countable nonstandard model of $WKL_0$, then $(M,\cal{X})$ is isomorphic to a proper initial segment of itself, i.e. to a model of the form $(I, \cal{X}_{I})$, where $I$ is a proper initial segment of $M$, and $\cal{X}_I$ is the restriction of $\cal{X}$ to $I$, consisting of sets of the form $X\cap I$, as $X$ ranges over $\cal{X}$; note that $\cal{X}_I$ coincides with $SSy_I(M)$.

So in this case, the $N$ you are asking for can be arranged to be isomorphic to $M$. For further work and references and more info, see this paper of mine (It appeared in New Studies in Weak Arithmetics, ed. by Patrick Cégielski, Charalampos Cornaros, and Costas Dimitracopoulos, CSLI Lectures Notes, No. 211, 2013).

If the end extension $N$ is only required to satisfy $I\Delta_0$, then result even holds if $M$ is a model of $I\Delta_0$ + $Exp$ + $B\Sigma_1$.

The above result appears as Theorem 4.6 in this recent paper of Tin Lok Wong and myself, where we prove that if $(M,\cal{X})$ is a countable model of $WKL^*_0$, then there is an end extension $N$ of $M$ such that $SSy_M(N)=\cal{X}$, and $N$ is a model of $I\Delta_0$. Here $WKL^*_0$ is the well-known subsystem of $WKL_0$ that is conservative over $I\Delta_0$ + $Exp$ + $B\Sigma_1$.

In case $(M,\cal{X})$ is a countable model of $ACA_0$, we can arrange the desired $N$ to be an elementary end extension of $M$.

The above follows from the following two facts:

(1) if $(M,\cal{X})$ is a model of $ACA_0$, then the expansion of $M$ with predicates for each $X\in\cal{X}$, i.e., the model $(M,X)_{X\in\cal{X}}$, satisfies the theory often referred to as $PA^*$, i.e., the natural extension of $PA$ in which the predicates $X\in\cal{X}$ can appear.

(2) The extension of the McDowell-Specker Theorem due independently to Phillips and Gaifman, that states that every countable model $M$ of $PA^*$ has a conservative elementary end extension $N$ ($N$ is a conservative extension of $M$ here means that the intersection of every parametrically definable subset of $N$ with $M$ is parameterically definable in $M$).

$\endgroup$
  • $\begingroup$ Lovely! (Note to other readers: Tanaka's paper is here, and "proper initial segment" of a second-order structure refers to a structure whose first-order part is a proper initial segment of the first-order part of the larger structure, and whose sets are the cutoffs of the sets in the larger structure.) In addition to isomorphism with $M$, can the embedding $M\subsetneq_{end} N$ be arranged to be elementary? $\endgroup$ – Noah Schweber May 21 '18 at 23:58
  • $\begingroup$ @NoahSchweber Elementarity can only be arranged if the model $(M,\cal{X})$ satisfies $ACA_0$. $\endgroup$ – Ali Enayat May 22 '18 at 0:02
  • $\begingroup$ But it can be arranged in that case? $\endgroup$ – Noah Schweber May 22 '18 at 0:03
  • $\begingroup$ Just to be clear: do you want both elementarity and isomorphism? If so, then the answer is no. But if you just want elementarity, then the answer is yes. I can add an edit later to elaborate this bit if you wish. $\endgroup$ – Ali Enayat May 22 '18 at 0:08
  • $\begingroup$ I would definitely be interested in that. $\endgroup$ – Noah Schweber May 22 '18 at 0:09
4
$\begingroup$

Your question has a positive answer: there do exist proper end extensions for countable models with the required coded sets.

The PA requirement can be weakened. Generalizing results of Friedman[1973], the MacDowell-Specker Theorem extensions of Phillips[1974] and Gaifman[1976], and the results of Kirby, MacAloon, and Murawski[1979], Joseph Quinsey proved in his unpublished (and perhaps unreadable) 1980 thesis Lemma 5.9:

Suppose $M$ is a countable model of arithmetic and $\mathcal{X}$ is a countable family of subsets of $M$ such that

$$(M, \mathcal{X})\models exp + \Delta_0^0\text{-Induction} + \Delta_0^0\text{-Arith-Collection} + \text{WKL}$$

where Arith-Collection is the schema (with $q$ not free in $\theta$):

$$\forall m \lt n\, \exists p\,\theta \rightarrow \exists q\,\forall m \lt n \, \exists p \lt q\,\theta \,.$$

Let $\text{T} \in \mathcal{X}$ be such that in $(M, \mathcal{X})$, $\text{T}$ is is the encoding of a consistent set of sentences of arithmetic. Then there exists a proper end-extension $N$ of $M$ which is a model of the standard sentences of $\text{T}$ and is such that $SS_M(N)=\mathcal{X}$.

Moreover, if $(M, \mathcal{X})$ is a model of $\Pi_1^0\text{-overspill}$ (or if $M$ is the standard model), $N$ can be chosen to be recursively saturated.

If additional conditions are placed on $(M, \mathcal{X})$, then using the embedding techniques of Friedman[1973], Wilkie[1977], and Wilmers[1977], we may obtain elementary end extensions. Theorem 5.8 of Quinsey's thesis gives:

Let $k \ge 1$. Suppose $M$ is a countable model of arithmetic and $\mathcal{X}$ is a countable family of subsets of $M$ such that

$$(M, \mathcal{X})\models \Delta_0^0\text{-CA} + \Delta_0^0\text{-Arith-Collection} + \text{WKL} + \text{“the $\bar{k}$th Turing jump of the empty set exists"}$$

Further suppose that $\Pi_1^0\text{-overspill}$ holds in $(M, \mathcal{X})$. Let $c \in M$. Then there exists a structure $(N, \mathcal{Y})$ isomorphic to $(M, \mathcal{X})$ such that

  • $N$ is a $(k - 1)$-elementary initial segment of $M$,
  • $SS_N(M)=\mathcal{Y}$, and
  • the isomorphism fixes $c$.

If in addition we have that $\Sigma_1^1\text{-overspill}$ holds in $(M, \mathcal{X})$ and that

$$(M, \mathcal{X})\models \text{“the $\bar{k}$th Turing jump of the empty set exists"}$$

for each standard integer $k$, then we may require that $N \prec M$.

Since the two structures are isomorphic, we may swap them to get the end-extension. Note in passing that these two results have nothing to do with the main thrust of the thesis, which is to explore applications of Kripke's notion of fulfillability.

$\endgroup$
  • $\begingroup$ Quinsey's 1980 thesis (full disclosure, my thesis) has recently been transcribed into LaTeX, and is posted at arxiv.org/pdf/1904.10540.pdf. $\endgroup$ – jeq May 3 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.