                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

1 Arithmetic I

1.1 First-order Arithmetic

Let ω be the structure (ω, +, ×, 0, 1), where ω is the set of non-negative integers. First-order Arithmetic is Th(ω), the set of first-order statements in the language {+, ×, 0, 1} which are true in ω. Much of the fascination of working with first-order number theory comes from the simple fact that there are so many assertions P, including unsolved problems, in number theory for which one can routinely exhibit a specific first-order φ such that the assertion P is true iff ω ⊧ φ. We say that such assertions can be expressed in first-order arithmetic.

This contrasts sharply with Presburger Arithmetic, i.e., the first-order theory of (Z, +, 0, 1, <), or the first-order theory for the calculus of classes, i.e., the first-order theory of all structures (P (U), ∪, ∩,′ , 0, 1). For these two examples there are no known unsettled assertions in mathematics for which one can find such a corresponding first-order φ.

In this section we look at the basic ideas for translating number-theoretic assertions into first-order arithmetic. The starting point is to express some well known relations by first-order formulas.

DEFINITION 1 For n ∈ ω we define the term n̄ by: ¯0 = 0, \overline{n + 1} = n̄+1.

n̄ is an obvious choice for a term to represent the number n.

DEFINITION 2 A relation r ⊆ ω^{n} is definable on ω if there is a formula φ(x_{1}, …, x_{n}) such that r = φω, i.e.,

(k_{1}, …, k_{n}) ∈ r  iff  ω ⊧ φ(k̄_{1}, …, k̄_{n}).

Now we look at a few definable relations:

Relation  Defining Formula
x ≤ y ∃z (x + z ≈ y)
x < y x ≉ y ∧ x ≤ y
x|y ∃z (xz ≈ y)
x ≡ y mod z ∃u [(u + x ≈ y ∨ y + u ≈ x) ∧ z|u]
prime(x) (x ≉ 1) ∧ ∀y (y|x ⟹ y ≈ 1 ∨ y ≈ x)
coprime(x, y) ∀u (u|x ∧ u|y ⟹ u ≈ 1)

With just these formulas we can express important results, for Euclid’s theorem on the infinitude of primes is given by

∀x∃y x < y ∧ prime (y);

and Dirichlet’s theorem about the infinitude of primes in an arithmetical progression an + b, when a and b are relatively prime, is expressed by

∀u∀v coprime(u, v) ⟹ ∀x∃y [x < y ∧ prime (uy + v)].

And one can express Goldbach’s Twin Prime conjecture by

∀x∃y x < y ∧ prime(y) ∧ prime(y + ¯2).

Many of the results and problems in number theory deal with the exponential function x^{y}. If we had given ourselves this function as a fundamental operation of ω then we could easily express Fermat’s Last Theorem by

∀x∀y∀z∀w [x^{w} + y^{w} ≈ z^{w} ⟹ w < ¯3 ∨ xy ≈ 0].

However we do not have this simple situation. Nonetheless we are able to work with a wide class of functions in first-order number theory by defining their graphs.

DEFINITION 3 A function f : ω^{n} ⟹ ω is definable in first-order arithmetic if there is a formula φ(x_{1}, …, x_{n}, y) such that f(k⃗) = m iff φω(k̄_{1}, …, k̄_{n}, m̄) holds in ω.

Now, if we could define the exponential function, say by φ_{↑}(x, y, z), then we could express Fermat’s Last Theorem by

∀x∀y∀z∀w∀u∀v φ_{↑}(x, w, u) ∧ φ_{↑}(y, w, v) ∧ φ_{↑}(z, w, u + v) ⟹ w < ¯3 ∨ xy ≈ 0.

So let us find a way to define exponentiation. The obvious approach is to use recursion (as Dedekind did): a^{0} = 1 and a^{n+1} = a^{n}a. To compute a^{n} directly from such a definition we would compute the sequence a^{0}, a^{1}, …, a^{n}. However this does not appear to be expressible in first-order form.

For the moment suppose there is a definable function s : ω^{2} ⟹ ω, defined by φ_{s}(x, y, z), such that for each finite sequence a_{0}, …, a_{n} there is a b such that s(b, 0) = a_{0}, …, s(b, n) = a_{n}. Then we could use φ_{s} to define exponentiation in first-order arithmetic using the following formula φ_{↑}(x, y, z):

∃u [φ_{s}(u, ¯0, ¯1) ∧ ∀v∀w (v < y ∧ φ_{s}(u, v, w) ⟹ φ_{s}(u, v + ¯1, wx)) ∧ φ_{s}(u, y, z)] .

