Théorème 4Logique du premier ordre

Théorème de Löwenheim-Skolem descendant

Énoncé

Toute théorie cohérente dans un langage dénombrable, au sens de la métathéorie, a un modèle fini ou dénombrable.

Démonstration

Soit $T$ une théorie cohérente sur une signature $\mathcal L$ finie ou dénombrable. Reprenons la démonstration du théorème de complétude en lisant la taille du modèle construit.

Par le point (iii) de l'extension par témoins, les mots sur l'alphabet de la signature $\mathcal L^+$ sont énumérés explicitement ; en particulier, ses énoncés forment une suite $\sigma_0, \sigma_1, \dots$ , et ses termes clos une suite $t_0, t_1, \dots$ . Le prolongement $\widehat T$ de $T \cup H$ s'obtient donc par le cas dénombrable (i) du lemme de Lindenbaum, sans aucun choix.

Le domaine du modèle des termes clos de $\widehat T$ est $M = \{[t] : t \in K\}$ , où $K$ est l'ensemble des termes clos de $\mathcal L^+$ : tout élément de $M$ est la classe d'un terme clos.

Associons à chaque $a \in M$ le plus petit entier $n$ tel que $[t_n] = a$ : c'est une application injective de $M$ dans l'ensemble des entiers, puisque l'entier $n$ associé à $a$ détermine $a = [t_n]$ . Son image est un ensemble d'entiers, fini, ou infini et alors énuméré sans répétition par ordre de grandeur ; $M$ est donc fini ou dénombrable.

La structure pour $\mathcal L$ obtenue en oubliant les nouvelles constantes a le même domaine, et c'est un modèle de $T$ . Dans toute cette démonstration, rien n'est choisi.

□

Remarque

Le modèle obtenu peut être fini : si $T$ contient $\forall x\, \forall y\, (x = y)$ , tous les termes clos sont dans la même classe, et $M$ n'a qu'un élément.

Pour obtenir un modèle infini et dénombrable d'une théorie $T$ qui a un modèle infini, on applique le théorème à $T$ augmentée, pour chaque $n$ , de l'énoncé qui affirme l'existence d'au moins $n$ éléments distincts : cette théorie a un modèle, le modèle infini de $T$ , donc elle est cohérente par la correction, et chacun de ses modèles est infini.

Remarque

D'où le paradoxe de Skolem : si $\mathsf{ZFC}$ est cohérente, elle a un modèle dénombrable, bien qu'elle démontre l'existence d'ensembles non dénombrables comme $\mathbb R$ . Il n'y a pas de contradiction : dans ce modèle, l'ensemble qui joue le rôle de $\mathbb R$ est dénombrable vu de l'extérieur, mais aucune bijection avec $\mathbb N$ n'appartient au modèle.

Remarque

La démonstration qui précède n'emploie aucune forme de l'axiome du choix, que le nœud Axiome du choix posera. La forme générale du théorème, qui fournit pour toute structure $\mathcal M$ sur un langage dénombrable une sous-structure élémentaire finie ou dénombrable, équivaut au choix dépendant : c'est une partie finie ou dénombrable du domaine, stable par les symboles, qui satisfait exactement les mêmes formules que $\mathcal M$ pour les valuations qui y prennent leurs valeurs.

Repose sur

Théorème de complétude

Sert à

Aucune fiche de ce graphe ne l'utilise encore.