Théorie des modèles
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

La théorie des modèles est une théorie de la vérité mathématique. Elle consiste essentiellement à dire 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 (La théorie des modèles est une théorie de la vérité mathématique. Elle consiste essentiellement à dire qu’une théorie est mathématiquement valide si on peut définir un univers dans...)

Elle a été formulée d’une façon complète et cohérente d’abord par Alfred Tarski, qui l'appelait aussi la sémantique du calcul des prédicats (Le calcul des prédicats du premier ordre, ou calcul des relations, ou logique du premier ordre, ou tout simplement calcul des prédicats est une formalisation du langage des mathématiques proposée par les...), pour deux raisons.

  • Elle donne une définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) de la vérité et de la conséquence logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la fois raison, langage, et raisonnement) est dans une première approche...) 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 (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une...) s'ils permettent de faire des phrases vraies dans un monde (Le mot monde peut désigner :) 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 (En mathématiques, le plan complexe (encore appelé plan de Cauchy) désigne un plan dont chaque point est la représentation graphique d'un nombre complexe unique.).

Symétriquement, si l'on peut dire, l'abbé Buée et Jean-Robert Argand (plan d'Argand), puis ensuite 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 (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur...) logique ou mathématique.

On dira qu'une théorie est non contradictoire s'il existe un modèle dans lequel elle est vraie. On dira qu'elle est consistante (ou cohérente) si elle ne permet pas de prouver à la fois une formule et sa négation. Il n'est pas toujours facile ou possible de montrer qu'une théorie est consistante. Il est parfois plus facile de montrer qu'elle est non contradictoire, puisqu'il suffit pour cela de mettre en évidence un modèle. Le Théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique...) de complétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui être ajouté, en un sens qu'il faut préciser dans...) de Gödel peut être considéré comme le théorème fondamental de la théorie des modèles. Il établit une équivalence entre les deux notions de non-contradiction et de consistance, et permet de montrer qu'une formule est vraie dans tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) modèle si et seulement si elle est prouvable dans un système de déduction adéquat. 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. Un modèle donne donc la certitude de travailler sur une théorie qui ne débouchera pas sur une contradiction (Une contradiction existe lorsque deux affirmations, idées, ou actions s'excluent mutuellement.).

  1. Une démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment...) est donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) par des règles de déduction et des axiomes.

Les modèles du calcul propositionnel classique

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 (En mathématiques et en logique, une variable est représentée par un symbole. Elle est utilisée pour marquer un rôle dans une formule, un prédicat ou un algorithme. En statistiques,...) propositionnelle atomique, une valeur de vérité (La notion de valeur de vérité consiste à attribuer aux énoncés des valeurs numériques au travers de fonctions dont il faudra définir les règles de composition : c'est le principe de...) (vraie ou fausse). On peut alors en déduire la vérité ou la fausseté de toute formule complexe.

La complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple...) d'une formule est mesurée par le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) maximal d’opérateurs emboîtés. Par exemple dans (\lnot P) \lor (Q \land R) , le ou \lor et le non \lnot sont emboîtés l’un dans l’autre. Mais le non et le et \land 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é n ait été définie. Montrons comment définir la vérité et la fausseté des formules de complexité n + 1. Soit P une formule de complexité n + 1, obtenue à partir de la formule ou des formules Q et R de complexité n ou inférieure, au moyen d'un connecteur logique. La vérité ou la fausseté de Q et R est donc déjà définie.

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

b) P = (Q \land R) : Si Q et R sont tous les deux vrais alors P aussi, mais P est faux dans tous les autres cas.

c) P = (Q \lor R) : Si Q et R sont tous les deux faux alors P aussi, mais P est vrai dans tous les autres cas.

d) P = (Q \to R) : Si Q est vrai et R est faux alors P est faux, mais P est vrai dans tous les autres cas.

