# definable

## 0.1 Definable sets and functions

### 0.1.1 Definability In Model Theory

Let $\mathcal{L}$ be a first order language. Let $M$ be an $\mathcal{L}$-structure  . Denote $x_{1},\ldots,x_{n}$ by $\vec{x}$ and $y_{1},\ldots,y_{m}$ by $\vec{y}$, and suppose $\phi(\vec{x},\vec{y})$ is a formula  from $\mathcal{L}$, and $b_{1},\ldots,b_{m}$ is some sequence  from $M$.

Then we write $\phi(M^{n},\vec{b})$ to denote $\{\vec{a}\in M^{n}:M\models\phi(\vec{a},\vec{b})\}$. We say that $\phi(M^{n},\vec{b})$ is $\vec{b}$-definable. More generally if $S$ is some set and $B\subseteq M$, and there is some $\vec{b}$ from $B$ so that $S$ is $\vec{b}$-definable then we say that $S$ is $B$-definable.

In particular we say that a set $S$ is $\emptyset$-definable or zero definable iff it is the solution set of some formula without parameters.

Let $f$ be a function, then we say $f$ is $B$-definable iff the graph of $f$ (i.e. $\{(x,y):f(x)=y\}$) is a $B$-definable set.

A set or function is definable iff it is $B$-definable for some parameters $B$.

Some authors use the term definable to mean what we have called $\emptyset$-definable here. If this is the convention of a paper, then the term parameter definable will refer to sets that are definable over some parameters.

### 0.1.2 Definability of functions in Proof Theory

In proof theory, given a theory $T$ in the language $\mathcal{L}$, for a function $f:M\rightarrow M$ to be definable in the theory $T$, we have two conditions:

(i) There is a formula in the language $\mathcal{L}$ s.t. $f$ is definable over the model $M$, as in the above definition; i.e., its graph is definable in the language $\mathcal{L}$ over the model $M$, by some formula $\phi(\vec{x},y)$.

(ii) The theory $T$ proves that $f$ is indeed a function, that is $T\vdash\forall\vec{x}\exists!y.\phi(\vec{x},y)$.

Title definable Definable 2013-03-22 13:26:52 2013-03-22 13:26:52 CWoo (3771) CWoo (3771) 17 CWoo (3771) Definition msc 03C07 msc 03F03 definable set definable function definable relation