Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
264 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Ensembles stationnaires et co-stationnaires

Envoyé par Martial 
Ensembles stationnaires et co-stationnaires
l’an passé
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
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Pour 2) : $f_n:\{\beta < \omega_1, \beta$ limite $\} \to \omega_1$ est "récessive" (je crois que c'est le mot) : $f_n(\alpha)<\alpha$. T'as pas un lemme connu qui te permet d'obtenir un stationnaire gratos quand t'as une fonction récessive définie sur un stationnaire (en l'occurrence même un club) ? winking smiley

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$ ?

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Ensembles stationnaires et co-stationnaires
l’an passé
@Max : oui bien sûr, le lemme dont tu parles est connu sous le nom de théorème de Fodor.
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.
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Ah oui, je vois mal comment faire la question 2) sans Fodor grinning smiley sauf à refaire la preuve naturellement

Pour l'histoire du singleton : je ne sais pas pour ton nez grinning smiley 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 !

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Dans les indications, PaDe ** , avait probablement en tête, des généralisations.

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 ...

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Une remarque d'ailleurs. Si $a\in \omega_1\mapsto S_a$ est une famille disjointe de stationnaires disjoints, tu gagnes une fonction $g$ telle que pour toute partie $P$ juste supposée non bornée de $\omega_1$ et tout ordinal $a$, il existe une suite $u$ d'éléments de $P$ telle que $g(p)=a$.

Ca va te rappeler quelque chose grinning smiley

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensembles stationnaires et co-stationnaires
l’an passé
@Christophe : je savais que sous AD le filtre des clos cofinaux est un ultrafiltre.
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.
Re: Ensembles stationnaires et co-stationnaires
l’an passé
@Martial: ne lis pas si tu veux réfléchir. Je poste juste pour les passants (ce genre de thème étant trop souvent ostracisé).

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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de l&rsquo;an passé et a été effectuée par AD.
Re: Ensembles stationnaires et co-stationnaires
l’an passé
J'ai suivi jusqu'au point 7), plus l'énoncé du point 8). Après, dès qu'il est question de degrés de Turing pour moi c'est de l'afghan ancien, lol.
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Tu vas voir ce n'est pas très méchant:

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$.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de l&rsquo;an passé et a été effectuée par christophe c.
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Bien que l'axiome "les jeux où on joue des ordinaux dénombrables sont déterminés" ne soit pas consistant, je "me dois" de signaler tout de même que, concernant le clubisme, le jeu est naturel:

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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensembles stationnaires et co-stationnaires
l’an passé
@Christophe : ta dernière "démo" avec Lea et Bob ressemble étrangement à la preuve (que je ne maîtrise absolument pas) du fait que AD entraîne que $\aleph_{1}$ est mesurable.

@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
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Avec la PJ ça sera plus facile à comprendre… Comme disait Sabbagh, une fois qu'on a dépassé la soixantaine ça devient le bordel dans le cerveau, lol
Pièces jointes:
ouvrir | télécharger - Fodor et applications.pdf (76.8 KB)
Re: Ensembles stationnaires et co-stationnaires
l’an passé
L'idée est d'utiliser le lemme de Fodor non pas sur $S$ mais sur $S_{\eta ,n}$. Tu restreins $f$ à $S_{\eta, n}$, et alors elle est toujours régressive naturellement, et elle est donc constante sur un stationnaire. Elle est constante, mais définie sur $S_{\eta, n}$, donc sa valeur ne peut être que $\geq \eta$ (se souvenir de la définition de $f$ et de celle de $S_{\eta, n}$)


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 !

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Une stratégie envoie chaque suite finie d'ordinaux sur un ordinal. Si une stratégie garantit un sup vert alors tout ordinal stable par s est vert et l'ensemble des srables par s est un club

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensembles stationnaires et co-stationnaires
l’an passé
@Max : Je crois qu'avec tes indications je devrais y arriver.
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
Re: Ensembles stationnaires et co-stationnaires
l’an passé
J'ai lu quelques passages de Jech, mais pas les mêmes que toi visiblement grinning smiley (spécifiquement j'avais feuilleté les passages sur le forcing et l'axiome de détermination).

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Je détaillerai aussi si tu veux. Pour les clubs et les stationnaires je t'avais fait un post "léger" (à côté de Jech grinning smiley ) et contenant tout tes trucs un peu plus haut

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensembles stationnaires et co-stationnaires
l’an passé
J'ai lu aussi le chapitre consacré au forcing… et là, je trouve qu'il se fout royalement de la gueule du monde. Peut-être la partie sur les algèbres de Boole est-elle accessible à un initié, mais sa façon d'expliquer le forcing classique est totalement imbittable à mon sens. Quant à l'axiome de détermination je préfère son petit livre "The axiom of choice", qui comme son nom l'indique parle essentiellement de modèles qui ne vérifient pas AC (par exemple AD ou autre).
Re: Ensembles stationnaires et co-stationnaires
l’an passé
@Christophe : oui, j'ai lu tous ces posts… mais j'ai quand même un peu de mal
Re: Ensembles stationnaires et co-stationnaires
l’an passé
En fait, c'est essentiellement de la dualité. Tu pourrais créer des quantificateurs $S,C$ comme suit:

$$ 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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Soit $D:=\{x\mid \forall y\in x: x\in C_x\}$. Je te prouve qu'il contient un club. On peut** supposer $x\mapsto C_x$ est décroissante où la relation d'arrivée est $\supseteq $.

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$.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Ensembles stationnaires et co-stationnaires
l’an passé
@Maxtimax : Ça y est, j'ai compris !
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
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Je voulais dire une BONNE nouvelle, oeuf corse !
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Martial : super si je t'ai aidé à comprendre thumbs down merci pour la flatterie spinning smiley sticking its tongue out (et bravo à ton élève !)

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Ensembles stationnaires et co-stationnaires
l’an passé
Ce n'était pas une flatterie, c'était un constat objectif.
Je lui transmettrai ton bravo, ça lui fera plaisir
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 225, Messages: 1 506 938, Utilisateurs: 27 661.
Notre dernier utilisateur inscrit ibra.


Ce forum
Discussions: 2 516, Messages: 51 073.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page