Paradoxe de Skolem

Le théorème de Löwenheim-Skolem connait plusieurs variantes. Prenons la suivante : en calcul des prédicats égalitaire du premier ordre, construit sur une signature (symboles primitifs non logiques) au plus dénombrable, tout modèle infini contient un sous-modèle dénombrable élémentairement équivalent, c'est-à-dire qu'il satisfait exactement les mêmes énoncés. En particulier la théorie des ensembles ZFC, utilise comme seul symbole non logique celui de la relation d'appartenance. Donc, si ZFC est cohérente, elle a un modèle, nécessairement infini à cause des axiomes, et ce modèle possède une sous-structure dénombrable qui satisfait exactement les mêmes énoncés, en particulier les axiomes de ZFC. Les « points » de cette structure, qui sont des ensembles, sont, en tant qu'ensembles, inclus dans la classe de tous les ensembles, le support de la structure.

Or, l'un des premiers résultats de la théorie des ensembles est la démonstration de l'existence d'un ensemble non dénombrable. C'est une conséquence immédiate du théorème de Cantor. Comment un ensemble non dénombrable pourrait-il être inclus dans une sous-structure dénombrable ?

Comme souligné par Skolem, le problème réside dans la relativité de ce qu'on appelle ici dénombrable. En théorie des ensembles, un ensemble est dénombrable s'il est en bijection avec N, l'ensemble des entiers naturels. Mais nous avons utilisé cette notion en deux sens différents : les ensembles dénombrables au sens du modèle de ZFC, et les ensembles dénombrables au sens de la théorie intuitive dans laquelle nous avons énoncé le théorème de Löwenheim-Skolem. On peut tout à fait formaliser ce théorème en théorie des ensembles, mais on ne peut faire coïncider le modèle de ZFC dans lequel on a effectué cette formalisation, et celui auquel on applique le théorème. Dans le modèle dénombrable de ZFC obtenu par Löwenheim-Skolem, il existe bien une collection (un ensemble de l'univers de la formalisation) de couples qui établit une bijection entre les ensembles N et R du modèle, mais comme R, l'ensemble des réels, n'est pas dénombrable, cette collection n'est pas représentée par un ensemble de ce modèle. Ce n'est même pas une classe. Il n'y a aucun moyen d'en parler dans ce modèle. L'ensemble R est bien non dénombrable au sens du modèle.

Le paradoxe repose sur une interprétation trop « intuitive » de la théorie axiomatique des ensembles, qui est une théorie formelle de l'appartenance au premier ordre, et sur une confusion entre méta-théorie et théorie, réminiscente des paradoxes des théories des ensembles insuffisamment formalisées comme ceux de Richard et de Berry.

Supposons que φ(x) soit une formule du premier ordre sur le langage de la théorie des ensembles qui correspond exactement à la formalisation de « x est non-dénombrable ». Le problème réside dans le fait que l'on peut avoir :

• avoir M satisfait φ(x) sans que l'interprétation de x soit un ensemble non-dénombrable ;
• avoir M satisfait x ∈ y sans que l'interprétation de x appartienne à l'interprétation de y. D'ailleurs les interprétations de x et y ne sont peut-être pas des ensembles, mais « des chiens ou des chats »[1].

L'existence, pour tout modèle de ZFC, d'une sous-structure dénombrable élémentairement équivalente, est en fait un résultat utile de théorie des ensembles.

Skolem, « Sur la logique mathématique », 1928. Article reproduit dans Jean Largeault, Logique Mathématique Textes, Armand Colin.