Ensembles stationnaires et co-stationnaires
Bonjour à tous,
Je sèche lamentablement sur l'exo suivant (exercice 34 Page 191 dans le livre de Patrick Dehornoy) :
Montrer qu'il existe un sous-ensemble stationnaire de $\omega_{1}$ dont le complémentaire dans $\omega_{1}$ est stationnaire.
Indications : 1) Fixer pour chaque $\alpha$ limite une suite $(\gamma_{n,\alpha})_{n<\omega}$ de limite $\alpha$.
(Jusque là, j'ai compris).
2) Considérer $f_{n}$ définie par $f_{n}(\alpha)=\gamma_{n,\alpha}$ pour obtenir $S_{n}$ stationnaire et $\gamma_{n}$ tels que $\alpha \in S_{n}$ entraîne $\gamma_{n,\alpha}=\gamma_{n}$.
Là, j'ai pensé poser $S_{n}=$ l'ensemble de tous les $\gamma_{n,\alpha}$ pour $\alpha$ limite, mais ça ne semble pas mener à grand-chose.
3) Montrer que l'intersection sur $n$ des $S_{n}$ est un singleton et qu'il existe $n$ tel que $\omega_{1}-S_{n}$ est stationnaire.
(là, je ne vois pas du tout).
Si vous pouvez me donner un début de piste pour démarrer…
Merci d'avance
Martial
Je sèche lamentablement sur l'exo suivant (exercice 34 Page 191 dans le livre de Patrick Dehornoy) :
Montrer qu'il existe un sous-ensemble stationnaire de $\omega_{1}$ dont le complémentaire dans $\omega_{1}$ est stationnaire.
Indications : 1) Fixer pour chaque $\alpha$ limite une suite $(\gamma_{n,\alpha})_{n<\omega}$ de limite $\alpha$.
(Jusque là, j'ai compris).
2) Considérer $f_{n}$ définie par $f_{n}(\alpha)=\gamma_{n,\alpha}$ pour obtenir $S_{n}$ stationnaire et $\gamma_{n}$ tels que $\alpha \in S_{n}$ entraîne $\gamma_{n,\alpha}=\gamma_{n}$.
Là, j'ai pensé poser $S_{n}=$ l'ensemble de tous les $\gamma_{n,\alpha}$ pour $\alpha$ limite, mais ça ne semble pas mener à grand-chose.
3) Montrer que l'intersection sur $n$ des $S_{n}$ est un singleton et qu'il existe $n$ tel que $\omega_{1}-S_{n}$ est stationnaire.
(là, je ne vois pas du tout).
Si vous pouvez me donner un début de piste pour démarrer…
Merci d'avance
Martial
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pour 3): Si $f_n(\alpha) = \gamma_n$, alors $\gamma_{n,\alpha} = \gamma_n$, donc $\alpha = \sup \gamma_{n,\alpha} = ...$ et donc ... Après je ne suis pas convaincu pour "est un singleton". Ma preuve donne "est inclus dans un singleton", mais est un singleton c'est autre chose, et je ne suis pas sûr que ce soit vrai (enfin plus honnêtement : je pense que c'est faux)
Ensuite pour ce fameux $n$, si $\omega_1\setminus S_n$ n'est jamais stationnaire, il y a un club $C_n$ qui ne le rencontre pas. Que dire de l'intersection des $C_n$ ?
En fait je voulais faire les choses à l'envers : il faut d'abord établir le théorème de Fodor avant de faire l'exercice, oeuf corse. C'est ce qui s'appelle mettre la charrue avant les bœufs.
Pour la suite il faut que j'y réfléchisse (j'ai un peu du mal à me concentrer en ce moment, je veux faire 50000 choses à la fois et ça donne rarement de bons résultats), mais pour l'histoire du singleton je pense que tu as raison : comme ça à vue de nez on imagine plus ce machin vide que réduit à un singleton.
Je pense que Patrick a voulu dire : "montrer que l'intersection machinchouette est au plus égale à un singleton".
En tous cas merci pour ton aide, je te tiens au courant si je n'y arrive pas, et même si j'y arrive.
A+
Martial
P.S. Je crois qu'on dit plutôt "régressive", en tous cas c'est le terme qu'emploie Dehornoy, et on trouve aussi "regressive" dans les textes anglo-saxons.
Pour l'histoire du singleton : je ne sais pas pour ton nez :-D mais c'est surtout la preuve que j'ai qui donne un sous-singleton, et qui donne une manière de prouver que ce n'est pas forcément un singleton
Ah oui, j'avais oublié, je savais qu'il y avait du re et du essive mais le milieu me gênait !
Mais dans ta situation précise, les définitions sont "idéales". Pour un ordinal dénombrable $a$, il existe une bijection $f(a)$ allant de $\mathbb{N}$ dans $a$
Tu peux donc suivre le plan "non inspiré":
1/ $\forall a\exists n(a): [\{x>a\mid f(x)(n(a)) = a\}$ est stationnaire$]$
2/ Avec quoi, tu gagnes plus, puisqu'avec $p$ tel que $\{a\mid n(a)=p\}$ stationnaire, tu gagnes une famille disjointe de $\omega_1$ stationnaires deux à deux disjoints.
Remarque: l'axiome du choix est utilisé "à donf". Il est consistant avec ZF que l'ensemble des club est un ultrafiltre.
** dont je sais ... et ne trouve pas les mots pour ...
Ca va te rappeler quelque chose :-D
Je voulais justement montrer à quel point c'est différent avec AC.
Il y a une méthode "peu constructive" : il est facile de voir qu'il n'existe pas d'ultrafiltre $\aleph_{1}$-complet sur $\R$, donc a fortiori sur $\omega_{1}$. Comme le filtre des clubs est justement $\aleph_{1}$-complet ce ne peut pas être un ultrafiltre.
Je me disais que l'exercice arriverait peut-être à m'aider pour donner une preuve un peu plus "constructive" du même phénomène : construire un ensemble qui ne contient aucun club, mais qui n'est disjoint d'aucun club.
Je me suis rendu compte après coup que l'exercice ne me suffirait pas pour ça, et je suis tout à fait conscient qu'il utilise AC à donf (déjà rien que dans l'énoncé).
En tous cas merci à tous deux pour vos indications précieuses, il faut que je me replonge là-dedans à tête reposée.
1/ Club veut "clos et non borné". Dans le cas particulier de $\omega_1$ (je ne vais parler de rien d'autre), ça veut juste dire "non borné et contient les borne sup de ses suites".
2/ Un intersection dénombrable de club est un club de manière quasiment évidente : choisir une suite strictement croissante en prenant successivement les termes comme suit : $$
\in C_1; \in C_2; \in C_1; \in C_2; \in C_3; \in C_1; \in C_2; \in C_3; \in C_4; \in C_1;\dots
$$ puis prendre sa borne sup
3/ Stationnaire veut dire "intersecter tout club
4/ Si $f$ va de $\omega_1$ dans $\mathbb{N}$, il existe donc $n$ tel que $\{x\mid f(x)=n\}$ est stationnaire
5/ Voilà, ce qui précède remplit les trous qui étaient sous-entendus.
6/ Les clubs sont stables par intersections diagonales, ce qui signifie précisément que si $\forall x\in \omega_1: C_x$ est un club alors : $$
\{x\mid \forall y<x: x\in C_y\}
$$ est un club. La preuve est "aussi facile" que celle en (2)
7/ Corollaire: qui que soit $f: \omega_1\to \omega_1$, il existe $a\in \omega_1$ tel que : $$
\{x\mid f(x)=a\ ou \ f(x)\geq x\}
$$ est stationnaire.
8/ L'axiome de détermination entraîne que l'ensemble des clubs est un ultrafiltre. Il y a mille preuves de ça, mais l'académique passe par les degrés de Turing, et présente ce fait comme un corollaire de :
9/ Sous AD: pour toute $A$ partie de $\R$, stable par Turing-équivalence, il existe $X\in \{\R\setminus A; A\}$, $a\in \R$ tel que pour tout $x$, si $x$ permet de calculer tout ce que permet de calculer $a$, alors $x\in X$.
10/ À chaque $d$ degrés de Turing, on peut associer un ordinal dénombrable, tout bêtement la sup des ordinaux codables grâce à la richesse calculatoire de $d$
11/ En (9), je dis juste l'ensemble des $B_d:= \{x\mid x\geq_{Turing\,d}\}$ quand $d$ parcourt les degrés de Turing est une base d'ultrafiltre.
soit $A$ un ensemble de degrés de Turing. Lea et Bob s'affrontent:
$$ m:= x_1;y_1;x_2;y_2;..$$
Lea gagne quand $m\in A$. Les $x_i,y_i$ sont des 0 et des 1
Si $s$ est une stratégie infaillible pour elle, et que $d$ est son degré de Turing (cadire l'ensemble des réels calculables avec $s$ comme oracle), et que $e\geq d$ alors il y a dans $e$ un match $(x,y)$ joué avec la stratégie $s$ par le joueur qui a les $x_i$ et le degré de Turing de ce match est e. Donc $e\in A$.
Lea et Bob construise une suite:
$$\alpha_1;\beta_1; \alpha_2;\beta_2; \alpha_2;\beta_2; \alpha_3;\dots$$
et Lea gagne quand le sup de cette suite est dans $A$.
On a alors "évidemment":
1/ si Lea sgagne alors il y a un club inclus dans $A$
2/ si Bob sgagne alors il y a un clib disjoint de $A$
Je trouve important de publiciter ces remarques, tant on se retrouve sur des affaires "enfantines". Des gamins qui essaient de viser "le plus haut possible", ou etc.
@Tous : J'ai essayé de rédiger un mini-papier sur Fodor et ses applications (je me suis volontairement limité au cas de $\omega_{1}$, voir PJ).
J'aimerais savoir si ça tient plus ou moins la route.
Pour le théorème 1 (Fodor), je ne crois pas qu'l y ait de problème.
Pour le théorème 2 (qui est l'objet initial de ce fil), je me suis servi des indications de Max, et j'aimerais savoir si ma rédaction est suffisante, ou bien s'il faut rajouter quelques explications intermédiaires.
Quant au théorème 3, c'est une traduction pure et dure d'un passage du Jech, avec toutefois quelques "améliorations", au moins dans le lemme, pour rendre la chose plus compréhensible.
Il y a toutefois quelques détails qui m'échappent :
*) dans le lemme, ça va
**) dans le théorème proprement dit, 4 lignes avant la fin je ne comprends pas pourquoi on a nécessairement $\gamma_{\eta}$ supérieur ou égal à $\eta$. (J'avais compris hier soir, mais ça m'a échappé depuis).
Je ne comprends pas non plus pourquoi $S_{\eta}$ est inclus dans $S_{\eta, n}$.
Quat à la dernière ligne, j'écris "il est clair que", mais j'aurais mieux fait d'écrire "il est obscur que".
Merci de vous pencher sur ce truc.
Martial
Pour $\alpha \in S_\eta, f(\alpha) = \gamma_n$. Or $\gamma_n \geq \eta$ et $f(\alpha) = \theta_n^\alpha$, donc $\theta_n^\alpha \geq \eta$ donc $\alpha \in S_{\eta, n}$ par définition de $S_{\eta,n}$, donc $S_\eta \subset S_{\eta, n}$
Quant à ton "il est clair que", il est effectivement clair : $f$ est constante à valeur $\gamma_\eta$ sur $S_\eta$, donc si $\gamma_\eta \neq \gamma_{\eta'}$, un bonhomme de $S_\eta\cap S_{\eta'}$ verrait son $f$ avoir deux valeurs : embêtant !
Je ne sais pas si tu as déjà essayé de comprendre une démo dans le Jech, mais pour mon cas personnel à partir d'un texte de 5 lignes il me faut une page et demie pour rédiger le truc de façon compréhensible.
@Christophe : J'ai un peu de mal avec tes stratégies : tu devrais peut-être renommer Lea en Marjorie ou Irina, ça ferait plus sexy, lol
$$ SxR(x)$$
signifie que $\{x\in \omega_1 \mid R(x)\}$ est stationnaire et
$$ CxR(x)$$
signifie que $\{x\in \omega_1 \mid R(x)\}$ contient un club
Tout provient alors du fait qu'une intersection dénombrable de clubs est un club et que si tous les $C_x, x\in \omega_1$ sont des clubs alors $\{x\mid \forall y<x: x\in C_y\}$ (cet ensemble s'appelle "intersection diagonale des $C_x$) est un club. (C'est la version duale d eFodor, mais elle est peut-être plus "cash et facile" puisque tu as des "et" à la place des "ou").
Par exemple, si $\forall a (Cx: f(x)\neq a)$ alors $Cx: f(x)\geq x$, qui s'écrit dualement (enfin contraposément):
si $Sx: f(x)<x$ alors $\exists a: (Sx: f(x)=a)$
par exemple.
Soit $u$ une suite strictement croissante d'éléments de $D$ et $s$ sa borne sup. Comme $s$ est dans tous les $C_{u(n)}$, (comme limite de leurs éléments), il est dans tous les $C_x, x<s$.
Non bornitude: soit $a$. Puis $a<u(0)\in C_a$, puis $u(0)<u(1) \in C_{u(0)}$, etc. La borne sup de $u$ est dans $D$.
** en remplaçant chaque C_x$ par $C'_x:=\cap_{y\leq x} C_y$.
Un bon restau avec des vieux potes + enfin une nouvelle (ma major de promo est admise à Supélec, concours DUT apprentissage) ont suffi à me remonter le moral et à me clarifier les idées.
Mais je pense sincèrement que tu es vraiment un meilleur pédagogue que Jech : avec lui, le minimum est dit, et il faut vraiment savoir ligne entre les lignes.
Encore merci !
Martial
Je lui transmettrai ton bravo, ça lui fera plaisir