le forcing expliqué aux matheux ordinaires

Le barbu rasé

Voilà, c'est là.

Très jolie preuve de PB sur le fil de Greg. Il y a aussi une preuve de GG qui est encore plus agréable.

Alors évidemment, ça me tue l'exo, mais bon.

christophe c

Merci LBR: bin pour pas tuer l'exo je me retiens quelques temps de cliquer!

christophe c

Bon, j'ai triché, Anatole m'a exposé une idée très simple pour s'en apercevoir, lol donc je peux aller voir le lien now...

L'idée d'Anatole: soit $b$ une base de $\Z ^\N$. On jarte tous les éléments de $b$ qui serve dans au moins une décomposition sur $b$ d'une suite presque nulle. On n'en dégae qu'un nombre dénombrable. Il en reste tellement qu'on peut construire un sous-module avec le reste qui ne contient que des suites $u$ telles que pour tout $n\in \N$ et tout $p<n:u_n$ est un multiple de $p$

En poussant un peu, on parvient à fabriquer un sous-module qui est un $\Q$ espace vectoriel car on peut diviser n'importe lequel de ses éléments par n'importe quel entier.

Bon, now, je vais voir le lien.. -D

christophe c

oulala bon je lirai ça à tête reposée, vues les histoires de p-adiques et tout lol

Le barbu rasé

Non, regarde la preuve de GG : c'est exactement l'idée d'Anatole, non ?

Maintenant, en réexploitant cette idée, peux-tu torcher l'exo sans passer par le calcul du dual ?

christophe c

ok, je reregarde, mais faut pas trop que j'y reste car je me lève tôt demain pour aller dans mon lycée exotique.

christophe c

oui, ça y ressemble fortement, mais snif, c'est tout barré et encore moins détaillé que mon résumé (ya exploité comme un axiome l'idée qu'un quotient d'un module libre est libre entre autre, hum hum, c'est surement vrai dans certains cas (facteurs directs) mais me semble que vaut mieux tout préciser)

Bon là je peux pas trop m'attarder, mais oui, sinon ton exercice me semble bien à part et "en soi" un autre résultat peut-être bien plus difficile que juste "Z^N n'est pas libre".

Le barbu rasé

"Mon" exercice est extrait des Olympiades mathématiques d'Iran de 2002.

Pas si difficile, donc, du moins au niveau des outils nécessaires, mais avec finalement une idée intéressante.

christophe c

oulala je ne me rappelais pas avoir laissé ce fil plonger depuis si longtemps dans les profonfeurs du forum

Bon je reconnecte à un peu avant. La correspondance de Curry Howard offre des outils neufs pour attaquer la recherche d'une contradiction en mariant correctement ZFc avec AD (le c minuscule étant volontaire, j'expliquerai): en voici un excitant.

Soit $A_n$ des variables propositionnelles. L'énonce suivant est un théorème de logique propositionnelle classique:

En notant $B:=A_0\wedge (A_1\to A_2)\wedge ((A_1\wedge A_3)\to A_4)...$

et $C:=(A_0\to A_1)\wedge ((A_0\wedge A_2)\to A_3)...$,

On a que $B\vee C$ est un théorème.

Or le "profil" de ce théorème, si maintenant on imagine les $A_i$ comme des ensembles, est d'affirmer l'existance d'une stratégie canonique pour un des 2 joueurs dans les jeux décrits aux posts précédents. Comme on utilise le RPA, c'est plutôt l'implication pour chaque jeu d'une stratégie canonique associée, calculable par un ordinateur dont les mémoires sont indicées par les ordinaux.

christophe c

Pourquoi le "c" minuscule" est volontaire? Et bien parce que l'axiome du choix (général) est réputé ne pas pouvoir s'exprimer par un axiome de compréhension.

Or:, en notant "$T_E$" la collection des ordinaux $a$ tels qu'il n'existe pas d'injection de $E$ dans $a$, le fait que pour chaque $E$ la collection $T_E$ soit un ensemble entraine (et est équivalent) à l'axiome du choix. On peut donc "réaliser" AC par le terme "identité" à la manière dont JLKrivine réalise les autres axiomes.

En résumé, contrairement à ce que l'histoire a laissé croire, ce n'est pas l'axiome du choix qui pose problème. Il s'ensuit donc que c'est du côté de AD que doivent se porter les efforts de réalisation.

christophe c

Histoire d'illustrer ça concrêtement , je mets ces idées à l'épreuve de camL..

A l'exception de "ii" (en rouge dans le code) dans le code suivant, tout est parfaitement défini, et se compile très bien (y compris ii, mais il fait appel à un oracle)

Bon lol désolé pour le gros fumage de moquette de première qualité, mais d'un autre côté, ça permet aux gens d'étudier récréativement le camL de voir comment on retrouve les pires infinis (et surtout la pire extensonnalité) en boite de conserve dans des fils d'ordinateurs:

