Well Ordering Principle and Principle of Mathemtical Induction

the Well-ordering principle states that every nonempty subset of natural numbers has a smallest element.

The principle of mathematical induction (PMI) states that given a sequence of claims such that the first claim is true and for any $n$ if the $n$ th claim is true then the $n+1$ th claim is true, then all the claims are true.

It is well known that these two principles are logically equivalent.

Suppose the WOP is true. Let $C$ be a sequence of claims such that $C_1$ is true and $C_n$ is true implies $C_{n+1}$ is true. Let $S$ be the set of all natural numbers $m$ for which $C_m$ is false. If $S$ is nonempty, then by the WOP it has a smallest element $h$ . Then $C_h$ is false and $C_{h-1}$ is true. But by the chain logic, $C_h$ is true implying that $h$ is not an element of $S$ , a contradiction. Hence $S$ is empty, that is every claim $C_n$ is true.

Conversely, suppose PMI is true. Let $C$ be the sequence of claims $C_n$ is “if $\exists k \in S : k \le n$ then $S$ has a smallest element. Clearly, $C_1$ is true, since $1$ is the smallest natural number. Let $C_n$ be true. Suppose there is $k \in S$ such that $k \le n+1$ . If $k \le n$ then $S$ contains a smallest element. If $k = n+1$ , either $S$ contains no elements $h\le n$ , in which case $n+1$ is the smallest element of $S$ , or it contains $h \le n$ in which case it has a smallest element. Hence by PMI the sequence $C$ are all true claims. Now, if $S$ is a nonempty set it contains some natural number $n$ and since $C_n$ is true, $S$ has a smallest element

Navigation

About

Raedwulf ….