Addition on Natural Numbers

Addition on Natural Numbers

We will define addition recursively. But before we are able to do it, we must prove that recursive definition makes sense. First, we remind the readers of the recursive definition in the case of the Fibonacci Sequence: $a_0, a_1, a_2, ...$.

$$a_0 = a_1 := 1$$
$$a_n = a_{n-1} + a_{n-2}$$
We can see that the recursive definition starts with some initial value. Then the element $a_n$ is defined as some some function $f$ of the previous values.

In this section, we are only concerned with one simple type of recursive definition. That is

Definition 1.2.1 (Recursive definition) The sequence $a_0, a_1, a_2, ...$ are defined recursively as follows

• $a_0 = c \in \mathbb{N}$
• $a_{n+1} = f_{n}(a_n)$

for $f_n$ is some function $\mathbb{N} \to \mathbb{N}$.

Note that the functions $f_0, f_1, f_2, ...$ can be the same or different. The instance that these functions are different is something like

$$a_{n+1} = f_{n}(a_n) = (a_n)^n$$

So $f_0(x) = 1, f_1(x) = x, f_2(x) = x^2, ...$ are all different functions.

We can see why definition 1.2.1 will not make sense for some weird number system that loops back.

In this situation, we see that $a_1$ is effectively defined twice: once as $a_1 = f_0(a_0)$ and as $a_1 = f_3(a_3)$. This is because $1$ is the successor of both $0$ and $3$ in this weird system, leading to duplicate definitions.

We will use induction to prove the validity of recursive definition 1.2.1. Induct on $n$. When $n=0$, we can see that $a_0$ is defined exactly once because $0$ has no predecessor (axiom 3). Now, if we assume that $a_n$ is defined once, then $a_{n+1} = f_n(a_n)$ is also defined once. This is because the predecessor of $n++$ is the unique $n$ by the unique predecessor axiom 4.

We are now ready to define addition.

Definition 1.2.2 (Addition of two natural numbers)
$m + n$ is defined as the value of $a_n$ in the sequence $A = a_0, a_1, a_2, ..., a_{n-1}, a_n$. The sequence $A$ is defined recursively
$$a_0 = m$$
$$a_n = f_{n-1}(a_{n-1}) = (a_{n-1}) ++$$
In other words,
$$ m + 0 : = m$$
$$m + (n++) := (m + n)++$$
with $m, n \in \mathbb{N}$
For example, $2 + 3$ is incrementing $2$ three times. $2 + 3 = (((2++)++)++)$.

Property 1 (Additive group closure)

Sum of two natural numbers are again a natural number.
Proof
With $m, n \in \mathbb{N}$, we will prove that $m + n\in \mathbb{N}$ by induction axiom 5 on $n$. For the base case $n = 0$, we know by the definition of addition that $n + 0 = n \in \mathbb{N}$.

Now, assume that the statement is proven for $n$. We will demonstrate that it also holds for $n++$. By recursive definition,

$m + (n ++) := (m + n)++$

Because by the inductive hypothesis $(m+n) = k$ is a natural number, $k++$ is also a natural number by increment axiom 2.


From definition 1.2.2, however, it is not clear that addition is commutative.

$$n + m = m + n$$

We will now prove a series of remarks by induction leading to the proof that addition is commutative.

Property 2 (Additive group identity)

$ 0 + m = m$
ProofNote that definition 1.2.2 states that $m + 0 := m$ and we have not proven addition to be commutative. Thus, $0 + m$ are not necessarily the same as $m + 0$. Note that the very definition of the natural number $m$ is defined recursively in axiom 2 that

$$m := \underbrace{(((0 ++) ++)... +++)}_{\text{$m$ times}} $$

So we can easily prove this remark by induction on $m$. For the base case $m = 0$, by definition 1.2.2, $n + 0 = n = 0 = m$. So the claim that $0 + m = m$ is true.

Now suppose that the claim is proven for $m$, we will prove it extends to $m++$. By definition 1.2.2,

$$0 + (m++) := (0 + m) ++$$

By the induction hypothesis,

$$(0 + m) ++ = (m) ++ $$

Therefore,

$$0+(m++)=(m)++$$

This proves the claim.

Remark $ (m++) + n = (m + n) ++$ 

Proof

We will again use induction on $n$. For $n = 0$, by definition 1.2.2, $(m++) + 0 := m++$, and $(m+0)++ = (m)++$ as proven by the group identity property above.

Now, assume the claim is true for $n$, that is 

$$ (m++) + n = (m + n) ++$$,

we will prove the claim for $n++$. That is we want to demonstrate that

$$(m++) + (n++) = (m+(n++))++$$

By definition 1.2.2,,

$$(m++) + (n++) := ((m++) + n)++$$

By the induction hypothesis,

$$= ((m+n)++)++$$.

Turning to the right hand side. Now using definition 1.2.2 again,

$$(m+(n++))++ := ((m+n)++)++$$

Obviously by the increment axiom 2, if $a = b$, then $a++ = b++$ (from now on, we will refrain from explicitly invoking axiom 2).

This completes our claim.

Property 3 (Addition is commutative) $n + m = m + n$

Proof
We will induct on $m$. For the base case $m = 0$, we already show in group identity property that $ 0 + n = n$. By definition \ref{def:3}, we also know that $n + 0 := n$ so the claim is proven for the base case.

Now, assume the claim is true for $m$, we extend it to $m++$. That is we want to demonstrate that

$$n+(m++) = (m++) + n$$

By definition 1.2.2,

$$n+(m++) := (n+m)++$$

By the proven remark, we also have

$$(m++)+n = (m+n)++$$

And by the induction hypothesis, we have

$$n+m = m +n$$

Thus, we conclude that

$$n+(m++) = (m++)+n$$

and addition is commutative.



Property 4 (Addition is associative) $a+(b+c) = (a+b)+c$

Proof We will prove the claim by inducting on $c$. For $c=0$, We know that $b+ 0 := b$, so it is certainly true that

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

By the group identity,

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

Thus, the claim is proven for base case. Now we assume that the claim is proven for a given $c$ i.e.

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









Now, we need to show that



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




By the definition of addition, the equation is equivalent to

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

$$\iff (a+(b+c))++ = ((a+b)+c)++ $$

We know that by the induction hypothesis,

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

Thus, by the unique successor implication of axiom 4

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

This concludes our induction.