(je suis allé jusqu'à la notion de cardinal, après un piti peu fatigué...)

type ens = L of (ens->bool)

type form = Ato of ens*ens | I of form*form | Foral of ens*form

exception T of (ens->bool)

let ii x=raise(T x)

let ii x=let s=read_line() in if s="!" then true else false

let ap x y=match y with
|L f->f x

let diagonalcantordangereuxnepasutiliser = let g z=if ap z z then false else true in L g

let inclus a b=let g x=if ap x a then ap x b else true in ii g

let egal a b=if inclus a b then inclus b a else false

let rec rpl x y f=match f with

|Ato(u,v)->if egal u v then if egal x u then Ato(y,y) else f else if egal x u then Ato(y,v) else if egal x v then Ato(u,y) else f
|I(h,c)->I(rpl x y h,rpl x y c)
|Foral (a,suite)->if egal x a then f else Foral (a, rpl x y suite)

let rec verite f=match f with
|Ato(u,v)->ap u v
|I(h,c)->if verite h then verite c else true
|Foral (x,p)->let g z=verite (rpl x z p) in ii g

let classeensembledesxtelsquef a f = let g z=verite (rpl a z f) in L g

let paire a b=let g z=if egal z a then true else egal z b in L g

let vide = let g z=false in L g

let sing a=paire a a

let parties a=let g z=inclus z a in L g

let couple a b=paire (sing a) (paire a b)

let suc a=let g z = if ap z a then true else egal z a in L g

let inductif a = let g z=if ap z a then ap (suc z) a else true in if ap vide a then ii g else false

let entier n = let g z=if inductif z then ap n z else true in ii g

let grandN= L entier

let grandR= parties grandN

let un=suc vide

let deux = suc un

let minimum m a=let g z=if ap z a then if ap m z then true else if egal z m then true else false else true in ii g

let existe test a = let g z=if ap z a then if test z then false else true else true in if ii g then false else true

let admetmin a = let test x= minimum x a in existe test a

let transitif a=let g z=if ap z a then inclus z a else true in ii g

let isnonvide a=if egal a vide then false else true

let no b=if b then false else true

let ordinal e = if no (transitif e) then false else
let g t=if isnonvide t then if inclus t e then admetmin t else true else true in ii g

let iscouple a=let h u v=no (egal a (couple u v)) in let g u=ii (h u) in no (ii g)

let exis test = let g z=no (test z) in if ii g then false else true

let premier a=if iscouple a then
let g y= let h u = let k v = if egal a (couple u v) then ap y u else false in exis k in exis h in [L g]
else []

let deuxieme a=if iscouple a then
let g y=let h u = let k v = if egal a (couple u v) then ap y v else false in exis k in exis h in [L g]
else []

let necontientquedescouples f=let g z = if ap z f then iscouple z else true in ii g

let isfonction f = if necontientquedescouples f then
let h a=let k b= let m c=if ap (couple a b) f then if ap (couple a c) f then if egal b c then true else false else true else true in ii m in ii k in ii h
else false

let domaine f = let g z = let h t = ap (couple z t) f in exis h in L g

let image f = let g z = let h t = ap (couple t z) f in exis h in L g

let inverse a=if no (iscouple a) then a else
match (premier a,deuxieme a) with
|([p1],[p2])->couple p2 p1

let sym f=let g t=ap (inverse t) f in L g

let bijection u v = let h f=let f2=sym f in
if isfonction f then
if isfonction f2 then
if domaine f=u then
if domaine f2=v then true
else false
else false
else false
else false in exis h

let trobig e z=if ordinal z then let k p=if inclus p z then if bijection e p then true else false else false in exis k else false

let cardinal e = let g t= let h z=if trobig e z then ap t z else true in ii h in L g

christophe c

Voilà ce que dit le compilateur (il est quand-même zentil):


type ens = L of (ens -> bool)
type form = Ato of ens * ens | I of form * form | Foral of ens * form
exception T of (ens -> bool)
val ii : (ens -> bool) -> 'a = <fun>
val ap : ens -> ens -> bool = <fun>
val diagonalcantordangereuxnepasutiliser : ens = L <fun>
val inclus : ens -> ens -> 'a = <fun>
val egal : ens -> ens -> bool = <fun>
val rpl : ens -> ens -> form -> form = <fun>
val verite : form -> bool = <fun>
val classeensembledesxtelsquef : ens -> form -> ens = <fun>
val paire : ens -> ens -> ens = <fun>
val vide : ens = L <fun>
val sing : ens -> ens = <fun>
val parties : ens -> ens = <fun>
val couple : ens -> ens -> ens = <fun>
val suc : ens -> ens = <fun>
val inductif : ens -> bool = <fun>
val entier : ens -> 'a = <fun>
val grandN : ens = L <fun>
val grandR : ens = L <fun>
val un : ens = L <fun>
val deux : ens = L <fun>
val minimum : ens -> ens -> 'a = <fun>
val existe : (ens -> bool) -> ens -> bool = <fun>
val admetmin : ens -> bool = <fun>
val transitif : ens -> 'a = <fun>
val isnonvide : ens -> bool = <fun>
val no : bool -> bool = <fun>
val ordinal : ens -> bool = <fun>
val iscouple : ens -> 'a = <fun>
val exis : (ens -> bool) -> bool = <fun>
val premier : ens -> ens list = <fun>
val deuxieme : ens -> ens list = <fun>
val necontientquedescouples : ens -> 'a = <fun>
val isfonction : ens -> bool = <fun>
val domaine : ens -> ens = <fun>
val image : ens -> ens = <fun>
File "C:/Documents and Settings/logane/Mes documents/thofset.ml", line 93, characters 0-61:
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
([], _)
val inverse : ens -> ens = <fun>
val sym : ens -> ens = <fun>
val bijection : ens -> ens -> bool = <fun>
val trobig : ens -> ens -> bool = <fun>
val cardinal : ens -> ens = <fun>

christophe c

En modifiant la ligne définissant "ii" comme suit:

let ii x=let s=read_line() in if s="!" then true else false

on obtient un programme vraiment exécutable, et on est "chargé" de donner les bonnes réponses X:-(

(je modifie dans le code initial)

christophe c

Je continue ici des idées commencées dans le fil suivant:
http://www.les-mathematiques.net/phorum/read.php?4,562105,565151#msg-565151
pour ne pas le polluer avec du hors-sujet.

Pour expliciter ce que je disais sur "l'identité = puissance", voici les détails:

en LC, a.f est ce que classiquement on entend par $f^a$. D'où on peut considérer que Identité: $(x,y)\mapsto y^x$, car en LC:

$I.x.y==x.y=="y^x"$ et $(a+b).f.x=a.f(b.f.x)$ (c'est une définition, en maths y a du grabuge pour arriver à prouver $f ^{(a+b)} (x)=f^a(f^b(x))$)

Sur le plan "théorie de la démonstration", la retournement de l'identité, ie "Pui" tel que Pui.x.y:=y.x réalise les énoncés de la forme:

$A\to ((A\to \to $

C'est marrant, dans le cas particulier $B:=tout$, ça donne la réciproque de l'axiome du raisonnement par l'absurde, et d'une manière générale, c'est un truc très utile qui permet de faire commuter les hypothèses si on ne dispose pas d'un axiome tout fait qui le permet.

En LC ça donne: Permut a u v = a v u qui réalise [(H1->(H2->C))]->[(H2->(H1->C))]

Pour obtenir Permut, on mélange "Pui" (puissance) et "×" multiplication comme suit: (je note par un P majuscule puissance et par C la multiplication (composition de fonctions)

a v u = P u (a v) =C (P u) a v = P a ( CCPu ) v = P a ( t u ) v = C ( P a) t u v = CCP a t u v = P t (CCP a) u v = C (P t) ( CCP) a u v

On obtient donc un Permut possible par : × ( Pui ( × × Pui ) ) ( × × Pui)

Si on note Z la fonction multiplication o Puissance, le permutateur obtenu est:

Y o Z

avec $Y:x\mapsto Z^x$

je ne sais pas trop ce que ça peut signfier, certes, mais bon...

christophe c

Je pense à un truc tout d'un coup.

Le lien suivant:
http://www.les-mathematiques.net/phorum/read.php?16,565698,page=1

me fait penser à vous signaler que Paul Cohen, l'inventeur du forcing, après sa découverte (solitaire d'ailleurs, je crois, c'est assez incroyable quand on voit ce qu'est le forcing) a, d'après ce que m'ont dit une fois dans un car à Luminy des gens qui le connaissaient, continué ses recherches de manière plutôt peu en collaboration avec les "forcingueurs" qui ont suivi.

En effet, il a tout de suite flairé un lien entre les théorèmes de complétude, une sorte (qui n'existait pas à l'époque) de
correspondance de Curry Howard, enfin je suppose que c'était ça qui pouvait l'emmener là,
et a cherché à découvrir ce qu'on appellerait "le epsilon zero" de ZF.

Le "epsilon zero" de Peano, c'est le premier ordinal infini qui contient omega et qui est stable par "puissance ordinale" et
on peut quand-même assez bien se le représenter sans mal de crane. Il permet de "déplier" (ie d'éliminer les coupures**)
de toute preuve arithmétique (enfin c'est pas lui qui permet, simplement "ya la place sous lui" de le faire) afin d'obtenir une preuve
"sans axiome"*** mais plus longue (justement, d'une longueur inférieure à epsilon0)

*** enfin on garde que la fonction successeur est injective et que 0 n'a pas de prédecesseur

** les coupures des preuves, on peut les comparer à une option facilitante dans un jeu, qui correspondrait à donner le droit à chacun
des joueurs, de dire "je rajoute tel ensemble A de positions finales où on dit que j'ai gagné" et l'autre doit répondre:

ou bien "ok" (et les positions dans A deviennent des fins de parties gagnées pour son adversaire)
ou bien "non" (et il doit alors choisir une position de A comme nouvelle position du jeu)

En arithmétique, typiquement, l'axiome de récurrence est un "gain de temps", mais si on ajoute la règle "infinitiste" (dans le prouveur -sceptique)
"j'en suis à vouloir te prouver $\forall xR(x)$; propose-moi***** un entier $n$ et je vais te prouver $R(n)$", bien évidemment, l'axiome de récurrence devient un théorème et n'a plus besoin d'être ajouté comme axiome.

***** un vrai entier, sous la forme 1+1+1+1+1+1+1+1+1, par exemple

christophe c

Une digression à propos de "probabilités", puisqu'elles sont en vogue. J'oublie chaque fois de le signaler, bon et bien comme ça, c'est fait:

AD implique qu'il n'y a pas de mesure simplement additive (ie pas sigma additive of course) "diffuse" sur $\N$.

Je laisse le preuve en exercice, elle est assez naturelle: à tout de rôle les 2 joueurs ramassent des ensembles finis d'entiers, parmi ceux non encore ramassés à un stade antérieur de la partie. A la fin de la partie, ils ont chacun leur ensemble d'entier (les 2 ensembles sont disjoints), et on regarde lequel a réussi à faire le plus gros avec la convention par exemple que s'ils ont la même mesure, c'est le joueur1 qui gagne.

Quelques pirouettes avec ces idées et on obtient facilement une contradiction (si on admet que pour tous les jeux précédents, l'un des joueurs a une stratégie infaillible).


Rien à voir: comme je l'ai déjà dit moult fois (c'est un peu mon dada, y compris dans "Boubaki21"), c'est une mauvaise approche que de voir les maths de l'infini en termes classiques. Cela ne veut pas dire qu'il ne faut pas être platonicien, mais qu'on dispose e la correspondance de Curry Howard et de tout pleins d'outils qui gomment la frontière entre le contradictoire et le consistant et rend sans "objet" la compulsion***** voulant "aller toujours plus haut jusqu'à atteindre la "limite" de la consistance", en tout cas d'y aller "sémantiquement".

Je resignale donc des points intéressants et "contradictoires" donc tombés aux oubliettes de la recherche ensembliste alors que les preuves des contradictions concernées sont en soi des "nonpreuves"*** et mériteraient d'être creusées au maximum.

*** Elles ne se "normalisent pas" en un sens respectables, autrement dit, elles donnent bien de bons programmes "à partir de rien ou presque" qui mènent au paradis "sans hypothèse", sauf qu'il "bouclent". C'est une situation différente des preuves de "tout" qui font des hypothèses gratuites (les théorèmes habituels des maths qui déduisent une contradiction d'hypothèses dont on veut prouver la fausseté)


premier point: "intuitivement", ça a un sens presque concret de tirer un réel au hasard (une suite de 0 et de 1 je veux dire). En particulier, ça a un sens (à peu près le même) de tirer une suite de réels au hasard. (Rappel: la preuve que AD implique que tout ensemble de réels(**) est Lebesgues mesurable permet de soutenir "visuellement" cette intuition). Habituellement (en tout cas dans la médiatisation de l'exercice suivant), on utilise Fubini pour mettre en conflit un bon ordre sur $\R$ avec (**). Cela me parait assez désolant de n'avoir que cet angle car Fubini est une intuition (les axiomes utilisés pour le prouver) trop matérielle (ie trop géométrique) et à priori non dénué d'un recours à la sigma additivité.

Voici une approche alternative beaucoup plus pure dont le recours à la sigma additivité n'est pas aussi constitutif de la compréhension du problème. D'ailleurs je ne fais pas allusion à la mesure de Lebesgues, mais à une intuition sur "la probabilité que", proche du paradoxe de Banch Tarski, mais sans la fragilité liée à la dépendance à l'intuition physique (qui entre en conflit avec le Th de BT et lui donne son caractère paradoxal)

Soit $\leq$ un bon ordre sur $\R:=$ l'ensemble des suites de 0 et de 1 pour simplifier.

On tire au sort une suite $u$ d'élément de $\R$. On s'intéresse aux probabilités suivantes:

(1) que $min_n (u_{2n} ) = min_n (u_{2n+1} )$

(2) que $min_n (u_{2n} ) > min_n (u_{2n+1} )$

En admettant quelques axiomes vox populi très simples, on obtient que proba (1) = 1, ce qui constitue un paradoxe.

Maintenant, on pourrait se demander l'intérêt de tout ça (c'est du remaché). En fait, c'est intéressant dans la mesure où on relit mon objection à ***** ci-dessus.

Il existe en quelque sorte "virtuellement" un "bon ordre" sur $\R$ (certes assez peu accessible à l'univers de ZF(C) dans lequel on se trouve), mais paradoxalement bien plus concret.

En effet, la recherche d'un modèle bien fondé de V=L qui contient un réel $x$ suffit si le trouve à attribuer "injectivement" un ordinal à $x$.

Autrement dit dans chaque univers bien fondé de ZF, il existe une application partielle, mais importante $T$ de $\R$ dans $On$ qui est injective.
De plus, face à un réel $x$ la recherche de ce $T(x)$ est récursive en un sens vraiment honnête, ie, je mettrai le petit programme (théorique) P caml qui monte monte le long de la colonne vertébrale ordinal de l'univers jusqu'à trouver $T(x)$,
le réel x étant donné au programme comme une fonction de type entier->bool (où entier est un type construit pour éviter les limites de mémoire.


Le pas à sauter est le suivant. S'entêter, face à un réel $x$ à ne pas interrompre le programme qui cherche $T(x)$. C'est ce pas que la tradition de la recherche a loupé, (ie elle a oublié de le sauter). (Pour n'importe quel ensembliste professionnel, l'ensemble des réels constructibles (ie ceux pour lesquels T(x) existe) est dénombrables "in the real world", et ils considèrent quasiment ce point comme un axiome légitime à rajouter à ZF(C) )

Une fois sauté ce pas, il existe une activité qui "mène au paradis" qui est la suivante. Le programme P bien entendu n'a pas besoin de connaitre tous les digits de $x$ d'un coup, il se contente de les appeler au fur et à mesure. On obtient donc une contradiction "sans hypothèses" ie une preuve de "tout" en tirant au sort les digit au fur et à mesure que P les demande.

Ce dernier point n'est pas vraiment formalisable dans ZF (en dehors de l'expédiation que AC construit des ensembles Lebesgues non mesurables par exemple) , mais est "concret" en ce qu'il construit un vrai programme qui mène au paradis à la condition toutefois de disposer d'assez de temps et de mémoire pour le laisser s'exécuter jusqu'à "la fin".

On a pas mal de variations sur ce thème, je les décrirai, mais à ma connaissance, seules ces activités mènent réellement à "Tout" au bout d'un "vrai" temps et d'un "vrai" parcours, même s'il est "infini".

christophe c

Remarque: j'ai déjà "raconté ma vie" dans d'autres fils, mais je redis (pour les maths, pas pour mes mémoires) que c'est en considérante le "théorème naif" disant que proba du (1) = 1 du post ci-dessus que j'ai inventé les ultrafiltres**. Après quoi leur considération m'avait détourné du problème initial qui pourtant est peut-être finalement plus juteux.

** considérer l'ensemble $W$ des parties $X$ de $\R$ (mais en fait on peut prendre n'importe quel ensemble E) tel que:

"probabilité que $min _ n (u_n) \in X$ = 1"

$W$ est forcément un ultrafiltre, modulo les mêmes axiomes vox populi naifs invoqués au post ci-dessus. De plus, il apparait "canoniquement associé" à "la mesure" (qu'on ne définit pas) vérifiant les axiomes vox populi en question (en fait, c'est con, on peut prouver qu'il n'existe pas de telle mesure ). Cependant, pour ce faire, on utilise plus de matériel (interne à l'univers) que pour juste pour obtenir W.

Par ailleurs, à priori, il ne s'agit pas de "n'importe quel" ultrafiltre. Il n'y a pas de raison que tous les ultrafiltres puissent "s'obtenir ainsi".

christophe c

Lien de ces 2 derniers posts avec le forcing

En considérant le préordre Y des boréliens de mesure non nulle, on obtient un "random réel" (ie les "réels génériques" (donc extérieurs à l'univers) pour ce préordre sont des "random réels")

C'est un "réel r" (intuitivement, car il ne peut pas être dans l'univers) tel que pour toute partie dense D de Y, il existe un borélien B de Y tel que $r$ "mérite" d'appartenir à B. (Il ne peut évidemment pas lui appartenir, vu qu'il n'est pas dans l'univers, mais "ses digits" attestent qu'il "est dedans") (rappel: un borélien, au delà de l'ensemble qu'il est est un "code" qui dit quels réels, y compris ceux de l'extérieur, méritent de lui appartenir)

J'en ai déjà parlé dans les premières pages de ce fil.

Par contre, un truc que j'ai passé sous silence, c'est le développement du rappel précédent dans cet exemple particulier de forcing.

Je comble ce retard avec une petite description d'un truc marrant qui associe une "mesure" à TOUS les "codes d'ensembles de réels".

Pour simplifier, on considère l'intervalle $J:=[0;1]$.

Les briques élémentaires sont les couples de rationnels $(r,s)$. On les considère comme des noms d'ensembles, précisément $(r,s)$ est le nom de l'intervalle $[r,s]$

On clit l'ensemble des "noms" par réunions quelconques et complémentaire.

Evidemment si on attachait à ces noms le vrai ensemble de réels qui lui correspond, on obtiendrait toutes les parties de $J$, et avec AC, on sait bien que certaines ne sont pas mesurables.

En quoi nous aide le forcing pour "comprendre" ce qu'on va faire maintenant?

christophe c

L'ensembles (ou plutôt la collection) Name des noms est donc la plus petite collection stable par "disjonction" et "non" et qui contient les couples de rationnels.

Prenons un nom R. Dans une extension générique VG qui collapse au dénombrable suffisamment de cardinaux (ie qui rajoute des surjections de $\N$ sur un assez gros ensemble), R est alors vu comme un code de vrai borélien. Il a donc une "mesure de Lebesgues" dans cette extension.

Le point excitant, c'est qu'en tant que "nom", R est un élément de l'univers de départ. S'il est de la forme "non(S)", inductivement, si on a attaché un réel (sensé représenter sa mesure), ie un réel m de l'univers de départ m à S, on peut attacher 1-m comme mesure "du nom R"

Supposons maintenant que R est une disjonction (ie le nom d'une réunion) $Disj_{i\in I} (S_i)$. Vu dans VG, il s'agit d'une disjonction dénombrable (même si vu dans l'univers V de départ, $I$ n'est pas dénombrable.

Admettons qu'on ait attaché à chaque réunion finie $Disj_{i\in F} S_i$ une mesure $m_F$ de manière que $F\mapsto m_F$ soit une application de $P_{fin}(I)$ dans $J$ qui est dans l'univers V de départ. Et bien, il n'est pas difficile d'obtenir "la mesure de R". C'est la borne sup des $m_F$, quand $F$ parcourt $P_{fin}(I)$ et c'est un réel qui lui aussi est dans l'univers de départ.

Il n'y a aucune obstruction (sauf celle de calculer les $m_F$ à partir des $m_{i}$ supposés donnés par récurence ordinale.

On vient ainsi d'attacher un nombre réel compris entre 0 et 1 à chaque nom et le tout a été fait dans l'univers de départ.

Il parait peu probable qu'on y aurait pensé sans l'intuition du forcing.

christophe c

Pour ceux qui sont à chevaleret, je signale une conférence de H.Woodin sur ces thèmes de "comment est fait le "real world"" des ensembles, dans 1H, à 17H.

Je crois qu'il va parler (d'après le message reçu) de comment étendre l'idée de L à des univers contenant des grands cardinaux et de pourquoi, jusqu'à récemment, on coryait ce programme voué à l'échec et que finalement, c'est de la bonne. Enfin, tout ceci étant dit si mon "anglais" n'est pas trop mauvais, (or l'hypothèse de la phrase précédente étant fausse...)

Je rappelle que L est la collection des ensembles obtenus de la manière suivante:

On part de l'ensemble vide.

Si a est n ordinal limite, $L_a$ est la réunion des $L_b$, quand $b$ précède $a$.

Si a=b+1, $L_a$ est $L_b$ union l'ensemble des parties définissables de $L_b$ avec des $\forall;\to;\in$ et des éléments de $L_b$.

La réunion de tous les $L_a$ est un modèle "canonique" de ZFC qui vérifie HC, l'axiome du choix et plein d'autres trucs et qui est le plus petit modèle transitif non collectivisant de ZF. De plus dès qu'on fait le moindre petit forcing, évidemment, comme le L de l'extension ne change pas, l'extension générique pense qu'il y a des ensembles qui ne sont pas dans $L$.

L'axiome désigné par le sigle $V=L$ dit que tout ensemble est dans L.

J'ai longtemps été "ennemi" (comme tout ensembliste moutonnier) de cet axiome.

En fait, depuis plusieurs années, au contraire, je le considère comme vraiment "vrai" (position archi ultraminoritaire) et excitant. Je raconterai en détails (je crois que je l'ai déjà fait d'ailleurs).

christophe c

Je résume d'une manière vraiment drastique pour les gens que ça intéresse, le contenu de l'exposé de H.Woodin de mercredi.

En faisant une recherche sur "grands cardinaux", vous devez pouvoir tomber sur des fils où j'ai donné la liste des axiomes actuels. Le plus important et canonique (mais pas le plus fort) étant "il existe un ensemble E et un ultrafiltre non principal W sigma additif sur E" (1).

L'axiome (1) entraine qu'il existe des ensemble non constructible, ie que $V\neq L$ (voir posts ci-dessus pour une définition de L.

Malgré ça il existe une manière "canonique" de "récupérer" une sorte de L, qui est essentiellement "L(W)", avec le W du (1). Ca a un intérêt car il y a un ancien mais subtil théorème qui dit que le L(W) ne dépend pas du W, mais seulement de l'ordinal auquel il oeuvre.

Hélas pour les "vrais durs" que sont le gros axiomes de grands cardinaux, il n'y a pas de technique pareille. Or H.Woodin prétend avoir finalement récemment (c'est plus que récent, c'est presque "à venir") trouvé un moyen de le faire.

Le résultat clé serait qui s'il parvient à le faire pour un cardinal "supercompact", le "superL" récupéré mange de manière gloutonne tous les autres "L(tel ou tel cardinal magique)" et donc qu'on ne perd plus rien à le faire (et même on gagne beaucoup, puisqu'on se retrouve avec un "univers" entièrement éclairé (c'est lintérêt de L, savoir ce qui est vrai et ce qui est faux).

Un des corollaires de ça sera que le problème ouvert crucial ***(sansAC) sera résolu de manière négative, ie une certaine borne ultime, pour l'instant encore considérée comme consistante car personne n'a trouvé de preuves que non, sera finalement trouvée contradictoire.

J'ai déjà donné la preuve, dans ce fil même que ***(avecAC) est contradictoire, résultat généralement appelé "borne de Kunen".

*** il existe un plongement élémentaire de V dans V qui n'est pas l'identité sur les ordinaux. L'abréviation "V" signifiant qu'on met dans les axiomes que les collections définies en utilisant le prédicat "j"
forment des ensembles selon le même protocole que ZF le demande pour les collections habituelles.

Une autre manière de le présenter est de dire: il existe un ensemble inaccessible E et un plongement j de E dans E qui est élémentaire qui ne fixe pas tous les ordinaux. "élémentaire" veut dire $R(a,b,c...)\iff R(j(a),j(b),...)$ pour toute R close écrite avec $\forall ; \in ; \to$

En présence de l'axiome de choix, c'est démontrablement faux (voir autres posts où j'ai donné une preuve)

Le rôle du forcing la dedans est le suivant:

depuis une trentaine d'années s'est développée une théorie maintenant bien comprise de comment les grands cardinaux "fixent" la valeur de vérité des énoncés "importants". Par exemple, s'il y a assez de grands cardinaux, AD est vrai dans $L[\R]$ qui lui-même est un univers vérifiant tous les axiomes de ZF. Ainsi, quand on utilise AD en maths (et il est plus que fructueux cet axiome), on prouve légitimement des "bonnes choses" dans $L[\R]$ qui est un "vrai" modèle respectable pour comprendre le monde.

christophe c

Ah, et j'oubliais la rubrique "voici paris".

Ca en amusera certains de savoir que H.Woodin a changé d'avis concernant HC. Autrement dit, maintenant "il y croit". Ainsi, le pdf qui a pas mal circulé ici même que P.Dehornoy avait écrit à la suite des travaux de synthèse de HW devient "périmé" en tant que présentation de l'opinion de HW.

La raison en est la suivante: dans le "superL" que HW annonce, ie le L qu'on pourrait appeler "L (du premier supercompact)", HC est vraie.


J'en profite pour résumer ce que j'ai dit au post d'avant concernant mon attachement à "V=L" (axiome qui entraine l'inexistence "platonicienne" des grands cardinaux et donc rejet par les ensemblistes.

Certes, c'est un attachement en 2 tps, mais en fait face à un objet non constructible (non dans L), il existe un programme "simple", presque récursif qui définit comment "chercher plus haut que l'univers" un ordinal qui construit x.

Il y a un lemme qui garantit la sécurité de ce programme, appelé "Lemme de d'absoluité de Shoenfield", qui n'est pas très difficile à comprendre.

Bien entendu, cette direction est orthogonale à la démarche ensembliste usuelle et n'est pas développée par les "génies" que sont les ensemblistes, hélas, et qui travaillent un peu en comité clos, c'est dommage (il faut dire que le autres ne les accueillent pas toujours gentiment).

HW m'a dit que les tenants de cette direction (tenants "philosophiques, puisque personne n'y travaille) s'appelaient "beta logique" et se résumait sous le sigle "V=L (omega1)". En résumé, tout est "in fine" dénombrable.

L'explication de ça vient de ce que si on applique la recherche de l'ordinal qui construit tel x, et qu'on ne fait rien d'autre avant de l'avoir trouvé (ie on ne peut appuyer syr "control C", alors une fois trouvé, cet ordinal rend tout l'ancien univers dénombrable et du coup, il est difficile de "distinguer" les montagnes "hautes" des basses". J

Cependant dès lors qu'on est à la recherche "du real world", on ne peut négliger que les dits programmes s'arrêtent systématiquement (ie ne bouclent jamais) et donc il est invalide de prétendre que "c'est un tort" de ne pas appuyer sur "control C". S'agissant de "la pratique", bien sûr c'est autre chose.

La Mec.quantique justifie de ne pas trop platoniser V. Les grands cardinaux restent bien sûr certes le sommet des maths, mais il est dommage que ne poussent pas quelques branches de recherches qui en tirent des corollaires pratiques. Jeme pose sincèrement une question: Au fond, des gens comme HW et bcp d'ensemblistes ne sont pas entrain d'exécuter le programme "V=L(omega1) sans le savoir en y mettant des décorations "affectives" à chaque virage. Auquel cas on ne pourrait pas considérer leur avancée comme s'inscrivant en désaccord avec le fait que "in fine tout est dénombrable", mais simplement comme s'inscrivant en tant qu'humains investis cérébralement dans l'exécution du programme.

Je rappelle que le mieux pour comprendre tout ça, enfin pour ceux que ça intéresse est de relire les preuves des contradictions dans les théories suivantes:

ZF+ AC +AD

ZFC + il existe un mesurable + il existe un jeu analytique non déterminé.

Un jeu analytique est un jeu où l'arbitre décide qui a gagné à la fin en appliquant la fonction caractéristique de la projection d'une application continue de $\N^\N$ (muni de la topproduit de la discrete) dans $2 ^\N$. (Les joueurs jouent alternativement des 0 et des 1 jusqu'à former une suite qui est un élément de $2^\N$)

Je rappelle que c'est un théorème (de Martin) très amusant que tous les jeux boréliens sont déterminés.

christophe c

L'existence d'un plongement élémentaire de V dans V (incompatible avec l'axiome du choix) est un problème ouvert connu depuis longtemps, mais qui apparaissait une anecdote jusqu'à ce que HW annonce*** que c'était actuellement l'ultime borne (dont il conjecture l'inconsistance***) avant l'axiome 0=1. HW déclare avoir prouvé qu'il entraine la consistance de tous les autres axiomes de grands cardinaux de manière uniforme. D'où les 2 ***.

Je le décris donc en détail sous forme accessible aux "peu" logiciens, pour qu'ls puissent éventuellement tenter de l'attaquer. Je rappelle qu'on n'a pas l'axiome du choix sinon c'est "presque trivial" que l'énoncé qui suit est contradictoire.

Il existe un ensemble E, et un ultrafiltre W sur T, en notant T l'ensemble des parties de E demême cardinal que E, ayant les propriétés suivantes:

1) W est sigma additif (stable par intersection dénombrable) et non principal

2) Pour tout $x\in E$, l'ensemble $A_x$ des parties $P$ de $E$ qui telles que $x\in P$ est dans W

3) Pour toute relation binaire $R\subseteq T\times E$, si l'ensemble $B_R$ des parties $P$ de $E$ telles que $\exists x\in P: (P,x)\in R$ est dans W alors il existe un élément $a\in E$ tel que l'ensemble des parties $P$ de $E$ tel que $a\in P$ et $(P,a) \in R$ est dans W.

L'existence de (E,W) est un objet "ultime" que l'on peut considérer comme l'axiome "divin" actuellement à "abattre". Il entraine "trop facilement" plein de choses pour être cru consistant, mais il semble qu'une preuve de l'inexistence de (E,W) ne soit pas connue pour l'instant.

Rappels: un ultrafiltre U sur X est un ensemble de parties de X tel que pour toute parties A,B de X:

1) si $A\in U$ et $A\subseteq B$ alors $B\in U$

2) $\emptyset \notin U$

3) si $A$ et $B$ sont dans $U$ alors $A\cap B$ est dans U

4) Si $A\notin U$ alors $E\setminus A$ est dans U.

Intuitivement, U est "une carte d'identité" d'un élément virtuel (ou réel ) de $E$. L'exemple typique (les carte d'identité d'éléments réels) d'ultrafiltre étant $U_b:=\{A\in P(E) / b\in A\}$

zephir

Bonjour Christophe,

J'aurais deux questions sur ce que tu racontes et que je trouve assez fascinant :
1) Qu'est-ce que $L(\R)$. Est-ce la collection des constructibles à paramètres dans $\R$ ?
2) Si $U$est un univers satisfaisant $V\ne L$. Est-ce que tout modèle dans $U$ de $V=L$ est dénombrable dans $U$ ?

Question subsidiaire : S'il n'existe pas dans $U$ de cardinaux inaccessibles, j'ai crû comprendre qu'il n'existe pas de plongement non trivial. Confirmes-tu ? Je crois qu'il y a un fil ou tu le démontres, mais lequel ?

Enfin est-ce une erreur de dire que le forcing consiste à déclarer que certaines parties intuitives de $\N$ sont dans le sur-univers et de prendre comme modèle extérieur la cloture par ZF ?

Merci d'avance pour les réponses.
Amicalement,
zephir.

christophe c

1) Pour définir $L[\R]$ tu peux procéder comme suit:

$L'_0:=\emptyset$

$L'_{a+1}:=$ l'ensemble des parties définissables avec $\in;\forall ;\to$ et un prédicat paramètre qui est une partie de $\N$

$L'_{ordinal\ limite}:=$ réunion des $L_b$ précédents.

$L[\R] $ est alors la réunion quand $a$ parcourt tous les ordinaux des $L'_a$ précédents.

2) La réponse à la question (2) est "non". Un univers peut à priori contenir plein de gros modèles de $V=L$, ne serait-ce par exemple que les $L_a$ , je veux dire ceux qui sont des modèles de ZFC + "V=L" et il y en a autant que d'ordinaux si on admet quelques "moyens" (très moyens) axiomes de grands cardinaux. Bien entendu, par Godel, il se peut aussi qu'un univers ne contienne aucun modèle de ZF tout court. Donc tout dépend de U.

QS: je t'avoue que je n'ai pas fait la liste référencée de tous mes posts hélas. Mais la réponse est "oui", un plongement (au sens usuel ensembliste) entraine non seulement l'existence d'un inaccessible (qui est un "petit" grand cardinal), mais aussi l'existence d'un mesurable. Je te réécris la preuve résumée:

Soit $j:V\to M$ (on n'a pas besoin de supposer que M vaut V, loin de là) et $cp$ un ordinal tel que $j(cp)\neq cp$. (En fait, exercice, alors $j(cp)>cp$). L'ensemble des parties $A$ de cp telles que $cp\in j(A)$ est un ultrafiltre non principal sigma additif sur $cp$.

Je te mettrai au post suivant pourquoi alors un tel cp est très très largement un cardinal inacessible


Last question:
Dans l'absolu "la cloture par ZF" est une notion délicate à définir. Si tu as un modéle M même dénombrable et transitif de ZFC, et une partie P de $\N$ quelconque , rien n'interdit qu'elle soit, par exemple, un codage très simple de $M$ lui-même. Il s'ensuivra alors qu'il n'y a pas de "ZF-cloture" comme tu aimerais qui soit un modèle de ZF qui contienne M et aussi P et qui soit de même hauteur que M (ie contienne les mêmes ordinaux. De plus rien n'indique dans le cas quelconque qu'il existe "un plus petit modèle de ZF qui contienne P et les éléments de M.

Donc "oui" c'est une sorte d'erreur de le présenter ainsi. Mais en fait c'est quand-même "presque" ça l'idée. En fait, un ensemble rajouté par forcing est "spécial" et très "lache": c'est un gentil petit mouton qui ne provoque aucun remou. Dès lors, on peut "à la fin" dire que si P est obtenu par extension générique alors oui, M[P] est le plus petit modèle de ZF contenant P et les éléments de M. Mais ce n'est pas comme ça qu'on le prouve (ie en faisant une construction qui rajoute des trucs un à un jusqu'à stabiliser). Ca arrive juste que c'est vrai à l'arrivée.

christophe c

Excuse, je peux poste en plusieurs trucs parce que les gros posts quand je fais une erreur latex, je galère après pour la trouver.

Donc suite:

pour obtenir le P petit mouton dont je te parle, tu te donnes d'abord une algèbre de Boole complète qui remplace le vrai/faux habituel des platoniciens.

Tu la choisis comme ça t'arrange pour regarder ensuite le spectacle des énoncés indécidables que ça peut donner.

Ensuite, au lieu de contruire l'univers "V" habituel, tu construis l'ensemble des "objets foringuement quantiques" suivants:

$V_ 0:=\emptyset$

$V_a$ = ensemble des applications de la réunion des $V_b$ qui précèdent $a$ dans $B$. Autrement dit, si B était l'ensemble à 2 éléments vrai/faux, alors la réunion des $V_a$ serait ton univers habituel.

Tu obtiens ce qu'on appelle traditionnellement, un "modèle booléen" W.

Chaque énoncé à une valeur booléenne. Mais c'est chiant de la calculer "à la main". Par exemple, ayant défini la valeur booléenne de chaque $R(e)$, pour $e$ dans $W$, tu as que la valeur booléenne de l'énoncé $\forall xR(x)$ est la borne inf des valeurs des $R(e)$. B étant complète, ça a un sens.

Pour éviter le "quantisme" et écrire des articles imbitables où le gars dit "bon bin, voilà la valeur booléenne de l'hypothèse du continue est tant", regardez je vais la calculer (et après 500 pages, tu obtiens $0_B$ par exemple, on "réduit le paquet d'onde avec un ensemble générique extérieur (donc lui il est bien extérieur, mais li est inoffensif en termes de non problèmes qu'il pose pour être considéré comme rajoutable à l'univers initial):

On appelle ensemble générique $G$ une partie de $B$ qui rencontre tous les ensembles denses de B de l'univers initial. Exercice, en fait $G$ est un ultrafiltre "magique" et complet dans le sens suivant:

si $\wedge _ i b_i\notin G$ alors il y a au moins un i tel que $b_i\notin G$.

Of course, un tel $G$ magique ne peut pas être dans V (sauf si B est inutile en termes de forcing).

L'avantage ici est que "tu connais" l'extension générique: c'est "bêtement" le quotientage de W par G. Les objets de $W$ deviennent des ensembles et pour savoir si l'un f appartient à l'autre g, tu demandes juste "est-ce que $f(g)\in G$ en ta rappelant que $f,g$ sont des applications partielles à valeur dans $B$ et que on pose que si $g$ n'est pas dans le domaine de $f$ alors $f(g):=0_B$

Et tout le reste est simple routine.

christophe c

Je te prouve le truc promis sur le fait qu'un ultrafiltre non principal et sigma additif entraine qu'il y a tout plein d'inaccessibles.

Tu prends le plus petit ordinal cm sur lequel existe un tel ultrafiltre, W.

Ca ne peut évidemment pas être $\N$. Et non plus un cardinal inférieur à celui de $\R$, car un tel ultrafiltre sur $\R$ serait égal à sa limite (en prenant une version compacte de $\R$).

Je pense que tu vois déjà pourquoi si ça ne peut être un cardinal de $E$ alors, pour les même raison que ci-dessus avec $\N$ et $\R$ ça ne peut être un cardinal $\leg$ à celui de $P(E)$.

Ca ne peut pas non plus être un cardinal singulier*. C'est terminé, cm est inaccessible.

* "singulier" veut dire de cofinalité strictement plus petite que lui-même. La cofinalité d'un cardinal $a$ étant le plus petit ordinal $b$ tel qu'il y a une application de $b$ dans $a$ dont la borne sup de l'image est $a$.

Pour voir que cm est en fait bien plus gros que le plus petit des inaccessibles e, tu recommences en partant de e.

Pour faire proprement les choses et monter haut, mieux vaut changer W en ce qu'on appelle une "normale mesure". Je te résume l'idée.

Pour l'instant W n'est qu'un vulgaire ultrafiltre sur $cm$ qui contient tout ensemble de la forme $[b,a[$, $b\in a$

Il se peut qu'il existe une application $f$ de $cm$ dans $cm$ telle que $\forall x\in a: f(x)<x$ et telle que l'image de W par f soit encore un ultrafiltre $W_1$sigam additif non principal sur $cm$. On peut recommencer avec $W_1$ et obtenir $W_2$ et $f_2$. Etc.. En fait c'est obligé de s'arrêter au bout d'un temps fini. En effet, sinon, soit $g$ l'application de $cm$ dans $cm^\N$ qui envoie $x$ sur $(f_n(x))_n$. Comme $W$ est sigma additif, il existe un entier $p$ tel que l'ensemble des $x$ tels que $f_{p+1}(x)\geq f_p(x)$ est dans W ce qui est une contradiction avec la définition de $W_{p+1}$

Donc wlog, tu obtiens un nouveau $W:=W_p$ tel que $\forall f:$, ou bien pour presque tous $x$ modulo $W$, $f(x)\geq x$ ou bien il existe un élément $d\in cm$ tel que pour presque tous $x$ modulo $W$, $f(x)=d$.

La considération de ce $W$ là, appelé "normale mesure" te permet de continuer le raisonnement très loin, par des "autoréférences". Par exemple, exercice, pour presque tout x modulo W, $f(x)$ est un cardinal inaccessible. Etc, etc. En fait pour presque tout $x$ modulo W, $x$ a les mêmes propriétés au premier et deuxième ordre que $cm$ lui-même. Ce n'est pas contradictoire car être munisabble d'un ultrafiltre non princpal sigma additif est une propriété du troisième ordre.

christophe c

Rappel (je l'ai déjà dit mais pour t'éviter un parcours interminable): un partie dense $D$ d'un algèbre de Boole complète $(B,\leq)$ est une partie telle que $\forall x\neq 0_B \exists y\in D, y\neq 0_B\ et\ y\leq x$

zephir

cc a écrit:

Je pense que tu vois déjà pourquoi si ça ne peut être un cardinal de $ E$ alors, pour les même raison que ci-dessus avec $ \mathbb{N}$ et $ \mathbb{R}$ ça ne peut être un cardinal $ \leg$ à celui de $ P(E)$.

Je m'en doute, mais je ne vois pas bien comment obtenir une version compacte de $P(E)$ lorsque $E$ est un ensemble quelconque. Un mot d'explication ?

J'ai l'impression que le chapitre XVI du Krivine t'a bien plu. Il y est beaucoup question d'algèbre de boule complète et d'ultrafiltre.

christophe c

J'ai l'impression que le chapitre XVI du Krivine t'a bien plu

Tant mieux, mais malgré tout le respect que j'ai pour lui, je n'ai pas appris le forcing dans son livre car il donne tellement de détails (tout à fait légitimes) en général que mon non mal de crane n'y résisterait pas

Pour ton autre question, c'est Tychonoff, ou si tu préfères:

Soit W un ultrafiltre ok blabla sur $P(E)$. Soit $A$ l'ensemble des $x\in E$ qui sont dans $Y$ pour presque tout $Y$ modulo W. Comme $W$ n'est pas principal, pour presque tout Y modulo W, f(Y) est un élément de la différence symétrique de Y avec A, en choisissant bien f. L'image de W par f est alors un ultrafiltre ok blabla sur $E$, contradiction.

zephir

Ok cc. cm est le plus petit ordinal tel que.. donc ...
Dans quel livre (ou dans quel cours) as-tu appris le forcing ?

christophe c

Bin en fait je ne sais pas trop, surtout dans les discussions de café je crois. J'ai feuilleté des résumés de l'idée, discuté avec des forcingueurs. Il me semble que j'avais emprunté un livre jaune de Kunen (mais je me souviens plus si c'est l'auteur exact, avec les histoires de borne de Kunen, je peux confondre).

Mais le principe du forcing, c'est finalement assez simple, c'est ça qui est beau dans cette découverte, vu à quel point à côté c'est fructueux. Tu remplace vrai / faux par Alg de Boole et essentiellement c'est fini (après y a de l'intendance à voir, en particulier avec l'extensionnalité, mais on "devine" la fin du film)

D'une certaine manière on peut dire que M.quantique et forcing se rejoignent dans ce qu'ils invitent à faire comme remise en cause spirituelle. A vrai dire, la vraie bonne manière de faire du forcing, ce serait de raisonner directement dans le modèle booléen que je t'ai signalé, mais je pense que tout le monde a la flemme, donc le passage par le "G" virtuel est plus jouissif. Mais il ne faut pas perdre de vue qu'il est au principe sérieux ce que l'analyse standard est aux ultrafiltres.

christophe c

Mais attention: je recommande le Krivine pour les autres, surtout si tu as envie de "vérifier" plein de petit trucs. La science c'est tout prouver.

ccnc

Je suggère un axiome très discret mais qui me semble finalement très important, dont il semble qu'il va jouer un rôle crucial (je viens de "l'inventer" au détour d'une pensée, mais en fait, à la lumière de news récentes, il me semble central.

C'est un axiome tout à fait "consistant", ie impliqué par l'axiome du choix et qui de plus, n'est à priori pas dénombrable dans ZF + CD. Pourtant, on est tenté de penser que ce qu'il dit est "vrai" (dans tous les univers, y compris non astreint "au choix").

Un ultrafiltre sigma additif (qu'il soit ou non principal) joue le rôle, comme tout ultrafiltre, d'un objet virtuel, mais "tellement peu virtuel"***, qu'a envie de le supposer "réel" dans le sens suivant: s'il n'est pas dans l'univers où on parle, on a envie de le rajouter avec une procédure "ad hoc". L'axiome suivant, très modéré, dit en substance que le défaut d'axiome du choix doit pouvoir se passer de "l'irréalité" de ces objets.

Pour tout ultrafiltre W sigma additif (principal ou non, il existe une fonction choix $f$ telle que $\forall X\in W:f(X)\in X$

C'est un cas particulier très inoffensif d'axiome du choix. Au nom de ***, on a envie de penser qu'il est totalement inoffensif!

*** Soit W un ultrafiltre sigma additif sur E et $f$ une application de $E$ dans $\N$ alors l'objet virtuel représenté par W est envoyé par f sur un vrai entier. ie, il existe $n\in \N: \{x: f(x)=n\}\in W$

On a la même chose en remplaçant $\N$ par $\R$ ci-dessus. Ainsi toutes les maths usuelles sont non affectées par cet axiome.

Et pourtant... il entraine qu'il existe des ensembles de réels non Lebesgues mesurables.

ccnc

erratum: "il existe une fonction f telle que ...." (j'ai écrit "choix" pour sensibiliser).

En fait, intuitivement, cette affirmation étant triviale pour les ultrafiltres principaux (la fonction f est même constante), l'idée est de forcer en douceur les sigma additif à "attirer" avoir une propriété des principaux.

ccnc

Cet axiome entraine aussi qu'il n'existe pas de plongement non trivial de V dans V, inexistence conjecturée démontrable par H.Woodin et nouvellement considérée comme un "carrefour" important.

christophe c

J'illustre par une des preuves de l'affirmation de 2 posts au dessus, un des trucs que j'ai dit au lien (à teneur philo): http://www.les-mathematiques.net/phorum/read.php?12,582885,582986#msg-582986

Supposons que tous les ensembles de réels soient Lebesgues-mesurables. Alors sur le quotient $T:=\R \cap [0;1]/ \Q$, les complémentaires des ensembles de mesure nulle induisent un ultrafiltre W sigma-additif sur T.

En effet, un ensemble stable par addition avec un rationnel ne peut être que négligeable ou conégligeable. L'aspect ultrafiltre vient de ce que tous les ensembles sont mesurables.

Soit $L$ une application choix sur $W$ uniquement:

remarque, c'est extrêmement peu demander car pour n'importe quel prouveur qui voudrait exploiter cet axiome, confronté à un sceptique au moment où l'occurence critique de l'énoncé viendrait, il n'aurait qu'à tirer au sort un réel (en jetant un pièce par exemple), et à moins que le monde soit "bizarre" il ne pourrait être mis en défaut à ce moment-là (faudrait que par malchance le réel tombe hors d'un ensemble conégligeable dont le sceptique aurait dû prouver avant qu'il est conégligeable (règle du jeu), et depuis le début de la partie, seul un nombre fini de tels ensembles auraient été considérés

Soit $u$ une suite ordinale allant jusqu'à un certain ordinal "borne" telle que pour tout ordinal $a<borne: u(a):=L(T-\{u(b)/b<a\})$

L'image de $u$ est dans $W$, et pour tout ordinal $a<borne$ l'image de la restriction de $u$ à $a$ induit un ensemble négligeable.

Le théorème de Fubini pour la mesure de Lebesgues induit alors une contradiction.

La conclusion est qu'avec un très petit axiome on prouve qu'il existe un ensemble non Lebesgues-mesurable. En fait, l'existence de $borne$ est un axiome "gratuit" (au sens affirmation gratuite) de ZF qui a du mal à être soutenu si on croit au "vrai hasard".

Maintenant, bien entendu, ça peut paraitre peu problématique à qui ne croit pas qu'il y ait de raison que tous les ensembles "naturels" soient mesurables. Voire un peu avant dans ce fil de quelle manière AD implique qu'ils le sont tous de manière naturelle. Maintenant, il peut ne pas paraitre naturel qu'AD soit un axiome réaliste. Mais là encore on peut répondre à l'objection en disant que "in the real world", dans les jeux impliqués par la demo, la stratégie infaillible pour gagner est vraiment simple (il suffit de jeter une pièce de manière répétée).

Le "bonne" conclusion est donc qu'il y a plus de réels que d'ordinaux et que les réels ne peuvent pas former un ensemble. Bien entendu c'est philosophique, mais au regard de la correspondance de Curry Howard, c'est la seule manière dont se mettrait d'accord un prouveur et un sceptique au moment de l'exécution de la preuve ci-dessus.

christophe c

Après un petit diner avec Anatole, nous sommes arrivés à une conclusion marrante et surement intéressante:

il parvient d'une manière relatviement "courante" à prendre n'importe quelle C*algèbre (et je pense d'autres algèbres, j'ai oublié de demander) et via les topos à l'envoyer dans une algèbre commutative, mais dans un modèle "intuionniste" de ZF, un genre de topos.

Ne connaissant pas les topos, je regarderai ça... Par contre, à priori, vu le procédé, très simple (à condition de connaitre les topos) on s'est demandé ce qu'on gagne/perd en prenant lourdement la logique classique. En effet, le procédé consiste à partir des sous-algèbre commutatives munies de l'ordre inclusion. C'est typique du forcing.

Admettons donc qu'on fasse la même chose avec $P:=(S(A);\supseteq)$ où $S(A)$ est l'ensemble des sous-algèbre commutative de $A$. Et bien on obtient, comme je le rappelais à Zephir, un truc appelé modèle booléen et noté $V^B$, où $B$ est l'algèbre de Boole complète canonique associé à $P$ (c'est à dire la plus petit algèbre de Boole complète dans laquelle P se plonge densément)

Ce $V^B$ représente relativement bien déjà beaucoup de choses concernant $A$. Et c'est bcp plus simple que tous les délires analytiques sur commutatif/pas commutatif.

Un truc qu'on récupère bien aussi, c'est le côté "réduction du paquet d'onde": en effet, contrairement à ce qui se passe en réalisabilité, ou avec les topos qui sont des objets un peu artisanaux et très compliqués dans leurs définitions par cas, avec le forcing, on dispose d'une capacité de quotienter abruptement par un ultrafiltre générique***. Dans ce cas, on se retrouve avec une "photo" entièrement classique de $V^B$ qui n'est rien d'autre qu'un modèle (générique certes) de ZF.

*** c'est à dire un ultrafiltre sur B, ie un truc qui envoie cohéremment chaque élément de $B$ sur vrai ou faux.

Si on en reste à $V^B$, on obtient un l'analogue d'un résultat "après décohérence" mais "avant mesure" (ie une superposition sans interférences de paquets d'histoires "parallèles", perçues par les habitants comme vivant dans un univers probabiliste classique, ie un (omega ; tribu ; P)). Donc, $V^B$ c'est déjà pas mal, même si ça a une odeur "classique".

christophe c

Ce post est une digression. J'ai surement déjà écrit plus haut dans le (long) fil ce qu'il dit, mais je le redis périodiquement. Il me semble important de ne pas perdre de vue la "nature" des maths. Il sert à ça.


Soit L un ensemble dit de variables propositionnelles. (La partie "premier ordre" n'est pas plus compliquée). Intuitivement, il représente les phrases sans connecteur logique de la science. Soit $tout$ un élément qui n'est pas dans $L$ (il réprésente le "faux" mathématique)

Soit $P$ le plus petit ensemble (au sens de l'inclusion) tel que $L\subseteq P$ et $P^2\subseteq P$ et $tout\in P$

Intuitivement, il représente l'ensemble de toutes les phrases, y compris articulées entre elles logiquement.

un couple $(a,b)$ sera plutôt écrit $a\to b$, qui représente intuitivement la phrase "si a alors b".

Soit $K$ l'ensemble des phrases de la forme $a\to (b\to a)$ ou de la forme $tout\to a$

Soit $S$ l'ensemble des phrases de la forme $(a\to (b\to c))\to ((a\to b)\to (a\to c))$

Soit $C$ l'ensemble des phrases de la forme $((a\to tout)\to tout)\to a$

Soit $T$ le plus petit ensemble inclus dans $P$ tel que $K\subseteq T$ et $S\subseteq T$ et $C\subseteq T$ et tel que:

$\forall x,y:$ si $x\in T$ et $x\to y\in T$ alors $y\in T$ (***)

Théorème de complétude:

Si $p\notin T$ alors il existe une partie $M$ de $P$ appelé "modèle" ayant les propriétés suivantes:

1) $p\notin M$
2) $\forall x,y: x\in M$ ou $(x\to y)\in M$
3) $\forall x: tout\to x\in M$
4) $tout\notin M$
5) $\forall x,y:$ si $x\in M$ et $x\to y\in M$ alors $y\in M$
6) $forall x,y:$ si $y\in M$ alors $x\to y\in M$
7) $\forall x,y:$ si $x\in M$ et $y\notin M$ alors $(x\to y)\notin M$

Autrement dit, il est possible de trouver une application de $P$ dans $\{vrai;faux\}$ qui "convient" aux connecteurs et qui attribue à $p$ la valeur "faux".

Les ensembles $K;S;C$ se traduisant "dans le vraie vie" par des axiomes formels très simples dits "évidences", et la seule rèlge étant (***) (appelée modus ponens) ça clot toute débat possible sur ce que "fait" la science (déontologiquement, pas sociologiquement). Elle cherche si un énoncé est dans $T$, quand il y est, elle peut le prouver, quand il n'y est pas il existe un modèle très concret qui retire tout espoir qu'il puisse être "sûr". Il n'y a donc pas de "marge" ou d'espoir de mystère caché je ne sais où.

A ça il faut ajouter la chose suivante, moins médiatisée, mais tout aussi "violente":


Remarque: $P$ est la réunion des $P_n$ où $P_0:=L\cup \{tout\}$ et $P_{n+1}:=P_n\cup $ l'ensemble des $x\to y$ tels que $(x,y)\in P_n ^2$.

On définit par récurrence la notion d'occurences positive ou négative d'un élément de $P$ (d'une manière un peu intuitive, certes, car il faudrait repérer des "places" dans les énoncés, mais bref.

Ayant déjà défini où sont les occurences positives, et les négatives de $a$ et de $b$, on déclare que
- les occurences positives de $a\to b$ sont celles de $b$ union les occurences négatives de $a$.
- les occurences négatives de $a\to b$ sont celles de $b$ union les occurences positives de $a$.

Théorème (une façon de l'énoncer intuitivement est de dire "tout théorème de maths est un cas particulier d'évidences):

Tout élément $t$ de $T$ est tel qu'il existe une suite $u_1;...;u_n=t$ telle que:

1) $u_1\in Axiome:=K\cup S\cup C$ (considéré comme l'ensemble des évidences)
2) pour tout $i$, pour passer de $u_i$ à $u_{i+1}$ on n'a fait qu'une seule chose:

2.1) ou bien on a remplacé une occurence positive de $u_i$ de la forme $a\to x$ par $x$ (et c'est tout), où $a\in Axiome$.
2.2) ou bien on a remplacé une occurence négative de $u_i$ de la forme $x$ par $a\to x$ (et c'est tout), où $a\in Axiome$.


(Autrement dit, on est passé à un cas particulier à chaque fois, ie d'un énoncé $u_i$ général, on est passé à $u_{i+1}$ cas particuler de $u_i$).



Là, j'ai donné unqiuement des versions (moins spectaculaires et pourtant déjà parlantes) faciles à prouver (je le ferai dans les posts suivants) d'un phénomène dont les expressions les plus fortes sont encore plus "parlantes".

Il parait donc "trompeur sur la marchandise" de crier trop fort que les théorèmes de maths ont un "fond" physicalisable jusqu'au bout, puisqu'au contraire, il n'expriment que des cas particuliers, de formes, pour l'essentiel, dites évidentes très proches de $A\to A$.

christophe c

Pour faire un post pas trop long, j'ai pris comme $K;S;C$ des ensemble qui peut-être ne représentent pas des choses totalement évidentes évidentes, mais il faut bien voire que:

Dans $K$, on ne trouve qu'affirmées: "si b alors si a alors a", on a juste "échangé" les hypothèses a et b.

Dans $S$ on ne trouve qu'affirmées: "si a implique $a\to b$ alors a implique b'" où b' dit $(b\to c)\to c$ au lieu de dire $b$, mais:

$b\to ((b\to c)\to c)$ n'est que dire la même chose que dire $(b\to c)\to (b\to c)$ en échangeant les hypothèses $b$ et $(b\to c)$, avant de conclure $c$.

Dans $C$ on n'affirme que si $non(non(a))$ alors $a$, en sachant que $non(a)$ est l'abréviation de $a\to tout$

christophe c

Comme promis, je prouve le deuxième théorème (juste après celui de complétude):

Prenons l'ensemble des $p\in P$ qui vérifient la conclusion. Il suffit de prouver qu'il est stable par modus ponens.

Soient $u_n=B\in Axiomes;...;u_1=A$ et $v_1\in Axiomes; ...; v_{p+1}=(A\to P)$

Alors la suite $v_1;....;v_{p+1}=(A\to P)=(u_1\to P);(u_2\to P);....;(B\to P); P$ atteste que $P$ vérifie la conclusion.


Je justifie l'utilisation du mot "cas particulier" du dernier post.

Je rappelle que (A-->B) --> (A-->((B-->C)-->C)) n'est rien d'autre que (A-->B) --->(A-->B) où on a remplacé B par (B-->C)-->C

Prenons "presque" une phrase de S:

(A->(B->C))->((A->B)->(A->(A->C))) et déplaçons ses hypothèses:

(A->B)->[A->((B->(A->C))->(A->C))] qui est de la forme (A->B)->(A->B') où B' est de la forme (B->X)->X, autrement dit un cas particulier de B.

On a donc juste, pour obtenir les phrases de S, remplacé A->(A->C) par A->C (clone), permuté des hypothèses et pris un cas particulier en partant d'un énoncé de la forme X implique X.

Pourquoi parler de passage au cas particulier à propos du passage de A à (A->B)->B.

Réponse: une preuve de A est une garentie beaucoup plus forte qu'un preuve de (A->B)->B. Les preuves de A fabriquent un objet $a$ dont on est sûr qu'il est dans A, et par là un objet canonique $ev_a$qui est l'évaluateur (si on considère les lettres comme des ensembles) , $ev_a(f) = f(a)$ pour toute $f\in A\to B$.

Mais: le fait d'utiliser cet axiome dans une preuve atteste que l'endroit où on va l'exploiter est "surfait". Ie on a besoin d'une preuve de (A->B)->B, pour continuer, autrement dit de n'importe quelle fonction $L$ qui envoie $A\to B$ dans $B$, et l'utilisation de l'axiome atteste, qu'on donne en guise de L non pas un objet quelconque, mais un $ev_a$, avec $a\in A$. La suite de la preuve "jette donc" toute la force que possédait la preuve de $a$ en ne retenant que le fait qu'elle a fourni une L allant de $A\to B$ dans B.

Chaque étape est ainsi, (à l'excption du "clonage d'hypothèse" qui lui n'est pas un simple passage au CP, puisqu'il donne le droit d'utiliser plusieurs fois une hypothèse), elle "jette" des contenus (en général assez importants) qui étaient fournis par l'évidence de départ. En quelque sorte on peut dire, que c'est parce qu'un théorème est vraiment trop faible qu'il n'est pas "visiblement" évident, ie il est trop loin, trop cas particulier, des évidences qui le généralisent pour "se voir" au premier coup d'oeil.

christophe c

Comme il a été plusieurs fois question récemment de hasard***, j'en profite pour redonner une preuve courte de l'indépendance de l'hypothèse du continu.

***
http://www.les-mathematiques.net/phorum/read.php?3,584861,584894#msg-584894

http://www.les-mathematiques.net/phorum/read.php?12,582885,582986#msg-582986



Les habitants d'un univers vérifiant les axiomes de ZFC sont à table un soir d'été et parlottent. Ils se demandent à quoi ressemblerait de prendre un gros ensemble $E$ et, pour chaque élément $e$ de $E$ de tirer au sort un réel $x(e)$ te manière à obtenir une application de $E$ dans $[0;1]; e\mapsto x(e)$

Lors de la discussion, il est "presque" évident pour eux, que s'ils se réfèrent au "vrai hasard" qu'il ne peuvent voir dans leur univers, certes, mais qu'ils peuvent imaginer, l'application obtenue sera avec probabilité 1 une application injective.

En effet, ils savent que rien ne leur permet d'avoir la moindre preuve qu'ils ne vivent pas dans un univers dénombrable sans le savoir. Or tirer une suite de réels donne avec proba=1 une suite injective.

Supposons maintenant que leur ensemble $E$ soit très gros, et qu'il y ait énoooormément de cardinaux entre $\N$ et celui de $E$.

Soit $p$ une preuve de HC. La particularité des preuves c'est qu'elles passent à TOUTES les algèbres de Boole (on n'utilise que le modus ponens, voir post ci-dessus), et en particulier à celle qui permet de formaliser la discussion qu'ils sont entrain d'avoir à propos de leur $x\in E\to \R$ imaginaire.

La preuve $p$ si elle existait, prouverait que $x$ n'est pas injective. Elle n'existe donc pas.

Ca répond aussi indirectement à une question du fil:

http://www.les-mathematiques.net/phorum/read.php?7,412300,584856#msg-584856

sur l'(in)utilité des réels "trop" compliqués. Ici on tire au sort "beaucoup" de réels, et on montre "qu'ils servent à rien... si ce n'est qu'ils servent si peu qu'ils servent en contre-partie à prouver qu'on ne peut prouver HC. Leur inutilité est "utile", car la preuve de leur inutilité est une preuve d'impossibilité de prouver HC.

christophe c

Un peu de pub.

JL m'a dit qu'il avait rédigé une version "self contained", et effectivement (avec des efforts) elle semble l'être.

Cet article me semble pouvoir intéresser bcp de mondes en ce qu'il décrit un peu l'aboutissement de bcp d'efforts (assez solitaires hélas) pour aller jusqu'au bout de la correspondance de Curry HOward.

L'idée clé de cet article n'est pas de "prouver" l'existence d'un ultrafiltre sur $\N$, mais d'utiliser le forcing, pour "le faire Curry-Howardement" exister et ainsi réaliser une forme d'axiome du choix très substantielle.

http://www.pps.jussieu.fr/~krivine/articles/Bon_ordre.pdf

christophe c

Je n'ai pas lu le papier cité au post précédent, mais je le résume

JLK cherche depuis des années à "réaliser" l'axiome du choix, qui est comme un village d'Astérix, puisque le seul axiome des maths qui lui donne du fil à retordre.

Rappel des conquètes antérieures: tous les axiomes se réalisent par un "programme" qui en gros "ne fait rien", celui qu'on appelle "l'identité" en lambda calcul. Pourquoi?

Et bien tout simplement parce qu'on raisonne "naturellement" en identifiant à un niveau très en amont les 2 phrases:

1) x est bleu

2) x appartient à l'ensemble des choses bleues

Or mis à part l'axiome d'extensionnalité toute la théorie des ensembles ne comporte que des axiomes du style "l'ensemble des choses bleues existe", qu'on peut appeler "des axiomes de compréhension. Voir d'ailleurs le lien suivant, ou la super théorie (contradictoire) mais naturelle dont j'ai parlé au tout début de ce fil.

lien à rajouter (bourbaki21)

JLK est très respectueux de ce qu'il considère comme la "naturalité" de ZF. Autrement dit, il n'approuverait ce que je viens d'écrire et trouverait que "c'est trop facile" de tricher comme ça. Il ne cherche donc pas à modifier ZF mais souhaite y répondre très exactement. Autrement dit, il n'a strictement aucune envie ni d'ajouter ni de retirer des axiomes de compréhension** à la théorie qui fonde les maths

** je rappelle que ce sont les axiomes de la forme: $\exists a\forall x : R(x)\iff x\in a$ qu'on trouve dans ZF.

Il restait donc 2 axiomes à réaliser: l'axiome d'extensionnalité et l'axiome du choix.

JLK a démarré avec une version de ZF sans extensionnalité, et a réalisé (très facilement) l'axiome du choix, sauf que... Dans ZF sans extensionnalité, l'axiome du choix (qui est le même énoncé) est incomparablement plus faible.

Ensuite il a construit une version un peu compliquée menant à l'extensionnalité avec un couteau, de la ficelle, et un sylex et réaliser que AC sans extensionnalité permet d'avoir l'axiome du choix dépendant (incontournable en analyse) dans le truc quotienté qui vérifie l'extensionnalité.

Pour l'axiome d'extensionnalité, par contre, c'est "sans espoir". En fait tous les théorèmes de maths peuvent être vus comme disant "si extensionnalité alors P".

Il restait donc l'axiome du choix général (et le raisonnement par l'absurde).

Le raisonnement par l'absurde a été découvert (sa réalisation je veux dire ) par T Griffin. C'est l'instruction Callcc (voir lien à rajouter, fil sur caml). In the real life, c'est l'astuce qui consiste à faire un chèque sans provision (mais un chèque de banque, ie d'état) de 50 000 000 d'euros à un criminel pour qu'il aille à la banque l'encaisser pour qu'on puisse le capturer (lool la police a pas encore inventé ça, T.Griffin est à l'avantgarde)

Il restait donc l'axiome du choix général.

Hélas, hélas, ça ne semble pas simple (enfin si on est respectueux comme JLK de ZF). Je vais donc raconter par quel détour, il est parvenu à mettre un bon ordre sur $\R$ (si si, mais non non, ce n'est toujours pas vraiment une réalisation de l'axiome du choix).

Avant, sachez que votre tonton christophe pour vous servir, pas aussi respectueux que JLK des traditions (ça doit être une question d'âge) réalise sans problème l'axiome du choix général par... l'identité aussi. (Je l'ai déjà signalé plus haut ou dans des fils racontant un peu de correspondance de Curry Howard).

Voici un axiome de compréhension qui implique l'axiome du choix: "pour tout E, l'ensemble des ordinaux a tels qu'il n'existe pas d'injection de E dans a existe". :D:P. C'est bien un axiome de compréhension:

$\forall E \exists Z \forall x: x\in Z\iff R(E,x)$ où $R(x)$ dit "il n'existe pas d'injection de $E$ dans $x$ et $x$ est un ordinal "

Bref... (je ne garantis pas que la suite est fidèle à l'article (que je n'ai pas lu), mais elle est un atout centrale en tout cas (et à priori incontournable) dans ce genre d'activité.

Si on renonce à la baguette magique qui précède, voici comment on peut utiliser le forcing (c'est ce que JLK a fait) pour, en gros, obtenir une inoffensivité de l'utilisation que $\R$ est bien ordonnable dans les preuves de résultats d'analyse.

On se place donc dans un univers qui vérifie ZF et l'axiome du choix dépendant (qui se réalise avec l'horloge de l'ordinateur).

Soit $T$ l'ensemble des parties non vides de $\R$.

A priori, il n'y a pas de fonction choix sur $T$, c'est à dire une application $f$ telle que $\forall X\in T: f(X)\in X$.

Comment "en rajouter" une sans faire trop de casse (ie l'idéal serait de ne pas rajouter des réels avatars qui viendraient avec ce rajout d'une fonction choix)?

Le foncing (c'est une des bases du forcong) donne la réponse, sans appel. Noter que cette technique a permis par exemple, dès le départ (ie dès l'invention du forcing) à Cohen de prouver la consistance de HC bien plus élégamment que Godel, en particulier, de prouver qu'on peut toujours élargir un univers de manière à obtenir qu'il vérifie HC. (Godel avait juste prouvé que HC est vrai dans L, l'univers des constructibles, mais ça n'allait pas "loin").

Ce qui me fait penser que l'article de JLK utilise beaucoup l'astuce qui va suivre, c'est qu'il dit lui-même qu'il réalise aussi HC. Et ça n'a rien d'étonnant. La technique qui suit est très propre, en particulier, elle n'importe pas d'avatars de nouveaux réels indésirables avec le rajout d'une fonction choix, par contre, elle a un prix c'est que si on s'y prend mal, elle force l'hypothèse du continu à être vrai (en tout cas dans les situations de base que je connais).

Voici le focing utilisé pour rajouter une fonction sur T sans rajouter de nouveau réels.


Soit $P$ l'ensemble ordonné par prolongement (ie inclusion inverse) des fonctions partielles de domaine au plus dénombrable qui sont des fonctions choix sur leur domaine de définition. On force avec l'algèbre de Boole complète $B$ associée à P (ou avec P ce qui revient au même).

Lemme1: $\forall X\in T$ l'ensemble des $f\in P$ telles que $X\in dom(f)$ est dense. (trivial)

par conséquent tout P-générique G induira une fonction choix sur T. On fixe G et on note $V[G] $ l'extension génerique

Lemme2: tout réel de l'extension générique est un réel qui existe déjà dans l'univers initial.

preuve: en fait, on va prouver plus. On prouve que toute suite $u$ d'éléments de V (l'univers initial) qui est dans $V[G]$ est en fait dans V. Soit un nom name de la suite u. Soit $a\in B$. Soit $a_1\in B$ et $v_1$ telle que $a_1\leq $ à la valeur booléenne de l'énoncé " name(1)= $v_1$ ". Soit $a_2\leq a_1$ et $v_2$ tel que $a_2\leq $ à la valeur de vérité de " name(2) = $v_2$ "; etc; etc

A la fin on obtient une suite descendante $a_1;a_2;...$ d'éléments de $B$ telle que $a_n\leq $ à la valeur de vérité de "name(n) = $v_n$ ".

lemme clé: l'ordre P (et donc l'algèbre $B$) a la propriété (évidente) suivante: il existe $b\in B$ tel que $b\neq 0_B$ et $\forall n\in N: b\leq a_n$.

Par ailleurs, $b\leq $ à la valeur de vérité de l'énoncé $name = v$.

On a donc prouvé que $\forall a\in B$ il existe $b\in B$ et $v\in V$ tel que $b\leq a$ et $b\leq $ l'énoncé $(name\in V)$. Ainsi l'ensemble des valeurs booléennes qui forcent $name$ à être dans $V$ est dense et rencontre donc tout générique. Il s'ensuit que $u\in V$.

Finalement, dans ce nouvel univers, on a bien que $T$ est muni d'une fonction choix, et de plus on a les mêmes réels que dans l'ancien univers. Ainsi tous ses énoncés "d'analyse" ont fondamentalement la même signification dans les 2 univers.

L'article de JLK est une mise en correspondance de CuHO de tout ça (je pense)

christophe c

Histoire d'alimenter le fil, je change provisoirement complètement de sujet et j'aborde un thème (les jeux) et je donne les quelques notions incontournables, car je crois que j'avais promis de le faire et ne l'ai jamais fait.

Par ailleurs, le forcing se nourrit énormément de jeux (en rapport souvent avec de la topologie) car au fond (in some sense), un énoncé $P$ est "forçable" (c'est à dire profondément indécidable et pas seulement Godeliennement indécidable) quand dans un certain jeu, un prouveur "réaliste" ne peut pas forcer un sceptique "réaliste" à perdre. Par réaliste qu'on joue des "vrais" objets et pas seulement leurs arguments, c'est donc un autre genre de jeu que celui dont les preuves dont des stratégies gagnantes pour le prouveur.


Soit $G$ une partie de $E^\N$

le principe est qu'on considère que "le joueur2" joue $u_0;u_3;_u_4; etc$ et le joueur1 joue $u_1;u_3;...$. (J'ai mis comme ça pour la parité). C'est donc le joueur2 qui commence la partie.

Chaque joueur joue son $u_n$ à l'étape $n$ connaissant les $u_p; p<n$ que son adversaire a joué.

Tout ceci est le principe.

Mathématiquement, on n'a bien sûr que la notion de stratégie, mais pour simplifier on suppose que chaque joueur joue aussi en connaissance de ses propres coups précédents:

une 2stratégie est une suite d'applications de l'ensemble des suites finies indicées par les nombres impairs dans $E$. Mais c'est trop lourd à noter donc on simplifie en parlant de notion de "débuts acceptés".

une 2stratégie est donc un ensemble de suites finies ayant certaines propriétés (le sens est que la stratégie accepte ou refuse certains débuts et ses choix se traduisent par le fait qu'elle doit accepter toute continuation quand ce n'est pas à son tour de jouer et exactement une continuation quand c'est à son tour de jouer. Précisément:

une 2stratégie est un ensemble S de suites finies tel que:

1) pour tout entier $n$ impair et toute suite $(u(0);...;u(n-1))$ qui est dans S et tout $x\in E$, la suite $(u(0);...;u(n-1);x))$ doit être dans S

2) pour tout entier $n$ pair et toute suite $(u(0);...;u(n-1))$ qui est dans S il existe $x\in E$ tel que la suite $(u(0);...;u(n-1);x))$ doit être dans S


