Representability and diagonalisation

In the last two web pages we learnt that $DOR$ is able to prove all true $Σ_{1}$ sentences and that $Σ_{1}$ formulas represent all r.e. relations. It is now time to put these facts together.

1. Representability

Definition.

A function $f : ℕ^{k} \to ℕ$ is $Σ_{1}$ -represented in $DOR$ if there is a $Σ_{1}$ formula $θ (\overline{x}, y)$ such that for all $\overline{n} \in ℕ$ and for $m = f (\overline{n})$ , $θ (\overline{n}, m)$ is true (and hence provable in $DOR$ ) and also

DOR ⊢ \forall y (θ (\overline{n}, y) \to y = m)

Definition.

A set $A \subseteq ℕ^{k}$ is $Σ_{1}$ -represented in $DOR$ if there is a $Σ_{1}$ formula $θ (\overline{x})$ such that for all $\overline{n} \in ℕ^{k}$

\overline{n} \in A \Rightarrow DOR ⊢ θ (\overline{n})

and

\overline{n} \notin A \Rightarrow DOR ⊢ \neg θ (\overline{n})

If you think about it, it should be clear that only recursive sets can be represented in $DOR$ . This is because one could search for proofs of $θ (\overline{n})$ or $\neg θ (\overline{n})$ to determine whether $\overline{n} \in A$ . Similarly, a total function $f : ℕ^{k} \to ℕ$ , if represented, must be recursive. In fact every recursive set and recursive function can be so represented.

Theorem.

Every total recursive function $f$ is $Σ_{1}$ -represented in $DOR$ .

Proof.

Let $f : ℕ^{k} \to ℕ$ be a total recursive function. We write $\overline{x}$ for a tuple of $k$ variables and $\overline{n}$ for a tuple of $k$ natural numbers. Similarly we write a bar to denote a tuple (pair, triple, quadruple, etc.) of unknown or undefined length.

We saw on an earlier web page that there is a $Δ_{0}$ formula $θ (\overline{x}, y, \overline{z})$ such that for all $\overline{n}, m \in ℕ$ $f (\overline{n}) = m$ holds iff $\exists \overline{z} θ (\overline{n}, m, \overline{z})$ is true. This formula does not have all the properties we require however. For example it may be consistent with $DOR$ that $\exists \overline{z} θ (\overline{n}, l, \overline{z})$ holds for some $l \neq m$ , though this is not actually true in $ℕ$ . In other words it may be that some $M ⊨ DOR$ has $\overline{c} \in M ⊨ \exists \overline{z} θ (\overline{n}, l, \overline{c})$ for $m \neq l$ though of course in such a case not all the $\overline{c}$ will be in $ℕ$ . We must modify $θ$ to obtain a formula representing $f$ in the required way.

For the tuple $\overline{x}$ , $Σ \overline{z}$ denotes the term $z_{1} + \dots + z_{l}$ where $l$ is the length of the tuple. Consider the formula $ψ (\overline{x}, y, \overline{z})$ defined to be,

θ (\overline{x}, y, \overline{z}) \land \forall u, \overline{v} ⩽ (y + Σ \overline{z}) (θ (\overline{x}, u, \overline{v}) \to (y + Σ \overline{z}) ⩽ (u + Σ \overline{v}))

saying that not only does $θ$ hold but the choice of $y + Σ \overline{z}$ is least possible. Note that the quantifier here $\forall u, \overline{v} ⩽ (y + Σ \overline{z}) \dots$ means that each variable quantified over is bounded by the term $y + Σ \overline{z}$ so it is a bounded quantifier.

First note that our new $ψ (\overline{x}, y, \overline{z})$ defines $f$ in $ℕ$ as before. For if $f (\overline{n}) = m$ there are $\overline{z} \in ℕ$ such that $ℕ ⊨ θ (\overline{n}, m, \overline{z})$ and we may choose $\overline{z}$ to minimise $m + Σ \overline{z}$ hence $ℕ ⊨ ψ (\overline{n}, m, \overline{z})$ .

To show that $DOR ⊢ \forall y (\exists \overline{z} ψ (\overline{n}, y, \overline{z}) \to y = m)$ consider some $M ⊨ DOR$ and $u, \overline{v} \in M ⊨ ψ (\overline{n}, u, \overline{v})$ . Then for the $\overline{z} \in ℕ$ chosen in the last paragraph we have $M ⊨ ψ (\overline{n}, m, \overline{z})$ since this is $Δ_{0}$ and true, and hence $u + Σ \overline{v} ⩽ m + Σ \overline{z} \in ℕ$ . Therefore $u, \overline{v} \in ℕ$ and as $M ⊨ ψ (\overline{n}, u, \overline{v})$ with $ψ$ in $Δ_{0}$ it must be true: $ℕ ⊨ ψ (\overline{n}, u, \overline{v})$ . (For if not, $ℕ ⊨ \neg ψ (\overline{n}, u, \overline{v})$ and this is also a true $Δ_{0}$ statement hence true in $M$ .) Therefore $m = u$ as this is the only value of the function $f (\overline{n})$ , as required.

