In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements satisfy some formula in the first-order language of that structure.
A set can be defined with or without parameters, which are elements of the domain that can be referenced in the formula defining the relation.
be the structure consisting of the natural numbers with the usual ordering[clarification needed].
stating that there exist no elements less than x: and a natural number
elements less than x: In contrast, one cannot define any specific integer without parameters in the structure
consisting of the integers with the usual ordering (see the section on automorphisms below).
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, and are classified in the arithmetical hierarchy.
If the structure is considered in second-order logic instead of first-order logic, the definable sets of natural numbers in the resulting structure are classified in the analytical hierarchy.
These hierarchies reveal many relationships between definability in this structure and computability theory, and are also of interest in descriptive set theory.
be the structure consisting of the field of real numbers[clarification needed].
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: Thus any
In conjunction with a formula that defines the additive inverse of a real number in
is called a definitional extension 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.
Thus the definable sets are Boolean combinations of solutions to polynomial equalities and inequalities; these are called semi-algebraic sets.
Generalizing this property of the real line leads to the study of o-minimality.
An important result about definable sets is that they are preserved under automorphisms.
This result can sometimes be used to classify the definable subsets of a given structure.
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
In contrast, there are infinitely many definable sets of pairs (or indeed n-tuples for any fixed n > 1) of elements of
: (in the case n = 2) Boolean combinations of the sets
In particular, any automorphism (translation) preserves the "distance" between two elements.
The Tarski–Vaught test is used to characterize the elementary substructures of a given structure.