# The well ordering principle

Here is the statement of The Well Ordering Principle: If A is a nonempty set, then there exists a linear ordering of A such that the set is well ordered. In the book, it says that the chief advantage of the well ordering principle is that it enables us to extend the principle of mathematical induction for positive integers to any well ordered set. How to see this? A uncountable set like R can be well ordered by the well ordering principle, so the induction can be applied to a uncountable set like R?

-
en.wikipedia.org/wiki/Transfinite_induction – user641 Mar 27 '11 at 4:07
@Antonio: I think it is a bit misleading to say that "in practice" something that is rather standard in set theory is almost impossible. – Andrés Caicedo Mar 27 '11 at 4:19
@Andres: I think you're talking to me. I meant any of the "usual" properties of the reals that are related to the analytical or algebraic properties of the reals; but yes, you are right, that was somewhat misleading. I'll "fix" it. – Arturo Magidin Mar 27 '11 at 4:21
@Yuan (corrected): See en.wikipedia.org/wiki/Transfinite_induction . Yes, you can do "induction on $\mathbb{R}$", and this is often done in set theory. But it is very hard to use this kind of argument to establish algebraic or analytical properties of $\mathbb{R}$, because the well-orderings that exist on $\mathbb{R}$ have little/nothing to do with the algebraic or analytical structure of $\mathbb{R}$, so there is no reason to expect us to be able to go from "$P(s)$ for all $s\prec r$" to "$P(r)$", when the property $P$ has little to do with the ordering. – Arturo Magidin Mar 27 '11 at 4:23
@Yuan: If you want to deal with the usual properties of the reals related to algebra or analysis, it is usually better to use something like: math.stackexchange.com/questions/4202/induction-on-real-numbers – Arturo Magidin Mar 27 '11 at 4:26

The first thing you should be aware of: The Well-Ordering-Theorem is equivalent to the Axiom of Choice, and is highly non-constructive. Deriving the principle of transfinite induction on well-ordered sets is rather easy, the problem with $\mathbb{R}$ is that such a well-ordering exists only non-constructively, that is, you cannot explicitly give it, you can just assume that it exists.

A possible usage of it is when proving that $\mathbb{R}$ as $\mathbb{Q}$ vector space has a base (even though this follows from the more general theorem that every vector space has a base, which is mostly proved by Zorn's lemma but can as well be proven by transfinite induction).

Assume $\sqsubseteq$ was such a well-ordering on $\mathbb{R}\backslash \{0\}$ (which we can trivially get from a well-ordering on $\mathbb{R}$). Define \begin{align*} A_0 &:= \inf_\sqsubseteq\; \mathbb{R}\\ A_{n+1} &:=\begin{cases} A_n \cup \inf_\sqsubseteq ( x\in\mathbb{R}\mid x\mbox{ lin. indep. from } A_n ) & \mbox{ if well-defined}\\ A_n &\mbox{ otherwise} \end{cases}\\ A_\kappa &:= \bigcup_{n<\kappa} A_n \qquad\qquad\text{for limit ordinals }\kappa. \end{align*}

If for some $A_i$, no more element can be added to $A_{i+1}$, then we have a basis. If not, we can proceed. But trivially, we know that at least $A_\mu$ is such a basis, where $\mu$ is the ordinal isomorphic to $\sqsubseteq$.

(Sorry for the bad formatting, but this latex-thingy refuses to recognize my backslashes and curly brackets).

-
sometimes you need to "escape" to get the brackets and backslashes to work, using \\{ and \\. It's still a mystery to me when you have and when you don't have to, but I just do it when it fails. – Arturo Magidin Mar 27 '11 at 18:25