1.2. The Natural Numbers 11

Example 1.2.5. Using the above definition and Peano’s axioms, prove the asso-

ciative law for addition in N. That is, prove

m + (n + k) = (m + n) + k for all k, n, m ∈ N.

Solution: We fix m and n and, for each k ∈ N, let Pk be the proposition

m +(n + k) = (m + n)+ k. We prove that Pk is true for all k ∈ N by induction on

k.

The base case P1 is just

(1.2.5) m + (n + 1) = (m + n) + 1,

which is the recursion relation (1.2.4) used in the definition of addition once we

replace s(n) with n + 1. Thus, P1 is true by definition.

For the induction step, we assume Pk is true for some k – that is, we assume

m + (n + k) = (m + n) + k.

We then take the successor of both sides of this equation to obtain

(m + (n + k)) + 1 = ((m + n) + k) + 1.

If we use (1.2.5) on both sides of this equation, the result is

m + ((n + k) + 1) = (m + n) + (k + 1).

Using (1.2.5) again, this time on the left side of the equation, leads to

m + (n + (k + 1)) = (m + n) + (k + 1).

Since this is proposition Pk+1, the induction is complete.

Example 1.2.6. Using Definition 1.2.4 and Peano’s axioms, prove that 1+n = n+1

for every n ∈ N.

Solution: Let Pn be the statement 1+ n = n +1. We prove by induction that

Pn is true for every n. It is trivially true in the base case n = 1, since P1 just says

1 + 1 = 1 + 1.

For the induction step, we assume that Pn is true for some n – that is, we

assume 1 + n = n + 1. If we add 1 to both sides of this equation (i.e. take the

successor of both sides), we have

(1 + n) + 1 = (n + 1) + 1.

By Definition 1.2.4, the left side of this equation is equal to 1 + (n + 1). Thus,

1 + (n + 1) = (n + 1) + 1.

Thus, Pn+1 is true if Pn is true and the induction is complete.

A similar induction, this time on m, with n fixed can be used to prove the

commutative law of addition – that is, m + n = n + m for all n, m ∈ N. The base

case for this induction is the statement proved above. The associative law proved

in Example 1.2.5 is needed in the proof of the induction step. We leave the details

to the exercises.

We leave the definition of multiplication in N to the exercises. Its definition

and the fact that it also satisfies the associative and commutative laws follow a