Loading AI tools
technique inventée par Paul Cohen pour prouver des résultats de cohérence et d'indépendance en théorie des ensembles De Wikipédia, l'encyclopédie libre
En mathématiques, et plus précisément en logique mathématique, le forcing est une technique inventée par Paul Cohen pour démontrer des résultats de cohérence et d'indépendance en théorie des ensembles. Elle a été utilisée pour la première fois en 1962 pour démontrer l'indépendance de l'hypothèse du continu vis-à-vis de la théorie ZFC. Combinée avec la technique des modèles de permutation de Fraenkel-Mostowski-Specker, elle a permis également d'établir l'indépendance de l'axiome du choix relativement à ZF. Le forcing a été notablement remanié et simplifié dans les années 1960 et s'est révélé être une technique extrêmement puissante, à la fois en théorie des ensembles et dans d'autres branches de la logique mathématique, comme la théorie des modèles ou la logique intuitionniste.
Le forcing est équivalent à la méthode des modèles à valeurs booléennes (en), qui est parfois ressentie comme plus naturelle et intuitive, mais qui est en général plus difficile à appliquer.
Intuitivement, le forcing consiste à étendre l'univers V. Dans cet univers plus large, V*, on pourra par exemple avoir de nombreux nouveaux sous-ensembles de ω = {0,1,2,…} qui n'existaient pas dans l'univers V, violant ainsi l'hypothèse du continu. A priori impossible, cette construction ne fait que refléter l'un des « paradoxes » de Cantor concernant l'infini, et en particulier le fait qu'il existe des modèles dénombrables de ZFC, contenant pourtant des ensembles non dénombrables (au sens du modèle), d'après le théorème de Löwenheim-Skolem. En principe, on pourrait par exemple considérer , identifier avec , et introduire une relation d'appartenance étendue mettant en jeu les « nouveaux » ensembles de la forme . Le forcing est une version élaborée de cette idée, réduisant l'expansion à l'existence d'un nouvel ensemble, et permettant un contrôle fin des propriétés de l'univers ainsi étendu.
La technique initialement définie par Cohen, connue à présent sous le nom de forcing ramifié (en), est légèrement différente du forcing non ramifié qui sera exposé ici.
Un ensemble partiellement ordonné de conditions de forcing, abrégé ici en ensemble de conditions[1], est un triplet (P, ≤, 1), où « ≤ » est un préordre sur P, et où 1 est un élément maximal, c'est-à-dire que p ≤ 1 pour tous les p de P. Les éléments de P sont appelés des conditions. On lit p ≤ q comme « p est plus forte que q » (ou encore « p raffine q »).
Intuitivement, les conditions « plus petites » fournissent davantage d'informations[2], tout comme l'intervalle plus étroit [3,141 592 6 ; 3,141 592 7] fournit davantage d'informations sur le nombre π que ne le fait l'intervalle [3,1 ; 3,2].
Associés à un ensemble de conditions donné P, on définit les P-noms, qui sont les ensembles de la forme {(u,p):u est un P-nom et p P}. Cette définition est circulaire, ce qui, dans ce contexte, veut dire qu'il s'agit en réalité d'une définition par récurrence transfinie ; une formulation rigoureuse consisterait par exemple à définir :
et alors la classe des P-noms est définie comme étant
Les P-noms constituent une extension de l'univers : étant donné x dans V, on définit xˇ comme étant le P-nom {(yˇ,1) : y x}. Là encore, il s'agit en fait d'une définition par récurrence transfinie.
Ėtant donné un sous-ensemble quelconque G de P, on définit ensuite, toujours par récurrence transfinie, l'application d'interprétation (ou de valuation) sur les noms par val(u, G) = {val(v, G) : ∃ p ∈ G, (v, p) ∈ u}. Remarquons que si 1 est dans G, alors val(xˇ, G) = x. On définit enfin G = {(pˇ, p) : p ∈ P}, et alors val(G,G) = G.
Un bon exemple d'ensemble de conditions de forcing est (Bor(I), ⊆, I ), où I = [0,1] et Bor(I) sont les sous-ensembles boréliens de I de mesure de Lebesgue non nulle. Dans ce cas, on peut interpréter les conditions comme étant des probabilités, et un Bor(I)-nom définit l'appartenance en un sens probabiliste. Cet exemple permettant une visualisation assez intuitive, le langage des probabilités est parfois utilisé également avec d'autres ensembles de conditions de forcing.
L'étape clé de la technique du forcing est, étant donné un univers V de ZFC, de déterminer un G approprié qui ne soit pas dans V. La classe de toutes les interprétations des P-noms s'avèrera être un modèle de ZFC, et une extension propre du V initial, puisque G∉V.
Plutôt que de travailler avec V, on considère un modèle transitif dénombrable M, avec (P,≤,1) ∈ M. M est ici un modèle de la théorie des ensembles, soit de tout ZFC, soit d'un sous-ensemble fini des axiomes de ZFC, ou encore d'une variante. La transitivité signifie que si x ∈ y ∈ M, alors x ∈ M ; le lemme de contraction de Mostowski dit qu'on peut supposer la transitivité de M si la relation d'appartenance est bien fondée. La transitivité permet de traiter l'appartenance et les autres propriétés élémentaires des ensembles de manière intuitive dans M. Enfin, il est toujours possible de prendre des modèles dénombrables, grâce au théorème de Löwenheim-Skolem.
M étant un ensemble, il y a des ensembles non dans M (c'est le paradoxe de Russell). L'ensemble G approprié, qu'on choisit d'adjoindre à M, doit être un filtre générique sur P, c'est-à-dire un sous-ensemble de P tel que
ce qui fait de G un filtre ; la condition pour que G soit générique est
L'existence d'un filtre générique G non dans M découle du lemme de Rasiowa-Sikorski (en). En fait, on a un résultat légèrement plus fort : étant donné une condition p ∈ P, il existe un filtre générique G tel que p ∈ G.
Si P n'a qu'un ensemble dénombrable de sous-ensembles denses, on peut en fait choisir G ∈ M ; c'est le cas trivial. Les éléments minimaux de P donnent aussi des G triviaux ; en effet si D est dense et si p est minimal, alors, comme le seul element q ≤ p est p lui-même, p ∈ D. Ainsi, tout filtre contenant un élément minimal est générique, et l'on peut encore choisir G ∈ M.
Étant donné un filtre générique G⊆P, la construction du nouveau modèle par forcing est la suivante. La sous-classe des P-noms dans M est notée M(P). Soit M[G]={val(u,G):u∈M(P)}. Pour ramener l'étude de la théorie des ensembles de M[G] à celle de M, on travaille dans le langage du forcing, qui est celui du calcul des prédicats du premier ordre avec l'appartenance comme relation binaire et tous les noms comme constantes.
Définissons alors p φ(u1,…,un) (qui se lit « p force φ ») où p est une condition, φ est une formule du langage du forcing, et les ui sont des noms, comme signifiant que si G est un filtre générique contenant p, alors M[G] ⊨ φ(val(u1,G),…,val(un,G)). Le cas particulier 1 φ est souvent noté P φ ou φ. Ces assertions sont vraies dans M[G] quel que soit le choix de G.
L'important est que cette définition « externe » de la relation de forcing p φ est équivalente à une définition « interne », par récurrence transfinie sur les noms pour les occurrences de u ∈ v et de u = v, suivie d'une récurrence ordinaire sur la complexité des formules. Cela a pour conséquence que toutes les propriétés de M[G] sont en fait des propriétés de M, et la vérification dans M[G] des axiomes de ZFC en devient élémentaire. On résume généralement cela par les trois propriétés suivantes :
On peut résumer ce qui précède en disant que le résultat fondamental de cohérence est qu'étant donné un ensemble de conditions P, on peut supposer qu'il existe un filtre générique G, non dans l'univers V, tel que V[G] est encore un univers, donc un modèle de ZFC. De plus, les assertions vraies dans V[G] se ramènent à des assertions vraies dans V par rapport à la relation de forcing.
Les deux styles, soit l'adjonction de G à un modèle transitif dénombrable M, soit à l'univers entier V, sont fréquemment employés. On rencontre moins souvent l'approche utilisant la définition « interne » du forcing, sans mentionner de modèles. Cette dernière méthode est celle qu'avait utilisée Cohen initialement, et qui est devenue la méthode de l'analyse des valeurs booléennes.
L'ensemble de conditions (non trivial) le plus simple est (Fin(ω,2), ⊇, 0), l'ensemble des fonctions définies sur une partie finie de ω à valeur dans 2={0,1}, ordonné par l'inclusion inverse, c'est-à-dire qu'une condition p peut être vue comme formée de deux sous-ensembles finis disjoints de ω, p−1[1] et p−1[0], que l'on peut voir comme les parties « oui » et « non » de p, aucune information n'étant donnée sur le complémentaire de ces sous-ensembles. Dire que q est plus forte que p signifie que q ⊇ p, autrement dit que les parties « oui » et « non » de q contiennent celles de p, donc donnent à ce sens davantage d'informations.
Soit G un filtre générique pour cet ensemble de conditions. Si p et q appartiennent à G, p∪q est également une condition, puisque G est un filtre. Cela veut dire que g=⋃G est fonctionnelle, car deux conditions de G ont les mêmes valeurs sur l'intersection de leurs domaines.
g est en fait une fonction partout définie sur ω : étant donné n ∈ ω, soit Dn={ p : p(n) est défini }, alors Dn est dense (car pour un p tel que n ne soit pas dans le domaine de p, en adjoignant une valeur quelconque pour n, le résultat sera dans Dn). Une condition p ∈ G∩Dn a n dans son domaine, et comme p ⊆ g, g(n) est défini.
Soit X=g−1[1], l'ensemble des réponses « oui » des conditions génériques. On peut déterminer un nom pour X directement. Soit X = { (nˇ, p) : p(n)=1 } ; on a donc val(X, G) = X. Supposons alors que A⊆ω soit dans V. Nous allons montrer que X≠A. Soit DA = { p : ∃n, n∈dom(p) et p(n)=1 si et seulement si n∉A }. DA est dense (en effet, étant donné p, si n n'est pas dans le domaine de p, il suffit d'adjoindre pour n une valeur opposée à celle de « n∈A »). Ainsi, tout p∈G∩DA force X≠A. En résumé, X est un nouveau sous-ensemble de ω, nécessairement infini.
La même construction, où ω est remplacé par ω×ω2, c'est-à-dire qu'on considère des fonctions définies sur un sous-ensemble fini de couples de la forme (n,α), avec n<ω et α<ω2, et ayant pour valeurs 0 ou 1, aboutit à créer ω2 nouveaux sous-ensembles de ω. Ces sous-ensembles sont tous distincts, par un argument de densité : étant donné α<β<ω2, soit Dα,β={p:∃n, p(n,α)≠p(n,β)} ; alors chaque Dα,β est dense, et une condition générique dans cet ensemble démontre qu'il y a un entier qui distingue le α-ème nouvel ensemble du β-ème, c'est-à-dire qu'il appartient à l'un des deux, mais pas à l'autre.
Ceci ne suffit pas à falsifier l'hypothèse du continu, car il faut encore montrer qu'on n'a pas créé de nouvelles applications qui seraient des bijections entre ω et ω1, ou entre ω1 et ω2. Ainsi, si l'on avait pris comme ensemble de conditions Fin(ω,ω1) (les applications allant des parties finies de ω vers ω1), on aurait dans V[G] une bijection de ω vers ω1, et donc ω1 serait devenu un ordinal dénombrable dans V[G] (on dit dans ce cas que ω1 s'est effondré).
C'est pourquoi la dernière étape dans la démonstration de l'indépendance de l'hypothèse du continu est de montrer que le forcing de Cohen n'effondre pas les cardinaux. Cette démonstration utilise une propriété combinatoire pour montrer que toutes les antichaînes de cet ensemble de conditions sont dénombrables, comme on le verra dans la section suivante.
Deux éléments p et q de P sont dits incompatibles (ce qu'on note p ⊥ q) s'il n'y a pas de r dans P tel que r ≤ p et r ≤ q (en particulier, on n'a ni p ≤ q, ni q ≤ p).
Une antichaîne forte (en) de P (appelée simplement antichaîne dans ce contexte) est un sous-ensemble A dont toutes les paires sont incompatibles (en particulier, A est une antichaîne au sens faible). Dans l'exemple des ensembles boréliens, l'incompatibilité de p et q signifie que p∩q est de mesure nulle. Dans l'exemple des applications de domaine fini, l'incompatibilité signifie que p∪q n'est pas une fonction, c'est-à-dire que p et q prennent deux valeurs différentes au même point.
On dit que P satisfait à la condition de chaîne dénombrable si toute antichaîne de P est dénombrable[3]. On voit facilement que Bor(I) satisfait la condition de chaîne dénombrable, parce que la somme des mesures ne peut dépasser 1.
Il en est de même de Fin(E,2) pour tout ensemble E infini, mais la démonstration en est plus difficile.
Ce qui justifie l'importance des antichaînes dans le forcing, c'est que pour la plupart des applications, ensembles denses et antichaînes maximales sont équivalents. Une antichaîne maximale A (pour l'inclusion) est une antichaîne telle que tout élément p ∈ P est compatible avec au moins un élément de A (toute antichaîne est contenue dans une antichaîne maximale, d'après le lemme de Zorn). Étant donné une antichaîne maximale A, soit D = {p : il existe q∈A, p≤q}. D est dense, et G∩D≠0 si et seulement si G∩A≠0. Réciproquement, étant donné un sous-ensemble dense D, le lemme de Zorn montre qu'il existe une antichaîne maximale A⊆D, et alors G∩D≠0 si et seulement si G∩A≠0.
Supposons alors que P satisfasse la condition de chaîne dénombrable. Étant donnés x et y ∈ V, avec f:x→y dans V[G], on peut approximer f dans V de la manière suivante : soit u un P-nom pour f (il en existe un par définition de V[G]) et p une condition qui force u à être une fonction de x vers y. On définit une fonction F dont le domaine est x par F(a) = { b : ∃ q ≤ p, q force u(aˇ) = bˇ }. D'après la propriété de définissabilité, cette définition a un sens dans V. Par cohérence du forcing, des b différents viennent de p incompatibles. D'après la condition de chaîne dénombrable, F(a) est donc dénombrable.
En résumé, f est « inconnue » dans V, puisqu'elle dépend de G, mais pas complètement pour un forcing satisfaisant à la condition de chaîne dénombrable : en effet, on peut alors identifier un ensemble dénombrable d'hypothèses sur la valeur de f en n'importe quelle entrée, indépendamment de G.
Il en découle la très importante conséquence suivante : si dans V[G], f:α→β est une surjection d'un ordinal infini vers un autre, une surjection analogue existe dans V. En particulier, les cardinaux ne peuvent s'effondrer ; la conclusion est que 2ℵ₀ ≥ ℵ2 dans V[G] ; la même construction permet en fait d'affecter à 2ℵ₀ « presque » n'importe quelle valeur comme on le verra dans la section suivante.
La valeur exacte de 2ℵ₀ dans le modèle de Cohen, ainsi que dans des variantes telles que Fin(ω × κ, 2) pour des cardinaux κ quelconques, fut déterminée par Robert M. Solovay, qui montra également comment construire des modèles où l'hypothèse du continu généralisée est fausse pour un nombre fini de cardinaux réguliers. Ainsi, dans le modèle de Cohen, si 2ℵ₀ = ℵ1 est vrai dans V, alors 2ℵ₀ = ℵ2 est vrai dans V[G].
En 1970, William Bigelow Easton (de)[4] montra comment violer l'hypothèse du continu généralisée pour un nombre infini, et même une classe propre, de cardinaux réguliers, démontrant que les restrictions connues sur les valeurs des puissances des cardinaux réguliers (monotonie, théorème de Cantor et théorème de König) étaient les seules démontrables dans ZFC.
Ce travail introduisit l'idée du forcing avec une classe propre de conditions. En général, cette technique échoue à construire un modèle de ZFC. Par exemple, Fin (ω × On, 2), où « On » est la classe de tous les ordinaux, fait du continu une classe propre. Fin (ω, On) permet une énumération (dénombrable) des ordinaux. Dans les deux cas, le V[G] qui en résulte n'est clairement pas un modèle de ZFC.
À cette époque, on pensait que des méthodes de forcing plus sophistiquées permettraient de même de construire des valeurs arbitraires des puissances des cardinaux singuliers. Mais le problème s'est avéré difficile, avec l'apparition de nouvelles restrictions démontrables dans ZFC, et les modèles obtenus par forcing dépendant parfois de divers axiomes de grands cardinaux ; il reste encore de nombreuses questions ouvertes[5].
Dans l'exemple des ensembles boréliens (Bor(I), ⊆, I), un filtre générique donné converge vers un nombre réel r, dont on dit que c'est un réel aléatoire. Un P-nom pour le développement décimal de r (au sens de l'ensemble canonique d'intervalles décimaux convergeant vers r) peut être donné en posant r = { ( Eˇ, E ) : E = [ k⋅10−n, (k+1)⋅10−n ], 0≤k<10n }. En un sens, ceci est simplement un sous-nom de G.
Pour retrouver G à partir de r, on prend les boréliens de I « contenant » r. Comme l'ensemble de conditions est dans V, mais que ce n'est pas le cas de r, cela est à proprement parler impossible. Mais il est en un certain sens naturel de dire que l'intervalle [0,5 ; 0,6] de V « contient » un réel aléatoire dont le développement décimal commence par 0,5. Ceci se formalise grâce à la notion de « code borélien ».
Tout borélien peut être construit en partant d'intervalles à extrémités rationnelles et en prenant les opérations de complémentaire et d'union dénombrable, ce un nombre dénombrable de fois (cette construction n'étant pas unique). La liste de ces opérations est appelée un code borélien. Étant donné un borélien B dans V, on en détermine un code, et on applique la même séquence de construction dans V[G], obtenant un borélien B*, dont on démontre qu'il ne dépend pas du code choisi, et que ses propriétés élémentaires sont les mêmes, par exemple, que si B⊆C, alors B*⊆C*, ou que si B est de mesure nulle, il en est de même de B*.
Ainsi, étant donné un réel aléatoire r, on peut montrer que G = { B (dans V) : r∈B* (dans V[G]) }. Cette équivalence amène généralement à écrire V[r] au lieu de V[G].
Une interprétation différente des réels de V[G] a été donnée par Dana Scott. Les rationnels de V[G] ont des noms qui correspondent à un ensemble dénombrable de valeurs rationnelles distinctes associées à une antichaîne de boréliens, ou, en d'autres termes, à une certaine fonction à valeurs rationnelles sur I = [0,1]. Les réels de V[G] correspondent alors à des coupures de Dedekind de telles fonctions, autrement dit, à des fonctions mesurables.
La méthode du forcing peut peut-être s'expliquer plus clairement en termes de modèles à valeurs booléennes[6]. Dans ces modèles, chaque assertion se voit attribuer une valeur de vérité choisie dans une algèbre de Boole infinie, plutôt que simplement l'une des deux valeurs « vrai » ou « faux ». On choisit ensuite un ultrafiltre sur cette algèbre, le passage au quotient par cet ultrafiltre donne des valeurs vrai/faux aux assertions. La théorie résultante possède un modèle contenant cet ultrafiltre, que l'on peut interpréter comme un modèle étendant le modèle de départ. En choisissant ce dernier, et l'ultrafiltre, de manière appropriée, on peut obtenir les propriétés voulues, car en un sens, seules les assertions qui doivent être vraies (qui sont « forcées » d'être vraies) le seront, par la propriété d'extension minimale.
Par le forcing, on cherche usuellement à montrer qu'une assertion donnée est cohérente avec ZFC (ou parfois avec une certaine extension de ZFC). Une façon d'interpréter cet argument est de supposer ZFC cohérente, et de l'utiliser pour démontrer la cohérence de ZFC + cette assertion.
Chaque condition de forcing est un ensemble fini d'informations, l'idée étant que seuls ces ensembles finis sont pertinents pour des démonstrations de cohérence, puisque d'après le théorème de compacité, une théorie possède un modèle si chaque sous-ensemble fini de ses axiomes en a un. On peut donc choisir un ensemble infini de conditions pour étendre un modèle de la théorie des ensembles, il suffit de vérifier la cohérence condition par condition, puis, déduire de la cohérence de la théorie des ensembles, la cohérence de la théorie étendue par cet ensemble infini de conditions.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.