27
$\begingroup$

Here is my attempt to prove the Well-Ordering Principle, i.e. that any non-empty subset of $\Bbb N$, the set of natural numbers, has a minimum element.

Proof. Suppose there exists a non-empty subset $S$ of $\Bbb N$ such that $S$ has NO minimum element. Define $A = \left\{n\in \Bbb N : (\forall s\in S)(n \leq s)\right\}$. It is obvious that $1\in A$. Suppose $n\in A$, then for each $s \in S$, there exists $q \in N$ such that $n + q = s$. Since $q \ge 1$, $n+1 \leq s$, for all $s\in S$. By Principle of mathematical induction, $A = \Bbb N$. Take any $s_0 ∈ S$, then $(\forall s\in S)(s_0 \leq s)$. (This contradicts that $S$ has no minimum element).

How do I prove the statement without invoking Mathematical Induction? Also, I read that the proof of Principle of Mathematical Induction makes use of Well-Ordering. Can it be proven independently of Well-Ordering too?

$\endgroup$
1
  • 2
    $\begingroup$ A mistake in your reasoning is that when you say $n\in A$ you might have $n\in S$, in which case $q=0$. Regarding your second question, it all depends on what you take as your axioms. $\endgroup$ Commented Jun 29, 2013 at 12:00

4 Answers 4

59
$\begingroup$

In a version of the natural numbers $\mathbb{N}$ where each number besides zero has a (unique) predecessor, such as the von Neumann ordinals, or any other model of the Peano Axioms (including the induction axiom), we have the following:

Induction implies well-ordering:

Suppose $S$ has no minimal element. Then $ n = 0 \notin S$, because otherwise $n$ would be minimal. Similarly $n = 1 \notin S$, because then $1$ would be minimal, since $n = 0$ is not in $S$. Suppose none of $0, 1, 2, \cdots, n$ is in $S$. Then $n+1 \notin S$, because otherwise it would be minimal. Then by induction $S%$ is empty, a contradiction.

Well ordering implies induction:

Suppose $P(0)$ is true, and $P(n+1)$ is true whenever $P(n)$ is true. If $P(k)$ is not true for all integers, then let $S$ be the non-empty set of $k$ for which $P(k)$ is not true. By well-ordering $S$ has a least element, which cannot be $k = 0$. But then $P(k-1)$ is true, and so $P(k)$ is true, a contradiction.

$\endgroup$
10
  • 2
    $\begingroup$ What would P(k) be in this case? The fact that S has a minimal element? $\endgroup$ Commented Oct 13, 2016 at 4:04
  • 5
    $\begingroup$ A problem I have here: how does one define $k-1$ while only using the well-ordering principle? All the proofs I know of that (say) all non-zero natural numbers have predecessors use induction, and I don't see an easy way to turn them into well-ordering proofs without using this construction (which runs into the same problem.) $\endgroup$ Commented Apr 2, 2018 at 18:41
  • 1
    $\begingroup$ @AndrewH.Hunter You are correct, and the proof above is wrong. Induction and well-ordering is not equivalent. $\endgroup$ Commented Nov 6, 2019 at 20:29
  • 8
    $\begingroup$ A reference: link.springer.com/content/pdf/10.1007%2Fs00283-019-09898-4.pdf $\endgroup$ Commented Nov 6, 2019 at 20:52
  • 1
    $\begingroup$ @Per that's a very nice paper, but I take it to show that it's only in the context of the other Peano axioms that Induction and well-ordering are not equivalent. There are other ways to define the integers, and the question of the equivalence of induction and well-ordering depends on which definition you use. (And OP never made it clear what definition was intended.) $\endgroup$ Commented Feb 23, 2020 at 1:42
11
$\begingroup$

The principle of mathematical induction is equivalent to the priciniple of strong induction and both are equivalent to the well-ordering principle. At least if we assume the natural numbers are a structure which satisfies some basic axioms.

This means that if we assume one, we have the other. Of course if we assume a much stronger system of axioms, or have a much larger universe which can meaningfully make statements about the natural numbers, then we can prove each of them from those axioms, but their equivalence would remain.

Indeed this equivalence is one of the most fundamental things in modern mathematics: something is well-ordered if and only if we can perform an induction over it. This is why we often prove one from the other, and vice versa.

$\endgroup$
3
$\begingroup$

Well ordering principle is equivalent to PMI.

We shall first prove that PMI $\implies$ WOP using strong induction. $P(n)$ Every subset of $\mathbb{N}$ containing n has a least element

Base: $1$ is certainly the least element of any subset of N containing $1$. Thus P(1) is true.

Induction: Consider any set S containing $k + 1$.

If S contains any element, say m, smaller than $k + 1$, then by strong induction, as $P(m)$ is true, we know that S contains a least element.

If S didn’t contain any element smaller than $k + 1$, then S contains a smallest element, namely $k + 1$. Thus $P(k + 1)$ is true. We shall now show the reverse direction namely WOP$\implies$PMI.

For contradiction, let us assume that there is a property P such that

$P(1)$ is true and whenever $P(k)$ is true, $P(k + 1)$ is also true.

There exists a number m such that $P(m)$ is false.

Let $S=\left \{x\in \mathbb{N}|P(x)\text{ is false} \right \}$.

Since $m\in S$, S is a non empty subset of N and thus has a least element say s.

$s\neq 1$ because $P(1)$ is true. Since s is the least element of S, $s − 1 \notin S$ .

$P(s−1)$ is true. But then $P((s −1)+1)$ must also be true and thus $s \notin S$

$\endgroup$
2
  • 2
    $\begingroup$ Please consider formatting your question. $\endgroup$
    – Pragabhava
    Commented Sep 14, 2016 at 14:29
  • 1
    $\begingroup$ How do you define s-1 ? $\endgroup$ Commented Nov 6, 2019 at 20:29
1
$\begingroup$

Well ordering principle $\implies $ principle of mathematical induction

Proof: Let, $P(n) $ be a proposition valid for all $n\in \Bbb{N}$.

Suppose, $P(1) $ holds and $P(n) $holds implies $P(n+1) $ holds.

To show : $P(n) $ holds for all $n\in \Bbb{N}$.

Let, $A=\{ n\in \Bbb{N} : P(n) \text { doesn't holds } \}$

If $A\neq \emptyset$ , then by well ordering principle, $A$ has a least element, say $a$.

Then, for any $a-1<a$ , $P(a-1) $ holds.

But this contradict the hypothesis that $P(n) \implies P(n+1) $ holds.

Hence, $A=\emptyset$ . Thus $P(n)$ holds for all $n\in \Bbb{N}$.

principle of mathematical induction$\implies $ Well ordering principle .

Suppose ,$A\subset \Bbb{N}$ has no least element.

Claim $A=\emptyset$ or $A^c (\Bbb{N}\setminus A) =\Bbb{N}$

$P(n) : n\in \Bbb{N}\text{ such that } n\in A^c$

Then, $1\in A^c$ otherwise it would be the least element of $A$.

Suppose, $n\in A^c$ .

Since $n\notin A$ and all predecessors of $n\notin A$ implies $n+1\notin A$ .

Hence, $n\in A^c \implies n+1\in A^c$ .

Hence,by principle of mathematical induction, $P(n) $ is true for all $n\in \Bbb{N}$ and thus $A^c=\Bbb{N}$ .

So, $A=\emptyset$ and hence every non empty subsets of $\Bbb{N}$ has least element.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .