Univers constructible

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Constructible.

En mathématiques et en théorie des ensembles, l'univers constructible, ou l'univers constructible de Gödel, noté L, est une classe d'ensembles qui peuvent entièrement être décrits en termes d'ensembles plus simples. Elle a été introduite par Kurt Gödel dans son article sur « la cohérence de l'axiome du choix et de l'hypothèse généralisée du continu »[1]. Il y montrait que cette classe est un modèle intérieur (en) de la théorie ZF et que ces deux hypothèses sont vérifiées dans ce modèle. Ceci prouve que ces deux propositions sont cohérentes avec les axiomes de ZF, à condition que ZF soit déjà cohérente. De nombreux autres théorèmes n'étant applicables que si l'une ou les deux hypothèses sont vraies, leur cohérence est un résultat important.

L'univers constructible, L[modifier | modifier le code]

L'univers L peut être construit par étages, de manière similaire à la construction de l'univers de von Neumann, V. Les étapes sont indexés par des nombres ordinaux. Alors que dans l'univers de von Neumann, l'étage Vα+1 d'un successeur est l'ensemble de tous les sous-ensembles de l'étage Vα précédent, dans l'univers constructible de Gödel cet ensemble est l'ensemble des sous-ensembles qui sont définissables par une formule φ qui respecte les contraintes suivantes :

  • φ doit être une formule du langage formel de la théorie des ensembles ;
  • φ ne doit être paramétrée que par des ensembles du précédent étage ;
  • les variables quantifiées doivent prendre leur domaine dans l'étage précédent.

En construisant un étage uniquement à partir de ce qui a été construit aux étages précédents, on s'assure que l'ensemble qui en résulte soit indépendant des particularité du modèle de théorie des ensembles qui sert de base, et soit inclus dans n'importe lequel des modèles de cette théorie.

Définition[modifier | modifier le code]

Soit

la fonction Def(X)
\begin{align}
\text{Def}(X) := & \Bigl\{ \{y \mid y\in X \text { et } \Phi(y,z_1,\ldots,z_n) \text{ est vraie dans }(X,\in)\} \mid \\ & \qquad \Phi \text{ une formule du premier ordre et }z_1,\ldots,z_n\in X\Bigr\}.
\end{align}

Alors par les règles de récurrence transfinie on définit :

l'univers L

Si z appartient à Lα, alors z = {y | y ∈ Lα et y ∈ z} ∈ Def(Lα) = Lα+1. Par conséquent Lα est inclus dans Lα+1, qui est un sous-ensemble de l'ensemble des parties de Lα. C'est donc une tour d'ensembles transitifs emboîtés.

Les éléments de la classe L sont appelés ensembles constructibles ; L est appelé l'univers constructible. Def et L sont définissables[2]. L'axiome de constructibilité, qu'on peut écrire V = L, affirme que tout ensemble de V est constructible, c'est-à-dire qu'il est aussi dans L.

Quelques développements sur L[modifier | modifier le code]

On peut également définir L par la formule Pour tout ordinal α, L_{\alpha} = \bigcup_{\beta < \alpha} \operatorname{Def} (L_{\beta}).

Les ensembles Ln et Vn sont identiques pour n'importe quel ordinal n fini, qu'on accepte ou rejette l'axiome de constructibilité. Par conséquent Lω = Vω : leurs éléments sont exactement les ensembles héréditairement finis (en). Pour les ordinaux plus grands, l'égalité n'est plus valide. Même pour les modèles de ZFC dans lesquels V est égal à L, Lω+1 est un sous-ensemble strictement inclus dans Vω+1, ce qui entraine que Lα+1 est un sous-ensemble strict de l'ensemble des parties de Lα pour tout α > ω.

Pour un ordinal infini α, Lα et α sont en bijection, par une bijection constructible. Ces ensembles sont donc équipotents dans n'importe quel modèle de théorie des ensembles les incluant.

Tel que défini au-dessus, Def(X) est l'ensemble des sous-ensembles de X définis par des formules de classe Δ0, les formules de la théorie des ensembles ne comprenant que des quantificateurs bornés (en) dont les paramètres sont X ou ses éléments.

