Ensemble définissable

Ensemble définissable


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

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

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

  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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Ensemble définissable de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Nombre Définissable — Un nombre définissable, nommé aussi parfois nombre accessible[1], ou nombre nommable[2], correspond à la notion intuitive décrite par Emile Borel [3] de « nombre pouvant être décrit comme un objet mathématique, de sorte que ceux qui en… …   Wikipédia en Français

  • Nombre definissable — Nombre définissable Un nombre définissable, nommé aussi parfois nombre accessible[1], ou nombre nommable[2], correspond à la notion intuitive décrite par Emile Borel [3] de « nombre pouvant être décrit comme un objet mathématique, de sorte… …   Wikipédia en Français

  • Nombre définissable — Un nombre définissable, nommé aussi parfois nombre accessible[1], ou nombre nommable[2], correspond à la notion intuitive décrite par Emile Borel [3] de « nombre pouvant être décrit comme un objet mathématique, de sorte que ceux qui en… …   Wikipédia en Français

  • Indéterminabilité — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Theoreme d'incompletude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude — de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les… …   Wikipédia en Français

  • Théorème d'incomplétude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude de Gödel — Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les propositions …   Wikipédia en Français

  • Théorème d'incomplétude de gödel — Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les propositions …   Wikipédia en Français

  • Théorème d'indécidabilité — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”