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

Paradis cantorien

Envoyé par Martial 
Re: Paradis cantorien
il y a six semaines
LMPC : non pas exactement: Alice et Bob jouent $\omega$ fois, à chaque tour un entier naturel. A la fin, on obtient une suite $x\in \omega^\omega$.

Le jeu est paramétré par un ensemble $X\subset \omega^\omega$, et Alice gagne si $x\in X$. Lorsque $X$ est borélien (pour la topologie produit), Alice ou Bob a une stratégie gagnante.
C'est l'un des rares théorèmes où toute la force du remplacement est utilisée.

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Paradis cantorien
il y a six semaines
LMPC: max t'a parfaitement répondu sauf sur "un détail".

On ne joue pas des entiers mais des éléments d'un ensemble $E$ donné et la preuve justement va faire monter $E$ très haut.

Mais évidemment on retient les versions où $E:=\N$ dans les médias, puisqu'on ne s'occupe pas de la preuve.

Pour tout $E$, tous les jeux boréliens jouant des coups dans $E$ sont déterminés

Exercice facile et amusant: il n'en est rien pour les analytiques!

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Paradis cantorien
il y a six semaines
Merci Maxtimax et cc !

Ca n'a rien à voir avec ce que j'avais imaginé lol.

Juste pour etre sur : Borelien pour la topologie produit des E munis de la topologie discrète, ou peu importe ?
Re: Paradis cantorien
il y a six semaines
@LMPC : oui c'est ça, $E^{\omega}$ muni de la topologie produit de la topologie discrète. (C'est d'ailleurs pour ça qu'on s'en fout un peu de la taille de $E$).

@Christophe : Kechris reprend la preuve de 85. Moschovakis donne une esquisse de celle de 75 (évidemment, puisque son bouquin est sorti en 80), mais je crois qu'il s'arrête aux $\mathbf{\Sigma^0_n}$ pour $n \in \omega$.

J'ai fini de rédiger la preuve. Pour l'essentiel j'ai traduit le papier de 1985, sauf pour le lemme de la limite inverse, où je me suis servi du document de Max (que je remercie au passage) qui est nettement plus clair.

Pour le lemme difficile (celui avec le fermé ou l'ouvert), je vais essayer de rédiger en plus ta preuve psychologique en introduction, et ensuite je publie le résultat des courses. Tu me diras ce que tu en penses. (Pour la preuve du fermé, c'est un mélange de chinois, de cyrillique et de néerlandais parlé à la sauce javanaise).
Re: Paradis cantorien
il y a six semaines
Je confirme LMPC: le plus petit ensemble contenant les ouverts et stable par complémentaire et unions dénombrables.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Paradis cantorien
il y a six semaines
0)@cc en fait ma question était de savoir si le théoreme etait vrai indépendamment de la topologie choisie sur chaque facteur, tu dis qu'on peut prendre n'importe quel E infini, (déjà est ce qu on est dans E^E ou dans E^omega. Et ensuite est ce que ça marche aussi si on prend la topologie produit mais de E muni de topologie non discrète)

En fait j'ai plusieurs interrogations qui me viennent je les note ici, aussi pour m'en souvenir, mais si quelqu'un a envie de répondre sur tel ou tel sujet, je numérote^^


Je sens que ce problème est de nature à me faire progresser dans plein de domaines que je ne connais que de nom... donc je vais m'y pencher un peu... quoi de mieux que d'essayer naïvement de le démontrer pour arriver à percevoir les difficultés d'un pb, mais avant ça je le regarde de loin sans me fatiguer la tête et je note déjà ces quelques questions naïves immédiates
J'ai du mal à concevoir ces boreliens. On a dedans toutes les unions denombrables de produit quelconque de sous-ensembles, et les complentaires de ces ensembles . Disons c'est le stade 1. (Le stade 0 on a qu'à dire que c'est les ouverts et les fermés) ensuite on considère les unions denombrables de trucs du stade 1 , qu on stabilise par complentaition. etc... déjà, combien de stade faut-il pour que ça s'arrête (je ne le note pas comme une question j'attends d'y réfléchir si c'est facile, je trouverai et si je ne trouve pas (ou si c est indécidable, qui sait) je demanderai )

