Definable

Definable Functions and Relations

Suppose $\mathfrak{N}=⟨\mathbb{N},S,+,\cdot ,0⟩$. Then $R\subseteq {\mathbb{N}}^n$ and $f:{\mathbb{N}}^n\to \mathbb{N}$ are definable in $\mathfrak{N}$ from $\phi (x_1,\dots ,x_n)$ and $\psi (x_1,\dots ,x_n,y)$ respectively iff $R(a_1,\dots ,a_n)⟹\mathfrak{N}\models \phi (a_1,\dots ,a_n),$ $f(a_1,\dots ,a_n)=b⟹\mathfrak{N}\models \psi (a_1,\dots ,a_n,b).$ It follows from the first and second implication, that respectively, $\neg R(a_1,\dots ,a_n)⟹\mathfrak{N}\models \neg \phi (a_1,\dots ,a_n),$ $f(a_1,\dots ,a_n)\ne b⟹\mathfrak{N}\models \neg \psi (a_1,\dots ,a_n,b).$

Chinese Remainder Theorem

Suppose $m_0,\dots ,m_n$ are relatively prime. Then for any sequence of natural numbers $k_0,\dots ,k_n$ with $k_i<m_i$, there is a $c$ such that $k_i=\text{Rem}(c,m_i)$.

Proof. Let $M_i={\prod }_{j\ne i}{m}_j.$ Then $M_i$ and $m_i$ are relatively prime, so there exist $b_i$ such that $b_i{M}_i\equiv 1(\mathrm{mod}{m}_i).$ Let $c={\sum }_i{k}_i{b}_i{M}_i$ Then $c\equiv k_i{b}_i{M}_i(\mathrm{mod}{m}_i)$,since $m_i\mid M_j$ if $j\ne i$. Hence $c\equiv k_i(\mathrm{mod}{m}_i).$ Since $k_i<m_i$ this means $k_i=\text{Rem}(c,m_i)$. $\square$

(G"odel's $\beta$-function)

Let $\beta (u,v,i)=\text{Rem}(u,(1+i)v+1)=u\mathrm{mod}((1+i)v+1).$ Then for any $n$ and any sequence $k_0,\dots ,k_n$ of natural numbers, there exist $c$ and $d$ (which depend on $n$ and $k_0,\dots ,k_n$ and can effectively be found) such that $\beta (c,d,i)=k_i$ for $0\le i\le n$. The function $\beta$ is representable in PA. (It is ${\Delta }_0$.)

Theorem

If $f$ is primitive recursive, then $f$ is definable (in $\mathfrak{A}$ in the language $\mathcal{L}$) and is representable in PA.