Representable

Representable Relation

A relation $R\subseteq {\mathbb{N}}^n$ is representable in the theory $T$ iff there is a formula $\phi (v_1,\dots ,v_n)$ in $\mathcal{L}$ such that $R(a_1,\dots ,a_n)⟹T⊢\phi (a_1,\dots ,a_n),$ $\neg R(a_1,\dots ,a_n)⟹T⊢\neg \phi (a_1,\dots ,a_n).$

Representable Function

A function $f:{\mathbb{N}}^n\to \mathbb{N}$ is representable in the theory $T$ iff there is a formula $\phi (v_1,\dots ,v_n,v_{n+1})$ in the language $\mathcal{L}$ such that (i) $f(a_1,\dots ,a_n)=a_{n+1}$ implies $T⊢\phi (a_1,\dots ,a_n,a_{n+1})$, (ii) $f(a_1,\dots ,a_n)\ne a_{n+1}$ implies $T⊢\neg \phi (a_1,\dots ,a_n,a_{n+1})$.

Specifically when we consider $T$ as $PA$, we have the following definitions.

Definition (Representable Relation). Suppose $R\subseteq {\mathbb{N}}^n$ and $PA$ are the Peano Axioms.

Then the relation $R\subseteq {\mathbb{N}}^n$ is represented in $PA$, or equivalently $PA$ represents $R$, by the $\mathcal{L}$-formula $\phi (v_1,\dots ,v_n)$ if for all $a_1,\dots ,a_n\in \mathbb{N}$,

\begin{align} R(a_1,\dots,a_n) &\Longrightarrow PA \vdash \varphi(a_1,\dots,a_n), \\ \neg R(a_1,\dots,a_n) &\Longrightarrow PA \vdash \neg\varphi(a_1,\dots,a_n). \end{align}

Definition (Representable Function). A function $f:{\mathbb{N}}^n\to \mathbb{N}$ is represented in $PA$, or equivalently $PA$ represents $f$, by the $\mathcal{L}$-formula $\phi (v_1,\dots ,v_n,w)$ if for all $a_1,\dots ,a_n,b\in \mathbb{N}$:

\begin{align} f(a_1,\dots,a_n) = b &\Longrightarrow PA \vdash \varphi(a_1,\dots,a_n,b), \\ f(a_1,\dots,a_n) \neq b &\Longrightarrow PA \vdash \neg\varphi(a_1,\dots,a_n,b). \end{align}

Remark

The reason that we have $⟹$ in representability definition and $⟺$ in definability definition is we don’t necessarily get consistency of $PA$ and T, but it’s always true that for every $\phi (a_1,\dots ,a_n)$ exactly one of $\mathfrak{N}\models \phi (a_1,\dots ,a_n)$ and $\mathfrak{N}\models \neg \phi (a_1,\dots ,a_n)$ will be the case.

Strongly Representable

A function $f:{\mathbb{N}}^n\to \mathbb{N}$ is strongly representable in the theory $T$ iff there is a formula $\phi (v_1,\dots ,v_n,v_{n+1})$ in the language $\mathcal{L}$ such that (i) $f(a_1,\dots ,a_n)=a_{n+1}$ implies $T⊢\phi (a_1,\dots ,a_n,a_{n+1})$, (ii) $f(a_1,\dots ,a_n)\ne a_{n+1}$ implies $T⊢\forall v_1...\forall v_n\exists !v_{n+1}\phi (v_1,...,v_n,v_{n+1}).$

which states that $\phi$ encodes a function in every model of $T$, not necessarily standard.