Théorie des modèles

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Modèle.

La théorie des modèles est une branche de la logique mathématique. Son principe de base est qu’une théorie est mathématiquement valide si on peut définir un univers dans lequel elle est vraie.

Présentation de la théorie des modèles[modifier | modifier le code]

Elle a été formulée d’une façon complète et cohérente d’abord par Alfred Tarski, dans un article fondateur, Le concept de vérité dans les langages formalisés, publié en 1933 (et traduit dans le recueil Logique, sémantique, métamathématique, Armand Colin 1972, p. 157-269). Tarski a considéré une formule apparemment triviale : « il neige » est une proposition vraie si et seulement si il neige. (p. 163), la nature de cet exemple étant de montrer la différence entre l'objet linguistique et son interprétation.

Tarski a appelé sa théorie la sémantique du calcul des prédicats, pour deux raisons :

  • Elle donne une définition de la vérité et de la conséquence logique, indépendante de ce que donnent les démonstrations[1] en logique ;
  • Elle donne une réponse partielle à la question de la signification du langage, parce que les mots ont du sens s'ils permettent de faire des phrases vraies dans un monde possible.

Mais ses racines sont beaucoup plus lointaines. Un premier modèle délibérément créé apparaît avec la naissance des géométries non euclidiennes. D'abord purement déductives, ces géométries ont peu à peu été acceptées à partir du moment où l'on a pu en donner des modèles, c'est-à-dire des supports géométriques avec des interprétations spécifiques pour désigner les droites. Poincaré par exemple donne un modèle du plan hyperbolique à partir d'un demi-plan du plan complexe.

Symétriquement, si l'on peut dire, l'abbé Buée et Jean-Robert Argand (plan d'Argand), puis Gauss et Cauchy donnent un modèle géométrique des nombres complexes.

Un modèle sert d'abord de structure pour valider une théorie logique ou mathématique.

Il existe deux notions de « consistance » ou de « cohérence » d'une théorie[2], a priori différentes, mais en fait équivalentes en logique classique du premier ordre, d'après le théorème de complétude de Gödel :

  • une notion sémantique : une théorie est satisfaisable[3] si elle possède un modèle, c'est-à-dire une structure qui permet d'interpréter tous les éléments du langage, et dans laquelle les axiomes (et les théorèmes) de la théorie sont vrais ;
  • une notion syntaxique : une théorie est non contradictoire[4] si on ne peut en dériver à la fois une formule et sa négation.

Un système de déduction est dit « correct » (tous les systèmes usuels le sont) si l'existence d'un modèle donne la certitude de travailler sur une théorie qui ne débouchera pas sur une contradiction. L'intérêt est que pour montrer la cohérence ou consistance d'une théorie, il est souvent plus facile d'en déterminer un modèle que de montrer qu'on ne peut dériver de contradiction.

Le théorème de complétude de Gödel assure qu'en logique classique du premier ordre, la réciproque est vraie : toute théorie non contradictoire possède au moins un modèle. Il clôt des recherches qui remontent au théorème de Löwenheim (1915) et qui s’inspirent d’une approche hilbertienne de la vérité mathématique, et il fournit le fondement de la théorie des modèles.

Les modèles du calcul propositionnel classique[modifier | modifier le code]

En calcul propositionnel de la logique classique, il n'y a pas de quantificateurs existentiels ou universels. Les formules sont constituées de propositions atomiques reliées itérativement par des connecteurs logiques. Un modèle consiste à définir, pour chaque variable propositionnelle atomique, une valeur de vérité (vraie ou fausse). On peut alors en déduire la vérité ou la fausseté de toute formule complexe.

La complexité d'une formule est mesurée par le nombre maximal d’opérateurs emboîtés. Par exemple dans , le ou et le non sont emboîtés l’un dans l’autre. Mais le non et le et ne le sont pas. Cette proposition est de complexité 2 parce qu’elle a au maximum deux opérateurs emboîtés.

Les formules de complexité 0 sont les formules atomiques. C'est le modèle choisi qui définit leur valeur de vérité.

Supposons que la vérité et la fausseté de toutes les formules de complexité ait été définie. Montrons comment définir la vérité et la fausseté des formules de complexité . Soit une formule de complexité , obtenue à partir de la formule ou des formules et de complexité ou inférieure, au moyen d'un connecteur logique. La vérité ou la fausseté de et est donc déjà définie.

a)  : Si est vrai alors est faux, par définition de la négation. Si est faux alors est vrai, pour la même raison.

