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.



Foundation scheme for $\Sigma_{n+1}$-formulas
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.


