Liste d'énoncés indécidables dans ZFC

Sans paradoxe, on peut démontrer rigoureusement (en utilisant la logique usuelle)[1] qu'un énoncé formulable dans une théorie T est indécidable dans T, c'est-à-dire que cet énoncé n'est pas démontrable dans T et que sa négation n'est pas non plus démontrable dans T ; en 1931, Kurt Gödel a démontré l’existence de tels énoncés (qu’il a construit explicitement) dans toute théorie capable de formaliser l’arithmétique ; ce fut l’un des premiers résultats négatifs importants de la riche théorie de la démonstration.

On a longtemps pensé que seuls des énoncés très artificiels, tels ceux construits par Gödel, étaient indécidables, et que des énoncés naturels, conformes à la pratique usuelle des mathématiciens, seraient tôt ou tard démontrés ou réfutés ; c'est la célèbre profession de foi de David Hilbert : « Il n'y a pas d'ignorabimus en mathématiques ; nous devons savoir ; nous saurons. »[2].

Pourtant, dès 1938, Gödel avait amorcé la preuve de l'indécidabilité de l'hypothèse du continu (achevée en 1963 par Paul Cohen) ; par la suite, de nombreux énoncés venus de toutes les branches des mathématiques se sont avérés indécidables, et en particulier on a pu montrer qu'il était possible de modéliser des machines de Turing par des constructions mathématiques très variées (automates cellulaires, suites de fractions, polynômes, etc.), rendant équivalent au problème de l'arrêt (ou à ses variantes) des énoncés d'allure innocente, et qui sont pourtant indécidables pour cette raison. Il est d'ailleurs très vraisemblable que la quasi-totalité des énoncés mathématiques, c'est-à-dire ceux formalisables dans un langage rigoureux (le plus souvent celui de la théorie ZFC) soient indécidables[3].

Néanmoins, prouver l'indécidabilité d'un énoncé spécifique, non construit spécialement pour cela, est difficile et rare ; cette liste expose des énoncés jugés importants par les mathématiciens et pour lesquels une telle preuve a pu être obtenue.

En 1931, Kurt Gödel démontra le premier résultat d'indécidabilité dans ZFC, valable en fait dans toute théorie capable d'exprimer les axiomes de l'arithmétique : le second théorème d'incomplétude, affirmant qu'une telle théorie ne peut démontrer sa propre consistance.

Les affirmations suivantes sont indépendantes de ZFC ; il faut y ajouter les démonstrations de Gödel et Cohen de ce que l'axiome du choix, et même d'autres axiomes plus faibles, comme l’axiome du choix dénombrable , sont indépendants des axiomes de ZF.

• l'hypothèse du continu (CH) et l'hypothèse généralisée du continu (GCH) : Gödel a construit un modèle de ZFC dans lequel GCH est vrai ; Paul Cohen a construit par la suite un modèle de ZFC où CH est faux, grâce à la méthode de forcing qu'il a inventé à cet effet ; des résultats d'indépendance plus précis se trouvent dans l'article Hypothèse du continu ;
• un résultat associé : si X a moins d'éléments que Y, X a également moins de sous-ensembles que Y (plus rigoureusement, ${\displaystyle {\rm {Card}}(X)<{\rm {Card}}(Y)\Rightarrow 2^{{\rm {Card}}(X)}<2^{{\rm {Card}}(Y)}}$) ; c'est une conséquence facile de GCH, mais on peut construire (par forcing) des modèles de ZFC où ${\displaystyle 2^{\aleph _{0}}=2^{\aleph _{1}}=\aleph _{2}}$[4] ;
• l'axiome de constructibilité (V = L) ;
• le principe du losange (en) (◊) ;
• L'axiome de Martin (MA) ;
• MA + ¬CH (résultat obtenu par Solovay et Tennenbaum (en))[5].

Diagramme montrant les relations entre ces résultats.

On a les chaînes d'implications suivantes :

V = L → ◊ → CH,

V = L → GCH → CH,

CH → MA,

et aussi (voir la section sur la théorie des ordres):

◊ → ¬ hypothèse de Souslin (HS),

MA + ¬CH → existence d'un ℵ₂-arbre d'Aronszajn → HS.

Les affirmations concernant l'existence d'un grand cardinal sont indépendantes de ZFC, car un tel cardinal est un modèle de ZFC, ce qui impliquerait une démonstration de la consistance de ZFC, impossible d'après le second théorème d'incomplétude. C'est en particulier le cas de :

• l'existence de cardinaux inaccessibles ;
• l'existence de cardinaux mesurables.

Beaucoup d'invariants cardinaux de la droite réelle, en relation avec la théorie de la mesure ou avec le théorème de Baire, ont leur valeurs indépendantes de ZFC. Bien qu'ayant des relations entre elles (voir le diagramme de Cichoń (en)), ces valeurs peuvent le plus souvent être n'importe quel cardinal régulier entre ℵ₁ et 2^ℵ₀.