b)  : Si et sont tous les deux vrais alors aussi, mais est faux dans tous les autres cas.

c)  : Si et sont tous les deux faux alors aussi, mais est vrai dans tous les autres cas.

d)  : Si est vrai et est faux alors est faux, mais est vrai dans tous les autres cas.

Une formule vraie dans tout modèle est dite universellement valide (en particulier, une tautologie en est une). Si la formule possède variables propositionnelles atomiques, il suffit en fait de vérifier la vérité de la formule dans les modèles possibles donnant les diverses valeurs de vérité aux propositions atomiques pour prouver que cette formule est une tautologie. Le nombre de modèles étant fini, il en résulte que le calcul des propositions est décidable : il existe un algorithme permettant de décider si une formule est une tautologie ou non.

Par ailleurs, le théorème de complétude du calcul des propositions établit l'équivalence entre être une tautologie et être prouvable dans un système de déduction adéquat.

Exemples[modifier | modifier le code]

Montrons que (loi de Peirce) est une tautologie, en utilisant la règle d). Si est vraie, alors étant de la forme est vraie. Si est faux, alors est vrai, est faux, et est vrai.

Étant vrai dans tout modèle, est une tautologie. Elle est donc également prouvable au moyen de systèmes de déduction, par exemple la déduction naturelle.

Par contre, n'est pas prouvable. En effet, dans un modèle où est faux, est également faux.

Les modèles dans le calcul des prédicats[modifier | modifier le code]

Dans le calcul des prédicats du premier ordre de la logique classique, les prédicats utilisés s'appliquent sur des variables. Pour définir un modèle, il convient donc d'introduire un ensemble dont les éléments serviront de valeurs à attribuer aux variables. Comme pour le calcul propositionnel, on commence par définir la vérité ou la fausseté des formules atomiques dans un domaine donné, avant de définir de proche en proche la vérité ou la fausseté des formules composées. On peut ainsi définir par étapes successives la vérité de toutes les formules complexes de la logique du premier ordre composées à partir des symboles fondamentaux d’une théorie.

Pour qu'un énoncé utilisant un ensemble de symbole défini par un langage soit considéré comme vrai, c'est-à-dire qu'on puisse dire qu'il soit un théorème, il faut et il suffit que toutes les -structures satisfassent l'énoncé.

Une formule est atomique lorsqu’elle ne contient pas d’opérateurs logiques (négation, conjonction, existentiation…). Atomique ne veut pas dire ici qu’une formule ne contient qu’un seul symbole mais seulement qu’elle contient un seul symbole de prédicat fondamental. Les autres noms qu’elle contient sont des noms d’objet et ils peuvent être très complexes. Qu’une formule est atomique veut dire qu’elle ne contient pas de sous-formule. Il s’agit d’une atomicité logique.

L'interprétation des formules atomiques dans un modèle[modifier | modifier le code]

Une interprétation d'un langage du premier ordre est une structure, définie par les éléments suivants.

  • Un ensemble U non vide, l’univers de la théorie. À chaque nom d’objet (constante) mentionné dans le langage est associé un élément de U.
  • À chaque prédicat unaire (à une place) fondamental mentionné dans le langage est associé une partie de U, l’extension de ce prédicat. C'est l'ensemble des valeurs pour lequel on décide que le prédicat est vrai. À chaque prédicat binaire fondamental mentionné dans le langage est associé une partie du produit cartésien U × U, c’est l’ensemble de tous les couples pour lesquels le prédicat est vrai. De même pour les prédicats ternaires, ou d’arité supérieure.
  • À chaque opérateur unaire mentionné dans le langage est associé une fonction de U dans U. À chaque opérateur binaire mentionné dans le langage est associé une fonction de U × U dans U. De même pour les opérateurs d’arité supérieure.

L’ensemble U, ou l’interprétation dont il fait partie, est un modèle d’une théorie lorsque tous les axiomes de cette théorie sont vrais relativement à cette interprétation.

L'usage du mot, modèle, est parfois multiple. Tantôt il désigne l'ensemble U, tantôt l'ensemble des formules atomiques vraies, tantôt l'interprétation. Souvent, quand on dit un modèle d'une théorie, on suppose automatiquement qu'elle y est vraie. Mais on dit aussi qu'une théorie est fausse dans un modèle.

La définition de la vérité des formules complexes[modifier | modifier le code]

Dès qu’on a une interprétation d’une théorie, la vérité de toutes les formules qui mentionnent seulement les constantes, les prédicats et les opérateurs fondamentaux, peut être définie. On commence par les formules atomiques et on procède récursivement aux formules plus complexes.

