6
$\begingroup$

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 ("cuts")?

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$
0
2
+200
$\begingroup$

I have posted a complete answer to this question on MathOverflow.

The general idea of the solution is that sufficiently saturated models will always fail to have $\Delta^1_1$ definable cuts, even with parameters. Computably saturated countable models should also be sufficient, which avoids set theoretic assumptions.

$\endgroup$
1
  • $\begingroup$ I wonder what's the shortest time interval between answer posting and bounty awarding - for the record, this was 8 seconds by my computer. $\endgroup$ – Noah Schweber Mar 3 at 3:27

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.