Syntaxe et sémantique : ce qu’une formule dit, et ce qu’elle veut dire

Une formule mathématique est une suite de signes. Elle ne devient vraie ou fausse qu’une fois placée dans un monde qui donne un sens à ces signes. Cette distinction entre ce qui relève de l’écriture et ce qui relève du sens — entre la syntaxe et la sémantique — n’est presque jamais énoncée dans l’enseignement secondaire. Elle est pourtant ce qui sépare « démontrer » de « être vrai », et sans elle le mot « démonstration » reste une intuition floue.

Cet article ouvre une nouvelle rubrique du blog, Niveau supérieur, consacrée aux articles de niveau universitaire rédigés en français. Il inaugure une série sur les fondements, tirée du chapitre 2 du Discours formel sur les mathématiques pour le secondaire.

1. Une confusion ordinaire

Considérons l’écriture suivante :

$\displaystyle \forall x\,\exists y\;(x<y)$

Est-elle vraie ? La question, telle quelle, n’a pas de réponse. Elle en aura une dès qu’on aura précisé de quoi parlent $x$ et $y$ , et ce que désigne le signe $<$ . Tant que ce n'est pas fait, nous n'avons devant nous qu'une suite de symboles correctement assemblés — rien de plus, mais rien de moins.

2. La syntaxe : un jeu de construction

Se donner un langage du premier ordre, c’est se donner deux choses. D’abord un alphabet logique, commun à tous les langages : des variables $x, y, z,\ldots$ , les connecteurs $\neg, \wedge, \vee, \Rightarrow$ , les quantificateurs $\forall$ et $\exists$ , le signe d’égalité, les parenthèses et la virgule. Ensuite une signature propre au langage considéré : des symboles de constante, des symboles de fonction et des symboles de relation, chacun affecté d’une arité.

Sur cet alphabet, deux règles de formation engendrent tout le reste. Les termes d’abord : une variable est un terme, une constante est un terme, et si $f$ est un symbole de fonction d’arité $n$ et si $t_{1},\ldots,t_{n}$ sont des termes, alors $f(t_{1},\ldots,t_{n})$ est un terme. Les formules ensuite : si $R$ est un symbole de relation d’arité $n$ , alors $R(t_{1},\ldots,t_{n})$ est une formule, dite atomique, de même que $t_{1}=t_{2}$ ; et si $\varphi$ et $\psi$ sont des formules, alors $\neg\varphi$ , $(\varphi\wedge\psi)$ , $\forall x\,\varphi$ et $\exists x\,\varphi$ en sont aussi.

Ce qu’il faut retenir de ces règles n’est pas leur contenu, qui est terne, mais leur nature : elles sont purement mécaniques. Décider si $\forall x\,\exists y\;(x<y)$ est bien formée, et si $\forall<x)y\exists$ ne l'est pas, ne demande de comprendre absolument rien. Une machine le fait. C'est là toute la syntaxe : un jeu de construction dont les pièces n'ont pas de sens.

3. La sémantique : il faut un monde

Pour qu’une formule signifie quelque chose, il faut lui fournir un monde où l’interpréter. Un tel monde s’appelle une structure.

Définition. Une structure $\mathcal{M}$ pour un langage $\mathcal{L}$ est la donnée d’un ensemble non vide $M$ , appelé domaine, et d’une interprétation de chaque symbole de $\mathcal{L}$ : à chaque symbole de constante un élément de $M$ , à chaque symbole de fonction d’arité $n$ une application de $M^{n}$ dans $M$ , à chaque symbole de relation d’arité $n$ une partie de $M^{n}$ .

Une fois la structure fixée, on définit par récurrence sur la construction des formules ce que signifie « $\varphi$ est satisfaite dans $\mathcal{M}$ », ce qu’on note $\mathcal{M}\models\varphi$ . C’est la définition de Tarski. Notons le point essentiel : le symbole $\models$ ne relie pas une formule à la vérité, mais une formule à une structure. La vérité toute seule, sans monde où la mesurer, n’est pas une notion mathématique.

4. Une même formule, deux verdicts

Reprenons $\varphi\;:\;\forall x\,\exists y\;(x<y)$ , dans le langage à un seul symbole de relation binaire.

Dans la structure $(\mathbb{N},<)$ , la formule est satisfaite : pour tout $x$ , l'entier $y=x+1$ convient.
Dans la structure $(\{0,1,2\},<)$ , elle ne l'est pas : aucun élément ne dépasse 2.

