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
Previous Page Next Page