6.1 Definable Sets and Functions

Definability is one of the central ideas of model theory. Once a first order language and a structure have been fixed, formulas can be used to describe subsets of the domain, relations on the domain, and functions between definable sets. In this way, syntax gives rise to geometry inside a structure: a formula becomes a description of a set of points satisfying a condition.

In this section, we work with a first order language $L$ and an $L$-structure $\mathcal M$. The domain of $\mathcal M$ will be denoted by $M$. Variables range over elements of $M$, and formulas are interpreted in $\mathcal M$ using the satisfaction relation developed earlier.

Definable Sets

Let $\varphi(x)$ be an $L$-formula with one free variable $x$. The formula $\varphi(x)$ defines a subset of $M$ by collecting exactly those elements of $M$ that satisfy the formula in $\mathcal M$.

Definition 6.1 (Definable Subset)

Let $\mathcal M$ be an $L$-structure with domain $M$. A subset $X \subseteq M$ is definable in $\mathcal M$ if there is an $L$-formula $\varphi(x)$ with one free variable such that:

In this case, we say that $\varphi(x)$ defines $X$ in $\mathcal M$.

The notation $\mathcal M \models \varphi(a)$ means that the formula $\varphi(x)$ is true in $\mathcal M$ when the variable $x$ is assigned the value $a$. More formally, if $s$ is an assignment with $s(x)=a$, then:

The set defined by $\varphi(x)$ is often denoted:

This notation emphasizes that the same formula may define different sets in different structures.

Example 6.2

Consider the structure:

The formula:

defines the set of even natural numbers.

Indeed:

The formula says that $x$ is the sum of some natural number with itself. Since $y+y=2y$, this is exactly the condition that $x$ is divisible by $2$.

Example 6.3

In the ordered field:

the formula:

defines the positive real numbers:

The formula:

defines the set of nonnegative real numbers:

This is because a real number is a square of another real number exactly when it is nonnegative.

Definable Relations

A formula may have more than one free variable. If $\varphi(x_1,\dots,x_n)$ is a formula with free variables among $x_1,\dots,x_n$, then it defines a subset of $M^n$.

Definition 6.4 (Definable Relation)

Let $\mathcal M$ be an $L$-structure with domain $M$. An $n$-ary relation $R \subseteq M^n$ is definable in $\mathcal M$ if there is an $L$-formula $\varphi(x_1,\dots,x_n)$ such that:

Thus definable subsets of $M$ are the special case $n=1$, and definable relations are the general case.

Example 6.5

In the structure:

the formula:

defines the relation:

Indeed, $x \leq y$ in $\mathbb N$ exactly when there exists $z \in \mathbb N$ such that $y=x+z$.

This example shows that a relation can be definable even if its symbol is not included as a primitive symbol of the language, provided that it can be expressed using the available symbols.

Definability With Parameters

Sometimes we want to define a set using particular elements of the structure as fixed constants. This leads to definability with parameters.

Definition 6.6 (Definability With Parameters)

Let $\mathcal M$ be an $L$-structure with domain $M$, and let $A \subseteq M$. A subset $X \subseteq M^n$ is definable over $A$, or $A$-definable, if there is an $L$-formula:

and parameters $a_1,\dots,a_m \in A$ such that:

If $A=\emptyset$, then $X$ is said to be definable without parameters.

A definable set without parameters is sometimes called $\emptyset$-definable.

Example 6.7

In the structure:

the interval:

is definable without parameters by:

The interval:

for arbitrary real numbers $a,b \in \mathbb R$ is definable with parameters $a$ and $b$ by:

Unless $a$ and $b$ are already named by terms of the language, the formula defining $(a,b)$ uses parameters.

Remark 6.8

There is a useful way to think about definability with parameters. If $A \subseteq M$, then one can expand the language $L$ by adding a new constant symbol $c_a$ for each $a \in A$, and interpret $c_a$ as $a$ in $\mathcal M$. In that expanded language, $A$-definable sets become definable without parameters.

This does not change the underlying structure $M$, but it changes the language available for describing subsets of $M$.

