Un article de Wikipedia.y-project.com.
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 laquelle elle est vraie.
[] Présentation de la théorie des modèles
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 é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 connait 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 du calcul propositionnel
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 emboités. Par exemple dans <math>(\lnot P) \lor (Q \land R)</math> , le ou <math>\lor</math> et le non <math>\lnot</math> sont emboités l?un dans l?autre. Mais le non et le et <math>\land</math> ne le sont pas. Cette proposition est de complexité 2 parce qu?elle a au maximum deux opérateurs emboité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é <math>n</math> ait été définie. Montrons comment définir la vérité et la fausseté des formules de complexité <math>n+1</math>. Soit <math>P</math> une formule de complexité <math>n+1</math>, obtenue à partir de la formule ou des formules <math>Q</math> et <math>R</math> de complexité <math>n</math> ou inférieure, au moyen d'un connecteur logique. La vérité ou la fausseté de <math>Q</math> et <math>R</math> est donc déjà définie.
a) <math>P = \lnot Q</math> : Si <math>Q</math> est vrai alors <math>P</math> est faux, par définition de la négation. Si <math>Q</math> est faux alors <math>P</math> est vrai, pour la même raison.
b) <math>P = (Q \land R)</math> : Si <math>Q</math> et <math>R</math> sont tous les deux vrais alors <math>P</math> aussi, mais <math>P</math> est faux dans tous les autres cas.
c) <math>P = (Q \lor R)</math> : Si <math>Q</math> et <math>R</math> sont tous les deux faux alors <math>P</math> aussi, mais <math>P</math> est vrai dans tous les autres cas.
d) <math>P = (Q \to R)</math> : Si <math>Q</math> est vrai et <math>R</math> est faux alors <math>P</math> est faux, mais <math>P</math> est vrai dans tous les autres cas.
Une formule vraie dans tout modèle s'appelle une tautologie. Si la formule possède <math>n</math> variables propositionnelles atomiques, il suffit en fait de vérifier la vérité de la formule dans les <math>2^n</math> modèles possibles donnant les diverses valeurs de vérité aux <math>n</math> propositions atomiques. 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.
[] 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 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 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, l?univers de la théorie. Le quantificateur, <math>\forall x</math>, est interprété comme, pour tout x dans U.
- A 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.
- A 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.
- A chaque opérateur unaire mentionné dans le langage est associé une fonction de U dans U.
- A 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 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.
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) <math>P = \forall x \;Q</math> : Si l'une des formules obtenues en substituant un élément de U à toutes les occurrences libres de <math>x</math> dans l'interprétation de <math>Q</math> est fausse alors <math>P</math> est fausse, sinon, si <math>Q</math> n'a pas d'autres variables libres que <math>x</math>, <math>P</math> est vraie.
f) <math>P = \exists x \;Q</math> : Si l'une des formules obtenues en substituant un élément de U à toutes les occurrences libres de <math>x</math> dans l'interprétation de <math>Q</math> est vraie alors <math>P</math> est vraie, sinon, si <math>Q</math> n'a pas d'autre variables libres que <math>x</math>, <math>P</math> 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.
[] Les modèles en logique intuitionniste
[] Voir également
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/Théorie des modèles