On reprend les règles définies dans le paragraphe relatif aux modèles du calcul propositionnel, et on définit les deux règles supplémentaires, relatives au quantificateur universel et existentiel.

e)  : Si l'une des formules obtenues en substituant un élément de U à toutes les occurrences libres de dans l'interprétation de est fausse alors est fausse, sinon, si n'a pas d'autres variables libres que , est vraie.

f)  : Si l'une des formules obtenues en substituant un élément de U à toutes les occurrences libres de dans l'interprétation de est vraie alors est vraie, sinon, si n'a pas d'autre variables libres que , est fausse.

e) et f) permettent de définir la vérité et la fausseté de toutes les formules closes, c’est-à-dire sans variables libres.

La vérité et la fausseté de toutes les formules complexes, sans variables libres, de la logique du premier ordre, peut donc être déterminée dans un modèle donné.

Une formule vraie dans tout modèle s'appelle loi logique ou théorème. Comme pour le calcul propositionnel, le théorème de complétude de Gödel énonce l'équivalence entre loi logique et formule prouvable dans un système de déduction adéquat. Ce résultat est remarquable, compte tenu du fait que, contrairement au calcul des propositions, le nombre de modèles pouvant être envisagé est en général infini. D'ailleurs, contrairement au calcul des propositions, le calcul des prédicats n'est pas décidable.

Exemples[modifier | modifier le code]

La formule est une loi logique. En effet, considérons un modèle U non vide. Il y a alors deux possibilités.

  • Ou bien on attribue la valeur vraie à R(y) lorsque y se voit attribuer une valeur quelconque dans U, et dans ce cas, on attribue à x une valeur quelconque dans U. L'implication est alors vraie pour tous les y dans U, donc est également vraie dans U, et x désignant également un élément de U, est vraie dans U.
  • Ou bien on attribue la valeur faux à R(y) pour au moins un y dans U. Désignons alors par x cet élément. Alors pour tout y de U, est vraie, donc est vraie dans U, et donc est également vraie.

Dans les deux cas, la formule est vraie. U étant quelconque, la formule est vraie dans tout modèle, et peut également être prouvée au moyen d'un système de déduction.

Par contre, la formule n'est pas prouvable. Il suffit de prendre comme modèle un ensemble U à deux éléments a et b, à poser P et Q(a) vraies, et Q(b) faux. est faux dans U, alors que est vraie (avec x = a). Il en résulte que est fausse dans U. La formule étant falsifiable n'est pas un théorème.

Catégoricité[modifier | modifier le code]

