View source for Proofs involving the addition of natural numbers

{{Short description|Mathematical proofs of basic properties of addition of the natural numbers}}
[[File:Inductive proofs of properties of add, mult from recursive definitions svg.svg|thumb|400px|Basic arithmetic properties (zoom in for induction proofs)]]
This article contains [[Mathematical proof|mathematical proof]]s for some properties of [[Addition|addition]] of the natural numbers: the additive identity, commutativity, and associativity. These proofs are used in the article Addition of natural numbers.

==Definitions==
This article will use the [[Peano axioms]] for the definition of natural numbers. With these axioms, ''addition'' is defined from the constant 0 and the [[Successor function|successor function]] S(a) by the two rules

{|
|-
| '''A1:''' || ''a'' + 0 = ''a''
|-
| '''A2:''' || ''a'' + S(''b'') = S(''a'' + ''b'')
|}

For the proof of commutativity, it is useful to give the name "1" to the successor of 0; that is,
:1 = S(0).

For every natural number ''a'', one has

{|
|-
| || S(''a'') 
|-
| = || S(''a'' + 0) || [by A1]
|-
| = || ''a'' + S(0) || [by A2]
|-
| = || ''a'' + 1 || [by Def. of 1]
|}

== Proof of associativity ==

We prove associativity by first fixing natural numbers ''a'' and ''b'' and applying [[Mathematical induction|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 identity element ==

Definition [A1] states directly that 0 is a right identity.
We prove that 0 is a left identity by induction on the natural number ''a''.

For the base case ''a'' = 0, 0 + 0 = 0 by definition [A1].
Now we assume the induction hypothesis, that 0 + ''a'' = ''a''.
Then
{|
|-
| || 0 + ''S''(''a'')
|-
| = || ''S''(0 + ''a'') || [by A2]
|-
| = || ''S''(''a'') || [by the induction hypothesis]
|}
This completes the induction on ''a''.

== Proof of commutativity ==

We prove commutativity (''a'' + ''b'' = ''b'' + ''a'') 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).

The base case ''b'' = 0 follows immediately from the identity element property (0 is an additive identity), which has been proved above:
''a'' + 0 = ''a'' = 0 + ''a''.

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'' (an induction proof within an induction proof). We have proved that 0 commutes with everything, so in particular, 0 commutes with 1: for ''a'' = 0, we have 0 + 1 = 1 + 0. Now, suppose ''a'' + 1 = 1 + ''a''. Then

{|
|-
| || ''S''(''a'') + 1
|-
| = || ''S''(''a'') + ''S''(0) || [by Def. of 1]
|-
| = || ''S''(''S''(''a'') + 0) || [by A2]
|-
| = || ''S''((''a'' + 1) + 0) || [as shown above]
|-
| = || ''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) || [as shown above]
|-
| = || (''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'' || [as shown above]
|}

This completes the induction on ''b''.

== See also==
*[[Binary operation]]
*Proof
*Ring

== References ==
<references/>
*[[Biography:Edmund Landau|Edmund Landau]], Foundations of Analysis, Chelsea Pub Co. {{ISBN|0-8218-2693-X}}.

{{DEFAULTSORT:Addition Of Natural Numbers/Proofs}}
[[Category:Abstract algebra]]
[[Category:Elementary algebra]]

{{Sourceattribution|Proofs involving the addition of natural numbers}}