# 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? An uncountable set like $$\mathbb{R}$$ can be well ordered by the well ordering principle, so the induction can be applied to a uncountable set like $$\mathbb{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. 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. 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. 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 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$.
• According to one definition of a proof, it does not follow from the fact that every vector space over $\mathbb{R}$ has a basis that every vector space over $\mathbb{Q}$ has a basis. I realize that assuming the axiom of choice, it can probably still be proven another way that every vector space over $\mathbb{Q}$ has a basis and once you know how to prove that about vector spaces over $\mathbb{R}$, it's easy to figure out how to prove that about vector spaces over $\mathbb{Q}$. Feb 6 '19 at 0:44