le forcing expliqué aux matheux ordinaires

Je mets ici une preuve d'un fait dont il est question au lien suivant: [www.les-mathematiques.net]



Supposons que Bil ait une stratégie gagnante s. Soit $x\in A$. Jouons $v:=x$ contre la stratégie s utilisée par Bil. Il existe alors un entier $n$ tel que $\forall p>n: u(n)=x(n)$. Associons à $x$ l'entier $n=: n(x)$ ci-dessus et la suite finie $z(x):=(x(0);...;x(n))$.

L'application qui à $x\in A$ associe le couple $(n(x);z(x))$ est une injection, ce qui prouve que $A$ est dénombrable.

Remarque-exercice: prouver la réciproque, ie si $A$ est dénombrable alors Bil a une stratégie gagnante.

Supposons maintenant que toto ait une stratégie gagnante $s$. Soit $f$ l'application continue (qui va forcément de $2^\N$ dans $A$) qui à chaque $x$ associe la réponse commandée par la stratégie $s$ quand, se substituant à Bil, on joue $x$.

L'image de $2^\N$ par $f$ est un compact inclus dans $A$. Il n'est pas dénombrable à cause des règles du jeu (exercice)

cordialement, "On ne désire que ce qu'on n'a pas. Ce qu'on a, au mieux, on l'apprécie"



Edité 1 fois. La dernière correction date de il y a deux mois et a été effectuée par christophe chalons.

Bon pour rester dans le thème récent et pour alimenter le fil, je continue sur AD le temps d'un post.