Une formule vraie dans tout modèle s'appelle une tautologie. Si la formule possède n variables propositionnelles atomiques, il suffit en fait de vérifier la vérité de la formule dans les 2n modèles possibles donnant les diverses valeurs de vérité aux n propositions atomiques. Le nombre de modèles étant fini, il en résulte que le calcul des propositions (Le calcul des propositions ou calcul propositionnel, dont le fondateur fut le logicien allemand Frege, version moderne de la logique stoïcienne, est une théorie logique...) 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

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

Étant vrai dans tout modèle, ((P \to Q) \to P) \to P est une tautologie. Elle est donc également prouvable au moyen de systèmes de déduction, par exemple la déduction naturelle (La déduction naturelle est une façon d'exposer les principes de la logique du premier ordre pour les rendre aussi proches que possible des façons naturelles de raisonner).

Par contre, (P \to Q) \to P n'est pas prouvable. En effet, dans un modèle où P est faux, (P \to Q) \to P est également faux.

Les modèles dans le calcul des prédicats

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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) 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.

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 (Les prédicats d’une théorie sont les formules qui contiennent des variables libres.) 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

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

  • Un ensemble U non vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.), l’univers de la théorie. À chaque nom d’objet (constante) mentionné dans le langage est associé un élément de U.
  • A 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 (En mathématiques, le produit cartésien de deux ensembles X et Y est l'ensemble de tous les couples, dont la première composante appartient à X et la seconde à Y. On généralise facilement la notion de produit...) 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.
  • A chaque opérateur (Le mot opérateur est employé dans les domaines :) 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 (L’usage est l'action de se servir de quelque chose.) 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

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) P = \forall x \;Q : Si l'une des formules obtenues en substituant un élément de U à toutes les occurrences libres de x dans l'interprétation de Q est fausse alors P est fausse, sinon, si Q n'a pas d'autres variables libres que x, P est vraie.

f) P = \exists x \;Q : Si l'une des formules obtenues en substituant un élément de U à toutes les occurrences libres de x dans l'interprétation de Q est vraie alors P est vraie, sinon, si Q n'a pas d'autre variables libres que x, P 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 (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en nombre ou en taille.). D'ailleurs, contrairement au calcul des propositions, le calcul des prédicats n'est pas décidable (En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique.).

Exemples

La formule \exist x \; \forall y \; (R(x) \to R(y)) 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 attribué une valeur quelconque dans U, et dans ce cas, on attribue à x une valeur quelconque dans U. L'implication R(x) \to R(y) est alors vraie pour tous les y dans U, donc \forall y \; (R(x) \to R(y)) est également vraie dans U, et x désignant également un élément de U, \exist x \; \forall y \; (R(x) \to R(y)) 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, R(x) \to R(y) est vraie, donc \forall y \; (R(x) \to R(y)) est vraie dans U, et donc \exist x \; \forall y \; (R(x) \to R(y)) 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 \exists x (P \to Q(x)) \to (P \to \forall x Q(x)) 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. P \to \forall x Q(x) est faux dans U, alors que \exists x (P \to Q(x)) est vraie (avec x = a). Il en résulte que \exists x (P \to Q(x))\to (P \to \forall x Q(x)) est fausse dans U. La formule étant falsifiable n'est pas un théorème.

Les modèles de la logique intuitionniste

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 prouvable 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 F une formule close :

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

C'est ainsi qu'on peut prouver que :

(\lnot \forall x \;F(x)) \to (\exists x \; \lnot F(x)) est un théorème de la logique classique, mais pas de la logique intuitionniste.
(\lnot \exists x \;F(x)) \to (\forall x \; \lnot F(x)) est un théorème de la logique intuitionniste (et également de la logique classique).

Les modèles de Kripke servent (Servent est la contraction du mot serveur et client.) aussi à donner des modèles pour les logiques modales.

Exemples d'application des modèles

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 consistance d'un système axiomatique en s'appuyant sur la consistance d'un autre système. Donnons quelques exemples.

