Addition of natural numbers is the most basic arithmetic operation. Here we will define it from Peano's axioms (see natural number) and prove some simple properties. The set of natural numbers will be denoted by N, and "0" will be used to denote the natural number which is not the successor of any other natural number.

Contents

1 Notation and terms 1.1 The definition 2 The properties 2.1 Proof of associativity 2.2 Proof of commutativity 2.3 Proof of identity element

Notation and terms

The operation of addition, commonly written as the infix operator "+", is a function + : N × N → N. For natural numbers a, b, and c, we write

a + b = c

Here, a is the augend, b is the addend, and c is the sum.

We let S(a) denote the successor of a as defined in the Peano postulates.

The definition

Addition is defined inductively by fixing the augend. In other words, we let a be any arbitrary, but fixed natural number, and we then make the following definitions:

• a + 0 = a [A1]
• a + (S(b)) = S(a + b) [A2]

By the recursion theorem, this defines a unique function "a +" : N → N. In words, it says that adding zero to a gives back a, and that applying the successor function to the addend has the effect of applying the successor function to the sum.

Since a was an arbitrary natural number, we can "put together" all these functions into a single binary operation N × N → N.

The properties

The following are two immediate and important properties of addition which can be deduced from the definition.

• Associativity: for all natural numbers a, b, and c, we have (a + b) + c = a + (b + c);
• Commutativity: for all natural numbers a and b, we have a + b = b + a;
• Identity element: for all natural numbers a, we have a + 0 = 0 + a = a

Together, these three properties show that the set of natural numbers N under addition is a commutative monoid.

It is useful to define another natural number closely related to the successor function, namely "1". We define 1 to be the successor of 0, in other words,

1 := S(0)

Note that for all natural numbers a,

S(a)

= S(a + 0) [by A1]

= a + S(0) [by A2]

= a + 1.

Proof of associativity

We prove associativity by first fixing natural numbers a and b and applying induction on the natural number c.

For the base case c = 0,

(a + b) + 0 = a + b = a + (b + 0)

Each equation follows by definition [A1]; the first with a + b, the second with b.

Now, for the induction. We assume the induction hypothesis, namely we assume that for some natural number c,

(a + b) + c = a + (b + c)

Then it follows,

(a + b) + S(c)

= S((a + b) + c) [by A2]

= S(a + (b + c)) [by the induction hypothesis]

= a + S(b + c) [by A2]

= a + (b + S(c)) [by A2]

In other words, the induction hypothesis holds for S(c). Therefore, the induction on c is complete.

Proof of commutativity

We prove commutativity by applying induction on the natural number b. First we prove the base cases b = 0 and b = S(0) = 1 (i.e. we prove that 0 and 1 commute with everything).

For the base case b = 0, we must show that 0 commutes with everything, i.e. for all natural numbers a, we have a + 0 = 0 + a. We prove this by induction on a (an induction proof within an induction proof). Clearly, the statement is true for a = 0, so assume that it holds for an arbitrary natural number a. Then

S(a) + 0

= S(a) [by A1]

= S(a + 0) [by A1]

= S(0 + a) [by the induction hypothesis]

= 0 + S(a) [by A2]

This completes the induction on a, so we have proved the base case b = 0. Next we will prove the base case b = 1, that 1 commutes with everything, i.e. for all natural numbers a, we have a + 1 = 1 + a. We will prove this by induction on a (another induction proof within an induction proof). Clearly, for a = 0, we have 0 + 1 = 0 + S(0) = S(0 + 0) = S(0) = 1 = 1 + 0. Now, suppose a + 1 = 1 + a. Then

S(a) + 1

= S(a) + S(0)

= S(S(a) + 0) [by A2]

= S((a + 1) + 0)

= S(a + 1) [by A1]

= S(1 + a) [by the induction hypothesis]

= 1 + S(a) [by A2]

This completes the induction on a, and so we have proved the base case b = 1. Now, suppose that for all natural numbers a, we have a + b = b + a. We must show that for all natural numbers a, we have a + S(b) = S(b) + a. We have

a + S(b)

= a + (b + 1)

= (a + b) + 1 [by associativity]

= (b + a) + 1 [by the induction hypothesis]

= b + (a + 1) [by associativity]

= b + (1 + a) [by the base case b = 1]

= (b + 1) + a [by associativity]

= S(b) + a

Proof of identity element

This follows immediately from definition [A1] and the commutativity of addition.