Cardinaux extensibles
Bonjour à tous,
Suite à une discussion privée sur les cardinaux fortement compacts Christophe me propose de papoter autour des cardinaux extensibles, qui sont beaucoup plus "sexy".
Je pense qu'on pourrait en profiter pour causer de la Vopenka Konjectur, qui, si mes souvenirs sont bons, n'est pas bien loin des extensibles en termes de consistency strength.
Bonne nuit à tous
Martial
Suite à une discussion privée sur les cardinaux fortement compacts Christophe me propose de papoter autour des cardinaux extensibles, qui sont beaucoup plus "sexy".
Je pense qu'on pourrait en profiter pour causer de la Vopenka Konjectur, qui, si mes souvenirs sont bons, n'est pas bien loin des extensibles en termes de consistency strength.
Bonne nuit à tous
Martial
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
La VP dit que "toute notion a un indice de compacité".
Je précise: considérons un ensemble comme une théorie, avec des noms, des constantes, etc. Ca parait "vide", mais vous allez voir. Considérons une notion de "modèle", autrement dit supposons que soit donné un sens N'IMPORTE LEQUEL à "la théorie T a comme modèle le modèle M".
Attention rien à voir avec ce qui est déjà connu.
La seule chose demandée est que la notion soit (ce qui est basique) stable par permutation des noms.
LA VP dit alors que forcément, il existe un cardinal $k$ tel que pour toute théorie $T$, si pour tout ensemble $S\subset T$ de cardinal $<k$, il existe un "modèle" de $S$, ALORS il existe un modèle pour $T$ tout entier.
Les cardinaux extendibles sont les indices de compacité pour la notion "être un modèle (plein) d'une théorie du second ordre"
Les cardinaux compacts sont les indices de compacité pour la notion "être un modèle d'une théorie du premier ordre"
Mais vous pouvez inventer tout ce que vous voulez à la place, et ça vous donne autant de notions de compacité que vous permet votre imagination.
La VP est d'ailleurs une sorte de pied de nez à la recherche fondamentale, car sa consistance (jusqu'ici pariée) est un véritable enfantillage comparé à tout ce qui a été découvert. On a envie de se dire: "pourquoi un truc aussi bête et méchant, n'est pas depuis la nuit des temps une question posée?"
Je vous invite à proposer des notions baroques de "M est un modèle de T", et on regardera où se situe l'indice de compacité affirmé exister par la VP.
Mon but est de "justifier philosophiquement" les axiomes de GC : pour simplifier je ne vais parler que des plus classiques, laissant de côté les ineffables, éthérés, subtils, remarquables etc.
En gros, jusqu'à mesurable inclus les énoncés peuvent se justifier par une répétition dans le non-dénombrable du saut du fini à l'infini. C'est clairement le cas pour les inaccessibles, Mahlo, faiblement compacts, indescriptibles, mesurables.
Après ce n'est plus le cas que dans certains cas particuliers, comme fortement compacts ou la VP dont tu viens de parler.
Mais à partir de mesurable on dispose d'une stratégie pour aller plus loin : en effet, quand tu étudies les mesurables tu t'aperçois avec stupeur que la définition est équivalente à supposer l'existence d'un certain plongement élémentaire de $V$ dans une certaine classe transitive $M$, d'ordinal critique $\kappa$ et qui laisse $L$ invariant. Du coup tu te dis que ça va pas être facile de reconstituer ZFC dans $M$ dans la mesure où il y a un "trou" entre $\kappa$ et $j(\kappa)$. Du coup, en te creusant un peu plus le cerveau tu te dis que plus tu vas imposer de conditions de clôture à la classe $M$ et plus tu vas être exigeant. Et alors les autres hypothèses tombent "presque" naturellement : forts, Woodin, Shelah, huge et j'en passe.
Après tu te dis "j'ose". Je fais $M=V$, et j'appelle cardinal Reinhardt le point critique d'un plongement élémentaire de $V$ dans $V$. Là-dessus arrive Kunen, sur sa tornade blanche, qui te dit "Attention, mon p'tit gars, tu viens de prouver que $0=1$".
Alors tu n'en crois pas tes yeux, tu décortiques la preuve et tu es obligé de rendre les armes (comme Hilbert après la lecture de la preuve des théorèmes d'incomplétude).
Tu t'enquilles quelques verres pour faire passer ton chagrin, et le lendemain vers 16h tu décides de faire une analyse fine de la preuve de Kunen... qui te donne "presque naturellement" les axiomes I3, I2, I1.
Boban nous a donné dans un DM un exercice qui consistait à démontrer que si $\kappa$ est ineffable, alors le principe "diamant" est vrai à l'étage $\kappa$. Il y avait une indication pour faire l'exo, qui était fortement "anti-naturelle". En gros tu fais une construction transfinie, où à chaque étape limite tu fais tout pour contredire le diamant à l'étape en question, et à l'arrivée tu as le diamant au niveau $\kappa$.
J'en ai discuté avec lui, il dit que ce truc est en quelque sorte "immoral", que normalement la démonstration ne devrait pas marcher, mais que c'est la définition qui fait le taf : on a inventé les ineffables pour qu'ils satisfassent le diamant.
Un peu plus haut:
:-D Tu surestimes un peu l'être humain. Comme tu dis on enlève des petits bouts qui faisaient marche la preuve, le moins possible (kiff par principe de la création de GC) et on a un nouvel axiome tout joli.
Mais cette activité rigolote ne donne strictement aucune justification, même philosophique, de ces GC. Si quelqu'un prouve $$
I_0\Rightarrow (RiemannHyp)
$$ en dehors de recevoir la médaille FieldS, je peux te garantir qu'il n'aura pas convaincu grand monde que RH est vrai :-D
Perso je suis persuadé que I2 implique Syracuse (pourquoi, je ne sais pas), mais même si j'arrive à le prouver je suis sûr de 2 choses :
1) Je n'aurai pas la médaille FieldS (pour cause de trop vieillerie)
2) Je n'aurai pas convaincu grand monde que Syracuse est vraie...
C'est du délire, ou pas ?
Par ailleurs, entre autre de par mon expérience quantique, je ne crois plus du tout à un vrai/faux absolu, si tant est que j'y ai cru un jour, mais plutot à des dégradés, avec une connexité de l'espace, donc un long chemin qui mène du vrai au faux.
L'oeuvre de PaDe sur les tresses par exemple, ou ta future oeuvre sur I2 => Syracuse situe Les tresses ou Syracuse dans cet espace.
L'intérêt des GC c'est qu'ils sont forcing-indéfaisables ET forcing-nonaccessibles, donc offrent une autre dimension de l'espace, vu, via le forcing, avec l'outil algèbre de Boole, Heyting, ordres, etc.
Les niveaux 0 (algébriques) et 1 (analyse) ne rendent pas compte de ces choses, et c'est un avantage d'avoir ce paysage infinitiste: tu te rends compte que si on ne l'avait pas, il y a des tas de gens qui chercheraient à classer la Turing-complexité à l'aide des vitesses de croissance*** de fonctions $\N\to \N$, et vivraient en noir et blanc?
Donc c'est bien de l'avoir, mais le prix à payer c'est une concession à l'absoluité** des certitudes obtenues.
*** ceci provient du préjugé que comme tout le prouvable se passe au niveau diophantien, et comme il suffit de tester des entiers jusqu'à "assez haut" pour savoir s'il y a des solutions, et que ce "assez haut" reste fini (un entier) pour chaque équation diophantienne, on pourrait réduire l'ordre de Turing à l'ordre $(f\leq g):=\exists a\forall n>a: f(n)<g(n)$.
Or on sait que c'est faux depuis Cohen: on peut faire monter aussi haut qu'on veut le deuxième ordre partielle sans rajouter de richesse de complexité (un réel de Cohen donne une fonction qui est $\geq$ à toutes celle de l'ancien univers)
** Attention, elles restent "sûres" (proba 1), les différences se jouent à un autre niveau, et ne se mesurent pas avec des réels.
C'est un aspect continuel en logique (c'est pour ça que c'est plus dur et subtil que le reste des maths), c'est cette utilisation continuelle de l'axiome, réalisé par $W$, qui dit $A\to (A+A)$, ou, si tu préfères:
$$ (A\to (A\to )\to (A\to $$
De la même manière tu prouves "facilement" qu'il n'y a pas d'algèbre de Boole complète libre.
Un autre exemple: pour tout réel constructible $x$, il existe un ordinal $a$ et une définition $D$ telle que:
$$L_a\models D(a)$$
Et bien, on peut renforcer avec: il existe une définition $D$ telle que pour tout réel constructible $x$, il existe un ordinal $a$ tel que:
$$L_a\models D(a)$$
en utilisant le truc que tu racontes. On a gagné le passage de $\forall \exists$ à $\exists\forall$.
Alors je recommence, mais cette fois je ne la copie-colle plus (oui je sais, j'suis con, mais il y a des limites).
Ce truc me fait penser à un célèbre théorème d'analyse :
Soit $f$ une fonction indéfiniment dérivable de $\R$ dans $\R$. Si pour tout réel $x$ il existe un entier $n$ tel que $f^{(n)}(x)=0$, alors $f$ est un polynôme, i.e. il existe un entier $n$ tel que pour tout réel $x$, $f^{(n)}(x)=0$. On a interverti les quantificateurs.
J'avais découvert cet exo en 1980 en suivant les TDs d'evt de Mazet (à l'époque tu devais seulement en savoir à peu près autant que moi en maths, lol).
En fait il s'est grave taulé dans la correction : visiblement il n'avait pas regardé avant et croyait que c'était une application triviale du théorème de Baire. En fait non : il y a bien du Baire, mais il faut recoller les morceaux et c'est épouvantable à rédiger. Ça c'est pour l'anecdote.
Mais ce qui est intéressant pour nous c'est qu'avant de commencer l'exo Mazet nous avait dit que les logiciens avaient leurs méthodes à eux pour résoudre ce type de problèmes avec interversion de quantificateurs. Cela rejoint d'assez près ce que tu dis dans ton dernier post.
Question bête : connais-tu une preuve "en 3 lignes" de ce truc avec des méthodes de logique ?
$$ [\forall s\exists t: match(s,t)\in A] \to [\exists t\forall s: match(s,t)\in A]$$
Mais, pour l'énoncé que tu évoques, le logicien n'est pas "plus avancé" si ce n'est dans son expertise filtrante à la rigueur, du fait que :
$$ (n\geq p)\to (\{x\mid f^{(p)}=0\} \subset \{x\mid f^{(n)}=0\}) $$
pour ce que tu appelles "recoller les morceaux", une fois constaté que:
$ \exists n,a,b: $ avec $a<b$ et:
$$ \forall x\in ]a,b[: f^{(n)}(x)=0 $$
par Baire.
Tandis que les énoncés évoqués avant sont véritablement de "l'autoréférence" validées par "ordinal d'épuisement" en quelque sorte.
Je vois à peu près ce que tu appelles l'autoréférence par épuisement ordinal.
Par contre je n'ai pas compris la ligne 4 de ton dernier post. (Maintenant je me méfie, je ne fais plus de CC**).
Tu peux développer un peu ?
** CC : Copier-Coller
[*** AD : Axiome du choix Dénombrable de Détermination. :-D AD]
[Edit selon Martial ci-dessous. :)o AD]
Ce que je voulais dire de toute façon est que l'exercice dont tu parles n'a pas de raison d'avantager les logiciens, en dehors peut-être d'une vue plus naturelle et rapide des treillis en jeu dans l'exo. Alors que le fait que tout ordinal soit définissable car le plus petit à ne pas l'être l'est par le fait qu'il est justement cedit plus petit est lui typiquement dans le truc dont tu parlais.
Et non, AD ne me semble pas raccourcir a priori l'exo dont tu parles, c'était juste un exemple de la famille des énoncés concernés.
@AD : non, tu te trompes, l'axiome du choix dénombrable est généralement noté $AC_{\omega}$, ou à la rigueur $AC-den$.
Par ailleurs, le AD dont parle CC est l'axiome de détermination, qui est contradictoire avec AC, mais pas avec ACD (axiome du choix dépendant).
C'est complexe...
Tiens, juste histoire de rigoler : j'ai un collègue (et ami) spécialiste de rétroacronymes. Il a relevé un défi qui consistait à faire un rétroacronyme avec le mot "fiabilité". Thème imposé : les statistiques sur le virus.
Voici le résultat :
"les Fausses Informations Assombrissent les Bonnes Inutilement et Laissent les Imbéciles Tergiverser Eternellement".
J'en reviens à ton énoncé de taupin: en fait, si si le logicien est avantagé (du moins si on considère que tous les logiciens connaissent bien ordinaux et arbres), puisqu'une application $C^\infty$ de $\R^n\to \R^n$ qui n'est pas un polynôme voit forcément un $a\in \R^n$ tel qu'aucune de ses dérivées ne s'y annule.
Cela tient au fait qu'à supposer que non, en notant $u_0:=(f, F,1)$ un contre-exemple ($F$ étant un fermé compact de $\R^n$ où $f$ ne coïncide pas avec un polynôme et $\forall x\in F: ||f(x)||\geq 1$, et d'intérieur disons non vide), et en notant pour tous $f,g,x,y,F,G$:
$$[(f,F,x)>(g,G,y)]:=([g=f']\ et\ [\forall x\in G: ||g(x)|| > y] )$$
pour des triplets $(f,F,x)$ où $f$ est $C^\infty$, $F$ fermé compact et $x>0$, l'absence de suite $u$ vérifiant pour tout $n:$
$$u_n>u_{n+1}$$
avec $u_0$ déjà choisie, on pourrait considérer le plus petit exemple au sens du rang dans l'arbre.
Donc j'ai berné involontairement les lecteurs en disant que le corpus logique de base aide peu. Bon, je suis endormi aujourd'hui de toute façon, je ne me suis jamais senti aussi mou...
Si ça peut te rassurer tu n'es pas le seul, lol
Mais tu peux prendre à peu près ce que tu veux. Par exemple, on peut s'amuser à dire qu'un graphe $G$ est "gentiment coloriable" quand il existe un poset $P$ qui ne détruit pas $\omega_1$ (ie $V^P\models \omega_1$ n'est pas dénombrable) tel qu'on peut associer à chaque somme un élément de $P$ de sorte que quand il y a une arête entre deux sommets, les éléments associés sont incompatibles.
Il existe $k$ tel que POUR TOUT G qui n'est pas gentiment coloriable, il existe sous-graphe $H$ de $G$ qui ne l'est pas non plus et tel que $card(H)<k$.
Autrement dit, c'est la fête!!!
Rien à voir mais en ce moment j'essaye de comprendre le forcing itéré. (Pour le forcing simple ça va en gros, même si mes connaissances restent fragiles). Mais dès qu'on itère transfiniment des conditions de forcing ça devient galère. Je crois avoir compris les "Two-step iterations" et les itérations à support fini, mais quand il faut appliquer ça pour prouver par exemple la consistance de l'axiome de Martin, là j'avoue que la RAM sature...
Pour l'intuition, il est mieux d'imaginer une sorte de gigantesque algèbre de Boole universelle, dans laquelle on applique des filtres progressifs pour faire ce qu'on a envie de faire. Un peu comme en proba conditionnelle.
Mais dès qu'on rentre dans les détails techniques je ne retrouve plus mes petits...