le forcing expliqué aux matheux ordinaires

christophe c

Je mets ici une preuve d'un fait dont il est question au lien suivant: http://www.les-mathematiques.net/phorum/read.php?7,516076,604154#msg-604154



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)

christophe c

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: http://www.les-mathematiques.net/phorum/read.php?4,601037,601373#msg-601373


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?

christophe c

Pour terminer un peu sur AD (provisoirement), j'ai mis sur le fil http://www.les-mathematiques.net/phorum/read.php?2,549404,610174#msg-610174

une question dont la réponse, si on suppose AD est non. L'idée serait d'essayer de prouver que la réponse est oui (la preuve que la réponse est non est assez inhabituelle et tordue), d'où une sorte d'espoir de "casser" AD de cette manière.

[Je me sens visé par ici :X AD]

christophe c

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.

christophe c

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

christophe c

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)

christophe c

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.

christophe c

Erratum, c'est "bats-toi toi-même sauf quand pas possible".

(Mais quand pas possible, c'est donc qu'on a atteint la stratégie infaillilbe)

christophe c

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

christophe c

oups, ça fait longtemps que je n'ai pas alimenté ce fil, je digresse pour répondre à la toute fin du post: http://www.les-mathematiques.net/phorum/read.php?3,625112,626775#msg-626775


Je vais essayer de résumer de manière séche et sans commentaire "embrouillant" car trop longs la situation de ce que le préjugé populaire appelle "le raisonnement par l'absurde" et qui n'est qu'un "banal" axiome comme il y en a plein d'autres en maths. Je ne traite que le cas "propositionnel" pour ce sujet de conversation, ça suffit.

Tout d'abord, sur quoi se fonde la science?
Réponse: sur la recherche de certitude.

Du coup, moins on a de notions premières plus on a la possibilité de permettre à des sceptiques d'exercer leur scepticisme sainement.

Le statut quo le plus naturel et le plus économique semble avoir été de faire reposer la science sur UN seul symbole logique: le "si...alors..." qui s'écrit en abrégé** et UNE SEULE "constante", la phrase "tout" qu'on peut comprendre comme "tout arrive" ou "tout est vrai", etc, etc:

** $A\to B$ := "si A alors B"

On s'autorise alors 3 "catégories d'évidences", valables pour toutes phrases A,B,C:

1) $A\to (B\to A)$
2) $(A\to (B\to C)\to ((A\to \to (A\to C))$
3) $tout\to A$

Par définition: la négation de A, à savoir le truc habituel noté "non(A)" est l'abréviation de $A\to tout$

Pourquoi "cette définition"? Et bien, si vous voulez envoyer un mail à quelqu'un et que votre clavier ne dispose que de mots entiers, mais que tous les mots permettant de construire de près ou de loin une "négation" sont en panne, comment allez-vous envoyer le mail "je ne suis pas allé voir Georges jouer à la pétanque"?

Solution (que la plupart des gens, après sondage, comprennent): vous pouvez taper
"si je suis allé voir Georges jouer à la pétanque alors les poules ont des dents"
Bon, en fait c'est encore mieux d'écrire:
"si je suis allé voir Georges jouer à la pétanque alors tout arrive"
et en abrégeant;
"si je suis allé voir Georges jouer à la pétanque alors tout"

En sciences, "tout" s'appelle "le faux".

Parvenir à le prouver (ce que personne n'a encore réussi à faire), c'est atteindre une sorte de maximum, de "paradis". En effet, à cause de (3), si vous parvenez à prouver "tout", vous avez automatiquement en votre possession "la lampe d'Aladin".

Bref...

Les axiomes 1-2-3 sont insuffisants. Ils constituent ce qu'on appelle les axiomes de la logique intuitionniste.

En ajoutant un axiome de plus (RPA), on obtient une "science" qui permet de "prouver" que toute phrase est "vraie" ou fausse" (ce qui correspond à l'idée intuitive que même si on ne sait pas si une phrase est vraie ou fausse, quelqu'un sait quelque part (par exemple Dieu, ou la NAture, ou le "Destin") si elle est vraie ou fausse, dès lors qu'on précise dans quel monde on est.

Par ailleurs on a l'important "théorème de complétude" qui dit qu'avec (RPA), ou bien on peut prouver P ou bien il existe au moins un monde où P est faux. Ce qui clôt l'affaire.

Alors tout ça c'est très bien, mais on n'a pas vraiment le droit d'inventer un axiome gratuitement, juste pour "réaliser le désir que tout soit comme on trouve que ça doit être, ie que toute phrase soit vraie ou fausse ou le théorème de complétude.

Bé, on a eu de la chance, car on dispose d'un axiome auquel TOUT LE MONDE CROIT (donc on n'a pas triché), qui dit par exemple, que si Madonna n'est pas pas blonde alors elle est blonde. C'est l'axiome $(non(non(A))\to A$ (***)

En désabrégeant, c'est l'axiome:

RPA) $((A\to tout)\to tout)\to A$

Cet axiome est beaucoup plus puissant que sa forme (***) ne le laisse présager.
Exemple d'application:

si on sait que tout nombre non nul peut être multiplié par un nombre de sorte que ça donne 1, on peut prouver que si le carré d'un nombre est nul alors le nombre lui-même est nul. Or je ne connais pas (et je ne pense pas qu'il en existe) de preuve sans RPA de ce théorème.

voici la preuve: au lieu de prouver que $a^2=0\to a=0$, je prouve $non(non(a^2=0\to a=0))$ (c'est là qu'est le RPA)

Je suppose donc que $(a^2=0\to a=0)\to tout$ (+), et j'essaie d'en déduire "tout".

lemme1: si $a=0$ alors tout
preuve: si $a=0$ alors $a^2=0\to a=0$ et donc d'après (+), tout CQFD
conclusion $a$ est non nul.
donc il existe un nombre $b$ tel que $ab=1$.
lemme2: si $a^2=0$ alors $a=0$.
preuve: si $a^2=0$ alors $a=a.1=aab=a^2b=0.b=0$ CQFD
conclusion $a^2=0\to a=0$
Finalement, d'après (+), tout.

Ne pas confondre le RPA avec des preuves de $A\to tout$ tout à fait "intuitionnistes". Par exemple, supposer "A", puis écrire une série de "donc" qui aboutissent à "donc tout", c'est prouver "A\to tout", c'est à dire c'est prouver non(A) et si on n'utilise que les axiomes 1,2,3, on a prouvé intuitionnistement nonA.

Je termine avec pourquoi le RPA est "suffisant" pour garantir que toute phrase est vrai ou fausse.

On rajoute une notion première qui est le mot "ou" et des axiomes incontestables le concernant.

Je prouve que A ou (nonA):
Grace au RPA, il me suffit de prouver que ((A ou nonA)=>tout)=>tout
Supposons ((A ou nonA)=>tout). Alors, A=>tout et (nonA)=>tout et donc A=>tout et (A=>tout)=>tout, et donc tout.

Le "théorème" A ou (nonA) s'appelle "le tiers exclu".

Pour finir, je précise un truc qui pose parfois des problèmes aux non scientifiques:

Théorème: si nonA alors (A=>B).
En effet, nonA est l'abréviation de A=>tout, et il est évident que si A=>tout alors A=>B en particulier. Exercice, le faire juste avec les axiomes 1-2-3.

ccnc

Deux petits compléments au post précédent:

je suis passé un peu vite sur la définition en apparence arbitraire ou "seulement" vox populi*** qui considère
non(A) comme une abréviation de (A=>tout)

*** la science construit des avions dont on veut qu'ils aient moins d'une chance /500000 de s'écraser. Une validation "vox populi" ne suffit pas.

En voici donc une preuve formelle dont on identifie parfaitement les axiomes:

Supposons A=>tout. But, prouver nonA.
de A=>tout, on déduit (non(tout)) => non(A), et donc non(A) (on a considéré que non(tout) est un axiome)

Réciproquement, supposons non(A). Alors (non(tout))=>(non(A)) et donc non(non(A))=>non(non(tout)) et comme A=>non(non(A)), donc A=>non(non(tout)), et finalement, A=>tout car (non(non(tout))) =>tout

Conclusion générale: (nonA) est équivalent à (A=>tout)

Dans la preuve précédente, ont été utilisés explicitement les axiomes suivants:

1) que non(non(tout)) =>tout
2) que A=>non(non(A)) (ne pas confondre avec le RPA)

qu'on peut écrire "(A=>B) donc (non(B)=>non(A))" dans une preuve
qu'on peut écrire "A=>B, et B=>C donc A=>C" dans une preuve,
etc.

