Natural numbers and induction

Basic number theory deals with the properties of the natural numbers. These are the numbers which count the number of elements of finite sets: 0,1,2,3, .... They can be defined as the smallest inductive set:

Definition 48   The system of natural numbers is defined by giving a designated starting element $0\in \ensuremath{\mathbb{N}}$ and a successor function $s:\ensuremath{\mathbb{N}}\to \ensuremath{\mathbb{N}}$ with the following properties:

1. 0 is not in the image of $s$
2. $s$ is one-to-one
3. If $S\subseteq \ensuremath{\mathbb{N}}$ has $0\in S$ and $n\in S \rightarrow s(n)\in S$ then $S=\ensuremath{\mathbb{N}}$

We can then define functions by recursion, noting that we can specify a subset $D$ of on which we have a well defined value for $f$. If we give $f(0)$ then $0\in D$. If we say how to get $f(s(n))$ from $f(n)$ then we get $n\in D \rightarrow s(n)\in D$. Thus $D=\ensuremath{\mathbb{N}}$.

This method lets us define operations by recursion:

Definition 49   If $a$ is a natural number then we define the function ``add $a$'' by

1. $a+0=a$
2. $a+s(n)=s(a+n)$

Definition 50   If $a$ is a natural number then we define the function ``multiply $a$'' by

1. $a\times 0=0$
2. $a\times s(n)=a+(a\times n)$

With some effort and considerable skill in induction proofs you can then prove that

Theorem 76   The natural numbers form a commutative semiring with unit:

1. Addition is commutative: $a+b=b+a$
2. Addition is associative: $a+(b+c)=(a+b)+c$
3. 0 is an identity element for addition: $a+0=a$
4. Multiplication is commutative: $a\times b=b\times a$
5. Multiplication is associative: $a\times (b\times c)=(a\times b)\times c$
6. $s(0)=1$ is a unit for multiplication: $1\times a=a$
7. Multiplication distributes over addition: $a\times (b+c)=(a\times b)+(a\times c)$

Unlike other theorems in this handout, I am not asking you to prove this.

Theorem 77   The cancellation law holds for addition in : if $n+a=m+a$ then $n=m$.

(5 Points )

Hint: This is an induction proof. $\spadesuit$

Definition 51   The set of positive natural numbers $\ensuremath{\mathbb{N}}^+$ is the image of $s$.

Proposition 78   $\ensuremath{\mathbb{N}}^+$ is closed under both $+$ and $\times$.

(2 Points )

Proposition 79   $\ensuremath{\mathbb{N}}= \ensuremath{\mathbb{N}}^+ \cup \{0\}$

(2 Points )

Definition 52   We say that $n<m$ if there is a positive natural number $p$ with $n+p=m$, we say $n\leq m$ is there is a natural number $k$ (not necessariloy positive) with $n+k=m$

Proposition 80   Whenever $n\leq m$ we have either $n=m$ or $n<m$.

(2 Points )

Proposition 81   There is no natural number $n$ with $0<n<1$.

(4 Points )

Proposition 82   Every nonempty subset of has a least element.

(4 Points )