Liste d'énoncés indécidables dans ZFC
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émonstration
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 ensembles
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ée à 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, ) ; c'est une conséquence facile de GCH, mais on peut construire (par forcing) des modèles de ZFC où [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].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Implication_Chains_of_Undecidable_ZFC_Statements.png/220px-Implication_Chains_of_Undecidable_ZFC_Statements.png)
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 :
- l'existence de cardinaux inaccessibles ;
- l'existence de cardinaux mesurables.
Ensembles de réels
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 2ℵ0.
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 ordres
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érale
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 nombres
Le théorème de Matiiassevitch implique qu'on peut construire un polynôme explicite p ∈ Z[x1, ..., x9] tel 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 mesure
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].
Topologie
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 fonctionnelle
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érences
- (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).
- ↑ 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.
- ↑ Étienne Ghys, « Les problèmes de Hilbert : Ce qui est embrouillé nous rebute », sur Images des mathématiques, (consulté le ).
- ↑ Jean-Paul Delahaye, « Presque tout est indécidable ! », Pour la Science, no 375, (lire en ligne)
- ↑ Voir par exemple cette discussion (en) sur MathOverflow.
- ↑ (en) Kenneth Kunen, Set Theory: An Introduction to Independence Proofs, Elsevier, (ISBN 0-444-86839-9)
- ↑ (en) Baumgartner, J., All -dense sets of reals can be isomorphic, Fund. Math. 79, pp.101 – 106, 1973.
- ↑ (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)
- ↑ (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
- ↑ (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
)
- ↑ (en) Saharon Shelah, Proper and Improper Forcing, Springer 1992
- ↑ (en) Chaz Schlindwein, Shelah's work on non-semiproper iterations I, Archive for Mathematical Logic (47) 2008 pp. 579 – 606
- ↑ (en) Chaz Schlindwein, Shelah's work on non-semiproper iterations II, Journal of Symbolic Logic (66) 2001, pp. 1865 – 1883
- ↑ (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
, MR 0357114)
- ↑ (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
)
- ↑ (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
)
- ↑ Barbara L. Osofsky, Homological Dimensions of Modules, American Mathematical Soc., (ISBN 9780821816622, lire en ligne), p. 60
- ↑ Voir, par exemple :
- (en) James P. Jones, « Undecidable diophantine equations », Bull. Amer. Math. Soc., vol. 3, no 2, , p. 859–862 (DOI 10.1090/s0273-0979-1980-14832-6
, lire en ligne)
- (en) M. Carl et B. Moroz, « On a Diophantine Representation of the Predicate of Provability », Journal of Mathematical Sciences, vol. 199, no 199, , p. 36–52 (DOI 10.1007/s10958-014-1830-2, hdl 21.11116/0000-0004-1E89-1
)For a summary of the argument, see Modèle:Slink.
- (en) James P. Jones, « Undecidable diophantine equations », Bull. Amer. Math. Soc., vol. 3, no 2, , p. 859–862 (DOI 10.1090/s0273-0979-1980-14832-6
- ↑ (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
, MR 573474)
- ↑ (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, MR 830085)
- ↑ H. G. Dales, W. H. Woodin, An introduction to independence for analysts,
- ↑ (en) Judith Roitman, « The Uses of Set Theory », Mathematical Intelligencer, vol. 14, no 1,
- ↑ (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)
- ↑ (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 externes
- (en) What are some reasonable-sounding statements that are independent of ZFC?, sur MathOverflow.
Portail des mathématiques
Portail de la logique