le forcing expliqué aux matheux ordinaires

christophe c · June 2009

Rappels:

Un ensemble $E$ est bien fondé quand pour toute partie non vide $A\subseteq E$ il existe $x\in A$ tel que pour tout élément $y$ de $A:y\notin x$

Un ensemble $E$ est transitif quand $\forall x,y: (x\in E$ et $y\in x)\to y\in E$

christophe c · June 2009

Généralisations de la méthode du forcing

Soit $T$ un ensemble $-$ une opération binaire sur $T$ et $C$ une application de $P(T)$ dans $T$. On distingue dans $T$ un élément privilégié appelé "0", qui symbolise une sorte de "paradis" (une fois qu'on y est, on a tout sans exception)

Soit $Z$ un ensemble quelconque:

On note $Z'$ l'ensemble des applications de $Z$ dans $T$.

On considère alors la collection $Y$ la plus petite contenant l'ensemble vide, stable par réunion quelconque et par $x\to x'$

On l'appelle $T-indéterminisation$ de l'univers.

à un couple $(a,b)$ de 2 éléments de $Y$ on associe $valeur(a,b)$ l'élément de $T$ de la manière suivante:

Si $a$ est dans le domaine de $b$ alors $valeur(a,b):=b(a)$

sinon, $valeur(a,b)=0$

Soit maintenant un énoncé $P$ à paramètres dans $Y$ dans langage $L(\forall;\to; \in)$. On lui associe une valeur généralisée $vg(P)$ comme suit:

S'il est atomique de la forme $"a\in b"$, on lui associe $vg(P):=vg("a\in b")=valeur(a,b)$.

S'il est de la forme $A\to B$ on lui associe $vg(A\to

:=vg(B)-vg(A)$

S'il est de la forme $\forall xR(x)$ on regarde l'ensemble $F$ des $vg(R(e))$ quand $e$ parcourt $Y$ et on lui associe $vg(P):=C(F)$

On a ainsi associé à chaque énoncé un élement de $T$ qu'on peut appeler sa $T-valeur$ de vérité.

Le forcing travaille avec des algèbres de Boole en guise de $T$, la spécialité développée par JLKrivine utilise d'autres $T$, assez proche de la notion d'algèbre de Heyting.

Il est à noter que n'importe quel espace topologique peut faire office de $T:=$ensemble des ouverts avec $U-V:=$plus grand ouvert dont l'intersection avec $V$ est inclus dans $U$ et en prenant pour $C$ l'intérieur de l'intersection. Esentiellement, à ma connaissance ce dernier exemple n'est rien de plus que du forcing "intuitionniste", le forcing "classique" se faisant avec les "bons ouverts" (ceux qui sont intérieur de leur adhérence).

christophe c · June 2009

En relisant les derniers posts, je m'aperçois que j'ai été un peu vite en besogne: j'ai dit que l'axiome "toute famille d'ensembles finis admet une fonction choix"(1) est appelé "axiome de l'ultrafiltre (tout filtre est contenu dans un ultrafiltre)"(2): il me semblait me rappeler de ça un peu "par coeur", mais à y réfléchir depuis quelques instants, je ne trouve pas de preuve.

Je me renseignerai*** et corrigerai éventuellement, cependant, il me semble que l'équivalence faisait partie de la culture à un moment... Alzeimer??

L'implication $(2)\to (1)$ elle est pratiquement évidente (découle des définitions sans étapes intermédiaires). A suivre donc...

*** Ca ne sera pas forcément rapide car il n'existe plus de spécialiste** de ces questions, et c'est d'ailleurs bien dommage

** je veux dire qui sait naturellement de mémoire les réponses et qui a l'habitude d'y réfléchir

En attendant, disons que c'est un exercice...

christophe c · June 2009

Alors j'ai demandé à 2 spécialistes: et bien pas de certitudes...

Leur avis unanime (2/2) est que (2) est strictement plus fort que (1) bien qu'il me semblait qu'il y avait une petite astuce permettant d'avoir (2) from (1)...

Donc si quelqu'un d'encore vivant (spécialité devenue non réprésentée snif) connait la réponse... :-(

christophe c · June 2009

Je reviens à AD (l'axiome de détermination, pas le modérateur

):
[Ouf :S j'ai craint un moment ... AD]

En principe, le thème suivant pourrait aller aussi dans le lien suivant: http://www.les-mathematiques.net/phorum/read.php?4,521494,524142#msg-524142

mais en fait, ce serait de la logique détournée.

Voilà un truc qui "fait le pont" et va intéresser un peu plus les gens qui aiment étudier à quelle vitesse croissent les fonctions.

Avec l'axiome du choix, on construit une suite ordinale $\alpha < L \to f_\alpha $ telle que:

pour tous $a,b< L:$ la limite quand $x\to +\infty$ de $f_b(x)-f_a(x)$ est $+\infty$ dès que $a< b$

et pour toute fonction $g$ il existe $a< L$ tel que $\forall x: g(x)\leq f_a(x)$

Pour des raisons habituelles, $L$ ne peut pas être dénombrable. Je ne suis pas sûr qu'il soit démontrable qu'il a forcément la puissance du continu (ce genre de trucs font généralement l'objet de recherches récentes (enfin les 30 last years) et le forcing permet souvent de varier les possibilités.

Par contre, voilà un résultat qui va "choquer" les gens peu habitués à la logique (genre les analystes pur sucre):

AD empêche une telle famille (ci-dessus) d'exister en un sens très fort. AD entraîne que :

tout ensemble de fonctions croissantes totalement ordonné par "$f< g=$ "$g-f$ tend vers $+\infty$ en $+\infty$" est dénombrable.

Admettons maintenant, qu'on trouve un autre moyen "d'arbitrer" (qui c'est c'est qui monte la plus vite) sans les comparer à une famille totalement ordonnée de fonctions de référence, mais si possible compatible avec AD.

Alors AD entraîne la chose suivante :

IL EXISTE une fonction croissante $g$, telle que pour TOUTE fonction croissante $f$, il existe une suite $u$ et une fonction $f^*$ telle que :

1) pour chaque entier $n$ pair: $u(n+1)=g(u(n))$

2) pour chaque entier $n$ impair $u(n+1)=f(u(n))=f^* (u(n))$

3) la fonction $f^*$ ne monte pas plus vite que la fonction $g$

Ne me dites pas que vous n'êtes pas surpris...

christophe c · July 2009

J'ai eu la réponse à quelques questions connectés entre les derniers posts et le fil:
http://www.les-mathematiques.net/phorum/read.php?4,521494,524142#msg-524142

J'y renvoie donc..

Voici aussi une précision concernant le passage

Pour des raisons habituelles, $L$ ne peut pas être dénombrable. Je ne suis pas sûr qu'il soit démontrable qu'il a forcément la puissance du continu (ce genre de trucs font généralement l'objet de recherches récentes (enfin les 30 last years) et le forcing permet souvent de varier les possibilités.

En fait je l'avais déjà dit il y a longtempes dans ce fil et l'avais moi-même oublié

, on peut par forcing, rajouter des randomréels sans que ça collapse de cardinaux.

De plus aucun random réel ne crée une nouvelle fonction qui monterait plus vite que toutes les anciennes, conclusion:

Il est consistant d'avoir:

La famille $L$ est indicé par omega1, le plus petit ordinal non dénombrable ET l'ensemble des réels, par exemple, a une cardinal monstreusement grand

Pour le prouver, rajouter à volonté tout plein de random réels à l'univers $V$. Vous obtenez un univers $V_2$ qui contient beaucoup de réels, mais telle tout fonction $g$ de $\N$ dans $\N$ qui est dans $V_2$ est telle qu'il existe une fonction $f$ dans $V$ avec $g(n)\leq f(n)$ pour tout entier $n$.

Pour la consistance évoquée, il suffit donc de partir d'un univers $V$ qui vérifie $HC$.

Foys0 · July 2009

Bon je prends la conversation en cours de route mais voilà:

CC a écrit:

AD empêche une telle famille (ci-dessus) d'exister en un sens très fort. AD entraîne que :

tout ensemble de fonctions croissantes totalement ordonné par "$ f< g=$ "$ g-f$ tend vers $ +\infty$ en $ +\infty$" est dénombrable.

$f_a: x \mapsto ax$ ,de $\mathbb R$ dans lui-même et avec $a \in \mathbb R _+$, n'est-il pas un tel ensemble? Ou àlors il s'agit peut-être d'un bon orde?

christophe c · July 2009

Merci foys, oui effectivement j'ai fait une erreur, du coup je suis condamné à une preuve afin de donner un énoncé sans erreur (non, je ne voulais pas dire "bien ordonné" (enfin je pense lol), je voulais dire de "cofinalité dénombrable" (c'est un peu plus général)), hélas, dans ce domaine, on parle tellement vite que ça génère des malentendus (on désigne par $\R$ l'ensemble $2^\N$, ou $\N ^\N$, indifféremment, etc)

Je rentre dans les détails: il est classique, sous AD, que toute partie bien ordonnée de $\R$ est dénombrable. Il s'ensuit donc que si j'avais dit "bien ordonné" ça n'en aurait été qu'un cas particulier. (1)

Avant la preuve, je donne un énoncé précis et formel:

Soit $T$ un ensemble totalement ordonné pour la relation en question. Il existe alors un ensemble $D$ dénombrable, inclus dans $T$ tel que $\forall f\in T\exists g\in D:f\leq g$. (2)

Je donnerai une preuve de ça au prochain post (faut que j'aille boire un café avant lol).

Si tu veux, le principe général, quand on regarde ce genre de questions (dans ce domaine...), c'est qu'on cherche à battre des records de vitesse de croissance, donc on oublie les petites fonctions qui viennent s'intercaler entre, on cherche à voir comme des dedrés, les vitesses de croissance.

Dans ton exemple, typiquement, les $x\to nx$ pour $n\in \N$ le jalonnent bien.

Mais mea culpa. Pourtant, en général dans ce fil, j'essaie de faire attention à chaque énoncé, sinon, vue sa longueur, l'addition d'inexactitudes serait dommage, mais cette négligence-là m'avait échappée.

(2) est un peu plus puissant que (1) comme conclusion, car il faut se méfier de ADX:-( ... Parfois juste pour des raisons de broutilles*, il peut donner des illusions: intuitivement, comme on ne peut sectionner les passages aux quotient, on a bien 2 énoncés différents qu'il faut démontrer pour chacun.

*par exemple, le fait qu'il empèche de mettre des bons ordres ne doit pas être exploité "abusivement" pour prétendre qu'il permet de rendre "un peu tout" dénombrable

christophe c · July 2009

Avant mon café, quand-même, je rappelle ce que signifie le mot "cofinal".

Etant donné $(E,R)$ une relation binaire quelconque: le plus petit cardinal possible d'une partie $P\subseteq E$ telle que:

$\forall x\in E\exists y\in P: xRy$

s'appelle la cofinalité de $(E,R)$

gilou1 · July 2009

bonjour, merci pour tes explications

Je me posais cette question "As-tu trouvé un scribe pour ton livre sur le forcing ?"(si ce n'est toujours pas le cas , je suis là et j'ai remis dans ma poche mes prétentions d'explications pour tous(l'idée du "forcing pour les nuls" avec beaucoup de blabla et pour que ce soit lisible pour les licences était assez dingue, un bon livre bien formel accessible aux étudiants niveau master(plutôt 2 que 1) sera plus logique).

Par ailleurs, j'aurai aimé connaitre la hiérarchie "actuelle" entre les axiomes des grands cardinaux(entre les cardinaux de Woodin et la borne de Kunen en fait).
J'avais parlé d' "invariance par forcing", l'idée est qu'un ensemble définissable est invariant par forcing
si toute méthode de forcing n' "ajoute aucune propriété nouvelle" à cet ensemble (bien sûr
avec un modèle canonique sympa) autrement dit toute propriété satisfaite dans une extension générique quelconque du modèle M dans lequel l'ensemble est défini était déjà satisfaite dans le modèle M, par exemple:

Sous l'hypothèse d'existence d'un cardinal supercompact(peut être que l'on peut mieux faire(c un résultat qui date un peu), tous les ensembles définissables de réels de R sont mesurables pour la mesure de Lebesgue(à partir un modèle où les ensembles définissables de réels de R sont mesurables que l' on peut construire lui-même par forcing à partir d'un modèle quelconque de R grâce à un théorème de Solovay qui date des années 60)
et surtout que l'on ne peut "modifier" aucune propriété de R par forcing.

Vu que tu parles de AD(axiome de détermination projective), si on note H_k l'union des V_k tel que k=< n
Un théorème de Martin-Steel dit que s'il
ZFC+AD donne une "bonne description" de H_1 et H_1 est invariante par forcing(Woodin), sous l'hypothèse "pour tout cardinal K il existe un cardinal de Woodin au dessus de K". Un autre résultat intéressant dû à Martin-Steel est sous l'hypothèse d'existence d'une infinité des cardinaux de Woodin alors AD est vrai. Voilà ma question,
serait-il possible(c peut être déjà fait par Woodin) de découvrir l'axiome à rajouter à
ZFC+AD pour "bien décrire" H_2 en essayant de voir les propriétés des ensembles d'ordinal aleph_2 invariantes par forcing(une sorte de forcing sur l'ensemble des forcing possibles(ou plutôt des extensions génériques possibles)).

Après avoir dit autant de bêtises, je vais me coucher.

a+

christophe c · July 2009

Bon rien à voir mais puisque j'ai reçu ce post par mail, j'en profite pour faire remonter à qui se reconnaitra (pas toi, mais le gars avec qui on vient de se bourrer la gueule autour de tapas et qui m'a expliqué c'est quoi le critère d'Abel...

Je suis bien convoqué à 11h, donc pas à 8H ouf (lever pas si matinal)

à Gilou: bon, bin t'as fait le tour des infos médiatiques que je connais, précision: les cardinaux de Woodin sont plus faibles que les supercompacts et donc supercompact ---> tout ce que t'as dit à propos de AD.

Le programme Woodinien autour du rebus:

Peano est aux entiers ce que détermination projective est aux réels ce que ??? est à H2, je ne le connais plus trop en détails, surtout ce soir lol mais je sais que la recherche concernant ??? se situe beaucoup autour de la omegaconjecture. Je demanderai à BV les détails et te répondrai en détails à partir de lundi pas avant...

De "Woodin" à Kunen il y a: strongly compact (qui permettent de faire de l'analyse non standard avec $<kapp$ plutot qu'avec fini; puis supercompact puis extendible, puis Vopenka conjecture puis Huge; puis n-Huge puis des trucs artificiels consistant à affaiblr un tout petit peu Kunen pour éviter la contradiction (pour l'heure). Le plus trippant c'est la Vopenka conjecture

Pour l'idée d'un livre, j'ai l'éditeur, me reste plus qu'à trouver "l'équilibre" (c'est le plus dur) et oui si tu veux fouiller un peu ce long fil et scriber avec grand plaisir, mais comme tout ce que je commence, c'est devenu un peu le bazarre dans les posts.

A mon avis un livre sur le forcing seul n'est pas pertinent (vu le marché) mais un livre sur "les objets virtuels en mathématiques" l'est plus: avec ultrafiltres, forcing, Correspondance de CuHO, mécanique quantique et jeux (AD stratagies, etc). Tous ces thèmes ont en commun qu'ils font appel à des "éléments" inexistants qui apportent des théorèmes comme s'ils existaient et chaque fois c'est le même mode de fonctionnement, et là, oui, à partir de L3 ou master ça peut intéresser du monde et sortir les gens de leur calculette pour les réconcilier avec leur cerveau...

Bon, vue l'heure faut que je me couche, demain, je suis sensé montrer des trucs comme "je sais calculer "sin(1)+sin(2)+...sin(n)"

et ça c'est beaucoup plus dur...

deufeufeu · July 2009

christophe: tu es au courant des travaux de jean-louis sur le lien entre forcing et réalisabilité.
Le truc est qu'il y a une grosse théorie qui s'exprime assez bien, et en rajoutant des contraintes on retombe sur le forcing ou sur la réalisabilité classique standard. Si tu voulais écrire un bouquin, ce genre d'approche un peu novatrice serait la bienvenue.
Il me semble qu'il en parle, entre autres, dans cet exposé http://www.pps.jussieu.fr/~krivine/articles/Brasilia.pdf . Malheureusement, j'ai du partir du Brésil avant d'avoir pu l'écouter, ma femme étant sur le point d'accoucher (j'ai d'ailleurs bien fait, car arrivé jeudi après-midi, le bébé est arrivé vendredi soir o_O)...

AD · July 2009

Bonjour Deufeufeu

Bravo à l'heureux papa, toute mes félicitations à la maman et une caresse au nouveau venu.

Alain

ev · July 2009

Félicitations.

Waouh, Jet lag + Bébé, tu cumules ! Tu arrives à faire tes nuits au moins ?
Je ne peux pas résister à faire cette blague de logicien :
C'est un garçon ou une fille ?

amicalement,

e.v.

deufeufeu · July 2009

C'est un garçon et j'ai déjà une fille de 21 mois. En bon logicien je dirais que la seule chose que cela prouve c'est qu'on a une inclusion $\{garcon,fille\}\subseteq Types(Enfant)$.
Sinon pour le jet lag, j'ai eu droit à une vraie nuit de sommeil le jeudi soir (enfin avec réveil à 6h40 parce que quand même il y avait ma fille). Sinon effectivement, je dors peu, mais j'ai pas mal de livres sur les catégories sur ma table de chevet, c'est très efficace pour faire des micro-siestes. Deux diagrammes et hop, je ronfle.

P.S. : parler de ce genre de choses sur un fil de christophe, c'est l'arroseur arrosé

ev · July 2009

Tssk deufeufeu,

Question: C'est un garçon ou une fille ?
Réponse: Oui.

Un grand classique, tu dois avoir un coup de mou (ou pas trop la tête à ça...)

amicalement,

e.v.

deufeufeu · July 2009

ev: désolé je suis intuitionniste de naissance. Pour moi un ou a nécessairement la propriété de la disjonction

christophe c · July 2009

Bravo, les nouveaux nés d'aujourdh'ui connaitront l'avèneent des mondes parallèles, quelle chance...

Sinon, pour les trucs de JLK je n'i pas cliqué (mon ordi là ne me le permet pas bien, je suis pas habitu au tableau ou on frotte pour faire office de souris, mais je le ferai à mon retour... Mais je pense deviner de quoi il s'agit, s'il n'a pas écris un tout nouveau truc récent (moins de 3 mois)

Effectivement, ça englobe forcing et réalisabilité d'un coup... Mais ç quelques petites nuances près et je suis pas trop daccord avec JLK sur sonrefus des ordinaux (mais je détaillerai), qu'il ne veut pas mettre à part et que du coup ca le fait galérer pour réaliser l'axiome du choix général. "Admettre" les ordinaux donne plus de jus et réalise AC avec son horloge habituelle (mais j'y reviendai en détails) mais il veut pas, parce qu'il veut plus ne pas mettre à part l'extensionnalité, parce sans l'extensionalité, pour lui, on trouve "le réseau" et que ça le fascine.. Mais la je peux pas detailler, je suisà l'hotel on a bu des bieres et faut que j'aille voir q quelle heure je suis convonqué demain pour camL (jcrois c aux aurores) et que je couche dns pas trop lgtps... Bon bin j'irai à la "modelisation" (pff pff) sans avoir jamais reboote sur le CD, ce sera l'avnture (bien que snif, il est la le CD sur ce propre ordi, mais javoue que j'ai un peu la flemme... pourtant y pas canalplus alhotel)

Sigma=espsilone · July 2009

Christophe, ton forcing est forcée

christophe c · July 2009

Sigma=espsilone
Re: le forcing expliqué aux matheux ordinaires
il y a treize minutes

Christophe, ton forcing est forcée

C'est quoi ce post???? Un message secret? Pourquoi "éE" à la fin? Je suis pas cryptologue

gilou1 · July 2009

Felicitations pour deufeufeu,

très bonne idée d'étendre le livre aux "objets virtuels", ce projet m'intéresse beaucoup, j'essaierai de "remettre au propre" tes différents posts pendant les vacances.

à la prochaine.

christophe c · August 2009

Bonne idée Gilou...

Bon je ne pense pas en avoir parlé dans les (nombreux) posts précédents, alors j'écris (on est tôt le matin) une preve-construction complète d'un mécanisme assez spécial qui marie forcing-détermination-axiome du choix.

Il s'agit de la pièce manquante du puzzle que la recherche ensembliste ne peut pas, à l'heure actuelle, prendre en compte car elle est est paralysée par son acceptation des maths "classique" et de la déontologie traditionnelle qu'on trouve hors-logique, celle consistant à voir toutes les contradictions comme des terminaisons définitives.

Comme je l'ai rappelé plusisuers fois, il est "bien connu" (disons que c'est un exercice classique pour débutant en th des ensembles qui veut démarrer, par exemple, une thèse) que ZF+AC+AD est contradictoire. Hélas, ce rappel est toujours expédié d'un revers de la main, sans approfondissement, car de "tout", on ne cherche généralement pas à déduire "finement" quelque chose de particulier. (On a tout, on expédie les choses en disant "donc X")

Les ensemblistes ignorant généralement à peu près tout de la correspondance de Curry Howard et réciproquement (souvent les correspondants de CuHo étant plutôt "informaticiens" dans l'âme, les méandres de l'infini leur apparaissent comme d'insondables mystères), la contradiction précédente reste posée là dans les archives sans être creusée.

C'est dommage: certes, en th des ensembles il y a quand-même une théorie contradictoire qu'on accepte de voir comme "plus intéressante" que les simples théorèmes de maths, à savoir la borne de Kunen, mais ça ne va pas bcp plus loin et surtout ne concerne pas vraiment $AC+AD\to tout$ qui est une autre affaire (à bas niveau: réels et entiers)

La construction suivante (résumée) prouve "tout" dans une théorie formelle mais non précisée (suffit d'inventorier les axiomes utilisés) sans être vraiment contradictoire (ce qui est un comble et un "way to paradise")

En fait, elle livre un programme qui ne boucle pas, mais ne termine jamais quelle que soit la mémoire (finie ou même infinie quelconque qu'on donne à la machine. A priori ça ne devrait pas être possible (ie ou bien l'exécution du processus ne converge pas (non arrêt), ou bien il converge, ou bien il déclenche une exception "over stack memory")

C'est le forcing qui permet d'établir que le processus converge.

Et c'est l'une (des innombrables) des preuves de $AD+AC\to tout$ qui déclenche "over stack memory" QUELLE QUE SOIT LA MEMOIRE FOURNIE AU PROCESS, même infinie, même en lui donnant tous les ordinaux qu'il demande comme places mémoires.

Ce que j'écris now est très classique, mais tourné de manière à mette en relief ce qui précède.

On suppose donné un couple $(T,k)$ où $T$ est une application injective de $k$, qui est un ordinal, dans $\R:=2^\N$

On va construire une réel $x$ qui n'est pas dans l'image de $T$. Avant toute chose, on prend le plus petit ordinal $m\leq k$ tel qu'il existe un procédé (tout sera précisé) construisant une surjection $s$ de $m$ sur $k$ à l'aide du couple $(T,k)$. Sans perte de généralité(***), on suppose que $m=k$ puisque sinon, on ferait la construction qui suit avec $(D,m)$ où $D(i)=T(s(i))$ pour tout $i<m$ et le $x$ obtenu conviendrait pour $(T,k)$. En particulier $k$ est un ordinal limite.

Dans la suite, je résume le prochain post (qui donnera le procédé effectif):

soit $W$ un filtre non trivial sur $k$, stable par intersection dénombrable, tel que
1) pour tout $i\in k$: l'ensemble des ordinaux de $k$, qui sont $>i$ est dans $W$
2) pour tout entier $n\in \N$, il existe $j\in 2$ tel que:
$\{i<k/T(i)=j\}\in W$

exercice: pour chaque entier $n$, le $j_n$ précédent est unique. Soit $x$ le réel $n\to j_n$.

Si $\forall i<k: T(i)\neq x$, on a fini, sinon, notant $a$ tel que $T(a)=x$:

EDIT: j'ai sauté un épisode, je réécris:

Soit $A_n:=$ l'ensemble des $i<k$ tels que $T(i)(n)\neq x(n)$

Noter que la réunion des $A_n$ contient tous les $i<k$ sauf $a$. Par ailleurs, le complémentaire de chaque $A_n$ est dans $W$. Contradiction.

Il reste donc à trouver un filtre $W$ qui fait l'affaire (prochain post)

christophe c · August 2009

Pour fabriquer $W$, on a l'embarras du choix, si on admet AD. C'est d'ailleurs pour ça que la contradiction AC+AD est considéré comme un exercice (puisqu'il y a moult solution, toutes courtes).

