Forcing

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.

Motivations intuitives Le forcing est équivalent à la méthode des , 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 , est légèrement différente du forcing non ramifié qui sera exposé ici.

Ensembles de conditions de forcing Un ensemble partiellement ordonné de conditions de forcing, abrégé ici en ensemble de conditionsBien que le terme de poset soit parfois utilisé en théorie des ensembles ordonnés, l'expression anglaise forcing poset ne semble pas avoir été reprise dans la littérature francophone., est un triplet (P, ≤, 1), où « ≤ » est un préordre sur P, et où 1 est l'élément maximum, 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'informationsToutefois, d'autres conventions sont parfois utilisées ; ainsi, en particulier, Saharon Shelah et ses coauteurs choisissent l'ordre inverse, 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 : Nom(0) = {}; Nom(α + 1) = l'ensemble des sous-ensembles de (Nom(α) × P); Nom(λ) = {Nom(α) : α < λ}, si λ est un ordinal limite, et alors la classe des P-noms est définie comme étant V = {Nom(α) : α est un ordinal}.

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 = {(pˇ, p) : p ∈ P}, et alors val(,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.

Modèles transitifs dénombrables et filtres génériques 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

1 ∈ G ; si p ≥ q ∈ G, alors p ∈ G ; si p,q ∈ G, alors ∃r ∈ G, r ≤ p et r ≤ q ;

ce qui fait de G un filtre ; la condition pour que G soit générique est

si D ∈ M est un sous-ensemble dense de P (c'est-à-dire, si p ∈ P implique ∃q ∈ D, q ≤ p) alors G∩D ≠ 0 .

L'existence d'un filtre générique G non dans M découle du lemme de Rasiowa-Sikorski. 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.

Forcing É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. Soit M[G]={val(u,G):u∈M. 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 φ(u,…,u) (qui se lit « p force φ ») où p est une condition, φ est une formule du langage du forcing, et les u sont des noms, comme signifiant que si G est un filtre générique contenant p, alors M[G] ⊨ φ(val(u,G),…,val(u,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 : Vérité : M[G] ⊨ φ(val(u,G),…,val(u,G)) si et seulement si pour une certaine condition p ∈ G, p φ(u,…,u) (la formule φ est forcée par G). Définissabilité : L'assertion « p φ(u,…,u) » est définissable dans M. Cohérence : si p φ(u,…,u) et q ≤ p, alors q φ(u,…,u).

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.

Le forcing de Cohen 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 et p, 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 D={ p : p(n) est défini }, alors D 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 D). Une condition p ∈ G∩D a n dans son domaine, et comme p ⊆ g, g(n) est défini.

Soit X=g, l'ensemble des réponses « oui » des conditions génériques. On peut déterminer un nom pour X directement. Soit = { (nˇ, p) : p(n)=1 } ; on a donc val(, G) = X. Supposons alors que A⊆ω soit dans V. Nous allons montrer que X≠A. Soit D = { p : ∃n, n∈dom(p) et p(n)=1 si et seulement si n∉A }. D 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∩D force X≠A. En résumé, X est un nouveau sous-ensemble de ω, nécessairement infini.

La même construction, où ω est remplacé par ω×ω, 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 α<ω, et ayant pour valeurs 0 ou 1, aboutit à créer ω nouveaux sous-ensembles de ω. Ces sous-ensembles sont tous distincts, par un argument de densité : étant donné α<β<ω, 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 ω, ou entre ω et ω. Ainsi, si l'on avait pris comme ensemble de conditions Fin(ω,ω) (les applications allant des parties finies de ω vers ω), on aurait dans V[G] une bijection de ω vers ω, et donc ω serait devenu un ordinal dénombrable dans V[G] (on dit dans ce cas que ω s'est effondré).