En géométrie (La géométrie est la partie des mathématiques qui étudie les figures de l'espace de dimension 3 (géométrie euclidienne)...), le Vème postulat d'Euclide (Euclide, en grec ancien Εὐκλείδης Eukleidês (né vers -325, mort vers -265 à Alexandrie) est un mathématicien de la Grèce...) est indépendant des autres axiomes de la géométrie. En effet, d'une part, le plan de la géométrie euclidienne (La géométrie euclidienne commence avec les Éléments d'Euclide, qui est à la fois une somme des connaissances géométriques de l'époque et une tentative de formalisation mathématique...) est un modèle dans lequel ce postulat est vrai. D'autre part, le demi-plan de Poincaré (Le demi-plan de Poincaré est un sous-ensemble des nombres complexes. Il a permis au mathématicien français Henri Poincaré d'éclairer les travaux du Russe Nicolaï...) est un modèle de la géométrie hyperbolique dans lequel ce postulat est faux. Dans ce modèle, l'univers (L'Univers est l'ensemble de tout ce qui existe et les lois qui le régissent.) (le plan hyperbolique) est constitué des points du demi-plan euclidien ouvert supérieur \{(x,y) \;|\; y>0 \}. Les droites du plan hyperbolique sont les ensembles d'équation (En mathématiques, une équation est une égalité qui lie différentes quantités, généralement pour poser le problème de leur identité. Résoudre l'équation consiste à déterminer toutes les...) x = a ou (xa)2 + y2 = R2.

Dans cet univers, si on se donne une droite et un point (Graphie) 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 définir les objets d'un nouveau modèle (droites du plan hyperbolique) en se servant d'autres objets d'un autre modèle (demi-droites et demi-cercles du demi-plan euclidien). Si on suppose la consistance du modèle euclidien, alors on a établi la consistance du modèle hyperbolique.

Cette utilisation de modèle pour montrer la consistance relative d'un autre modèle est très fréquente. Considérons par exemple la théorie axiomatique des ensembles (Il existe plusieurs versions formelles de la théorie des ensembles, mais quand on parle de « la » théorie axiomatique des ensembles, on désigne habituellement sous ce nom la théorie ZFC. Au XXIe siècle,...), notée ZF. Considérons par ailleurs ZF auquel on ajoute l'axiome (Un axiome (du grec ancien αξιωμα/axioma, « considéré comme digne, convenable, évident en...) du choix, notée ZFC (En mathématiques, l'abréviation ZF désigne la théorie de Zermelo-Fraenkel, ZFC quand elle comprend l'axiome du choix, théorie axiomatique des ensembles la plus couramment utilisée en mathématiques contemporaines. Bien que la théorie ne...). On peut montrer que si ZF est consistante, alors ZFC aussi. On est en effet capable de définir une fonction F définie sur les ordinaux qui à tout ordinal α associe un ensemble Fα, et la classe L = \{F_{\alpha} \;|\; \alpha \;\mathrm{ordinal} \} de façon que :

  • L vérifie tous les axiomes de ZF
  • Les ensembles Fα appartenant à L sont constructibles dans le sens où Fα est défini à partir des Fβ, pour β < α, par récurrence transfinie.
  • Pour tout x de L, on définit l'ordre de x comme étant le plus petit ordinal α tel que x = Fα.
  • A tout x de L, on peut lui associer y élément de x d'ordre minimal, définissant une fonction f de L dans L en posant y = f(x).

On a alors défini dans L une fonction f vérifiant \forall x, f(x) \in x. Autrement dit, f est une fonction de choix dans L, et L vérifie ZF ainsi que l'axiome du choix. L est donc un modèle de ZFC.

Toujours dans la théorie des ensembles (La théorie des ensembles est une branche des mathématiques créée initialement par le mathématicien allemand Georg Cantor à la fin du XIXe siècle.), si on pose R_0 = \varnothing et pour tout entier n, R_{n+1} = \mathfrak P(R_n) (ensemble des parties de Rn), alors la réunion (La Réunion est une île française du sud-ouest de l'océan Indien située dans l'archipel des Mascareignes à environ 700...) des Rn pour tout n entier définit un modèle qui vérifie tous les axiomes de ZF sauf l'axiome de l'infini. Ceci prouve que ce dernier axiome ne peut être prouvé à partir des autres axiomes.

Page générée en 0.269 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique