Logique (mathématiques)/Théorie des modèles

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Une règle de déduction est valide lorsqu’elle ne permet pas de passer de prémisses vraies à une conclusion fausse. Pour préciser cette notion de validité, il faut préciser celle de vérité mathématique.

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 vraie si on peut imaginer qu’elle est vraie, s’il y a un monde possible, idéal, dans lequel elle est vraie.

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, pour deux raisons.

• Elle donne une définition de la vérité et de la conséquence logique indépendante de l'approche syntaxique de la prouvabilité, jusqu'alors adoptée par tous les logiciens. Syntaxique veut dire ici qu'on donne des règles de manipulation des symboles.
• 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. Le théorème de complétude de Kurt Gödel peut être considéré comme le théorème fondamental de la théorie des modèles. 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.

On ne peut pas la considérer comme une réponse complète à la question de la nature de la vérité mais seulement comme une réponse minimale. Par minimale, il ne faut pas entendre que personne ne doit contester ses principes mais seulement qu’elle est une réponse respectable, efficace au moins pour résoudre quelques problèmes élémentaires.

Les modèles et l'imagination

Les énoncés mathématiques portent sur des êtres abstraits. Un théorème est vrai lorsque ces êtres abstraits sont idéalement comme il le dit. Mais comment être vraiment sûr que les êtres abstraits existent et que nous savons ce qu’ils sont ? Comment connaissons-nous tout ce que nous connaissons sur les êtres idéaux ?

Un être idéal existe aussi longtemps qu’on peut y penser. On peut penser à un être si on peut le nommer et développer une bonne théorie à son sujet.

Un fait logique suffit pour établir l’existence d’un être idéal. Cet être existe parce que je lui ai donné un nom. Tout être rationnel dispose d’un tel pouvoir divin, mais il est restreint aux mondes virtuels. C’est simplement un cas particulier de la puissance de l’imagination. Pour n’importe quel nom, on peut imaginer qu’on connaît un être ainsi nommé.

Les prédicats d’un être idéal peuvent aussi être établis avec un simple fait. Ces prédicats sont vrais pour cet être parce que j’ai décidé qu’ils le sont. N’importe quelle vérité par convention peut ainsi être choisie. Il n’y a qu’une seule restriction. Si j’ai décidé qu’un prédicat est vrai pour un objet, alors je ne dois pas décider aussi qu’il ne l’est pas. Ce principe de cohérence est une façon très naturelle de penser à la raison.

Nous savons qu’un être idéal existe et que ses prédicats sont vrais quand nous avons une théorie cohérente dans laquelle cet être est nommé et ses prédicats sont considérés comme vrais. De ce point de vue, les questions sur l’existence des êtres idéaux et sur notre savoir à leur sujet sont identiques aux questions sur la cohérence des théories. Cette réponse minimale à la question de la nature de la vérité mathématique a été défendue par David Hilbert, en réponse aux objections sur l’existence d’êtres problématiques.

Les vérités mathématiques sont semblables aux vérités expérimentales sauf qu’elles portent sur des mondes virtuels, alors que les vérités expérimentales portent sur notre unique monde réel. Un monde virtuel est couramment appelé un modèle de la théorie.

Les modèles et les ensembles de formules atomiques

Un modèle est défini lorsque toutes les vérités virtuelles de base sont définies. Au point de vue technique, les vérités virtuelles de base sont définies par un ensemble de formules atomiques. 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 sorte d’atomicité logique.

Une formule atomique est considérée comme vraie si elle est dans l’ensemble choisi de toutes les formules atomiques vraies, sinon elle est fausse. Il s’agit simplement de vérités conventionnelles. Tarski a énoncé cette définition de la vérité avec l’exemple suivant. La phrase « la neige est blanche » est vraie si et seulement si la neige est blanche.

Quand l’ensemble de toutes les vérités atomiques et l’ensemble de tous les objets de la théorie (son univers d’objets) sont définis alors la vérité ou la fausseté de toutes les formules bien composées (avec la grammaire de la logique du premier ordre) sont également définies. Supposons par exemple qu'A(x) est une formule atomique lorsque x est remplacé par un nom d’objet. Alors la formule complexe (pour tout x, A(x) ) est vraie si et seulement si toutes les formules atomiques A(x) sont vraies pour tous les noms x dans le domaine des noms d’objets. 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.

L'interprétation des axiomes dans un modèle

Une théorie est définie par un système, fini ou infini dénombrable, d’axiomes. La vérité des formules atomiques est définie quand on a une interprétation de la théorie. Une interprétation est définie par les éléments suivants.

• Un ensemble U, l’univers de la théorie. Le quantificateur, pour tout x, est interprété comme, pour tout x dans U.
• À chaque nom d’objet (constante) mentionné dans les axiomes est associé un élément de U.
• À chaque prédicat unaire (à une place) fondamental mentionné dans les axiomes est associé une partie de U, l’extension de ce prédicat.
• À chaque prédicat binaire fondamental mentionné dans les axiomes est associé une partie du produit cartésien de U et 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 les axiomes est associé une fonction de U dans U.
• À chaque opérateur binaire mentionné dans les axiomes est associé une fonction de U X 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 sont vrais relativement à cette interprétation.

L'usage du mot, modèle, est parfois un peu confus. 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.

La complexité d’une formule est mesurée par le nombre maximal d’opérateurs emboîtés. Par exemple dans ((non p) ou (q et r)) , 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 au maximum deux opérateurs emboîtés.

Les formules de complexité 0 sont les formules atomiques. Elles sont vraies si elles sont dans l'ensemble, défini par convention, des formules atomiques vraies ; sinon elles sont fausses.

Supposons que la vérité et la fausseté de toutes les formules de complexité n sans variables libres 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. On a l'un des six cas suivants (si l’on a adopté ces opérateurs logiques comme opérateurs de construction des formules, voir Prédicats et Calcul des prédicats)

a) p = non q

b) p = (q et r)

c) p = (q ou r)

d) p = (si q alors r)

e) p = (pour tout x)q

f) p = (il existe un x tel que q)

q et r sont des formules de complexité n, ou inférieure, dont la vérité ou la fausseté est donc déjà définie, sauf si elles contiennent des variables libres.

a) 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) Si q et r sont tous les deux vrais alors p aussi, mais p est faux dans tous les autres cas.

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

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

e) Si l'une des formules obtenues en substituant une constante (un élément de U) à toutes les occurrences libres de x dans q est fausse, alors p est fausse ; sinon, si q n'a pas d’autres variables libres que x, p est vraie.

f) Si l'une des formules obtenues en substituant une constante (un élément de U) à toutes les occurrences libres de x dans q est vraie, alors p est vraie ; sinon, si q n'a pas d’autres 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éfinie à partir d’un modèle.