On définit de manière analogue la notion de 1stratégie.

un élément de $u\in E^ \N$ est appelé un "match" (ou une partie) et si S est une 2stratégie, on dira qu'il est joué (ou accepté) par S si $\forall n\in \N: u/n \in S$ en notant $u/n$ la restriction de $u$ à $n:=\{0;...;n-1\}$.

Une fois posé tout ça, si $G\subseteq E^\N$ on dira que $S$ (une 2 stratégie) est infailliblement gagnante (ou gagnante) au jeu $G$ quand $\forall u\in E^\N: u$ est accepté par $S$ implique $u\in G$

On définit de même tout ça pour les 1stratégie, mais le but d joueur1 étant de mettre la suite hors de $G$, on remplace par $\notin G$ la définition précédente.

Le théorème (évident, c'est une redite des axiomes des maths en fait) ) de Gales Stewart dit que si $G\subseteq E^\N$ est ouvert (ou fermé), l'un des 2 joueur dispose d'au moins une stratégie gagnante au jeu $G$.

Un théorème très célèbre de Tony Martin est qu'il en va de même des jeux boréliens et aucune preuve connue, meme abrégée ne fait 3 lignes de ce théorème.

Je donne 2 preuves du théorème de GS et une esquisse de l'idée de Martin.

preuve1 de GS: supposons que $G$ soit fermé et que le joueur1 n'ait pas de stratégie gagnante. C'est au joueur2 de commencer la partie. Et bien il existe un coup à jouer tel qu'après ce coup, le nouveau jeu qui résultera sera toujours un jeu fermé et tel que le joueur2 ne sera pas non plus dans une situation où si son adversaire joue bien il peut le forcer à gagner. Le même argument donne aussi le résultat si le jeu est ouvert, ie, si ce n'est pas à lui de commencer la partie. La rédaction de ça est superlourde, mais triviale (pas évidente syntaxiquement, mais triviale) car il faut "re-signer" les règles du jeu. Ainsi, à tout moment d'une partie, le fait de jouer (si c'est à son tour de jouer) ou d'attendre le coup sinon, de manière à ce que, si la position n'est pas désespérée, avant elle reste non désespérée après le coup conduit à une partie où le joueur qui essaie de mettre la suite dans $G$ (partie fermée de $E^\N$) où il n'arrive jamais que la situation soit désespérée. En particulier, la suite $u\in G$ à la fin de la partie, sinon, il existerait un entier $n$ tel que toute suite $v$ telle que $v/n=u/n$ serait hors de $G$ (par définition du fait que $E^\N - G$ est un ouvert.