La question qui m'intersse sur ces boreliens là, c'est
1)quelle est la tête d'une mesure qu'on peut mettre dessus... (Edit : hors mesures produits )
[(Lasuite du paragraphe, i.e. cette partie entre crochet , a un interet romanesque et je m'en servirai sans doute à ces fins mais vous pouvez sauter ce passage^^)
Quoi qu'il en soit une fois qu'on a une mesure, est-ce que la stratégie : "bob va dans la branche où l'intersection avec le borelien paramètre est de plus grande mesure et Alice dans celle de plus petite mesure "est une meilleures strategue commune? Intuitivement je dirai que la détermination dans le cas où X est de mesure non nulle suivant ces stratégies est déterminé... : si X n'est pas de mesure nulle , ça doit marcher, même si les mesures tendent vers 0 car... ah mais non, je me rends compte qu'il y a un problème même si les mesure tendent vers 0: si Bob prend le chemin le plus lourd mais que ce chemin contient une possibilité pour Alice de sortir de X....remarque une idée pourrait être que si une branche choisie par bob est perdante elle est de mesure 0, après tout je ne sais pas quelle tête a la mesure et c'est peut-être une façon de la construire, elle dépendrait d'un borelien particulier mais pourquoi pas .... soit ce que je dis mène à une tautologie ou dit autrement c'est une façon de traduire un aspect problème sans plus, soit la construction que j'imagine dans le flou est vouée à être une absurdité quelles que soient ses velléités de précision , soit ... c est une piste intéressante mais bon j'ai déjà oublié de quoi j'étais entrain de parler ]



Quelques questions naïves se posent à moi


2) est ce que le déterminisme de X est lié au déterminisme du complémentaire de X?

3)est-ce que les ensembles déterministes forment une tribu(ou au moins une algèbre de Boole)

J'imagine que cette question est compliquée puisque déjà c'est compliqué de dire que ça contient les boreliens (à moins que la difficulté principale soit de montrer que les ouverts)

Je n'ai pas encore assez réfléchi et mon plan va être de montrer le résultat pour un ouvert et un fermé... je précise aussi qu'au stade léger ou j en suis (je n'arrive pas à me concentrer car il y a du bruit ) il ne m'est pas naturel de concevoir qu'en général il y a pas de déterminisme, en fait ce quu est drôle c'est que quand j'avais réfléchi à cette question indépendamment, je m'était persuadé qu'il était évident que quel que soit X l'un des deux joueurs a une stratégie gagnante et en fait, ne trouvant pas d'argument immédiat je me suis dit que la difficulté était juste parcequ'il fallait poser le problème, et que" j'ai la flemme mais bon c'est évident". En fait ça ne l'était pas. Si la réponse est liée à l'axiome du choix, et que sans l'axiome du choix tout est déterministe (pardon si je dis des énormités ) ... ça serait alors, pour moi, le premier exemple contre intuitif de l'axiome du choix, bon il y a quand même Banach-Starsky ...d'ailleurs c'est lié à la mesure. Ce qui m'amène à une dernière question, est ce que le coup de " tout ensemble est mesurable " dans un modèle de ZF est spécifique au boreliens de R ou est ce que c'est plus général?


Je précise une fois de plus que je n'ai pas le toupet d'attendre des réponses, a ces nombreuses questions, mais si vous voulez en piocher une ça et/ou là*, n'hésitez pas^^



Bon j espere ne pas avoir nuit au fil en me ramenant a ces considérations au raz des pâquerettes par rapport à ce que je lis (et ne comprends pas ^^) , je vais maintenant relire pour ne pas agacer les modérateurs avec des fautes d'orthographes.

*"ça et/ou là " hahaha je la ressortirai



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par lesmathspointclaires.
Re: Paradis cantorien
il y a six semaines
Est-ce une bonne idée de prendre la topologie de $\R$ comme base de départ? Il y a plein de façon de définir la tribu borélienne. Par exemple c'est le plus petit ensemble $\mathcal T$ de parties de $\R$ contenant toutes les parties de la forme $]x,+\infty[$ avec $x\in \R$, stable par union dénombrable croissante et tel que pour tous $A,B\in \mathcal T$, si $A\subseteq B$ alors $B\setminus A \in \mathcal T$ (voir par exemple "lemme de classe monotone" sur un moteur de recherche).



Edité 2 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Paradis cantorien
il y a six semaines
LMPC : 0) c'est $E^\omega$ en principe, après tu peux aussi imaginer des jeux plus longs (donc $E^\alpha$, et en particulier si tu as un bon ordre sur $E$ tu peux demander $E^E$).

Pour 1), tu as des mesures de Lebesgue car $\omega^\omega$ est homéomorphe à un Cantor.

Pour 3), comme c'est facile de montrer ouvert/fermé , si "tribu" était facile, borélien serait facile winking smiley

L'axiome du choix entraîne effectivement l'existence de jeux non déterminés, et sans AC il est cohérent qu'ils le soient tous ("similairement" au fait qu'il est cohérent que tout soit Lebesgue mesurable; d'ailleurs AD implique que tout est Lebesgue mesurable)