Je vais en présenter une qui est un peu plus longue, mais qui a le mérite de ne pas être sensible à "beaucoup" de propriétés de la continuité (et qui pourra être étendue de manière algébrique).

Voici le lemme (présenté de manière volontairement un peu étrange, c'est dû au conflit entre AD et AC, pour préserver ce qui est "effectif"):

Soit $E$ un ensemble de réels et $R$ une application de $E$ dans $\N$. (C'est là "l'étrangeté", on ne suppose pas que $E=\R$). De plus, si $x\notin E$, on prolonge $R$ à $x$ en déclarant $R(x)=-1$

A la fin on obtient une application, encore notée $R$ qui va de $\R$ dans $S:=\N\cup \{-1\} $.
Lemme: il existe un unique élément $n$ de $S$ tel qu'il existe une application continue $f$ de $\R$ dans $\R$ telle que:

$\forall x\in \R:R(x)<R(f(x))$ ou $R(x)=R(f(x))=n$

Exercice: construite $W$ à l'aide du lemme avec $E:=Im(T)$

christophe c · August 2009

Avant de continuer, pour que ça ait un intérêt, et en espérant ne pas en avoir déjà parlé, quelques mots sur les ultrafiltres et leur complexes et affectives relations avec AD et AC.

AC entraine que tout filtre peut être prolongé en un ultrafiltre

AD, lui au contraire entraine que tout ultrafiltre est stable par intersection dénombrable. MAIS:

AD entraine qu'il y a quand-même TOUT PLEIN d'ultrafiltres (et ils sont tous essez géniaux à vrai dire) non principaux.

Pour prendre la mesure de ce spectacle, il faut savoir qu'en présence d'AC, tout ensemble muni d'un ultrafiltre (non principal) stable par intersections dénombrables est supersupergrand.

C'est l'axiome (voir quelques posts avant) "il existe un cardinal mesurable"

Voici le plus célèbre de tous les "ultrafiltres" non principaux et stable par int.den: soit om1 le premier ordinal non dénombrable, et soit F le filtre engendré par les ensembles qui sont non bornés dans om1 et qui sont stables par borne sup (ie si une suite croissante est dans X alors sup(u) est dans X)

A priori (en présence de AC) ce filtre est un petit filtre. Et bien en présence de AD, ce filtre est un ULTRAFILTRE

exercices:

1) prouver que F est un filtre
2) avec AC prouver que F n'est pas un ultrafiltre
3) (je le corrige après): prouver que AD implique F est un ultrafiltre