J'ai déjà raconté tout ça à divers endroits, mais, ce post et le précédent localisent ce sujet pour un lien éventuel dans d'autres fils.

[Correction selon ton indication, par un modérateur bourré de compassion. AD]

christophe c

Un troisième complément, je poste le programme "universel" en camL qui fait passer (ou boucle) d'une preuve quelconque à une preuve sans coupure***** (et donc "sans axiomes logiques") et la "présente". J'ai essayé de l'écrire de manière "pédagogique" avec des noms longs.

type form = I of form*form | Tout | Pourtout of (ens->form) | Estdans of ens*ens
and ens = Vide | Setof of (ens->form)

type terme = Projection of ens | Lambda of (terme->terme) | Produit of (ens->terme) |Modus of terme*terme | Hypothese of form

type environnement = Fond of form | Pile of terme*environnement | Touche of ens*environnement

type preuve = Comprehension1 of ens*ens*preuve | Comprehension2 of ens*ens*preuve | Paradis | Axiome of form*form | Suppose of form*preuve | Attendrechoixdusceptique of form*(ens->preuve) | Enchaine of form*preuve*preuve | Casparticulier of form*form*preuve


exception Bug of (terme*environnement)


let rec elicut t e = match t,e with

|Modus(u,v) , ee->elicut u ( Pile(v,ee) )
|Lambda f, Pile(u,ee)->elicut (f u) ee
|Produit g, Touche(a,ee) ->elicut (g a) ee
|Projection x, Pile(u,ee) ->elicut u (Touche(x,ee))

|Hypothese s , Fond z->Axiome(s,z)
|Hypothese (I(h,c) as s), Pile(u,ee) ->let cc = Hypothese c in Enchaine(s, elicut u (Fond h), elicut cc ee)
|Hypothese (Pourtout g as z), Touche(a,ee) ->let h1=g a in let h=Hypothese h1 in Casparticulier(z, h1, elicut h ee)
|Hypothese Tout, ee ->Paradis
|Hypothese (Estdans(a,Vide)), ee->Comprehension1(a, Vide,Paradis)
|Hypothese (Estdans(a,(Setof g as b))),ee->Comprehension1(a,b,elicut (Hypothese (g a)) ee)

|tt, Fond (I(h,c) as z) ->let u=Hypothese h in Suppose(z, elicut tt (Pile(u,Fond c)))
|tt, Fond (Pourtout f as z) ->let h x = elicut tt (Touche(x,Fond (f x))) in Attendrechoixdusceptique (z,h)
|tt,Fond (Estdans(a,(Setof g as b)))->Comprehension2(a,b,elicut tt (Fond (g a)))

|_->raise(Bug (t,e))

let rec verite te s=match s with

|Tout->false

|I(h,c)->if verite te h then verite te s else true

|Pourtout g->verite te (g (te g))

|Estdans (u, Vide) ->false

|Estdans (u, (Setof f))->verite te (f u)


On voit que les preuves peuvent toutes se contenter de:

1) faire une abstraction: "(supposons A..... donc donc (A=>B)" (le "titre" Suppose)

2) S'apprêter à prouver $\forall xR(x)$ et disant "donne-moi a, je te prouve R(a)" (le titre Attendrechoixdusceptique)

3) Dire "comme on a supposé $\forall xR(x)$, en particulier $R(a)$" (le titre Casparticulier)

4) Dire: "dans les hypothèses, j'ai A=>B. Prouvons A: ..... donc A; donc B...... donc P" (le titre Enchaine)

La théorie utilisée est la théorie naive sans extensionnalité, celle qui est contradictoire, cela venant de la simplicité qu'il y a à définit un ensemble comme un objet qui à chaque ensemble associe un énoncé (intuitivement, un ensemble est une collection)

Remarque, la contradiction n'est pas gênante puisque dans une preuve tous les axiomes se voient et donc chaque fois qu'est utilisée une instance du schéma de compréhension, dans la preuve, on voit laquelle et on peut (en tant que sceptique) dire "t'abuses là"

Voilà, s'il y en a que ça amuse de convivialiser et d'ajouter des fonctions qui "affichent" les résultats pour des preuves particulières

Remarque: ce sont les avancées de la théorie Krivinienne, de la correspondance de Curry Howard qui valident la à mon avis historique et très jolie boucle récursive de "elicut". Les théorèmes d'élimination des coupures disent qu'elle termine dans tous les "bons" cas. (Evidemment, avec la théorie contradictoire ci-dessus, ce n'est pas dans tous les cas)

Le programme compile bien sous camL

***** ie où on voit "en live" que la conclusion est juste un cas particulier des hypothèses faites.

christophe c

Remarque: la fonction "verite" ci-dessus, n'a rien à voir, j'aurais dû l'enlever avant de poster. Elle boucle ou dit si un énoncé est vrai ou faux à partir d'un témoin (te) qui étant donné une formule pour tout x R(x) prétend choisir un a tel que R(a)=>(pour tout x R(x))

christophe c

Je change un chouya de thème, pour répondre à une question de Martial dans le fil http://www.les-mathematiques.net/phorum/read.php?16,637844,637844#msg-637844

J'ai déjà raconté ce que sont les axiomes de grands cardinaux et énoncé les plus connus. Je recommence et commente un peu comment ils "naissent" (ou plutôt ils sont nés, car on n'en produit plus beaucoup par an )

Je rajouterai des exemples dans les posts suivants. Je ne reprécise pas à chaque fois "sous réserve de consistance de machin truc"

Tout commence avec la notation (plus finalement les axiomes rajoutés d'infini) "IN". Il est "bien connu" que souvent pour prouver un truc fini, on suppose l'infini. On le fait d'une manière honnête, mais ça n'enlève rien au fait qu'on le suppose.

Question: y a-t-il une manière de "monter"?

Réponse oui: par exemple, le fait de "supposer IR" (je résume, IR n'est pas une phrase ) permet de prouver la consistance de l'arithmétique de Peano (improuvable en ne supposant qu'honnêtement le dénombrable, d'une certaine façon).

Le fait de "supposer P(IR)" permet de prouver la consistance de l'arithmétique du second ordre

etc, etc

Au début du siècle, la théorie ZF a formalisé ça d'une manière propre en disant que $\forall E: P(E)$ "existe" et en disant que toute collection qu'on peut de manière définissable voir comme ne contenant pas plus d'éléments qu'un ensemble "déjà là" est elle-même un ensemble.

Ca permet d'avoir IN, IR, P(IR), P(P(IR)), P^3(IR), ..., et grace à (2) d'avoir (intuitivement) aussi sup des P^n(IR), P de ce sup, etc, etc, et ça a clos l'affaire des "maths officielles" en ce sens que 99 pourcents de maths se sont avérées être faites en gros dans P(P(IR)) (et de temps en temps, quand on a besoin d'artillerie, dans P(P(P(IR)), etc.

Bien évidemment, je ne rentre pas dans les détails du lien entre "axiomatique" et "sémantique", ie le fait que le "vrai" P(IR) par exemple (remarque: essentiellement, je rappelle que P(IN)=IR) n'est pas du tout "accédé" par ces méthodes (si tant est qu'il a un sens), mais simplement "l'idée qu'on s'en fait")

La première "limite" pas franchie par ce système conventionnel ZFC (qui résume toutes les maths sans effort, et à condition de connaitre et d'avoir compris la thèse de Church est "définitif" dans son principe, ie toute "révolution" ou "refondation" sera soit dérisoire soit une falsification de la thèse de Church, en gros) est le premier ensemble $E$ appelé "inaccessible" qui comme son nom l'indique vérifie:

1) $E$ est transitif (dans notre contexte, on monte le long d'une échelle ordinale et on ne s'intéresse qu'à des ensembles "bases" qui contiennent tous les truc d'un "palier")
2) $\forall x\in E: P(x)\in E$
3) $\forall A\subseteq E$ si $A\notin E$ alors $\forall x\in E: card(x)<card(A)$

Il est "presque évident" qu'un tel $E$ ne peut être prouvé exister puisqu'il vérifie facilement tous les axiomes de ZFC. Ainsi si on prouvait qu'il existe, on pourrait "lui" appiquer la preuve et obtenir $E_1\ni E_2\ni ...$ (merci à remarque dont j'ai appris l'autre jour comment faire le "appartient" à l'envers)

Bref, on peut monter comme ça longtemps et c'est un peu monotone, en considérant le deuxième, puis le troisième, puis le quatrième etc ensemble inaccessible. Remarque: ce paragraphe prouve en quelques lignes le théorèmes de Godel, soit dit en passant.

