Introduction à la théorie des modèles

Motivations

Considérons les deux énoncés suivant:

«La Terre tourne autour du Soleil.»
«Si il neige, il neige.»

Les deux énoncés sont vrais, mais il n'ont pas vraiment le même statut. Nous savons que le premier énoncé est vrai grâce (entre autres) aux observations astronomiques. Mais à la limite, on pourrait imaginer un univers parallèle dans lequel ce n'est pas le cas. Par contre, le deuxième énoncé est forcément vrai, c'est à dire il n'y a pas besoin de faire la moindre observation pour être sûr que c'est vrai. On peut dire que cet énoncé est vrai dans tout les univers possibles. On ne peut se placer dans un univers imaginaire dans lequel cet énoncé serait faux.

Comme le deuxième énoncé est vrai dans tout les mondes possibles, on va dire que cet énoncé est une loi logique. On peut définir cette notion de façon un peu plus précise. Au lieu de parler de «mondes possibles», nous allons parler de modèles. Une loi logique est donc un énoncé vrai dans tout les modèles. Si un énoncé $A$ est vrai dans un certain modèle $M$ (un certain monde), alors on dit que $M$ est modèle de $A$ , et on écrit cela symboliquement:

M ⊧ A

Si $A$ est une loi logique, on peut écrire:

⊧ A

Et il faut comprendre par cette notation que tout modèle $M$ est modèle de $A$ . De même que l'on a définit la notion de loi logique, il est naturel de définir la notion de contradiction, une contradiction est simplement un énoncé faux dans tout les modèles, et l'on peut noter:

⊭ A

Il reste à définir de façon précise la notion de modèle.

Notion de modèle

Nous allons énoncer une série de définitions qui va nous amener à définir rigoureusement la notion de modèle.

Définition 9.

Soit $U$ un ensemble, un $n$ -uple de $U$ est une suite ordonnée de $n$ éléments de $U$ .

Notation: si les éléments de $U$ sont notés $u_{1}, u_{2}, u_{3}, . . .$ , alors $(u_{1}, u_{2}, . . ., u_{n})$ est un $n$ -uple de $U$ . Un élément de $U$ peut être vu comme un $1$ -uple, et un $2$ -uple est aussi appelé un couple. On va aussi convenir que l'on a:

(u_{1}, u_{2}, . . ., u_{n - 1}, u_{n}) = ((u_{1}, u_{2}, . . ., u_{n - 1}), u_{n})

Notons donc $U^{n}$ l'ensemble des $n$ -uples de l'univers, nous avons alors la:

Définition 10.

Soit $U$ un ensemble, une relation $n$ -aire sur $U$ est un sous-ensemble de $U^{n}$ .

On conviendra d'utiliser de façon générale le terme de relation pour désigner une relation d'arité $n$ quelconque.

Définition 11.

Soit $E$ et $F$ des ensembles, une fonction $n$ -aire définie sur $E$ et à valeur dans $F$ , est un ensemble de couples $(a, b)$ tel que $a$ appartienne à $E^{n}$ et $b$ appartienne à $F$ , et tel que pour un élément donné $x$ de $E^{n}$ , il existe au plus un élément $y$ de $F$ , tel quel le couple $(x, y)$ soit élément de la fonction.

On conviendra d'utiliser de façon générale le terme de fonction pour désigner une fonction d'arité $n$ quelconque.

Définition 12.

Soit $E$ et $F$ des ensembles, une application $n$ -aire définie sur $E$ et à valeur dans $F$ , est une fonction définie sur $E$ et à valeur dans $F$ tel que pour tout élément $x$ de $E^{n}$ , il existe un élement $y$ de $F$ , tel que le couple couple $(x, y)$ soit élément de la fonction.

On conviendra d'utiliser de façon générale le terme d'application pour désigner une application d'arité $n$ quelconque.

Définition 13.