Je ne trouve personnellement pas ça contre-intuitif, d'ailleurs les conséquences de AD sont, elles, très bizarres selon moi.
Finalement, pour ta question sur les boréliens de $\mathbb R$, je ne sais pas ce que tu entends par là. Je peux facilement décrire des espaces mesurables où tout n'est pas mesurable, et c'est prouvable sans AC grinning smiley
Peut-être qu'on peut trouver un analogue avec des groupes de Lie compacts (mesure de Haar) mais dans ce cas-là je pense que ça doit être la même chose que pour $\mathbb R$.

(Banach-Tarski grinning smiley)

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Paradis cantorien
il y a six semaines
@foys: ça ne change rien, ce sont les même boréliens. Tant que tu ne changes pas les srtatégies, c'est assez robustes.

Revisité avec $\R$ (enfin $[0,1]$), ça donne l'équivalent de $AD$ suivant *** :

Pour toute application $f$ de $A:=[0,1]^n\to n$, il existe un fermé $F\subset A$ et un $i\in N$ tel que:

1/ $\forall x\in [0,1]\exists y\in F: y(i)=x$

2/ $\forall z\in F: f(z)=i$

Le problème est que tu ne peux pas remplacer $F$ par un graphe de fonction continue, la connexité casse tout. C'est assez fascinant, ce "saut" que permet de "sauter" en un ensemble dénombrable de points. (Les stratégies sont des applications continues sur $\R\setminus \Q$ si tu veux, mais pas sur $\R$. Faut pouvoir faire des sauts. C'est pour ça que j'ai pris l'option avec des fermés pour te poster une réponse).

*** et bien entendu la complexité suit: avec ZF tu le prouves pour les $f$ boréliennes, avec des indiscernables, tu le prouves pour les "analytiques" (enfin je mets des guillemets d'ailleurs car comme c'est une fonction, faut modifier un peu la définition, les fonctions analytiques étant forcément boréliennes), etc.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Paradis cantorien
il y a six semaines
Merci Maxtimax!!

Est-ce que ça change quelque chose si on prends non pas $\omega^{\omega}$ mais $2^{\omega}$ ?

Ca change quelque chose à le sens de les démos sont à peu près les même mais on peut aussi le voir comme "est-ce que le déterminisme est vrai aussi?"

Dans ce(s) cas, est-ce que le même jeu avec X borelien de R au sens usuel, en identifiant suite et réel, est déterminé?