La chaîne de symboles est rigoureusement la même ; les verdicts sont opposés. Un second exemple, plus parlant peut-être : dans le langage des anneaux, la formule $\forall x\,\forall y\;(x\cdot y=y\cdot x)$ est satisfaite dans $\mathbb{R}$ et ne l’est pas dans l’anneau des matrices carrées d’ordre 2. Rien dans l’écriture ne permet de trancher — il faut sortir de l’écriture.

5. Variables libres : pourquoi « x² = 4 » n’est ni vrai ni faux

Dans $\exists y\;(x<y)$ , la variable $y$ est liée par le quantificateur, tandis que $x$ reste libre. Une formule sans variable libre s’appelle un énoncé clos ; seuls les énoncés clos reçoivent une valeur de vérité dans une structure. Une formule à variables libres, elle, ne définit pas une proposition mais une partie du domaine : celle des éléments qui la satisfont.

Cela éclaire une habitude scolaire tenace. L’écriture $x^{2}=4$ n’est ni vraie ni fausse : la variable $x$ y est libre. Dans la structure $\mathbb{R}$ , cette formule définit la partie $\{-2\,;\,2\}$ ; dans $\mathbb{N}$ , elle définit $\{2\}$ ; dans $\mathbb{Z}/3\mathbb{Z}$ , où 4 et 1 désignent le même élément, elle définit $\{1\,;\,2\}$ , puisque $1^{2}=1$ et $2^{2}=4=1$ . Une seule et même suite de symboles, trois ensembles différents.

Résoudre une équation, c’est donc exactement ceci : déterminer, dans une structure fixée, l’ensemble des valeurs de la variable libre qui satisfont une formule. Une opération sémantique menée sur un objet syntaxique. Que l’on omette de préciser la structure, et l’énoncé « résoudre $x^{2}=4$ » devient littéralement incomplet.

6. Démontrer n’est pas être vrai

Nous pouvons maintenant nommer proprement deux relations que l’enseignement confond régulièrement.

$T\vdash\varphi$ — syntaxique. Il existe une démonstration de $\varphi$ à partir de $T$ , c’est-à-dire une suite finie de formules dont chacune est un axiome ou se déduit des précédentes par une règle. Vérifier une telle suite est une opération mécanique.
$T\models\varphi$ — sémantique. Toute structure qui satisfait $T$ satisfait $\varphi$ . Il s’agit d’une quantification sur tous les mondes possibles, dont il n’y a aucune raison a priori qu’elle soit vérifiable.

Ces deux notions sont de nature entièrement différente : l’une parle de suites de signes, l’autre de mondes. Qu’elles coïncident est un théorème, et un théorème difficile.

Théorème de complétude (Gödel, 1930). Pour la logique du premier ordre, $T\vdash\varphi$ si, et seulement si, $T\models\varphi$ .

Une précaution s’impose ici, car la confusion est fréquente : il s’agit du théorème de complétude, et non des théorèmes d’incomplétude publiés l’année suivante. Les deux ne se contredisent nullement. L’énoncé de Gödel construit en 1931 pour une théorie arithmétique $T$ convenable est vrai dans $\mathbb{N}$ mais faux dans certains autres modèles de $T$ ; on n’a donc pas $T\models\varphi$ , et la complétude n’exige alors aucune démonstration. Être vrai dans le modèle standard et être vrai dans tous les modèles sont deux choses distinctes — distinction qui, une fois de plus, n’est lisible que si l’on a séparé la syntaxe de la sémantique.

Ces notions sont exposées en détail au chapitre 2 de Discours formel sur les mathématiques pour le secondaire, Volume I, qui les met ensuite à l’œuvre sur l’axiomatisation de la géométrie du plan.

Publicités

Formalis Mathematica

Rigueur et formalisme au cœur de l’apprentissage et de l’enseignement des mathématiques

Syntaxe et sémantique : ce qu’une formule dit, et ce qu’elle veut dire

1. Une confusion ordinaire

2. La syntaxe : un jeu de construction

3. La sémantique : il faut un monde

4. Une même formule, deux verdicts

5. Variables libres : pourquoi « x² = 4 » n’est ni vrai ni faux

6. Démontrer n’est pas être vrai

Laisser un commentaire Annuler la réponse.

1. Une confusion ordinaire

2. La syntaxe : un jeu de construction

3. La sémantique : il faut un monde

4. Une même formule, deux verdicts

5. Variables libres : pourquoi « x² = 4 » n’est ni vrai ni faux

6. Démontrer n’est pas être vrai

Partagez :

Similaire

Laisser un commentaire Annuler la réponse.