Soit $L$ un langage prédicatif, une $L$ -structure est la donnée d'un ensemble non vide $U$ appelé univers, d'un ensemble de relations sur $U$ appelé prédicats, et d'un ensemble d'appplications définies sur $U$ et à valeur dans $U$ . De plus, pour tout $n$ , si $L$ possède des symboles prédicatifs $n$ -aires, il doit y avoir dans la $L$ -structure au moins un prédicat $n$ -aire; de même, pour tout $n$ , si $L$ possède des symboles fonctionnels $n$ -aires, il doit y avoir dans la $L$ -structure au moins une application $n$ -aire.

Définition 14.

Soit $L$ un langage prédicatif, $U$ l'univers d'une $L$ -structure, une interprétation de $L$ associe:

à chaque symbole propositionnel de l'alphabet de $L$ une et une seule valeur de vérité: $T$ ou $F$ ,
à chaque constante de l'alphabet de $L$ un élément de $U$ ,
à chaque symbole prédicatif $n$ -aire de l'alphabet de $L$ un prédicat $n$ -aire de la $L$ -structure,
à chaque symbole fonctionnel $n$ -aire de l'alphabet de $L$ une application $n$ -aire de la $L$ -structure.

Nous arrivons enfin à la définition d'un modèle:

Définition 15.

Soit $L$ un langage prédicatif, un modèle pour $L$ est la donnée d'une $L$ -structure et d'une interprétation de $L$ .

Exemple. Considérons un langage prédicatif très simple: aucun symbole propositionnel, seulement deux symboles prédicatifs, $p^{1}$ et $q^{1}$ (d'arité $1$ ), et aucun symbole fonctionnel. Définissons maintenant une $L$ -structure. Comme Univers, prenons l'ensemble:

U = {chat, chien, pigeon, crocodile, ordinateur}

Et prenons les deux prédicats (unaires) suivant:

P = {chat, chien, pigeon, crocodile}

et:

Q = {chat, chien}

$P$ correspond intuitivement à «est un animal», tandis que $Q$ correspond intuitivement à «est un mammifère». On va bien sûr choisir comme interprétation de $L$ celle qui associe au prédicat $P$ le symbole prédicatif $p^{1}$ , et au prédicat $Q$ le symbole prédicatif $q^{1}$ . Toujours intuitivement, la phrase (ou énoncé) suivante:

«Tout les mammifère sont des animaux.»

va s'écrire:

\forall x (q^{1} x \Rightarrow p^{1} x)

Si de plus, on convient que (par exemple) l'interprétation associe la constante $a$ à l'élément « $ordinateur$ », alors la phrase:

«L'ordinateur n'est pas un animal.»

correspond à:

\neg p^{1} a

Autre exemple. Choisissons un langage prédicatif sans symbole propositionnel, un symbole prédicatif binaire $p^{2}$ , et un symbole fonctionnel binaire $f^{2}$ . On choisit comme Univers:

U = {0, 1, 2}

Et on définit un prédicat binaire:

P = {(0, 0), (1, 1), (2, 2)}

et une application binaire:

F = {(0, 0, 0), (0, 1, 1), (0, 2, 2), (1, 0, 1), (1, 1, 2), (1, 2, 0), (2, 0, 2), (2, 1, 0), (2, 2, 1)}

Intuitivement, $P$ correspond à l'égalité, et $F$ à l'addition modulo trois (c'est à dire une addition où l'on soustrait un multiple de trois si on arrive ou dépasse trois, de sorte que le résultat soit strictement inférieur à trois, ainsi $2 + 2 = 4$ devient $2 + 2 = 1 \mod 3$ ). On va dans l'interprétation associer $P$ à $p^{2}$ et $F$ à $f^{2}$ . Ainsi la phrase:

«Tout nombre est égal à lui-même»

devient:

\forall x p^{2} x x

Et la phrase:

«L'addition d'un nombre et de zéro redonne ce nombre.»

donne, si dans l'interprétation, on associe la constante $a$ à $0$ :

\forall x p^{2} x f^{2} x a

La phrase:

«Tout nombre peut s'exprimer comme la somme (modulo trois) de deux autres nombres.»

s'écrit:

\forall x \exists y z p^{2} x f^{2} y z

Page Précédente Sommaire