Natural Numbers

Table Of Contents

Peano Axioms

We start with axioms to help clarify this.

• Axiom 1 : $0 \in \mathbb{N}$

• Axiom 2: If $n \in \mathbb{N}$,, then $n++ \in \mathbb{N}$

• Axiom 3: 0 is not an increment of any other natural number $n \in \mathbb{N}$

• Axiom 4: If $n \neq m$, $n++ \neq m++$

• Axiom 5: (Principle Of Mathematical Induction) Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n++)$ is also true. Then $P(n)$ is true for every natural number.

We then make an assumption: That the set $\mathbb{N}$ which satisfies these five axioms is called the set of natural numbers. With these 5 axioms, we can construct sequences

Recursive Definitions

Addition

Proof. We use induction,

The base case, n = 0,

Suppose inductively, that $n+0=n$,

For $n=n++$,

Proof. Inducting on $n$ while keeping $m$ fixed, This we know is true from the definition of addition $(0+m:=m)$

Suppose inductively, that $n+(m++) = (n+m)++$ is true. For $n=(n++)$,

Putting m = 0, we get $n+1 = n++$

Proof. We induct over $n$, For the base case, $n=0$,

We must show that $m+0 = 0+m$ From the definition of addition, we have

$$0+m = m$$

As shown earlier, we have

$$m+0 = m$$

This is clearly true for $n=0$.

Now suppose inductively that $m+n = n+m$

For $n=n++$, we must show that $m+(n++) = (n++) + m$

We know from the definition of addition that,

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

And we proved earlier that,

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

Therefore,

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

Proof. We take $(a+b)+n = a + (b+n)$

Inducting over n,

For $n=0$,

We have in the LHS,

On the RHS,

Suppose inductively that $(a+b)+n = a+(b+n)$,

For $n=n++$, We have to show that $(a+b)+(n++) = a+(b+(n++))$

On the LHS we have,

On the RHS we have,

LHS = RHS

Proof. We have,

$$n+b=n+c$$

Inducting over n, For the base case, $n=0$

Suppose inductively that $n+b=n+c$ For $n=n++$,

$$(n++)+b=(n++)+c$$

On the LHS

On the RHS

We know from the inductive hypothesis that,

$$\text{If} n+b = n+c, \text{then} b = c$$

Thus we have,

$$b++ = c++$$

Proof. Inducting over b,

For $b$ = 0,

This proves the base case, since we know a is positive.

Now, suppose inductively, that $(a+b)$ is positive.

For $(a+(n++))$,

We know from Axiom 3 that $n++ \neq 0$. Thus we close the inductive loop. Proof. Proof by contradiction, Suppose that there are two different increments, $m++$, $n++$ that equal to $a$,

We have,

Then we can say,

But we said that m and n are different numbers which increment to $a$.

Therefore, we can conclude that there is only one number $b$ which increments to $a$

Order

Proof. 1. Proving order is reflexive, $a \geq a$

We know that, $a = a + 0$ From the definition of order, We can write that $a \geq b$ when $a = b + d$ where $d \in \mathbb{N}$ Thus $a \geq a$.

2. Proving order is transitive, $a \geq b$ and $b \geq c$ then $a \geq c$

   We write,

   $$\begin{aligned} a & = b + d \\ b & = c + e \\ a & = c + e + d \end{aligned}$$
   We can say that since $(e+d) \in \mathbb{N}$

   We define $f := (e+d)$ Where $f \in \mathbb{N}$

   $$\begin{aligned} a & = c + (f) \end{aligned}$$

   Thus we can say,

$$\text{If } a \geq b, b \geq c \text{then} a \geq c$$

3. Proving order is antisymmetric, If $a \geq b$ and $b \geq a$ then $a=b$ We can say,

   $$\begin{aligned} a = b + d \\ b = a + e \\ \end{aligned}$$
   Where $d,e \in \mathbb{N}$
   $$\begin{aligned} a = (a + e) + d \\ b = (b + d) + e \\ \end{aligned}$$

   Then we can write,

   $$\begin{aligned} a = a + (e + d) \\ b = b + (d + e) \\ \end{aligned}$$

   Then we can say that $(e+d)$ and $(d+e)$ are 0.

   We know that if $a + b = 0$ then $a,b = 0$

   Thus $d$ and $e$ are 0.

   $$\begin{aligned} a = b + d \\ a = b \end{aligned}$$

4. Proving $a < b$ if and only if $b =a+d$ for some positive number d If $b = a+d$ where $d$ is a positive natural number, $d \neq 0$

   Which means that $b \neq a + 0$ or $b \neq a$

   This means that b is strictly greater than a

   If $a<b$ then $a \geq b$ and $a \neq b$

   So if $a \geq b$ Then,

   $$\begin{aligned} a = b + d \\ \end{aligned}$$
   But,
   $$\begin{aligned} a \neq b \\ a \neq b + 0 \\ d \neq 0 \end{aligned}$$
   Thus d cannot be 0. $d$ can only be a positive natural number.

5. Proving addition preserves order, $a \geq b$ if and only if $a + c \geq b + c$ Proving $a \geq b$ if $a + c \geq b + C$

   Where $d \in \mathbb{N}$

   $$\begin{aligned} a + c & = b + c + d & & \text{By definition} \\ a + c & = (b+d) + c & \\ a & = (b+d) & & \text{By cancellation law} \\ a & \geq b \end{aligned}$$
   Proving $a + c \geq b +c$ if $a \geq b$

   We know,

   $$\begin{aligned} a = b + d \\ \end{aligned}$$
   Where $d \in \mathbb{N}$

   We write a+c using what we know from above,

   $$\begin{aligned} a + c & = b + d + c \\ a + c & = b + c + d \\ (a + c) & = (b + c) + d \\ a + c & \geq b + c \end{aligned}$$

6. Proving $a < b$ if and only if $a++ \leq b$ Proving $a < b$ if $a++ \leq b$

   We can write,

   $$\begin{aligned} a++ & = b + d & \text{Where $d \in \mathbb{N}$} \\ a++ + d & = b \\ a + (d++) & = b \\ \end{aligned}$$
   Since from Axiom 3, we know that 0 is not an increment of any natural number, $(d++ \neq 0)$ Therefore,
   $$\begin{aligned} a & < b \end{aligned}$$

Proof. First we show that no more than one of the statements is true. If $a < b$ then $a \neq b$ by definition. If $a > b$ then $a \neq b$ by definition. If $a > b$ and $a < b$ then $a = b$, which we proved earlier.

Now to show that exactly one of these statements are true. We induct on a,

When a = 0, We know that,

suppose inductively that exactly one of the above statements are true for a and b. for $a++$, we take each statement. first for $a > b$, we have

for $a = b$

for $a < b$, we get,

we have two cases, if $d = 1$, then by cancellation law

$$a++ = b$$

if $d \neq 1$ then

$$a++ < b$$

but never both, which concludes the inductive loop.

Special Forms of Induction

Proof. For a property $Q(n)$, which is the property that $P(m')$ is true for $m_0 \leq m < n$, then $P(n)$ is true...Then it is true $\forall \ m \geq m_0$

For $Q(0)$, we can say that the statement is vacuous since the conditions are not satisfied for both when $m_{0} = 0$ and when $m_{0} <0$

Suppose inductively that $Q(n)$ is true.

Which means that,

P(m) is true for $m_{0} \leq m \leq n$

Then for Q(n++),

We know that the property $P(m)$ is true for $m_{0} \le m \le n$ Take the upper limit of the range,

$$m_0 \leq n$$

We can rewrite this as,

$$m_0 < n++$$

Since $a<b$ if and only if $a++ \leq b$

So we have the property is true for $m_0 \leq m < n++$, the property is true for $P(n++)$, since that is how we chose $Q(n)$

Thus $Q(n++)$ is true, closing the inductive loop.

Since we know that $P(m)$ is true for any $n$ larger than $m$, we can then say that $m \geq m_{0}$

Proof. We can cast this into a standard inductive proof. Consider a property $Q(m)$ defined as $P(n + m)$. Inducting over $m$:
When $m = 0$, which we have taken to be true. Suppose inductively that $Q(m) = P(n + m)$ is true. Then, from the definition of $P(m)$, we know that $P((n + m)++)$ is true.

Multiplication

We can say $0 \times m = 0$, $1 \times m = 0 + m$, $2 \times m= 0 + m + m$ and so on.

Proof. We use the way we proved that addition is commutative as a blueprint. There are two things we need to prove first.

1. For any natural number, $n$, $n \times 0 = 0$

2. For any natural numbers, $n$ and $m$, $n \times (m++) = (n \times m) + m$

First we prove,

1. For any natural number, $n$, $n \times 0 = n$ We induct over $n$, For $n = 0$,

$$0 \times 0 = 0$$

Which is true from the definition Now suppose inductively, that $n \times 0 = 0$, For $(n++) \times 0$, From the definition we can write this as,

Therefore,

$$n \times 0 = n$$

2. For any natural numbers, $n$ and $m$, $n \times (m++) = (n \times m) + m$ We induct over $n$, (keeping $m$ fixed)

   For $n = 0$, We know from the definition for multiplication with zero that,

   $$\begin{aligned} 0 \times (m++) = 0 \\ \text{We also know that} \\ (m++) \times 0 & = (m \times 0 ) + 0 \\ (m++) \times 0 & = 0 \\ (m++) \times 0 = 0 \times (m++) & = (0 \times m) + m \end{aligned}$$

   Suppose inductively that $n \times (m++) = (n \times m) + m$ For $n = (n++)$ To prove $(n++) \times (m++) = ((n++) \times m) + m$,

   $$\begin{aligned} (n++) \times (m++) & = (n \times (m++)) + m++ \\ \text{We can rewrite RHS using the inductive hypothesis} \\ (n++) \times (m++) & = ((n \times m) + m) + m++ \end{aligned}$$
   Taking the LHS, we write
   $$\begin{aligned} (n++) \times (m++) & = (n \times (m++)) + m++ & \text{From the definition} \\ & = (n \times m)+ m) + m++ & \text{From the inductive hypothesis} \\ & = (n \times m)+ m + (m++) & \text{Associativity of addition} \\ & = (n \times m)+ (m++) + m & \text{Commutativity of addition} \end{aligned}$$

   We can say that LHS = RHS, closing the inductive loop

