Ensemble définissable - Definable set

En logique mathématique , un ensemble définissable est une relation n -ary sur le domaine d'une structure dont les éléments sont précisément ces éléments satisfaisant une formule dans le langage du premier ordre de cette structure. Un ensemble peut être défini avec ou sans paramètres , qui sont des éléments du domaine pouvant être référencés dans la formule définissant la relation.

Définition

Soit un langage de premier ordre, une structure avec domaine , un sous - ensemble fixe de et un nombre naturel . Puis:

  • Un ensemble est définissable avec des paramètres à partir de si et seulement s'il existe une formule et des éléments tels que pour tous ,
si et seulement si
La notation entre crochets indique ici l'évaluation sémantique des variables libres dans la formule.
  • Un ensemble est définissable dans sans paramètres s'il est définissable avec des paramètres de l' ensemble vide (c'est-à-dire sans paramètres dans la formule de définition).
  • Une fonction est définissable dans (avec des paramètres) si son graphe est définissable (avec ces paramètres) dans .
  • Un élément est définissable dans (avec des paramètres) si l' ensemble de singleton est définissable dans (avec ces paramètres).

Exemples

Les nombres naturels avec uniquement la relation d'ordre

Soit la structure composée des nombres naturels avec l'ordre habituel. Ensuite, chaque nombre naturel est définissable sans paramètres. Le nombre est défini par la formule indiquant qu'il n'existe pas d'éléments inférieurs à x : et un entier naturel est défini par la formule indiquant qu'il existe exactement des éléments inférieurs à x :

En revanche, on ne peut définir aucun entier spécifique sans paramètres dans la structure constituée des entiers avec l'ordre habituel (voir la section sur les automorphismes ci-dessous).

Les nombres naturels avec leurs opérations arithmétiques

Soit la structure du premier ordre constituée des nombres naturels et de leurs opérations arithmétiques habituelles et de leur relation d'ordre. Les ensembles définissables dans cette structure sont connus sous le nom d' ensembles arithmétiques et sont classés dans la hiérarchie arithmétique . Si la structure est considérée dans la logique du second ordre au lieu de la logique du premier ordre, les ensembles définissables de nombres naturels dans la structure résultante sont classés dans la hiérarchie analytique . Ces hiérarchies révèlent de nombreuses relations entre la définissabilité dans cette structure et la théorie de la calculabilité , et sont également intéressantes pour la théorie descriptive des ensembles .

Le domaine des nombres réels

Soit la structure constituée du champ des nombres réels . Bien que la relation d'ordre habituelle ne soit pas directement incluse dans la structure, il existe une formule qui définit l'ensemble des réels non négatifs, puisque ce sont les seuls réels qui possèdent des racines carrées:

Ainsi any est non négatif si et seulement si . En conjonction avec une formule qui définit l'inverse additif d'un nombre réel dans , on peut utiliser pour définir l'ordre habituel dans : pour , définir si et seulement si est non négatif. La structure agrandie s est appelée une extension définitionnelle de la structure originale. Il a le même pouvoir expressif que la structure d'origine, en ce sens qu'un ensemble est définissable sur la structure agrandie à partir d'un ensemble de paramètres si et seulement s'il est définissable sur la structure d'origine à partir de ce même ensemble de paramètres.

La théorie de a quantificateurs élimination . Ainsi, les ensembles définissables sont des combinaisons booléennes de solutions aux égalités et inégalités polynomiales; ceux-ci sont appelés ensembles semi-algébriques . La généralisation de cette propriété de la ligne réelle conduit à l'étude de l' o-minimalité .

Invariance sous automorphismes

Un résultat important concernant les ensembles définissables est qu'ils sont conservés sous automorphismes .

Laissez - être un -structure avec le domaine , et définissable avec des paramètres de . Soit un automorphisme dont l'identité est sur . Alors pour tous ,
si et seulement si

Ce résultat peut parfois être utilisé pour classer les sous-ensembles définissables d'une structure donnée. Par exemple, dans le cas ci-dessus, toute traduction de est un automorphisme préservant l'ensemble vide de paramètres, et il est donc impossible de définir un entier particulier dans cette structure sans paramètres dans . En fait, puisque deux entiers quelconques sont portés l'un à l'autre par une translation et son inverse, les seuls ensembles d'entiers définissables dans sans paramètres sont l'ensemble vide et lui - même. En revanche, il existe une infinité d'ensembles définissables de paires (ou en fait n -tuples pour tout n > 1 fixe ) d'éléments de , puisque tout automorphisme (translation) préserve la "distance" entre deux éléments.

Résultats supplémentaires

Le test de Tarski – Vaught est utilisé pour caractériser les sous - structures élémentaires d'une structure donnée.

Les références

  • Hinman, Peter. Fondamentaux de la logique mathématique , AK Peters, 2005.
  • Marker, David. Théorie des modèles: une introduction , Springer, 2002.
  • Rudin, Walter. Principes d'analyse mathématique , 3e. ed. McGraw-Hill, 1976.
  • Slaman, Theodore A. et W. Hugh Woodin. Logique mathématique: le cours de premier cycle de Berkeley . Printemps 2006.