The Gödel incompleteness theorems are closly linked with computability theory. Not much computability theory is required to understand the connection, but this connection is best seen when one relates the idea of ${\Sigma}_{1}$ formulas to the idea of recursively enumerable sets (also sometimes called computably enumerable sets). This page reviews a small amount of computability theory and sets out the connection.

Computability theory identifies an informal intuitive idea of what it
means for a fuction or set to be computable with a precise machine model
for computability, such as Turing machines or register machines. The fact
that there are so many machine models known that capture the same notion
of computable

can be taken a evidence that the intuitive idea is
indeed accurately captured by these models. Here I will take the idea
of register machine

, as it is a little more convenient for our
purposes. The energetic reader will be able to verify that the register
machine model does indeed correspond whith his/her favourite model,
be it Turing machines, the lambda calculus, Kolmogorov machines, or whatever.

Definition.

A register machine has a finite number of registers
${R}_{0},{R}_{1},\dots $
each of which is capable of storing a natural number. It has a *program*
which is a finite list of instructions labelled ${I}_{0},{I}_{1},\dots $.
Each instruction is of the type

- ${I}_{k}$: ${R}_{i}\text{:=}{R}_{i}+1$

or

- ${I}_{k}$: if ${R}_{i}>0$ then ${R}_{i}\text{:=}{R}_{i}-1$ else goto ${I}_{j}$

In both cases, the next instruction to be execute is the next one on the list, ${I}_{k+1}$,
unless the goto ${I}_{j}$

is performed. There is a last instruction, and if this last
instruction is performed without any goto ${I}_{j}$