Merci encore pour tes réponses !!



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par lesmathspointclaires.
Re: Paradis cantorien
il y a six semaines
LMPC : en principe non.
Je crois (Christophe confirmera, il sait mieux que moi grinning smiley) que les boréliens de $2^\omega$ sont "les mêmes " que ceux de $\mathbb R$, donc ça ne devrait pas changer

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Paradis cantorien
il y a six semaines
Je confirme. En espérant que les guillemets ne gênent personne.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Paradis cantorien
il y a six semaines
$\N^{\N}$ est homéomorphe (lorsqu'il est muni de la topologie produit) à $\R\backslash \Q$ par les fractions continues (on prend $f:\N \to \Z$ bijective comme $x\mapsto -k$ si $x=2k$ et $x\mapsto k+1$ si $x=2k+1$) et on pose $\varphi(a):=f(a_0)+ 1/(a_1+(1/a_2+1/(a_3+ 1/(a_4+ ...))))$

Comment transformer cette fonction en isomorphisme d'espaces mesurables entre $\N^{\N}$ et $\R$? Soit $r:\N \to \Q$ une bijection. On peut prendre une partie $D=\{d_n\mid n\in \N\}$ infinie dénombrable de $\N^{\N}$ et poser $g(d_{2k}):=f(d_k)$, $g_{2k+1}=r(k)$ et ensuite pour tout $x\in \N^{\N}$, $\varphi'(x):=\varphi(x)$ si $x\notin D$ et $\varphi'(d_n)=g(d_n)$ pour tout $n\in \N$. Alors $\varphi'$ va être bimesurable tout comme $\varphi$ (soit $(X,\mathcal A)$ un espace mesurable dans lequel tous les singletons appartiennent à $\mathcal A$. Soit $Y \subseteq X$ dénombrable. Alors pour toutes parties $B$ de $X\backslash D$ et $Z$ de $Y$, $B\in \mathcal A$ si et seulement si $B\cup Z\in \mathcal A$).
Re: Paradis cantorien
il y a six semaines
On peut le dire autrement (de cette inoffensivité au regard de la tribu borélienne)

.

1/ On peut ne s'intéresser qu'à $[0,1]$, un borélien de $\R$ étant une réunion de boréliens inclus dans dans les $[n,n+1], n\in \Z$

2/ $[0,1]$ est juste un quotient topologique $2^\N$ (on identifie $d^+$ et $d^-$ quand $d\in \mathbb{D}$ par exemple (idem avec $10^\N$))

3/ un borélien de $[0,1]$ est juste un borélien de $2^\N$ qui ne distingue pas les $...39999...$ et $...4000...$

4/ $\N^\N$ est juste la partie de $2^\N$ constitué des suites de $0$ et de $1$ qui contiennent une infinité de $1$ (l'encodage étant:

$$ 001011000010110001... == 2104103...$$

(on compte le nombre de $0$ entre deux "1"))

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 il y a six semaines et a été effectuée par christophe c.
Re: Paradis cantorien
il y a six semaines
J'en profite pour dire ce qu'est un ensemble analytique:

Soit $A$ l'ensemble des parties ayant une infinité de $1$.

$X$ est analytique veut dire "il existe $f: 2^\N\to 2^\N$, continue (pour la produit de la discrète) telle que $X=ImageDirecteDePar(A,f)$

1/ Tous les boréliens sont analytiques

2/ Il y a des analytiques non boréliens

3/ Pour tous analytiques $X,Y$ disjoints il existe un borélien $B$ tel que $X\subset B$ et $Y\cap B=\emptyset$


ZFC ne permet pas de prouver que les jeux analytiques sont déterminés. Cette affirmation équivaut à une hypothèse assez forte de grand cardinal en terme de consistency-strength.

Remarque: prendre $A$ donne une grosse puissance là où prendre $2^\N$ n'aurait rien donné puisque l'image continue d'un compact est compacte.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Paradis cantorien
il y a six semaines
Et je donne un exemple très simple d'analytique non borélien. Vous prenez une bijection $f$ de $\N$ sur $\N^2$. Notez que $P(\N)$ s'identifie à $2^\N$, je parlerai donc de $P(\N)$.

La fonction $f$ fait "tout passer" de $\N$ à $\N^2$, je parlerai donc de $P(\N^2)$.

L'ensemble des $X\subset \N^2$ tels qu'il existe une suite $u$ vérifiant $\forall n: (u_n,u_{n+1}) \in X$ est un analytique non borélien universel (tous les analytiques s'y réduisent)

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Paradis cantorien
il y a six semaines
@Foys : l'argument $N^N$ homeomorphe à $R-Q$ me convainc bien. Je peine à lire la suite dans le détail et je serais étonné qu'on ne puisse pas conclure avec des arguments généraux, je me trompe peut-être.... je vais y réfléchir, sauf que j'ai surtout envie de réfléchir au N.B.

N.B : je ne savais pas que cette fonction $\phi$ était injective, c'est génial !! C'est un homeo en plus... je vais passer un peu de temps pour le comprendre!!
(au fait, un detail : c'est pas plutôt $\phi$ de ${N^*}^N$ dans $R-Q$?)

EDIT : je viens de lire la réponse de cc, qui est l'autre extrême en terme de précision vs vague grinning smiley



Edité 2 fois. La dernière correction date de il y a six semaines et a été effectuée par lesmathspointclaires.
Re: Paradis cantorien
il y a six semaines
à @lesmathspointclaires oui il faudrait mettre $\N \times (\N^{*})^{\N}$ ou décaler les termes de la suite (remplacer $a_k$ par $1+a_k$ pour $k\geq 1$) dans ce que j'ai fait. D'ailleurs avec le critère que j'ai donné par la suite, la fonction de mon fil est déjà une bijection bimesurable de $\N^{\N}$ dans $\R$ sauf erreur.
Re: Paradis cantorien
il y a cinq semaines
NB: soit $(E,d)$ un espace métrique et $\{y_n\mid n\in \N\}$ un ensemble dénombrable dense de $E$. Alors l'application qui à $x\in E$ fait correspondre $\left (\min \{d(x,y_n);1 \}\right )_{n\in \N} \in [0,1]^{\N}$ (muni de la topologie produit) est un homéomorphisme sur son image et de plus cette image est une intersection dénombrable d'ouverts si et seulement si il existe sur $E$ une distance complète définissant la même topologie que $d$ sur $E$. Autrement dit on peut voir les polonais comme les parties de $[0,1]^{\N}$ qui sont des intersections dénombrables d'ouverts.
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 228, Messages: 1 506 987, Utilisateurs: 27 661.
Notre dernier utilisateur inscrit ibra.


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

 

 
©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