Foundation scheme for $\Sigma_{n+1}$-formulas

Question

I have trouble working out a proof in the second part of

Jean-Pierre Ressayre and Alex Wilkie. Modèles non standard en arithmétique et théorie des ensembles. Publications Mathématiques de l'Université Paris VII, 1987.

On page 140, Ressayre writes:

4.6 Théorème […] – b – En revanche, l'énoncé plus faible “$\forall\gamma\ \exists(\mathrm L_{\alpha_i})_{i\leqslant\gamma}$ chaîne faiblement $\Pi_n$-élémentaire” n'est pas $\omega$-conséquence de $\Sigma_{n+1}$-$(\text{collection}+\text{fondation})$.

Preuve de (b): on applique 4.5 dans un $\omega$-modèle non standard $M$.

This refers back to page 139 on which he writes:

4.5 Corollaire – Pour tout modèle dénombrable non standard $M$ de $\Pi_n$-collection, et tout ordinal non standard $\rho$ de $M$, il existe $I\subset^{\rm e}\mathrm{On}^M$ tel que $\rho\in I$ et $\mathrm L_I^M\models\Pi_n\text{-collection}+{}$“il n'existe pas de chaîne $\Pi_n$-élémentaire $(\mathrm L_{\alpha_i})_{i\leqslant\rho+\rho}$”

Perhaps I should explain some of the terms used here.

• $I\subset^{\mathrm e}\mathrm{On}^M$ means $I$ is a proper initial segment of $\mathrm{On}^M$ and $\mathrm{On}^M\setminus I$ has no minimum element.
• If $I\subset^{\mathrm e}\mathrm{On}^M$, then $\mathrm L_I^M=\bigcup_{\alpha\in I}\mathrm L_\alpha^M$.
• $\Pi_n$-collection denotes the scheme consisting of (extensionality, pair, union, foundation, $\Delta_0$-separation, and) all sentences of the form $$\forall a,\bar c\bigl(\forall x\in a\ \exists y\ \theta(x,y,\bar c)\rightarrow \exists b\ \forall x\in a\ \exists y\in b\ \theta(x,y,\bar c)\bigr)$$ where $\theta\in\Pi_n$.
• $\Gamma$-foundation is the scheme saying “every nonempty parametrically $\Gamma$-definable class/set has an $\in$-minimal element”.
• A chain $(\mathrm L_{\alpha_i})_{i\leqslant\gamma}$ is (weakly) $\Pi_n$-elementary if $\mathrm L_{\alpha_i}\prec_{\Pi_n}\mathrm L_{\alpha_\gamma}$ for all $i<\gamma$.

Corollary 4.5 visually gives a model of $\Pi_n$-collection, or equivalently, $\Sigma_{n+1}$-collection. It is also easy to verify that this model satisfies $(\Sigma_n\cup\Pi_n)$-foundation by elementarity. It is, however, not clear to me how to get a model of $\Sigma_{n+1}$-foundation out of 4.5, and I see no reason why $(\Sigma_n\cup\Pi_n)$-foundation should imply $\Sigma_{n+1}$-foundation. From how Ressarye writes about it, the proof is apparently straightforward (if not immediate).

Does anyone have any idea of how an argument showing $\Sigma_{n+1}$-collection in Theorem 4.6(b) above can go?

---

Edit (7 May, 2014): With the help of Google Translate, I made a rough translation of Ressayre's statements quoted above:

4.5 Corollary – For every nonstandard denumerable model $M$ of $\Pi_n$-collection, and every nonstandard ordinal $\rho$ of $M$, there exists $I\subset^{\rm e}\mathrm{On}^M$ such that $\rho\in I$ and $\mathrm L_I^M\models\Pi_n\text{-collection}+{}$“there does not exist a $\Pi_n$-elementary chain $(\mathrm L_{\alpha_i})_{i\leqslant\rho+\rho}$”

4.6 Theorem […] – b – On the other hand, the weaker assertion “$\forall\gamma\ \exists(\mathrm L_{\alpha_i})_{i\leqslant\gamma}$ that is weakly $\Pi_n$-elementary” is not an $\omega$-consequence of $\Sigma_{n+1}$-$(\text{collection}+\text{foundation})$.

Proof of (b): one applies 4.5 to a nonstandard $\omega$-model $M$.

Please feel free to edit the text for any improvements on the translation.

---

Edit (9 May, 2014): Let me describe the problems I faced in more details below.

Start with a nonstandard $\omega$-model $M\models\rm ZFC+V{=}L$. Suppose $\varphi(v,x)$ is a $\Pi_n$-formula for which $$A=\{x\in\mathrm L_I^M:\mathrm L_I^M\models\exists v\ \varphi(v,x)\}\not=\varnothing.$$

