Definability

Definition

A set or relation is definable in a formal language $\mathcal{L}$ over a first-order structure $\mathcal{M}$ if there is a formula of $\mathcal{L}$ that holds exactly of the elements in question when interpreted in $\mathcal{M}$.

For a subset $A\subseteq M^k$, this means that there is a formula $\phi (x_1,\dots ,x_k)$ such that

$A=\{\bar{a}\in M^k\mid \mathcal{M}\models \phi (\bar{a})\}.$

In this situation, one says that $A$ is defined by $\phi$ in $\mathcal{M}$. Here $M$ denotes the underlying set of the structure $\mathcal{M}$.

Example

Let $A\subseteq \mathbb{N}$. Then $A$ is definable in the standard model of Peano arithmetic if there is a formula $\phi (n)$ such that

$n\in A⟺\mathbb{N}\models \phi (n).$

Thus definability means that membership in $A$ can be characterised by a logical formula.

Dependence on context

Definability is always relative to both a language and a first-order structure.

• Enlarging the language can make more sets definable.
• Changing the structure can change which formulas hold.
• Restrictions on the form of the formula lead to finer notions such as ${\Sigma }_1$-definability or first-order definability.

For this reason, phrases such as “definable in Peano arithmetic”, “arithmetically definable”, and “definable in the standard model of arithmetic” are related but not interchangeable.

Related Concepts

• Formal Language
• First-Order Structure
• Model Theory
• Peano Arithmetic
• standard model