le forcing expliqué aux matheux ordinaires

Médiat

Bonjour HelloWorld,

Je ne possède pas ce livre et ne peut donc en dire grand-chose, mais je possède la version précédente (en PUF) qui est superbe (je serais tenté de dire "comme tout ce qu'écrit Krivine", mais je ne suis peut-être pas objectif, il a été mon prof en Maîtrise en 73 )

FrançoisD

Salut,

c'est très loin d'être un texte "nouveau", j'en ai une version de 1991 chez Cassini, ah! comme tous les arguments sont beaux s'ils font vendre.

Amicalement,

F.D.

christophe c

olala, j'ai promis de reprendre ce fil il y a ... 4mois

Bon, je reprends et fais un petit bilan:

Si vous vous accrochez (juste un peu), vous constatez une relation assez profonde entre forcing, notions de jeux, notions de preuves, notions d'axiomes.

Ultrarésumé: les logiciens ont découvert que les preuves de maths sont des stratégiques gagnantes à des jeux où les inférences logiques fixent les règles du jeu et les axiomes fixent les moment où on peut dire j'ai gagné. M

Mais au moment de l'invention du forcing, Cohen s'en moquait surement un peu.

Un dialogue entre un prouveur et un sceptique qui acceptent tous 2 les axiomes de ZFC peut donc ressembler de très près à une partie à ce jeu.

La théorie du forcing "sépare" les variables un peu comme parfois les analystes le font dans les equadif.

Il y a une partie du jeu qui trouve sa place dans... l'univers où vivent les ensembles, et une autre qui reste sur la table de café où parlent les mathématiciens d'accord sur ZF.

LA PARTIE qui reste sur la table, avec un grand P, c'est le caractère fini, ou dénombrable des mots et des objets qu'ils vont nommer.

La théorie de Cohen consiste à faire la remarque suivante: quand un gars sait comment il va résister au prouveur, ça se traduit (tellement les axiomes de ZFC sont forts) en une algèbre de Boole complète qui existe à l'intérieur de l'univers dont les 2 parlent.

Dans un premier temps, donc, Cohen a "senti" (j'invente, je ne fais pas de l'histoire) comment résister à quelqu'un qui voudrait lui prouver l'hypothèse du continu.

Et dans un deuxième temps, son "intuition" il a pu la traduire en une algèbre de Boole complète et la présenter à l'académie de maths pour qu'elle constate qu'il venait de fabriquer un modèle de nonHC.

Pour mieux comprendre, il suffit donc de se familiariser avec ces notions de jeux, d'où mes quelques posts.

Le meilleur exemple, c'est d'imaginer un jeu où le fait, pour le sceptique, de pouvoir énumérer par une suite tous les ensembles de l'univers, pourtant non dénombrable! lui permet de gagner à un jeu où le gain se traduit par un moment fini du jeu où il dit "j'ai gagné" lui permet de gagner s'il connait la stratégie de son adversaire.

Et bien, grace à la théorie du forcing, l'hypothèse ci-dessus garantit qu'en fait le sceptique a une stratégie gagnante, dans l'univers initial (où pourtant la suite "magique" qu'il a imaginée n'existe pas.

Etudiez (sans lire la suite) cette simple idée, et vous aurez fait un pas de géant dans la compréhension de toutes ces idées.

