Univers constructible

L'univers constructible de Gödel L peut être construit par étages, de manière similaire à la construction de l'univers de von Neumann, V. Les étapes sont indexées 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és 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.

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

Les ensembles L_n et V_n 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 entraîne 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 Δ₀, 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 à ${\displaystyle L_{\omega _{1}^{\mathrm {CK} }}}$, où ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ désigne l'ordinal de Church-Kleene (en) et, inversement, les sous-ensembles de ω appartenant à ${\displaystyle L_{\omega _{1}^{\mathrm {CK} }}}$ sont hyperarithmétiques[4].

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 Δ₀ 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[5]. L est un modèle de ZFC[6], 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 x ∈ L, alors par transitivité de L, y ∈ L. 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 x ∈ L et y ∈ L, alors il existe un ordinal α tel que x ∈ L_α et y ∈ L_α. Par conséquent {x, y} = {s | s ∈ L_α 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 x ∈ L_α, alors ses éléments sont dans L_α et leurs éléments appartiennent à L_α. y est donc un sous-ensemble de L_α. y = {s | s ∈ L_α et il existe z ∈ x tel que s ∈ z} ∈ L_α+1. Donc y ∈ L.

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, z₁, … , z_n et n'importe quelle proposition P(x, z₁, … , z_n), {x | x ∈ S et P(x, z₁, … , z_n)} est un ensemble. Par induction sur les sous-formules de P, on peut montrer qu'il existe un α pour lequel L_α contient S et z₁, … , z_n 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 | x ∈ S et P(x, z₁, … , z_n) est valide dans L} = {x | x ∈ L_α et x ∈ S et P(x, z₁, … , z_n) 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 x ∈ S 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 | y ∈ L et il existe x ∈ S tel que P(x, y) est vraie dans L} = {y | il existe x ∈ S 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 | z ∈ L_α 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.

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.

Il y a plusieurs manières de faire de L un bon ordre. Certaines partent de l'élégante structure (traduction de « fine structure) ») décrite par Ronald Bjorn Jense[7] de L. Dans son article, il donne un aperçu 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 apparaît dans L_β+1, et β différent de α, alors définissons x<y si et seulement si α<β. À partir de ce point nous supposerons que β=α.

Rappelons que L_α+1 = Def (L_α), c'est-à-dire que L_α+1 est défini grâce à des formules paramétrées par des ensembles de <L_α. Si on oublie temporairement les paramètres, les formules peuvent être énumérées par un codage de Gödel standard. Si Φ et Ψ sont les formules de plus petits nombres de Gödel 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 paramètres de L_α. Supponsons que la séquence de paramètre z₁, ..., z_n soit la séquence de paramètres de Φ utilisée pour définir x, et que de même w₁, ..., w_n soit celle de y. Choisissons alors x<y si et seulement si

• z_n<w_n ;
• (z_n=w_n et z_n-1<w_n-1) ;
• (z_n=w_n et z_n-1=w_n-1 et _n-2<w_n-2) ;
• etc.

C'est-à-dire l'ordre lexicographique inverse. S'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 ordonné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ètre est donné par l'hypothèse d'induction de cette récurrence. Les valeurs des n-uplets de paramètres sont bien ordonné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 ensembles, seulement avec les variables libres x et 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 standard de ZF muni des mêmes ordinaux) et nous pouvons supposer 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 qui couvre les classes propres d'ensembles non vides; il est donc plus puissant que l'axiome du choix habituel.

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(z₁, ..., z_k) avec z₁, ..., z_k appartenant à L_β constituée de moins de n symboles (les constantes contenues dans L_β comptent pour un symbole), nous obtenons que P(z₁, ..., z_k) est vérifiée dans L_β si et seulement si elle est vérifiée dans L.

Soit ${\displaystyle S\in L_{\alpha }}$, et T n'importe quel sous-ensemble constructible de S. Il existe alors un ordinal β pour lequel ${\displaystyle T\in L_{\beta +1}}$, donc ${\displaystyle 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 ${\displaystyle z_{i}}$ choisis dans ${\displaystyle L_{\beta }}$. Par le théorème de Löwenheim-Skolem inversé, il existe nécessairement un ensemble transitif K contenant ${\displaystyle L_{\alpha }}$ et un ${\displaystyle w_{i}}$, qui possède une théorie du premier ordre identique à ${\displaystyle L_{\beta }}$ dont le ${\displaystyle w_{i}}$ serait substitué par ${\displaystyle z_{i}}$; ce K aura le même cardinal que ${\displaystyle L_{\alpha }}$. comme ${\displaystyle V=L}$ est vérifiée dans ${\displaystyle L_{\beta }}$, il est aussi vrai dans K, par conséquent ${\displaystyle K=L_{\gamma }}$ pour un γ qui a le même cardinal qu'α. Donc ${\displaystyle 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 ${\displaystyle L_{\beta }}$ et ${\displaystyle L_{\gamma }}$ ont la même théorie. T est donc dans ${\displaystyle L_{\gamma +1}}$.

Tous les sous-ensembles constructibles 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 ${\displaystyle 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 ${\displaystyle \|\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.

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 libres pour X et α. En l’utilisant, nous pouvons étendre la définition pour n’importe quel ensemble constructible. Si s∈L_α+1, alors s = {y|y∈L_α et Φ(y,z₁,...,z_n) sont vérifiées dans (L_α,∈)} pour une formule Φ et un z₁, ..., z_n de L_α. C'est la même chose de dire : pour tout y, y∈s si et seulement si [il existe un X tel que X=L_α et y∈X et Ψ(X, y, z₁, ..., z_n)] dans laquelle Ψ(X, ...) est le résultat de la restriction de tous les quantificateurs aux ensembles de X dans Φ(...). Notons que chaque z_k∈L_β+1 pour un β<α. Combinons alors les formules destinées aux z avec la formule affectée à s. Si nous appliquons une quantification existentielle 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_α.

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

Un modèle de la théorie des ensembles 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 de tous les ordinaux.

L(A) est définie par récurrence transfinie

• L₀(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 ${\displaystyle L_{\lambda }(A)=\bigcup _{\alpha <\lambda }L_{\alpha }(A)\!}$.
• ${\displaystyle 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 axiome du choix 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 Def_A (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 remplacé 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'exception 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.