Boolean Closure of Definable Sets

Definable sets are closed under the usual Boolean operations. This follows from the fact that formulas are closed under logical connectives.

Lemma 6.9 (Closure Under Complement)

Let $X \subseteq M^n$ be definable in $\mathcal M$. Then $M^n \setminus X$ is definable in $\mathcal M$.

Proof

Since $X$ is definable, there is a formula $\varphi(x_1,\dots,x_n)$ such that:

Consider the formula:

For any tuple $a \in M^n$, we have:

if and only if:

This is true if and only if $a \notin X$. Hence:

Therefore $M^n \setminus X$ is definable.

Lemma 6.10 (Closure Under Intersection)

Let $X,Y \subseteq M^n$ be definable in $\mathcal M$. Then $X \cap Y$ is definable in $\mathcal M$.

Proof

Since $X$ and $Y$ are definable, there are formulas $\varphi(x_1,\dots,x_n)$ and $\psi(x_1,\dots,x_n)$ such that:

and:

Consider the formula:

For any $a \in M^n$, we have:

if and only if:

and:

This is equivalent to saying:

Thus:

Therefore $X \cap Y$ is definable.

Lemma 6.11 (Closure Under Union)

Let $X,Y \subseteq M^n$ be definable in $\mathcal M$. Then $X \cup Y$ is definable in $\mathcal M$.

Proof

Choose formulas $\varphi(x_1,\dots,x_n)$ and $\psi(x_1,\dots,x_n)$ defining $X$ and $Y$, respectively.

Consider:

For any $a \in M^n$, the formula is true exactly when $\varphi(a)$ is true or $\psi(a)$ is true. This is exactly the condition that $a \in X$ or $a \in Y$.

Therefore:

Hence $X \cup Y$ is definable.

Lemma 6.12 (Closure Under Difference)

Let $X,Y \subseteq M^n$ be definable in $\mathcal M$. Then $X \setminus Y$ is definable in $\mathcal M$.

Proof

Choose formulas $\varphi(x_1,\dots,x_n)$ and $\psi(x_1,\dots,x_n)$ defining $X$ and $Y$.

The difference $X \setminus Y$ consists of those tuples that belong to $X$ and do not belong to $Y$. Therefore it is defined by:

Indeed, for any $a \in M^n$:

if and only if:

Thus $X \setminus Y$ is definable.

Projection and Existential Quantification

Definable sets are also closed under projection. This is the semantic counterpart of existential quantification.

Definition 6.13 (Projection)

Let $X \subseteq M^{n+1}$. The projection of $X$ onto the first $n$ coordinates is:

Projection forgets one coordinate while remembering whether there exists a value of that coordinate making the tuple belong to $X$.

Lemma 6.14 (Closure Under Projection)

Let $X \subseteq M^{n+1}$ be definable in $\mathcal M$. Then its projection $\pi(X) \subseteq M^n$ is definable in $\mathcal M$.

Proof

Since $X$ is definable, there is a formula:

such that:

We claim that $\pi(X)$ is defined by:

Let $a=(a_1,\dots,a_n) \in M^n$. Then:

if and only if there exists $b \in M$ such that:

By the definition of $X$, this is equivalent to:

for some $b \in M$.

By the semantics of the existential quantifier, this is equivalent to:

Therefore:

Hence $\pi(X)$ is definable.

Universal Quantification

Universal quantification can also be understood in terms of definable sets. If a formula $\varphi(x,y)$ defines a subset of $M^{n+1}$, then the formula:

defines the set of $x$ such that every possible $y$ satisfies the relation.

This can be reduced to complement and projection, since:

is equivalent to:

Thus closure under universal quantification follows from closure under complement and projection.

Lemma 6.15 (Closure Under Universal Quantification)

Let $\varphi(x_1,\dots,x_n,y)$ be an $L$-formula. The set:

is definable in $\mathcal M$.

Proof

The set is defined directly by the formula:

Equivalently, using negation and existential quantification, the same set is defined by:

