le forcing expliqué aux matheux ordinaires
C'est la méthode inventée par Paul Cohen dans les années 1960 pour démontrer que les axiomes des maths ne peuvent ni prouver, ni infirmer l'hypothèse du continu.
L'hypothèse du continu est l'assertion qui affirme que toute partie du $\R$ qui n'est pas "aussi" grande que $\R$ est obligatoirement dénombrable. Plus précisément: si une partie $A$ de $\R$ n'est pas dénombrable alors il existe une surjection de $A$ sur $\R$
L'hypothèse du continu est l'assertion qui affirme que toute partie du $\R$ qui n'est pas "aussi" grande que $\R$ est obligatoirement dénombrable. Plus précisément: si une partie $A$ de $\R$ n'est pas dénombrable alors il existe une surjection de $A$ sur $\R$
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Car, en fait, il est vrai que Cohen a prouvé qu'on ne peut décider HC (l'hypothèse du continu) ni avec les axiomes de ZFC, ni même avec d'autres axiomes qui seraient acceptables comme {\it axiomes des maths}. Et pour ça, en passant, d'ailleurs, je vais vous rappeler (ou signaler) une manière disons "résumée" d'aborder cette très politique notion {\it d'axiomes} des maths
Par avance, je m'excuse pour toutes les coquilles qui vont suivre, mais j'écris "en live" lol
Il s'agit d'une théorie inconsistante (c'est à dire contradictoire) qui contient trois groupes d'axiomes.
2 des 3 groupes contiennent un seul axiome: autrement dit, il ya 2 axiomes et une famille d'axiomes fabriqués tous selon le même principe
Mais avant, quelques postulats déontologiques qui n'ont guère besoin d'^^etre nommés "axiomes":
*Tout objet mathématique est {\bf un ensemble}. Un ensemble appartient ou non à un autre ensemble. Pour dire qu'un ensemble $a$ appartient à un ensemble $b$, on note $a\in b$. (Pour intervenir, vous pouvez cliquer sur la case latex pour voir comment on fait le symbole d'appartenance)
Dès maintenant, un commentaire (stéril) s'impose. J'y reviendrai: que tout objet mathématique soit un ensemble est une manière très politiquement orientée de démarrer une formalisation des maths. Cependant, retenez bien que c'est ainsi que l'histoire a procédé!
axiome no1: 2 ensembles différents ne contiennent pas les mêmes éléments. Il existe un élément qui appartient à l'un des 2 ensembles mais pas aux 2.
Cet axiome s'appelle {\bf axiome d'extensionnalité}. Il est pus rigolo qu'il n'y parait en première lecture:
Si vous voulez emmerder un étudiant peu soigneux, par exemple, demandez-lui de justifier que la fonction $f$ et la fonction $g$ sont égales sachant que $f:x\mapsto x^2+1$ et que $g: x\mapsto x^2+2-1$.
Si vous voulez emmerder un pédagogue qui fait une conférence sur la délicatesse pédagogique qu'il y a à présenter la notion de fonction à des élèves, laissez-le d'abord exposer qu'une fonction est une petite machine ou un petit processus qui transforme les objets puis posez-lui la question précédente...
{\bf L'axiome no2: il existe une application $\phi$ de tout l'univers dans tout l'univers telle que pout tout $x$, si $\phi (x)\notin x$ alors $x$ est vide, c'est à dire que $\forall y:y\notin x$. }
Cet axiome s'appelle l'axiome du choix
Je ne peux pas écrire "axiome no3"!!!
Le terme "officiel" est
{\bf Schéma d'axiomes: toute "collection" est un ensemble, en ce sens que, si vous inventez une nouvel adjectif qualificatif "bleu", vous avez le droit d'affirmer l'assertion très précise qui suit:
$\exists a\forall x: [x\in a$ si et seulement si $x$ est bleu]}
Ce schamé sera appelé {\bf \it schéma de supercompréhension}
en appelant "être bleu" le fait pour $x$ d'être tel que $x\notin x$, on obtient une contradiction si on utilise le schéma de supercompréhension. (Rappel: une contradiction est une conjonction d'un énoncé et de son contraire. Je ferai quelques rappels plus tard sur les axiome logiques, entre autre sur le fait que le faux est l'éoncé qui dit "tout est vrai" et sur le fait qu'une contradiction équivaut au faux)
Preuve (célébrissime): using une instance du schéma de supercompréhension, donnons le nom $a$ à un ensemble qui contient exactement les $x$ tels que $x\notin x$. Si $a\in a$ alors $a\notin a$ et donc, "le faux". Ainsi, $a\in a\to $"le faux", ce qui n'est rien d'autre que $a\notin a$. Donc $a\in a$ et comme on a déjà prouvé que $a\in a$ implique tout... {\bf tout!}
Comment s'en est-on sorti?
Il apparaissait à tout le monde que la propriété "$\lambda x:x\notin x$" était certes trop subtile, ou trop compliquée, mais comment faire le tri entre les propriétés subtiles et les autres. Entre celles auxquelles on pouvait appliquait le schéma de supercompréhension et les autres?
Commençons donc par faire "comme si" on n'avait jamais rencontré le problème que je viens d'évoquer, et "amusons-nous" à faire des maths avec ces axiomes...
Bon très bien, mais peut-on parler des nombres entiers, de l'addition, de la multiplication, etc, avec juste des ensembles???
Intuitivement les nombres entiers sont des classes d'équivalence obtenues en quotientant la relation "contenir autant d'éléments". Soit! Bah ça commence mal... C'est compliqué!
Apparemment, $\emptyset$ est un excellent représentant du nombre zéro. donc décrétons que $0:=\emptyset$
Sondage: que pensez-vous de $\{\emptyset \}$ pour réprésenter $1$?
Bon, sans attendre votre réponse, je vous informe que {\it la communauté mathématique internationale} a {\bf décidé} (c'est une convention) que $1:=\{\emptyset \}$
Arrggg, maintenant, va falloir s'occuper de 2! Je vais boire un café et je "re"
Moi, il m'en vient un sans effort: $\{0;1\}$!!! Autrement dit, les 2 qu'on a déjà fait. En fait, je pense que vous êtes tous entrain de vous rendre compte d'un truc, c'est que les nombres entiers naturels vont naturellement "se construire" en continuant comme ça... A chaque fois, le "suivant" est l'ensemble est l'ensemble de ceux que vous avez déjà construits et c'est "terriblement" canonique lol...
L'entier naturel $n$ est l'ensemble $\{0;..;n-1\}$. C'est rigolo car c'est {\bf une définition!}
$n:=\{0;..;n-1\}$
Sauf que franchement, j'ai abusé avec mon "n-1"...
Commençons par une chose peut-être plus simple: la notion de successeur ($8$ est le successeur de $7$, $55$ est le successeur de $54$, etc)
D'une manière plus générale, dans notre parafigme, comment va-t-on faire pour définir une notion respectable de "successeur" de n'importe quel "entier"?
Avouez franchement qu'on aura réussi (condition suffisante!!!) si on parvient à donner un sens carrément général à la notion de successeur de n'importe quel objet
Je voudrais rajouter un élément, UN SEUL élément à $F$. Comment faire?
Il y a un problème!!!
En effet, si par la plus grande des malchances, $F$ contient déjà tous les objets du monde, je n'ai aucun espoir de parvenir à lui {\bf rajouter} un élément... Dans le sens que rajouter veut dire trouver un élément qui ne lui appartient pas déjà.
C'était bien au fait cette pièce, t'as aimé?
Je précise aux collégiens et aux lycéens qui pérégrinent sur ce forum que la référence d'Alexandre Vandeville est une référence culturelle!
{\it Le monologue du vagin...} est le titre d'une pièce de théatre sortie il y a quelques années. Je ne l'ai pas vue
Mais au lieu d'en donner une description formelle, je vous propose plutôt un slogan laconique: au lieu d'appliquer la supercompréhension à toutes les "collections" d'objets, on l'applique à "toutes les petites" collections.
Mais on ne définit pas le mot "petit". Disons que chaque démonstration qui aboutit à une contradiction et qui n'utilise que des instances de la supercompréhension (en plus de AC et de l'ax d''extensionnalité) "prouve" que l'une des collections (supposée contenir les mêmes éléments qu'un certain ensemble) est "grosse" (dans le sens "non-petite")
Exercice:
1) prouver que les ensembles bien fondés forment une collection qui ne peut pas être un ensemble.
2) Prouver que si $a$ est bien fondé alors $a\notin a$
On considèrera qu'elle n'a de sens que pour les ensembles bien fondés: $x+1$ est juste l'ensemble obtenu à partir de $x$ en lui rajoutant $x$ comme élément. Si $x$ est bien fondé alors on a bien {\bf rajouté} un élément à $x$.
Redite: par définition, le successeur de $x:=$l'ensemble des éléments qui sont dans $x$ ou égaux à $x$.
Et c'est exactement ce qui s'est passé dans les posts précédents avec les premiers entiers naturels. $n+1:=n\cup \{n\}$ (exercice)
Maintenant, je tente de définir une notion d'addition (sur les entiers naturels) {\bf en respectant les gens} (c'est à dire en évitant de le faire par récurrence, à partir de la notion de successeur, ce qui serait se foutre du monde...). D'ailleurs, je ne vais pas vraiment "définir", mais plutôt "officialiser" sa "vox populi-définition"!!
Cependant, AVANT, il faudrait peut-être se mettre d'accord sur ce que veut dire "entier naturel". Comme on l'a vu, $0$ (c'est à dire $\emptyset$) en est un. Et tout successeur d'un entier naturel est un entier. Et à priori, ce sont les seuls lol (qu'est-ce que ça veut dire ça?) à être des entiers naturels, ces objets-là...
{\bf Définition:}un ensemble ($A$) inductif est un ensemble qui contient $0$ et est stable par successeur, cadire que pour tout $x$ qui $\in A$: $x+1\in A$.
{\bf Définition:} $z$ est appelé "entier naturel" si tout ensemble inductif le contient.
Je n'ai pas tout lu, mais puisque personne ne te répond et que tu te donnes du mal à taper, je te donne mon avis, qui, comme son nom l'indique, n'engage que moi !
J'admets que pour un logicien, ces questions puissent être de la plus haute importance. Cependant, je ne m'intéresse pas du tout à ces questions car, selon moi :
Elles concernent les maths mais ne sont pas des maths.
Cette réaction te surprendra peut-être.
Mais je pense qu'elle n'est pas isolée. En effet, si profond que soient les résultats produits par la métamathématique (je pense bien sûr aux travaux de Gödel ou Cohen) je crois savoir qu'une grande majorité de mathématiciens s'en soucie peu.
Ce n'est bien sûr pas un argument, mais si ça peut alimenter le débat...
PS : Tu me trouveras peut-être prétentieux lorsque je me permets de dire que telle chose "n'est pas des maths" et je n'aurai rien à objecter.
Ciao ciao.
{\bf Définition:} un ensemble $F$ est dit fini quand il existe une bijection entre un entier naturel et lui.
Désolé, je vais accélérer un peu, je n'ai pas envie d'y passer la nuit... Je redéfinis vite fait ce que signifie les mots {\it applications, injections surjections, bijections}, mais ensuite, je vous considèrerai comme suffisamment "érudits" et "entrainés" pour faire le raccord entre la "religion ensembliste" et les maths telles que vous les avez rencontrées dans vos études de premiers cycle lol
Les expressions françaises suivantes sont définies de la manière suivante:
$(x,y)$ est une abréviation de "ensemble des 2 éléments suivants: l'un contient pour seul élément $x$ et l'autre contient 2 éléments (ou 1 seul si $x=y$): $x$ et $y$
<<$f$ est une {\bf application} de $A$ dans $B$, si $f$ est un ensemble de couples $(x,y)$ avec $x\in A$ et $y\in B$ telle que pour tout $x$ dans $A$ il existe un UNIQUE $y$ dans $B$ tel que $(x,y)\in f$. Cet unique $y$ s'appelle l'image de $x$ par $f$ et se note $f(x)$>>
<<$f$ est une {\bf injection} de $A$ dans $B$, si $f$ est un ensemble de couples $(x,y)$ avec $x\in A$ et $y\in B$ telle que pour tout $x$ dans $A$ il existe un UNIQUE $y$ dans $B$ tel que $(x,y)\in f$ et telle que pour chaque $y$ dans $B$ il n'y a pas plus d'un seul $x$ dans $A$ tel que $(x,y)\in f$>>
<<$f$ est une {\bf bijection} de $A$ dans $B$, si $f$ est un ensemble de couples $(x,y)$ avec $x\in A$ et $y\in B$ telle que pour tout $x$ dans $A$ il existe un UNIQUE $y$ dans $B$ tel que $(x,y)\in f$ et telle que pour chaque $y$ dans $B$ il y a un unique $x$ dans $A$ tel que $(x,y)\in f$>>
Non, mais surtout, je pense que la preuve de l'indépendance de l'hypothèse du continu sur un fil de ce forum a une valeur culturelle non négligeable. J'ai remarqué que beaucoup de gens (matheux "ordinaires") ouvrent des yeux "complexés" bien que "fascinés" quand on l'évoque.
Ce qui est interessant en soi, ce n'est pas l'hypothèse du continu, mais {\bf la preuve qu'elle est indécidable}, non?
Mais t'inquiètes, si je vois que le nombre de "lecteurs" du sujet n'augmente pas assez vite, j'arrêterai d'écrire... En fait, c'est comme si je jouais à un jeu électronique: je regarde le nombre de lecteurs défiler et je trouve ça grisant...
En plus, j'essaie de "sauter le diner" (j'ai repris 4kg en 2 semaines et ça me saoule grave!)
$a,b,c$ étant des entiers, la phrase {\it $c$ est la somme de $a$ et de $b$} est définie comme étant l'énoncé suivant:
{\it il existe 3 ensembles finis A,B et C tels que A et B sont disjoints et leur réunion est C, et de plus A est en bijection avec a, B avec b et C avec c}
Exercice: prouver que pour tout $a,b$ il existe un unique $c$ qui soit la somme de $a$ et de $b$ et que l'opération $+$ est commutative et associative. De plus prouver que le successeur de $n$ est $n+1$ au sens de l'addition de $n$ avec $1$.
Ce qu'on appelle une "fraction" est sujet à polémique. On voudrait bien pouvoir parler d'un nombre qui donne $2$ quand on le multiplie par $3$, mais, hélas, il n'y en pas qui soit "entier naturel". De même, on voudrait bien parler des nombres {\bf négatifs}... Il v ay avoir de la négociation car je vous rappelle ce qu'est la déontologie de la science: n'accepter que ce qui est absolument sûr et certain (et "donc" prouvé). N'oubliez pas qu'indépendamment de son intérêt, la science garantit que vos voyages au soleil ne finiront pas par un crash
Du coup, il serait peu honnête de fonder les maths de l'école primaire et du collège sur des axiomes "risqués".
Mais comment éviter tout risque? Comment s'assurer qu'une croyance en l'existence de $\frac{2}{3}$ ne conduira pas les ingénieurs à fabriquer des avions qui s'écraseront avec un taux de $1\%$ {\bf ce qui est énorme}?!!
Etant donné des entiers $a,b$, le couple $(0,(a,b))$ sera provisoirement appelé "désir d'un nombre qui donne $a$ quand on le multiplie par $b$" et noté "fraction$\frac{a}{b}$". Une chose est certaine: ce désir existe. On peut maintenant se demander si ce désir est mégolo ou modeste.
Et puis on peut aussi se demander quand 2 désirs de ce genre peuvent être satisfaits par un "même nombre de rêve". Ce sont des questions tout à fait respectables, et vous connaissez les réponses aussi bien que moi.
Exercice: je vous laisse écrire les définitions formelles des phrases françaises suivantes:
<<les fractions$\frac{a}{b}$ et $\frac{u}{v}$ peuvent être satisfaites par le "même nombre magique">>
<<la fraction f, représente un désir qui, satisfait, serait la somme des fractions g et h>>
etc...
Je ne vous apprendrai rien en vous rappelant qu'on peut considérer "les nombres réels" comme écrivables par un couple $(n,s)$ où $n$ est un nombre entier et $s$ est une suite de chiffres, les chiffres étant les éléments de l'ensemble $\{0,1,2,3,4,5,6,7,8,9\}$. Cependant, il n'est pas tout à fait exact d'identifier un $(n,s)$ à un nombre réel. Si une suite se termine par que des "9", on peut la changer en la suite obtenue en remplaçant tous les 9 finaux et en augmentant de 1, le dernier chiffre différent de "9".
En fait, là encore, il s'agit de "désir". On "désire" un nombre compris entre $n$ et $n+1$, et les digits de la suite $s$ représente des précisions de notre "désir"...
Or les écritures décimales décimales du genre $0,176324...$ qui ne contiennent pas de "9" parmi les digits désignent chacune un nombre réel différent. A elles seule, elles sont plus nombreuses que les nombres entiers.
En termes de "cardinaux" (notion que je vous laisse redéfinir), on peut donc dire que $card(\N)<card(\R)$. L'hypothèse du continu (sujet de ce fil) dit qu'il n'existe pas de cardinaux strictement compris entre celui de $\N$ et celui de $\R$
Comme avant, Pour établir que cette hypothèse n'est pas décidable, nous allons faire pareil qu'avant: nous allons "désirer" un cardinal strictement compris entre le dénombrable et le continu, et voir que ce désir n'est pas trop mégalo (que ce n'est pas demander l'impossible)...
qui connait les éditions Cassiny? Parce que voilà ce que je propose: un interlocuteur vient, avec moi, remplir ce fil en posant des questions, en réagissant, etc, etc... de plus il garde les copies "latex" de ce fil, de plus, il les peaufine (fautes d'orthographe, etc) et finalement, à l'arrivée, dans une ou 2 semaines, on produit un "joli" petit bouquin de 100 pages qu'on propose à André Bellaiche (éditions Cassiny) d'éditer.
Tous les intervenants, à part le "rédacteur" touchent à eux tous $30\%$ des droits, le rédacteur touche $30\%$ et moi je touche $40\%$ (je suis un peu fauché lol). Donc les candidats rédacteurs, signalez-vous, qu'on négocie...
***
Avant de quitter ce fil, préparez-vous à la suite (lol comme dans les séries télé): nous allons désirer la fausseté de l'hypothèse du continu. Ce désir, au même titre que le désir des nombres rationnels "les fait exister" via les paradigmes ensemblistes, qui, finalement, offrent une structure "isomorphe" au désir qui est "satisfaction" du désir (ce n'est pas toujours possible et semble caractériser la démarché mathématique...) va être exprimé {\bf d'une manière très simple} et très sincère. Et la grande idée de Cohen a été de remarquer que, sans pour autant les faire exister (sinon on prouverait ainsi que l'hypothèse du continu est fausse), les désirs de la fausseté de HC sont des objets suffisamment "ressemblant" à ce que seraient leurs satisfaction pour qu'on puisse conclure qu'ils écartent toute chance de prouver leur inexistence.
Vous allez ainsi rentrer dans un monde très fantomatique et très suggestifs et vous rendre compte que nous sommes entourés "d'esprits frappeurs".
En même temps ce sera une introduction à la façon dont on pense aussi en mécanique quantique...
A suivre...
De toute façon, ce sera utile!!!
Un {\it ordinal} est un ensemble (intuitivement) obtenu en partant de $0$ (lensemble vide) et en passant autant qu'on veut de fois au successeur, ou à la réunion (d'ordianux déjà construits).
La définition "officielle" est : c'est un ensemble {\it bien ordonné} par la relation $\in$ et "transitif" (cadire qui contient les éléments de ses éléments).
Exercice: prouver l'équivalence des 2 définitions (l'informelle et la formelle)
{\bf Théorème:} il y a beaucoup d'ordinaux (en ce sens, qu'en tant que collection, ils ne forment pas un ensemble)
Preuve: soit $E$ l'ensemble des ordinaux. $E$ est un ordinal (exercice facile). Donc $E\in E$ contradiction car alors l'ensemble réduit au seul élément $E$ n'a pas de minimum (la suite $E,E,E...$).
{\bf Remarque:} l'ensemble des entiers naturels est un ordinal et son autre nom traditionnel est "$\omega$"
Le {\it cardinal} d'un ensemble $E$ est le plus petit ordinal $\alpha$ qui est en bijection avec $E$.
Exercice: l'axiome du choix entraine qu'il en existe toujours un
Pour prouver l'indépendance de HC, voilà le projet:
On va prendre un ordinal $Z$ suffisamment grand pour qu'il y ait tout pleins de cardinaux compris entre $\N$ et $Z$ et puis on va fabriquer des "désirs" $d_\alpha$, $\alpha$ variant sur $Z$ de réels tous 2 à 2 différents.
Bien sûr, nous n'allons pas pouvoir prouver qu'ils existent vraiment.
Nous allons juste prouver qu'ils sont des désirs "suffisamment inoffensifs" pour ne pas être "destructibles" par une preuve de leur inexistence!
Vous pourriez presque le faire vous-mêmes maintenant que vous avez tous ces indices et "mériter" la médaille field qu'a obtneu Cohen pour cette démarche...
Ben j'ai bien aimé lire tout ça moi... j'ai tout lu et j'attend la suite donc. ça m'a occupé pendant 2 heure au taf (suis informaticien et j'ai la nostlagie des math...)
1) j'ai dit à un moment que tout ensemble $E$ est en bijection avec au moins un ordinal.
Preuve: soit $E$ un ensemble. La collection des ordinaux $\alpha$ qui sont injectables (il existe une injection de $\alpha$ dans $E$) dans $E$ sans être surjectables (il existe une surjection de $\alpha$ sur $E$) est une {\bf petite} collection et c'est donc un ensemble, qui de plus est un "segment initial" des ordinaux (s'il contient $\alpha$ il contient tout $\beta<\alpha$)
{\bf Cet ensemble est un ordinal} qui est en bijection avec $E$ (exercice).
{\bf Remarque: à aucun moment je n'ai justifié que la collection ci-dessus est petite!}
2) Lors d'un prochain post je prouverai un théorème qui ne porte pas le nom d'un auteur mais qui contient à peu près toute la théorie du forcing. En voici un résumé informel:
Soit $P$ une formule propositionnelle, éventuellement fabriquée avec des conjonctions infinies. Alors:
ou bien, elle a un "modèle"
ou bien, $P\to tout$ est prouvable de la manière habituelle, en enchainant des évidences
ou bien, il existe un "monde de rêve" dans lequel elle a un modèle et dans ce monde, aucun ordinal supplémentaire n'est "créé" par ce modèle
Ce qui est intéressant est la troisième alternative qui ne survient pas quand la formule $P$ est "héréditairement" dénombrable (fabriquée à tous les échelons avec des conjonctions au plus dénombrables). Cette troisième alternative est TYPIQUE du forcing...
Voici un exemple très simple d'une telle formule:
pour chaque nombre réel $x$, vous ajoutez une famille de lettres $A_x^n$ où $n$ parcourt $\N$
P est la conjonction des $D_x$ et des $B_{x,y}$, $x\neq y$:
Pour chaque $x$, la formule $D_x$ est définie par $C_x\to tout$.
$C_x$ étant la conjonction des $A_x^n$, pour $n\in \N$
Pour chaque $x,y$ la formule $B_{x,y}$ est la conjonction des ($[A_x^n\to tout]$ et $[A_y^n\to tout])\to tout$ pour $n$ variant dans $\N$
Intuitivement, $P$ exprime le désir d'un injection de $\R$ dans $\N$. On peut prouver que $P$ n'a pas de modèle, mais on ne peut pas prouver $\neg P$ en termes de logique propositionnelle.
{\bf T'es payé combien de l'heure?}
{\bf théorème: }(de Gale-Stewart)
{\it Soit $E$ un ensemble et $F$ une partie de l'ensemble des suites $u$ à valeurs dans $E$. On suppose que $F$ est "fermé" dans le sens que si $u\notin F$ alors il existe un entier $p$ tel que toute suite $v$ qui coincide avec $u$ jusqu'à $v_p$ est hors de $F$.
Soit $G$ le jeu suivant: 2 joueurs "pair" et "impair" (ce sont leur prénom) jouent alternativement les valeurs $u_{2n}$ et $u_{2n+1}$ et construisent une suite $u$. Le joueur "pair" est déclaré gagnant si la suite $u$ est dans $F$
L'un des 2 a alors une stratégie infaillible qui lui permet de battre l'autre quoiqu'il fasse. }
***
Tous les ordinaux ont "presque" l'air dénombrable... Vous allez voir que l'axiome du choix intervient d'une manière assez drastique dans des questions de ce genre...
Notons $\omega _1$ le premier ordinal non dénombrable et, en appliquant l'axiome du choix, pour chaque $\alpha<\omega _1$, notons $i_\alpha$ une injection de $\alpha$ dans $\N$.
On fixe un ordinal $e<\omega _1$
Voici un jeu amusant $G_e$, qui oppose Toto à Gertrude:
Toto commence en disant un entier $n$ ou $\infty$ appelé "option"
Ensuite, Gertrude joue un entier $p$ et un ordinal $\alpha_1<\omega_1$
Puis Toto répond par un ordinal $\alpha_2>\alpha_1$
Puis Gertrude répond par un ordinal $\alpha_3>\alpha_2$
Il ont le devoir de jouer des ordinaux supérieurs à $e$ et $<\omega _1$
Leur suite a une borne supérieure $\beta<\omega _1$, sinon $\omega _1$ serait dénombrable...
Toto gagne la partie si $i_\beta(e)=option\in \N$ ou si [$option=\infty$ et $i_\beta(e)\neq p$]
Justifier les choses suivantes:
1) Il existe $e$ tel qu'aucun des 2 joueurs n'a de stratégie gagnante au jeu $G_e$
2) ce jeu est presque "régulier" en un sens que vous pouvez essayer de préciser. Le mot "régulier" signifie qu'il s'en faut de très peu pour qu'aucun n'ait de stratégie gagnante en un sens que vous préciserez. En particulier, expliquez en quoi ce jeu ressemble beaucoup à un jeu auquel le théorème de Gale-Stewart pourrait s'appliquer.
Pourtant un argument plutôt célèbre conduit à la conclusion contraire:
Le voici: soit $\phi$ une application de l'ensemble des sous-ensembles stricts de $\R$ dans $\R$ telle que pour toute partie $A\neq \R$ de $\R$, $\phi (A)\notin A$.
soit $u$ telle que $u_\alpha = \phi(\{u_\beta}/\beta < \alpha\}$ pour des ordinaux $\alpha$ jusqu'à plus possible. Notez que si tout $u_\alpha$ "existait", $u$ serait une injection des ordinaux dans $\R$. Donc, il arrive un moment, disons pour un certain $\kappa$ où $\{u_\beta}/\beta < \kappa\}=\R$. Exercice: cet ordinal $\kappa$ n'est pas dénombrable.
Voici l'argument "externe": Soit $(E,R)$ avec $R$ une relation binaire incluse dans $E^2$. On la suppose "extensionnelle": si $a\neq b$ alors il existe $x$ tel que $xRa$ n'équivaut pas à $xRb$.
Si pour tout a, il existe b avec $bRa$, on a fini (on peut dire en quelque sorte que l'ensemble vide "échappe" à $(E,R)$). Sinon, soit $u_0$ le seul et unique $a$ tel que pour tout $b$ on n'a pas $bRa$. Puis, tant que c'est possible, $u_\alpha$ est défini comme l'élément unique $a$ de $E$ (s'il existe) tel que pour tout $b\in E$, $bRa$ ssi il existe $\beta <\alpha $ tel que $b=u_\beta$.
Le premier $\kappa$ tel qu'on ne peut construire $u_\kappa$ représente "la hauteur" de "l'univers $(E,R)$. Et les $u_\alpha$ pour $\alpha <\kappa$ sont une sorte de colonne vertébrale "canonique" de cet univers.
Au passage, ça donne une "version" tout en douceur du fait qu'il n'existe pas de surjection de $E$ sur $P(E)$
Serait-ce la méthode inventée et employée par Cohen afin de prouver l'indécidabilité de l'hypothèse du continu généralisée ?
Je ne redéfinis pas ce qu'est une algèbre de Boole complète?
Exercice:
On définit un petit problème général de la manière suivante:
On se donne un ensemble de lettres (éventuellement très grand, non dénombrable, etc) qui vont par paires. Intuitivement 2 lettres d'une même paire seront dites "contraires" l'une de l'autre.
Puis on se donne un ensemble $E$ d'ensembles de ces lettres. But du jeu: trouver un ensemble V de lettres de façon que chaque $X\in E$ rencontre V mais de manière aussi qu'aucune paire $\{x,$contraire de $x\}$ ne soit incluse dans V.
Evidemment l'existence de V dépend de $E$.
Il y a 3 catégories de $E$.
1) Ceux pour lesquels "il est évident" (ou plutôt démontrable par enchainement d'évidences) que V n'existe pas
2) Ceux pour lesquels, il existe un ensemble V
3) Les autres.
Une algèbre de Boole est une généralisation de l'ensemble $\{vrai,faux\}$ muni de "ou" et de "et". La grande découverte de Cohen a été de remarquer que ces notions de $vrai/faux$ {\bf ne sont jamais utilisées} distinctement des valeurs d'une algèbre de Boole. Autrement dit, quand le cerveau humain "raisonne" il aime bien avoir l'impression de parler d'un unique "vrai" et d'un unique "faux", mais en fait, sur le plan mathématique, il ne s'agit là que d'un confort "psychologique".
Dans une algèbre de Boole complete, la notion de borne inférieure représente le "et" et la notion de borne supérieure représente le "ou"
Le vrai est plus grand que tout le monde, et le faux est plus petit que tout le monde.
Dans la suite toutes les algèbres de boole sont supposées completes
Prouver donc la chose suivante:
Soit $E$ comme précedemment. On suppose qu'il n'existe pas d'enchainement d'évidences que V n'existe pas. Il existe alors forcément une algèbre de Boole $IB$ telle que on peut affecter à chaque lettre $x$ un élément $v(x)$ de cette algbère de Boole avec la propriété suivante:
Pour chaque ensemble $A$ dans $E$, la "réunion" (borne supérieure) des $v(x)$ pour $x\in A$ vaut le vrai de $IB$, cadire $1_{IB}$.
2 lettres complémentaires $x,y$ sont telles que $v(x)$ et $v(y)$ ont une borne inférieure égale au faux de $IB$, cadire $0_{IB}$.
{\bf Ainsi, si on remplace le $vrai/faux$ habituel par une algèbre de Boole, on peut éviter la situation 3) ci-dessus. C'est le théorème de complétude de la logique infinitiste...}
{\bf Remarque: pour la compréhension de la suite, ce post n'est pas nécessaire}
Montrer qu'il existe une algèbre de Boole complète $B$ qui donne une solution à ce système en nombres {\bf \it pseudo}-complexe.
Qu'est-ce qu'un nombre pseudo-complexe?
Réponse: c'est une "onde" sur le plan complexe (non, je déconne, mais bon...).
Précisément: c'est une application $\sigma$ de $\C \times \R^{*+}$ dans B qui est "cohérente" dans le sens suivant: si le disque de centre $z$ et de rayon $r$ est inclus dans le disque de centre $y$ et de rayon $s$ alors $\sigma(z,r)\leq \sigma(y,s)$. Par ailleurs, si la distance entre $z$ et $y$ est supérieure à $r+s$ alors la borne inf de $\sigma(z,r)$ et de $\sigma(y,s)$ est $0_B$. De plus, la borne sup des $\sigma (0,n), n\in \N$ est $1_B$
On en était où? Aux ordinaux! Mais je crois que j'avais tout dit à leur propos (mis à part bien sûr, le "vif du sujet" qui ne sera abordé que quand on va traiter frontalement le "forcing")
Passons au minimum vital de logique: en maths, quand on prouve quelque chose, on écrit un texte. Pour prouver qu'il n'existe pas de preuve telle que blabla, on va devoir prouver qu'il n'existe pas de texte tel que patati, patata...
Mais à quel genre de texte ressemble une preuve?
Version propositionnelle: si $P$ est une tautologie, alors il existe une preuve de $P$ dans le sens qui suit:
il existe un "arbre" qui dont les feuille sont des axiomes "banals" et dont la racine est $P$ et dont les "enchainements" sont des modus ponens.
La phrase {\it les "enchainements" sont des modus ponens} signifie que chaque sommet de l'arbre étiqueté $Q$ a 2 fils, l'un étiqueté par $R\to Q$ pour une certaine $R$ et l'autre étiqueté par $R$.
Autrement dit, on n'a que 2 "droits":
1) partir d'axiomes
2) de $A\to B$ et de $A$ (déjà établis) {\it déduire} $B$
{\bf Ce seront les choses qu'on s'autorisera!}
A tout moment on a une formule dite "la phrase courante" $Q$ et le prouveur propose une phrase $R$:
Le "sceptique" répond alors en remplaçant la phrase courante par $R$ ou par $R\to Q$
Le prouveur ne peut prétendre gagner la partie que si la phrase courante fait partie d'une liste "d'axiomes offciels". De cette liste "dépend" la logique considérée:
les $A\to (B\to A)$ et les $[A\to (B\to C)]\to [(A\to \to (A\to C)]$ suffisent à caractériser la logique intuitionniste.
Si on y rajoute les $((A\to \to A)\to A$, on obtient la logique classique.
(Tout ça, je vais le prouver)... Ca permettra d'ailleurs de vous "entrainer" à la suite.
Donc dans le jeu "intuitionniste", quand la phrase courante est de la forme $A\to (B\to A)$ ou de la forme $[A\to (B\to C)]\to [(A\to \to (A\to C)]$ la partie s'arrête et le sceptique PERD.
Donc dans le jeu "classique", quand la phrase courante est de la forme $A\to (B\to A)$ ou de la forme $[A\to (B\to C)]\to [(A\to \to (A\to C)]$ ou de la forme $((A\to \to A)\to A$, la partie s'arrête et le sceptique PERD.
Si on se place dans une algèbre de Boole complète qui "croit" aux axiomes supplémentaires (ceux qu'on rajoutera aux axiomes ci-dessus) de la théorie des maths, alors l'algèbre en question croira aussi aux théorèmes!
Ici, dire qu'une algèbre de Boole $B$ "croit" à un énoncé P signifie juste que l'énoncé P ne peut que recevoir la valeur $1_B$ dans toute "interprétation".
Une "interpretation" est une application $f$ qui associe à chaque phrase $P$ une "valeur de vérité" $f(P)\in B$ et telle que $f(X\to Y)=$ la réunion du complémentaire de $X$ et de $Y$. Par complémentaire de $X$ dans une algèbre de Boole, on entend la borne supérieure des éléments $Z$ qui sont orthogonaux à $X$ et on dit que $X$ et $Y$ sont orthogonaux quand leur borne inf est $0_B$
Imaginons maintenant qu'on parvienne à fabriquer une algèbre de Boole qui "ne croit pas" à l'hypothése du continue, alors ça voudra dire que l'hypothèse du continu n'est pas prouvable à partir des axiomes
Cependant, il va falloir utiliser autre chose que de la logique propositionnelle pour ça... Mais vous allez voir que ce n'est pas là que se trouve la difficulté!
Je vous propose (avant de prouver ce qui précède) un petit exercice qui permettra aux surdoués de prendre un raccourcis pour comprendre le mécanisme global
Soit $E$ un ensemble {\bf ééééééééénoooooorrrrrmmmeeeee}
On va rajouter des "réels" virtuels, mais en plus de ça on va le faire d'une manière que ça ne rajoute pas grand chose de plus qu'eux-même.
En particulier, ça ne rajoutera pas de surjections "virtuelles" entre des ensembles de taille différente.
Voici donc l'exercice:
$E$ est supposé de cardinal bien plus grand que $\R$
Une famille $(a_i)_{i\in I}$ d'éléments d'une algèbre de Boole est appelée "antichaine" quand $a_i$ et $a_j$ sont orthogonaux pour chaque $(i,j)$ tel que $i\neq j$
$T(B)$ est l'ensemble des antichaines de $B$
Prouver qu'il existe une algèbre de Boole complète $B$ qui a les propriétés suivantes:
1) si une famille $(a_i)_{i\in I}$ d'éléments de $B$ est une "antichaine" alors $I$ est obligé d'être dénombrable
2) il existe une application $s$ de $E\times \N$ dans $B$ avec la propriété suivante:
pour chaque couple $(x,y)\in E^2$, {\it l'objet $s(x,.)$ et l'objet $s(y,.)$ disent avec la valeur $1_B$ que le réel virtuel $f(x)$ et le réel virtuel $f(y)$ sont différents}. ("$f$" étant une sorte d'injection virtuelle de $E$ dans un ensemble qui contiendrait des réels virtuels en plus des vrais réels)
Je précise la phrase énigmatique {\it l'objet $s(x,.)$ et l'objet $s(y,.)$ disent avec la valeur $1_B$ que le réel virtuel $f(x)$ et le réel virtuel $f(y)$ sont différents}:
Soit $x\neq y$ des élément de $E$, et $n$ un entier. Ceux qui sont cultivés en MQ pourraient comprendre l'idée que $s(x,n)$ représente une sorte d'amplitude pour que {\it le réel associé à $x$ via "$f$", en écriture binaire, commence par $0,...$ et son $n$-ième digit vaut 1. }
Du coup, voici la traduction de la phrase {\it l'objet $s(x,.)$ et l'objet $s(y,.)$ disent avec la valeur $1_B$ que le réel virtuel $f(x)$ et le réel virtuel $f(y)$ sont différents}:
<<on note $w(x,y)$ la borne $inf_{n\in \N}$ dans $B$ de ($s(x,n)$ inter $s(y,n)$) union (l'orthogonal de $s(x,n)$ inter l'orthogonale de $s(y,n)$)). Alors $w(x,y)=0_B$>>
Bien sûr "$f$" est une vue de l'esprit, je n'en parle que "pédagogiquement" dans l'exercice.
Pour ceux qui ne sont pas habitués à la mécanique quantique, $s(x,n)$ représente une sorte de {\bf probabilité} pour que {\it le réel associé à $x$ via "$f$", en écriture binaire, commence par $0,...$ et son $n$-ième digit vaut 1. }
Mais cette probabilité n'est pas un élément de $[0;1]$
Je suis donc "condamné" à en donner une:
C'est un quadruplet $(B,0_B,1_B,\leq)$ avec:
1) $\leq$ est une relation d'ordre
2) $0_B$ est plus petit que tout le monde
3) $1_B$ est plus grand que tout le monde
4) la borne inf pour le "et" vérifie les propriétés de distributivité du "et"/"ou" (avec la borne sup pour le "ou"). Et idem en échangeant "et" et "ou".
5) "Complète" si tous les ensembles ont une borne inf.