7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Lawrence, could you please translate the French to English? $\endgroup$
    – Wei Wang
    May 7, 2014 at 15:19
  • $\begingroup$ @WeiWang: I included a rough translation in the question as requested. It is probably not a good translation since I am rather bad at French, but I hope it helps. $\endgroup$ May 7, 2014 at 19:31
  • $\begingroup$ Perhaps a silly question: when applying 4.5, how about starting with $M$ modelling $\Sigma_{n+1}$-foundation (and enough collection)? $\endgroup$
    – Wei Wang
    May 9, 2014 at 1:48
  • $\begingroup$ @WeiWang: this was also the first idea that came to my mind, but it does not seem to work out: see my latest edit to the question. I am sorry for being quite messy in the descriptions there, but organizing ideas that do not work out is really quite hard. $\endgroup$ May 9, 2014 at 16:08

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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