Complexité de l'hypothèse du continu — Les-mathematiques.net The most powerful custom community solution in the world

Complexité de l'hypothèse du continu

Salut à tous,

Hier par le plus grands des hasards je me suis posé la question suivante : quelle est la complexité logique de la formule $2^{\aleph_0} = \aleph_1$ ? $\Pi_1$ ? $\Sigma_2$ ? $\Pi_2$ ?
J'avoue que je n'en ai aucune idée.
Merci d'avance pour vos éclaircissements
Martial.

Réponses

  • Il faut préciser un peu ce que tu entends par là je crois. La complexité logique d'un énoncé complexe comme celui-ci n'est pas a priori bien définie en termes absolus, sauf à l'écrire toi-même sans abbréviations, auquel cas la question devient triviale.
    Donc pour poser ta question, il faut préciser avec quels axiomes : ZF, ZFC,... ? (Par exemple dans ZF + HC, la question est triviale :-D )
    En effet, dans ce cas tu peux demander la complexité minimale d'une formule qui , dans la théorie T, est équivalente à HC.
    Bon tu le sais sûrement, mais je voulais le préciser.
    Disons que, vu comme tu l'as écrite, tu pensais à ZFC (+ cf. une discussion avec Christophe, où il m'expliquait que dans ZF, HC n'a pas trop de sens - ce dont témoigne par exemple les phénomènes dus à AD)

    Dans ce cas... je ne sais pas :-D (tout ça pour ça)

    Il faut aussi dire à quel point on a le droit de tricher. Certainement tu ne veux pas "$\omega_1$" dans le langage, mais quid de $\omega$ ? Bon ça, à la limite ça va pas trop changer la complexité, mais un truc qui risque de changer c'est est-ce que tu autorises $A\times B$ ? (À un niveau de complexité près, $\{x,y\}$) bon c'est des détails mais ça va changer la donne au total de 3-4 niveaux de complexité (sauf s'il y a une manière astucieuse de faire)

    Dernière remarque : j'oublie toujours ces résultats, mais il y a un truc genre absolutié de Shoenfeld ou je-ne-sais-quoi qui te minore ta conplexité puisque HC n'est pas absolu entre $L$ et $V$. En travaillant plus, certainement on peut minorer par la véritable borne
  • Par exemple, je pense que

    "Il existe un ordinal $\alpha$ qui se surjecte sur $P(\omega)$ et dont tous les éléments s'injectent dans $\omega$"

    doit être pas loin du min en complexité (quitte à remplacer $\omega$ par $z$ et rajouter un "il existe $z$ qui est $\omega$ et tel que"). À noter qu'il fait éviter de parler de fonctions ici, parce que "$f$ est une fonction" ça prend de la complexité, donc il fait "faire une christophe" et juste dire que $f$ est un ensemble qui contient certains couples et vérifie certains trucs moins complexes.
    Pareil pour "est un ordinal" on utilisera à profit les formulations efficaces de Christophe (qui reposent souvent sur AF, d'où l'importance aussi du choix de la théorie)
  • Ou peut-être "tout ensemble de parties de $\omega$ s'injecte dans $\omega$ ou se surjecte sur les parties de $\omega$" (même remarque sur la notion de fonction et sur $\omega$)

    PS : Shoenfield's absoluteness theorem montre que ça ne peut pas être $\Sigma^1_3$ ou moins, parce que ces énoncés passent de $L$ à $V$ , et je pense que mes suggestions ne sont pas loin de $\Pi^1_4$ ou $\Sigma^1_4$, donc pas loin de la borne inférieure imposée par Shoenfield. Il faudrait l'écrire. Sachant que $\omega$ et les couples sont absolus entre $L$ et $V$, on peut faire le même genre de choses en s'autorisant ces machins dans le langage
  • Zut Shoenfield parle de la hiérarchie analytique et pas arithmétique ... :-S je suis un peu paumé à vrai dire avec ça dans le cas de la TDE et pas de l'arithmétique

    + je crois que je me suis doublement embrouillé car si je me souviens bien, les formules bornées ne comptent pas en complexité ?
  • Je reprends en étant un peu moins confus (désolé Martial, je bombarde ton fil de bêtises :-D )

    Si on définit $\Sigma^0_0= \Delta_0^0 = \Pi^0_0$ en autorisant les quantificateurs bornés ($\forall x\in y, \exists z\in w$), et en autorisant le symbole $\omega$, alors ma deuxiéme suggestion peut s'écrire (je crois) en $\forall \exists\forall$, donc en $Pi_3^0$

    En retirant le droit à $\omega$, il faut rajouter un $\exists$ devant + un truc de basse complexité (quasiment tout dans $z=\omega$ est borné, donc $z=\omega$ est $\Pi^0_1$ si je ne dis pas de bêtises encore), et donc on atteint du $\Sigma^0_4$

    J'ai du mal à imaginer aller plus bas, en s'autorisant ou pas $\omega$. Apparemment Shoenfield parle de la hiérarchie analytique, mais je pense qu'il y a des résultats similaires pour la hiérarchie arithmétique.

    Je m'arrête là avant de dire plus de bêtises
  • HC tel quel est un énoncé $\forall x\in P(\R) \exists y\in P(\R)$ (je ne sais plus, je crois que ça se note $\pi_2^2$

    Mais comme on peut l'écrire "il existe une surjection de $\omega_1$ sur $\R$", ce dernier étant un énoncé $\exists x\in P(\R)$, c'est cette complexité-là qu'on va retenir (ie $\pi_2^1$). Il y a une autre manière, mais elle n'est pas plus simple, elle est juste "plus pure"**.

    Woodin avait annoncé (sous GC's) que $HC$ implique toutes les vérités $\exists x\in P(\R)$, ie que la théorie sous cette complexité est gelée.

    ** il existe $S\subset \R^2$ tel que pour tout $x\in \R$ l'ensemble des $y$ tel que $(y,x)\in S$ est dénombrable et aussi telle que $\forall x,y$ dans $\R: (x,y)\in S$ ou $(y,x)\in \R$.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Salut Max.

    "désolé Martial, je bombarde ton fil de bêtises".
    Non, il suffisait de ne lire que le dernier post, lol.

    Petite précision (j'aurais dû le dire) : ma question était dans ZFC avec axiome de fondation.

    Je suis assez d'accord avec $\Pi^0_3$.
    Mais tu crois vraiment que si on s'interdit $\omega$ dans le langage ça va augmenter la complexité ?
    On ne peut pas s'en tirer en utilisant le fait que $\omega$ est absolu pour les modèles intérieurs ?

    Je n'ai jamais rien compris au lemme d'absoluité de Shoenfield mais si je me souviens bien il dit que les propriétés $\Pi^0_2$ ne peuvent pas être modifiées par forcing, c'est ça ?
    Donc, si une propriété (par exemple HC) est modifiable par forcing, tu peux en déduire sans calcul que sa complexité est $> \Pi^0_2$. J'ai bon ?
  • Je rebondis sur ton premier post, où il n'y avait pas que des bêtises, lol.

    Je suis d'accord avec Christophe que, en l'absence de AC, ça n'a pas grand sens de parler de HC, ou alors il faut préciser ce qu'on entend par là.

    Par exemple il me semble me rappeler que sous AD, toute partie de $\mathbb{R}$ qui n'est pas dénombrable est en bijection avec $\mathbb{R}$. Mais évidemment le cardinal (généralisé) de $\mathbb{R}$ n'est pas du tout égal à $\aleph_1$.
  • Sous AD, toute partie non dénombrable de $\R$ contient un fermé non dénombrable.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Martial : si je comprends bien, Shoenfield parle de trucs du genre $\Pi^1_{truc}$, donc pas $\Pi^0$ ! C'est ce qui m'a fait dire des bêtises.

    Quant à $\omega$, je viens de me rendre compte que j'ai dit une bêtise: si, à la place de dire "il existe $z$ qui est $\omega$ et tel que $\Pi^0_3$", je dis "pour tout bonhomme $z$ qui est$\omega$, on a $\Pi^0_3$", on reste sur du $\Pi^0_3$ et donc on est heureux.
    Donc en fait quoi qu'il arrive (en mettant un $\exists$ ou un $\forall$ pour gérer $\omega$) on peut faire semblant que $\omega$ est dans le langage !

    Maintenant, aller plus bas me semble complexe.
  • Pour les symboles, ça dépend si on part de $\N$ ou de $\R$.

    Si c'est $\N$, quantifier sur les entiers niveau 0, quantifier sur les réels niveau 1, sur les parties de $\R$ niveau 2, etc

    Si c'est $\R$, quantifier sur les réels niveau 0, sur les parties de $\R$ niveau 1, etc

    Le niveau d'alternances de quantificateurs se met en bas et le niveau d'itération par $P$ en haut? En tout cas c'est ce que maxtimax a restitué à son last post. Moi j'avais fait l'inverse. Comme une montée de niveau écrase tout, un $\pi_n^k$ est toujours $\pi_0^{k+1}$, etc, etc.

    Bon de toute façon, le mieux c'est de dire explicitement les formules.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • @Christophe :
    1) Sorry, je n'avais pas lu ton 1er post.
    2) "Woodin avait annoncé (sous GC's) etc" : je pense que c'est plutôt sous la $\Omega$-Conjecture + "il existe une classe propre de cardinaux Woodin".
    3) Je pense que tes définitions dans ton 2ème post sont correctes.

    @Tous 2 : mézalor ça veut dire que HC est $\Pi^1_3$, c'est ça ?
  • Et donc Shoenfield dit que les propriétés $\Pi^1_2$ ne sont pas modifiables par forcing, c'est toujours ça ?
  • De mon téléphone. Non c'est un sigma, pas un pi. C'est "il existe un ensemble de réels tel que blabla".
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • @Christophe : je crois qu'on s'est fourvoyés dans les notations.
    Moi je travaille dans ZF, donc peu me chaut qu'on quantifie sur $\omega$, sur $\mathbb{R}$, sur $\mathscr P(\mathbb{R})$ etc. Pour moi toutes ces quantifications sont bornées.

    Voilà les définitions que j'emploie :
    https://drive.google.com/file/d/1HkX2WhSHm5E3TTwcZameSBEj3_hKXaVj/view
    pages 4 et 5.

    Donc toute formule ensembliste du 1er ordre est $\Sigma^0_n$ ou $\Pi^0_n$ pour un certain entier $n$. Ce n'est que si je dois quantifier sur des parties de l'univers que je vais utiliser des formules $\Sigma^1_{Truc}$ etc.
  • Ok Martial.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!