christophe c · August 2009

Dans ce post, j'illustre 2 des annonces précédentes:

Pour prendre la mesure de ce spectacle, il faut savoir qu'en présence d'AC, tout ensemble muni d'un ultrafiltre (non principal) stable par intersections dénombrables est supersupergrand.

On note $T(E)$ l'ensemble des ultrafiltres stables par intersections dénombrables et $Tr(E)$ ens des ultrafiltres sur $E$ qui sont principaux (ie triviaux, ils sont de la forme "profil(x)" en notant profil(x) l'ensemble des parties de E qui contiennent x)

On montre que si $E$ n'est pas "très gros" alors $T(E)\subseteq Tr(E)$

Comme la notion ne dépend que du cardinal de $E$, on considère le plus petit cardinal possible (CM) pour un éventuel contre-exemple

Soit $E$ de cardinal inférieur à CM. Soit U un élément de $T(P(E))$. Soit $A$ la partie de $E$ qui contient les $x\in E$ tels que "pour presque tout $B$ modulo U, $x\in B$

(AC): soit $ f : P(E) \to E $ telle que pour tout $X\neq A$, $f(X)$ est dans la différence symétrique de $A$ et $X$. L'ultrafiltre image de U par f est dans $T(E)$. Il est donc principal de la forme $profil(a)$. Supposons que pour presque tout élément B modulo U on ait $B\neq A$. Alors pour presque tout élément $B$ modulo U, $f(B)=a$.