Pourquoi le mot "cardinal"? Et bien en fait on est là dans un paradigme où "l'intention" (traduit en syntaxe) rejoint la sémantique, à savoir "qu'on a le sentiment" (bien vérifié pour IN, IR, P(IR), etc, ie pour les petits objets) que la force de la théorie augmente avec la taille des objets qu'on suppose. Par ailleurs, on a aussi le sentiment qu'on "ne risque pas beaucoup plus que la limite Godélienne à les supposer" c'est à dire qu'on applique aux infinis de plus en plus gros la simple même idée que "supposer IN".

Plutôt que traiter avec E,P(E), blabla, on traite le problème cardinalement. Par exemple, par convention, on parle plutôt "du premier cardinal inaccessible" pour parler du "premier ensemble inaccessible". Ceci a été initié par deux remarques historiques célèbres:

1) $card(E)<card(P(E))$ (je ne le reprouve pas )
2) En définissant l'application $V$ qui associe à chaque ordinal $a$ l'ensemble $V_a:=P(\cup_{b\in a} V_b )$, on a que $\cup_{a:ordinal} V_a$ vérifie les axiomes de ZFC et aussi l'axiome de fondation, et ça correspond bien à ce qu'on attend des mathématiques (de tout prouver et de tout fonder, quitte à supposer explictement des trucs, mais en les assumant bien): on part de l'ensemble vide, on prend l'ensemble de ses parties, et on itére ordinalement

Il y a toute une panoplie de théorèmes "triviaux" mais importants qui disent que pour notre thème présent d'étude, les barrières importantes sont en correspondance, ie $a$ est un cardinal inaccessible ssi $V_a$ est un ensemble inaccessible, que $P(V_a)=V(a+1)$, etc.

ZFC fait que quand on franchit une barrière, on franchit un cardinal. Rappel: un ordinal est un cardinal quand il n'existe pas de sujection d'un ordinal plus petit que lui sur lui.

Ca c'était les préliminaires. Le post suivant raconte comment on est monté très haut ensuite.

christophe c

L'axiome divin de grand cardinal, très tôt pressenti par les hommes, et inconsistant est "il existe un ensemble E tel que $P(E)\subseteq E$

Si aujourd'hui cet axiome ne parait pas sérieux, il a quand-même (sous d'autres formes) fait couler beaucoup d'encre. C'est un peu l'analogue d'un entier n qui sera égal à lui-même +1, "chose" (je parle de "l'entier") qui a effleuré tout enfant quand il s'interroge sur l'infini.

Le très célèbre théorème qui empéche P(E) d'être inclus dans E a cependant une plus grande auréole de mystère autour de lui: en effet, un truc tel que x=x+1 n'est pas contradictoire, c'est juste "pas un entier" et les enfants par exemple pensent que c'est une bonne caractérisation de l'infini. Mais mais, mais, le théorème de Cantor (pas de P(E) inclus dans E), lui ne donne pas ce répit, puisqu'il prouve que c'est "tout simplement impossible", que l'objet soit fini ou infini , d'avoir qu'il contient comme éléments tous ses sous-ensembles.

On a donc une "trinité" (3 étages) de puissances:

étage1) le fini
étage2) l'infini consistant
étage3) le "divin" (je rigole), ie les choses tellement puissantes qu'on ne peut pas en parler car les supposer mène à "tout devient vrai" ou encore "tout devient possible", ie les choses appelées académiquement contradictoires.

Je ne suis pas spécialiste d'histoire, mais vient ici se placer une citation (que je ne connais pas, dont j'ai juste en mémoire un extrait): "le paradis que Cantor a créé pour nous blabla". A quoi fait-elle référence?

Réponse: aux ordinaux!
En effet, avec les entiers, on avait une porte de sortie: le désir 'inassouvissable" d'avoir un n tel que n=n+1 menait "au moins" vers un objet dit "l'infini" vérifiant ça.

Avec les ordinaux et l'application $a\mapsto V_a$ pas de porte de sortie. On a le "sentiment" qu'une fois arrivés en haut des ordinaux, on entre à "l'Olympe divine" et qu'elle est tellement inaccessible qu'on a même "la preuve" qu'on ne peut pas en parler.

Aujourd'hui, la convention (très sérieuse) des spécialistes est d'appeler l'axiome de grand cardinal record "0=1".

Et l'étude des grands cardinaux est une étude qui se veut étudier ce qui se passe juste en dessous.

Suite au post suivant

christophe c

Après avoir lu les deux posts précédents, on peut résumer le truc ainsi:

1) la science cherche des certitudes, et du coup est hélas obligée d'assumer, ie de supposer tout ce qu'elle ne prouve pas explictement (en anglais "supposer" se dit "to assume")

2) une technique prudente consiste à monter échelon après échelon le long d'une échelle de certitudes

3) Godel a prouvé que chaque échelon gravi enlève un gramme de certitude

4) On travaillait initialement avec les entiers, ie on passait de n à n+1

5) Cantor a découvert que l'échelon pertinent est le pasage de $n$ à $2^n$

6) ces échelons continuent de se gravir en n'ayant cure que l'endroit où on se trouve soit déjà infini (l'infini n'est qu'une étape qui parait anecdotique aux demi-dieux qui jouent dans les bacs à sables de la cour de l'Olympe (IR; P(IR); le premier inaccessible; etc). C'est le théorème de Cantor: P(E) sera toujours strictement supérieur à E, quelque soit E

7) Cantor a mal fini (bon ok, c'est hors-sujet) et Godel aussi (et la plupart des gens qui se sont intéressés à ça, je me dois d'en informer les aspirants à ces jeux!!!!! ça rend fou)

8) Tout en haut des ordinaux, il y a la "vraie" olympe inaccessible au sens propre, ie les limites de la logique et des maths, qui a le bon gout de "signer" sa présence par une absence présente dans les mots: la contradiction.

Finalement, les ordinaux se sont subsitués aux entiers (qui ne menaient qu'au premier infini) pour former une échelle qui mène jusqu'aux portes du "total univers" en quelque sorte, ou, on peut aussi le voir autrement, qui mènent jusqu'à Dieu, mais pas celui des religions.

Ce n'est cependant pas sans rappeler les évolutions mythologiques qui ont conduit des petits gremlins appelés demi-dieux qui se bastonnaient, limités par divers entraves individuelles, dans les contes mythologiques anciens aux réputées plus sérieuses reflexions ou religions actuelles qui voient Dieu comme bien plus "tout puissant" que je ne sais plus quelle religion voyait Hercule, Thor ou Zeus.

Pour en revenir et couronner la robustesse de cette fondation scientifique (hautement platonicienne ) sur "l'échelle ordinale" (et comme signalée, en fait cardinale (les ordinaux sont des petits joueurs, les vraies étapes sont franchies en passant des cardinaux), signalons le théorème d'élimination des coupures qui dit en gros, que l'exponentielle "échappe" (ie le passage de n à 2^n) à toute "preuve", précisément:

On peut prendre n'importe quelle théorie (consistante) qui parle (entre autre) des entiers, et rajouter un prédicat unaire P (pour "petit") et deux axiomes:

P(0)
$\forall x, entier: P(x)$=>$P(x+1)$

Et bien, il est impossible de définir une propriété Q (à partir de P) telle que:

$\forall n: Q(n)$=>$Q(2^n)$ et $Q\subseteq P$

christophe c

Comme je l'ai répété 1 000 000 000 fois sur le forum, l'objet incontournable pour comprendre les maths infinitistes est L'ULTRAFILTRE.

Après avoir affirmé qu'il existe beaucoup d'ensembles inacessibles, on se retrouve (si on n'a pas d'inspiration) un peu à sec pour "monter" le long de l'échelle ordinale. (Enfin, ils sont déjà pas mal vus qu'il permettent de rendre consistant la théorie ZF + tout ensemble de réels est Lebesgues mesurable)

Dans la suite, je raconte comment on est monté, finalement, par "grands bonds". Par contre, je ne sais pas si je vais respecter l'histoire et l'ordre dans lequel les axiomes de grands cardinaux ont été "inventés/découverts" (j'en ai inventé bcp moi-même et ne sais pas trop les dates de première apparition)

Les ultrafiltres sont des "objets virtuels" qui sont discernables d'un vrai objet seulement en posant une infinité de questions. Voir ma pge "analyse non standard" (je mettrai le lien)

On dispose alors d'un "boulevard" de questions, dont la première fondatrice est "y a t-il des objets virtuels, non réels, mais tels que pour les discerner (s'apercevoir qu'ils sont des fausses cartes d'idendité, des imposteurs) il faudrait poser, non plus seulement une infinité de questions, mais une infinité NON DENOMBRABLES de questions? "

Et la réponse est historiquement à marquer d'une pierre dans l'étude de l'infini: si oui, on ne peut pas le prouver dans ZFC et loin s'en faut!

En termes formels, un ultrafiltre $U$ sur $E$ représente un tel objet s'il est non principal et s'il est stable par intersections dénombrables

Théorème: si un tel couple $(U,E)$ existe, alors il existe un plus petit ordinal (qui est évidemment un cardinal) $k$ tel qu 'il existe un ultrafiltre ok sur l'ordinal $k$. Et $k$ est inaccessible, et même bien plus, il est limite d'inaccessibles, limite de limites d'ina..., etc)