On dit d'une théorie qu'elle est catégorique si tous ses modèles sont isomorphes (rappel : deux modèles 𝔐, 𝔐' sont isomorphes s'il existe un homomorphisme bijectif de M dans M'). L'intérêt de manipuler des théories catégoriques réside dans leur univocité : on peut dire d'elles qu'elles caractérisent véritablement les objets dont elles énoncent les lois. Tous les énoncés valides (resp. non valides) dans un modèle donné le sont également dans tout autre modèle. À l'inverse, une théorie non-catégorique a ceci de gênant qu'elle contient des énoncés vrais (resp. faux) de ses objets qui ne le sont pas nécessairement dans un autre modèle.

Exemples[modifier | modifier le code]

(l'arithmétique de Peano axiomatisée au premier ordre) n'est pas catégorique, i.e on peut en exhiber un modèle qui n'est pas isomorphe à l'interprétation standard des entiers naturels dans lequel un certain entier est strictement plus grand que tous les entiers naturels standards. En revanche, est catégorique, et caractérise en conséquence proprement la notion intuitive que nous avons des entiers naturels.

La théorie des relations transitives et la théorie des relations réflexives axiomatisées au premier ordre sont catégoriques. En revanche, la théorie des bons ordres n'est pas catégorique au premier ordre.

Une fois découvert qu'une théorie donnée n'est pas catégorique, on peut toujours espérer qu'elle soit -catégorique pour un certain cardinal , c'est-à-dire telle que tous ses modèles de cardinalité (i.e ses modèles dont le domaine est de cardinalité ) sont isomorphes. Par exemple, on peut démontrer que la théorie des ordres linéaires denses sans extrémités est -catégorique (son seul modèle de cardinalité est à l'isomorphisme près) et que la théorie des corps algébriquement clos de caractéristique p est -catégorique pour tout .

Les modèles de la logique intuitionniste[modifier | modifier le code]

Les modèles présentés jusqu'ici sont des modèles de la logique classique. Mais il existe d'autres logiques, par exemple la logique intuitionniste qui est une logique qui construit les démonstrations à partir des prémisses. Il existe pour cette logique une théorie des modèles, les modèles de Kripke avec un théorème de complétude : une formule est démontrable en logique intuitionniste si et seulement si elle est vraie dans tout modèle de Kripke.

Ces modèles permettent par exemple de répondre aux questions suivantes. Soit une formule close :

  • Ou bien n'est pas un théorème de la logique classique. Pour le montrer, il suffit d'exhiber un modèle classique qui invalide la formule ;
  • Ou bien est un théorème de la logique classique. Pour le montrer, il suffit d'en donner une démonstration dans un système de déduction de la logique classique. Il y a alors deux sous-cas :
Ou bien est également un théorème de la logique intuitionniste. Pour le montrer, il suffit d'en donner une démonstration dans un système de déduction intuitionniste (ou de montrer que est vraie dans tous les modèles de Kripke) ;
Ou bien n'est pas démontrable en logique intuitionniste. Pour le montrer, il suffit de donner un modèle de Kripke invalidant la formule.

C'est ainsi qu'on peut démontrer que :

est un théorème de la logique classique, mais pas de la logique intuitionniste ;
est un théorème de la logique intuitionniste (et également de la logique classique).

Les modèles de Kripke servent aussi à donner des modèles pour les logiques modales.

Exemples d'application des modèles[modifier | modifier le code]

Nous avons déjà donné des applications des modèles :

  • satisfaire ou au contraire falsifier une formule (par exemple distinguer formule vraie en logique classique mais fausse en logique intuitionniste : la formule est vraie dans tout modèle classique, mais il existe un modèle en logique intuitionniste qui la falsifie) ;
  • prouver qu'une théorie ou un système d'axiomes n'est pas contradictoire en exhibant un modèle satisfaisant tous les axiomes.

En ce qui concerne les systèmes d'axiomes, les modèles interviennent également pour montrer l'indépendance des axiomes entre eux, ou établir la non-contradiction d'un système axiomatique en s'appuyant sur la non-contradiction d'un autre système (on parle alors de « consistance relative »). Donnons quelques exemples.

En géométrie, le Ve postulat d'Euclide est indépendant des autres axiomes de la géométrie. En effet, d'une part, le plan de la géométrie euclidienne est un modèle dans lequel ce postulat est vrai. D'autre part, le demi-plan de Poincaré est un modèle de la géométrie hyperbolique dans lequel ce postulat est faux. Dans ce modèle, l'univers (le plan hyperbolique) est constitué des points du demi-plan euclidien ouvert supérieur . Les droites du plan hyperbolique sont les ensembles d'équation ou .

Geodes.GIF

Dans cet univers, si on se donne une droite et un point extérieur à cette droite, il existe une infinité de droites passant par le point et non sécantes à la première droite.

Dans cet exemple, on voit qu'on peut construire un modèle de la nouvelle théorie (le plan hyperbolique et ses droites) en se servant d'un modèle de l'ancienne (dans le plan euclidien : le demi-plan et ses demi-droites et demi-cercles). Si on suppose la « cohérence » ou « consistance » de la géométrie euclidienne, alors on a établi celle de la géométrie hyperbolique.

Cette utilisation de modèles pour montrer la consistance relative d'une théorie est très fréquente. Considérons par exemple la théorie des ensembles, notée ZF. Considérons par ailleurs la théorie, notée ZFC, constituée de ZF à laquelle on ajoute l'axiome du choix. On peut montrer que si ZF est non contradictoire alors ZFC aussi. En effet (grâce au théorème de complétude de Gödel) on suppose qu'il existe un modèle de ZF. On est alors capable, dans ce modèle, d'associer à tout ordinal α un ensemble Fα de façon que :

  • la classe L « réunion » de tous les Fα vérifie tous les axiomes de ZF ;
  • les Fα sont constructibles par récurrence transfinie, dans le sens où Fα est défini à partir des Fβ, pour β < α ;
  • si l'on définit l'ordre d'un y de L comme étant le plus petit ordinal α tel que y appartienne à Fα, alors, à tout x non vide de L « on peut associer » un élément de x d'ordre minimal, que l'on note f(x).

On a alors défini une « fonction » f de L dans L (ou plus exactement, une classe fonctionnelle) vérifiant . Autrement dit, f est une « fonction de choix » dans L, si bien que L vérifie non seulement ZF mais aussi l'axiome du choix. L est donc un modèle de ZFC.

Toujours dans un modèle de ZF, si l'on pose et pour tout entier , (ensemble des parties de ), alors la réunion des pour tout entier définit un modèle qui vérifie tous les axiomes de ZF sauf l'axiome de l'infini. Ceci prouve (toujours sous l'hypothèse que ZF est non contradictoire) que ce dernier axiome ne peut être dérivé des autres axiomes.

La théorie de l'omega-stabilité[modifier | modifier le code]

L'un des objectifs de la théorie des modèles est de proposer une caractérisation et une classification des théories, en particulier des théories mathématiques, sur la base des propriétés que possèdent leurs modèles ( pour reprendre la formule de Shelah, le programme général est de construire une « classification theory », voir section 5.1 de Hodges, Wilfrid and Scanlon, Thomas, "First-order Model Theory", The Stanford Encyclopedia of Philosophy (Fall 2013 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/fall2013/entries/modeltheory-fo/>.).

La stabilité est à cet égard une propriété significative (pour les prolégomènes et le développement de la théorie de la stabilité, se rapporter notamment aux travaux de Morley et de Shelah). En particulier, pour les théories complètes dans un langage dénombrable, on peut s'intéresser à la propriété d'être -stable (on lit « oméga-stable »). 
 Nous devons au préalable introduire certaines notions. On appelle un 1-type un ensemble de formules  avec v une variable tel que  est satisfaisable dans la structure, c'est-à-dire tel que   

pour toute formule appartenant à et avec la structure, T la théorie, une assignation de variables. Il faut remarquer que la notion de type peut être généralisée : pour un n-type, on considère l'ensemble des formules avec v un n-uplet. Nous pouvons spécifier la définition précédente en considérant les 1-types sur un ensemble A : les formules de peuvent comporter des paramètres qui appartiennent à A. On dit que le 1-type t est complet si pour toute formule du langage , on a soit ou .

 Dès lors, une théorie est  -stable si pour chaque modèle de la théorie (pour chaque ensemble A inclus dans l'univers), il  existe au plus un nombre dénombrable de 1-types complets (sur A). Intuitivement, cela signifie que la théorie présente une forme de simplicité car elle ne possède pas un nombre trop grand de types, ces derniers peuvent être aisément classés : on retrouve une notion analogue à celle de base dans un espace vectoriel. Par ailleurs, l'oméga-stabilité est à mettre en relation avec la notion de catégoricité non-dénombrable; nous cherchons alors à donner sens à l'idée d'une caractérisation unique et concise d'une théorie (voir la section consacrée à la catégoricité).

Exemple :

rappel : un corps algébriquement clos est un corps tel que tous les polynômes appartenant à l'anneau des polynômes défini sur le corps ont au moins une racine dans le corps

D'après le théorème de Macintyre (1971), la théorie des corps algébriquement clos est -stable (la démonstration repose sur le théorème de la base de Hilbert, et donc l'axiome du choix.).

La propriété de stabilité peut être généralisée de la façon suivante : une théorie T dans un langage L est stable s'il existe un cardinal tel que pour tout modèle de T de cardinalité inférieure ou égale à , il y a au plus un nombre de 1-types complets.

Références : notes du cours « théorie des modèles » délivré par A. Arana dans le cadre du Master 1 LOPHISC 2016/2017 Université Paris I Panthéon-Sorbonne Hodges, Wilfrid and Scanlon, Thomas, "First-order Model Theory", The Stanford Encyclopedia of Philosophy (Fall 2013 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/fall2013/entries/modeltheory-fo/>. https://en.wikipedia.org/wiki/Model_theory https://en.wikipedia.org/wiki/Stable_theory https://ncatlab.org/nlab/show/stability+in+model+theory

Notes[modifier | modifier le code]

  1. Une démonstration repose sur des règles de déduction et des axiomes.
  2. Nous éviterons d'utiliser ces deux termes, car chacun des deux peut, selon les auteurs, désigner soit l'une, soit l'autre des deux notions qu'on cherche, justement, à distinguer. Par exemple dans les notes de cours d'E. Bouscaren, « consistance » (p. 6) désigne la notion sémantique et « cohérence » (p. 5) la notion syntaxique, tandis qu'A. Delessert, p. 185 de Gödel : une révolution en mathématiques (ISBN 2-88074-449-0), nomme « consistance » la notion syntaxique.
  3. Notes de cours d'E. Bouscaren, p. 6.
  4. Notes de cours d'E. Bouscaren, p. 5.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Ouvrage de référence[modifier | modifier le code]