Cela impliqurait que $a$ est dans la différence symétrique de $B$ et $A$ pour presque tout $B$ modulo A, contradiction.

Donc $U=profil(A)$.

Conclusion: si E est trop petit, alors $P(E)$ aussi. Il s'ensuit que $\R$ et trop petit, $P(\R)$ aussi, etc etc.

Dans l'autre sens, ne supposons plus AC, mais AD. En particulier, tous les ensembles sont Lebesgues-mesurables et ont la propriété de Baire. En fait, la plus faible des 2 conséquences est celle consistant à supposer que tous les ensembles ont la propriété de Baire (il me semble me rappeler qu'elle n'est pas plus forte que ZFC, en consistancy strength)

On quotient $\R$ par $x==y$ ssi $x-y\in \Q$, pour obtenir un ensemble quotient $E$. Et on regarde $T:=$l'ensemble des parties de $E$ dont l'image réciproque par la projection canonique est complémentaire d'un ensemble maigre (inclus dans une réunion dénombrables de fermés d'intérieur vide)

Exercice: $T$ est un ultrafiltre stable par intersection dénombrable sur $E$.

Conclusion: autant "il existe un ultrafiltre stable par intersections dénombrables" n'est pas un énoncé très fort sans AC, autant supposer AC le rend "explosif et superpsuissant"

