# 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},\mathrm{\dots},{x}_{n}$ by $\overrightarrow{x}$ and ${y}_{1},\mathrm{\dots},{y}_{m}$ by $\overrightarrow{y}$, and suppose $\varphi (\overrightarrow{x},\overrightarrow{y})$ is a formula^{} from $\mathcal{L}$, and ${b}_{1},\mathrm{\dots},{b}_{m}$ is some sequence^{} from $M$.

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

In particular we say that a set $S$ is $\mathrm{\varnothing}$-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.

If $S$ is $B$-definable then any automorphism^{} of $M$ that fixes $B$ pointwise, fixes $S$ setwise.

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 $\mathrm{\varnothing}$-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.

Sometimes in model theory^{} it is not actually very important what language^{} one is using, but merely what the definable sets are, or what the definability relation^{} is.

### 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\to 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 $\varphi (\overrightarrow{x},y)$.

(ii) The theory $T$ *proves* that $f$ is indeed a function, that is $T\u22a2\forall \overrightarrow{x}\exists !y.\varphi (\overrightarrow{x},y)$.

For example: the *graph* of exponentiation^{} function ${x}^{y}=z$ is definable by the language of the theory $I{\mathrm{\Delta}}_{0}$ (a subsystem of PA, with induction axiom^{} restricted to bounded formulas only), however the function itself is *not* definable in this theory.

Title | definable |
---|---|

Canonical name | Definable |

Date of creation | 2013-03-22 13:26:52 |

Last modified on | 2013-03-22 13:26:52 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 17 |

Author | CWoo (3771) |

Entry type | Definition |

Classification | msc 03C07 |

Classification | msc 03F03 |

Defines | definable set |

Defines | definable function |

Defines | definable relation |