5.2: The Language, the Structure, and the Axioms of N

We work in the language of number theory

$$\mathcal{L}_{NT} = \{ 0, S, +, \cdot, E, < \},$$

and we will continue to work in this language for the next two chapters. $\mathfrak{N}$ is the standard model of the natural numbers,

$$\mathfrak{N} = \left( \mathbb{N}, 0, S, +, \cdot, E, < \right),$$

where the functions and relations are the standard functions and relations on the natural numbers.

We will now establish a set of nonlogical axioms, $N$. You will notice that the axioms are clearly sentences that are true in the standard structure, and thus if $T$ is any set of axioms such that $T \vdash \sigma$ for all $\sigma$ such that $\mathfrak{N} \models \sigma$, then $T \vdash N$. So, as we prove that several sorts of formulas are derivable from $N$, remember that those same formulas are also derivable from any set of axioms that has any hope of providing an axiomatization of the natural numbers.

The axioms system $N$ was introduced in Example 2.8.3 and is reproduced here. These 11 axioms establish some of the basic facts about the successor function, addition, multiplication, exponentiation, and the $<$ ordering on the natural numbers.

Chaff: To be honest, the symbol $E$ and the axioms about exponentiation are not needed here. It is possible to do everything that we do in the next couple of chapters by defining exponentiation in terms of multiplication, and introducing $E$ as an abbreviation in the language. This has the advantage of showing more explicitly how little you need to prove the incompleteness theorems, but adds some complications to the exposition. We have decided to introduce exponentiation explicitly and add a couple of axioms, which will allow us to move a little more cleanly through the proofs of our theorems.

The Axioms of $N$

$$\begin{align} &1. \left( \forall x \right) \neg Sx = 0. \\ &2. \left( \forall x \right) \left( \forall y \right) \left[ Sx = Sy \rightarrow x = y \right]. \\ &3. \left( \forall x \right) x + 0 = x. \\ &4. \left( \forall x \right) \left( \forall y \right) x + Sy = S \left( x + y \right). \\ &5. \left( \forall x \right) x \cdot 0 = 0. \\ &6. \left( \forall x \right) \left( \forall y \right) x \cdot Sy = \left( x \cdot y \right) + x. \\ &7. \left( \forall x \right) xE0 = S0. \\ &8. \left( \forall x \right) \left( \forall y \right) xE \left( Sy \right) = \left( xEy \right) \cdot x. \\ &9. \left( \forall x \right) \neg x < 0. \\ &10. \left( \forall x \right) \left( \forall y \right) \left[ x < Sy \leftrightarrow \left( x < y \lor x = y \right) \right].\\ &11. \left( \forall x \right) \left( \forall y \right) \left[ \left( x < y \right) \lor \left( x = y \right) \lor \left( y < x \right) \right]. \end{align}$$

Exercises

1. You have already seen that $N$ is not strong enough to prove the commutative law of addition (Exercise 8 in Section 2.8). Use this to show that $N$ is not complete by showing that
   $$N \nvdash \left( \forall x \right) \left( \forall y \right) x + y = y + x$$
   and
   $$N \nvdash \neg \left[ \left( \forall x \right) \left( \forall y \right) x + y = y + x \right].$$
2. Suppose that $\Sigma$ provides an axiomatization of $Th \left( \mathfrak{N} \right)$. Suppose $\sigma$ is a formula such that $N \vdash \sigma$. Show that $\Sigma \vdash \sigma$.
3. Suppose that $\mathfrak{A}$ is a nonstandard model of arithmetic. If $Th \left( \mathfrak{A} \right)$ is the collection of sentences that are true in $\mathfrak{A}$, is $Th \left( \mathfrak{A} \right)$ complete? Does $Th \left( \mathfrak{A} \right)$ provide an axiomatization of $\mathfrak{N}$? Of $\mathfrak{A}$?