Bon, tout ça c'est très joli, mais techniquement?

Et bien la stabilité par intersections dénombrable produit quelque chose de "prodigieux": un "nouvel univers", PLUS PETIT en largeur que l'univers de départ, MAIS AUSSI HAUT.

En effet, Notons $T$ la classe des fonctions définies sur $E$. Et disons que $fDansg$ quand $\{x\in E/f(x)\in g(x)\}\in U$. Alors pour toute suite de $f_n\in T$, il existe un entier $n$ tel que $f_{n+1}$ n'est pas "dans" $f_n$ (exercice).

Il s'ensuit, qu'on peut faire correspondre à chaque $f\in T$ un élément $\phi (f)$ de sorte que:

$f Dans g\iff \phi(f)\in \phi(g)$ pour toutes f,g de T.

La classe des $\phi(f)$ sera un nouvel univers, appelons le M et DE PLUS, l'application $j$ qui à chaque $x$ associe $\phi(constante_x)$ sera ce qu'on appelle un plongement élémentaire.

C'est à dire que pour tous élements $a_1,...,a_n$ et toute relation $R(x_1,...,x_n)$ écrite avec `$\forall ; \exists; \in$:

$R(a_1,..,a_n)\iff M|=R(j(a_1),...,j(a_n))$

Remarque: dans ce cas particulier, tu vois bien (je parle à Martial) que le plus petit $k$ tel que $j(k)\neq k$ est un cardinal

Du coup, ça donne l'idée de "penser" en termes de plongements élémentaires plutôt qu'en termes d'ultrafiltres. Remarque: la relation "dans" est connue aussi pour les ultrafiltres quelconques, mais on ne dispose plus de la "phi" qui fait apparaitre un nouvel univers en bonne et due forme

Pourquoi "se jeter" sur les plongements élémentaires?

Réponse: à cause de la réciproque suivante!

Soit $j:V\to M$ un plongement élémentaire, tel que k est le premier odinal tel que $j(k)\neq k$. Alors l'ensemble des parties $A$ de $k$ tel que $k\in j(A)$ est un ultrafiltre stable par intersections dénombrables, et même plus que ça, stable par intersections indicées par un ordinal $c\in k$.

Donc ça répond à ta question: le plus petit ordinal $a$ tel qu'un ultrafiltre n'est pas stable par intersections indicées par $a$ est OBLIGATOIREMENT un cardinal (exercice presque évident).

christophe c

Je reprends tes premières questions:

$j(\emptyset)=\emptyset$ (tu vois pourquoi?)

$j(n+1) = j(n)+1$ (idem?)

$\omega$ est l'ensemble des entiers donc $j(\omega)$ est, vu dans $M$ l'ensemble des entiers, donc $j(\omega)=\omega$

(Remarque: $M$ est une collection transitive et contient tous les entiers)

Pour l'anecdote: si $x\in P(\N)$, alors $x\subseteq j(x)$ et $j(x)\subseteq x$ donc $j(x)=x$; etc, etc, etc.

