Méthode d'automorphisme

En théorie des modèles, la méthode d'automorphisme est une méthode permettant de démontrer la non-définissabilité d'un ensemble dans une structure.

Présentation

On rappelle que pour tous homomorphisme $h:|{\mathfrak {A}}|\to |{\mathfrak {B}}|$ , individus $a_{1},\ldots ,a_{n}\in |{\mathfrak {A}}|$ , et ${\mathcal {L}}$ -formule $\phi$ , on a $\models _{\mathfrak {A}}\phi [a_{1},\ldots ,a_{n}]$ si et seulement si $\models _{\mathfrak {B}}\phi [h(a_{1}),\ldots ,h(a_{n})]$ . Cela implique en particulier que si un ensemble est définissable dans une structure, alors il contient nécessairement son image par tous les automorphismes de cette structure.

La méthode d'automorphisme consiste alors à appliquer la contraposée de cette affirmation : si, pour une structure ${\mathfrak {A}}$ et un ensemble $E\subseteq |{\mathfrak {A}}|^{n}$ , il existe un automorphisme qui associe à un élément de $E$ un élément n'appartenant pas à $E$ , alors $E$ n'est pas définissable dans ${\mathfrak {A}}$ .

Exemple

On souhaite démontrer que la relation d'addition $R=\{(x,y,z)\in \mathbb {R} ^{3}\mid x+y=z\}$ n'est pas définissable dans la structure $\langle \mathbb {R} ,\times \rangle$ des réels munis uniquement de la multiplication. Pour cela nous allons utiliser la méthode d'automorphisme avec $h:\mathbb {R} \to \mathbb {R}$ définie comme la fonction cube $h(x)=x^{3}$ .

On commence par s'assurer que $h$ est bien un automorphisme :

$h(x\times y)=(x\times y)^{3}=x^{3}\times y^{3}=h(x)\times h(y)$

$h$ est donc un homomorphisme. De plus, $h$ est bijective car elle possède une application inverse définie par $h^{-1}(x)={\sqrt[{3}]{x}}$ .

Il suffit ensuite de prendre $x=y=2$ et $z=4$ : en effet, $2+2=4$ , mais $h(2)+h(2)=2^{3}+2^{3}=16\not =64=4^{3}=h(4)$ . On a donc trouvé des éléments $x,y,z\in \mathbb {R}$ tels que $(x,y,z)\in R$ , mais $(h(x),h(y),h(z))\not \in R$ .

On conclut que la relation d'addition n'est pas définissable dans $\langle \mathbb {R} ,\times \rangle$ .

Applications

Pouvoir expressif des théories

La non-définissabilité est une propriété particulièrement utile pour étudier le pouvoir expressif des langages non-logiques associés aux structures, et par extension des théories formulées dans ces langages. Un résultat typique utilisant la méthode d'automorphisme est l'impossibilité de définir l'addition uniquement à partir de la multiplication dans $\mathbb {N}$ , et réciproquement de définir la multiplication uniquement à partir de l'addition.

Ce résultat est à rapprocher d'une part de la complétude de l'arithmétique de Presburger, et d'autre part des théorèmes d'incomplétude de Gödel. Ces derniers énoncent en effet que l'arithmétique de Peano est incomplète, avec à cela plusieurs conséquences que l'on peut considérer problématiques telles que l'existence d'énoncés indécidables, ou encore l'impossibilité pour la théorie de prouver sa propre cohérence. On aimerait donc pouvoir la réduire à une théorie arithmétique complète telle que l'arithmétique de Presburger, ce qui implique qu'on doit conserver le même pouvoir expressif (modulo traduction si les langages des deux théories diffèrent). Or on a montré que la multiplication n'était pas réductible à l'addition dans $\mathbb {N}$ . Puisque l'arithmétique de Presburger est précisément l'arithmétique de Peano privée de la multiplication, on conclut que la réduction en question est impossible.

Bibliographie

David Marker, Model Theory: An Introduction, Springer, 2002.
Notes du cours « Théorie des modèles » délivré par A. Arana dans le cadre du Master 1 LOPHISC 2017/2018 Université Paris I Panthéon-Sorbonne.

Voir aussi

Articles connexes

Portail des mathématiques