Inmathematical logic, adefinable set is ann-aryrelation on thedomain of astructure whose elements satisfy someformula in thefirst-order language of that structure. Aset can be defined with or withoutparameters, which are elements of the domain that can be referenced in the formula defining the relation.

Let${\displaystyle \mathcal{L}}$ be a first-order language,${\displaystyle \mathcal{M}}$ an${\displaystyle \mathcal{L}}$-structure with domain${\displaystyle M}$,${\displaystyle X}$ a fixedsubset of${\displaystyle M}$, and${\displaystyle m}$ anatural number. Then:

• A set${\displaystyle A\subseteq M^m}$ isdefinable in${\displaystyle \mathcal{M}}$ with parameters from${\displaystyle X}$ if and only if there exists a formula${\displaystyle \phi [x_1,\dots ,x_m,y_1,\dots ,y_n]}$ and elements${\displaystyle b_1,\dots ,b_n\in X}$ such that for all${\displaystyle a_1,\dots ,a_m\in M}$,

${\displaystyle (a_1,\dots ,a_m)\in A}$ if and only if${\displaystyle \mathcal{M}\models \phi [a_1,\dots ,a_m,b_1,\dots ,b_n].}$

The bracket notation here indicates the semantic evaluation of thefree variables in the formula.

• A set${\displaystyle A}$ is definable in${\displaystyle \mathcal{M}}$ without parameters if it is definable in${\displaystyle \mathcal{M}}$ with parameters from theempty set (that is, with no parameters in the defining formula).
• A function is definable in${\displaystyle \mathcal{M}}$ (with parameters) if its graph is definable (with those parameters) in${\displaystyle \mathcal{M}}$.
• An element${\displaystyle a}$ is definable in${\displaystyle \mathcal{M}}$ (with parameters) if thesingleton set${\displaystyle \{a\}}$ is definable in${\displaystyle \mathcal{M}}$ (with those parameters).

Let be the structure consisting of the natural numbers with the usual ordering. Then every natural number is definable in${\displaystyle \mathcal{N}}$ without parameters. The number${\displaystyle 0}$ is defined by the formula${\displaystyle \phi (x)}$ stating that there exist no elements less thanx:

and a natural number${\displaystyle n>0}$ is defined by the formula${\displaystyle \phi (x)}$ stating that there exist exactly${\displaystyle n}$ elements less thanx:

In contrast, one cannot define any specificinteger without parameters in the structure consisting of the integers with the usual ordering (see the section onautomorphisms below).

Let 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 thearithmetical sets, and are classified in thearithmetical hierarchy. If the structure is considered insecond-order logic instead of first-order logic, the definable sets of natural numbers in the resulting structure are classified in theanalytical hierarchy. These hierarchies reveal many relationships between definability in this structure andcomputability theory, and are also of interest indescriptive set theory.

Let${\displaystyle \mathcal{R}=(\mathbb{R},0,1,+,\cdot )}$ be the structure consisting of thefield ofreal 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:

${\displaystyle \phi =\mathrm{\exists }y(y\cdot y\equiv x).}$

Thus any${\displaystyle a\in \mathbb{R}}$ is nonnegative if and only if${\displaystyle \mathcal{R}\models \phi [a]}$. In conjunction with a formula that defines the additive inverse of a real number in${\displaystyle \mathcal{R}}$, one can use${\displaystyle \phi }$ to define the usual ordering in${\displaystyle \mathcal{R}}$: for${\displaystyle a,b\in \mathbb{R}}$, set${\displaystyle a\le b}$ if and only if${\displaystyle b-a}$ is nonnegative. The enlarged structure${\displaystyle {\mathcal{R}}^{\le }=(\mathbb{R},0,1,+,\cdot ,\le )}$ is called adefinitional 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.

Thetheory of${\displaystyle {\mathcal{R}}^{\le }}$ hasquantifier elimination. Thus the definable sets areBoolean combinations of solutions to polynomial equalities and inequalities; these are calledsemi-algebraic sets. Generalizing this property of the real line leads to the study ofo-minimality.

An important result about definable sets is that they are preserved underautomorphisms which fix their parameter set.

Let${\displaystyle \mathcal{M}}$ be an${\displaystyle \mathcal{L}}$-structure with domain${\displaystyle M}$,${\displaystyle X\subseteq M}$, and${\displaystyle A\subseteq M^m}$ definable in${\displaystyle \mathcal{M}}$ with parameters from${\displaystyle X}$. Let${\displaystyle \pi :M\to M}$ be an automorphism of${\displaystyle \mathcal{M}}$ that is the identity on${\displaystyle X}$. Then for all${\displaystyle a_1,\dots ,a_m\in M}$,

${\displaystyle (a_1,\dots ,a_m)\in A}$ if and only if${\displaystyle (\pi (a_1),\dots ,\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 above, any translation of${\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${\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${\displaystyle \mathcal{Z}}$ without parameters are the empty set and${\displaystyle \mathbb{Z}}$ itself. In contrast, there are infinitely many definable sets of pairs (or indeedn-tuples for any fixedn > 1) of elements of${\displaystyle \mathcal{Z}}$: (in the casen = 2) Boolean combinations of the sets${\displaystyle \{(a,b)\mid a-b=m\}}$ for${\displaystyle m\in \mathbb{Z}}$. In particular, any automorphism (translation) preserves the "distance" between two elements.

TheTarski–Vaught test is used to characterize theelementary substructures of a given structure.

• Hinman, Peter.Fundamentals of Mathematical Logic, A K Peters, 2005.
• Marker, David.Model Theory: An Introduction, Springer, 2002.
• Rudin, Walter.Principles of Mathematical Analysis, 3rd. ed. McGraw-Hill, 1976.
• Slaman, Theodore A. andWoodin, W. Hugh.Mathematical Logic: The Berkeley Undergraduate Course. Spring 2006.

• Model theory
• Logic
• Mathematical logic

• Wikipedia articles needing clarification from January 2023