Et finalement pour répondre à ta question "pourquoi les points critiques des plongements élémentaires sont si gros?", c'est le théorème du post précédent (je vais faire un edit et le mettre en bleu): ce sont toujours des cardinaux sur lesquels existent ce qu'on appelle une "normale mesure" (je vais préciser ce que c'est)

christophe c

Une normale mesure sur un ordinal $k$ est un ultrafiltre W sur $k$, non principal et tel que pour toute application $f$ de $k$ dans $k$, il existe $a\in k$ tel que $\{x\in k / x>f(x)$=>$f(x)=a\}\in W$

Je continuerai un peu plus tard

christophe c

Je continue la petite histoire, et après je rentre dans les détails purement formel au cas où tu les souhaiterais sur TES questions précises.

Théorème: (borne de Kunen) il n'y a pas de plongement élémentaire de V dans V. Autrement dit, quand tu as un plaongement élémentaire de V dans M (via par exemple un ultrafiltre sigma additif), $M\neq V$

preuve: soit k le premier ordinal tel que $j(k)>k$. Soit $m$ le premier ordinal tel que $m>k et j(m)=m$. Soit f une fonction de $m^\N$ dans $m$ telle que pour toute partie A de $m$ de cardinal $m$ et tout $x\in m$ il existe une suite $u\in A^\N$ telle que $f(u)=x$. Il existe de telles $f$, je te mettrai un lien vers un post ancien où j'ai mis une preuve sur le forum.
Soit $G$ l'ensemble des $j(x); x\in m$. Il existe alors une suite $u$ d'éléments de $G$ telle que $j(f)$ envoie $u$ sur k. Mais comme $u\in G^\N$, il existe une suite $v$ telle que $\forall n\in \N: j(v(n))=u(n)$. Soit $a$ tel que $f(v)=a$. Alors (j(f)(j(v))=j(a) et donc $k=j(f)(u)=j(a)$ ce qui est contradictoire car $\forall x: k\neq j(x)$ (remarque "a est l'image par f de v donc j(a) est l'image par j(f) de j(v)"). Le fait que $u=j(v)$ est dû au fait que pour chaque entier n, v(n) est l'image par v de n et donc j(v(n)) est l'image par j(v) de j(n) qui vaut n.

Ce théorème explique le sentiment général: une nouvelle façon de dire "0=1" consiste à dire "il existe un plongement de V dans V".

L'intuition commande alors de procéder comme suit: chercher des axiomes qui affirment qu'il existe un plongement élémentaire de V dans M, avec M le plus proche possible de V.

Il y a plusieurs façons de procéder. Je commence directement par la manière la plus violente:

Dans la preuve précédente, on a en fait prouvé que si $j:V\to M$ alors $M$ ne peut pas contenir les "fameuses" $f$ allant de $m^\N$ dans $m$, qui sont essentiellement analogues à des parties de $2^m$, puisque ce sont des parties de $m^\N\times m$

Je ne connais pas les nomenclatures (I1,I2, etc), mais en gros, voici un axiome juste en dessous que l'inconsistant qui affirme l'existence d'une $j:V\to M$ tel que $M^{(2^m)}\subseteq V$)

tu affirmes l'existence d'un $j:V\to M$ avec point critique $k$ et $m$ comme ci-dessus et tel que $M^m\subseteq M$ (et tu peux, je crois même pousser le bouchon jusqu'à $L(2^{V_m})\subseteq M$

Bon, mais ça c'est "l'extrême" qu'on peut énoncer dans cette direction (d'essayer de rapprocher le plus possible M de V)

Si par exemple, tu te contentes de $M^{j(k)}\subseteq M$ tu as déjà beaucoup de choses intéressantes, comme la consistance de la Vopenka conjecture par exemple, qui affirme que toute notion mathématique*** a un "niveau de compacité"

*** une collection est disons "mathématique" quand elle est stable par isomorphisme (ie quand ce qui compte c'est la structure et pas la manière de nommer les objets)

Dire qu'une collection "être bleu" a "un niveau de compacité" c'est dire qu'il existe un cardinal c tel que pour tout ensemble X si toutes les parties de X de cardinal plus petit que c sont bleues alors X est lui-même bleu.



Je te décris une version ultrafiltrante de ce qui précède:

Soit $E$ un ensemble. Soit $W$ un ultrafiltre sur P(E) (sigma additif) tel que:

1) $\forall x\in E$ l'ensemble des parties $A$ de $E$ telles que $x\in A$ est dans $W$
2) pour toute fonction choix $f$, il existe $a\in E$ tel que l'ensemble des parties $A$ de $E$ telles que $f(A)=a$ est dans $W$

Et bien l'astuce de la borne de Kunen prouve aussi que l'ensemble des parties A de $E$ telles que $card(E)>card(A)$ est dans $W$.

(autrement dit, l'objet virtuel représenté par W ne peut pas être une partie de même cardinal que $E$)

Un axiome ultrafiltrant plus fort que la Vopenka conjecture dit que par contre, il existe un ultrafiltre $W$ vérifiant 1 et 2 et aussi tel que l'ensemble des parties $A$ de $E$ telles que $card(A)=k$ est dans W où $k$ est un cardinal tel qu'il existe une famille d'intersection vide d'éléments de W indicée par $k$. (Autrement dit, $A$ est "assez grosse" et de cardinal fixé, comme objet virtuel).

Ca entre légèrement en conflit avec (2) puisque d'un côté, il existe une application $g$ de P(E) dans k telle que l'image par g de W est un ultrafiltre non principal, alors que l'image par n'importe quel fonction choix de W est principal (et pourtant, il y a dans le "A" virtuel suffisamment d'éléments pour injecter k).

christophe c

Je termine cette première "intro" à ce sujet en racontant un outil lui aussi "incontournable", qui est connu sous le nom génériques "les phénomènes de Ramsey"

On note $X_p$ l'ensemble des parties de cardinal $p$ de $X$. Soit p un entier.
Soit $f$ allant de $\N_p$ dans 2. Il existe alors $i\in 2$ et $A$ une partie infinie de $\N$ telle que $\forall x\in A_p: f(x)=i$ (c'est le théorème de Ramsey).

Il est important à cause du truc suivant: quand tu as une formule $\forall a_1\in \N\exists a_2\in \N ....\forall a_p\in \N: R(a_1,...)$, tu peux colorier $\N_p$ de la manière suivante:

un ensemble $\{b_1,...,b_p\}$ avec $b_p>...>b_1$ est envoyé sur 0 ou 1 selon qu'il est vrai ou non que $\forall a_1\leq b_1\exists a_2\leq b_2 ....\forall a_p\leq b_p: R(a_1,...)$

Et bien toute partie infinie dont l'existence est affirmée par Ramsey est "dans le bon i", ie si la formule est vraie, le i est obligatoirement 1, idem avec faux.

Du coup, Ramey ramène "la vérité dans $\N$" à un oracle-Ramsey sur des ensembles de complexité NP inclus dans $\N_p$

Ca se généralise avec l'infini dans le sens suivant:

Un cardinal $A$ est "grand" quand pour toute application $f$ de l'ensemble des parties finies de $A$ dans $\N$ il existe une partie Y de de $A$ de même cardinal que $A$ et une application $g$ de $\N$ dans $\N$ telle que $\forall F$ partie finie de $Y$, $f(F)=g(card(F))$

C'est plus élégant que l'énoncé Ramseyien avec les entiers.

Exercice: soit $k$ un cardinal et $W$ une normale mesure sur $k$/ Prouver que $k$ est grand.

christophe c

Je complète légèrement.

L'inexistence d'un plongement élémentaire de V dans V entraine en particulier que s'il existe un ultrafiltre sigma additif non principal, alors $V\neq L$, puisqu'un tel ultrafiltre donne un plongement naturel de $V$ dans $M$ et que si $V=L$ alors $V=L=M$

Le ramseyisme montre plus: il montre qu'il existe dans ce cas un réel $x$ tel que $x\notin L$, et même il montre que $L\cap \R$ est dénombrables. Comment on peut procéder?

Je te résume juste, mais c'est le début d'une série d'astuces qui ont beaucoup motivé les gens entre 1980 et 2000. Ca se connecte à la théorie des jeux de la manière suivante:

soit $A$ une partie de $2^\omega$. On dit qu'elle est analytique si elle est l'image par une fonction continue de $\omega^\omega$ dans $2^\omega$ muni de la topologie produit des discrtes. Il se trouve qu'il y a beaucoup de parties analytiques (mais faut travailler un peu), en particulier que tous les boréliens sont analytiques et bien d'autres.

Lorsqu'on "joue", ie chacun joue un digit dans 2 alternativement jusqu'à construire une suite de 0 et de 1 et que par exemple le joueur1 essaie de faire que la suite soit dans un certain analytique $A$ (et donc le J2 essaie de l'en empécher), à priori, aucun théorème de ZFC ne permet de prouver en toute généralité que l'un des deux a une stratégie infaillible.

Grace aux normales mesures (ou même aux Ramsey cardinaux), on a un atout supplémentaire.

Compliquons la tache (légèrement) du joueur2: dans le jeu initial, il doit faire que la suite de 0 et de 1, u ne soit pas l'image d'un certain élément $v\in \omega^\omega$ par une fonction continue $f$, donnée. Ca se traduit par l'existence d'un arbre donné au départ qui sera bien fondé, si $u\notin Im(f)$ (l'arbre en question résume la problématique, en autorisant les suites de couple $(i,n)\in 2\times \omega$ telles que "on n'est pas encore sûr que la future suite jouée u commençant ainsi (le segment obtenu en ne regardant que les digits \in 2) ne sera pas l'image d'un élément $v$ commençant ainsi (le segment des digits $\in \omega$))

Dans le nouveau jeu, le J2 doit en plus de jouer ses 0 et ses 1, associer à chaque suite finie d'entiers un ordinal de sorte que ça garantisse qu'à la fin, s'il avait perdu, ça donnerait une suite descendante d'ordinaux.

Evidemment, connaissant les ordinaux joués, le joueur1 peut en profiter, et ça désavantage J2, dans le deuxième jeu, par rapport au premier jeu.

MAIS: si on dispose d'un cardinal Ramsey k (que j'ai appelé "grand" ci-dessus), en fait, ça ne change rien. Le nouveau jeu est déterminé car fermé (ie on sait au bout d'un temps fini que J2 a perdu (il échoue à jouer un coup de plus compatible avec les exigences) si c'est le cas). Si J1 a une stratégie infaillible S alors elle consiste en divers applications de divers $k^n$ dans 2 et on utilise la Ramseyite de $k$ pour prouver que finalement, "ça ne change rien", ie il existe un ensemble $A$ d'ordinaux appartenant à $k$ tel qu'on peut jouer n'importe lesquels, ça ne change pas la manière dont S répond. Et finalement, ça induit une stratégie pour le joueur1 dans le jeu intial.

Où est le rapport avec L?

Et bien, en fait le jeu est très simple: le joueur2 est chargé de coder une stratégie qu'il prétend être celle suivie par son adversaire, et en plus de coder cette stratégie, il doit coder un modele dénombrable bien fondé de "V=L" qui la contient.

C'est un jeu analytique, donc, via un k qui est Ramsey, déterminé. La stratégie qu'on récupère n'est alors pas un réel constructible (sinon, J2, contre elle n'aurait qu'à la coder ainsi que coder le premier $L_a$ qui la contient, pour la battre)

Des idées (plus compliquées) mais similaires ont conduit les ensemblistes à prouver que les grands cardinaux influaient sur la théorie des petits objets (IR, IN) de cette manière. Le théorème central prouvé vers 1980 est que $L(\R)|=AD$ des qu'il y a par exemple un cardinal supercompact.

christophe c

Je me force un peu à alimenter en restant dans la continuité des posts ci-dessus, mais en arrêtant un instant de parler de grands cardinaux pour rappeler un outil de base hyperarchi adoré par les ensemblistes quand ils ont étudié l'influence des grands cardinaux sur IR.

Faut avouer que ça donne des histoires surprenantes.

J'en ai deja parlé dans le fil, mais je recommence, en espérant améliorer et aller plus à l'essentiel.

Soit k un ordinal limite (sans predécesseur). Une partie A de k est dite un "club" (joli nom) quand:

1) toutes suite croissante d'éléments de A a sa borne sup (si celle-ci est dans k) dans A.
2) pour tout élément a de k il existe un élément b de A qui est plus grand que a.

"club" est l'abréviation de "clos non borné". La notion de "clos" renvoie à de la topologie, car (1) est une demande que A "soit fermé".

Jusque là, rien de bien folichon.... On cause de fermés non bornés, bin voilà ça a pas l'air de grand chose.

En fait, supposons maintenant que k ne soit pas de cofinalité dénombrable, c'est à dire qu'il n'existe pas de suites d'élément de k dont la borne sup est k. (Plus loin on pourra même supposer que k n'est pas de cofinalité un certain t donné, mais je préciserai)

voici des théorèmes "banals" mais amusants, quand ils vont être mis en "conflit" avec un autre truc qui viendra ensuite:

T1) Toute intersection de clubs $C_n$, quand n varie dans IN est un club
T2) Supposons que k soit régulier, cadire que pour tout $t\in k$ et toute application $i\mapsto u_i, i\in t$ il existe $b\in k$ tel que $\forall i\in t: b>u_i$. Soit alors $j\mapsto C_j, j\in k$ une famille de clubs, indicée par les éléments de k. Alors: l'ensemble Z des $a\in k$ tel que $\forall i\in a: a\in C_i$ est lui-même un club.

Ce sont des "exercices" pas vraiment difficiles, je les laisse à qui ça peut amuser. Le plus rigolo, c'est de prouver la fin (le côté non borné) de (T2)

L'ensemble Z évoqué dans T2 s'appelle "l'intersection diagonale des $C_i$

En guise de conclusion, à partir de clubs, on peut faire beaucoup d'autres clubs, la prise de l'intersection diagonale étant particulièrement amusante.


Question: à quoi ça peut bien servir, et bien je le raconte au post suivant

christophe c

En fait, il y a deux approches possibles: à coups "d'axiomes" ou à la force du poignée.

Mais le poignée casse très vite hélas.

Par contre, il y a un plan de bataille simple pour par exemple, embêter des étudiants de M2 qui aurait ce genre de sujet à grignoter.

Je dis tout de suite "l'axiome" magique (et je le "démontre" avec un autre axiome lol) qui a fait bcp causer les ensemblistes:

Soit k un ordinal régulier. Pour toute partie A de k, ou bien il existe un club disjoint de A, ou bien il existe un club inclus dans A.

axiome purement gratuit, faux en toute généralité, en tout cas en présence de l'axiome du choix, mais comment dire, "en pratique" vrai.

Ca ressemble un peu à "tous les ensembles de réels que les gens constuisent sans l'axiome du choix sont Lebesgues mesurables"

Je disais qu'on peut embêter des étudiants, voici comment: on leur donne un ensemble A d'ordinaux éléments de k qu'on leur définit en alternant 3 ou 4 quantificateurs de manière bien pénible et on leur demande de prouver l'existence d'un club C tel que $C\subseteq A$ ou $C\cap A=\emptyset$.
Si ensuite ils s'attaquent à la résolution de l'exo à la force du poignée, ça leur promet bien des galères.

Pourquoi c'est un "bon axiome"?

Réponse: soit $A$ une partie quelconque de $k$. On joue au jeu suivant:

Alice joue un ordinal $a_1$ puis Bob joue un ordinal $a_2>a_1$, puis Alice joue un ordinal $a_3>a_2$ etc.

Ils construisent ainsi une suite $a$ d'éléments de k. On dit que Alice a gagné si $sup(a)\in A$

Théorème***: si Alice a une stratégie infaillible pour gagner, alors il existe un club inclus dans A. Si Bob a une stratégie infaillible pour gagner, alors il existe un club disjoint de A

(Idem c'est un exercice plutôt facile)

Maintenant, "l'axiome" ci-dessus vient juste du fait qu'en maths, on n'est jamais parvenu à construire des jeux "non déterminés" qui ne sentent pas le souffre (ie en utilisant l'axiome du choix, ou en faisant un petit tour de passe passe autre, ou en manipulant des parties de IR comme des digits)

En particulier l'axiome AD (deja souvent évoqué) entraine l'axiome pour $k:=\omega _1$, et même pour $k=\omega_2$ je crois (et même pour les cardinaux suivants jusqu'à assez loin me semble-t-il, bref).

Autre remarque: quand on a "construit" l'ensemble A (par exemple qu'on donnerait à des étudiants pour les embêter), le fait de prouver qu'il existe un club inclus dans ou disjoint de A se ramène, vu le Th*** à une activité largement plus exaltante: étudier le jeu associé et essayer de fabriquer une stratégie gagnante (pour Alice ou pour Bob)

Et là, en général, il y a des armes connues, comme la détermination borélienne par exemple, enfin les techniques qui y ont été investies.

Mais la petite histoire n'est pas finie

FrançoisD

"poignet" camarade syndiqué des voitures à pieds (non parce que quand je te vois faire de la logique, les bras m'en tombent lol)

F.D.

christophe c

Merci François, et le pire est que j'ai hésité entre les 2 orthographes, mais je n'ai jamais pensé que l'existence du mot "poignée" venait de "poignée de porte"

Bruno

Que penses-tu d'une poignée de riz ? Et de la poignée de mains ?

Bruno 8-)

FELIX1

Poignée et poignet ne viendraient-ils pas de poing ?

Bruno

Je n'ai aucune connaissance en étymologie Félix -D.

Bruno

gb

Félix a écrit:

Poignée et poignet ne viendraient-ils pas de poing ?

Bien sûr que si ! ainsi que poigne.

FELIX1

Bonsoir Bruno et GB,

On peut ajouter pugnace, pugilat, et assez étonnamment pygmée.
Une forte envie me tenaille d'y inclure callipyge, mais c'est quelque peu aventureux.
Bonne soirée, amitiés.
Félix

Bruno

Félix : -D

Bruno

Eric Chopin

Mais le pois niais point n'y est..

Bon ok c'est nul mais j'assume... ;-)

eric

christophe c

pygmée???????????????? Ya un algorithme ou faut le savoir?

FELIX1

Je suis heureux de saluer Eric.

Pour Christophe, le y était en réalité un u.
Le poing : pugme
dérivé : pugmaios, haut d'une coudée
Un peuple légendaire chez Homère : pugmaios, le pygmée, qui est un nain.
On dirait de nos jours "haut comme trois pommes".
Source consultée : Dictionnaire historique de la langue française, le Robert.
En ayant toujours à l'esprit que l'étymologie n'est pas une science exacte.
Amicalement.

christophe c

Merci Felix et bonjour à tous les autres. Ah oui, c'est pas une science exacte!! (décidément je ne pense à rien en ce moment)

Je continue la petite histoire des clubs. Comme je l'ai dit, l'axiome du choix permet "facilement" de fabriquer un ensemble A ni disjoint d'un club ni n'en contenant un (et par la même occasion donnant lieu à un jeu non déterminé).

Pour k:=$\omega_1$ voici un argument plutôt court:

Chaque $a\in k$ qui est limite (sans prédecesseur) est dénombrable et en particulier, il existe une suite d'ordinaux $f(a)$ tous dans $a$, strictement croissante et dont la borne sup est $a$.

On va supposer que tous les ensembles qui suivent contiennent ou sont disjoints d'un club et arriver à une contradiction.

D'après les théorèmes signalés avant, pour tout entier $n$, il existe $u_n$ et un club $C_n$ tel que pour tout x dans $C_n$: $x>u_n$ et $f(x)(n)=u_n$.

Soit $D$ l'intersection des $C_n$ qui est un club et $x\in D$. Alors $\forall n\in \N: f(x)(n)=u_n$ et donc $f(x)=u$

Or $x=sup(f(x))$ donc $x=sup(u)$. C'est en contradiction avec le fait qu'un club ne peut pas être un singleton.

Cependant j'ai utilisé $f$ qui "choisit" une suite cofinale $f(x)$ dans $x$.

La suite de l'histoire raconte comment on peut se passer en partie de "ce choix" et obtenir des choses paradoxales.

christophe c

Précision du post précédent: je suis passé un peu vite sur l'existence de $u_n$.
Soit $g$ une fonction qui à chaque ordinal $x$ non nul et limite de $k$ associe $g(x)$ tel que $x>g(x)$.
Supposons que pour tout $a$, il n'existe pas de club $C$ tel que pour tout $x\in C$: $x>a$ et $g(x)=a$.
Alors (sous l'hypothèse que tout ensemble contient ou est disjoint d'un club), pour tout $a$, il existe un club $C_a$ tel que pour tout $x\in C_a$: $x>a$ et $g(x)\neq a$.
Soit $D$ l'ensemble des $y$ tels que $\forall x\in y: y\in C_x$. On a vu précemment que c'est un club, appelé intersection diagonale des $C_a$, donc non vide, contenant des ordinaux limite non nuls, soit $z\in D$ un tel ordinal. Alors $\forall x\in z: g(z)\neq x$, ce qui est une contradiction.

Il s'ensuit qu'il existe a et un club C tel que $\forall x\in C: x>a$ et $g(x)=a$. Il reste alors à appliquer ça dans le post ci-dessus à $g:=x\mapsto f(x)(n)$ pour obtenir $u_n$

christophe c

Voici maintenant une façon de froler la contradiction. On fait une construction par récurrence ordinale amusante. Le point clé, c'est qu'on ne fait jamais appel à l'axiome du choix en apparence.

On suppose que k est un ordinal et qu'on a une famille $t_a, a\in K$ telle que $\forall a\in k: t_â$ est une injection de $a$ dans IN.

si $k$ est le successeur de $b$, on a une injection de $k$ dans IN qui est canonique: on envoie $b$ sur 0 et les éléments $x$ de $b$ sur $1+t_b(x)$

C'est quand $k$ est un ordinal limite que c'est intéressant. Tous les arguments précédents donnent chaque fois que "quelque chose cloche" une injection de $k$ dans IN. La seule issue possible est donc qu'ou bien on a une injection canonique de $k$ dans IN, ou bien un ensemble "canonique" A qui n'est ni disjoint d'un club de k, ni ne contient un club de k.

En apparence on ne fait aucun choix et on a donc l'impression que l'un des ensemble A issu de *** "devrait" contenir ou être disjoints d'un club, et que si ce n'est pas le cas, "l'univers" n'est pas "plein".

Autrement dit, c'est un premier argument qui montre que les axiomes de ZF founissent une manière de parler qui elle-même fournit une "porte" pour sortir de l'univers supposé vérifier les axiomes de ZF. Avec le forcing, je raconterai au post suivant une manière encore plus nette de le faire, qui est vraiment bluffante.

Mais, d'abord "l'injection canonique" de k dans IN:

soit $a\in k$ et $h(a)$ un ENTIER n tel qu'il existe un club $C$ de $k$ avec $\forall x\in C: x>a$ et $t_x(a)=n$. ***

S'il existe plusieurs tels entiers, on prend le plus petit, mais s'il en existe plusieurs alors il existe une injection canonique de k dans IN: en effet, soient n,p deux entiers différents et deux clubs C,D associés à chacun comme ci-dessus.

Soient $b_1\in C$; $b2\in D$ avec $b_2>b_1$; $b_3\in C$ avec $b_3>b_2$^, etc, etc (on ne fait pas de choix, on prend chaque fois "le plus petit qui...". Comme C,D sont des club, la borne sup s de la suite b est à la fois dans C et dans D. Donc on devrait avoir $n=t_s(a)=p$ ce qui est une contradiction. Il s'ensuit que $sup(b)=k$ et ca fournit l'injection suivante de k dans IN^2: à chaque $x\in k$ on associe le couple (q,e) d'entiers tels que $q$ est le premier entier vérifiant $b_q>x$ et $e:=t_{b_q}(x)$

Si donc "tout continue", pour chaque $a$, il existe un UNIQUE entier tel que ***.

(remarque, supposons qu'il n'en existe pas du tout: alors soit $C_n$ un club tel que $\forall x\in C_n: x>a$ et $t_x(a)\neq n$. Soit alors la suite croissante v obtenue de la manière suivante: on prend un élément dans $C_1$, puis un élément plus grand dans $C_2$ puis un élément dans $C_1$ puis dans $C_2$ puis dans $C_3$, etc, etc ce qui donne schématiquement: $C_1,C_1C_2,C_1C_2,C_3, ...$. La borne sup de $v$ devrait être dans tous les $C_n$ et cette borne sup ne peut être que k et on conclut comme ci-dessus)

Supposons que l'application $h$ ne soit pas injective. (Si elle l'est c'est fini, c'est notre injection de k dans IN)

Soient $n$ un entier et $a,b$ différents tels que $h(a)=h(b)=n$.

Soit $C$ un club tel que $\forall x\in C: x>a$ et $t_x(a)=n$ et $D$ un club tel que $\forall x\in x>b$ et $t_x(b)=n$

Comme ci-dessus la suite strictement croissante $u$ canonique telle que $\forall n\in \N: u_{2n}\in C$ et $\forall n\in \N: u_{2n+1}\in D$ a une borne sup qui ne peut être que k et on termine comme ci-dessus. (Rapelle $t_x$ est injective, et la borne sup de $u$ devrait être dans $C\cap D$, c'est à dire en particulier être un ordinal $s$ tel que $t_s(a)=t_s(b)=n$

On obtient donc ainsi chaque fois une "injection canonique" qui va de k dans IN (sous réserve de l'existence suffisante de clubs "canoniques"). Ca donne une construction par récurrence qui rend dénombrable tous les ordinaux et plutôt ça montre que le premier ordinal qui provoque un échec a un ensemble "canonique" (on n'a pas utilisé de choix) qui ne contient, ni n'est disjoint d'aucun club "canonique". Ceci entre en conflit avec le fait que les constructions effectives ne devraient avoir cette propriété intuitivement.

christophe c

Avant de continuer avec la parti politique "il y a beaucoup de clubs, tirons-en les conséquences", voici un truc qui va vraiment dans le sens inverse, mais qui est intéressant car il se relie à un autre phénomène:

On reste avec $k:=\omega_1$. A chaque ordinal limite a non vide, on associe une suite strictement croissante d'éléments de a dont la borne sup est $a$ (axiome du choix).

On a donc $a=sup$ de l'ensemble des $u_n(a)$ quand $n$ parcourt IN.

Supposons qu'il y ait un club $C_n$ et un ordinal $b_n$ tel que pour tout entier $n$, et tout $x\in C_n: u_n(x)\leq b_n$.

Soit $s>$ à tous les $b_n$ et $z>s$ un ordinal limite qui se trouve dans tous les $C_n$. Alors $\forall n\in \N: u_n(z)\leq b_n$ et donc $sup$ des $u_n(z)\leq s$ qui est strictement inférieur à $z$ ce qui est une contradiction.

Il existe donc un entier $n$ (je vais l'appeler "8") tel que pour tout ordinal $b$, l'ensemble des $x$ tels que $u_n(x)\leq b$ ne contient aucun club.

Un ensemble dont le complémentaire ne contient aucun club s'appelle "stationnaire".

La reformulation de l'axiome philosophique faux et expéditif, mais "désirable" quelques posts plus haut dit donc "tout stationnaire contient un club"

Regardons maintenant ce que $u_8$ permet de faire.

Soit c un ordinal. On vient de voir que l'ensemble S des ordinaux $x>c$ tels que $u_8(x)>c$ est stationnaire. Supposons, cependant, que pour tout ordinal $d>c$ l'ensemble des $x>d$ tels que $u_8(x)\neq d$ contienne un club $C_d$. Soit $e>c$ un ordinal qui se trouve dans l'intersection diagonale des $C_i,i>d$ ainsi que dans $S$. On a une contradiction. Or on a vu que l'intersection diagonale de clubs est un club. Il s'ensuit qu'il existe un $d>c$ tel que l'ensemble des $x>d$ tels que $u_8(x)=d$ est stationnaire.

On obtient donc que l'ensemble $T$ des ordinaux $b$ tels que l'image réciproque par $u_8$ du singleton $\{b\}$ est stationnaire est non borné dans $\omega_1$, et est donc de cardinal $\omega_1$.

On vient de partionner $lim(\omega_1)$ (les ordinaux limite) en $\omega_1$ stationnaires 2 à 2 disjoints. Notons $i\mapsto S_i, i\in \omega_1$ cette partition.

Soit $u$ une suite strictement croissante d'éléments de $\omega_1$. On lui associe G(u) l'unique indice $i$ tel que $sup(u)\in S_i$

Soit maintenant une partie $A$ quelconque de $\omega_1$ qui soit de cardinal $\omega_1$. L'ensemble des bornes sup de suites strictement croissantes d'éléments de A est un club

Il intersecte donc TOUS les $S_i$.

Il s'ensuit que: pour toute partie A de $\omega_1$ de cardinal $\omega_1$ et pour tout ordinal $a\in \omega_1$, il existe une suite $u$ strictement croissante d'éléments de A telle que $G(u)=a$.

Ceci est à relier avec un argument célèbre qui permet de prouver qu'il n'existe pas de plongement élémentaire de l'univers dans lui-même, qui utilise aussi l'existence de fonctions comme G.

christophe c

Au dessus, j'ai raconté comment on peut creer avec l'axiome du choix des stationnaires qui ne sont pas des clubs.

Mais sans construction "magique" (Axiome du choix), tout porte à croire qu'un stationnaire DOIT contenir un club dans un univers bien fait.

La suite est vraiment rigolote parce qu'elle emmene à contrario vers une AUTRE situation où au moins un stationnaire ne contient pas de club, mais cette fois-ci, AUCUN des stationnaire ne contient la moindre once d'axiome du choix ou construction compliquée. Ca tend donc à faire penser que ZF donne une image erronée du monde. Ou plutôt que ZF fournit les clés pour sortir de l'univers.

christophe c

L'argument st assez classique, mais je le remixe pour mettre en évidence LE phénomène. Il faut savoir que ce phénomène NE PEUT PAS être étudié sérieusement sous peine de filer la migraine aux pros, car il ne permet pas d'en faire éclore de manière standard quelque chose.

L'avantage est qu'il se raconte assez vite, et utilise le forcing d'une manière inhabituelle car dans le sens non d'une indécidabilité, mais d'une preuve. Preuve d'ailleurs que je ne saurais faire courtement sans forcing.

christophe c

Ce coup-ci, au lieu de prendre $k=\omega_1$, je prends $k:=\omega_2$.

Je rappelle la définition de $a$, ordinal $\mapsto L_a$:

$L_0:=\emptyset$
Quand $a$ est de la forme $b+1$, $L_a:=P_{def}(L_b)$
Quand $a$ est un ordinal limite, $L_a:=$ la réunion des $L_b$ quand $b\in a$

C'est une définition par récurrence ordinale.

$P_{def}(E)$ est l'ensemble des parties de $E$ qui peuvent être définies avec des $\forall$, le signe "=>", des paramètres, et le signe $\in$

La réunion des $L_a$ quand $a$ parcourt tous les ordinaux est une classe qui vérifie les axiome de ZF + l'axiome du choix + l'hypothèse généralisée du continu + bien d'autres choses.

L'axiome nommé "V=L" dit: $\forall x\exists a, $ ordinal tel que $x\in L_a$

Tout modele bien fondé de "ZF+V=L" est isomorphe à un $(L_a,\in/L_a)$ où $a$ est un ordinal

christophe c

Le sigle "L" tout court, désigne la réunion des $L_a$ quand $a$ parcourt les ordinaux

Notons $e$ le premier ordinal que $L$ voit comme non dénombrable, c'est à dire le plus petit ordinal tel qu'il n'existe pas de surjection de IN sur lui qui est dans $L$.

Dans l'univers V, on ne sait pas si oui ou non, $e=\omega_1$, et peu importe pour ce qui va suivre.


Dans le langage de la théorie suivante T, on a ajouté un symbole de constante $c_i$ pour chaque $i\in e$ et un symbole de constante $d$.
Soit T la théorie suivante: elle demande ZF + V=L + $c_i\neq c_j$ pour chaque couple $(i,j) $ de $e^2$ tel que $i\neq j$ et $c_i<d$ + $c_i$ est un ordinal + $d$ est un ordinal dénombrable, et ce pour chaque $c_i$

christophe c

Le point crucial est le suivant: non seulement T n'a pas de modele bien fondé, mais T n'a pas de modèle bien fondé même vue dans une extension générique quelle qu'elle soit!!!!

Je rappelle ce qu'est "un modele bien fondé" dans notre contexte: c'est un uplet (M,R,...) où il n'existe pas de suite $u$ d'éléments de M telle que $\forall n\in \N: u(n+1)Ru(n)$

Il est équivalent de dire que c'est un couple (f,(M,R,...)) où $f$ envoie chaque élément de M sur un ordinal et tel que $\forall (x,y)\in M^2: xRy$=>$f(x)\in f(y)$

Précision concernant la partie rouge: étant donné deux univers $V\subseteq W$ ayant les mêmes ordinaux, la même relation d'appartenance et bien fondés, le "L" calculé dans $V$ est EGAL au "L" calculé dans W. En particulier si W est une extension générique de V, et si la théorie T a un modele bien fondé dans W, alors il sera (isomorphe à ) un $L_a$ qui sera dans V et qui sera un modele de T, vu dans V

christophe c

La théorie T possède $\omega_1$ axiomes qu'on peut canoniquement ranger et numéroter avec des ordinaux de $\omega_1$.

On met aussi dans T des témoins de Skolem, c'est à dire pour chaque $R(x)$ une contante $z$ et l'axiome $R(z)$=>$\forall xR(x)$

Voici maintenant un jeu de type "prouveur-sceptique":

Le prouveur propose un énoncé $E_1$ du langage de T et le sceptique doit dire s'il est vrai ou faux: "V" ou "F". Puis on recommence ainsi $E_2$ suivi de "V" ou "F" joué par le sceptique. De plus si l'énoncé est de la forme $a\in b$ et que le scetique répond "vrai", alors il doit EN PLUS jouer 2 rationnels $\in \Q$, l'un r attribué à $a$ et l'autre s à $b$ et les choisir tels que $s>r$

Tous les 10 coups (j'aurais pu choisir un autre nombre), le sceptique doit prendre le premier rationnel apparaissant avant dans la partie et non encore "affecté" d'un ordinal et lui affecter un ordinal DE $k$, c'est à dire $\omega_2$. Il doit s'y prendre d'une manière telle qu'à que l'application partielle construite progressivement soit strictement croissante. S'il ne respecte pas ces règles, il perd.

christophe c

Le sceptique a aussi le devoir de répondre "vrai" à chaque fois qu'un axiome de T lui est proposé.

Maintenant, quelques remarques:

1) supposons que V=L. Alors tout sous-ensemble dénombrable de $T$ a un modele bien fondé.
2) Dans le jeu précédent, si le prouveur décide à l'avance de jouer uniquement des énoncés dans un sous-ensemble dénombrable D de T, il n'est pas assuré de gagner: en effet, le sceptique n'a qu'à répondre correctement en suivant "la vérité" d'un modèle bien fondé de T (un tout bête $L_a$ avec $a$ suffisamment grand) et à étiqueté les rationnels qu'il choisira par des ordinaux de $\omega_2$ (il pourrait même les choisir tous $\in$ un ordinal dénombrable donné

christophe c

Maintenant une remarque allant dans l'autre sens, qui prouve que le sceptique ne peut pas avoir de stratégie gagnante:

on se place dans une extension générique très simple où on s'est juste contenté de mettre une surjection de $\N$ sur $T$. Dans cette extension, le prouveur va pouvoir jouer tous les énoncés du langage de la théorie T, les uns après les autres en les soumettant au sceptique. A la fin, si à aucun moment le sceptique ne perd, il aura construit un modèle bien fondé de ZF+V=L qui voit sa constante d comme dénombrable alors qu'il y a $e$ ordinaux AU MOINS qui sont sous $d$.

Dans cette extension générique, le modèle construit est OBLIGATOIREMENT un $L_a$ où a est un ordinal, qui "pense que $e$ est dénombrable".

Mais ce $L_a$ est un élément de l'univers de départ, or il n'existe ni dans l'univers de départ, ni dans l'extension générique de tel $L_a$.

christophe c

Le jeu quant à lui est un jeu fermé, c'est à dire que si le sceptique perd, ça ne se déclenche pas à la fin de la partie, mais AVANT (au bout d'un nombre fini de coups).

Par conséquent, ce jeu est déterminé

Et donc, c'est le prouveur qui a une stratégie gagnante, qui de plus sera canonique, vue la définition du jeu.

christophe c

On est dans une situation en apparence très simple: un jeu dont les règles sont claires et quasiment "récursives" (je mets des guillemets car il y a des constantes en nombre non dénombrable). Et à ce jeu "on sait" que le prouveur a une stratégie gagnante S.

La nature du jeu est la suivante, le prouveur propose des énoncés qu'il choisit dans T EN FONCTION DES coups précédents du sceptique qui à l'exception de dire "vrai, faux", joue aussi parfois des rationnels, et des éléments de $\omega_2$.

Remarque importante: si on n'obligeait pas le sceptique à jouer des éléments de $\omega_2$ alors le prouveur jouerait ses coups en fonction des coups précédents du sceptique qui sont des suites finies d'éléments d'un ensemble très simple: vrai;faux; des rationnels

Par conséquent, sans l'obligation deja citée, une stratégie du prouveur ne se servirait pour toute partie jouée contre lui que d'un ensemble dénombrable d'éléments de T. Précisément il existerait un ensemble dénombrable D tel que dans toute partie jouée contre le prouveur, les énoncés choisis par lui sont dans D.

Or toute sous-théorie dénombrable de T a un modele bien fondée si V=L et donc, sans la contrainte, c'est le sceptique qui aurait une stratégie gagnante!

christophe c

Digression: sans le forcing, je n'avais aucun moyen rapide pour vous convaincre que le prouveur a une stratégie gagnante. Ca doit être une vraie galère de le prouver à la main.

Maintenant, on va "abstraire" le profil du jeu et "oublier" son fond pour ne regarder que sa structure, sans perte de généralité.

On peut le voir comme suit:

Le prouveur joue des éléments de $\omega_1$ et le sceptique répond par des couples de la forme $(r,a)$ où $r\in \Q$ et $a\in \omega_2$.

Le début d'une partie est donc de la forme $u_1; (r_1,a_1); u_2; (r_2,a_2),...$ où $u_1\in \omega_1$ et $r_i\in \Q$ et $a_i\in \omega_2$

Et si le prouveur suit la stratégie canonique S gagnante signalée avant, par exemple, et bien $u_7=S((r_1,a_1),(r_2,a_2)...(r_6,a_6))$ (ceci étant valable bien sûr pour les autres entiers que 7 aussi.

Par ailleurs l'ensemble des couples $(r_i,a_i)$ doivent former une graphe de fonction partielle strictement croissante de $\Q$ dans $\omega_2$