Fork me on GitHub
Math for the people, by the people.

User login


% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these

% used for TeXing text within eps files
% need this for including graphics (\includegraphics)
% for neatly defining theorems and propositions
% making logically defined graphics

% there are many more packages, add them here as you need them

% define commands here
\subsection{Definable sets and functions}

\subsubsection{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 {\em 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 \emph{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.

\subsubsection{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 \emph{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$ \emph{proves} that $f$ is indeed a function, that is $T\vdash \forall \vec{x} \exists ! y. \phi(\vec{x}, y)$.

For example: the \emph{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 \emph{not} definable in this theory.

%\section{Definable closure and Algebraic closure}

%We define dcl$(B)$, the {\em definable closure of $B$} to be the set of %elements $a \in M^{n}$ for some $n$ so that $\{a\}$ is $B$-definable.

%As a weakening of this idea, we say that $a \in $acl$(B)$ iff there is some %finite $B$-definable set $S$ so that $a \in S$. 
%Note that if $M$ is an algebraically closed field, then acl$(B)$ is the %algebraic closure of $B$ because all polynomials have finitely many roots. 
%Thus this idea is an generalisation of the idea of \PMlinkname{algebraic %closure}{AlgebraicClosure}, so when there can be no confusion we call acl$(B)$ %the algebraic closure of $B$.
%% This subsection Also defines: definable closure, algebraic closure, parameter %   definable, zero definable