Une définition équivalente de Gödel, sans référence à la définissabilité, caractérise chaque Lα+1 comme l'intersection de l'ensemble des parties de Lα et de la clôture de Lα∪{Lα} par une collection de neuf fonctions particulières.

Tout sous-ensemble de ω ou relation sur ω qui est arithmétique appartient à Lω+1, la définition arithmétique en fournissant une dans Lω+1. Inversement, tout sous-ensemble de ω appartenant à Lω+1 est arithmétique car les éléments de Lω sont codables par des entiers naturels de manière que l'appartenance ∈ soit définissable, donc arithmétique. Cependant, Lω+2 contient déjà certains sous-ensembles non arithmétiques de ω, comme l'ensemble des (entiers codant des) énoncés arithmétiques vrais : en effet, il est définissable à partir de Lω+1 ; il appartient donc à Lω+2.

Tous les sous-ensembles de ω et les relations sur ω qui sont hyperarithmétiques (en) appartiennent à L_{\omega_1^{\mathrm{CK}}}, où \omega_1^{\mathrm{CK}} désigne l'ordinal de Church-Kleene (en) et, inversement, les sous-ensembles de ω appartenant à L_{\omega_1^{\mathrm{CK}}} sont hyperarithmétiques[3].

L est un modèle intérieur standard de ZFC[modifier | modifier le code]

L est un modèle « standard », au sens où c'est une classe transitive dont la relation d'appartenance est celle de V. Par conséquent, toute formule Δ0 est absolue (en) pour L. On en déduit que L est un modèle intérieur, c'est-à-dire une sous-classe de V qui contient tous les ordinaux de V. En effet, on montre par induction transfinie que α ∈ Lα+1[4]. L est un modèle de ZFC[5], c'est-à-dire qu'il satisfait les axiomes suivants :

L'axiome de fondation
Tout ensemble non vide x possède un élément y disjoint de x.
(L, ∈) est une sous-structure de (V, ∈) qui est bien fondée, elle l'est donc également. En particulier, si xL, alors par transitivité de L, yL. Si l'on reprend ce même y de la même manière que dans V, alors il est toujours disjoint de x parce qu'on réutilise l'élément sans y ajouter de nouvel ensemble.
L'axiome d'extensionnalité 
Deux ensembles sont identiques si et seulement s'ils ont les mêmes éléments,
par transitivité de L.
L'axiome de la paire 
Si x, y sont des ensembles, alors {x, y} est un ensemble.Si xL et yL, alors il existe un ordinal α tel que xLα et yLα. Par conséquent {x, y} = {s | sLα et (s = x ou s = y)} ∈ Lα+1. Nous pouvons en déduire que {x, y} ∈ L et que sa signification dans L est identique à celle dans V.
L'axiome de l'union 
Pour tout ensemble x, il existe un ensemble y dont les éléments sont précisément les éléments des éléments de x. Si xLα, alors ses éléments sont dans Lα et leurs éléments appartiennent à Lα. y est donc un sous-ensemble de Lα. y = {s | sLα et il existe zx tel que sz} ∈ Lα+1. Donc yL.
L'axiome de l'infini 
Il existe un ensemble x tel que ∅ appartienne à x et tel que si y appartient à x, l'union y∪{y} lui appartienne égalementcar ω est un ordinal de V.
L'axiome de compréhension 
Étant donné n'importe quels ensembles S, z1, … , zn et n'importe quelle proposition P(x, z1, … , zn), {x | xS et P(x, z1, … , zn)} est un ensemble. Par induction sur les sous-formules de P, on peut montrer qu'il existe un α pour lequel Lα contient S et z1, … , zn et (P est vraie dans Lα si et seulement si P est vraie dans L — c'est le principe de réflexion (en)). Donc {x | xS et P(x, z1, … , zn) est valide dans L} = {x | xLα et xS et P(x, z1, … , zn) est valide dans Lα} ∈ Lα+1. Par conséquent ce sous-ensemble est dans L.
L'axiome de remplacement 
Étant donné n'importe quel ensemble S et n'importe quelle classe fonctionnelle, définie formellement comme une proposition P(x, y) pour laquelle P(x, y) et P(x, z) implique y = z, {y | il existe xS tel que P(x, y)} est un ensemble. Soit Q(x, y) la formule qui relativise P à L, c'est-à-dire que les quantificateurs de P sont restreints aux membres de L. Q est une formule bien plus complexe que P, mais est toujours finie, et comme P était fonctionnelle sur L, Q est fonctionnelle sur V ; par conséquent, on peut appliquer le remplacement dans V à Q. Donc {y | yL et il existe xS tel que P(x, y) est vraie dans L} = {y | il existe xS tel que Q(x, y)} est un ensemble dans V et est une sous-classe de L. En utilisant à nouveau l'axiome de remplacement, on peut montrer qu'il existe un α tel que cet ensemble est inclus dans LαLα+1. On peut alors utiliser l'axiome de compréhension dans L (ci-dessus) pour terminer de montrer que c'est également un élément de L.
L'axiome de l'ensemble des parties 
Pour tout ensemble x, il existe un ensemble y dont les éléments sont précisément les sous-ensembles de x.
En général, certaines parties d'un ensemble x de L ne sont pas dans L, donc l'ensemble de toutes les parties de x non plus. Ce qu'on doit montrer ici, c'est que l'intersection avec L de cet ensemble des parties appartient à L. Nous utilisons l'axiome de remplacement dans V pour montrer qu'il existe un α pour lequel cette intersection est un sous-ensemble de Lα. L'intersection s'exprime alors {z | zLα et z est inclus dans x} ∈ Lα+1. L'ensemble requis est donc dans L.
L'axiome du choix 
Étant donné un ensemble x d'ensembles non vides deux à deux disjoints, il y a un ensemble y (appelé ensemble de choix de x) contenant exactement un seul élément pour chaque membre de x.
On peut montrer qu'il existe un bon ordre sur L dont la définition fonctionne avec la même définition à l'intérieur de L lui-même. Nous pouvons donc choisir le plus petit élément de chaque élément de x pour construire y par les axiomes (ci-dessus) d'union et de compréhension dans L.