• I can go below $I$ and look at some $\mathrm L_\beta^M\prec_{\Pi_n}\mathrm L_I^M$ for which $A\cap\mathrm L_\beta^M\not=\varnothing$. (I am not sure whether I can have more elementarity while keeping the non-existence of long $\Pi_n$-elementary chains.) We are done if $A\cap\mathrm L_\beta^M$ turns out to be definable in $M$, because then we can apply foundation to it. One way to make this set definable is to find $b\in M$ such that $$\forall x\in\mathrm L_\beta^M\ \bigl( \exists v\in\mathrm L_I^M\ M\models\varphi(v,x) \Leftrightarrow M\models\exists v\in b\ \varphi(v,x) \bigr).$$ As $I$, and hence $\mathrm L_I^M$, may not be definable in $M$, it is not clear how this can be achieved. Actually, it seems possible that $$\forall\delta\in I\quad \exists x\in A\cap\mathrm L_\beta^M\quad \forall v\in\mathrm L_\delta^M\quad M\models\neg\varphi(v,x).$$

• Perhaps we should consider $A_\beta=\{x\in\mathrm L_\beta^M:\mathrm L_\beta^M\models\exists v\ \varphi(v,x)\}$, where $\mathrm L_\beta^M\prec_{\Pi_n}\mathrm L_I^M$. This is definable in $M$, and so if it is nonempty, then it has an $\in$-minimal element. However, this $\in$-minimal element may not be an $\in$-minimal element of $A$ because of the possibility that $A_\beta\subsetneq A\cap\mathrm L_\beta^M$.

• Well, let us go above $I$ and look at $\mathrm L_\varepsilon^M\succ_{\Pi_n}\mathrm L_I^M$. (Again, I am not sure whether I can have more elementarity while keeping the non-existence of long $\Pi_n$-elementary chains.) Then $A_\varepsilon$, defined in the same way as $A_\beta$ in the previous bullet point, has an $\in$-minimal element. Suppose, out of goodwill, that we can find one such $\in$-minimal element $a\in\mathrm L_I^M$. This would satisfy the desired condition that $x\not\in A$ for all $x\in a$. However, we do not know whether $a\in A$ because we do not have enough elementarity between $\mathrm L_\varepsilon^M$ and $\mathrm L_I^M$.

• Alright, perhaps we should also bound the witnesses for $A$: every $\mathrm L_\varepsilon^M\succ_{\Pi_n}\mathrm L_I^M$ satisfies $$\exists x,v\ \bigl( \varphi(v,x)\wedge\forall x',v'(\varphi(v',x')\rightarrow x'\not\in x \bigr).$$ Assuming $I$ is not definable in $M$, this underspills to give $\mathrm L_\delta^M\prec_{\Pi_n}\mathrm L_I^M$ satisfying the displayed sentence above. This does not provide what we want because it only tells us $A_\delta$ has an $\in$-minimal element (which we already saw is apparently not sufficient).

• A similar argument shows it is sufficient to prove the existence of some $\mathrm L_\varepsilon^M\succ_{\Pi_n}\mathrm L_I^M$ such that for every $\mathrm L_{\varepsilon'}^M\prec_{\Pi_n}\mathrm L_\varepsilon^M$ above $\mathrm L_I^M$, the set $A_{\varepsilon'}$ contains an $\in$-minimal element of $A_\varepsilon$. This statement is not apparent because even though we can find $a\in\mathrm L_{\varepsilon'}^M$ that is $\in$-minimal for $A_\varepsilon$, we cannot guarantee this $a$ to be an element of $A_{\varepsilon'}$.

• …

I could go on, but perhaps this is already a little too much.

Answer 1

The point is that the $\omega$ in an $\omega$-model satisfies full induction, even if the whole model does not.

Take a nonstandard $\omega$-model $M\models\rm \Pi_n\text{-}collection+V\,{=}\,L$. Let $I$ be that given by Corollary 4.5. Suppose $\varphi(v,x)$ is a $\Pi_n$-formula for which $$A=\{x\in\mathrm L_I^M:\mathrm L_I^M\models\exists v\ \varphi(v,x)\}$$ is nonempty but has no $\in^M$-minimal element. By recursion, we will define an $\in^M$-decreasing $\omega$-sequence $(a_i)_{i\in\omega}$ of elements of $A$ such that $\{a_i:i\in\omega\}$ is $\Delta_{n+1}$-definable in $M$. This gives what we want because it contradicts $\Delta_{n+1}$-foundation and hence $\Pi_n$-collection in $M$.

Start with any $a_0\in A$. Suppose we already have $a_i\in A$, where $i\in\omega$. By our hypothesis, we know $A$ contains some $\hat a_{i+1}\in^M a_i$. Find $\hat v_{i+1}\in\mathrm L_I^M$ such that $M\models\varphi(\hat v_{i+1},\hat a_{i+1})$. Given any big enough $\mathrm L_\alpha^M\subseteq\mathrm L_I^M$ containing both $a_i$ and $\hat v_{i+1}$, define $$ \begin{aligned} v_{i+1}&=\min\{ v\in\mathrm L_\alpha^M: M\models\exists x\in a_i\ \varphi(v,x) \},\ \text{and}\\ a_{i+1}&=\min\{ x\in a_i:M\models\varphi(v_{i+1},x) \}, \end{aligned} $$ where the minima are taken with respect to the $\mathrm L^M$-order. These exist because $M$ has $\Delta_{n+1}$-foundation. It can be verified that this choice of $a_{i+1}$ does not depend on the choice of $\alpha$.

Since $\omega^M=\omega$, one sees that $i\mapsto a_i$ is a total function $\omega^M\to M$. The rest is straightforward.