Definition: Natural Numbers $\N$

The set of all positive integers ${1, 2, 3, …}$ are natural numbers, denoted by $\N$.

Axioms: Peano Axioms (Peano Postulates)

N1. $1$ belongs to $\N$.

N2. If $n$ belongs to $\N$ then its successor $n + 1$ belongs to $\N$.

N3. $1$ is not the successor of any element in $\N$.

N4. If $n$ and $m$ in $\N$ have the same successor, then $n = m$.

N5. (Principal of Induction) A subset of $\N$ which contains $1$, and which contains $n + 1$ whenever it contains $n$, must equal $\N$.

Definition: Proposition

A proposition is a mathematical statement, usually denoted by $P$.

$P(n)$ is a proposition about $n$.

Theorem : Well-Ordering Principle of Natural Numbers

N5’. Every nonempty subset of $\N$ has a minimal element.

Proof by strong induction [expand]

Let $A$ be a non-empty subset of $\N$. Want to know that $A$ has a minimal element, that is, there is an element $a \in A$ such that $a \leq n$ for all $n \in A$. We will do this by strong induction on the following predicate:

$$P(n): \text{If }n \in A\text{, then }A\text{ has a minimal element.}$$

the base case: $P(0)$ is clearly true, since $0 \leq n \forall n \in N$.

the inductive step: Want to show that $[P(0) \land P(1) \land P(2) \land … \land P(n)] \to P(n + 1)$.

To this end, suppose that $P(0), P(1), …, P(n)$ are all true and that $n + 1 \in A$. We consider two cases.

CASE 1: $\neg \exists m (m \in A \land m < n + 1)$

In this case, $n + 1$ is the least element of $A$.

CASE 2: $\exists m (m \in A \land m < n + 1)$

In this case, since $P(m)$ is true, $A$ has a least element.

Either way, we conclude that $P(n + 1)$ is true.

So, by strong mathematical induction, we obtain that $P(n)$ is true for all $n \in N$. Since $A$ is not empty, we can pick an $n \in A$. Moreover, since $P(n)$ is true, this implies that $A$ has a least element.

N1 - N4, N5 $\iff$ N1 - N4, N5’

Corollary

O1. For $a,b \in \N, a \leq b$ or $b \leq a$.

O2. $a \leq b, b \leq a \implies a = b$.

O3. $a \leq b, b \leq c \implies a \leq c$.

Example

Prove that N1 - N4, N5 $\implies$ $\forall x \in X, x \neq 1$ is a successor in $X$.

Proof [expand]

Let $X$ be a subset of $\N$,

Assume that $x \neq 1$ and $x$ not a successor.

Let $X$ be a set of $\set{ 1 } \cup \set{ \text{all successors}} = \N$ by N5.

Then $x \in X , x \neq 1$ is CONTRADICTION; $x$ is a successor.

Definition: Mathematical Induction

Mathematical induction is a mathematical proof technique used to prove that a property $P(n)$ holds for every natural number $n$.

The proof consists of two steps:

1. The base case: prov that the statement holds for the first natural number $n_1$.
2. The inductive step: assume the statement holds for some natural number $n$, and prove that then the statement holds for $n + 1$.

The hypothesis in the inductive step, that the statement holds for some $n$, is called the induction hypothesis or inductive hypothesis.

Example: Mathematical induction

$P(n) = 1 + 3 + 5 + … + 2n - 1 = n^2$

$P(1) = 1 = 1^2$

$P(2) = 1 + 3 = 4 = 2^2$

Assume $P(n)$:

Then $1 + 3 + 5 + … + 2n -1 = n^2$

$1 + 3 + 5 + … + 2n + 1 = n^2 + 2n + 1$

$1 + 3 + 5 + … + (2(n+1) - 1) = (n+1)^2$

So $\P(n) \implies \P(n+1)$.

Definition: Complete Induction (Strong Induction)

Complete induction is a variant of mathematical induction which has a stronger inductive hypothesis. The hypothesis assumes that $P(n)$ holds for all natural $n$ less than or equals to $n$.

The proof still consists of two steps:

1. The base case: prov that the statement holds for the first natural number $n_1$.
2. The inductive step: assume the statement holds for all natural numbers $\leq n$, and prove that then the statement holds for $n + 1$.
Example

Try to prove that $N1 - N4, N5 \iff N1, …, N4, N5’$

Example: Prime factorization

Every $n \in \N$ is a product of primes.

Let $P(n)$: $n$ is a product of primes.

Assume $P(m)$ is product of primes for all $m \leq n$.

For $n + 1$,

if $n+1$ prime, then $n + 1$ is a product of prime.

if $n+1$ not prime (composite), then $n + 1 = a \cdot b$ for some $a, b \in \N$, $a,b > 1$.

$\therefore$ by complete induction

$$a = p_1, p_2, …, p_{ k }$$

$$b = q_1, q_2, …, q_{ l }$$

$\therefore n + 1 = ab = p_1 p_2 … p_{ k } q_1 q_2 … q_{ l }$

$\therefore P(n + 1)$

Note: For $P(1)$, allow $1$ to be a prime.

Example

$P(n): \abs{ \sin(nx)} \leq n \abs{ \sin(x)}$

If $n = 1$, $\abs{ \sin (1 x)} \leq 1 \abs{ \sin x }$

Assume $P(n)$ consider

$\abs{ \sin ((n + 1) x)} = \abs{ \sin nx \cos x + \cos nx \sin x}$

$\abs{ a + b } \leq \abs{ a } + \abs{ b }$(triangle inequality)

$\therefore$

\begin{align*} \abs{ \sin((n+1)x)} &\leq \abs{ \sin nx \cos x } + \abs{ \cos nx \sin x } \br & \leq \abs{ \sin nx } \abs{ \cos x } + \abs{ \cos nx } \abs{ \sin x } \br & \leq \abs{ \sin nx } \cdot 1 + 1 \cdot \abs{ \sin x } \br & \leq n \abs{ \sin x } + \abs{ \sin x } = (n+1) \abs{ \sin x } \end{align*}

$\therefore P(n + 1)$.