For any $a \in M^n$, this formula holds exactly when there is no $b \in M$ such that $\varphi(a,b)$ fails, which is exactly the condition that $\varphi(a,b)$ holds for all $b \in M$.

Definable Functions

A function is definable when its graph is definable. This is the standard model theoretic definition because first order formulas naturally define relations, and the graph of a function is a relation.

Definition 6.16 (Definable Function)

Let $X \subseteq M^n$ and $Y \subseteq M^m$. A function:

is definable in $\mathcal M$ if its graph:

is a definable subset of $M^{n+m}$.

Equivalently, there is a formula:

such that:

if and only if:

The formula defining the graph must determine a unique output for each input in $X$.

Example 6.17

In the structure:

the function:

is definable.

Its graph is:

This graph is defined by the formula:

Therefore $f$ is definable.

Example 6.18

In the ordered field:

the function:

is definable by the formula:

The function:

is also definable, because its graph is defined by:

Here $-x$ can be expressed as the unique element $z$ such that:

If the language includes subtraction or unary minus, the formula can be written more directly.

Lemma 6.19 (Composition of Definable Functions)

Let $f : X \to Y$ and $g : Y \to Z$ be definable functions in $\mathcal M$. Then:

is definable in $\mathcal M$.

Proof

Since $f$ is definable, its graph is defined by a formula:

Since $g$ is definable, its graph is defined by a formula:

The graph of $g \circ f$ consists of pairs $(x,z)$ such that there exists $y$ with:

and:

Therefore the graph of $g \circ f$ is defined by:

For any $x$ and $z$, this formula holds exactly when there is an intermediate value $y$ such that $(x,y)$ lies in the graph of $f$ and $(y,z)$ lies in the graph of $g$. Since $f$ and $g$ are functions, this means precisely that:

Hence $g \circ f$ is definable.

Lemma 6.20 (Preimage of a Definable Set)

Let $f : X \to Y$ be a definable function, and let $D \subseteq Y$ be definable. Then:

is definable.

Proof

Let $\varphi_f(x,y)$ define the graph of $f$, and let $\psi(y)$ define $D$.

The preimage $f^{-1}(D)$ consists of those $x \in X$ for which $f(x) \in D$. This is expressed by:

For any $x$, this formula holds if and only if there exists $y$ such that $y=f(x)$ and $y \in D$. Since $f$ is a function, this is equivalent to $f(x) \in D$.

Therefore the preimage is definable.

Lemma 6.21 (Image of a Definable Set)

Let $f : X \to Y$ be a definable function, and let $D \subseteq X$ be definable. Then:

is definable.

Proof

Let $\varphi_f(x,y)$ define the graph of $f$, and let $\psi(x)$ define $D$.

The image $f(D)$ consists of all $y \in Y$ such that $y=f(x)$ for some $x \in D$. This is expressed by:

For any $y$, this formula holds exactly when there exists $x$ satisfying $\psi(x)$ and lying in the graph relation with $y$. This is precisely the condition that $y$ belongs to the image of $D$ under $f$.

Therefore $f(D)$ is definable.

Definable Families

Definable families are collections of definable sets that vary with parameters. They are important because many constructions in model theory involve a single formula whose parameters define many different sets.

Definition 6.22 (Definable Family)

Let $\varphi(x,y)$ be a formula, where $x$ may stand for a tuple of object variables and $y$ may stand for a tuple of parameter variables.

For each parameter tuple $b \in M^{|y|}$, define:

The collection:

is called the definable family determined by $\varphi(x,y)$.

Example 6.23

In the ordered field of real numbers, the formula:

defines a family of open intervals:

as the parameters $a$ and $b$ vary over $\mathbb R$.

Thus one formula defines many subsets of $\mathbb R$, each obtained by choosing different parameter values.

Definability and Automorphisms

Definable sets without parameters are preserved by automorphisms. This gives a useful test for non-definability.

Definition 6.24 (Automorphism)

An automorphism of an $L$-structure $\mathcal M$ is a bijection:

that preserves the interpretations of all symbols of $L$.

This means that constants, functions, and relations are respected by $\sigma$.

