## You are here

Homedefinable

## Primary tabs

# 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.

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 $\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.

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\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)$.

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

## Mathematics Subject Classification

03C07*no label found*03F03

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Problem with Search Results

Hi, the search results display a description of the item found - this description is based on the corresponding LaTeX file. However, it displays also the REMARKED lines (i.e., those starting with %...).

Maybe it shouldn't.