Je rappelle une version équivalente à AD (que j'ai déjà dû donner plusieurs fois) qui parle (ou est censé parler) aux gens qui ne font pas de logique:

Pour toute partie $A\subseteq [0,1]^2$, il existe une application $f$ de [0,1] dans lui même, continue sur $[0,1]\setminus \Q$ et telle que

ou bien $\forall x\in [0,1]: (x, f(x))\in A$

ou bien $\forall x\in [0,1]: (f(x), x)\notin A$

Le "pas continu en $\Q$" semble jouer un rôle primordial.

Je mets donc un lien vers un fil amusant récent où a été explorée une alternative qui ne marche pas: [www.les-mathematiques.net]


Question, dans le fil en lien, en remplaçant $\R^2$ par un éventuel $\R^n$ avec n bien choisi, est-ce que ça pourrait marcher?

cordialement, "On ne désire que ce qu'on n'a pas. Ce qu'on a, au mieux, on l'apprécie"

loool AD. Bon, un peu de vacances pour toi, je reprends quelques trucs marrant concernant le forcing.

Dans je poste, je raconte comment il permet de "donner du sens" à certains notions peu accessibles autrement. Face, par exemple, à un graphe, on peut se demander s'il est coloriable avec des entiers. Evidemment, tout graphe dénombrable l'est, mais qu'en est-il des autres, en général.

Même dans les problèmes de nombres chromatiques finis, c'est djà un problème NP-complet, alors en passanr à l'infini

On peut faire encore plus vicieux: le forcing permet bien sûr de colorier n'importe quel graphe avec des entiers, si on ne met pas de restrictions sur l'extension générique qu'on attend.

Par contre, on peut se poser des questions du genre suivant: le forcing traditionnel qui rend $\R$ grand (mais n'agrandit pas $\N$, ie ne rend pas des ensembles anciennement non dénombrables, dénombrables) permet-il de colorier d'anciens graphes avec $\N$ couleurs, alors qu'ils ne l'étaient pas initialement?

Et bien étant donné la question ci-dessus, posée à propos d'un graphe $G$ quelconque, mais qui n'est pas coloriable avec des entiers, se traduit (et en fait on le sait grace à la familiarité avec le forcing) grosso modo de la manière suivante:

Existe-t-il un espace topologique $E$ vérifiant (***) tel qu'il y ait une application col de $Sommets(G)$ dans $Ouverts(E)$ telle que $\forall (x,y)\in Aretes(G): col(x)\cap col(y)=\emptyset$? Quand la réponse est oui, on dira que le grpahe $G$ est rouge. Sinon, on dit qu'il est bleu

(***) est la propriété: toute famille disjointe d'ouverts de $E$ est dénombrable.

Je ne crois pas que les réponses à ces questions soient évidentes, à cause des difficultés liées aux nombres chromatiques.

Pour illustrer à quel point on est encore peu de choses face à de grandes généralités, voici un truc rigolo dû aux axiomes de grands cardinaux et qui montre à quel point ils sont généraux.

Prenons la classe C des graphes non coloriables avec des entiers dans une extension générique qui ne collapse pas de cardinaux. C'est une définition rigoureuse, mais parfaitement délirante et inaccessible qui fait entrer plein de choses. Il ne fait aucun doute qu'elle ne peut pas avoir été complètement investiguée.

Et bien pourtant, un axiome de grand cardinal permet d'affirmer qu'il existe un ensemble $P$ inclus dans $C$ tel que tout graphe de C contient un sous-graphe qui est (à isomoprhisme près) dans P.

On ne voit pas très bien quelle peut être la taille de P (probablement très grande).

Voici un autre exemple du même jus:

il existe un ensemble $Q$ de graphes bleux tel que tout graphe bleu contient un sous-graphe qui est (à isomoprhisme près) dans $Q$.

J'aime beaucoup ce que permet cet axiome. En gros, il dit que tout a un indice de compacité, et il n'y a plus qu'à s'amuser à les chercher.

cordialement, "On ne désire que ce qu'on n'a pas. Ce qu'on a, au mieux, on l'apprécie"

Ca sort un peu du cadre du forcing, il me vient une question "quantique".

Existe-t-il un graphe $G$ qui ne peut pas être colorié avec 74 couleurs, mais tel qu'il existe une application col de $sommets(G)$ dans $\R^{74}$ (vu comme espace euclidien) telle que $\forall (x,y)\in aretes(G): col(x)$ est orthogonal à $col(y)$?????

(Je vais aussi donner un numéro à cette question dans le fil "il est facile de". )

cordialement, "On ne désire que ce qu'on n'a pas. Ce qu'on a, au mieux, on l'apprécie"

J'en reviens à des choses concernant l'infini, dont je ne pense pas avoir parlé avant. Ca mélange jeux et ordinaux. Il y a plusieurs manières d'attaquer les ordinaux non dénombrables, dont une plus ludique que les autres.

Soit donc $O$ le premier odinal non dénombrable (son nom habituel est $\omega_1$, mais j'ai la flemme de le noter à chaque fois ainsi.

Voici un jeu rigolo:

A chaque étape $a\in O$, le joueur1 joue $n_a$ un entier et le joueur2 joue ensuite $p_a$. Ils construisent ainsi 2 applications de $O$ dans $\N$ qui ne peuvent pas être injectives, par définition de $O$.

On peut donc se demander plein de truc canoniques, car il y a une "marque" qui signale quand un joueur a fini de jouer ses coups. Par exemple, pour le joueur1, on peut s'amuser à dire qu'il a terminé de jouer quand à l'étape $a$ il rejoue un $n_a$ qu'il a déjà joué auparavant, ie quand $\exists b\in a: n_b=n_a$. On considère alors que ses coups suivants sont joués pour du beurre.

Pour toute application $n$ de $O$ dans $\N$, on appelle donc $s(n)$ le premier $a$ tel qu'il existe $b\in a: n_b=n_a$.

L'un des premiers jeux tout bête est de regarder "lequel" parvient à étirer sa tentative de mettre "son" $s(n)$ le plus loin possible, ie qui arrive à "injecter" le plus gros début de $O$ dans $\N$.

Compte-tenu du fait que J2 joue toujours ses coups après J1, il a une stratégie évidente pour gagner: il joue de façon à avoir $p_i=2n_i$ pour tout $i$ et dès qu'il voit que J1 recopie un entier qu'il a déjà joué avant, J2, au lieu de jouer $p_i=2n_i$, joue un nombre impair.

Ainsi il a la garantie de gagner au jeu: "$s(n)<s(p)$"

Les variations sur ce thème sont multiples et on peut aller très loin.

Le plus "paresseux" et spectaculaire est plutôt de ne pas utiliser $O$, mais plutôt un ordinal (on peut prendre le plus petit ainsi) $Z$ tel qu'il n'y a pas de surjections de $2^\N$ sur $Z$ .

Puis à chaque étape, les joueurs, au lieu de jouer d'un coup un élément $r_a\in 2^\N$, ils jouent un digit. De sorte qu'on obtient une application de $Z$ dans $2^\N$ de manière indirecte, en regardant les applications $r$ de $Z$ dans $2$ contruites par chaque joueur comme des applications canoniquement de $Z$ dans $2^\N$, via *****

Dans ce cas, théorème "presque évident": le joueur2 n'a pas, comme dans l'histoire précédente avec les entiers, de stratégie gagnante au jeu où J2 doit s'arrêter strictement après J1. Je le laisse en exercice, c'est un bon petit exercice pour intégrer tout ça.


***** Soit $f$ une application de $Z$ dans $2$. On lui associe, par récurrence ordinale l'application $g$ de $Z$ dans $2^\N$ de la manière suivante:
pour tout $a\in Z, n\in \N$
$g(a)(n) =f(w(a)+n)$

En notant $w$ l'application de $Z$ dans $Z$ définie par:
$w(0):=0$
$w(a+1)=w(a)+\N$
$w(a)=$ le premier ordinal $r$ strictement plus grand que tous les $w(b),b\in a$ (pour $a$ ordinal limite)

cordialement, "On ne désire que ce qu'on n'a pas. Ce qu'on a, au mieux, on l'apprécie"

Je reprends une opinion que j'avais effleuré dans le fil sur les topos.

La "vraie" théorie des maths est la théorie contradictoire suivante:

$\exists a\forall x (R(x)\iff x\in a)$ (***) appliqué à n'importe quelle relation R, y compris avec paramètres

La contradiction célèbre (valable en logique intuitionniste!!!! c'est souvent oublié) a été retenue par l'histoire comme "l'ensemble des ensembles qui ne s'appartiennent pas à eux-même"

Je rappelle rapidement l'argument: soit P un énoncé (quelconque!). Soit $a$ tel que $\forall x: (x\in a\iff (x\in x\to P))$. On obtient que $a\in a\to (a\in a\to P)$ et donc que $a\in a$ et donc $P$ (ainsi on peut prouver n'importe quoi).

On a donc bridé cette théorie en inventant ZF. En fait, il y a eu une d'autres alternatives, comme par exemple NF, qui restreint (***) aux R où on peut mettre des petits numéros à chaque variable libre ou liée apparaissant dans R de sorte que dans chaque occurence $u\in v$, le numéro attribué à u vaut 1 de moins que le numéro attribué à v. A ma connaissance, c'est un problème ouvert que de savoir si NF est consistante.

Elles ont toutes été "recalées" par ZF dans le sens où les matheux veulent se sentir libres de prendre les R qu'ils veulent dans (***). La tradition est donc: "si on obtient une contradiction en utilisant quelques R's dans un raisonnement, l'un au moins doit être considérée comme contenant "trop" de choses". C'était assez tolérant dans la mesure où les matheux utilisent des objets bien fondés (le fini, puis l'infini dénombrable, puis $\R$, puis de tps en tps $P(\R)$, etc, mais, tels de petits animaux prudents, ils s'aventurent avec grande hésitation vers des collections plus grosses.

Actuellement, n'importe quelle preuve dans n'importe quel article utilise des ensembles qui sont la pupart du temps des parties d'ensembles déjà évoqués avant dans l'article et donc, no souci.

Par ailleurs, si on "pense" à des ensembles mal fondés, sauf exception rarissime et exotique, on peut les représenter par des $(E,R)$ où $E$ est un banal ensemble bien fondé et $R$ une relation binaire qui "simule" l'appartenance de l'animal étrange qu'on veut évoquer.

Cependant la question se pose concernant les R qu'on peut mettre en oeuvre dans *** pour obtenir des lampes d'Aladin pas chères:

Rappel d'un exemple "bête": Brouwer ne pouvait guère prouver son théorème comme suit:

Soit $a$ l'ensemble des $(x,y)$ tels que $y\in f(x^*)$ en notant $x^*$ l'ensemble des $t$ tels que $(x,t)\in x$. On obtient alors que pour tout $z$: $z\in a^*\iff (a,z)\in a\iff z\in f(a^*)$ et donc $f(a^*)=a^*$ ce qui donne un point fixe de $f$ uniquement en utilisant (***) et l'extensionnalité (2 ensembles ayant les mêmes éléments sont égaux)

Parmi les "collections" qu'on a supposé être des ensembles, il est intéressant de voir lesquelles pourraient "être trop grosses" dans le raisonnement ci-dessus:

ce n'est pas l'ensemble des $t$ tels que $(x,t)\in x$ dans la mesure où c'est presque un sous-ensemble de quelque chose qui est déjà supposé être un ensemble "avant (en l'occurence $x$)

C'est donc la collection $G(f)$ des couples $(x,y)$ tels que $y\in f(x^*)$ !!!!

Conformément à la "tradition ZF", les $f$ qui n'ont pas de point fixe sont telles que $G(f)$ est "trop grosse".

Pourquoi je raconte tout ça?

Et bien parce que dire qu'un jeu est déterminé (ie que l'un des joueurs a une méthode infaillible pour gagner) c'est demander un certain point fixe à une certaine fonction. Or il se trouve que dans le cas fini, ça marche très bien. Ie le programme naif "bats-toi toi-même" qui s'appelle récursivement lui-même ne boucle jamais dans les vrais jeux (il consomme certes bcp de ressources, mais c'est tout).

Il est donc notable qu'en passant à l'infini, on puisse obtenir des jeux indéterminés et donc générer des "G(f)" très grosses avec simplement des demandes du type "bats-toi toi-même".

Et ça donne des contradictions exploitant des instances de (***) beaucoup plus subtile que la preuve "nonBrouwerienne" signalée ou que l'arugment diagonal.

cordialement, "On ne désire que ce qu'on n'a pas. Ce qu'on a, au mieux, on l'apprécie"



Edité 3 fois. La dernière correction date de il y a sept semaines et a été effectuée par christophe chalons.

Bon aller, abant d'aller prendre mon train, j'offre un petit exo marrant à la sagacité des gens pas en vacances (je le mettrai aussi dans le filde questions, mais c'est une incication de le mettre ici)

Soit $E,F$ tous les 2 bien ordonnés (vous pouvez prendre $\N$ dans les 2 cas, pour concrétiser)

On note $T$ l'ensemble des applications de $E$ dans $F$. J'ai déjà rappelé plusieurs fois l'outil cantorien de base:

théorème1: pour toute application $L$ de $T$ dans $E$ il existe $e\in E$ tel que pour tout $y\in F$ il existe $f\in T$ telle que ($f(e)=y$ ET $L(f)=e$)

J'aime appeler ce lemme le "lemme de l'étoile" car on imagine $e$ au centre et les $y$ des extrémités et les $f$ dont l'existence est affirmée des rayons.

Bref.

Dans un autre fil, j'ai embêté Samok avec la généralisation suivante:

théorème2: pour toute application $L$ de $T$ dans $E$ il existe $e\in E$ et une application $y\mapsto f_y$ tel que pour tout $y\in F$ ($f_y(e)=y$ ET $L(f_y)=e$), d'une part et d'autre part: $\forall y,z\in F\forall x\in E: y\geq z\to (f_y(x)\geq f_z(x)$


Le th1 se prouve facilement par un argument dit diagonal: à chaque $e\in E$ associer un $g(e)\in F$ tel que $\forall f\in T: L(f)=e\to f(e)\neq g(e)$. On voit bien la contradiction venir.

Je laisse à samok le lemme2, qui fonctionne à peu près pareil.

Voici un théorème3 qui semble devoir se prouver un peu différemment (à moins que je n'ai pas vu une évidence):


Cette fois-ci, on suppose que la $L$ allant de $T$ dans $E$ est telle que le $e$ dont l'existence est affirmée au th1 est unique.
A chaque $u\neq e$, on associe $h(u)$ le plus petit élement s de $F$ tel que $\forall f\in T: L(f)=u\to f(u)\neq s$. Attention, $h$ est donc définie seulement sur $E-\{e\}$
Théorème3: on note $K$ l'ensemble des $g\in T$ telles que $\forall x\neq e: g(x)\leq h(x)$. Alors pour tout $y\in F$ il existe $f\in K$ (et non plus seulement dans $T$) telle que $L(f)=e$ et $f(e)=y$.

exercices: prouver les th2 et 3

cordialement, "On ne désire que ce qu'on n'a pas. Ce qu'on a, au mieux, on l'apprécie"