Well Ordering Principle

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which $x$ precedes $y$ if and only if  $y$ is either $x$ or the sum of $x$ and some positive integer (other orderings include the ordering $2,4,6$; and $1,3,5$).

The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem". On other occasions it is understood to be the proposition that the set of integers $\{…,−2,−1,0,1,2,3,…\}$ contains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element.

Well-ordering Principle: If $S$ is a non-empty set of non-negative integers, then $S$ has a least element, i.e., there is an integer $c \in S$ such that $c \le x$ for all $x \in S$.

The principle of mathematical induction follows directly from well-ordering principle.

(Principle of Induction): Let $S$ be set of positive integers such that

1. $1 \in S$

2. $k \in S \implies  k + 1 \in S$

Then $S$ is the the set $N$ of all natural numbers.

Proof: Consider the complement $S'$ of the set $S$ in $N$:

$$S' = N - S:$$

We want to show that $S'$ is the empty set.Suppose $S'$ is non-empty. Then by wellordering principle it has a least element, say $n'$. Clearly, $n' \ne 1$ as $1 \in S$.Therefore $n' - 1$ is a natural number which is not in $S'$. Hence $n' -1 \in S$. By hypothesis, $n'- 1 \in S \implies n' \in S$. Therefore, $n' \in S \cap S'$, which is a contradiction. Therefore $S'$ must be empty, and $S = N$.

 

Mathematical induction is a powerful proof technique used to prove statements about natural numbers. The principle of mathematical induction can be stated as follows:

Principle of Mathematical Induction: Suppose we have a statement $P(n)$ that we want to prove for all natural numbers $n \geq a$, where $a$ is some fixed natural number. If we can establish two things:

1.Base Case: Prove that the statement holds for the smallest value of $n$, usually $n=a.$
2.Inductive Step: Prove that if the statement holds for some arbitrary $k \geq a$, then it also holds for the next natural number $k+1$.

Then, we can conclude that the statement $P(n)$ is true for all natural numbers $n \geq a$.

Proof by Mathematical Induction:

Let $P(n)$ be the statement that we want to prove for all natural numbers $n \geq a$.

Base Case: Verify that $P(a)$ is true.

Inductive Step: Assume that $P(k)$ is true for some arbitrary natural number $k \geq a$. Then, show that under this assumption, $P(k+1)$ is also true.

Conclusion: By the principle of mathematical induction, $P(n)$ is true for all natural numbers $n \geq a$.

Example:

Let's prove the statement $P(n)$: "The sum of the first $n$ positive integers is given by the formula $\frac{n(n+1)}{2}$ using mathematical induction.

Base Case: When $n = 1$, the sum of the first positive integer is 1, and $\frac{1(1+1)}{2}=1$. So, the formula holds for the base case.

Inductive Step: Assume that the formula holds for some $k \geq 1$, i.e., $P(k)$ is true. That is, the sum of the first $k$ positive integers is $\frac{k(k+1)}{2}$​. Now, we need to show that this implies that $P(k+1)$ is true, i.e., the sum of the first $k+1$ positive integers is $\frac{(k+1)(k+2)}{2}$​.

Starting with $P(k)$, the sum of the first $k$ positive integers: 

$$1 + 2 + 3 + \ldots + k = \frac{k(k+1)}{2}$$

Adding $(k+1)$ to both sides, we get: 

 

$$1+ 2 + 3 + \ldots + k + (k+1) = \frac{k(k+1)}{2} +(k+1)$$
$$= \frac{k(k+1) + 2(k+1)}{2}$$ ​
$$\frac{(k+1)(k+2)}{2}$$

This proves that $P(k+1)$ holds.

 

Conclusion: By the principle of mathematical induction, the formula holds for all natural numbers $n \geq 1$.

This completes the proof by mathematical induction.