2. Théorie des modèles
La notion de modèle en logique s'attache à établir le lien précis entre les formules – qui sont des objets finis purement syntaxiques – et les structures elles-mêmes (construites de manière ensembliste), qui pourront posséder ou non les propriétés exprimées par les formules.
Choisissons par exemple le langage composé des symboles =, + et s (en plus des symboles purement logiques). Des formules de ce langage seront par exemple : pour tout x : x + s(y) = s(x + y) ; pour tout x, pour tout y, pour tout z : (x + y) + z = x + (y + z).
Un modèle de ces deux formules sera une structure vérifiant les formules. Un tel modèle pourrait être ici la donnée de (ℕ, s',+') avec ℕ l'ensemble des entiers, s' la fonction successeur de ℕ dans ℕ, +' l'addition entre entiers (il faut distinguer les symboles s et + des objets ensemblistes qui constituent le modèle et qu'on note s' et +'). Il existe bien d'autres possibilités, par exemple prenant comme ensembles d'objets de base des ensembles finis ou infinis non dénombrables.
Parmi ses résultats, la théorie des modèles indique pour le calcul des prédicats du premier ordre (un seul type d'objet est envisagé pour les quantifications « quel que soit » et « il existe ») que :
– si un ensemble de formules F possède un modèle, alors F possède aussi un modèle dont la base est infinie dénombrable (théorème de Löwenheim et Skolem, 1915 et 1920) ;
– si un ensemble de formules F ne possède pas de modèle, alors il existe un sous-ensemble fini de F qui n'en possède pas (théorème de finitude) ;
– un ensemble de formules F possède un modèle, si et seulement si on ne peut déduire de F (en utilisant les règles de raisonnement du calcul des prédicats) une contradiction (théorème de complétude de Kurt Gödel, 1930).
[…]… pour nos abonnés, l'article se prolonge sur 2 pages…
