16
$\begingroup$

Here is my attempt to prove the Well-ordering principle, i.e. 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?

Thank you.

$\endgroup$
  • 1
    $\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$ – Edvard Fagerholm Jun 29 '13 at 12:00
40
$\begingroup$

Induction implies well-ordering:

Suppose $S$ has no minimal element. Then $ n = 1 \notin S$, because otherwise $n$ would be minimal. Similarly $n = 2 \notin S$, because then $2$ would be minimal, since $n = 1$ is not in $S$. Suppose none of $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(1)$ 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 = 1$. But then $P(k-1)$ is true, and so $P(k)$ is true, a contradiction.

$\endgroup$
  • 1
    $\begingroup$ What would P(k) be in this case? The fact that S has a minimal element? $\endgroup$ – Kenneth Worden Oct 13 '16 at 4:04
  • $\begingroup$ I think just any property which has the inductive property ($P(1)$ and $P(i) \implies P(i+1)$). Recall that induction is [equivalent to] if the inductive property holds, it is true for the every number in the naturals. $\endgroup$ – mdave16 Mar 20 '17 at 21:58
  • 1
    $\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$ – Andrew H. Hunter Apr 2 '18 at 18:41
8
$\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$
2
$\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$
  • 1
    $\begingroup$ Please consider formatting your question. $\endgroup$ – Pragabhava Sep 14 '16 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.