Théorème de Löwenheim-Skolem

Partons d’une formalisation de la logique des prédicats du 1^er ordre. Celle-ci contient des variables d’objets, des variables de propositions, des variables de prédicats unaires, binaires, etc., des fondeurs propositionnels et les quantificateurs. On appelle champ d’interprétation la donnée des domaines suivants :
— un domaine d’objets quelconques D_o, ou domaine de base, que l’on fait correspondre aux variables d’objets ;
— le domaine D_v = df{1,0}, intuitivement le domaine {vrai, faux} qui correspondra aux variables de propositions ;
— le domaine des applications de D_o vers D_v, que l’on fait correspondre aux variables de prédicats unaires ;
— le domaine des applications de D_o × D_o vers D_v que l’on fait correspondre aux variables de prédicats binaires ; et ainsi de suite.

Les opérateurs propositionnels sont définis par les tables de vérités usuelles et (∀x) A a la valeur 1 si A a la valeur 1 pour toute valeur de x. (V. calcul des prédicats.)

Dès lors, une expression bien formée A de la logique des prédicats est dite réalisable sur si l’on peut attribuer à chacune de ses variables un élément du domaine correspondant (donner à A une assignation) et que le résultat par les opérateurs et les quantificateurs soit 1. A sera valide sur , si le résultat a la valeur 1 pour toute assignation possible. A sera valide (sans plus) si elle est valide sur tout champ dans lequel D_o n’est pas vide.

Supposons maintenant que l’on ajoute à la logique des prédicats de nouvelles constantes et des axiomes appropriés (comme nous l’avons fait, par exemple, pour ). On obtient ce qu’on appelle une logique appliquée ℒ des prédicats du 1^er ordre. On dit alors que ℒ possède un modèle s’il existe un champ d’interprétation dans lequel tous les théorèmes de ℒ sont valides sur . Un modèle est fini, dénombrable, non dénombrable si D_o est fini, dénombrable, non dénombrable.

Remarque

Au sens strict, la logique des prédicats avec identité est déjà une logique appliquée.

La notion de modèle permet de revenir sur celles de consistance et de complétude. On dira qu’un système est sémantiquement consistant s’il possède au moins un modèle. L’anglais dit satisfiable et l’allemand erfüllbar. D’autre part, un système est sémantiquement complet (on dit aussi complet au sens faible) s’il existe un modèle par rapport auquel toute expression bien formée valide est un théorème. La complétude sémantique est donc relative au modèle choisi.

Par ailleurs, l’étude des modèles conduit à des résultats importants.

En 1915, Leopold Löwenheim avait établi un théorème, généralisé par Skolem en 1920 et qui conduit au théorème dit « de Löwenheim-Skolem » :

Si une logique appliquée du 1^er ordre est consistante, elle admet un modèle dénombrable.

Ce théorème mène à une conséquence fondamentale. Il est en effet possible, dans une logique appliquée du 1^er ordre, de formaliser diverses théories mathématiques et, en particulier, celle des ensembles. Or, cette dernière comporte des ensembles non dénombrables, mais, dans la mesure où sa formalisation est consistante, il est néanmoins possible de donner un domaine D_o dénombrable, de telle sorte que tous les théorèmes soient satisfaits (paradoxe de Skolem). Cela a conduit Thoralf Skolem (1887-1963) à admettre que la notion d’ensembles dénombrables et non dénombrables n’était que relative et dépendait de l’axiomatisation choisie.

Une autre conséquence découle immédiatement de là. Disons qu’un système formel est catégorique si tous ses modèles sont isomorphes. est-il catégorique ? Il possède de toute évidence des modèles isomorphes.

En voici, par exemple, deux :

Les signes –, + et . dans les modèles ont leur signification arithmétique normale, et le modèle 1 est celui qui est visé par Peano.

Skolem en 1934 a démontré non seulement que possédait des modèles non isomorphes à ceux-ci (modèles non standard), mais que toute formalisation de l’arithmétique dans une logique du 1^er ordre possédait de tels modèles, c’est-à-dire qu’elle ne pouvait être catégorique.

Notons, pour terminer, qu’il est possible d’obtenir une formalisation catégorique de l’arithmétique, mais à deux conditions. D’une part, il faut faire usage de la logique des prédicats du 2^e ordre (les variables de prédicats y sont quantifiées) et, d’autre part, il faut s’en tenir aux modèles tels qu’ils ont été définis, modèles dans lesquels on fait correspondre, aux variables de prédicats à n places, toutes les applications de D_o vers D_v.

J.-B. G.

 S. C. Kleene, Introduction to Metamathematics (Amsterdam, 1952) ; Mathematical Logic (New York, 1967 ; trad. fr. Logique mathématique, A. Colin, 1971). / J. Ladriere, les Imitations internes des formalismes (Nauwelaerts, Louvain et Gauthier-Villars, 1957). / R. M. Smullyan, Theory of Formal Systems (Princeton, N. J., 1961). / R. Martin, Logique contemporaine et formalisation (P. U. F., 1964). / G. Kreisel et J. L. Krivine, Éléments de logique mathématique. Théorie des modèles (Dunod, 1967).