Proposition

Un ensemble E est infini si et seulement si il possède une partie indéfinissable par le schéma d'axiomes de séparation.

Démonstration

Si E possède une partie indéfinissable, alors il est infini

Tout d'abord, il est clair que pour un ensemble E fini, tous ses sous-ensembles sont définissables par le schéma d'axiomes de séparation. En effet un ensemble E' inclus dans E est fini et on peut du coup trouver un entier naturel n tel que $E' = {x_{1}; x_{2}; x_{3}; ...; x_{n}} = \{x \in E| x = x_{1} \lor x = x_{2} \lor x = x_{3} \lor x = x_{4} \lor ... \lor x = x_{n}\}$ . Par contraposée, si un ensemble E possède une partie indéfinissable via l'axiome de séparation alors il n'est pas fini.

L'ensemble F des formules du calcul des prédicats est dénombrable

On sait que l'on dispose d'un ensemble dénombrable X de variables et d'un ensemble dénombrable $Σ_{F}$ de fonctions ayant chacune une arité n. L'ensemble des termes T est tel que X est inclus dans T et pour tout $t_{1}, t_{2}, t_{3}, ... t_{n}$ de T et pour tout fonction f de $Σ_{F}$ d'arité n, $f (t_{1}, t_{2}, t_{3}, ... t_{n})$ appartient à T.

Si U est une partie dénombrable de T, alors étudions l'ensemble V des éléments t de T tel qu'il existe $t_{1}, t_{2}, t_{3}, ... t_{n}$ de U et une fonction f de $Σ_{F}$ d'aridité n pour lesquels on ait $t = f (t_{1}, t_{2}, t_{3}, ... t_{n})$ . Chacun de ces éléments peut alors être codé par un élément d'un ensemble de la forme $Σ_{F} \times U^{n}$ , qui est dénombrable puisque $Σ_{F}$ et U le sont.

Or on peut construire un ensemble dont les éléments sont exactement les éléments des ensembles de cette forme. Pour se faire, on contruit d'abord l'ensemble A dont les éléments sont les $Σ_{F} \times U^{n}$ , en utilisant le schéma d'axiomes de remplacement sur l'ensemble $ℕ^{*}$ (on remplace chaque élément $n \in ℕ^{*}$ par $Σ_{F} \times U^{n}$ ). A est alors en bijection avec $ℕ^{*}$ (justement par la fonctionnelle de remplacement en question) et est donc dénombrable. Il ne reste plus qu'à appliquer l'axiome de l'union sur A : $⋃ A$ est une réunion dénombrable d'ensembles dénombrable et est donc lui-même dénombrable (conséquence de l'axiome du choix). Finalement on utilise le schéma d'axiomes de remplacement sur $⋃ A$ pour retrouver V qui est donc lui aussi dénombrable.

Récapitulons : on part de l'ensemble dénombrable $U_{0} = X$ des variables. Pour tout entier n, on défini $U_{n + 1}$ le sous-ensemble de T obtenu à partir de $U_{n}$ via les fonctions de $Σ_{F}$ . Le raisonnement précédent permet de montrer par récurrence que tous les $U_{n}$ sont dénombrables. On a alors par définition $T = ⋃_{n \in ℕ} U_{n}$ qui est dénombrable comme réunion dénombrable d'ensembles dénombrables.

On démontrerait de même que l'ensemble des atomes de la forme $p (t_{1}, t_{2}, t_{3}, ... t_{n})$ où les t sont des termes et p un élément de l'ensemble dénombrable des prédicats $Σ_{p}$ est dénombrable. Enfin l'ensemble des formules F que l'on peut former avec les atomes, les connecteurs $\lor$ , $\land$ , $\Rightarrow$ , $\neg$ et les quantificateurs $\forall$ ,∃ est lui aussi dénombrable puisque l'ensemble des atomes l'est.

Si E est infini, alors il possède une partie indéfinissable.

Maintenant supposons que l'on ait affaire à un ensemble E infini. Un sous-ensemble E' est définissable par le schéma d'axiomes de séparation si et seulement si il existe une formule f de F tel que $E' = \{x \in E| f (x)\}$ . On fait alors l'hypothèse que à tout élément E' de $℘ (E)$ , on peut trouver une formule f qui permette de le définir. On va par conséquent construire l'application qui tout élément E' de $℘ (E)$ , associe le plus petit élément de F (qui existe car F est dénombrable donc bien ordonnable) qui permet de définir le sous-ensemble E' de E. Cette application constitue une injection de $℘ (E)$ dans F, puisque si deux sous-ensembles ont la même image, alors il sont définies par une même formule et sont donc égaux. Cette injection permet d'affirmer que $Card (℘ (E)) \leq Card (F) \leq ℵ_{0}$ . Mais comme E est infini, $ℵ_{0} \leq Card (E)$ et par transitivité $Card (℘ (E)) \leq Card (E)$ , ce qui contredit le théorème de Cantor. Notre hypothèse de départ est donc absurde : tous les sous-ensembles d'un ensemble infini ne sont pas définissables par le schéma d'axiomes de séparation.

Remarques supplémentaires

Cette démonstration fait suite à ma tentative pour bien ordonner l'ensemble des nombres réels (sans utiliser l'axiome du choix), pour laquelle il suffirait de démontrer que l'existence d'un bon ordre sur E entraîne celle d'un bon ordre sur $℘ (E)$ . Dans le cas où F n'est pas dénombrable mais simplement bien ordonnable, l'injection de $℘ (E)$ dans F permet de construire ce bon ordre sur $℘ (E)$ .

Maitenant, si on admet l'axiome du choix, tous les ensembles de E ne sont pas définissables d'après la proposition que l'on vient de démontrer. Le fait qu'il existe des sous-ensembles indéfinissables par l'axiome de séparation, entraîne alors la question suivante : Peut-on réellement ordonner $℘ (E)$ alors que l'on ne peut construire tous ses éléments ?

Cette page est conforme aux normes du W3C - Auteur : Frédéric WANG - Dernière mise à jour : lundi 27 décembre 2004