Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Principle of Induction and Principle of Well-Ordering

  1. Jan 24, 2010 #1
    Can anyone prove that the Principle of Induction is a consequence of the Principle of Well-Ordering?

    How bout that the Principle of Well-Ordering is a consequence of the Principle of Induction?
  2. jcsd
  3. Jan 25, 2010 #2
    Assuming that you are referring to finite induction (that is, applied to [tex]\mathbb N[/tex] and its subsets) and the strongest form of the induction principle for this case:

    Given a nonempty set [tex]X\subseteq \mathbb N[/tex], then:

    [tex]0 \in X \wedge \forall n \in \mathbb N\left(n \in X \rightarrow n+1 \in X\right)\rightarrow X=\mathbb N[/tex]

    Then, as the usual ordering relation in [tex]\mathbb N[/tex] is a well-order implies the induction principle for, suppose [tex]X\neq \emptyset[/tex], [tex]X \subset \mathbb N[/tex] (with strict inclusion), then its complement [tex]X' = \mathbb N / X[/tex] is also nonempty and, by the well-ordering principle, has a minimum element, say [tex]a \in X'[/tex]. But [tex] a \neq 0[/tex], so [tex]a-1 \in X[/tex]; but then, [tex]a=\left(a-1\right)+1 \in X[/tex], which is a contradiction. Therefore, [tex]X = \mathbb N[/tex].

    As for the reciprocal, the exact statement is: if a totally ordered set satisfies the induction principle (finite or transfinite), then it must be well-ordered.
    In the case of [tex]\mathbb N[/tex], it suffices to prove that the usual ordering is also a well-order. Let [tex]X \subseteq \mathbb N[/tex], [tex]X \neq \emptyset[/tex]; then we have:

    (1)[tex]0 \in X[/tex]. Then we are done: 0 is the minimum element of X.

    (2)Otherwise, as 0 belongs to the complement of X, applying the induction principle to it, then either [tex]X' = \mathbb N[/tex], which means that X is empty, or

    [tex]\forall n \in \mathbb N\left(n \in X' \rightarrow n+1 \in X'\right)[/tex]

    is false. Therefore, there must be an [tex]n[/tex], such that [tex]n+1 \notin X'\Leftrightarrow n+1 \in X[/tex] and this implies that either that n+1 is the minimum element of X, or that we have to check, at most, a finite number of cases [tex]\left\{0,...,n+1\right\}[/tex] to find it.

    These statements carry to the transfinite case (in fact, it can be proved that [tex]\mathbb N[/tex] is well-ordered without induction and a little set theory, as this set is the smallest transitive one), where the proofs are basically the same, but they require a knowledge of ordinals (the main difference is that there are two distinct types of infinite ordinals).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook