Skip to content
Topos Uranos
English

Basic operations on natural numbers and order relations

Summary

This lesson defines addition, multiplication and exponentiation of natural numbers from the successor of the Peano axioms, with the recursion theorem, which guarantees that recursive definitions determine a unique operation; it admits the existence part of that theorem, proves its uniqueness part by induction, and deduces the properties of the operations: commutativity, associativity, distributivity and cancellation. It then defines the order relation by means of addition, with its properties of trichotomy, transitivity and monotonicity, and the inverse operations, subtraction and division, together with the conditions under which they exist. The principle of induction is the instrument of every proof.

Learning objectives

  1. State the recursion theorem and use it to write the recursive definitions of addition, multiplication and exponentiation of natural numbers.
  2. Prove by induction properties of the operations from their definitions.
  3. Define the order of the natural numbers by means of addition and apply its properties of trichotomy, transitivity and monotonicity.
  4. Recognize when the subtraction and the division of two natural numbers exist, and operate with them without leaving the natural numbers.

Addition

The operations on natural numbers have been familiar since school; the aim here is to found them with mathematical precision. In the lesson on the Peano axioms, the natural numbers were defined from 11 and the successor operation, which assigns to each natural number nn the next one, S(n)S(n). Addition is defined from the successor by two rules: adding 11 is taking the successor, and adding the successor of mm is taking the successor of the sum with mm.

n+1=S(n),n+S(m)=S(n+m)n + 1 = S(n), \qquad n + S(m) = S(n + m)

A definition of this kind is called recursive: the first rule fixes the value for 11 and the second reduces each case to the previous one. Now, that two such rules actually define an operation involves two distinct claims: that there exists a function satisfying them for all natural numbers (existence) and that no two different functions satisfy them (uniqueness). Together they form the recursion theorem, due to Dedekind: this course admits the existence part, as explained after the box, and proves the uniqueness part. It is stated in a general form so that it also serves for multiplication, for exponentiation and for the recursive definitions of the following lessons.

Admitted fact (recursion theorem). Let XX be a set and cc an element of XX, and suppose given, for each natural number nn, a rule gng_n that assigns to each element of XX an element of XX. Then there exists a function ff from N\mathbb{N} to XX such that f(1)=cf(1) = c and f(S(n))=gn(f(n))f(S(n)) = g_n(f(n)) for every natural number nn, and that function is unique.

Existence is admitted in this course without proof. Its proof requires constructing the function ff as a set of pairs: the smallest set of pairs that contains (1,c)(1, c) and that, together with each pair (n,x)(n, x), contains (S(n),gn(x))(S(n), g_n(x)); and then verifying, by induction, that to each natural number there corresponds in it a unique second element. That construction belongs to set theory and contributes nothing to the arithmetic that follows. Uniqueness, by contrast, is a direct consequence of the fifth Peano axiom.

LemmaUniqueness of the function defined by recursion

If two functions ff and hh from N\mathbb{N} to XX satisfy the two conditions of the recursion theorem, then they are equal. The figure represents the values of both on the first natural numbers.

Proof

  1. A={n∈N:f(n)=h(n)}\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}

    Let AA be the set of natural numbers at which the two functions coincide. It suffices to prove that AA is the set of all natural numbers.

  2. f(1)=c=h(1)f(1) = \resaltar{c} = h(1)

    The number 11 belongs to AA, because both functions take the value cc at 11.

  3. f(S(k))=gk(f(k))=gk(h(k))=h(S(k))f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))

    If kk belongs to AA, so does S(k)S(k): both functions apply the same rule gkg_k to the same value.

  4. A=N,(∀n∈N) (f(n)=h(n))A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))

    By the fifth Peano axiom, AA is the set of all natural numbers: the two functions are equal.

Addition is obtained from the theorem by fixing the first summand nn and taking X=NX = \mathbb{N}, c=S(n)c = S(n) and, for every mm, the rule gmg_m that assigns to each natural number its successor: the function ff provided by the theorem is the one that assigns to each mm the number n+mn + m, and the two rules of addition are the two conditions of the theorem. In the same way, with c=nc = n and the rule that adds nn, multiplication is obtained, and with c=bc = b and the rule that multiplies by bb, exponentiation. Adding mm amounts, in short, to applying the successor mm times.

ExampleTwo plus two is four

The best-known statement of arithmetic is a theorem that is proved with the two rules of addition and the names 2=S(1)2 = S(1), 3=S(2)3 = S(2) and 4=S(3)4 = S(3).

Proof

  1. 2+2=2+S(1)2 + 2 = 2 + S(1)

    We write the second summand as the successor of 11.

  2. 2+S(1)=S(2+1)2 + S(1) = S(2 + 1)

    By the second rule, adding a successor is taking the successor of the sum.

  3. S(2+1)=S(S(2))S(2 + 1) = S(S(2))

    By the first rule, adding 11 is taking the successor.

  4. S(S(2))=S(3)=4S(S(2)) = S(3) = 4

    Since S(2)=3S(2) = 3 and S(3)=4S(3) = 4, the result follows.

From the rules of addition its properties are deduced by induction. For all natural numbers aa, bb and cc:

  1. Commutativity: a+b=b+aa + b = b + a.
  2. Associativity: (a+b)+c=a+(b+c)(a + b) + c = a + (b + c). That is why a+b+ca + b + c can be written without parentheses.
  3. Cancellation: if a+c=b+ca + c = b + c, then a=ba = b.

Commutativity was proved in solved problem 5 of the lesson on the Peano axioms, and associativity is one of the proposed problems there. Cancellation is proved in solved problem 1 of this lesson.