FrançoisD · August 2009

Salut,

juste un retour sur une définition qui me manque : quel sens donnes-tu à "plus faible que" ou "plus fort que"?
En quoi ton "ultrafiltre stable" obtenu via ZF-AD (il n'y est pourtant pour rien le pauvre! ;-p) dit-il que "[ZFC] est explosif et superpuissant"?

Allez, une dernière, ce fameux quotient E peut-il être colorié? et si oui combien de couleurs faut-il? je crois que là aussi c'est AC ou non qui rend la chose intéressante... (si quelqu'un peut me préciser les tenants et les aboutissants de ce truc,merci)

Amicalement,

F.D.

christophe c · August 2009

Dans le "paradigme" présent, (comparaison de "la force" des axiomes), les gens utilisent généralement:

"X" est plus fort que "Y" quand on peut prouver "ZF+X" entraine la consistance de "ZF+Y" (ou même sans être dans ZF)

Par exemple, la théorie:

"Peano +l'équation diophantienne Matiasevicienne qui a des solutions ssi ZF+AD est contradictoire n'a pas de solutions" est une théorie plus forte que ZFC (très largement) et pourtant ce n'est qu'une théorie arithmétique (Peano) à laquelle on a rajouté un seul "petit" axiome: $\forall x_iP(..x_i...)\neq 0$ avec le bon polynome $P$ à coefficients dans $\Z$.

Sur l'ultrafiltre c'était juste un commentaire:

ZF+AC+il existe un ultrafiltre stable blabla est une théorie très forte dans le sens précédent

et "ZF + AD" implique il existe un tel ultrafiltre.

Par ailleurs "ZF+AD+AC" implique tout, donc tu as peut-être mal lu où j'ai mal écrit: ce n'est pas ZFC seul à priori qui est superpuissant.

Quand j'écris (maladroitement) la phrase $A$ rend $T$ superpuissant ça veut vaguement dire "T+A" est superpuissant.

[size=x-small]En l'occurence là, une même notion (ultrafiltres blabla) intervient de manière continuelle dans les 2 théories "ZFC" et "ZF+AD" et "l'affaiblissement" de la th contradictoire de "ZF+AD+AC" en "ZF+ultrablabla+AC" fait descendre de "tout" à "puissant". Et disons que je milite pour étudier ça de manière "non discrète" (je pense qu'il y a un "fil" un peu magique qui mène de "rien" (le vrai) à "tout" (le faux), qui pourrait bien être muni d'une "topologie" qui le rend "connexe", et donc une contradiction un peu magique.[/size]

Qu'entends tu par "colorié"?

FrançoisD · August 2009

Si je me rappelle bien,

