Ensemble définissable

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher


En mathématiques, un ensemble définissable dans une structure donnée d'ensemble de base M est un sous-ensemble de Mm (m entier naturel) pour lequel on peut trouver une formule du langage de la structure, avec éventuellement pour paramètres des éléments de M, de façon que les éléments sont exactement ceux qui satisfont cette formule.

Définition[modifier | modifier le code]

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

  • Un sous-ensemble E de M^m est définissable dans \mathcal{M} avec paramètres dans X s'il existe une formule \varphi[x_1,\ldots,x_m,y_1,\ldots,y_n] du langage \mathcal L, et des éléments b_1,\ldots,b_n\in X tels que pour tous a_1,\ldots,a_m\in M,
(a_1,\ldots,a_m)\in E si et seulement si \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 \mathcal{M} (avec paramètres) si son graphe est définissable dans \mathcal{M} (avec ces paramètres).
  • Un élément a de M est définissable (avec paramètres) dans \mathcal{M} si le singleton {a} est définissable dans \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 Mm.

Bibliographie[modifier | modifier le code]