Now we can finally get on with proving that multiplication is commutative, armed with the lemmas we've proved here we can prove this similarly to how we proved addition is commutative We are proving, $m \times n = n \times m$ We fix $m$ and induct over $n$

For $n=0$,

Suppose inductively that $m \times n = n \times m$ is true.

For proving $m \times (n++) = (n++) \times m$, Take the LHS,

Take the RHS, We can see that LHS = RHS, closing the inductive loop

Thus multiplication is commutative

Proof. First we prove if both $n,m$ are both positive, then $nm$ is positive We have, $n$ and $m$ such that $n,m > 0$

Let $a,b \in N$ such that $a++ = m, b++ = n$

Since we know that $m>0$, then $m+d$ where $d \in \mathbb{N}$ is also greater than 0. Thus it's proved.

Now onto proving the first statement, Let $n,m$ be natural numbers, then $n \times m = 0$ if and only if at least one of $n,m$ is equal to zero.

We have to prove it both ways, if $n\times m = 0$ then at least one of $n,m$ is equal to zero.

Proving by contradiction when $nm = 0$ let's assume $n,m \ne 0$ meaning $n,m$ are positive natural numbers.

Proof. We only need to show the first identity, then the other would be implied by commutativity We keep $a$ and $b$ fixed, and induct over c.

For $c = 0$, We have on the LHS,

We have on the RHS, LHS=RHS
This is true for the base case. Now suppose inductively that $a(b+c) = ab + ac$

For $c=(n++)$, We have on the LHS,

We have on the RHS,

Thus, LHS = RHS

Closing the inductive loop.

Proof. We fix $a,b$ and induct over c

For $c=0$, On the LHS,

On the RHS,

This covers the base case, suppose inductively that $(a \times b) \times c = a \times (b \times c)$

For $c = c++$,

We have on the LHS,

We have on the RHS,

From the inductive hypothesis, $(ab)c = a(bc)$, the LHS and the RHS statements are equivalent

Thus we have LHS = RHS

Closing the inductive hypothesis

Proof. If $a > b$, we say that $a = b+d$ where $d$ is a positive natural number.

Multiplying by $c$ on both sides,

We know that $cd$ is a positive natural number, so this is expressed in the form $m = n + d$ which is the same as writing $m > c$

Thus we can write,

$$ac > bc$$

Let $a,b,c$ be natural numbers such that $ac = bc$ and $c$ is non-zero. Then $a = b$

Proof. Let's examine the three cases possible for $a,b$

When $a<b$, then $ac < bc$ from the previous proposition which is a contradiction of the assumption.

When $a>b$, then $ac>bc$ from the previous proposition which is another contradiction of the assumption.

Thus, the only possible case is $a = b$

Proof. Inducting over n,

For $n=0$,

When $a,b \in \mathbb{N}$, $a + b = 0$ if and only if $a=b=0$ We know that,

The converse is easily true, since $a + b = 0$, Thus the base case is true.

Suppose inductively that there exists $m,r \in \mathbb{N}$ such that $0 \leq r < q$ and $n=mq + r$

For $n++$,

We can write,

Now we have two cases to look at here, We know that $0 \le r < q$ from the inductive hypothesis. But for $r++$, that is not necessarily the case, The range of (r++) becomes $0++ \le r++ < q++$ or $1 \le r++ \le q$ since $a<b$ if and only if $a++ \le b$,

When $1 \le r++ < q$, we have closed the inductive loop but there is one more case to look at.

When $r++ = q$ We have,

Thus we have for this case, $r = 0$, which satisfies the condition $0 \le r < q$

Closing the inductive loop.

Thus we can write, $m^0 = 1, m^1 = m^0+m = m, m^2 = m^1 + m = 2m$ and so on

Proof. Take the RHS, We have,

Thus we have LHS = RHS