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

page de liste de Wikipédia

Cette liste d'énoncés indécidables dans ZFC est formée d'affirmations dont il est démontré qu'elles sont indépendantes de la théorie des ensembles ZFC (la théorie prise comme fondement des mathématiques contemporaines, formée des axiomes de Zermelo–Fraenkel auxquels on adjoint l'axiome du choix), c'est-à-dire que cette théorie (en supposant qu'elle soit consistante) ne peut ni les démontrer, ni démontrer leur négation.

Indécidabilité et théorie de la démonstrationModifier

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.

Théorie des ensemblesModifier

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.

 
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 2-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 :

Ensembles de réelsModifier

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 1 et 20.

Un sous-ensemble X de   est fortement de mesure nulle (en) si pour toute suite (εn) de réels positifs il existe une suite d'intervalles (In) recouvrant X et telle queIn 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   est  -dense si tout intervalle ouvert contient   éléments de X. L'affirmation selon laquelle tous les ensembles  -denses sont isomorphes (pour l'ordre) est indépendante de ZFC[6].

Théorie des ordresModifier

Le problème de Souslin demande si une certaine courte liste de propriétés caractérise   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 à   ; 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   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].

Algèbre généraleModifier

En 1973, Saharon Shelah montra que le problème de Whitehead (en) (« tout groupe abélien A tel que Ext1(A, Z) = 0 est-il libre ? ») est indépendant de ZFC[13]. Un groupe abélien tel que Ext1(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].

Théorie des nombresModifier

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

Théorie de la mesureModifier

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 ω1, 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].

TopologieModifier

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[réf. souhaitée].

Analyse fonctionnelleModifier

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.

RéférencesModifier

  1. Techniquement, il s'agit de démontrer qu'aucun enchaînement logique partant des axiomes de T ne conduit à P ni à non P ; Gödel a montré comment coder ces enchaînements par des suites d'entiers ; une démonstration d'indécidabilité devient alors une démonstration d'un résultat d'arithmétique.
  2. Étienne Ghys, « Les problèmes de Hilbert : Ce qui est embrouillé nous rebute », sur Images des mathématiques, (consulté le ).
  3. Jean-Paul Delahaye, « Presque tout est indécidable ! », Pour la Science, no 375,‎ (lire en ligne)
  4. Voir par exemple cette discussion (en) sur MathOverflow.
  5. (en) Kenneth Kunen, Set Theory: An Introduction to Independence Proofs, Elsevier, (ISBN 0-444-86839-9)
  6. (en) Baumgartner, J., All  -dense sets of reals can be isomorphic, Fund. Math. 79, pp.101 – 106, 1973.
  7. (en) Robert Solovay et Stanley Tennenbaum, « Iterated Cohen extensions and Souslin's problem », Annals of Mathematics, vol. 94, no 2,‎ , p. 201–245 (DOI 10.2307/1970860, JSTOR 1970860)
  8. (en) Baumgartner, J., J. Malitz, et W. Reiehart, Embedding trees in the rationals, Proc. Natl. Acad. Sci. U.S.A., 67, pp. 1746 – 1753, 1970
  9. (en) Saharon Shelah, « Free limits of forcing and more on Aronszajn trees », Israel Journal of Mathematics, vol. 38,‎ , p. 315–334 (DOI 10.1007/BF02762777  )
  10. (en) Saharon Shelah, Proper and Improper Forcing, Springer 1992
  11. (en) Chaz Schlindwein, Shelah's work on non-semiproper iterations I, Archive for Mathematical Logic (47) 2008 pp. 579 – 606
  12. (en) Chaz Schlindwein, Shelah's work on non-semiproper iterations II, Journal of Symbolic Logic (66) 2001, pp. 1865 – 1883
  13. (en) Saharon Shelah, « Infinite Abelian groups, Whitehead problem and some constructions », Israel Journal of Mathematics, vol. 18, no 3,‎ , p. 243–256 (DOI 10.1007/BF02757281  , Math Reviews 0357114)
  14. (en) Saharon Shelah, « Whitehead groups may be not free, even assuming CH, I », Israel Journal of Mathematics, vol. 28,‎ , p. 193–204 (DOI 10.1007/BF02759809  )
  15. (en) Saharon Shelah, « Whitehead groups may not be free even assuming CH, II », Israel Journal of Mathematics, vol. 35,‎ , p. 257–285 (DOI 10.1007/BF02760652  )
  16. Barbara L. Osofsky, Homological Dimensions of Modules, American Mathematical Soc., (ISBN 9780821816622, lire en ligne), p. 60
  17. Voir, par exemple :
  18. (en) Harvey Friedman, « A Consistent Fubini-Tonelli Theorem for Nonmeasurable Functions », Illinois J. Math., vol. 24, no 3,‎ , p. 390–395 (DOI 10.1215/ijm/1256047607  , Math Reviews 573474)
  19. (en) Chris Freiling, « Axioms of symmetry: throwing darts at the real number line », Journal of Symbolic Logic, vol. 51, no 1,‎ , p. 190–200 (DOI 10.2307/2273955, JSTOR 2273955, Math Reviews 830085)
  20. H. G. Dales, W. H. Woodin, An introduction to independence for analysts,
  21. (en) Judith Roitman, « The Uses of Set Theory », Mathematical Intelligencer, vol. 14, no 1,‎
  22. (en) Ilijas Farah, « All automorphisms of the Calkin algebra are inner », Annals of Mathematics, vol. 173,‎ , p. 619–661 (DOI 10.4007/annals.2011.173.2.1  , arXiv 0705.3085)
  23. (en) N. C. Phillips et N. Weaver, « The Calkin algebra has outer automorphisms », Duke Mathematical Journal, vol. 139, no 1,‎ , p. 185–202 (DOI 10.1215/S0012-7094-07-13915-2, arXiv math/0606594)

Liens externesModifier