clause being executed then the machine
instead of attempting to execute the next instruction (which doesn't exist) simply halts.

Definition.

A register machine *computes a total function*
$f:\mathbb{N}\to \mathbb{N}$
if, for all $n\in \mathbb{N}$, whenever
it is started with ${R}_{0}$ containing $n$ and all other registers zero it eventually halts
with $f\left(n\right)$ in ${R}_{0}$. Similarly, it *computes a partial
function*
$f:\mathbb{N}\to \mathbb{N}$ (i.e. a function
$f:A\to \mathbb{N}$ where $A\subseteq \mathbb{N}$)
if, for all $n\in \mathbb{N}$, whenever
it is started with ${R}_{0}$ containing $n$
and all other registers zero, if $f\left(n\right)$ is defined
(i.e. $n\in A$) then it eventually halts
with $f\left(n\right)$ in ${R}_{0}$ and if $f\left(n\right)$ is not
defined (i.e. $n\notin A$) then it goes on for ever.

We can modify the definition just given to computing (total or partial) functions $f:{\mathbb{N}}^{k}\to \mathbb{N}$ of several arguments by just requiring that ${R}_{0},\dots ,{R}_{k-1}$ contain the arguments ${n}_{0},\dots ,{n}_{k-1}$ of $f({n}_{0},\dots ,{n}_{k-1})$.

Definition.

A (total or partial)
function is computable or *recursive* if it can be computed
by a register machine.

In the theory, total recursive functions
and partial recursive functions behave quite differently
and recursive function

is reserved to mean
total recursive function

,
the word partial

if applicable being never omitted.

Definition.

If $A\subseteq \mathbb{N}$ its *charactistic function*
${\chi}_{A}:\mathbb{N}\to \left\{0,1\right\}$
is the total function with $f\left(n\right)=1\leftrightarrow n\in A\leftrightarrow f\left(n\right)\ne 0$.
A register machine *computes the set*
$A$ if and only if
it computes the characteristic function ${\chi}_{A}$.
Similarly for $A\subseteq {\mathbb{N}}^{k}$,
${\chi}_{A}:{\mathbb{N}}^{k}\to \left\{0,1\right\}$
is defined by $f({n}_{0},\dots ,{n}_{k-1})=1\leftrightarrow ({n}_{0},\dots ,{n}_{k-1})\in A\leftrightarrow f({n}_{0},\dots ,{n}_{k-1})\ne 0$ and $A$ is computed if and only if ${\chi}_{A}$ is.
A set that is computed by some register machine is called
computable or *recursive*.

There is a weaker notion of computability that is also important.

Definition.

A set is *recursively enumerable* or *r.e.* if either it is empty or
there is a (total) computable function
$f:\mathbb{N}\to \mathbb{N}$ such that $A$
is the range of $f$.

Exercise.

Show that that a set $A$ is r.e. if and only if there is a register machine which when started with $n$ in ${R}_{0}$ and all other registers zero then the machine halts if and only if $n\in A$, and that this holds if and only if the partial function $f:A\to \left\{0\right\}$ is partial recursive.

Definition.

A set
$A\subseteq \mathbb{N}$ is *co-r.e.* if its complement
$\mathbb{N}-A$ is r.e.

Theorem.

A set $A$ is recursive if and only if it is both r.e. and co-r.e.

There is a convincing informal argument that says that this
notion of computability really does capture the correct

intuitive idea. This argument is due to Turing, for the idea
of computability defined using Turing machines, but it can
be adapted to register machines by simply showing how to simulate
an arbitrary Turing machine by a register machine. The statement
that this notion of computability is correct is known as
*Church's thesis* or *the Chruch-Turing thesis*.

The main theorem here says that a set is r.e. if and only if it is defined by a ${\Sigma}_{1}$ formula and is co-r.e. if and only if it is defined by a ${\Pi}_{1}$ formula. If we are to prove statements like this we must start by finding ways of expressing complicated predicates as ${\Delta}_{0}$ formulas. This is how we start. The key result is due to Gödel and is often called the $\beta $-function lemma. It expresses the well-known fact that there is an injection ${\mathbb{N}}^{<\omega}\to \mathbb{N}$ from finite sequences of naturals to naturals, but the twist is that Gödel shows how to do this in such a way that the inverse map can be described by a ${\Delta}_{0}$ formula.

We start first with something a little simpler.

Exercise.

Show that the function

is a bijection ${\mathbb{N}}^{2}\to \mathbb{N}$.

This function is (for obvious reasons) called the *pairing function*.
Note that if $\u27e8u,v\u27e9=x$ then
$u,v<x+1$ and the statement $\u27e8u,v\u27e9=x$
is quantifier free, so is certainly ${\Delta}_{0}$.

Definition.

We write

for $z<y\wedge \exists w<x+1\u200a(x=yw+z)$. This formula is clearly ${\Delta}_{0}$ and says that $z$ is the remainder on dividing $x$ by $y$.

Exercise.

It is true (i.e. in $\mathbb{N}$) that $\forall x\u200a\forall y\u200a(y\ne 0\to \exists z\u200az=\text{rem}\left(\frac{x}{y}\right))$. This statement is not however provable in $\text{DOR}$.

Definition.

For $x,y\in \mathbb{N}$, we let $\beta (x,y)$ be

where $x=\u27e8u,v\u27e9$.

Lemma.

There is a ${\Delta}_{0}$ formula defining $\beta (x,y)=z$ and for any $k\in \mathbb{N}$ and sequence $s=({s}_{0},\dots ,{s}_{k-1})\in {\mathbb{N}}^{<\omega}$ of length $k$ there is $x\in \mathbb{N}$ such that $\forall y<k\u200a{s}_{y}=\beta (x,y)$.

There are a number of possible proofs of this. The original and perhaps the simplest uses the Chinese Remainder Theorem.

Theorem.

If ${m}_{0},{m}_{1},\dots ,{m}_{k-1}$ are positive integers and pairwise coprime and is ${x}_{i}\in \mathbb{N}$ for each $i$ then there is $x\in \mathbb{N}$ such that $x\equiv {x}_{i}\text{mod}{m}_{i}$ for each $i<k$.

**Proof.**

Given $s\in {\mathbb{N}}^{<\omega}$, $s=({s}_{0},{s}_{1},\dots {s}_{k-1})$, let $w=max({s}_{0},{s}_{1},\dots {s}_{k-1},k)$ and $v=w$. So for $0<i<j\u2a7dk$, if $p$ is prime and $p\left|\right(iv+1)$ and $p\left|\right(jv+1)$ then $iv+1=ap$ and $jv+1=bp$ for some $a,b\in \mathbb{N}$ with $b>a$, so $(j-i)v=(b-a)p$ hence $p$ divides $(j-i)v$. If $p$ divides $v$ then $p$ divides $iv$ and hence $p=1$ since it also divides $iv+1$. So $p|j-i$. In particular $p<k\u2a7dw$ so $p$ divides $w=v$ and once again this means $p$ equals $1$. Thus there is no such prime $p$ and the moduli $iv+1$ are coprime for $1\u2a7di\u2a7dk$. Also ${s}_{i}\u2a7dw<(i+1)v+1$ for all such $i$, so by the Chinese Remainder Theorem there is $u$ with ${s}_{i}=\text{rem}\left(\frac{u}{(i+1)v+1}\right)$ for all $0\u2a7di<k$.

Put $x=\u27e8u,v\u27e9$ and we are finished, the ${\Delta}_{0}$ formula $\beta (x,y)=z$ being

In particular for a sequence $s\in {\mathbb{N}}^{<\omega}$ the map $s\mapsto \u27e8x,k\u27e9$ defines an injection ${\mathbb{N}}^{<\omega}\to \mathbb{N}$, where $k$ is the length of $s$ and $x$ is the least natural number such that $\forall y<k\u200a{s}_{y}=\beta (x,y)$.

The link with computability comes with the following consequence of Gödel's $\beta $-function lemma.

Theorem.

Suppose $f:{\mathbb{N}}^{k}\to \mathbb{N}$ is a partial recursive function. Then there is a ${\Sigma}_{1}$ formula $\theta (\stackrel{\_}{x},y)$ such that for all $\stackrel{\_}{n},m\in \mathbb{N}$ $\mathbb{N}\models \theta (\stackrel{\_}{n},m)$ holds if and only if $f\left(\stackrel{\_}{n}\right)=m$.

**Proof.**

The proof is by describing the action of a register machine using the $\beta $ function.

Given a register machine using registers ${r}_{0},\dots ,{r}_{n}$ we consider a formulas starting $\exists {R}_{0},\dots ,{R}_{n},I,t\u200a\dots $ where $\beta ({R}_{i},j)$ is the contents of ${r}_{i}$ at time $j$, $\beta (I,j)$ is the index of the next instruction to be performed at time $j$, and $t$ is the total time of the computation. Then the entire computation can be described in a ${\Delta}_{0}$ way with formulas such as

- $\beta ({R}_{i},0)={x}_{i}$, saying ${r}_{i}$ is initially ${x}_{i}$,
- $\beta ({R}_{i},t)=y$, saying ${r}_{i}$ is at the end $y$,
- $\beta ({I}_{i},0)=0$, saying the first instruction is performed first,
- $\beta (I,i)=p\to \beta ({R}_{j},i\mathrm{+1})=\beta ({R}_{j},i)\mathrm{+1}\wedge \beta (I,i)=p\mathrm{+1}$, for the "${I}_{p}:{r}_{j}:={r}_{j}+1$" instruction,
- $\beta (I,i)=p\wedge \beta ({R}_{j},i)>0\to \beta ({R}_{j},i\mathrm{+1})\mathrm{+1}=\beta ({R}_{j},i)\wedge \beta (I,i)=p\mathrm{+1}$, and $\beta (I,i)=p\wedge \beta ({R}_{j},i)=0\to \beta ({R}_{j},i\mathrm{+1})=\beta ({R}_{j},i)\wedge \beta (I,i)=q$, for the "${I}_{p}:{r}_{j}:={r}_{j}-1\text{else go to}{I}_{q}$" instruction,

and $\beta ({R}_{l},i\mathrm{+1})=\beta ({R}_{l},i)$ for all other $l$, quantified over all $i<t$.

Theorem.

A set $A\subseteq {\mathbb{N}}^{k}$ is r.e. if and only if it is defined by a ${\Sigma}_{1}$ formula. $A$ is co-r.e. if and only if it is defined by a ${\Pi}_{1}$ formula.

It follows that a set is recursive iff it is simultaneously defined by both a ${\Sigma}_{1}$ formula and a ${\Pi}_{1}$ formula.

Exercise.

Find a recursive set that is not definable by a ${\Delta}_{0}$ formula. Hint: show that the set of $(n,m)$, such that $n$ is the Gödel-number of a ${\Delta}_{0}$ sentence ${\theta}_{n}\left(x\right)$ and ${\theta}_{n}\left(m\right)$ is true, is recursive.