A beautiful observation of Gödel in his 1931 paper was the fact that one could find such a formula — however it was simpler to define a certain function of three variables, called Gödel’s beta function, given by

β(x, y, z) = rem (1 + (z + 1)y, x),

where rem (x, y) is the remainder after dividing y by x. Clearly β is defined by the following formula φ_{β}(x, y, z, w):

∃w [w ≡ x mod 1 + (z + 1)y ∧ w < 1 + (z + 1)y].

The following lemma says that for any finite sequence a_{0}, …, a_{n} from ω there are numbers b and c from ω such that a_{i} is the result of reducing b modulo 1 + (i + 1)c.

LEMMA 4 Given any finite sequence a_{0}, …, a_{n} ∈ ω there are b, c ∈ ω such that β(b, c, i) = a_{i} for 0 ≤ i ≤ n.

Proof. Let c = max(n, a_{0}, …, a_{n})! and let u_{i} = 1 + (i + 1)c for 0 ≤ i ≤ n. Then for p a prime we have p|u_{i} ⟹ p |̸c, and thus for 0 ≤ i < j ≤ n we have

p|u_{i} & p|u_{j} ⟹ p|u_{i} − u_{j}
⟹ p|(i − j)c
⟹ p|i − j.

But i − j|c, so p|c, which is impossible. Thus the u_{i} are pairwise coprime. Consequently by the Chinese remainder theorem one can find an integer b (< u_{0} ⋯ u_{n}) such that b ≡ a_{i} mod u_{i}; and since a_{i} < u_{i} we have rem (u_{i}, b) = a_{i}.

So now a slight modification of our attempt (using φ_{s}) at defining exponentiation succeeds, and we can write a a simple sentence φ_{F LT} which holds in ω iff Fermat’s Last Theorem is true.

Exercises Let DEF be the class of functions definable on ω (we include the constants as nullary functions).

Problem 1 Show that DEF is closed under composition, i.e., if f : ω^{n} ⟹ ω and g_{i} : ω^{k} ⟹ ω are in DEF, 1 ≤ i ≤ n, then f(g_{1}, …, g_{n}) : ω^{k} ⟹ ω is in DEF.

Problem 2 Show that DEF is closed under primitive recursion, i.e., suppose n > 0 and g : ω^{n−1} ⟹ ω and h : ω^{n+1} ⟹ ω are in DEF. Then f : ω^{n} ⟹ ω given by

f(x_{1}, …, x_{n−1}, 0) = g(x_{1}, …, x_{n−1})
f(x_{1}, …, x_{n−1}, x_{n} + 1) = h(x_{1}, …, x_{n}, f(x_{1}, …, x_{n}))

is also in DEF^{1}.

1.2 Peano Arithmetic

Based on the work of Dedekind and Peano one can give a relatively simple set of first-order axioms, called PA, for the natural numbers^{2} from which one can prove all standard theorems of number theory which can be formulated as first-order statements.

1Note that we obtain exponentiation by using g = 1 and h(x_{1}, x_{2}) = x_{1} · x_{2}.

2Although Dedekind, Peano, and Landau were interested in axiomatizing positive integers (natural numbers), the standard now is to work with the nonnegative integers.

Peano Arithmetic

• The language is {+, ×, 0, 1}

• The AXIOMS are

\begin{matrix}∀x & x + 1 ≉ 0 \\ ∀x∀y & x + 1 ≈ y + 1 ⟹ x ≈ y \\ ∀x & x + 0 ≈ x \\ ∀x∀y & x + (y + 1) ≈ (x + y) + 1 \\ ∀x & x × 0 ≈ 0 \\ ∀x∀y & x × (y + 1) ≈ (x × y) + x \end{matrix}

and for each first-order formula φ(x, y⃗) the first-order induction axiom

∀y⃗ ([φ(0, y⃗) ∧ ∀z(φ(z, y⃗) ⟹ φ(z + 1, y⃗)] ⟹ ∀xφ(x, y⃗))

The standard model of PA is (ω, +, ×, 0, 1), where the operations are the usual ones. In Example V.14.3 of LMCS we saw that there are other countable models of PA. And once we have developed a derivation calculus then it is possible to return to the sentences φ in §1 which expressed important assertions and try to prove them by seeing if we can show PA ⊢ φ. This method cannot work all the time by Gödel’s incompleteness theorem – and indeed we do not know if PA is strong enough to prove any interesting open problems in number theory.