5
$\begingroup$

This was asked and bountied at MSE with no response:

My question is the following:

Is there a nonstandard model $\mathcal{M}\models\mathsf{PA}$ such that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable nonempty proper successor-closed initial segments?

Here "$\Delta^1_1$" is meant in the sense of the standard semantics of second-order logic - so a $\Delta^1_1$ subset of $\mathcal{M}$ doesn't need to be "internal" to $\mathcal{M}$ in any nice sense.

If we replace $\Delta^1_1$ with $\Pi^1_1$ the answer is trivially negative since the cut of standard naturals is $\Pi^1_1$; no parameters are needed here. If we replace $\Delta^1_1$ with $\Sigma^1_1$ this answer again becomes negative since for each nonstandard $a\in\mathcal{M}$ the set of elements infinitely below $a$ is $\Sigma^1_1(a)$ over $\mathcal{M}$. (See here.) However, I don't see a way to get a $\Delta^1_1$ cut in a nonstandard model of $\mathsf{PA}$. On the other hand, I don't see how to build a nonstandard model without a $\Delta^1_1$ cut. In particular, a natural hope might be to look at a nontrivial ultrapower of $\mathbb{N}$, but while $\Sigma^1_1$ formulas are preserved by taking ultrapowers, $\Delta^1_1$-ness (= an equivalence between a $\Sigma^1_1$ formula and a $\Pi^1_1$ formula) doesn't obviously need to be.

$\endgroup$
5
$\begingroup$

I believe you don't need this, but assume that there is a strongly inaccessible cardinal $\kappa$. Fix a first-order completion $T$ of $\mathsf{PA}$ and let $\mathcal{M}$ be a saturated model of $T$ of cardinality $\kappa$. I will show that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable cuts.

Claim. For any $\Sigma^1_1(a)$ formula $\varphi(x,a)$, there is a closed set $F_\varphi \subseteq S_{x}(a)$ of types such that $\mathcal{M} \models \varphi(b,a)$ if and only if $\mathrm{tp}(b/a) \in F_\varphi$ (where $\mathrm{tp}(x/y)$ is the first-order type of $x$ over $y$).

Proof. Given $\varphi(x,a)$, by compactness, there is a set of formulas $\Lambda(x,a)$ such that for any $b \in \mathcal{M}$,

  • there exists an elementary extension $\mathcal{N} \succeq \mathcal{M}$ for which $\mathcal{N} \models \varphi(b,a)$

if and only if $\mathcal{M} \models \Lambda(b,a)$. Since $\mathcal{M}$ is saturated, it is resplendent, and if there is such an elementary extension for a given $b$, then we actually have that $\mathcal{M} \models \varphi(b,a)$ (since some expansion of $\mathcal{M}$ by a predicate satisfies the part of $\varphi(b,a)$ after the set quantifier). Clearly the other direction holds, so we have that $F_\varphi$ is the set of types corresponding to the partial type $\Lambda(x,a)$. $\square_{\text{claim}}$

Assume that there is a $\Delta^1_1$-with-parameters-definable cut, so in other words, assume that we have two $\Sigma^1_1$ formulas $\varphi(x,a)$ and $\psi(x,a)$ such that $\varphi(\mathcal{M},a)$ is the cut and $\psi(\mathcal{M},a)$ is the complement of the cut. Let $F_\varphi$ and $F_\psi$ be as in the claim.

Since $\mathcal{M}$ is saturated, it is $\omega$-saturated. This implies that $F_\varphi$ and $F_\psi$ are disjoint (otherwise a type in their intersection would be realized) and cover $S_x(a)$ (otherwise a type in the complement of their union would be realized). Therefore, they are actually clopen, and correspond to some first-order formula $\chi(x,a)$ and its negation, but then $\chi(x,a)$ is a definable cut, which cannot happen, as $T$ is an extension of $\mathsf{PA}$. $\square$

As for getting rid of the inaccessible, I believe a special model will be sufficient, since they are resplendent for finite expansions. I actually think a computably saturated model might be sufficient too, since the first-order theory we're trying to expand to is c.e. (finitely axiomatizable, even).

$\endgroup$
9
  • $\begingroup$ Nice! A couple questions: what is a "special model," and what does "resplendent for finite extensions" mean? Also, it seems at a glance that all you need is resplendence, since the only things about $\mathcal{M}$ you actually use are its resplendence and $\omega$-saturatedness, and the former implies the latter. Or am I missing something? $\endgroup$ – Noah Schweber Mar 3 at 2:46
  • 1
    $\begingroup$ Incidentally, for those (like me) less familiar with resplendence, I recommend this quick survey by Kossak as a fun starting point. Basically, resplendent = elementary extensions preserve $\Sigma^1_1$ formulas. $\endgroup$ – Noah Schweber Mar 3 at 2:47
  • $\begingroup$ Yes, really we're only using resplendence and $\omega$-saturation, but full saturation or specialness are actually the only ways I know to get full resplendence. This is why a computably saturated countable model is probably good enough (countable computably saturated models are resplendent for expansions to computable theories). $\endgroup$ – James Hanson Mar 3 at 3:09
  • $\begingroup$ You probably figured this out by now, but specialness is a kind of almost saturation that's good enough for many applications but doesn't require any set theoretic assumptions. $\endgroup$ – James Hanson Mar 3 at 3:10
  • $\begingroup$ There's a pretty direct argument that some model has no $\Delta_1^1$ cuts, but setting it up precisely is probably more work than verifying that computably saturated models work. You can build a chain of elementary extensions of a countable model of $\mathsf{PA}$ and force that any given pair of $\Sigma_1^1$ formulas either overlaps or fails to cover the whole model. In order to make sure this stays true, you expand the language at each step with new unary predicates, and then you build elementary extensions in that new bigger language. You deal with parameters by catching your tail. $\endgroup$ – James Hanson Mar 3 at 3:13

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.