Ensemble définissable

Soient ${\displaystyle {\mathcal {L}}}$ un langage du premier ordre, ${\displaystyle {\mathcal {M}}}$ une ${\displaystyle {\mathcal {L}}}$-structure de domaine ${\displaystyle M}$, ${\displaystyle X}$ un sous-ensemble de ${\displaystyle M}$, et m un entier naturel. Alors :

• Un sous-ensemble ${\displaystyle E}$ de ${\displaystyle M^{m}}$ est définissable dans ${\displaystyle {\mathcal {M}}}$ avec paramètres dans ${\displaystyle X}$ s'il existe une formule ${\displaystyle \varphi [x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}]}$ du langage ${\displaystyle {\mathcal {L}}}$, et des éléments ${\displaystyle b_{1},\ldots ,b_{n}\in X}$ tels que pour tous ${\displaystyle a_{1},\ldots ,a_{m}\in M}$,

${\displaystyle (a_{1},\ldots ,a_{m})\in E}$ si et seulement si ${\displaystyle {\mathcal {M}}\models \varphi [a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n}]}$

si l'ensemble X est M lui-même, on dit simplement que E est définissable (éventuellement définissable avec paramètres) dans ℳ ;

si l'ensemble X est vide, c'est-à-dire qu'aucun paramètre n'apparaît dans la formule φ, on dit que E est définissable dans ℳ sans paramètres.

• Une fonction est définissable dans ${\displaystyle {\mathcal {M}}}$ (avec paramètres) si son graphe est définissable dans ${\displaystyle {\mathcal {M}}}$ (avec ces paramètres).
• Un élément a de ${\displaystyle M}$ est définissable (avec paramètres) dans ${\displaystyle {\mathcal {M}}}$ si le singleton {a} est définissable dans ${\displaystyle {\mathcal {M}}}$ (avec ces paramètres).

La définissabilité dans une structure dépend bien-sûr fortement du langage ℒ (celui de la structure) utilisé pour la définition, et on dit aussi que l'ensemble E est ℒ-définissable dans ℳ, ou encore que E est un sous-ensemble ℒ-définissable (définissable dans le langage ℒ) de M^m.

• Elisabeth Bouscaren, Cours du magistère Math-Info (Ulm) 2003-2004
• David Marker, Model Theory: An Introduction, Springer, 2002.