Theorem.

Every recursive set $A$ is $Σ_{1}$ -represented in $DOR$ .

Proof.

If $A \subseteq ℕ^{k}$ is recursive then we know its characteristic function is represented in the sense of the previous result. This means that there is a $Σ_{1}$ formula $θ (\overline{x}, y)$ such that if $\overline{n} \in A$ then $DOR ⊢ θ (\overline{n}, 1)$ and if $\overline{n} \notin A$ then $DOR ⊢ θ (\overline{n}, 0)$ . Also, since $DOR ⊢ 0 \neq 1$ , if $\overline{n} \notin A$ then $DOR ⊢ θ (\overline{n}, 0)$ and also $DOR ⊢ \forall x (θ (\overline{n}, x) \to x = 0)$ hence $DOR ⊢ \neg θ (\overline{n}, 1)$ . Therefore $A$ is represented as a set by the formula $θ (\overline{n}, 1)$ .

2. Diagonalisation

The key lemma here, called the Diagonalisation lemma or the Diagonal lemma is due to Gödel. It is rather powerful and used for much more than just to prove the incompleteness theorems. In some sense it generalises Cantor's diagonal method that was used to prove that neither the set of reals nor the power set of the naturals is countable. First we review the idea of Gödel-numbering.

Gödel-numbering is a system of numbering expressions of a first order language. Since a first order language can be considered as a countable set of symbols (with certain grammatical production rules) the set of strings (of finite length) formed from these symbols is also countable. It follows that there is an injection $s \mapsto ⌜s⌝ \in ℕ$ from strings $s$ to natural numbers, called Gödel-numbering. With the $β$ -function we can be more precise: if we have a mapping of symbols $α \mapsto g (α) \in ℕ$ we can define $⌜s⌝ = ⟨ k, x ⟩$ where $k$ is the length of $s = s_{0} s_{1} \dots s_{k - 1}$ and $x$ is the least code of the sequence $g (s_{0}), g (s_{1}) \dots g (g_{k - 1})$ in the sense of the $β$ -function: $\forall y < k (g (s_{y}) = β (x, y))$ . The important thing is that this operation is computable in a very natural sense: every syntactical operation of terms and formulas of the language required to define the notion of proof corresonds to a recursive operation on Gödel-numbers. (This is a lot of detailed checking and somewhat outside the scope of these notes.)

From now on, we fix such a Gödel-numbering for the usual language of arithmetic.

Diagonalisation Lemma

For any $L_{A}$ formula $θ (x)$ with a single free variable $x$ there is a sentence $G_{θ}$ of $L_{A}$ such that

DOR ⊢ G_{θ} \leftrightarrow θ (⌜G_{θ}⌝)

Moreover, if $θ$ is $Π_{1}$ then we can find such $G_{θ}$ which is also $Π_{1}$ .

Proof.

Define the recursive function $diag (n)$ to be $⌜\forall y (y = n \to σ (y))⌝$ if $n = ⌜σ (x)⌝$ , the Gödel-number of a formula of one single free variable $x$ , and to be $0$ otherwise. Thus $diag (⌜σ (x)⌝)$ is the Gödel-number of a sentence equivalent to $σ (n)$ where $n = ⌜σ (x)⌝$ . Let $δ (x, y)$ be a $Σ_{1}$ formula representing $diag (x) = y$ in $DOR$ . Let $ψ (x)$ be $\forall z (δ (x, z) \to θ (z))$ , which you can think of as $θ (diag (x))$ . Let $n = ⌜ψ (x)⌝$ , so you may think of $ψ (n)$ as $θ (⌜ϕ (n)⌝)$ , and $DOR ⊢ G_{θ} \leftrightarrow θ (⌜G_{θ}⌝)$ where $G_{θ}$ is $\forall y (y = n \to ψ (y))$ .

Tarski's theorem on Truth

Let $M ⊨ DOR$ . Then for no formula $τ (x)$ of $L_{A}$ is it the case that

M ⊢ τ (⌜σ⌝) \leftrightarrow σ

for all sentences $σ$ of $L_{A}$ .

Proof.

If such $τ (x)$ exists in some $M$ , find $G$ such that $DOR ⊢ G \leftrightarrow \neg τ (⌜G⌝)$ and obtain a contradiction.

Exercise.

Why does the preceding argument not show that there is no $Π_{1}$ definition of $Π_{1}$ truth? In fact there is some $Π_{1}$ formula $τ (x)$ of $L_{A}$ such that for all sufficiently strong models $M$ (satisfying a few additional axioms as well as $DOR$ ) it the case that

M ⊢ τ (⌜σ⌝) \leftrightarrow σ

for all $Π_{1}$ sentences $σ$ of $L_{A}$ . (Follow the above class and point out where the formula class is wrong.) What class of formulas can you convincingly prove not to define $Π_{1}$ truth?