For example, if $R$ is a binary relation symbol, then:

if and only if:

Lemma 6.25 (Parameter Free Definable Sets Are Automorphism Invariant)

Let $X \subseteq M^n$ be definable without parameters in $\mathcal M$. If $\sigma$ is an automorphism of $\mathcal M$, then:

if and only if:

Proof

Since $X$ is definable without parameters, there is a formula $\varphi(x_1,\dots,x_n)$ such that:

We prove by induction on formulas that automorphisms preserve truth of parameter free formulas. For atomic formulas, preservation follows from the definition of automorphism, since automorphisms preserve equality, relations, functions, and constants.

The Boolean connectives are preserved because truth of compound formulas is determined from truth of their immediate subformulas. For example, if truth of $\varphi(a)$ is preserved, then truth of $¬\varphi(a)$ is also preserved. Similarly, preservation for conjunction, disjunction, implication, and biconditional follows from the corresponding truth rules.

For quantifiers, suppose:

Then there is $b \in M$ such that:

By the induction hypothesis:

Hence:

The converse follows by applying the same argument to $\sigma^{-1}$, since an automorphism is a bijection whose inverse is also an automorphism.

Thus:

if and only if:

Therefore $X$ is invariant under $\sigma$.

Example 6.26

Consider the pure equality structure:

with no non-logical symbols besides equality, and suppose $M$ has at least two elements.

No singleton $\{a\}$ is definable without parameters.

Indeed, if $\{a\}$ were definable without parameters, it would be fixed by every automorphism of $\mathcal M$. But in the pure equality structure, every permutation of $M$ is an automorphism. If $b \neq a$, there is a permutation sending $a$ to $b$. Such a permutation does not preserve the set $\{a\}$. Hence $\{a\}$ is not definable without parameters.

However, $\{a\}$ is definable with parameter $a$ by the formula:

Definable Closure

Definable closure records which elements are uniquely determined by parameters.

Definition 6.27 (Definable Closure)

Let $\mathcal M$ be an $L$-structure and let $A \subseteq M$. An element $b \in M$ belongs to the definable closure of $A$, written:

if there is a formula $\varphi(x,\bar a)$ with parameters $\bar a$ from $A$ such that:

and:

Here $\exists! x$ means “there exists a unique $x$”.

Thus $b$ lies in $\operatorname{dcl}(A)$ if $b$ is uniquely definable using parameters from $A$.

Example 6.28

In the ordered field:

the element:

is definable without parameters because it is the unique element satisfying:

More generally, every rational number is definable without parameters in this structure, since it can be described using $0$, $1$, addition, multiplication, and additive inverses.

If $a \in \mathbb R$, then $a+1$ belongs to $\operatorname{dcl}(\{a\})$, since it is uniquely defined by:

Lemma 6.29 (Basic Properties of Definable Closure)

For any $A \subseteq M$, the following hold:

If $A \subseteq B$, then:

Also:

Proof

First, let $a \in A$. Then $a$ is uniquely defined over $A$ by the formula:

Therefore:

This proves:

Second, suppose $A \subseteq B$ and let $c \in \operatorname{dcl}(A)$. Then $c$ is uniquely defined by some formula with parameters from $A$. Since every parameter from $A$ is also a parameter from $B$, the same formula defines $c$ uniquely over $B$. Hence:

This proves monotonicity:

It remains to prove idempotence. By monotonicity and the inclusion $A \subseteq \operatorname{dcl}(A)$, we have:

For the reverse inclusion, suppose:

Then $b$ is uniquely defined by a formula using finitely many parameters:

For each $c_i$, choose a formula $\theta_i(z_i,\bar a_i)$ with parameters from $A$ that uniquely defines $c_i$ over $A$.

The element $b$ is defined over the parameters $c_1,\dots,c_n$ by some formula:

Replace the parameters $c_i$ by variables $z_i$, and define a new formula over $A$:

Because each $\theta_i$ uniquely defines $c_i$, this formula uniquely defines the same element $b$ over $A$. Therefore:

Thus:

Combining both inclusions gives: