théorème de Löwenheim-Skolem

C'est le plus ancien des résultats fondamentaux de la théorie des modèles.

Il en existe plusieurs versions dues successivement à L. Löwenheim, T. Skolem, A. Tarski. La plus générale est principalement l'œuvre de Tarski.

Ce résultat se présente sous une forme paradoxale qui a provoqué bien des discussions. Dans sa première version, il énonce, en effet, que si un ensemble dénombrable d'énoncés élémentaires a un modèle infini, alors il a un modèle dénombrable. Par exemple, si la théorie axiomatique des ensembles admet un modèle, alors elle admet un modèle dénombrable, lequel contient évidemment des ensembles non dénombrables comme l'ensemble des sous-ensembles de nombres entiers ! Il en découle qu'on ne peut distinguer, dans un langage formel du premier ordre, entre le dénombrable et le non–dénombrable. C'est pourquoi analystes ou théoriciens des ensembles voient dans le théorème de Löwenheim-Skolem un inconvénient ou une limite de la logique élémentaire.

En fait, il représente pour celle-ci un précieux outil de construction de modèles. Sous sa forme la plus générale, il établit, en effet, qu'un ensemble d'énoncés élémentaires d'un langage ayant un nombre dénombrable de symboles primitifs qui a un modèle infini a des modèles de tout cardinal infini.

Mais il est vrai que c'est un théorème spécifique de la logique élémentaire dans le sens suivant : une logique dont le pouvoir d'expression dépasse celui du premier ordre n'admet pas simultanément un analogue du théorème de Löwenheim-Skolem et un analogue du théorème de complétude (ou du théorème de compacité). Autrement dit, la validité conjointe du théorème de Löwenheim-Skolem et de l'un des deux autres caractérise la logique élémentaire.