le graphe E (car il s'agit d'un graphe dont les sommets sont les classes d'équivalence et les arêtes, euh...?) admet 2 couleurs (ZF+AC) ou une infinité (ZF + moins que AC). Je n'ai pas trouvé de "vraie" publi là-dessus, je voulais juste savoir si ce résultat pouvait être lisible (si je dis "accessible" on va repartir en live) pour moi et, éventuellement, des élèves de TES.

Amicalement,

F.D.

christophe c · August 2009

Donc on dans E=R/relation x-y est dans Q c'est ça????

Bin, je vois pas trop ta question, si on ne s'occupe pas d'autre chose qu'un ensemble, on a juste un ensemble, donc pas question de colorier quoique ce soit sans arête...

AC n'intervient pas spécialement..

Par contre, tu veux peut-être parler de R et les arêtes seraient alors données par la rel d'eq?

Bin avec la definition aretes entre chaque x et x+un rationnel, il est coloriable avec des entiers (chaque classe est dénombrable) et sinon on peut pas faire mieux que le colorier avec le cardinal de IR comme nombres de couleurs (puisqu'il y aura une clique de cardinal IR, en prenant un élément dans chaque classe, ils seront 2 à 2 reliés)

Sans AC, on peut colorirer le 2ième graphe (à chaque x on lui donne la couleur x, en cardinal, ce n'est pas moins bien que le premier), quant au premier graphe, on ne peut pas faire mieux que le colorier avec IR couleurs aussi à priori, enfin je pense, faudrait que j'y réfléchisse plus longuement. Sous AD, il y aurait une grosse couleur* (ie un ensemble A de mesure non nulle dont tous les elts la recevrait), or sous AD, tous les ensembles sont Lebesgues mesurables donc A-A contiendrait un voisinage de 0 et donc un rationnel, contradiction.

Après tout dépend ce qu'on appelle couleur, sans AC, c'est sensible. Sous AD, par exemple, pour toute application de IR dans les ordinaux quelle qu'elle soit, l'un des singletons a une image réciproque de mesure non nulle à cause de Fubini

Mais présenter ça à des enfants (enfin des TES) me parait difficile, à cause que c'est entièrement une gestion de divers infinis (ils ne sont pas très ladedans en TES)

christophe c · August 2009

[size=small]Ah je rappelle une lemme qui me semble succulent et surement bien connu des analystes

Si A est une partie de $\R ^n$ de mesure non nulle alors $A-A:=$l'ensemble des $x$ tel que il existe un élément $e $ dans A avec aussi $x+e$ dans A est un voisinage de $0$

preuve: sinon, il existe un $e$ superproche de $0$ (donc une infinité dans tout voisinage) tel que $A$ et $A+e$ sont disjoints, ce qui limite la mesure de A inter une boule de mesure1 à ne pas dépasser, 1/2, mais en fait on peut recommencer le raisonnement astucieusement** plein de fois et limiter la mesure de A par le nombre positif qu'on veut (vu le fil je ne détaille pas).

** (si A est de mesure non nulle, il existe une boule B ou mesure de A/mesure de B>0,7, par exemple)[/size]

[size=large]Du coup, en présence de AD TOUT ensemble inclus dans $\R^n$ est tel que lui ou son complémentaire a cette propriété[/size]

FrançoisD · August 2009

Salut,

de mémoire on peut prouver ça avec de l'intégrale de Lebesgue (preuve faite en exo à l'oral de l'agreg lol)

F.D.

christophe c · August 2009

lol (ra mais t'es méchant de me taquiner comme ça avec des invitations aux calculs

-D ), oui j'imagine qu'on peut prendre la fonction caractéristique f de A et considérer les intégrales $\int f$ et $\int (f+\epsilon)$ (1), vers la conclusion (mais pour $\R^n$, je préfère m'imaginer le truc à l'artisanale, quand de tps en tps un truc "me parle", si fallait que je fasse (1) avec des intégrales multiples snif.....

De toute façons, quand on pense à AD, c'est aussi bien de savoir que tout ensemble mesurable ([size=large]donc tout ensemble[/size]) a des grumeaux (ie ya des boules B où mesA/mesB proche de 1 et des boules B où mesA/mesB, bref que le paysage est montagneux...)

FrançoisD · August 2009

Salut,

en fait on utilise le produit de convolution $1_A*1_A$ est on peut montrer que ce truc est $L^2*L^2$ donc $C^0$ bof, c'est pas si méchant mais ça pète sa race à l'oral lol

F.D.

christophe c · August 2009

Oui, lol c'est bien pour ça que j'y suis un peu allergique à ces trucs qui pètent leur race de concours, faudra que je retrouve le lien de DF, avec le "benzin" je crois qui pète la race de tlm

D'ailleurs, je t'avoue que je ne capte pas trop ce que tu as dit, qui est C0, L2 et en quoi ça implique que A-A est un voisinage de 0 plus que juste ce que j'ai dit avec intA et int(A+epsilon)? mais c'est un peu trop savant, retour demain j'y verrai plus clair..

remarque · August 2009

Christophe, je te détaille l'argument pour que tu puisses dépiauter tranquillement les axiomes mis en jeu. C'est en fait assez indirect.

1. Par l'inégalité de Hölder, si $f\in L^p$ et $g\in L^{p'}$ (avec $\frac1p+\frac1{p'}=1$), alors $f\star g\in L^\infty$ avec $\|f\star g\|_\infty\le \|f\|_p\|g\|_{p'}$.

2. Les fonctions continues à support compact sont denses dans tous les $L^p$, $p<+\infty$. Donc si $1<p<+\infty$, alors le 1. implique en fait que $f\star g$ est une fonction continue.

3. On applique ça à $f=\mathbf{1}_A$, $g=\mathbf{1}_{-A}$, avec $\mathrm{mes}\,A<+\infty$ (si la mesure est infinie, on enlève ce qu'il faut pour arriver à un ensemble de mesure finie, non mais sans blagues). Ils sont donc par exemple dans $L^2$, et on en déduit que $\mathbf{1}_A\star\mathbf{1}_{-A}$ est une fonction continue.

4. Un petit calcul, là on n'y échappe pas, montre que $\mathbf{1}_A\star\mathbf{1}_{-A}(x)=\mathrm{mes}(A\cap(x+A))$.

5. Si $\mathrm{mes}A>0$, alors $\mathbf{1}_A\star\mathbf{1}_{-A}(0)>0$.

6. Comme cette fonction est continue, elle reste strictement positive au voisinage de $0$, en particulier $A\cap(x+A)\neq\emptyset$ au voisinage de $0$.

C'est astucieux et joli, mais on ne voit pas vraiment la propriété ensembliste de la mesure qui fait marcher l'argument.

christophe c · August 2009

Merci beaucoup remarque, j'ai compris les enchainements, et je pense que je peux voir de manière presque formelle la partie admise sur le produit de convolution (alala tout ce que j'aurais à apprendre...).

C'est vrai, que du coup, c'est tellement embouteillé dans des outils forts que la conclusion tombe sans trop permettre de voir "où" ça se passe.

De plus, ça "fait peur" pour un gars comme moi d'essayer de plagier un tel argument dans $\R ^n$ (même si je veux bien croire qu'il s'y trouve aussi un sorte de convolution), mais en tout cas je suis sûr que la "convolution" doit se réinventer à chaque fois (puisqu'il faut que l'espace de départ (le mesuré) ait une addition.

D'une manière ensembliste et sans aucune intégrale, on peut passer par un lemme (facile) qui dit que si A est de mesure non nulle alors il existe une boule P(ou un pavé ou un convexe, bref, un peu ce qu'on veut d'un peu "rond") avec mes(A)/mesure(P)>0,8 par exemple, et ça entrera très vite en conflit avec le fait que $C:=A \cap P$ serait tel que $C$ et $C+\epsilon$ seraient disjoints pour $\epsilon$ très petit

christophe c · August 2009

Je ne serais pas étonné d'ailleurs que si on enlevait toutes les notations et dépliait tout, on verrait en fait la même preuve avec des mots différents, ici, enfin il me semble

remarque · August 2009

C'est déjà dans $\R^n$.;) En fait, tu as une convolution dans tout groupe localement compact, mais je ne me rappelle pas si on a les mêmes propriétés au niveau des espaces fonctionnels que dans $\R^n$.

christophe c · August 2009

Merci, ouii, j'imaginais un peu "somme_t des f(t)g(a-t)" mais ça me faisait un peu peur à vrai dire.. Il suffit d'avoir un signe "-", dans la notation précédente.

C'est "puissant" (le mot est mal choisi, peut-être veux-je dire "exportable") la notion de convolution, je veux dire y a un énoncé court ne contenant presque pas, voir pas du tout de théorie de la mesure, et qui se démontrerait à coup de convolutions?

Je dois avoir un livre la dessus, faudra un jour quand-même que j'essaie de les lire

christophe c · August 2009

Bon, je reviens sur la lancée initiale d'il y a quelques posts (ultrafiltre, AC, AD)

Soit OM le premier ordinal non dénombrable. Soit Club l'ensemble des parties P de OM qui sont non bornées et fermées*

* pour tout A, si A inclus dans P alors sup(A) appartient à P

En présence de AC, la coutume "didactique" est de dire que ce filtre est un "petit" filtre sur OM qui ressemblerait un peu au filtre de fréchet sur $\N$ (enfin de loin). En présence de AD, c'est un ultrafiltre

Avant de prouver que AD--->c'est un ultrafiltre, voici un jeu, qui permet, en supposant AD(OM) de prouver que c'est un ultrafiltre "sans peiner". Rappel: AD(E) dit que tous les jeux, où les joueurs jouent leur coups dans E sont déterminés. AD est l'abréviation de $AD(\N)$

Soit W une partie de OM. Description du jeu $G_W$:

les joueurs jouent alternativement des ordinaux de plus en plus grands. A la fin de la partie, ils ont produits une suite $u$ str croissantes d'ordinaux dénombrables. On regarde la borne sup s de cette suite: si elle est dans $W$, "impair" est déclaré gagnant et sinon c'est pair qui gagne.

Ce jeu est bien parce qu'il correspond le plus naturellement du monde à des activités humaines, une sorte de course où les 2 adversaires sont attachés, l'un essayant d'aller dans W, l'autre essayant de l'en empécher.

exercice: supposons que impair ait une stratégie infaillible. Prouver qu'alors $W\in Club$. Prouver que si c'est pair, par contre, qui a une stratégie infaillible, alors $OM-W\in Club$

Conclusion: $AD(OM)$ entraine que Club est un ultrafiltre

Exercice: montrer que le filtre $Club$ est stable par intersections dénombrables

Que se passe-t-il en présence de AC? Pour toute ordinal $a\in OM$, il existe un injection $f_a$ de $a$ dans $\N$

Soit alors $a\in OM$: il existe forcément un entier $p_a$ tel que l'ensemble $Y_a$ des $b\in OM$ tels que $b>a$ et $f_b(a)\neq p_a$ n'est pas dans $Club$. L'application $g:a\to p_a$ est une application de $OM$ dans $\N$. $g$ n'étant pas injective, il existe $a,b\in OM$ tels que $g(a)=g(b)$

Il s'ensuite que ni $Y_a$, ni $Y_b$ ne sont dans $Club$. Or leur réunion contient l'ensemble des $c\in OM$ qui sont $>$ à $a$ et $b$.

$Club$ n'est donc pas un ultrafiltre.

Exercice: il reste à voir pourquoi $AD(\N)$ suffit à obtenir que $Club$ soit un ultrafiltre (plutôt qu'un recours à $AD(OM)$; mais je voulais donner l'idée (extrêmement naturelle))

christophe c · August 2009

Rapport avec l'informatique et preuve du dernier point:

prenons la camL, mais implémenté sur une machine qui dispose de cases mémoires numérotées par des entiers. Autrement dit pas de limite finie, une quantité dénombrable de ressources.

Dans ce post (comme à peu près dans tout le fil), les réels sont des applications de $\N$ dans $2$, ie des suites de "0";"1" (on identifie 0 à false et 1 à true)

On va s'en servir comme des oracles.

Un réel $x$ est dit plus fort qu'un réel $y$ s'il existe un programme f:real * int->bool en camL (je l'ai choisi arbitrairement, pour l'exemple) tel que pour tout entier $n$: en lançant: f x n, le programme termine et renvoie comme valeur y(n)

L'emplacement rouge signifie qu'on utilise x comme oracle.

C'est un préordre évident, et ses classes modulo $x\leq y \ et\ y\leq x$** sont appelées "degrés de Turing". ** cette relation d'équivalence est notée "==".

On regargde ce qui se passe dans $E:=\R / ==$.

Soit $A$ une partie de $E$. Le jeu $G_A$ est défini de la manière suivante: les joueurs jouent alternativement des 0 et de 1, produisant un réel $z$. On regarde si $classe(z)\in A$. SI oui, impair est déclaré gagnant, sinon c'est pair.

Théorème amusant: si impair a une stratégie infaillible alors il existe un degré $d\in E$ tel que tout degré $e\in E$ qui est $\geq d$ est forcément dans A. Version duale, si c'est pair qui a une stratégie infaillible (ie $\exists d\in E\forall e\in E:e\geq d\to e\in E-A$

preuve: soit $d$ le degré de la stratégie infaillible $s$ de impair, supposée exister. Soit $e$ un degré $\geq d$. Soit $x$ un réel tel que $Classe(x)=e$. Voici comment le joueur pair peut jouer contre impair: ses digits impairs, il produit la description de $s$ et ses digits pairs, il produit $x$. Pendant ce temps, le joueur impair lui répond en suivant les recommandations de $s$.

exercice: la partie produite $y$ est telle que $y==x$ (faire 2 programmes en camL.. qui en attestent)

Puisque $s$ est infaillible, $e=classe(y)\in A$, CQFD

Bilan: soit $F$ le filtre sur $E$ engendré par les "cones" $C_a$ de la forme $\{d\in E / d\geq a\}$. D'après ce qui précède, $F$ est un ultrafiltre (si on suppose AD)

Etant donné un réel $x$ il existe un certain nombre de bons ordres sur $\N$ (donc des parties de $\N ^2 $ ) qu'on peut programmer en utilisant $x$ comme oracle. Ils sont tous pour chacun isomorphes à un certain ordinal dénombrable et la borne sup de ces ordinaux "réductibles" en quelque sorte à $x$ est notée $puissance(x)$ (provisoirement)

exercice: prouver que l'image de l'ultrafiltre $F$ par "puissance" est $Club$ (ce qui fait de Club un ultrafiltre..)

Remarque: il n'est pas facile de créer "humainement" des réels puissants, of course. En fait, humainement, on ne va pas bien loin, puisque tous les bons ordres qu'on peut fabriquer sont "équivalents" et obtenus à partir du degré de Turing 0, puisqu'ils sont récursifs (un bon ordre récursivement énumérable est évidemment récursif).

Ca n'enlève pas l'intérêt de ce jeu (fabriquer des "ordinaux" à la main, qui bien sûr seront dénombrable, mais on peut essayer de les faire monter haut)

Une façon universelle de procéder est de fabriquer un arbre bien fondé (ou non d'ailleurs): ie une ensemble de suites finies d'entiers $T$ tel que pour aucun suite infinie $u$ on ait $\forall n\in \N: u/n\in T$, en notant $u/n$ la restriction de $u$ à $n$.

Même si $T$ est mal fondé (il peut y avoir une ou des suites $u$ comme ci-dessus), il y a quand-même un niveau ordinal de $T$ qui est donné par. On essaie toutes les suites (dans l'ordre lexicographique, avec des demi-tours quand blocage) et ou bien on arrive "en haut" de l'arbre (il est alors bien fondé) ou bien on arrive "à droite" de l'arbre (je le représente couché: racine à gauche) à l'issue du parcours de sa "première branche". Dans les 2 cas, on s'est promené pendant un "temps ordinal" et à la fin on a un ordinal canonique associé au parcours de l'arbre.

Voilà pourquoi certaines démonstrations m'intéressent, comme par exemple Jacobson. Il lui correspond un arbre naturel:

en gros on se place dans les axiomes d'anneau (quelconque, pas commutatif), ie même $\Z[a,b]$ à 2 indéterminées. On "suppose" que $ab\neq ba$, et on parcourt l'arbre qui exige qu'on précise qui est "égal" à qui dans tous les polynomes. De plus, on doit dès le départ de chaque sous-parcours du polynome $P$ préciser $n$ dont on prétend que $P^n=P$ (ces arbres sont intéressants en ce qu'ils sont à branchement infinis bien sûr, sinon... Lemme de Konig)

D'après Jacobson, on ne va jamais arriver à droite, mais on arrivera en haut de l'arbre en le parcourant entièrement. Et bien sa "hauteur ordinale", j'aimerais bien l'évaluer. Vaut-elle $\omega$; $\omega ^4$; $\omega ^{\omega ^\omega}$?

Plus elle sera haute, plus le théorème pourra être déclaré "profond".

christophe c · August 2009

Bon, je suis sûr, vraiment sûr que j'en ai déjà parlé (mais un peu vite?) dans le fil à la page je ne sais combien, mais j'y reviens, car occasion immanquable de faire cette remarque, à propos de degrés de Turing

Ils offrent, particulièrement dans le contexte précédent, une porte sur la compréhension du phéomène sexuel (dans le sens de la reproduction et de la génétique).

Il est bien connu (Godel, Tarski, and co) qu'un réel $x$ ne peut pas "connaitre" son "ensemble vérité" (ie l'ensemble des énoncés de $(\N;+;\times ;0;1;x)$ qui sont vrais de manière calculable. S'il est seul c'est désespéré.

La question est: peut-il y avoir 2 réels tels qu'en se "mariant", de leur mariage éclot un programme qui donne l'ens-ver de chacun?

La réponse est FORTEMENT oui, et ce n'est qu'un cas particulier du post ci-dessus avec la fonction $x\to ensverite$ de $x$, mais qui marche avec toute fonction.

Définition: le mariage de x et y est le résultat de l'opération qui les met ensemble de la manière la plus bête du monde: $mariage(x,y):=x_1;y_1;x_2;y_2;...$

Exercice (AD): prouver le théorème suivant

Si $f,g$ sont 2 applications de $\R$ dans $\R$ il existe 2 réels $x,y$ tels que le degré de Turing d du mariage de x et de y contient à la fois $f(x)$ et $g(y)$.

L'égalité ou non de f,g ne joue aucun rôle et $f$ peut représenter les rêves des femmes et $g$ ceux des hommes.

Cas particulier annoncé obtenu avec $f:=g:=x\to ens.verite(x)$

christophe c · August 2009

DIgression rapide: dans un autre post, je viens de m'apercevoir qu'on peut "satisfaire" des demandes "rigides" (ie sur des trucs d'algèbres que l'humain ne peut pas "décider" avec des axiomes) en utilisant le forcing.

http://www.les-mathematiques.net/phorum/read.php?3,535873,536266#msg-536266

C'est donc l'occasion de présenter un itinéraire un peu hallucinant (puisque contradictoire), mais néanmoins utile (d'où d'ailleurs l'illustration que les théories consistantes sont une restriction un peu débile dans les maths)

Soit $(P, \leq ) $ un ensemble ordonné. La théorie du forcing consiste à rajouter, comme déjà dit au début du fil une partie "magique" $G$ de $P$ qui a les 2 propriétés "contradictoires" suivantes:

1) $G$ est filtrant: si $p,q\in G$ alors il y a dans $G$ un élément $r$ tel que $p\leq r$ et $q\leq r$
2) $G$ rencontre tous les ensembles denses (ceux de l'univers), ie pour tout $D$ dense inclus dans $P$, $D\cap G\neq \emptyset$

$D$ dense veut juste dire: $\forall p\in P\exists q\in

p\leq q$

La littérature sur le sujet retourne l'ordre par rapport à ce post, mais peu importe.

Of course, $G$ ne peut pas faire partie de l'univers puisque sinon, le complémentaire de $G$ serait nondense, et vue les définitions, $P$ aurait des propriétés spectaculairement faibles ($G$ étant filtrant, ça obligerait par exemple qu'il y ait un élément $p\in P$ dont tous les majorants filtreraient, ce qui arrive rarement pour les ordres intéressants).

Par contre, pour les "maths pratiques" (où l'utilisation de l'infini n'est pas trop sensible (les maths dénombrables ou calculatoires), on peut faire "comme si" $G$ existait vraiment. Par exemple, en ordonnant les familles libres d'un module ou d'un ev, on obtient des bases de l'espace entier ou des obstructions très visibles sur ce qui les empèche d'exister.

L'avantage de ce $G$ magique est qu'il existe un univers agrandi qui le contient et la théorie du forcing établit que la magie de $G$ ne détruit aucune des anciennes propriétés algébriques de l'ancien univers et même que le nouveau ne monte même pas plus haut ordinalement (ie on ne peut ajouter de suites descendante "magique" d'ordinaux" déjà mais même, ça ne crée aucun nouvelle ordinal ou "bon ordre" (à isomorphisme près). $G$ est donc "discret" dans son intrusion: en particulier, la base magique rajoutée implique l'existence d'une vraie base par exemple (sauf énorme tricherie sur les hypothèses)

L'ajout de $G$ ne "perturbe" que les propriétés "topologiques" des anciens espaces (par exemple il "tue" la compacité de l'ancien $\R$), mais pas les propriétés "définies" (le nouveau $\R$ est compact et l'ancien $\R$ devient juste un sous-corps du nouveau $\R$)

Les algébristes peuvent donc (plus que les topologues) toujours supposer que $G$ existe et jongler avec des $(P,<)$ astucieux

christophe c · August 2009

malentendu: "ne peut pas décider avec des axiomes" est ici utilisé dans le sens populare: ils ne peuvent "orienter" la vérité de l'énoncé à coup d'axiomes, ie sa vérité est "à découvrir" (exemple, les équa dioph qui ont ou n'ont pas de solution)

christophe c · August 2009

Fin de la digression : (je dois partir, mais vais y réfléchir):

exercice-question : Soit $A$ un anneau quelconque et $M$ un $A$module quelconque : on suppose que $M$ a une base générique. A-t-il forcément un vraie base ?

à mon avis "oui". Bon sujet de réflexion pour mon AR en train

[La case LaTeX. AD]

Toto.le.zero · August 2009

Va falloir que tu nous expliques un peu le sens de tes guillemets. Ma vision des choses: lorsque tu écris: bla bla bla "machin" bla bla bla, ça signifie que machin est situé dans un voisinage proche du concept censé seoir à ce qui est présent dans ta tête mais que tu ne peux approcher à moins d'$\varepsilon$ près.

En même temps, il est 3h du matin, et je n'ai plus les idées très claires

En espérant ne pas avoir dit trop de conneries.

christophe c · August 2009

à Toto: Oui, c'est à peu près ça.

Bon je reviens sur les derniers guillemets.

Dans à mon avis "oui"., je voulais dire que les modules exceptions doivent être plutôt tarabiscotés

Dans "ne peut pas décider avec des axiomes", justement j'y suis revenu, ce n'était qu'une citation (d'où les guillemets)

Dans ils ne peuvent "orienter" la vérité c'est pour dire que ce n'est pas comme l'axiome du choix par exemple, qu'on peut décider être vrai ou décider être faux selon qu'on le prend comme axiome ou non. l'affirmation que tout ensemble est mesurable par exemple, on peut "l'orienter"

Dans l'autre sens, un exemple pour expliquer le guillemet sa vérité est "à découvrir" est celui, par exemple du théorème des 4 couleurs (qu'on a finalement résolu), mais qui est de bas niveau (presque un énoncé finitiste en fait) et insensible aux axiomes choisis

Je reviens sur les anneaux et les modules: en y réfléchissant, je me suis aperçu que c'est vraiment un objet (le module en général) d'une trop grande généralité pour que je sois sûr de ce que j'ai conjecturé au post d'avant. ONpeut faire des modules formels avec à peu près tout. C'est donc à la fois intéressant, mais difficile.

Par exemple, pour aller dans le sens opposé de ma conjecture, je ne vois pas spécialement de raisons pour qu'il n'existe pas de module dont toute partie libre est dénombrable et toute partie génératrice est non dénombrable. Or un tel module, avec une construction astucuieuse pourrait bien avoir une base générique. Il me semble donc que les propriétés de l'anneau soient chaque fois prépondérantes.

Précision formelle: une base générique dans un module est une stratégie infaillible pour le joueur "base" dans le jeu suivant:

Le joueur "antibase" joue $v_1$; puis le joueur "base" répond par $F_1$ puis on recommence, antibase joue $v_2$, antibase répond par $F_2$, etc

Pour gagner, le joueur "base" doit faire des $F_n$ qui sont des parties LIBRES finies du modules avec $F_n\subseteq F_{n+1}$ pour tout $n$ et pour chaque $n$, le vecteur $v_n$ doit être dans le sous-module engendré par $F_n$.

Si à un moment de la partie, ces exigences sont en défaut, la partie s'arrête et "antibase" est déclaré gagnant, sinon, si ça dure éternellement, c'est "base" qui est déclaré gagnant.

anatole · September 2009

Bonjour Christophe,

le module Z^N est un Z-module qui a une base générique et qui pourtant n'est pas libre.

Amitié

Anatole

christophe c · September 2009

Merci de l'info... euh.... va me falloir un peu de tps pour m'apercevoir qu'il a une base générique... Tu le vois tout de suite en fait toi?

Et même

je crois qu'il va me falloir du tps pour m'apercevoir qu'il n'est pas libre lol

Le barbu rasé · September 2009

CC a écrit:

Et même je crois qu'il va me falloir du tps pour m'apercevoir qu'il n'est pas libre

Greg en a déjà parlé sur le forum mais je ne retrouve pas le fil.
L'argument du fil en question : si Z^N avait une base B (nécessairement non dénombrable) alors son dual serait isomorphe à Z^B (et donc non dénombrable). Or, on peut montrer que le dual de Z^N est Z^(N), qui est dénombrable.

Montrer que le dual de Z^N est Z^(N) n'est pas facile. Mais voici déjà un exo marrant pour toi si tu ne le connais pas : si f est un morphisme de Z-module de Z^N dans Z qui est nul sur les suites presques nulle, alors f est nul.

le forcing expliqué aux matheux ordinaires

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 32