# 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.
1. Is the theory decidable? Does it have a nice or finite set of axioms?
2. What subsets are definable?
3. 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 $\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 $\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|\in P\}$ . Consider $H=\{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}$ .