# Definable set

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Definable_set
> Markdown URL: https://mediated.wiki/source/Definable_set.md
> Source: https://en.wikipedia.org/wiki/Definable_set
> Source revision: 1346290511
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Term in mathematical logic

In [mathematical logic](/source/Mathematical_logic), a **definable set** is an *n*-ary [relation](/source/Relation_(mathematics)) on the [domain](/source/Structure_(mathematical_logic)#Domain) of a [structure](/source/Structure_(mathematical_logic)) whose elements satisfy some [formula](/source/Formula_(mathematical_logic)) in the [first-order language](/source/First-order_language) of that structure. A [set](/source/Set_(mathematics)) can be defined with or without **parameters**, which are elements of the domain that can be referenced in the formula defining the relation.

## Definition

Let L {\displaystyle {\mathcal {L}}} be a first-order language, M {\displaystyle {\mathcal {M}}} an L {\displaystyle {\mathcal {L}}} -structure with domain M {\displaystyle M} , X {\displaystyle X} a fixed [subset](/source/Subset) of M {\displaystyle M} , and m {\displaystyle m} a [natural number](/source/Natural_number). Then:

- A set A ⊆ M m {\displaystyle A\subseteq M^{m}} is *definable in M {\displaystyle {\mathcal {M}}} with parameters from X {\displaystyle X}* if and only if there exists a formula φ [ x 1 , … , x m , y 1 , … , y n ] {\displaystyle \varphi [x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}]} and elements b 1 , … , b n ∈ X {\displaystyle b_{1},\ldots ,b_{n}\in X} such that for all a 1 , … , a m ∈ M {\displaystyle a_{1},\ldots ,a_{m}\in M} ,

- ( a 1 , … , a m ) ∈ A {\displaystyle (a_{1},\ldots ,a_{m})\in A} if and only if M ⊨ φ [ a 1 , … , a m , b 1 , … , b n ] . {\displaystyle {\mathcal {M}}\models \varphi [a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n}].}

- The bracket notation here indicates the semantic evaluation of the [free variables](/source/Free_variable) in the formula.

- A set *A {\displaystyle A} is definable in M {\displaystyle {\mathcal {M}}} without parameters* if it is definable in M {\displaystyle {\mathcal {M}}} with parameters from the [empty set](/source/Empty_set) (that is, with no parameters in the defining formula).

- A function is definable in M {\displaystyle {\mathcal {M}}} (with parameters) if its graph is definable (with those parameters) in M {\displaystyle {\mathcal {M}}} .

- An element a {\displaystyle a} is definable in M {\displaystyle {\mathcal {M}}} (with parameters) if the [singleton set](/source/Singleton_(mathematics)) { a } {\displaystyle \{a\}} is definable in M {\displaystyle {\mathcal {M}}} (with those parameters).

## Examples

### The natural numbers with only the order relation

Let N = ( N , < ) {\displaystyle {\mathcal {N}}=(\mathbb {N} ,<)} be the structure consisting of the natural numbers with the usual ordering. Then every natural number is definable in N {\displaystyle {\mathcal {N}}} without parameters. The number 0 {\displaystyle 0} is defined by the formula φ ( x ) {\displaystyle \varphi (x)} stating that there exist no elements less than *x*:

- φ = ¬ ∃ y ( y < x ) , {\displaystyle \varphi =\neg \exists y(y<x),}

and a natural number n > 0 {\displaystyle n>0} is defined by the formula φ ( x ) {\displaystyle \varphi (x)} stating that there exist exactly n {\displaystyle n} elements less than *x*:

- φ = ∃ x 0 ⋯ ∃ x n − 1 ( x 0 < x 1 ∧ ⋯ ∧ x n − 1 < x ∧ ∀ y ( y < x → ( y ≡ x 0 ∨ ⋯ ∨ y ≡ x n − 1 ) ) ) {\displaystyle \varphi =\exists x_{0}\cdots \exists x_{n-1}(x_{0}<x_{1}\land \cdots \land x_{n-1}<x\land \forall y(y<x\rightarrow (y\equiv x_{0}\lor \cdots \lor y\equiv x_{n-1})))}

In contrast, one cannot define any specific [integer](/source/Integer) without parameters in the structure Z = ( Z , < ) {\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)} consisting of the integers with the usual ordering (see the section on [automorphisms](/source/Automorphism) below).

### The natural numbers with their arithmetical operations

Let N = ( N , + , ⋅ , < ) {\displaystyle {\mathcal {N}}=(\mathbb {N} ,+,\cdot ,<)} be the first-order structure consisting of the natural numbers and their usual arithmetic operations and order relation. The sets definable in this structure are known as the [arithmetical sets](/source/Arithmetical_set), and are classified in the [arithmetical hierarchy](/source/Arithmetical_hierarchy). If the structure is considered in [second-order logic](/source/Second-order_logic) instead of first-order logic, the definable sets of natural numbers in the resulting structure are classified in the [analytical hierarchy](/source/Analytical_hierarchy). These hierarchies reveal many relationships between definability in this structure and [computability theory](/source/Computability_theory), and are also of interest in [descriptive set theory](/source/Descriptive_set_theory).

### The field of real numbers