Tout l'intérêt de L est que la preuve que c'est un modèle de ZFC nécessite uniquement que V soit un modèle de ZF, c'est-à-dire qu'elle ne dépend pas de la validité de l'axiome du choix dans V.

L est absolu et minimal[modifier | modifier le code]

Soit W un modèle standard de ZF qui possède les mêmes ordinaux que V. L'univers L défini dans W est alors le même que celui défini dans V. En particulier Lα est le même dans V et W pour n'importe quel ordinal α, et les mêmes formules et paramètres dans Def(Lα) produisent les mêmes ensembles constructibles dans Lα+1.

De plus, comme L est une sous-classe de V et de W, L est la plus petite classe qui à la fois contient tous les ordinaux et est un modèle standard de ZF. En effet, L est l'intersection de toutes ces classes.

S'il existe un ensemble W dans V qui est un modèle intérieur de ZF et si l'ordinal κ est l'ensemble des ordinaux appartenant à W, alors Lκ est le L de W. S'il existe un modèle standard (en) de ZF, alors le plus petit de ces ensembles est un tel Lκ. Cet ensemble est appelé le modèle minimal (en) de ZFC. En utilisant le théorème de Löwenheim-Skolem descendant, on peut montrer que le modèle minimal, s'il existe, est nécessairement dénombrable.

Bien sûr, n'importe quelle théorie cohérente doit avoir un modèle, donc il existe des modèles de ZF y compris à l'intérieur de ce modèle minimal (en supposant que ZF soit cohérente). Cependant, ces modèles des ensembles ne sont pas standards. En particulier, ils n'utilisent pas la relation normale d'appartenance et ils ne sont pas bien fondés.

On déduit que V = L est vrai dans L et dans tout Lκ qui est un modèle de ZF, des faits que le L de L et le V de L sont tous deux le vrai L et que le L de Lκ et le V de Lκ sont le vrai Lκ. Ce sont cependant les seuls modèles standard de ZF dans lesquels V = L soit valide.

L et les grands cardinaux[modifier | modifier le code]

