Section 3.0: Number Theory

This chapter focuses on the language of the number theory, i.e. the theory of the structure $\mathfrak{N}=(\mathbb{N};0,S,<,+,\cdot,E)$ , as well as its reducts, i.e. $\mathfrak{N}_{S}=(\mathbb{N};0,S)$ , $\mathfrak{N}_{L}=(\mathbb{N};0,S,<)$ , $\mathfrak{N}_{A}=(\mathbb{N};0,S,<,+)$ , and $\mathfrak{N}_{M}=(\mathbb{N};0,S,<,+,\cdot)$ .

The questions for each theory to ask are as follows.

Is the theory decidable? Does it have a nice or finite set of axioms?
What subsets are definable?
What non-standard models are there for the theory?

An interesting thing about the number theory is that it contains a certain undecidable subtheory, implying that any theory that is at least as strong as this subtheory must be undecidable as well.

Preview

We want to compare the concepts of truth and proof; that is, we want to compare the set of sentences true in $\mathfrak{N}$ with the set of sentences that might be provable from an appropriate set $A$ of axioms.

Let $\#\alpha$ , called the Gödel number of $a$ , be a unique number assigned to each wff $\alpha$ of the language. Similarly, to each finite sequence $D$ of wffs (such as a deduction) we can assign a unique integer $\mathcal{G}(D)$ . There are three approaches now: self-reference, diagonalization, and computability approaches.

Self-reference

Let $A\subseteq\mbox{Th}\mathfrak{N}$ such that $\{\#\alpha|\alpha\in A\}$ is definable in $\mathfrak{N}$ . Then, there is a sentence $\sigma$ true in $\mathfrak{N}$ that is not deducible from $A$ .

We want a sentence $\sigma$ that would say something like “I am not deducible from $A$ .” Note, that such a sentence just ought to be true in $\mathfrak{N}$ , and, hence, not deducible from $A$ . To do this, we need a way in which a sentence can self-reference itself. We can do this by creating another formula $\phi$ (free in $v_{1}$ ), determining its Gödel number $q$ , and substituting $q$ for $v_{1}$ in $\phi$ to obtain $\sigma$ . The formula $\phi$ itself should say something like “If you substitute $n$ for $v_{1}$ in formula number $n$ , then it is not deducible in $A$ .” Then, $\sigma$ will say “If you substitute $q$ for $v_{1}$ in formula number $q$ , then the resulting formula is not deducible from $A$ .” In other words, $\sigma$ will say “ $\sigma$ is not deducible from $A$ .”

First, we define a relation $R$ such that $<a,b,c>\in R$ iff formula $\alpha_{a}(\mathbb{S}^{b}0)$ ( $\#\alpha_{a}=a$ ) is deducible from $A$ using the deduction number $c$ ( $c=\mathcal{G}(D)$ where $D$ is the deduction). One can argue that, since $\{\#\alpha|\alpha\in A\}$ is definable, so is $R$ (the proof of this is left for later subsections). Then, if $\rho$ defines $R$ , let $q=\#\phi$ where $\phi=\forall v_{3}\neg\rho(v_{1},v_{1})$ . What $\phi$ under assignment $s(v_{1})=n$ says is that $\alpha_{n}(\mathbb{S}^{n}0)$ is not definable from $A$ . Let $\sigma=\phi(\mathbb{S}^{q}0)=\forall v_{3}\neg\rho(\mathbb{S}^{q}0,\mathbb{S}^{q}0)$ . Then $\sigma$ says that $\alpha_{q}(\mathbb{S}^{q}0)=\phi(\mathbb{S}^{q}0)=\sigma$ is not definable from $A$ .

Corollary: $\{\#\alpha|\alpha\in\mbox{Th}\mathfrak{N}\}$ is not definable in $\mathfrak{N}$ . Indeed, the theorem implies that if $\{\#\alpha|\alpha\in A\}$ is definable, then there is $\sigma\in\mbox{Th}\mathfrak{N}-\mbox{Cn}A\subseteq\mbox{Th}\mathfrak{N}-A$ .
The Church’s thesis, being studied later, says that if a subset of $\mathbb{N}$ is decidable, then it is definable in $\mathfrak{N}$ . Hence, $\{\#\alpha|\alpha\in\mbox{Th}\mathfrak{N}\}$ is not decidable, and $\mbox{Th}\mathfrak{N}$ is not axiomatizable.

Diagonalization

Consider a relation $P$ such that $<a,b>\in P$ iff “ $a$ is true of $b$ ”: there is a wff $\alpha$ such that $\#\alpha=a$ , $v_{1}$ is the only free variable in $\alpha$ , and $\alpha(\mathbb{S}^{b}0)$ is true in $\mathfrak{N}$ . Then $A\subseteq\mathbb{N}$ is definable in $\mathfrak{N}$ iff for some $a$ , $A=P_{a}=\{b|<a,b>\in P\}$ . Consider $H=\{b|<b,b>\notin P\}$ . Then, $H$ is not definable in $\mathfrak{N}$ . It can be shown that the only way $H$ can be not definable in $\mathfrak{N}$ , if “true in $\mathfrak{N}$ ” is not definable.

$\{\#\alpha|\alpha\in\mbox{Th}\mathfrak{N}\}$ is not definable in $\mathfrak{N}$ (same as in the corollary above). $\mbox{Th}\mathfrak{N}$ is undecidable and not axiomatizable.

Computability

From Section 2.6 it follows, that if $A$ is effectively enumerable, then $\mbox{Cn}A$ is effectively enumerable as well. Using, again, Church’s thesis, it will be shown later that $\mbox{Th}\mathfrak{N}$ is not effectively enumerable.

For an effectively enumerable set $A$ , $\mbox{Cn}A\neq\mbox{Th}\mathfrak{N}$ .