nLab
definable set

Definition

Definability is most often considered only for a first-order language $L$ (not a theory); a definable set is an equivalence class of formulas which evaluate in the same way in every $L$-structure. It makes sense to do the same for a theory: in that case in the definition of the equivalence relation one restricts to models of $T$.

Let $L$ be a first-order language and $T$ a theory in $L$. Any formula $\varphi (x_1,\dots ,x_n)$, whose only free variables could be among $x_1,\dots ,x_n$, together with a model $M$ for $T$ evaluates to a truth value on each $a=(a_1,\dots ,a_n)\in M^n$, hence it determines the subset $\varphi (M)\subset M^n$ of all $a$ such that $\varphi (a)$. Two formulas $\varphi ,\psi$ with the same number of free variables are equivalent if $\varphi (M)=\psi (M)$ for every model $M$ of $T$. A definable set $X$ in $T$ is an equivalence class of formulas in $L$ under this relation. Consider the category ${ℳ}_{\mathrm{el}}(L)$ of $L$-structures and elementary monomorphism?s and its full subcategory ${ℳ}_{\mathrm{el}}(T)$ whose objects are the models of $T$. We can also view a definable set for a theory $T$ as a functor ${ℳ}_{\mathrm{el}}(T)\to \mathrm{Set}$ which is of the form $M\mapsto \varphi (M)$ for some $L$-formula $\varphi$.

By $X(M)$ denote the set of all $a\in M$ such that $X(a)$ holds, i.e. $\varphi (a)$ is true for any choice of representative $\varphi \in X$.

Given two definable sets $X,Y$ in $T$ a definable function $f:X\to Y$ is a definable subset of the product sort $X\times Y$ such that $f_M\in X(M)\times Y(M)$ is a function (we also write $f_M:X(M)\to Y(M)$) for every model $M$ of $T$. Analogously a definable equivalence relation is a definable subset $R\subset X\times X$ such that $R(M)$ is an equivalence relation for every model $M$ of $T$.

Properties

Proposition. Given a small category $ℳ$ and two functors $F,G:ℳ\to \mathrm{Set}$ the natural transformations $\alpha :F\to G$ are in 1-1 correspondence with functors $\tilde{\alpha }:ℳ\to \mathrm{Set}$ such that $\tilde{\alpha }(A)\subset F(A)\times G(A)$ and such that $\tilde{\alpha }(A)$ is a functional relation.

Proof. If $\alpha :F\to G$ is an $\mathrm{Ob}(ℳ)$-indexed family with components ${\alpha }_A:F(A)\to G(A)$ viewed as functional relations ${\tilde{\alpha }}_A\subset F(A)\times G(A)$, then the extension to a functor means
that there is a (automatically unique) dotted arrow ${\tilde{\alpha }}_f$

$$\begin{array}{ccc}{\tilde{\alpha }}_A& \stackrel{{\tilde{\alpha }}_f}{\hookrightarrow }& {\tilde{\alpha }}_B\\ \downarrow & & \downarrow \\ F(A)\times G(A)& \stackrel{F(f)\times G(f)}{⟶}& F(B)\times G(B)\end{array}$$\array{ \tilde\alpha_A & \stackrel{\tilde\alpha_f}\hookrightarrow & \tilde\alpha_B\\ \downarrow && \downarrow \\ F(A)\times G(A)&\stackrel{F(f)\times G(f)}\longrightarrow & F(B)\times G(B) }

making the diagram commutative (once the existence of ${\tilde{\alpha }}_f$ is known, the functoriality of ${\tilde{\alpha }}_{f\circ g}={\tilde{\alpha }}_f\circ {\tilde{\alpha }}_g$ comes by uniqueness of ${\tilde{\alpha }}_f$ and the functoriality of $F\times G$ which it restricts from). That means that for every $x\in F(A)$ $(x,{\alpha }_A(x))$ should be sent to $(F(f)(x),G(f)({\alpha }_A(x)))$ by ${\tilde{\alpha }}_f$, what is a restriction of $F(f)\times G(f)$, but by ${\alpha }_B$ being functional relation this must be the same as $(F(f)(x),{\alpha }_B(F(f)(x)))$, i.e. that $G(f)({\alpha }_A(x))={\alpha }_B(F(f)(x))$. Q.E.D.

In other words, functoriality of $\tilde{\alpha }$ is the same as $\alpha$ being natural.

Corollary. Definable functions for $L$ (for $T$) are in 1-1 correspondence with natural transformations of definable sets as functors ${ℳ}_{\mathrm{el}}(L)\to \mathrm{Set}$ (resp. ${ℳ}_{\mathrm{el}}(T)\to \mathrm{Set}$).

For a fixed (multi-sorted, first-order) theory $T$, definable sets and definable functions form a category $\mathrm{Def}(T)$. This category (or any equivalent category) is the syntactic category of the theory. Models of $T$ can be recovered as left exact functors $\mathrm{Def}(T)\to \mathrm{Set}$. Notice that definable sets are functors from models to sets, and models are functors definable sets to sets; just the latter are the “evaluation functionals” among all functors.

See also definable groupoid.

An $\mathrm{\infty }$-definable set is an intersection of definable sets.

We can also consider a relative version of a definable set (definability with parameters).

Given definable sets $X,Y$, a fixed model $M$ and a fixed set $A\subset X(M)$, we say that an element $b\in Y(M)$ is definable over $A$ if there is $(a_1,\dots ,a_n)\in A^n$ and a $T$-definable function $f:X^n\to Y$ such that $f(a_1,\dots ,a_n)=b$. All elements $b$ definable over $A$ form the subset $Y(A)\subset Y(M)$. A subset $B\subset M$ is definably closed if it is closed under definable functions. Given $A\subset M$, there is the minimal definably closed subset $B$ such that $A\subset B\subset M$, the definable closure $B=\mathrm{dcl}(A)$ of $A$.

If we extend the language by the constants from $A$ we get a new language $L_A$. The definable sets in language $L$ over $A$ are the definable sets in language $L_A$ over $\varnothing$.

One can also study ind-objects and pro-objects in the category of definable sets and definable functions.

Related concepts

• constructible set

• definable groupoid

References

• Moshe Kamensky, Ind- and Pro- definable sets, math.LO/0608163

• Jan Holly, Definable operations on sets and elimination of imaginaries, Proc. Amer. Math. Soc. 117 (1993), no. 4, 1149–1157, MR93e:03052, doi, pdf

• David Kazhdan, Lecture notes in model theory, pdf

• D. Haskell, E. Hrushovski, H.D.Macpherson, Definable sets in algebraically closed valued fields: elimination of imaginaries, J. reine und angewandte Mathematik 597 (2006), MR2007i:03040, doi/CRELLE.2006.066)