Comme OnLV, les propriétés des ordinaux qui dépendent de l'absence d'une fonction ou d'une autre structure (i.e. les formules Π1ZF) sont préservées de V à L. Les ordinaux initiaux (en) de V sont donc aussi initiaux dans L. Les ordinaux réguliers (en) le restent dans L. Les cardinaux limites faibles (en) deviennent des limites fortes dans L parce que l'hypothèse généralisée du continu est vérifiée dans L. Les cardinaux faiblement inaccessibles deviennent fortement inaccessibles. Plus généralement, n'importe quelle propriété de grand cardinal plus faible que 0# (en) (voir la liste de propriétés de grands cardinaux (en)) sera vérifiée également dans L.

Cependant 0# n'est pas vérifiée dans L, même si elle l'est dans V. Tous les grands cardinaux dont l'existence implique 0# ne conservent donc que leur propriétés plus faibles que 0#. Par exemple les cardinaux mesurables ne sont plus mesurables dans L mais restent de Mahlo (en).

On peut remarquer que si 0# est vraie dans V, alors il existe une classe close et non bornée (en) d'ordinaux indiscernables (en) dans L. Bien que certains d'entre eux ne soient même pas des ordinaux initiaux de V, ils ont les propriétés plus faibles que 0# dans L. De plus, n'importe quelle fonction sur les classes strictement croissante de la classe des indiscernables vers elle-même peut être étendue d'une manière unique en un plongement élémentaire (en) de L dans L. Cette propriété confère à L une structure de segments se répétant.

L peut être bien ordonné[modifier | modifier le code]

Il y a plusieurs manières de faire de L un bon ordre. Certaines partent de la l'élégante structure (traduction de « fine structure) ») décrite par Ronald Bjorn Jense[6] de L. Dans son article, il donne un apercu d'une construction de bon ordre pour L utilisant seulement les définitions données jusqu'ici plutôt que d'expliquer cette structure.

Supposons que x et y soient deux ensembles différents appartenant à L, et que nous souhaitons déterminer si x<y ou si x>y. Si x apparaît à l’étage Lα+1 et y apparait dans Lβ+1, et β différent de α, alors définissons x<y si et seulement si α<β. À partir de ce point nous supposeront que β=α.

Rappelons que L α+1 = Def (Lα), c'est-à-dire que Lα+1 est défini grace à des formules paramétrée par des ensembles de <Lα. Si on oublie temporairement les paramètres, les formules peuvent être énumérées par une énumération de Gödel (en) standard. Si Φ et Ψ sont les formule de plus petits nombre de Gödels permettant de définir respectivement x et y, et si ces formules sont différentes, nous définissons x<y si et seulement si le nombre de Φ est strictement inférieur au nombre de Ψ. Nous avons supposé β=α, donc nous supposerons Φ=Ψ.

Continuons la définition en supposant que Φ possède n parametres de Lα. Supponsons que la séquence de paramètre z1,...,zn soit la séquence de paramètre de Φ utilisée pour définir x, et que de même w1,...,wn soit celle de y. Choisissons alors x<y si et seulement si

  • zn<wn ;
  • (zn=wn et zn-1<wn-1) ;
  • (zn=wn et zn-1=wn-1 et n-2<wn-2) ;
  • etc.

c'est-à-dire l'ordre lexicographique inverse. Si il existe plusieurs séquences définissant le même ensemble, nous choisissons la plus petite par cette définition. Nous devons remarquer que les valeurs possibles pour un paramètre sont ordonées d'après l'ordre sur L restreint à Lα, cette définition est donc une définition par récurrence transfinie.

Le bon ordre des valeurs sur chaque paramètres est donné par l'hypothèse d'induction de cette récurrence. Les valeurs des n-uplets de paramètres sont bien ordonées par leur ordre produit. Les formules paramétrées sont bien ordonnées par somme ordonnée par les nombres de Gödel de bons ordres. Enfin L est bien ordonné par somme ordonnée par α des ordres sur Lα+1.

Notons que ce bon ordre peut être défini dans L lui même par une formule sans paramètre de la théorie des ensemble, seulement avec les variables libres x and y. Cette formule a la même valeur de vérité quelle que soit la manière dont on l'évalue dans L, V, ou W (un autre modèle standards de ZF muni des mêmes ordinaux) et nous pouvons upposer qu'elle sera fausse si soit x soit y ne sont pas dans L.

Il est bien établi que l'axiome du choix est équivalent à la possibilité de donner un bon ordre sur n'importe quel ensemble. Bien ordonner la classe propre V (comme nous venons de le faire avec L) est équivalent à Axiome du choix global (en) qui couvre les classe propres d'ensemble non vide et donc est plus puissant que l'axiome du choix habituel.

L possède un principe de réflexion[modifier | modifier le code]

Faire la démonstration que L vérifie l'axiome de séparation, l’axiome de remplacement, et l’axiome du choix nécessite (au moins dans la démonstration précédente) l'utilisation d'un principe de réflexion (en) pour L, en voici un: Par induction mathématique sur n<ω, nous utilisons ZF dans V pour démontrer que pour n’importe quel nombre ordinal α, il existe un ordinal β>α pour lequel n’importe quelle formule P(z1,...,zk) avec z1,...,zk appartenants à Lβ constituée de moins de n symboles (les constantes contenues dans Lβ comptent pour un symbole), nous obtenons que P(z1,...,zk) est vérifiée dans Lβ si et seulement si elle est vérifiée dans L.

L'hypothèse généralisée du continu est vraie dans L[modifier | modifier le code]

Soit S \in L_\alpha , et T n'importe quel sous ensemble constructible de S. Il existe alors un ordinal β pour lequel T \in L_{\beta+1}, donc T = \{x \in L_\beta : x \in S \wedge \Phi(x, z_i)\} = \{x \in S : \Phi(x, z_i)\} , pour une formule Φ et un z_i choisi dans L_\beta. Par le théorème de Löwenheim-Skolem inversé, il existe nécessairement un ensemble transitif K contenant L_\alpha un un w_i, qui possède une théorie du premier ordre identique à L_\beta dont le w_i serait substitué par z_i; ce K aura le même cardinal que L_\alpha. comme  V = L est vérifiée dans L_\beta, il est aussi vrai dans K, par conséquent K = L_\gamma pour un γ qui a le même cardinal qu'α. Donc T = \{x \in L_\beta : x \in S \wedge \Phi(x, z_i)\} = \{x \in L_\gamma : x \in S \wedge \Phi(x, w_i)\} parce que L_\beta et L_\gamma ont la même théorie. T est donc dans L_{\gamma+1}.

Tous les sous-ensembles constructible d'un ensemble infini S ont des rangs κ (au maximum) identiques au rang de S; il suit que si α est l’ordinal initial de κ+, alors L \cap \mathcal{P}(S) \subseteq L_{\alpha+ 1} peut servir d'"ensemble des parties" de S à l’intérieur de L. Cette étape montre que le simili ensemble des parties de S à un cardinal d'au plus \|\alpha\|. En supposant que S a κ pour cardinal, cet ensemble des parties doit avoir un cardinal d'exactement κ+. Ce qui est exactement l'hypothèse généralisée du continu rapportée à L.

Les ensembles constructifs sont définissables à partir des nombres ordinaux[modifier | modifier le code]

Il existe une formule de la théorie des ensembles qui énonce quelque chose de similaire à X=Lα. Elle n’est composée que de variables libre pour X et α. En l’utilisant nous pouvons étendre la définition pour n’importe quelle ensemble constructible. Si s∈Lα+1, alors s = {y|y∈Lα et Φ(y,z1,...,zn) sont vérifiées dans (Lα,∈)} pour une formule Φ et un z1,...,zn de Lα. C'est la même chose de dire la chose suivante: pour tout y, y∈s si et seulement si [il existe un X tel que X=Lα et y∈X et Ψ(X,y,z1,...,zn)] dans laquelle Ψ(X,...) est le résultat de la restriction de tout les quantificateur aux ensemble de X dans Φ(...). Notons que chaque zk∈Lβ+1 pour un β<α. Combinons alors les formules destinées aux z avec la formule affectée à s. Si nous appliquond une quantification existentielles aux z de l’extérieur, nous obtenons une formule définissant l’ensemble s en utilisant uniquement les ordinaux α apparaissant comme paramètre dans les expressions similaires à X=Lα.

Exemple  :

L'ensemble {5,ω} est constructible. S'il est l’unique ensemble s, qui vérifie la formule \forall y (y \in s \iff (y \in L_{\omega+1} \and (\forall a (a \in y \iff a \in L_5 \and Ord (a)) \or \forall b (b \in y \iff b \in L_{\omega} \and Ord (b))))),
(avec Ord (a) une notation pour \forall c \in a (\forall d \in c (d \in a \and \forall e \in d (e \in c))).)

Nous avons en fait encore dans cet exemple une version version simplifiée de la formule résultant des l’exécution des instruction données ici, mais le résultat est quand même là : il existe une formule de la théorie des ensembles vérifiées seulement pour les ensembles s que nous désirions, paramétrée seulement par des valeurs ordinales.

Constructibilité relative[modifier | modifier le code]

Un modèle de la théorie des ensemble aussi petit que L, mais incluant ou étant lié à un ensemble constructible est parfois recherché. On dispose dans ces cas de deux versions d'une constructibilité relative notées L(A) et L[A].

La classe L(A) d'un ensemble non constructible est définie comme l’intersection de toutes les classes modèles standards de la théorie des ensembles qui incluent A et tous les ordinaux.

L(A) est définie par récurrence transfinie
  • L0(A) = le plus petit ensemble transitif auquel appartient A, c'est-à-dire la fermeture transitive de {A}.
  • Lα+1(A) = Def (Lα(A))
  • Si λ est un ordinal limite, alors L_{\lambda}(A) = \bigcup_{\alpha < \lambda} L_{\alpha}(A) \! .
  • L(A) = \bigcup_{\alpha} L_{\alpha}(A) \! .

L'axiome du choix est utilisable si L(A) contient un bon ordre pour la fermeture transitive de {A}. Cet peut être extensible à L(A). Dans le cas contraire, l'axiome n’est pas valable.

Un exemple classique en est L(R), le plus petit modèle incluant les réels, très utilisé en théorie descriptive des ensembles.

L[A] 
la classe des ensembles dont la construction dépend d'une classe propre ou d'un ensemble (à priori non constructible) A.
Sa définition utilise DefA (X), identique à Def (X) si ce n’est que dans l’évaluation de la valeur de vérité des formules Φ le modèle (X,∈) est substituée par le modèle (X,∈,A), dans lequel A est un prédicat d'arité 1 s'interprétant « A(y) est y∈A ».

Cette classe est systématiquement modèle de l’axiome du choix. Même si A est un ensemble, il n’appartient pas nécessairement à L[A], à l'exceptions des A constitués uniquement d'ordinaux.

Les ensembles de L(A) et de L[A] ne sont cependant, rappelons le, souvent pas constructibles, et leurs propriétés peuvent être très différentes de celles de L.

Références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) Ulrich Felgner, Models of ZF-Set Theory, Springer, coll. « Lecture Notes in Mathematics »,‎ 1971 (ISBN 3-540-05591-6)
  • (en) Kurt Gödel, The Consistency of the Continuum Hypothesis, AM 3, Princeton, N. J., Princeton University Press, coll. « Annals of Mathematics Studies »,‎ 1940 (ISBN 978-0-691-07927-1, lire en ligne)

Notes[modifier | modifier le code]

  1. (en) Kurt Gödel, « The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis », PNAS, vol. 24, no 12,‎ 1938, p. 556–557 (liens PubMed?, PubMed Central?, DOI? et JSTOR?).
  2. (en) Keith Devlin (en), Constructibility, Berlin, Springer,‎ 1984 (ISBN 978-0-387-13258-7, lire en ligne), chap. II (« The Constructible Universe »), p. 56-107.
  3. (en) Jon Barwise, Admissible Sets and Structures, Berlin, Springer,‎ 1975 (ISBN 0-387-07451-1), p. 60.
  4. (en) Thomas Jech, Set Theory, Springer, coll. « Springer Monographs in Mathematics »,‎ 2002, 3e éd. (ISBN 3-540-44085-2, lire en ligne), p. 175.
  5. Jech 2002, p. 176.
  6. (en) Ronald Bjorn Djensen, « The fine structure of the constructible hierarchy », Annals of Mathematical Logic,‎ 1972 (lire en ligne)