preuve2 de GS: Considérons les ensembles, indicés par des ordinaux suivants:

$T_0:=$ ensemble des suites finies $s$ telles que toute suite infinie $u$ qui commence comme $s$ est hors de $G$

$T_a:=$ l'ensemble des suites finies $s$ telles que le joueur qui cherche à mettre la partie dans $G$ ne peut pas se comporter, si c'est à lui de jouer de telle sorte qu'après coup suivant $x$ joué $s+x$ soit en dehors de tous les $T_b; b<a$

Soit $T$ la réunion des $T_a; a$ ordinal

Si la suite vide est dans $T$ le joueur1 a une stratégie évidente pour gagner (il s'arrange pour faire, à chaque fois que c'est à lui de jouer, baisser l'ordinal $a$ tel que la partie partielle $s$ où on en est arrivé $\in T_a$

Sinon, le joueur2 se maintient hors de $T$ tout au long de la partie. La suite $u$ obtenue appartiendra à $G$ (rappel $G$ est fermé)

Suite au prochain post pour montrer prolonger ce genre d'argument aux boréliens...

christophe c

Avant de continuer, je donne un exemple de jeu qui est typique des idées de F.Galvin que j'ai évoqué dans le fil suivant:

http://www.les-mathematiques.net/phorum/read.php?14,599529,599551#msg-599551



Soit $E$ un ensemble infini.

2 joueurs s'affrontent: le joueur empty et le joueur non empty.

Ils doivent jouer à tour de rôle des ensembles $A_n$ tels que $A_n\supseteq A_{n+1}$ et $card(A_n)=card(E)$

Si $\cap_n A_n = \emptyset$ alors c'est epty qui a gagné la partie, sinon c'est nonempty.

Théorème (AC) (je pense qu'il est dû à F.Galvin):
Quelque soit $E$ infini, le joueur empty a une stratégie infaillible pour gagner.

Ce qui est rigolo, c'est que si vous y réfléchissez un peu, il n'est pas si simple que ça de gagner. C'est pourquoi, je mets la correction en police claire, pour ceux qui ont envie de chercher.





On peut mettre un bon ordre sur $E$, donc sans perte de généralité on peut supposer que $E$ est un cardinal. Quand c'est à empty de jouer, et qu'il doit répondre $A_{n+1}$ face à $A_n$ il joue l'ensemble des éléments de $A_n$ qui ont un prédécesseur dans $A_n$

A la fin, si $I:= \cap A_n$ n'était pas vide, il y aurait une contradiction: en effet, soit $p$ le pluspetit élément de $I$. Il a un prédecesseur $q_n$ dans tous les $A_n$ joué par nonempty. Par ailleurs, plus $n$ est grand, plus $q_n$ est petit (à cause des inclusions). Il s'ensuit qu'il existe un entier $k$ tel que $\forall n\geq k: q_k=q_n$. Mais alors $q_k<p$ et $q_k\in I$ contradiction.[/color]

christophe c

Précision: dans le jeu du post précédent, si on n'admet pas l'axiome du choix et qu'on joue avec $E:=[0;1]$, et si on admet "tout partie de $E$ de même card que E contient une partie fermée non dénombrable" (qui est connu comme consistant, et par exemple, impliqué par AD) on obtient que c'est nonempty qui gagne facilement: en effet, il joue chaque fois que c'est son tour $A_{n+1}$ fermé inclus dans $A_n$ et par compacité, il gagne.

FrançoisD

Désolé Christophe mais ton post avec des caractères jaunes est illisible!!!

L'accro que je suis veut sa dose! lol

F.D.

remarque

Il est lisible dans le source LaTeX...

christophe c

ok, j'enlève le jaune...