Un sous-ensemble X de ${\displaystyle \mathbb {R} }$ est fortement de mesure nulle (en) si pour toute suite (ε_n) de réels positifs il existe une suite d'intervalles (I_n) recouvrant X et telle queI_n soit de longueur au plus ε_n. Borel a conjecturé que tout ensemble fortement de mesure nulle est dénombrable, mais ce résultat est indépendant de ZFC.

Un sous-ensemble X de ${\displaystyle \mathbb {R} }$ est ${\displaystyle \aleph _{1}}$-dense si tout intervalle ouvert contient ${\displaystyle \aleph _{1}}$ éléments de X. L'affirmation selon laquelle tous les ensembles ${\displaystyle \aleph _{1}}$-denses sont isomorphes (pour l'ordre) est indépendante de ZFC[6].

Le problème de Souslin demande si une certaine courte liste de propriétés caractérise ${\displaystyle \mathbb {R} }$ en tant qu'ensemble ordonné ; ce résultat est indépendant de ZFC [7]. Une droite de Souslin est un ensemble ordonné satisfaisant ces propriétés mais non isomorphe à ${\displaystyle \mathbb {R} }$ ; le principe du losange (en) ◊ montre l'existence de droites de Souslin, tandis que MA + ¬CH entraîne que tout arbre d'Aronszajn est spécial[8] , ce qui entraîne à son tour[9] qu'il n'existe pas de droites de Souslin.

L'existence d'une partition de l'ordinal ${\displaystyle \omega _{2}}$ en deux couleurs ne contenant aucun sous-ensemble monochromatique non dénombrable et séquentiellement fermé est indépendante de ZFC, de ZFC + CH et de ZFC + ¬CH, sous l'hypothèse de l'existence d'un cardinal Mahlo (en)[10] - [11] - [12].

En 1973, Saharon Shelah montra que le problème de Whitehead (en) (« tout groupe abélien A tel que Ext¹(A, Z) = 0 est-il libre ? ») est indépendant de ZFC[13]. Un groupe abélien tel que Ext¹(A, Z) = 0 est appelé un groupe de Whitehead ; MA + ¬CH implique l'existence d'un groupe de Whitehead non libre, tandis que V = L montre que tous les groupes de Whitehead sont libres ; dans l'une des premières applications du forcing, Shelah a construit un modèle de ZFC + CH dans lequel il y a un groupe de Whitehead non libre[14] - [15].

Un produit direct d'un ensemble dénombrable de corps est de dimension globale 2 si et seulement si l'hypothèse du continu est vraie[16].

Le théorème de Matiiassevitch implique qu'on peut construire un polynôme explicite p ∈ Z[x₁, ..., x₉] telle que l'assertion « il existe des entiers m₁, ..., m₉ tels que p(m₁, ..., m₉) = 0 » soit indécidable dans ZFC (et en fait, cette assertion est équivalente à Consis (ZFC))[17].

Une version plus forte du théorème de Fubini pour les fonctions positives, ne demandant pas que la fonction soit mesurable, mais seulement que les deux intégrales itérées soient définies (et aient une valeur finie), est indépendante de ZFC : d'une part, si l'hypothèse du continu est vraie, le théorème est faux (dans le carré unité) pour la fonction indicatrice d'un bon ordre sur [0, 1] d'ordinal ω₁, d'autre part, Friedman a démontré que le théorème était consistant avec ZFC[18] ; c'est d'ailleurs une conséquence d'une variante de l'axiome de symétrie de Freiling (en)[19].

La conjecture des espaces de Moore normaux, affirmant que tout espace de Moore normal est métrisable, peut être réfutée en supposant CH or MA + ¬CH, et démontrée à l'aide d'un axiome supposant l'existence de grands cardinaux.

Garth Dales et Robert Solovay ont démontré en 1976 que la conjecture de Kaplansky est indépendante de ZFC[20].

Dans l'algèbre B(H) des opérateurs linéaires bornés sur un espace de Hilbert (de dimension infinie) séparable H, l'ensemble des opérateurs compacts forme un idéal bilatère. La question de savoir si cet idéal est somme de deux sous-idéaux non triviaux est indépendante de ZFC, comme l'ont démontré Andreas Blass et Saharon Shelah en 1987[21].

Ilijas Farah[22], N. Christopher Phillips et Nik Weaver[23] ont montré que l'existence d'automorphismes extérieurs de l'algèbre de Calkin était indépendante de ZFC.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « List of statements independent of ZFC » (voir la liste des auteurs).

• (en) What are some reasonable-sounding statements that are independent of ZFC?, sur MathOverflow.