Ensemble définissable

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


En mathématiques, un ensemble définissable est une relation m-aire sur le domaine d'une structure dont les éléments sont précisément ceux qui satisfont une formule donnée dans le langage de la structure. Un ensemble E peut être défini avec ou sans paramètres, lesquels sont des éléments du domaine, qui peuvent être référencés dans la 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 \subset  M, et m un nombre entier naturel. Alors :

  • Un ensemble E\subseteq M^m est définissable en \mathcal{M} avec paramètres dans X si et seulement s'il existe une formule \varphi[x_1,\ldots,x_m,y_1,\ldots,y_n] et 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 \leftrightarrow  \mathcal{M}\models\varphi[a_1,\ldots,a_m,b_1,\ldots,b_n]
  • Un ensemble E est définissable en \mathcal{M} sans paramètres s'il est définissable dans \mathcal{M} avec X=Ø, aucun paramètre n'apparaît dans la formule définissante.
  • Une fonction est définissable dans \mathcal{M} (avec paramètres) si son graphe est définissable (avec ces paramètres).
  • Un élément a de M est définissable (avec paramètres) si son singleton {a} est définissable (avec ces paramètres).

Théorème de Beth[modifier | modifier le code]

On définit, pour une propriété, les notions d'être implicitement ou explicitement définissable dans une théorie. Le théorème de définissabilité de Beth établit que ces deux notions sont équivalentes[1].

Notes et références[modifier | modifier le code]

  1. René Cori et Daniel Lascar, Logique mathématique II. Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles [détail des éditions], p. 210