L'exemple que je vais donner est très génaral: c'est le théorème de complétude de la logique INFINIE. (Je crois que je l'ai déjà fait, ci-avant, mais je vais le refaire).

christophe c

Pour prouver des choses les mathématiciens admettent des axiomes et font des déductions.

Toutes les déductions peuvent se ramener à une seule.

Par exemple, vous savez comment prouver A et aussi comment prouver B, et vous voulez dire "donc A et B".

Soit vous inventez (bêtement) une règle qui autorise à le dire, et ce faisant, vous changez les règles du jeu et non les axiomes ce qui a des inconvénients car on ne sait s'il faudra éternellement change règles règles du jeu, soit vous faites comme suit:

vous dites, "A et B" car je peux te prouver B et aussi B--->(A et

le sceptique a le choix de vous répondre "prouve moi B" ou "prouve moi B--->(A et "

S'il choisit "prouve moi "prouve moi B--->(A et ", vous dites

vous dites je peux te le prouver car je peux te prouver A et aussi A--->(B--->(A et )

S'il choisit la deuxième option, vous déclarez que c'est un axiome.

En fait toutes les "règles" d'un jeu compliqué de prouveur-sceptique peuvent, s'il n'est pas trop corrompu (et "faux") se ramener à une seule règle (appelée le modus ponens) et des axiomes.

Cette traduction des règles en axiomes permet de voir toutes les mathématiques selon un standard uniforme, qui peut ensuite être étudié avec clarté (pas besoin de se demander si on oublie une règle ou un cas, puisqu'il n'y a qu'une seule règle.

christophe c

{\bf Preuve du théorème de complétude "infinitiste":}

A cause des conjonctions infinies, on a besoin d'une règle (qui n'a rien d'étonnante ou de subtile), qui permet au prouveur, quand il prétend qu'une certaine conjonction de $A_i$ pour $i\in I$ est prouvable, de demander au sceptique de choisir parmi les $i\inI$ avec laquelle on continue la partie.

Mais avant, voyons le jeu en détails.

Soit $H$ qui sera appelé un ensemble d'hypothèses, et $P$ une phrase.

La partie commence avec une certaine $P$ comme phrase à prouver (à chaque étape du jeu, j'appellerai la "PC" la phrase courante à prouver)

Quand $P$ n'est pas une conjonction, le prouveur n'a qu'une seule option possible: le modus ponens. Il propose au sceptique de remplacer la PC (qui à ce moment est $P$) par au choix du sceptique: $A\to P$ ou $A$

Le sceptique, fait son choix, et la partie continue, avec $A$ si le sceptique a choisi $A$ ou $A\to P$ si le sceptique a choisi $A\to P$

Si la phrase $P$ est la conjonction des $A_i$ pour $i\in I$, le prouveur a une autre option possible: demander au sceptique de choisir $i\in I$. La partie continue alors avec $A_i$ comme nouvelle PC.

Si, à un moment donné, la $PC$ se trouve dans $H$ alors le prouveur a le droit de dire "j'ai gagné".

Supposons que $P$ soit une tautologie (éventuellement infinitiste), c'est à dire qu'il n'y a aucun moyen d'attribuer des valeurs "vraie"/"faux" à chaque phrase (de l'ensemble des phrases) de manière que toutes les phrases de $H$ ait reçu la valeur "vraie" et la phrase $P$ ait reçu la valeur "faux", et que certaines règles élémentaires soient respectées en ce qui concerne les conjonctions et le signe $\to $.

Je vais juste montrer que le sceptique n'a pas de stratégie gagnante (et en fait la procédure rendra explicite une manière de le battre à coup sûr)

On se donne une surjection $w$ de $\N$ sur toutes les phrases (et c'est là que le foricng apparait, car peut-être l'ensemble des phrases n'est-il pas dénombrable)

On commence par demander au sceptique de choisir entre $(P\to tout)\to tout$ et $P\to tout$

Aux étapes $n$ où on n'a pas déjà commencé à faire quelque chose de précis, qu'on finit, voilà comment on procède:

La phrase courante du moment est $P$
On propose au sceptique le modus ponens entre $(A\to P)\to P$ et $A\to P$ où $A:=w(q)$ où $q$ est le premier entier tel que $w(q)$ n'a pas encore été proposé en modus ponens lors d'un coup précédent.

Si $A$ n'est pas une conjonction, on continue la partie, en recommençant à l'étape $n+1$ avec la même méthode.

Si $A$ est une conjonction de $B_i$ et que le sceptique a choisi $Q:=(A\to P)\to P$ alors on lui propose un modus ponens entre $D\to Q$ et $D$ où $D$ est la conjonction des $((B_i)\to P)\to P$; ensuite on lui demande de choisir un des $i\in I$ et on obtient une des $((B_i)\to P)\to P$ comme nouvelle PC. Puis on continue...

Si, à aucun moment de la partie on est en position de gagner, elle dure jusqu'à la fin et, à la fin, on attribué une "valeur" de vérité à toutes les phrases de la manière suivante: les phrases $A\to P$ qui apparaissent à un moment en hypothèse "attribuent" (en imagination) la valeur "faux" à la phrase $A$ et les autres sont déclarées vraies.

Ce "prémodèle" n'étant pas un modèle, il vous reste à montrer qu'à un moment de la partie, on n'aurait pu gagner en quelques coups.

christophe c

Par récurrence, la notion d'hypothèses d'une phrase est définie de la manière suivante:

Une conjonction n'a pas d'hypothèses, une phrase "atomique" non plus.

Les hypothèses de $A\to B$ sont les hypothèses de $B$ ainsi que $A$

christophe c

Pardon d'oublier d'alimenter régulièrement ce fil.

Une petite chose toute simple:

Finalement, dans tous les théorèmes de complétude qui ont éclos il y a une substantifique moelle importante, qu'on ertrouve SYSTEMATIQUEMENT.

C'est la détermination des jeux. par exemple, le théorème de Gale-Stewart.

Une preuve est un arbre, mais il est mieux de la voir comme une stratégie gagnante. Dès lors, l'"étrange" choix lié au tiers exclus dans les preuves ou dans le fait qu'on demande aux modèles de rendre chaque phrase "vraie" ou "fausse", n'est pas si caractéristique de la logique classique, contrairement à un préjugé.

La logique intuitionniste s'exprimant, elle aussi, comme un jeu, offre le même profil, et c'est la règle de "coupure", autorisée dans TOUTES les logiques, même les plus faibles qui donne cette dichotomie apparente:

j'arrive à gagner si tu me donnes A et j'arrive aussi à gagner si tu me demandes de prouver A (à la place de ce que je suis entrain de prouver), donc je te demande ou bien de m'offrir gratuitement A comme hypothèse, ou bien d'oublier ce que j'étais entrain de te prouver, mais de me demander de prouver A

Cette revendication est formellement, mathématiquement, pratiquement équivalente à:

Voyons voir, si A est vraie... je gagne et si A est faux... je gagne

Or demander pour chaque A au sceptique de choisir entre "donne-moi A" et "donne-moi nonA", et attendre "bêtement" jusqu'à la fin, c'est, sans se fatiguer, lui demander de construire un contre-modèle de ce qu'on est entrain de prouver.

Si on est entrain de prouver une tautologie, on sait qu'avant la fin il fera une "erreur" (par hypothèse, une tautologie n'a pas de contre-modèle) on attend en dormant presque cette erreur et quand elle est commise, on n'a plus qu'à gagner sans intelligence.

Le slogan "les preuves avec coupures ne peuvent être recherchées par ordinateur parce qu'elles nécessitent une inspiration" est un peu arnaquant.

En effet, au contraire, en LC, elle permettent de gagner en dormant, et dormir n'est pas exprimer extérieurement de l'inspiration.

Le forcing tombe à pique pour généraliser tout ça au calcul propositionnel infini. En effet, on a besoin de collapser l'ensemble des formules pour qu'il devienne dénombrable. J'ai presque envie de dire "et c'est tout ce qu'apporte le forcing" mais ce serait source de malentendus et trop théorique.

Mais voilà ça me donne la suite: je rentrerai dans les détails de ce que veut dire "collapser" au prochain post.

christophe c

Voyons l'indépendance de HC.

On commence la partie avec l'énoncé "hypothèse du continue". Le prouveur prétend la prouver. Comme dit avant (plutôt début de ce fil), on va se servir d'un ensemble de variables bien précis (ce qui ne changera rien, les varaibles n'étant que des lettres, mais le sceptique, pour résister, les verra autrement).

Il s'agit des "noms" suivant:

Un nom est un ensemble ne contenant que des couples (x,p) où x est lui-même un nom (l'axiome de fondation rend sensé cette "autoréférence") et p une "condition de forcing"

On choisit l'ensemble T des conditions de forcing comme étant des applications partielles, à domaine fini de I×N dans 0,1, avec I un gros ordinal. T est ordonné par prolongement.

I est choisi de manière à contenir tout plein de cardinaux infinis.

Je rappelle que le "forcing" préserve les axiomes de ZFC. D'ailleurs l'argument qu'on va donner va démontrer la consistance de non(HC), non pas avec seulement ZFC, mais avec toutes les théories qui ne contiennent que des axiomes qui préservés par la forcing.

La seule règle hors du modus ponens est celle qui propose au sceptique de choisir une lettre (un nom) quand la phrase courante à prouver est de la forme "pour tout x blabla", et qui la transforme en blabla, où les occurences libres de x ont été remplacées par le nom choisi par le sceptique.

Le sceptique garde dans son intimité, tout au long de la partie une condition de forcing q qu'il fait varier en la renforçant, à chaque étape et qui "force" chaque hypothèse de la phrase courante et la négation de sa conclusion

A chaque étape d'une partie où le prouveur doit prouver P et opte pour le modus ponens en demandant de choisir au sceptique entre A--->P et A, le sceptique va répondre de la manière suivante: il regarde sa q courante intime (qui force nonP)et:

L'ensemble des conditions r qui force A ou qui force A--->P étant dense, s'il y en une plus petite que q qui force A, il demande au prouveur de prouver A--->P et prend cette nouvelle condition comme "q" (qui donc force non(A--->P)). Sinon, il demande au prouveur de prouver A, et choisit une condition qui force non(A), plus petite que q comme nouvelle "q" intime (elle existe).

En jouant de cette façon, le sceptique gagnera forcément la partie, car la condition la moins forçante force non(HC).

Quand le prouveur demande au sceptique de choisir un nom parce qu'il a une phrase qui commence par "quelquesoit" à prouver, le sceptique choisit un nom correctement* et garde q comme condition intime.

*q ne force "pour tout xR(x)" que si pour tout nom a, q force R(a)

Question: pourquoi n'importe quelle condition (donc la moins forçante) force non(HC)?

HC dit qu'il existe une surjection du plus petit ordinal $A$ non dénombrable sur l'ensemble des suites de 0 et de 1 (S). (En fait, on met une bijection entre le vrai "S" virtuel et un ordinal convenable, que l'on note encore S). Ce qui fait que, sans perte de généralité:

S'il existe une condition c qui force cet énoncé, il existe aussi un nom z qui est "forcé" d'être une surjection de A sur S par une condition d qui renforce c. Comme vu dans le fil précédemment, il existe alors un vrai ensemble, une vraie application f (et non pas un nom) de A dans S, ainsi qu'une condition e qui renforce d et qui force tous les couples (i,w) de z à être tel que w appartient à f(i). J'ai mis cet énoncé en italique, car sa formalisation est forcée par e, mais z n'est qu'un nom et non pas une vraie application.

e forcerait donc f à avoir une propriété qui permettrait de mettre une surjection de A sur S, ou plutot sur une ensemble d'ensembles dénombrables dont la réunion est S.

Pour les mêmes raisons, le A est en fait bêtement le vrai plus petit ordinal non dénombrable de l'univers réel initial. (même genre d'argument que ci-dessus)

Rappel: c'est la condition d'antichiane dénombrable du T qu'on a choisi qui permet de passer de z à f!

christophe c

{\it Mais voilà ça me donne la suite: je rentrerai dans les détails de ce que veut dire "collapser" au prochain post.}

Oups je n'avais pas tenu ma promesse. Bon... Mieux vaut tard que jamais

Disons qu'on se trouve dans l'univers $V$ (qui vérifie tous les axiomes qu'on veut, mais au moins ceux de ZFC)

Collapser un cardinal $\kappa$, ça veut dire "ajouter" une surjection d'un cardinal plus petit $\alpha$ que $\kappa$ sur $\kappa$.

Un telle surjection sera bien sûr hors de $V$ (sinon $\kappa$ ne serait pas un ordinal dans $V$)

Si "on force" avec l'ensemble $T$ (ordonné canoniquement) des applications de $\alpha$ dans $\kappa$ dont le domaine est fini alors les extensions génériques de $V$ modulo $T$ contiendront {\bf toutes} une surjection de $\alpha$ sur $\kappa$

La raison: et bien, si vous avez une application partielle $f$ (à domaine fini) de $\alpha$ dans $\kappa$, et un élément quelconque $x\in \kappa$, il existera toujours un prolongement $g$ de $f$ qui sera un élément de $T$ et tel que $x\in Im(g)$.

Ainsi pour tout $x\in \kappa$, l'ensemble des $f\in T$ telles que $x\in Im(f)$ est un ensemble {\bf dense}.

L'objet générique que le forcing rajoute (ou rêve de rajouter) à V est une partie filtrante* de $T$ qui rencontre toutes les parties denses* de $T$.

Evidemment, ce "générique" n'est pas dans $V$...


Rappels:

$(P,<)$ ordre partiel donné:

une partie $D$ de $P$ est dense quand pour tout $x\in P$ il existe $y\in D$ avec $y\leq x$

une partie (en général, elle ne peut pas être dans $V$, l'univers des ensembles "déjà là") $G$ de $P$ est générique quand elle son intersection avec n'importe quel dense est non vide et quand pour tout $x,y\in G$ il existe $z\in G$ avec $z\leq x$ et $z\leq y$

Dans l'exemple ci-dessus (où $P=T$) l'ordre $\leq$ est $\supseteq$

christophe c

Concrêtement rendre le vieux $\R$ dénombrable avec le forcing, ça se passe comme suit:

on force avec l'ensemble des suites finies de réels où $u\leq v$ signifie juste que $u$ prolonge $v$

On "imagine" (en dehors de $V$) un ensemble $G$ "magique" de telles suites (il sera appelé "générique") qui a les propriétés suivantes:

1) tout ensemble dense (de $V$ bien sûr!) de suites rencontre $G$

2) 2 suites finies $u,v$ dans $G$ sont "compatibles" (il existe un prolongement commun)

Exercice: prouver que $G$ donne canoniquement une suite $u$ de réels telle que tout réel $x$ (dans $V$) est égal à l'un des $u_n$

Alors évidemment, vous pourriez penser que le procédé diagonal de Cantor permet de construire facilement un réel qui n'est pas l'un des $u_n$.

Certes, mais un tel réel sera en dehors de $V$. Ce sera un "nouveau" réel créé par le forcing.

{\bf Ce que peut faire le forcing:}

Rajouter des réels, des suites, et tout un tas de choses

{\bf Ce que ne peut pas faire le forcing:}
L'une des impossibilités les plus célèbres: le forcing {\bf ne peut pas} rajouter une suite (même extérieure à $V$) d'ordinaux $\alpha _1, \alpha _2$, etc.. telle que pour tout entier $n$:
$\alpha _{n+1}<\alpha _n$

christophe c

Le deuxième point, ci-dessus, mérite une attention approfondie. quand on s'autorise un "pouvoir magique" (ici rajouter, rêver, ou je ne sais quoi des objets "extérieurs" à l'univers), il est bon d'avoir en tête une limitation, sinon on risque d'espérer que tout est permis (et du coup d'être découragé de réfléchir)

Ce que le forcing autorise très formellement comme rêve "accessible" est la chose suivante (répétition volontaire):

Etant donné une ordre partiel quelconque $(P,<)$ il existe un ensemble "générique" $G$ extérieur (ou non) à l'univers qui est une partie de $P$, qui rencontre toutes les parties denses de $P$ qui sont dans l'univers et qui est "filtrant" (2 éléments quelconques de $G$ ont un minorant commun)

Pourquoi $G$ est-il "magique"? Et bien, supposons qu'il soit dans l'univers: ça oblige alors son complémentaire dans $P$ à ne pas être dense. Il existe donc un élément $p$ de $P$ tel que tous les minorants de $p$ sont dans $G$, et comme $G$ est filtrant, tous les minorants de $p$ sont compatibles (ont un minorants commun 2 à 2)

La plupart des ordres partiels n'ont pas cette propriété. Leurs "génériques" sont donc "magiques" (extérieurs, forcément, à l'univers)

Cette magie, après tout pourquoi pas, pourrait autoriser à expérer qu'on puisse "rêver" ou "ajouter" une suite descendante extérieure à l'univers dans un bon ordre qui n'en a pas (évidemment, par définition) à l'intérieur de l'univers.

Il n'en est rien.


Soit donc un ordinal $\kappa$. Soit une application $f$ (dans l'univers!) de $P\times \N$ dans $\kappa$ et $G$ un $P$-générique, tels que pour tout entier $n$:

il existe un élément $p\in G$ tel que $f(p,n)<f(p,n+1)$

De plus on suppose que $f(q,n)\leq f(p,n)$ pour tout couple $(q,p)\in P^2$ tel que $q\leq p$


Ces hypothèses permettraient de fabriquer une suite descendante d'ordinaux à l'aide de $G$:

Soit $D_n$ la partie formée des éléments $p\in P$ tels que $\forall r\leq p: f(n,r)\geq f(p,n)$

Chaque $D_n$ est une partie dense de $P$ (exercice)

$G$ rencontre chaque $D_n$, disons en $p_n$, et on peut s'arranger pour que $p_{n+1}\leq p_n$



La suite (qui elle n'est pas dans l'univers, à priori, car définie à l'aide de $G$) $u:n\mapsto f(p_n,n)$ serait descendante.

Exercice: prouver que cela mène à une contradiction (sans rien supposer concernant $G$, de plus que ce qui a été déjà supposé)

christophe c

Histoire de faire remonter le fil, un petit lemme facile dès qu'on a digéré les préliminaires "forcing" et qui pourtant mérite la même célébrité que la découverte de Cohen

Historiquement, Godel a prouvé la consistance de HC en montrant qu'elle est vrai dans L et que L vérifie les axiomes de ZF.

Le forcing permet de partir d'un univers V de l'élargir en un univers V_2 qui vérifie HC (alors que peut-être V vérifie nonHC..) mais qui en plus contient les mêmes réels (et les mêmes suites d'objets) que V

De sorte que V_2 contient bien une surjection de omega1 dans IR (qui n'était pas dans V), mais ce faisant, il ne contient pourtant aucun nombre réel supplémentaire.


Première partie: soit (P,<) un ordre partiel tel que pour toute suite décroissante u_1>u_2... il existe un v dans P tel que pour tout n, u_n>v

Soit V_2 une extension générique de notre univers V, via P. G étant le générique qui intersecte tous les denses de P qui sont dans V

Alors toute suite u dans V_2 d'éléments de V est dans V. Soit une suite u dans V_2 et soit w un "nom" de u.

Remarque: la preuve ne peut pas être totalement naive, vous ne pouvez pas dire:

"soit p_1 dans G qui force w_1=x_1, p_2<p_1 dans G qui force w_2=x_2... finalement en prenant z<tous les p_i, z force que chaque w_n=x_n et donc w=x". En effet, la suite des p_i, n'est pas forcément dans V, car pour la définir, vous avez utilisé G

Cependant, l'idée est la même. comme 1 la moins exigeante des conditions de P force que w est une suite, soit q un élément quelqconque de P

il existe p_1<q et x_1 dans V tel que p_1 force w_1=x_1. Puis p_2<p_1 et x_2 tel que p_2 force w_2=x_2, etc

Ensuite soit z< tous les p_i. Alors pour tout entier n, z force w_n=x_n. Et donc z force w=x.

Ainsi il existe x une suite et z une condition <q (élément de P) telle que z force w=x.

L'ensemble D des z tel que il existe x tel que z force w=x est dense, dans V et rencontre donc G.

soit donc z dans G et x dans V qui force "w=x". Comme w est le nom de u, c'est que u=x et donc u est bien dans V.

christophe c

Dans ce post, une digression sur les jeux, de manière à préparer quelques points préliminaires pour détailler ma réponse du fil sur la omega conjecture

Les "set theorists" n'échappent pas au défaut répandu dans les maths: on retient plus facilement les théorèmes que leur preuve, et on oublie souvent que la preuve apprend plus que le théorème

Il en va ainsi du théorème de Martin que les jeux analytiques sont déterminés:

La démonstration consiste à transformer un jeu analytique en un jeu équivalent, mais fermé (donc déterminé) mais en jouant avec des ordinaux appartenant à un très gros ensemble

Par l'absurde, c'est finalement le joueur qui essaie de mettre la partie dans l'ensemble ouvert (donc qui gagne en temps fini) qui a une stratégie infaillible

On obtient ainsi, en raisonnant par l'aburde l'existence d'un certain réel (et on oublie que la correspodance de curry howard livre une sorte de "constructibilité" même pour les preuves par l'absurde hautement non constructible

Précisément (mais je ne vais pas imposer ici la technicité du th de Martin), vous pouvez vous affronter au petit problème suivant:

2 joueurs, "pair" et "impair" s'affrontent: ils jouent alternativement x1,x2, x3, etc

On se donne un certain ensemble T de suites finies.

Le joueur impair joue x1, puis x3 (connaissant x2), puis x5 (connaissant x2 et x4) etc

Le joueur pair joue x2 connaissant x1, puis x4 connaissant x1 et x3, etc

But du joueur impair: il existe un entier n tel que (x1,x2...xn) appartient à T

Dans ce cas, il gagne. Sinon la partie continue indéfiniment et c'est pair qui gagne

1) Démontrer que l'un des 2 joueurs a une stratégie gagnante
(c'est un grand classique)

2) étant donné une preuve que ce n'est pas pair qui a une stratégie gagnante, essayez de trouver de manière assez effective une stratégie infaillible pour le joueur impair

C'est extrêmement difficile, et il y a même un argument qui prouve essentiellement que c'est impossible dans le cas général (et pourtant ça a l'air en apparence plus simple que dans le cas opposé où on souhaiterait construire une stratégie pour le joueur pair...)

Le défi est lancé (sans qu'il y ait besoin de connaitre le forcing)

C'est essentiellement ce petit fait anodin qui conduit les recherches de Woodin et de ses associés à être un peu illusoires, car elles s'appuient sur l'idée d'un certain ordinal de rupture (dont l'existence est impliquée par ZF+tels et tels axiomes) alors que cet ordinal est une simple limite de l'Univers, mais relative à l'Univers, sans propriétés "absolues"... Détails à suivre

christophe c

Suite du post précédent:

Peut-être les quelques lecteurs se demandent-ils quel est ce mystérieux "ordinal de rupture" dont j'ai parlé...

Et bien, en fait, il s'aigit banalement de "omega_1", c'a dire du banal plus petit ordinal non dénombrable

Peut-être l'un des premiers exploits de Woodin (et de ses fans) a-t-il été de faire prendre conscience aux gens que omega1 est tout sauf non problématique...

En fait, il est immense!

Pour donner une idée de ça, l'axiome de détermination (déjà présenté dans ce fil) et dans d'autres entraine qu'il contient un ultrafiltre stable par intersection dénombrable. De plus cet ultrafiltre est canonique et définissable: il s'agit de l'ensemble des clubs, ie les parties C qui sont non bornées et stable par borne supérieure, ie si une suite u a son image incluse dans C alors sa borne sup est dans C.

En présence de l'axiome du choix "être muni d'un ultrafiltre stable par intersections dénombrables" fait du plus petit cardinal ainsi un grand cardinal. Un tel grand cardinal implique plein de choses, dont une spectaculaire, qui est qu'il n'y a qu'un nombre dénombrable de réels constructibles.


voir <a href="http://www.logique.jussieu.fr/~chalons/analysenonstandard.php">ce lien</a> pour une définition précise de ce qu'est un ultrafiltre

Ci-dessous, je vous prouve que IR, l'ensemble des nombres réels ne peut être muni d'un tel ultrafiltre:

Soit donc W un tel ultrafiltre. Il existe forcément un entier n tel que l'ensemble des réels y inférieurs à n est dans W. De même, avec supérieur. Soit donc un intervalle [p,n] qui appartient à W

Cet intervalle est compact donc W a une limite z dans [a,b]. Si le singleton {z} n'est pas dans W, alors il existe un entier q non nul tel que l'intervalle
]z-1/q;z+1/q[ a son complémentaire dans W (toujours la même raison, sinon le singleton {z} qui est l'intersection des ]z-1/r;z+1/r[ pour r entiers non nuls serait dans W.

Conclusion: W est trivial

Même l'ensemble P(R) ne peut être muni d'un ultrafiltre non trivial stable par inter denombrable:

Soit W un tel ultrafiltre sur P(R) (ensemble des parties de R):

Soit T l'ensemble des réels y tels que l'ensemble des A inclus dans R qui contiennent y est dans W.

Comme W ne contient pas le singletion {T}, pour chaque partie A de R, différente de T soit f(A) un réel dans la différence symétrique de T et A.

L'image de W par f est donc un ultrafiltre sur R stable par inter dénombrable. Il est donc trivial et contient le singleton disons {b}

l'ensemble des A inclus dans R tels que f(A)=b est donc dans W, si b est dans T contradiction et si b est hors de T contradiction aussi.

***

La notion d'ultrafiltre est très fédératrice: elle permet à la fois des maths classiques, l'analyse standard et permet de mieux comprendre le forcing, à travers les ultrapuissances génériques (issues des ultrafiltre génériques).

christophe c

Pour donner une idée (certes un peu abstraite) de l'économie de pensée que permettent les ultrafiltres (et en particulier ceux stables par intersection dénombrable), vous pouvez penser aux espaces de Hilbert:

Les Hilbert ont des boules "bien rondes"

Soit donc H un hilbert et W un ultrafiltre non trivial, stable par intersections dénombrables.

*W ne peut pas "être à l'infini": prouver qu'il existe un entier n tel que la boule de contre l'origine et de rayon n est dans W

*W a un "représentant" qui est l'unique porte du hilbert H pour le rejoindre: prouver qu'il existe un unique point y de H et un réel positif strictement r ayant la propriété suivante: l'ensemble des z de H tels que la distance de y à z est r est dans W et pour tout point t différent de y, il existe un réel s>r tel que l'ensemble des points z de H à la distance s de t est dans W.

Conclusion: y est le point le plus proche de l'objet virtuel sous-jacent à W et c'est le seul: en s'éloignant de y, on s'éloigne de W.

ccnc

Autre exemple amusant, avant un retour à omega1:

Soit A un anneau noethérien n'ayant qu'un nombre dénombrable de couples (I,P) où I, P sont des idéaux, et I inclus dans P, I non premier et P premier et on ne peut intercaler aucun idéal strictement entre I et P. Un tel anneau sera appelé "anneau violet". (Les couples (I,P) ci-dessus seront dits "atomiques")

Une barrière dans A est un ensemble T d'idéaux tel que pour tout couple d'idéaux (I, P) tels que I non premier, P premier et I inclus dans P, il existe J dans T tel que I inclus dans J inclus dans P.

Exercice: il existe un cardinal fixe k (éventuellement infini) tel que tout anneau violet admet une barrière de cardinal inférieur à k.

Question: y a-t-il des anneaux violets aussi grand que l'on veut?

christophe c

Remarque: l'exercice précédent est très facile, mais je n'avais pas la solution (évidente ou presque) avant de l'inventer... L'énoncé est "venu" tout seul de l'existence d'ultrafiltre comme si ou comme ca.

Retour progressif vers omega1 et les "jeux":

Soit k un ordinal et U un ultrafiltre sur k non trivial et stable par intersections dénombrables.

On suppose que k est le plus petit ordinal à admettre un tel U.

1) Prouver que k est un cardinal

2) Prouver que pour tout ordinal j<k, et toute application f de k dans j, il existe i appartenant à j tel que l'ensemble de z de k tels que f(z)=i est dans U

3) Prouver qu'il existe un ultrafiltre V sur k, non trivial et stable par intersections dénombrables tel que:

3.1) pour tout application f de k dans k tel que pour tout u dans k sauf 0, f(u)<u, il existe un élément m de k tel que l'ensemble des z tel que f(z)=m appartient à V.


3.2) Soit f une application de l'ensemble des parties finies de k dans un IN. Prouver qu'il existe une application h de IN dans IN et un élément A de V tel que pour toute partie finie G de A, f(A)=h(card(G))

La propriété 3.2 ci-dessous fait de k ce qu'on appelle un cardinal de Ramsey.

L'affirmation il existe un cardinal de Ramsey est en elle-même un axiome de grand cardinal.

christophe c

Alimentation du fil:


bin, tiens histoire de faire un peu de pub aux ultrafiltres...

1) Ils donnent presque gratuitement l'analyse non standard (qui permet d'avoir une "vision" pour les gros théorèmes d'analyse qui ne sont pas des résultats "finis" cachés)

2) Ils se marient très bien avec la compacité et en offre (de la compacité) là où il y en a peu

3) Ils rendent les moult théorèmes "à la Ramsey" faciles à prouver (exemple ci-dessous)

4) Ils donnent "gratuitement" le théorème de complétude (qui dit que la logique classique été "bien choisie" et ne pouvait l'être autrement, entre autre)

Ca a été évoque récemment dans un autre fil, voici la preuve d'un théorème de Hindman, assez spectaculaire:

Soit f une application de IN dans un ensemble fini F

Définition: étant donné 2 ultrafiltres U,V sur IN, on note U+V l'ensemble des parties A de IN telles que {x/ {y/ x+y est dans A} est dans V} est dans U

L'opération est continue à gauche (en fixant la variable de droite) sur l'ensemble des ultrafiltres sur IN où les voisinnages de U sont de la forme "ens des V tels que A est dans V" avec A dans U

l'espace est compact donc il existe un ultrafiltre U tel que U+U=U

(Considérer un fermé L minimal non vide stable par +: soit U dans L l'ens des V qui peuvent s'écrire W+U avec W dans L est fermé et stable par +. Donc il contient L. Donc soit V dans L tel que V+U=U. L'ens des V' tels que V'+U=U est stable et fermé donc contient L donc U+U=U)


Soit A_n une suite de parties de IN et a_n une suite d'éléments de IN avec:

a_1<a_2<....

a_i est dans A_i

A_i contient A_{i+1} pour tout entier i

A_i est dans U

pour tout x dans A_(i+1), a_i+x est dans A_i


il existe c dans F tel que pour tout x dans A_1, f(x)=c

Soit B l'ensemble infini formé par les a_i.

alors toute somme s (finie) d'éléments de B est tel que f(s)=c

(construction "évidente" par récurrence: après avoir a_n; A_n, prendre le A_(n+1) dans U qu'il faut puis prendre a_(n+1) dans A_(n+1)

**********

christophe c

Rien à voir, mais pour les "amateurs" curieux qui oublient parfois un truc sur ZF, ZFC, etc:

On se donne 2 ens de "constantes" infini dénombrable

On numérote tous les énoncés clos, R_n avec éventuellement des constantes en paramètres écrits avec "pour tout", "implique" et "appartient"

Puis on regarde l'arbre T (objet tout à fait syntaxique) formé des suites finies [u_1,...,u_n> où chaque u_i est ou bien R_i ou bien nonR_i

A chaque R_i(x) on adjoint "proprement" une des constantes, c et l'axiome "si R(c) alors pour tout x R(x)" (en prenant c sans tricher).

On exige que les axiomes de ZF soient vrais (si une suite finie contient "nonA" avec A axiome de ZF, elle est rejetée)

On rajoute un nombre de petites exigences de ec genre (informatiquement très simples) et ça nous donne un sous-arbre S de T formé de suites finies acceptables.

Les branches infinies de cette arbre sont les modèles de ZF

En particulier, la branche "la plus à gauche" est un modèle de ZF... (en décrétant que la suite u+P est plus à gauche que la suite u+nonP

En particulier (si ZF est consistant), il existe un modèle arithmétique de ZF (calculez sa complexité)

ccnc

é bé, je viens de battre le record de longueur de pause à alimenter ce fil... Bon, je me fais un peu violence:

comme il ne me vient pas grand chose à l'idée dans l'immédiat, voici un ptit exercice:

Construire une algèbre de Boole B complète et 2 appplications f, g de N dans B (où N désigne l'ensemble des entiers naturels) telles que:

Pour toute partie infinie A de N, la disjonction des f(x) pour x dans A vaut 1
Pour toute partie infinie A de N, la disjonction des g(x) pour x dans A vaut 1

Pour tout x dans N, f(x) inter g(x)=0

---

Je pense que cet exercice est un bon "pont aux ânes" pour qui a été découragé par la lecture du fil et son énoncé est simple

Rappels: dans une algèbre de Boole, "a inter b" désigne la borne inf de a et b et le mot "disjonction" est utilisé pour désigner la borne sup

Une algèbre de Boole complète est un ordre (E,<) dont toute partie a une borne inf et une borne sup. La borne sup des éléments de E est notée 1 et la borne inf des elts de E est notée 0. De plus on demande une distributivité (finie) entre inf et sup. Autrement dit, en notant a+b la borne sup de a,b et × la borne inf de a,b: a+(b×c)=(a+b)×(a+c) (et dualement)


---

Les f,g de l'exercice représentent 2 ensembles "virtuels" et disjoints qui rencontrent chacun toutes les parties infinies de N

pour un entier n, f(n) est "la valeur booléenne" (ou encore une sorte de probabilité au sens large) que n soit dans l'ens virtuel représenté par f. Idem pour g.

La condition f(x) inter g(x)=0 représente pour chaque x, représente l'exigence qu'ils soient disjoints. La condition disj des f(x) pour x dans A=1, représente l'exigence que l'ens virt représenté par f rencontre A.

christophe c

Histoire d'alimenter le fil, sinon, je risque d'attendre 10a....

quelques mots sur la manière de prouver des indécidabilités concernant l'axiome du choix (je crois que je n'en ai pas beaucoup parlé)

Comment, par exemple, on prouve que l'énoncé "tous les ensenbles sont mesurables" est compatible avec ZF (tous les axiomes des maths sauf l'ax du choix)

Voici l'idée générale:

1) on part d'un univers V vérifiant ZFC, qui contient un cardinal d inaccessible.

2) on rend tous les cardinaux <d dénombrables (on passe à un univers V2 un peu plus large)

3) V2 vérife toujours ZFC...

4) Dans V2, on s'intéresse seulement aux objets héréditairement définissables en termes de réels***

5) ils forment un sous-univers M de V2 qui vérifie ZF + "tous les ens sont lebesgues mesurables"

(lol pour une fois j'ai fait simple?)

Pour caricaturer, un ensemble de réels, dans M, est presque un ensemble borélien dans V2 à 3 chouillas près (c'est assez spectaculaire d'ailleurs)


***Pour info, on part de IR, qu'on note L0, et pour chaque ordinal a, L_a est la réunion R des L_b, b<a et de l'ensemble des parties de R qui sont définissables avec "appartient" et quelque soit et implique

La "réunion" des L_a, pour a ordinal forme le sous-univers M

---

Une question générale: tout peut-il être "décidée" par le forcing (autrement dit, étant donné un énoncé, peut-on "décider" si oui ou non il est indécidable en n'ayant que la méthode du forcing à portée de main)?

Réponse: en un certain sens, oui!

Pas directement, mais dans le sens suivant:

Soit M un modèle bien fondé de ZFC. S'il existe un modèle N de même hauteur que M qui vérifie un énoncé E alors les habitants de M peuvent "presque" le savoir. C'est du forcing "extérieur".

Exercice: j'ai déjà dit dans le fil pourquoi, trouver où. Aide: c'est le théorème de complétude généralisé au calcul propositionnel infini où on autorise les conjonctions quelqconques (et pas seulement finies)

---

Info! il y a lgtps que je n'y avais pas pensé, mais voici une conjecture toujours non résolue: la conjecture de Vaught.

Elle dit: si pour une théorie T il n'y a pas d'ensemble parfait* de modèles non isomorphes, alors T n'a qu'un nombre dénombrable de modèles (non isomorphes)

Je parie (personnellement) qu'elle est vraie. Qu'en pensez-vous?

*c'est un ensemble de réels non dénombrables et sans point isolé

gilderetz0

bonjour

J'allais quand même pas te laisser seul.
je me demandais premièrement la différence qu'il y a entre la démonstration par forcing "partant de" ZFC et celle "partant de" NBG. Deuxièmement, comment "réinterpréter" l'invariance par forcing d'un modèle en termes d'ultrafiltre. Troisièmement, pour la conjecture de Vaught-Steel, il y avait un papier intéressant mais peut être que tu l'as déjà lu disponible à l'adresse suivante
http://arxiv.org/abs/math.LO/0007199

sinon je me dis qu'en considérant un modèle saturé(MS) et un modèle atomique(MA)(pour l' "ordonnancement" des modèles, un joli appel à "l'axiome de l'ultrafiltre" serait peut être possible ou nécessaire qui sait ), il est peut être possible de montrer que pour chaque n-type du modèle saturé non contenu dans le modèle atomique, "modèle atomique + n-type" est non isomorphe MS et MA mais aussi à certains autres "MA+ p-type". Bon après toutes les bêtises que je viens de dire, je vais me coucher.
.
A plus.

christophe c

lol j'étais tellement omnubilé par les déterminants que je ne vois plus rien d'autre...

je me demandais premièrement la différence qu'il y a entre la démonstration par forcing "partant de" ZFC et celle "partant de" NBG

je connais mal NBG, mais du peu que je m'en souvienne, il ne doit pas y en avoir bcp:

Le forcing permet juste de mettre en forme proprement le fait que si un modèle M de ZFC est bien fondé "il voit" les modèles de même hauteur que lui, mais plus large qui vont satisfaire tel ou tel énoncé. J'ai décrit le principe dans un des premiers posts: si tu as une formule propositionnelle (infinie et peu importe la taille de ses conjonctions et de ses disjonctions, on fait comme on veut qui est dans M) alors s'il n'existe pas une preuve dans M (au sens du calcul propositionnel) qu'elle est fausse, il existe un modèle de cette formule (ie l'attribution de vrai/faux à ses variables prop) qui est "presque" dans M, ie qui est dans une extension générique de M. En gros c'est l'alpha et l'omega du forcing: "voir" tousles objets extérieurs à l'univers qui n'ajoutent pas d'ordinaux "au dessus" de M. Ca devient compliqué pour des raisons peu significatives à cause des quelquesoit il existe alterné, mais essentiellement, le forcing ne fait que "voir" les modèles propositionnels des formules qui en ont: par exemple une "injection" de E dans IN se "demande" (au père noel) par une liste d'axiomes propositionnels et les forcing permet de "voir" qu'il n'y a pas d'obstruction (il n'y en pas dans "M", mais c'est tout (de telle injection))

Deuxièmement, comment "réinterpréter" l'invariance par forcing d'un modèle en termes d'ultrafiltre

Je ne comprends pas ta question à cause de l'expression "invariance par forcing": peux-tu préciser?

Merci pour le papier sur Vaugth mais non, je n'ai pas le courage de le lire et je ne le connaissais pas. Ma conviction qu'elle est vraie tient au fait que fausse, elle permettrait grace à une seul théorie de premier ordre de "voir" tous les ordinaux (y compris ceux au-dessus du modèle qui contient la théorie contre-exemple)

En fait, il y a un moyen simple, étant donné une théorie qui n'a pas un ens parfait de modèles 2 à 2 non isomorphes d'accéder aux ordinaux dénombrables via ses modèles dénombrables (la preuve par enrichissement du langage jusqu'à obtenir tous les non isomorphiques)

Pour la suite de ton post je ne comprends pas et ne connais pas bien les notions auxquels tu fais référence:

en particulier je ne sais pas ce qu'est un modèle saturé (on me le redit régulièrement et je le réoublie à chaque fois)

christophe c

Alimentation du fil (pour me rappeler qu'il existe)....

Le saviez-vous?

Soit D une partie de $\Q$, l'ensemble des rationnels, qui est bien fondée (pas de suite $u_1>u_2>..$ d'éléments de $D$)

On considère la relation binaire Z suivante entre les couples c:= (R(x); r) (l'ensemble de ces couples sera appelé T) où R(x) est une relation avec une seule variable libre écrite seulement avec $\in$; $\notin$ des $\forall$ et des $\cap$ et $\cup$ et (le connecteur "implique") et mise sous forme prénexe (tous les quantificateurs sont avant le reste). L'élément r du couple c ci-dessus sera noté e(c).

Elle est définie par induction:

pour que cZd, il faut et il suffit que :

$e(c) < e(d)$ ET que le joueur $\exists$ soit avantagé (ait une stratégie gagnante) au jeu suivant: on suppose que d=(R(x);e(d))

on remplace "x" (dans R(x)) par c

les 2 joueurs $\forall$ et $exists$ remplacent alternativement leur variable liée par des éléments u de T tels que $e(u)<e(d)$

Puis quand arrive la fin de ces remplacements (on se donc devant une conjonction ou une dsijonction), si c'est une conjonction c'est $\forall$ qui choisit lequel de ses items avec qui on continue et sinon c'est $\exists$.

On arrive finalement à une formule de la forme $a\in b$ (1) ou de la forme $a\notin b$ (2)

mais $e(a), e(b)<e(d)$.

si c'est (1): alors $\exists$ gagne ssi aZb et sinon, si c'est la forme (2), $\exists$ gagne ssi a (nonZ) b


Exercices: prouvez que Z est bien fondée (c'est assez trivial)

Soit $f$ l'unique fonction qui a la propriété suivante:

pour tout a dans T: $f(a)=\{f(x)/ x\in T\ et\ xZa\}$

Prouvez que pour tout a, f(a) est dénombrable, et même que l'ensemble des f(a), pour a dans T est dénombrable

Toute cette construction dépend à priori du $D$ bien fondé qu'on a choisi au départ. L'ensemble des $f(a)$ tels que $a\in T$ sera donc noté $L_D$.

Soit $D;E$ 2 parties bien fondées de $\Q$: prouvez que $L_D\subseteq L_E$ ou $L_E\subseteq L_D$

Essayez de construire un ensemble d'entiers qui n'est pas dans la réunion des $L_D$ quand $D$ parcourt l'ensemble des parties bien fondées de $\Q$

christophe c

Problème (probablement ouvert):

on travaille dans la théorie contraadictoire suivante: pour toute relation unaire R(x), on se donne le droit de dire que:

$\{x/ R(x)\}$ contient exactement exactement les $a$ tels que $R(a)$

Elle est contradictoire car le fait de considérer l'ensemble des $x$ tels que $x\in x \to tout$ suffit à prouver "tout" (ce qu'on veut)

Maintenant on considère les 2 phrases suivantes comme {\bf parfaitement "égales":} (ie dans la suite, on peut subsituer l'une à l'autre sans contrainte)

$R(a)$

$a\in \{x/ R(x)\}$

On va restreindre le "droit de démontrer"...

je rappelle qu'une preuve est un arbre bien fondé (les sommets sont étiquetés par des énoncés) ayant les propriétés suivantes:

sa racine est sa conclusion

il y a 4 sortes seulement de possibilités:

1) le sommet $P$ n'a que 2 fils, l'un étiqueté par $A\to P$ l'autre par $A$

2) le sommet $P$ est de la forme $\forall xR(x)$ et a comme ensemble de fils un ensemble de sommets étiqueté par chaque $R(a)$ possible (où $a$ est de la forme "ensemble des x tels que..." les "..." parcourant tous les relations possibles unaires (x seule variable libre) avec ou sans paramètre

3) le sommet $P$ est dlf $R(a)$ et n'a qu'un fils qui est $\forall xR(x)$

4) le sommet $P$ est $A\to B$ et n'a qu'un fils qui est $B$

Les feuilles sont étiquetées chacune par un énoncé de la forme $A$ tel qu'il existe $B$ avec $A\to B$ qui étiquette au moins un de ses ancètres ou sinon, elles sont de la forme $A\to A$



on dira qu'une preuve est "sans boucle" quand on ne trouve pas de configurations d'une des formes suivantes:

* un sommet P dans la catégorie 1, avec son fils $U\to P$ qui est dans la catégorie 4

* une succession 3-2

* une possibilité de remplacer les énoncés par d'autres "égaux" (voir début en gras) de sorte qu'on obtienne des boucles

* des feuilles de la forme $A\to A$

{\bf \it les conclusions des preuves sans boucles forment-elles une théorie consistante? Sont-elles toutes des théorèmes de ZFC?}

christophe c

Je vais commencer à corriger quelques exercices donnés au cours du fil, mais désolé dans le désordre et selon la météo (histoire d'utiliser le joli LaTeX du forum.

L'une des familles de théorèmes annoncée par les progrès de la logique a le titre suivant:

{\it tout théorème de maths est un cas particulier d'évidence}

Bien évidemment, comme c'est un "slogan" français, il faut lui donner un corps. Dans la suite de ce post je propose un de ces corps, plutôt issu de la correspondance de Curry Howard. Il y a moult variations...

{\bf Lemme1:} au prix de peu d'axiomes, on peut restreindre toutes les preuves de maths à une seule règle et des axiomes. La règle est le modus ponens: De $A\to B$ déjà prouvé et $A$ déjà prouvé on peut inférer $B$

{\it preuve:} la seule autre chose utilisée pour écrire des preuves de maths est l'abstration, qui est une règle un peu "usine à gaz" à expliquer aux non logiciens. Elle consiste à écrire des preuves avec hypothèses (prenons une de ces preuves $d$ (dont la conclusion est C) qui utilise A parmi ses hypothèses), puis à prétendre d'un revers de mains que {\it la "même" preuve d} établit $A\to C$ {\bf sans supposer A}

C'est assez incontestable dans la mesure, où on remplace l'utilisation de A dans d, par la supposition de A dans la conclusion.

Soit donc une preuve $d$ qui conclut C et qui utilise $A$ et ne s'autorise que des modus ponens (et fait évidemment et forcément tout plein d'autres hypothèses). On procède par récurrence sur la hauteur de $d$. On suppose que $d$ à une hauteur minimum parmi les preuves qui seraient des exceptions au lemme1.

$d$ contient 2 sous-preuves $d_1,d_2$ , l'une de $B\to C$ et l'autre de $B$, chacune étant par hypothèse de hauteur inférieure à $d$.

Donc il existe 2 preuves $d'_1;d'_2$ n'utilisant pas $A$ et concluant respectivement $A\to (B\to C)$ et $A\to B$ et ne s'autorisant que le modus ponens et les autres hypothèses de $d$ + éventuellement des axiomes.

Voici comment fabriquer une preuve de $A\to C$ n'utilisant que le modus ponens et les autres hypothèses de $d$:

on suit d'abord $d'_1;d'_2$ puis on évoque l'axiome $(A\to (B\to C))\to ((A\to \to (A\to C))$ que l'on coupe (modus ponens) avec la conclusion de $d'_1$ qui est $A\to (B\to C)$ pour inférer $(A\to \to (A\to C)$

Maintenant qu'on $(A\to \to (A\to C)$ ainsi que $A\to B$ (grace à $d'_2$) on infère $A\to C$

{\bf Initialisation:} voyons ce qu'il en est pour les preuves d'une seule étape (autrement dit les affirmations pures et simples). Je prouve $A$ sans l'inférer de quelque chose: autrement dit, il fait partie des hypothèses. Pour obtenir une preuve de $A\to A$ sans hypothèse... Et bien je considère que $A\to A$ est un axiome. Je n'ai pas utilisé $B$, mais si je veux prouver $B\to A$ à partir de l'hypothèse $A$, j'utilise $A\to (B\to A)$

{\bf Remarque:} le choix des axiomes triviaux à rajouter (là j'en ai choisi 2 pour ne pas en taper trop long) est large et on a l'embarras du choix en fait.

Ainsi au prix du rajoute de quelques axiomes "évidents" et immadiatement reconnaissables comme tel, on peut faire toutes les maths avec la seule règle du modus ponens.

{\bf Théorème: pour tout théorème $P$ il existe un axiome $A$ tel que $A\to P$ soit une évidence}

{\it preuve:}

{\bf définition}: "évidence" veut dire conjonction affaiblie d'axiomes

Qu'est-ce qu'une conjonction affaiblie?

soit $A_1;A_2;....;A_n$ une suite finie d'énoncés et $B$ un énoncé. Soit $T:=A_1\to (A_2\to (... )))...)$.

{\it définition:} $T\to B$ est appelé "conjonction des $A_i$ modulo $B$

On procède comme dans la preuve du lemme (je ne réécris pas tout), supposant qu'on a une éventuelle preuve de hauteur minimale qui conclut P. Juste avant de conclure $P$, la preuve évoque qu'elle a déjà prouvé un énoncé $A\to P$ ainsi que $A$, et par hypothèse de minimalité, il existe des axiomes E,F tels que:

$E\to (A\to P)$ est évident et $F\to A$ est évident.

La conjonction affaiblie modulo P des 4 énoncés (les 2 précédents + E + F) est une évidence de la forme $T\to P$ où $T$ est un axiome.

{\bf Remarque et généralisations:} on peut aller plus loin, mais c'est une mise en bouche qui me semble édifiante. Les arguments précédents passent parfaitement bien à la logique infinie (où on accepte les conjonctions quelconques, etc)

Pour connecter ça avec les autres choses, je signale que n'utiliser que $\to $ (le signe "implique") n'est pas appauvrissant. En effet, rappel:

* nonA:=$A\to tout$

* A et B est par définition la conjonction affaiblie de A; B modulo tout (lol donc pas très affaiblie)

* A ou B est par définition non((nonA) ou (nonB))

etc

Bien sûr, je propose là les traductions "logique classique", mais c'est un simple jeu de peaufiner tout ça pour faire de l'intuitionnisme.

Les axiomes TOUJOURS admis (logique classique) sont:

* $tout\to A$

* $(non(nonA))\to A$

{\bf Remarque philosophique:} il est intéressant de revoir le théorème de complétude sous l'angle de ces "nouveautés":

{\bf Théorème de complétude:} pour tout énoncé A: ou bien il existe un modéle de nonA, ou bien il existe un axiome E telque $E\to A$ est une conjonction d'axiomes (ie est évident)

christophe c

Il a été question dans le fil suivant des axiomes de grands cardinaux.

http://www.les-mathematiques.net/phorum/read.php?7,513528

Je sais que ça fascine un peu, mais peu d'accès publics à ces notions. Je crois que je l'avais déjà fait (peut-être même dans ce fil), mais je le refais: je donne la liste des "superinfinis" les plus célèbres, en partant d'en bas (juste au dessus de $\N$) et en allant jusqu'en haut (l'inconsistance). Je ne mentionne que les plus spectaculaires.

axiome:: il existe un ensemble infini

axiome:: il existe un ensemble inaccessible

définition: un ensemble inaccessible $E$ est un ensemble transitif, stable par $x\to P(x)$ et tel que pour toute partie $A$ de $E$ telle que $|A|<|E|: \ A\in E$



axiome:: Il existe un ordinal de Ramsey.

définition: $z$ est un ordinal de Ramsey, ssi pour toute application $f$ de l'ensemble des suites finies croissantes d'éléments de $z$ dans un ensemble fini $G$, il existe une partie $T$ non bornée de $z$ et une application de $\N$ dans $G$ telle que pour toute suite finie $s$ d'éléments de $T$; $f(s)$ est égale à $g(n)$ où $n$ est la longueur de $s$


axiome:: il existe un ensemble $E$ et un ultrafiltre sur $E$, non principal et stable par intersection dénombrable


axiome:: il existe un cardinal présupercompact

définition: un cardinal $z$ est présupercompact quand pour tout ensemble $E$, si on note $W$ l'ensemble des parties de $E$ qui sont de cardinal $<z$ alors il existe un ultrafiltre $U$ sur $W$ tel que pour tout $x\in E$ l'ensemble des $A\in W$ tels que $x\in A$ est dans $U$ et pour toute fonction choix $f$ définie sur $W$, il existe un élément $e\in E$ tel que l'ensemble des $A\in W$ tels que $f(A)=e$ est dans $U$

remarque: j'ai simplifié la définition traditionnelle, pour qu'elle tienne en quelques lignes, le plus petit cardinal présupercompact étant supercompact, ça ne change rien (l'axiome habituel est "il existe un cardinal supercompact")


axiome:: il existe un cardinal extensible

définition: un cardinal $z$ est dit extensible ssi pour toute théorie du second ordre $T$ qui n'a pas de modèle plein, il existe un sous ensemble de $T$, de cardinal $<z$ qui n'a pas de modèle plein


axiome:: il existe un ensemble inaccessible qui est Vopenka

définition: $E$ est Vopenka quand pour toute partie $A$ de $E$ qui n'est pas un élément de $E$, il existe $(a,b)\in A^2$ avec $a\neq b$ et il existe un plongement élémentaire $j$ de $a$ dans $b$ (un plongement élémentaire est un morphisme qui respecte toutes les formules)



axiome:: il existe une suite stristement croissante $n\to E_n$ d'inaccessibles et une fonction $j$, telle que la réunion $R:=\cup_n E_n$ est un modèle de ZFC et tel que $j$ est définie sur $R$ à valeur dans $R$ et est un plongement élémentaire, avec pour tout $n\in \N: j(E_n)=E_{n+1}$

On peut aller un tout petit peu plus loin, sans avoir encore rencontré de contradiction, mais on se heurte vite à la borne de Kunen qui est contradictoire:


axiome: "borne de Kunen": il existe un inaccessible $E$ et un plongement élémentaire $j$ de $E\to E$ tel que $j$ n'est pas l'identité sur les ordinaux de $E$.




Remarque: cette hiérarchie est vraiment "enfantine" dans le sens que ça fait penser aux géants de Marvel, il y a un ordre total.

J'avais inventé une notion qui a été reprise par un mathématicien J.Hamkin et exploitée différemment de mes intentions initiales par Lui et Woodin. . Cette intention était de mettre en lumière que l'aspect "ordre totale"est beaucoup plus liée à nos délires compulsifs que "réelle". En effet, toutes la science plaide plutôt en faveur du nombre "au moins 2", ie à une sorte d'existence de 2 sexes, l'un ne pouvant produire vraiment sans l'autre. Par exemple, tous les théorèmes de maths sont le mariage de 2 axiomes (voir post juste avant), il y a 2 orientations, 2 valeurs de vérité, en théorie des jeux, 2 adversaires qui s'affrontent (donnant une notion de mariage pour les degrés de Turing (de calculabilité)), etc. Je pensais donc qu'il y avait des axiomes qui réagissaient avec les grands cardinaux sans être des axiomes de grands cardinaux et de fait j'ai trouvé une famille générale qui joue ce rôle, famille que j'ai appelé "les catalyseurs".

La manière la plus simple de la présenter est le schéma d'axiomes suivant, pour chaque énoncé:

si P est forçable et si nonP n'est pas forçable alors P

C'est une version courte.


Pour en profiter pleinement, mais ça devient alors un axiome de grand cardinal partiel, par contre c'est un ultracatalyseur, le mieux est de dire:

V étant notre univers alors pour toute extension générique $V_2$ de $V$, il existe une extension généraique $V_3$ de $V$ contenant $V_2$ et telle que $V$ se plonge élémentairement dans $V_3$.

Ca implique évidemment que le premier schéma est vrai dans $V$, mais Woodin m'a écrit que ça implique d'avance un certain nombre d'axiomes de grands cardinaux.

Il faut remarquer que ça catalyse TOUS LES AUTRES, même ceux qui ne sont pas impliqués.

christophe c

Je reviens sur la notion de mariage, en l'absence de l'axiome du choix on a un phénomène très intéressant:

on s'intéresse au "degrés de Turing". Qu'est-ce que c'est? Soit $x,y\subseteq \N$ (identifiables à des suites de 0 et de 1...)

On dit que $x$ est plus fort que $y$ s'il existe un programme (par exemple en pascal) qui en se servant de l'oracle $x$ produit $y$

autrement dit une

function y(n: integer):boolean;
a,b,..:boolean;p,q,..:integer
begin
....
des instructions du genre p:=x(n)
...
end;


Les degrés de Turing sont les classes d'équivalence pour "x est plus fort que y et y est plus fort que x"

si u,v sont 2 degrés de Turing, u+v est défini assez canoniquement. On prend un représentant x de u et un y représentant de v, et u+v est la classe de z(2n):=x(n) et z(2n+1):=y(n) (exercice ça a un sens)


Maintenant, si les degrés de Turing disposaient d'une bonne agence matrimoniale, ils pourraient réaliser tous leur rève, en effet, on a le théorème suivant:

Soit T l'ensemble de degrés de Turing. Soit f une fonction de T dans T. Alors il existe 2 degrés de Turing u,v tels que:

u+v est plus fort que f(u)+f(v)

Suffit donc de prendre f qui à chaque u associe "les rèves de u".

Remarque: le théorème précédent est une conséquence de l'axiome AD (tous les jeux sont déterminés, déjà abordés dans ce fil)

christophe c

Un problème ouvert consiste à identifier un sexe mâle et un sexe femelle chez les degrés de Turing...

christophe c

Avant de m'absenter, je reviens sur la borne de Kunen (donc le haut de l'univers, tellement haut qu'il est contradictoire), je l'ai mis en rouge dans le post d'avant.

J'en donne une démonstration, dans la mesure, où, dans le paradigme des grands cardinaux, on peut considérer que c'est la démonstration la plus "puissante" des maths (celle qui est juste à la limite entre consistance et inconsistance). En effet, "in some sens", la borne de Kunen est la borne supérieur des infinis "consistants" et donc toute preuve de maths n'est qu'une sorte de déclinaison grossière de cette preuve, qui utilise d'ailleurs toutes les subtilités de la démarche mathématique. Je saute 2 ou 3 étapes, mais je complèterai.

La plupart des énoncés de grands cardinaux enlève un tout petit peu de force à la borne de Kunen, c'est ainsi qu'ils sont construits très souvent.

Le théorème suivant a été démontré ici même (je remettrai le lien vers le fil), et il va servir:

(1) Pour tout ensemble $E$ il existe une application $f$ de $E^\N$ dans $E$ telle que pour toute suite $u\in E^\N$, il existe un entier $p$ tel que pour tout entier $n>p$:

$u_n=f((u_{n+1};u_{n+2};...)$

---

Preuve que la borne de Kunen est contradictoire

Soit $j$ un plongement élémentaire de $E$ dans $E$ ($E$ étant un inaccessible) et $a$ le plus petit ordinal tel que $j(a)>a$. Posons $b_{n+1}:=j(b_n)$ pour tout $n$, avec $b_0:=a$

Remarque: pour tout ordinal $e<a:j(e)=e$ donc pour tout ordinal $e:j(e)\neq a$


Comme $E$ est inaccessible, il existe $s\in E$ qui est la borne supérieure de la suite $b$. $j(s)=s$, car $j(b)=(b_1;b_2;b_3..)$, en effet, l'énoncé "$b_n$ est le terme numéro $n$ de $b$" est conservé par $j$ et donc "$j(b_n)$ est le terme numéro $n$ de $j(b)$", etc

Soit $T$ l'ensemble des parties de $s$ de cardinal celui de $s$. Soit $f$ est une fonction comme en (1), pour $s$.

On construit par récurrence $A_{n+1}\subseteq A_n$ et $c_n$ avec $A_0:=s$ de sorte que:

a) pour tout suite $v$ à valeurs dans $A_{n+1}$, la fonction $f$ n'envoie pas $v$ sur $c_n$

b) les parties $A_n$ sont de même cardinal que celui de $s$

c) $c_n\in A_n$

Ca mène à une absurdité car pour le $p$ dont l'existence est affirmée dans (1), la suite $d:=(c_{p+1}; ...)$ a toutes ses valeurs dans $A_{p+1}$ et pourtant $f(d)=c_p$

Il s'ensuite qu'il existe une étape $n$ telle que pour toute partie $X$ de $A_n$ de cardinal $s$, et tout élément $c$ de $A_n$, il existe une suite $v$ à valeurs dans $X$ telle que $f(v)=c$

En transportant tout par bijection vers $s$, on obtient donc une fonction $g$ de $s^\N$ à valeurs dans $s$ ayant la propriété suivante:

pour tout élément $x$ de $s$ et toute partie $X$ de $s$ de cardinal égal à $s$, il existe une suite $v$ à valeurs dans $X$ telle que $g(v)=x$. Une telle fonction $g$ sera dite correcte.

Revenons au plongement $j$. "Etre correcte" étant une notion définissable (on vient de le faire), et $j$ étant un plongement élémentaire, $j(g)$ est une fonction correcte pour $s$.

Soit $Y$ l'ensemble des $j(e)$ pour $e\in s$.

$Y$ a le même cardinal que $s$ et donc il existe une suite $w$ à valeurs dans $Y$ telle que $j(g)(w)=a$ (Rappel: $a$ est un ordinal tel que $j(a)>a$ et c'est le plus petit donc, $\forall b: j(b)\neq a$

Chaque $w_n$ est de la forme $j(v_n)$, puisque $w$ prend ses valeurs dans $Y$.

En fait, même, la suite $v$ est telle que $j(v)=w$.

donc $j(g)(j(v))=a$

soit $t:=g(v)$. Alors "t est l'image par g de v" et donc $j(t)$ est l'image par $j(g)$ de $j(v)$ et donc $j(t)=a$ contradiction.

christophe c

Ma conviction:

certes, elle n'est pas "officiellement" partagée. En fait, je pense que les axiomes de Peano, même eux, sont contradictoires, autrement dit qu'il existe une preuve de "tout" en les supposant.

Godel a démontré "qu'on ne pourrait jamais savoir" s'ils sont consistants, qu'on ne pouvait "qu'y croire".

Russel (ou d'autres) a démontré que la théorie "totale" (celle qui suppose que toute collection définissable est un ensemble) est contradictoire.

Le premier "infini" est celui de Peano. Le passage à l'ensemble des parties (via Cantor) a révélé que c'est lui qui est puissant (avec l'extensionnalité).

Depuis, on fait des maths "sans risque" en n'utilisant que des axiomes "éliminables" en ce sens que chacun d'entre eux n'a de risqué que l'infini supplémentaire qu'il suppose. Ca permet de savoir où s'arrêter. On monte, on monte, et si on tombe sur une contradiction, on redescends, mais il n'y a pas de "difficulté" autre que de croire "à l'infini".

ZF représente une convention centrale car les infinis qui y sont supposés sont "modérés" (on passe à l'ensemble des parties un certain nombre de fois dans une preuve, encore que les matheux, vont rarement au delà de P(P(R)) et quand on veut monter plus haut, on "indice" l'itération de passer à l'ensemble des parties par un plus petit objet dont l'existence est déjà prouvée)

Les axiomes de grands cardinaux "marquent" les différentes façons de monter plus haut "gentiment". Le "tout en haut" est la borne de Kunen. On est obligé de se placer en dessous puisqu'elle est contradictoire.

J'ai le sentiment qu'on va redescendre comme ça, lentement, en "cassant" les axiomes encore tout en haut et pour l'heure consistants, puis qu'on passera par le cassage de ZF (dans longtemps?), puis, bouquet final, par celui de Péano.

La physique (la MQ et la relativité) nous invite à avoir l'intuition qu'effectivement, la Nature semble avoir voulu de l'infini, mais qu'elle n'y est pas parvenu (la MQ et la relativité sont des découvertes que certaines limites finies remplacent l'infini). Pourquoi n'y est-elle pas parvenu? Une possibilité raisonnable est que ce n'était pas possible, car l'infini est contradictoire.

Bruno

Bonjour Christophe.

je pense que les axiomes de Peano, même eux, sont contradictoires, autrement dit qu'il existe une preuve de "tout" en les supposant.

Tu as sans doute énuméré plus haut les axiomes de Peano auxquels tu fait référence, mais pourrais-tu me rappeler :

Axiomes du premier ordre ou du second ordre ?

Axiomes avec dans le langage du successeur ou avec les lois de compostion ?

Merci

Bruno

christophe c

Bonjour Bruno,

Langage:

une constante $0$

un symbole fonctionnel unaire $S$

2 symboles fonctionnels binaires: $+;\times$

Axiomes:

Edit: $\forall x:x+0=x$ lol

$\forall x: S(x)\neq 0$

$\forall x\forall y: x+S(y)=S(x+y)$

$\forall x\forall y: x\times S(y)=(x\times y)+x$

pour chaque relation $R(a_1,...,a_n,x)$, l'axiome:

$\forall a_1\forall a_2...\forall a_n (R(a_1...a_n,0)\to (( \forall x: ((R(a_1..a_n,x))\to (R(a_1..a_n,S(x)))) )\to (\forall xR(x))))$

je poste et vérifie qu'il n'y a pas d'erreur de frappe, lol j'ai eu une indigestion de parenthèses...

christophe c

Précisions, il y a des phénomènes de robustesse: la théorie précédente, constitue un "jalon", mais par exemple, ZF(C) sans l'axiome de l'infini est le même jalon (même force, interprétabilité de l'une dans l'autre). Le "jalon suivant" est l'arithmétique de Péano du seconde ordre, même axiomes calculatoires, mais où, au lieu de "décréter" qu'il n'y a que des entiers dans le domaine, on se contente de définir que:

"$n$ est un entier" veut dire $\forall X: ([X(0); \forall u(X(u)\to X(S(u)))] \to X(n))$

christophe c

Pour les visiteurs peu familiers, je sais que ces axiomes ont l'air pauvres. Je montre comment on démarre pour avoir tous les théorèmes habituels.

Je ne le fais pas "cabalistiquement" pour adoucir, mais tout est traduisible...

Tout d'abord, je mettrai un lien vers un autre fil où on a déjà établi en papotant les uns et les autres, qu'on peut prouver par racurrence que $a=b$ ou $a\neq b$.

Donc pas besoin de faire d'utiliser le tiers exclus comme axiome, car c'est un théorème..

Pour montrer que le tiers exclus est valable pour toute phrase et non pas seulement pour les phrases sans quanteurs:

Exercices: de $A$ et $non(non(B))$ déduire $non(A\to $; supposant que $non(nonB)$ implique $B$, déduire que c'est encore vrai en remplaçant $B$ par $A\to B$.

Supposant qu'on sache prouver $nonnonR(u)\to R(u)$, déduire $(nonnon\forall xR(x))\to \forall xR(x)$

Ne travailler (en filigrane) qu'avec $\to$ et $\tout$ et considérer ($A$ et $B$) et ($A\vee B$) comme les abréviations habituelles. (En particulier, $nonA$ veut dire $A\to tout$

Preuve du tiers exclus à partir du schéma $(nonnonA)\to A$

Posant $T:=A$ ou $nonA$, et supposant $nonT$, on obtient $nonA$ ainsi que $nonnonA$, donc tout. Ainsi, on a bien nonnonT, et donc T.

Associativité de +:


Mettre en forme une récurrence qui exploite que:

si $a+(b+c)=(a+b)+c$ alors $a+(b+S(c))=a+S(b+c)=S(a+(b+c))=S((a+b)+c)=(a+b)+S(c)$

commutativité de +

Bruno

Merci Christophe.

Je digère un peu et peut-être aurais-je quelque chose à poster .

Bruno

christophe c

Ca me donne l'occasion de continuer, je m'étais arrêté au titre précédent, puis j'ai oublié de compléter.

succintement, on prouve d'abord par récurrence que $a+S(b)=S(a)+b$, (pour tout a,b) puis la commutativité vient de:

$S(a)+b=a+S(b)=S(a+b)=S(b+a)=b+S(a)$ qui l'établit pour $S(a)$ en la supposant pour $b$

Les associativités et commutativités de $\times$ sont dans la même veine et ce qui est intéressant est que la "pauvreté" des axiomes oblige à voir tout ce qui se passe

Le fait que tout entier non nul, a un prédecesseur provient d'une exploitation directe de la récurrence, avec ça de curieux que l'axiome de récurrence est utile sans que l'hypothèse de récurrence soit exploitée:

en effet, $S(n)$ est tel qu'il existe un entier $p$ avec $S(p)=S(n)$, ainsi, si c'est vrai pour $n$, qu'il existe $q$ avec $S(q)=n$ alors ... c'est vrai pour ...$S(n)$. De plus, $0$ est bien tel que "si $0\neq 0$ alors il existe p tel que $0=S(p)$", tout simplement parce que $0\neq 0$ entraine tout. Conclusion: pour tout n, si $n\neq 0$ alors il existe $p$ tel que $S(p)=n$

Je trouve ce mécanisme édifiant: on n'a pas besoin de l'hypothèse de récurrence pour l'étape d'itération, mais on a besoin de l'axiome de récurrence pour conclure.

christophe c

Retour sur un des posts (le 7ième ou 8ième au-dessus) où il est question de sexes (mariages des degrés de Turing).

Voici pourquoi il ne peut pas exister de mondes avec 3 sexes:

On s'intéresse à $E^3$, c'est à dire les triplets d'éléments de $E$, $E$ étant un ensemble quelconque.

Soit T l'ensemble des applications de $E$ dans $E$ et W celui des applications de $E^2$ dans $E$.

Etant donné un triplet $(a,f,g)$ de $E\times T\times W$ on appelle "enfant de ce triplet" l'élément $[a;f(a);g(a;f(a))]$ de $E^3$.

Le raisonnement qui suit a l'air d'utiliser l'axiome du choix, mais il est valable pour n'importe quel ensemble $E$ ayant au moins 2 éléments... Donc il ne l'utilise pas.

Le but est de montrer l'existence de 3 "rèves", cadire de 3 applications $A,B,C$ telles qu'aucun triplet $(a,f,g)$ n'est tel que chacun "réalise" les rèves des 2 autres, autrement dit:

1) $a=A(f,g)$

2) $f(a)=B(a,g)$

3) $g(a;f(a))=C(a,f)$

Dans la suite, (1) et (2) et (3) sera noté R(a,f,g).

Soit A l'application de $T\times W$ dans $E$ telle que si $R(A(f,g);f;g)$ alors $\forall x\in E: \ R(x;f;g)$

Soit $C$ une application de $E\times T$ dans $E$ telle qu'il n'existe aucune application $g\in W$ telle que pour tout $h\in T$ et pour tout $x\in E$: $g(x,h(x))=C(x;h)$. Une telle $C$ existe, il suffit de choisir $C$ de façon que $C(x;identite)\neq C(x;constante[x])$

Soit $L$ une application de $W$ dans $T$ qui à $g\in W$ associe un élément $h$ de $T$ tel que:

$non[\forall x\in E: \ g(x;h(x))=C(x;h)]$

On note alors $B$ l'application qui au couple $(x,g)$ associe $L(g)(x)$

Exercice: CQFD

---

Remarque: avec seulement 2 sexes, on n'a pas de contradiction, et on peut (à l'heure actuelle en tout cas) même aller très loin, puisqu'il existe des tas de généralisations de la "détermination des jeux".

Avec 3 sexes, l'hypothèse convenable est contradictoire, même sur un jeu de 3 coups en jouant des 0 et des 1.

---

Remarque importante: attention, ici, il ne s'agit pas de mettre en valeur le fait que certains jeux à 3 joueurs à informations parfaites ne sont pas déterminés car ce dernier point est trivial à cause des phénomènes de coalition. Là, l'impossibilité des 3 sexes établit en quelque sorte que même un fois enlevé (d'une manière très large en plus) l'obstruction des coalitions, il existe des jeux profondément non déterminés.

christophe c

Dans ce post, je rappelle le grisant axiome "AD" (axiome de déterminayion) qui entre en conflit avec l'axiome du choix, mais est plutôt jouissif...

Comme je l'ai déjà présenté autrement dans ce fil, je varie les plaisirs.

On note $T$ la réunion des ensemble $S_n$ pour $n\in \N$, en notant $S_n$ l'ensemble des suites de longueur $n$ dont les termes sont 0 ou 1.

Quand $s\in T$, et $x\in 2$, $s+x$ désigne la suite $s$ prolongé d'un terme de plus, qui vaut $x$.

----

Une partie $P$ de $T$ est dite une pairpréstratégie si elle a la propriété suivante:

Elle contient toutes les suites de longueur impaire

Pour toute suite $s$ de longueur impaire, il existe un $x\in 2$ telle que $s+x\in P$

----

Une partie $P$ de $T$ est dite une impairpréstratégie si elle a la propriété suivante:

Elle contient toutes les suites de longueur paire

Pour toute suite $s$ de longueur paire, il existe un $x\in 2$ telle que $s+x\in P$

----

On note $W$ l'ensemble des suites (infinies) de 0 et de 1

Soit $u$ un élément de $W$ et P un pair ou une impairpréstratégie

On dit que $u$ est acceptée par $P$ quand pour tout entier $n$: $u/n\in P$

En notant $u/n$ la restriction de $u$ aux $n$ premiers termes.

----

Axiome détermination (AD):

Pour toute partie $A$ de $W$, il existe des préstratégies $P,Q$ où $P$ est une pairepréstratégie, et $Q$ une impairpréstratégie et telles que:

l'ensemble des $u\in W$ acceptées par $P$ est inclus dans $A$

ou

l'ensemble des $u\in W$ acceptées par $Q$ est disjoint de $A$


----

Exercice: démontrer que AD implique nonAC et que AD entraine que tout ensemble de réels est Lebesgues mesurables

[réellement ? :S AD]

christophe c

Et oui... AD, tu es homonyme d'un des plus jolis axiomes du 20ième siècle. Il est tripant cet axiome...

Où se situe-t-il dans les "grands cardinaux"?

Depuis 1985, théorème de Martin Steel, on sait qu'il suffit qu'il existe un cardinal supercompact (voir quelques posts au-dessus) pour qu'il soit consistant.

Il entraine en 2 coups de cuillère que:

1) tous les ensembles sont mesurables

2) tout ensemble non dénombrable contient un fermé non dénombrable

3) Tout ensemble est ouvert à un ensemble maigre près

4) S'il y a une surjection de $\R$ sur un ordinal $a$ alors il y a une surjection sur l'ensemble des parties de $a$.

5) il existe un ultrafiltre non principal et stable par intersection dénombrable sur le premier ordinal non dénombrable, ainsi que sur le deuxième, etc

6) et des tas d'autres choses

---

Exercices:

Dans la définition du post ci-dessus, le fait que $W $ soit l'ensemble des suites de 0 et de 1 ne joue pas de rôle ensuite. On peut parler de l'ensemble des suites d'éléments de $E $

AD est donc l'énoncé $AD(2)$

Montrer l'équivalence entre $AD(\N)$ et $AD(2)$

Montrer l'inconsistance de $AD(\omega_1)$ (premier ordinal non dénombrable)

L'axiome $AD(\R)$ est encore plus fort que $AD$ et aussi consistant s'il y a un supercompact.

---

Une question (je ne connais pas la réponse): existe-t-il une relation de préordre sur $\R$ telle que le quotient $(E,< ) $ soit un ordre total, avec $E$ non dénombrable et $<$ total et toute partie de $E$ est bien dénombrable ou bien de complémentaire dénombrable??

christophe c

Variante: plutôt que parler de toutes les parties de $\R$ et renoncer à l'axiome du choix, on peut utiliser un autre axiome, ou plutôt schéma d'axiomes:

Pour une partie $A$ de $W$, on dit qu'elle est déterminée quand:

il existe des préstratégies $P,Q$ où $P$ est une pairepréstratégie, et $Q$ une impairpréstratégie et telles que:

l'ensemble des $u\in W$ acceptées par $P$ est inclus dans $A$

ou

l'ensemble des $u\in W$ acceptées par $Q$ est disjoint de $A$

Une variante compatible avec AC (modulo grands cardinaux) est le schéma d'axiomes suivant:

à chaque relation unaire sans paramètre, du langage de ZFC on regarde l'ensemble des $x\in W$ tels que $R(x)$. Et on affirme que qu'il est déterminé.

christophe c

Un archétype de jeu non déterminé avec AC:

V est un ultrafiltre sur $\N$

Les 2 joueurs jouent alternativement des entiers $>0$ formant une suite $u$.

On regarde $S_n:=u_1+...+u_n$ et $f(p):=$le premier $n$ tel que $S_n>p$

le joueur "impair" est déclaré gagnant ssi $V$ contient l'ensemble des $p$ tel que f(p) est impair.

---

Une conséquence amusante de AD (en fait du fait que tous les ensembles sont Lebesgues-mesurables:

Pour toute application $f$ de $\R$ dans les ordinaux, il existe un ordinal $\alpha$ tel que l'ensemble $E$ des $x\in R$ tels que $f(x)<\alpha$ est de mesure 1 et l'image de $E$ par $f$ est dénombrable.

Ca contraste avec le fait que AD entraine AUSSI qu'il y a des tas d'ultrafiltres sur $\omega _1$ qui sont non triviaux, tous étant pourtant sigma additifs et généralement image d'un filtre sur $\R$ par une fonction de domaine $\R$.

Le filtre en question contient alors toujours un ensemble négligeable. Ca donne une "vision" simple du fait qu'un réel aléatoire ne contient pas d'information.

Sylvain

Je ne sais pas si c'est le bon endroit pour poser ma question, toutes mes excuses si je pollue le fil. J'ai toujours entendu dire qu'on avait besoin de l'axiome du choix pour dire que tout espace vectoriel admet une base. Est-ce à dire que c'est l'existence de la base pour tout ev qui nécessite l'AC ou la preuve de cette existence qui le nécessite ? Si on n'autorise pas AC, l'existence d'une base pour tout ev peut-elle être vraie mais indémontrable ?
Merci de clarifier ce point car ça me semble important.

deufeufeu

Une base c'est une famille libre maximale, un coup de lemme de Zorn et hop.

Bruno

Je n'en suis plus très sûr, mais si on a $\neg AC$, il me semble que le lemme de Zorn est dans les décors non ?

Bruno

[La case LaTeX. AD]

deufeufeu

Il me semble qu'avec non AC, et donc non Zorn, on a un ensemble inductif sans élément maximal, et on doit pouvoir construire une espace vectoriel libre au dessus de celui-ci, de sorte que l'existence d'une base soit contradictoire. Bien entendu, l'ev en question doit être de dimension non-apprivoisable.

Bruno

Merci deufeufeu (et Alain).

Bruno

christophe c

à Sylvain, non bien sûr que tu ne pollues pas, je m'y sens même un peu seul parfois... -D, donc ravi d'avoir de la visite, le frigo est plein

Je n'ai pas compris ta question parfaitement: bien sûr, l'existence d'une base dans chaque ev est prouvée à l'aide de AC ou de Zorn qui est équivalent. Mais affirmer l'existence d'une base ne nécessite bien sûr aucune preuve, on peut affirmer ce qu'on veut.

Zorn et AC sont équivalents dans ZF fais-le comme exercice de le prouver, c'est vraiment rien du tout

Les familles libres de vecteurs d'un ev, ordonné par $\subeteq$, forment un ensemble inductif, et c'est un exercice de prouver qu'une famille libre maximale est une base.

Je ne connais pas officiellement la réponse à la question suivante, mais je crois me rappeler qu'elle est "oui", on peut le prouver:

Dans ZF: supposons que tout ev admet une base ALORS AC est vrai?.

Comme t'ont dit Bruno et deufeufeu, prenons un ensemble d'ensembles 2 à 2 disjoints, et "décrétons" que 2 éléments $x,y$ d'un même composant C, sont multiples l'un de l'autre, via la relation $(C,x,y)\times x=y$.

Il reste à faire des éléments formels $(C,x,y)$ des éléments d'un corps ce qui n'est pas bien méchant.

A priori une base commencera à donner, du moins, presque, un élément pas très loin de chaque composante $C$. Petit travail à faire et doute:

d'une manière générale, AC se décompose en la conjonction de 2 axiomes A, et B en eux-mêmes intéressants: l'axiome A suffit dans la plupart des situations actuellement fréquentes hors logique:


AxiomeA: $\forall E$ si $E$ est un ensemble d'ensembles 2 à 2 disjoints non vides alors il existe une partie $P$ de $E$ telle que l'intersection de $P$ avec chaque élément de $E$ est à la fois non vide et finie


AxiomeB: $\forall E$ si $E$ est un ensemble d'ensembles 2 à 2 disjoints FINIS et non vides alors il existe une partie $P$ de $E$ telle que l'intersection de $P$ avec chaque élément de $E$ est un singleton

Il est connu (je ne sais pas la preuve) que: ZF+B n'entraine pas A prouvablement.

Je ne sais pas si A entraine AC??? Je demanderai.

A et B entrainent bien sûr AC

B est connu comme étant "l'axiome de l'ultrafiltre" (c'est son nom, me semble-t-il)

Hélas, on peut regretter que ces questions ne sont plus étudiées, ayant laissées avec elles leur problème ouverts et pourtant en désuétude.

J'en signale un dont il m'a un peu énervé que ce ne soit plus étudié, bien qu'à ma connaissance, non résolu (ou non bcp diffusé):

Sans AC, peut-il exister un ensemble infini $E$ avec une surjection de $E^2$ sur $P(E)$?
Il est presque évident alors qu'une telle surjection ne peut être injective.

Personnellement, je trouve que l'axiome "A et nonAC" mériterait plus d'investigation (mais peut-être qu'il a été prouvé que A entraine AC sans que je le sache)

christophe c

Une remarque en passant: les aximes de ZF sont assez particuliers. Par exemple, ils affirment presque tel quel qu'il existe un ordinable non dénombrable, ou aussi, par exemple, d'un ordinal qu'on ne peut mettre en injection dans $\R $

Un certain nombre de théorèmes de maths sont prouvés avec ça.

En fait, c'est scientifiquement assez notable, car selon toute vraisemblance, tout ordinal est dénombrable si on veut vraiment parler du monde logico-réel (celui qui contient tout ce qui est possible dans notre monde ou un autre).

En effet, le système d'équations suivantes "a toujours une solution":

on prend des variables $x^e _ n$ indicées en haut par un ordinal dénombrable et en bas par un entier et on demande:

$non(x^e _n\vee x^f_n) $ pour chaque entier $n$ et 2 ordinaux dénombrable $e,f$ tels que $e\neq f$

disjonction$_{n\in \N} $ des $x^e_n$, pour chaque ordinal $e$ dénombrable

L'expression "a toujours une solution" voulant dire que le système n'est en une manière très forte, pas contradictoire***.

***Il existe une algèbre de Boole complète qui donne la valeur 1 à toutes les exigences (c'est expliqué un peu avant (page 3 ou 4) dans le présent fil.

christophe c

Précision: la convention veut que quand on parle de ZF, on n'inclut pas l'axiome de fondation qui dit que tout ensemble est bien fondé.

Toutes les maths sont en fait construites dans ZF + AF + ACdépendant (+ AC en option)

Je redonne donc une division de "ZF" (dans l'esprit, pas dans la forme) en grands groupes:

"Groupe ZF"

1) toute collection pas trop grande est un ensemble

2) 2 ensembles ayant les mêmes éléments appartiennent aux mêmes ensembles

3) Définition: "a=b" veut alors dire "a et b contiennent les mêmes éléments"


"Groupe fondation:"

4) un seul axiome: "tout ensemble est bien fondé"

"groupe choix":

Tous les axiomes du choix plus ou moins forts, plus ou moins équivalents qu'on peut trouver


"Groupe grands cardinaux"

Ce groupe est comparable au premier groupe, en ce qu'il affirme, pour diverses collections qu'elles sont des ensembles, par exemple, pour affirmer que qu'il y a un cardinal mesurable:

la collection des ensembles transitifs qui ne sont munissables d'aucun ultrafiltre non principal et sigma additif est un ensemble


"Groupe catalyseur" (lol c'est chauvin, car c'est le mien, mais je le mets quand-même car il sera développé dans les 50 ans qui viennent :P)

Ce sont des axiomes qui affirment pour différentes manières d'étendre l'univers (par forcing ou autrement) la chose suivante pour tout énoncé $P$

si on peut rendre vrai $P$ en élargissant l'univers et si, une fois rendu vrai, $P$ il reste vrai quand on continue d'élargir, alors $P$ est vrai d'avance.

"Groupe incompatible avec axiomes du choix"

Moult axiomes de régularité, par exemple que tous les ensembles de réels sont Baire ou encore mesurables, etc

L'axiome phare dans cette direction est l'axiome de détermination (AD)


En ce qui concerne l'axiome A d'un post précédent j'ignore si on peut prouver dans ZF tout court qu'il entraine AC, par contre:

exercice: A entraine que tout ensemble bien fondé peut être muni d'un bon ordre.