Ce théorème s’applique à des théories du premier ordre. Un langage (ou une signature) est un ensemble de symboles de constantes, de fonctions et de relations. Une théorie est un ensemble d’axiomes formulés dans ce langage. Un modèle d’une théorie est une structure mathématique (un univers et une interprétation des symboles) dans laquelle tous les axiomes de la théorie sont vrais.
La cardinalité d’un modèle est la cardinalité de son univers. La cardinalité d’un langage est le nombre de symboles qu’il contient.
Le théorème se décline en deux versions :
- Version Descendante : Soit $T$ une théorie dans un langage au plus dénombrable. Si $T$ admet un modèle infini, alors elle admet un modèle dénombrable (la plus petite cardinalité infinie).
- Version Ascendante : Soit $T$ une théorie dans un langage au plus dénombrable. Si $T$ admet un modèle infini, alors pour toute cardinalité infinie $\kappa$, $T$ admet un modèle de cardinalité $\kappa$.
Esquisse de la Démonstration
Démonstration de la Version Descendante
Cette preuve est une conséquence assez directe de la démonstration du théorème de complétude de Gödel (via la méthode de Henkin).
- Existence d’un modèle : L’hypothèse est que la théorie $T$ admet un modèle infini, $M$. Cela signifie que $T$ est consistante.
- Construction du modèle canonique : La preuve de Henkin pour le théorème de complétude montre que si une théorie est consistante, on peut construire un modèle pour elle (le « modèle canonique »).
- Cardinalité du modèle construit : L’étape cruciale est d’examiner la taille de ce modèle. L’univers du modèle canonique est construit à partir des termes du langage. Si le langage de départ est dénombrable, le nombre de formules et de termes que l’on peut construire est également dénombrable. Même après l’ajout des constantes de Henkin (qui sont en nombre dénombrable si le langage l’est), l’univers du modèle final reste dénombrable.
- Conclusion : On a donc construit un modèle de $T$ qui est dénombrable.
Démonstration de la Version Ascendante
Cette preuve utilise le théorème de compacité, qui est lui-même une conséquence du théorème de complétude.
- Théorème de Compacité : Une théorie $T$ a un modèle si et seulement si toute sous-partie finie de $T$ a un modèle.
- Enrichissement du langage : Soit $T$ une théorie ayant un modèle infini, et soit $\kappa$ une cardinalité infinie quelconque. On enrichit le langage de $T$ en ajoutant un ensemble de $\kappa$ nouvelles constantes, $C = \{c_i \mid i \in I\}$ où $|I|=\kappa$.
- Extension de la théorie : On étend la théorie $T$ en une nouvelle théorie $T’$ en ajoutant une infinité d’axiomes qui forcent les nouvelles constantes à être distinctes : $$ T’ = T \cup \{ c_i \neq c_j \mid i, j \in I, i \neq j \} $$
- Consistance de la nouvelle théorie : Montrons que $T’$ admet un modèle en utilisant le théorème de compacité. Soit $T’_0$ une sous-partie finie quelconque de $T’$. $T’_0$ contient un nombre fini d’axiomes de $T$ et un nombre fini d’axiomes de la forme $c_i \neq c_j$. Puisque $T$ admet un modèle infini, on peut toujours interpréter ce nombre fini de nouvelles constantes par des éléments distincts de ce modèle, tout en satisfaisant les axiomes de $T$. Donc, toute sous-partie finie $T’_0$ de $T’$ admet un modèle.
- Conclusion : Par le théorème de compacité, la théorie $T’$ entière admet un modèle, notons-le $M’$. Dans ce modèle $M’$, tous les axiomes de $T$ sont vrais, et toutes les constantes $\{c_i\}$ sont interprétées par des éléments distincts. L’univers de $M’$ contient donc au moins $\kappa$ éléments. Sa cardinalité est donc supérieure ou égale à $\kappa$. (Une version plus fine du théorème permet de construire un modèle de cardinalité exactement $\kappa$).
Le Paradoxe de Skolem
Le théorème de Löwenheim-Skolem a des conséquences qui peuvent sembler paradoxales. Considérons la théorie des ensembles ZFC. C’est une théorie dans un langage dénombrable. Le théorème de Cantor, qui est un théorème de ZFC, prouve l’existence d’ensembles indénombrables (comme $\mathbb{R}$).
Pourtant, le théorème de Löwenheim-Skolem (descendant) nous dit que si ZFC est consistante, alors elle doit admettre un modèle dénombrable. Comment un modèle dénombrable peut-il contenir un objet qui, de son point de vue interne, est « indénombrable » ?
La résolution de ce paradoxe réside dans la distinction entre ce qui est « interne » et « externe » au modèle. Dans le modèle dénombrable de ZFC, l’ensemble qui « joue le rôle » de $\mathbb{R}$ est lui-même un ensemble dénombrable d’éléments. Cependant, la bijection qui mettrait en correspondance cet ensemble avec $\mathbb{N}$ n’existe pas *à l’intérieur* du modèle. Le modèle est trop « pauvre » pour contenir cette fonction. Ainsi, du point de vue du modèle, cet ensemble est bien indénombrable, même si un observateur extérieur peut voir que son univers est dénombrable.