Let R = ( R , 0 , 1 , + , ⋅ ) {\displaystyle {\mathcal {R}}=(\mathbb {R} ,0,1,+,\cdot )} be the structure consisting of the [field](/source/Field_(mathematics)) of [real numbers](/source/Real_number)[*[clarification needed](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*]. Although the usual ordering relation is not directly included in the structure, there is a formula that defines the set of nonnegative reals, since these are the only reals that possess square roots:

- φ = ∃ y ( y ⋅ y ≡ x ) . {\displaystyle \varphi =\exists y(y\cdot y\equiv x).}

Thus any a ∈ R {\displaystyle a\in \mathbb {R} } is nonnegative if and only if R ⊨ φ [ a ] {\displaystyle {\mathcal {R}}\models \varphi [a]} . In conjunction with a formula that defines the additive inverse of a real number in R {\displaystyle {\mathcal {R}}} , one can use φ {\displaystyle \varphi } to define the usual ordering in R {\displaystyle {\mathcal {R}}} : for a , b ∈ R {\displaystyle a,b\in \mathbb {R} } , set a ≤ b {\displaystyle a\leq b} if and only if b − a {\displaystyle b-a} is nonnegative. The enlarged structure R ≤ = ( R , 0 , 1 , + , ⋅ , ≤ ) {\displaystyle {\mathcal {R}}^{\leq }=(\mathbb {R} ,0,1,+,\cdot ,\leq )} is called a [definitional extension](/source/Extension_by_definitions) of the original structure. It has the same expressive power as the original structure, in the sense that a set is definable over the enlarged structure from a set of parameters if and only if it is definable over the original structure from that same set of parameters.

The [theory](/source/Theory_(mathematical_logic)) of R ≤ {\displaystyle {\mathcal {R}}^{\leq }} has [quantifier elimination](/source/Quantifier_elimination). Thus the definable sets are [Boolean combinations](/source/Field_of_sets) of solutions to polynomial equalities and inequalities; these are called [semi-algebraic sets](/source/Semi-algebraic_sets). Generalizing this property of the real line leads to the study of [o-minimality](/source/O-minimality).

## Invariance under automorphisms

An important result about definable sets is that they are preserved under [automorphisms](/source/Automorphism) which fix their parameter set.

- Let M {\displaystyle {\mathcal {M}}} be an L {\displaystyle {\mathcal {L}}} -structure with domain M {\displaystyle M} , X ⊆ M {\displaystyle X\subseteq M} , and A ⊆ M m {\displaystyle A\subseteq M^{m}} definable in M {\displaystyle {\mathcal {M}}} with parameters from X {\displaystyle X} . Let π : M → M {\displaystyle \pi :M\to M} be an automorphism of M {\displaystyle {\mathcal {M}}} that is the identity on X {\displaystyle X} . Then for all a 1 , … , a m ∈ M {\displaystyle a_{1},\ldots ,a_{m}\in M} ,

- - ( a 1 , … , a m ) ∈ A {\displaystyle (a_{1},\ldots ,a_{m})\in A} if and only if ( π ( a 1 ) , … , π ( a m ) ) ∈ A . {\displaystyle (\pi (a_{1}),\ldots ,\pi (a_{m}))\in A.}

This result can sometimes be used to classify the definable subsets of a given structure. For example, in the case of Z = ( Z , < ) {\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)} above, any translation of Z {\displaystyle {\mathcal {Z}}} is an automorphism preserving the empty set of parameters, and thus it is impossible to define any particular integer in this structure without parameters in Z {\displaystyle {\mathcal {Z}}} . In fact, since any two integers are carried to each other by a translation and its inverse, the only sets of integers definable in Z {\displaystyle {\mathcal {Z}}} without parameters are the empty set and Z {\displaystyle \mathbb {Z} } itself. In contrast, there are infinitely many definable sets of pairs (or indeed *n*-tuples for any fixed *n* > 1) of elements of Z {\displaystyle {\mathcal {Z}}} : (in the case *n* = 2) Boolean combinations of the sets { ( a , b ) ∣ a − b = m } {\displaystyle \{(a,b)\mid a-b=m\}} for m ∈ Z {\displaystyle m\in \mathbb {Z} } . In particular, any automorphism (translation) preserves the "distance" between two elements.

## Additional results

The [Tarski–Vaught test](/source/Tarski%E2%80%93Vaught_test) is used to characterize the [elementary substructures](/source/Elementary_substructure) of a given structure.

## References

- Hinman, Peter. *Fundamentals of Mathematical Logic*, A K Peters, 2005.

- Marker, David. *Model Theory: An Introduction*, Springer, 2002.

- [Rudin, Walter](/source/Walter_Rudin). *Principles of Mathematical Analysis*, 3rd. ed. McGraw-Hill, 1976.

- [Slaman, Theodore A.](/source/Theodore_Slaman) and [Woodin, W. Hugh](/source/W._Hugh_Woodin). *Mathematical Logic: The Berkeley Undergraduate Course*. Spring 2006.

Authority control databases National United States Israel Other Yale LUX

---
Adapted from the Wikipedia article [Definable set](https://en.wikipedia.org/wiki/Definable_set) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Definable_set?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.