diagonalization about incompleteness

Question

In the Enderton's logic book(page 186-187), he writes 'diagonalization approach' for proving undefinability of $\#Th\mathfrak{N}=\{\#\tau |\vDash_{\mathfrak{N}}\tau \}$ where $\#\tau$ is the godel number of sentence $\tau$. sketch introduced there is,

$<a,b>\in P$ iff $a$ is the godel number of a formula $α(v_1)$ and $\vDash_{\mathfrak{N}}α(S^b0)$. define $P_a=\{b|<a,b>\in P\}$, $H=\{b| <b,b>\notin P \}$.

then any definable subset of natural numbers are listed as $P_2,P_2,\cdots$. since $a\in H \Longleftrightarrow a\notin P_a$, $H$ is not definable in $\mathfrak{N}$.

In the book, endertons writes "if $Th\mathfrak{N}$ were definable in $N$, then the above set $H$ would also be definable, which it is not." thus $\#Th\mathfrak{N}$ is not definable in $\mathfrak{N}$.

I understand $H$ is not definable by above, but do not get idea how to derive contradiction assuming $Th\mathfrak{N}$ is definable. and another question is whether $\#Th\mathfrak{N}$ is definable iff $Th\mathfrak{N}$ is definable.

Thanks in advance!

Answer 1

See page 152 :

Recall that the theory of $\mathfrak A$, written $\mathsf{Th} \mathfrak A$, is the set of all sentences true in $\mathfrak A$.

See page 184 :

THEOREM 30A : Let $A ⊆ \mathsf{Th} \mathfrak N$ be a set of sentences true in $\mathfrak N$, and assume that the set $\{ \# α \mid α \in A \}$ of Gödel numbers of members of $A$ is a set definable in $\mathfrak N$. Then we can find a sentence $\sigma$ such that $\sigma$ is true in $\mathfrak N$ but $\sigma$ is not deducible from $A$.

Page 186 :

COROLLARY 30B : The set $\{ \# \tau \mid \vDash_\mathfrak N \tau \}$ of Gödel numbers of sentences true in $\mathfrak N$ is a set that is not definable in $\mathfrak N$.

PROOF. If this set were definable, we could take $A = \mathsf{Th} \mathfrak N$ in the preceding theorem to obtain a contradiction.

In Th.30A we have that, for a set $A ⊆ \mathsf{Th} \mathfrak N$ whatever of sentences true in $\mathfrak N$, the corresponding set of Gödel numbers is not definable in $\mathfrak N$.

This is of course true also for $A = \mathsf{Th} \mathfrak N$, i.e. the set of Gödel numbers of $\mathsf{Th} \mathfrak N$ itself is not definable in $\mathfrak N$.

But $\mathsf{Th} \mathfrak N$ is the set of all sentences true in $\mathfrak N$, and thus the corresponding set of Gödel numbers is the set $\{ \# \tau \mid \tau \in \mathsf{Th} \mathfrak N \} = \{ \# \tau \mid \vDash_\mathfrak N \tau \}$.

---

You have to take care about the difference between $\mathsf{Th} \mathfrak N$, which is a set of sentences of arithmetic and the corresponding set of Gödel numbers, i.e. the set $\{ \# \tau \mid \tau \in \mathsf{Th} \mathfrak N \}$, which is a set of numbers.

What is not definable in $\mathfrak N$ is the last one; see page 90 :

In general, a $k$-ary relation on $| \mathfrak A |$ is said to be definable in $\mathfrak A$ iff there is a formula $\varphi$ (whose free variables are among $v_1,\ldots, v_k$) that defines it there.

Thus Th.30A proves that there is no formual $\varphi$ of first-order arithmetic such that $\varphi(n)$ holds in $\mathfrak N$ iff $n$ is the Gödel number of a sentence $\tau \in \mathsf{Th} \mathfrak N$.

---

The same result is proved again [see page 187] : THEOREM 30C (a) : PROOF. Part (a), which is the same as Corollary 30B [...], with the diagonalization approach.

The "ingredients" of the proof are :

(i) a binary relation $P$ on the natural numbers such that :

$\langle a,b \rangle \in P \Leftrightarrow$ $a$ is the Gödel number of a formula $\alpha(v_1)$ (with just $v_1$ free) and $\vDash_\mathfrak N \alpha(S^b0)$,

i.e. :

$\langle a,b \rangle \in P \Leftrightarrow$ “[the formula with Gödel number] $a$ is true of $b$”.

Assuming that the relation $P$ is definable, and recalling the above definition of definable, we have that the binary relation $P$ on $\mathbb N$ is definable in $\mathfrak N$ iff there is a formula $\varphi$ (whith two free variables $v_1,v_2$) such that : $a,b \in P \Leftrightarrow$ iff $\vDash_\mathfrak N \varphi[a,b]$.

Then any set of natural numbers that is definable in $\mathfrak N$ equals, for some $a$, the “vertical section” $P_a = \{ b \mid \langle a,b \rangle \in P \}$ of $P$.

Consider for example the simple formula $(v_1=0)$, i.e., more "formally" $=(v_1,0)$, and let $f$ its Gödel number. Then,

$\langle f,n \rangle \in P \leftrightarrow \vDash_\mathfrak N (v_1=0)(S^n0)$.

But clearly $\vDash_\mathfrak N (v_1=0)(S^n0)$ only for $n=0$; thus, $\langle f,0 \rangle \in P$, i.e. $P_f = \{ 0 \}$.

In this way, we have a listing of all sets definable in $\mathfrak N$ : $P_1, P_2, \ldots$, generated by the list of all formulae with one free variable.

(ii) Consider now the "diagonal" set $H = \{ b \mid \langle b, b \rangle \notin P \}$.

Clearly, $H \ne P_n$, for all $n$, because $n \in H \Leftrightarrow n \notin P_n$.

Then $H$ is nowhere on the list $P_1, P_2,\ldots$. Therefore $H$ is not definable in $\mathfrak N$ [because it is not in the list of all the definable sets].

Why is $H$ undefinable? After all, we have above specified that :

$b \in H \Leftrightarrow$ “not [the formula with Gödel number $b$ is true of $b$]” $\Leftrightarrow$ not [$b$ is the Gödel number of a formula $α(v_1)$ (with just $v_1$ free) and $\vDash_\mathfrak N α(S^b0)$].

What is the barrier to translating this specification into the language of arithmetic? We will show that the barrier is not being the Gödel number of a formula [...] and the barrier is not having $v_1$ free and not substituting the numeral $S^b0$ into a formula.

All these steps will be performed through the technique of "arithmetization of syntax" : see for example : Gödel's incompleteness theorems and see Enderton's book, SECTION 3.4.

By the process of elimination, we will show that the only possible barrier is saying of a sentence that is true in $\mathfrak N$.

Thiss means that our construction of the relation $P$ such that :

$\langle a,b \rangle \in P \Leftrightarrow$ “[the formula with Gödel number] $a$ is true of $b$”

based on the assumption that the relation $P$ is definable, will not do, i.e. it is not able to generate the list of all defineable sets.

And thus, in conclusion, the relation “$a$ is the Gödel number of a formual that is true of $b$” is not "expressible" in the language of arithmetic.

---

See page 236 :

TARSKI UNDEFINABILITY THEOREM (1933) : The set $\# \mathsf{Th} \mathfrak N$ is not definable in $\mathfrak N$.