# Direct proofs from the well ordering theorem

In the course of writing yesterday’s post about Zorn’s lemma I noticed a different proof of the theorem that every vector space has a basis:

Let $$V$$ be a vector space and define some well-ordering $$<$$ on it. Let $$B$$ be the set of $$x$$ such that $$x$$ is not in the span of $$\{y: y < x\}$$.

Claim: B is a basis.

Proof: Certainly $$B$$ is linearly independent: If not, let $$x_1 < \ldots < x_n \in B$$ be linearly dependent. Then $$x_n$$ is in the span of $$x_1, \ldots, x_{n – 1}$$, which are $$< x_n$$, contradicting the definition of $$B$$.

Claim: For all $$x$$, $$x$$ is in the span of $$\{y \in B: y \leq x\}$$.

Proof: Transfinite induction. Either $$x$$ is not in the span of $$\{y: y < x\}$$, and thus $$x$$ is actually in this set and thus certainly in the span. Else, we can find $$y_1, \ldots, y_n < x$$ such that $$x$$ is in their span. But by induction assumption, each of these is in the span of $$\{y \in B: y < x\}$$, and thus so is $$X$$.

QED

To some extent this is just the normal proof in disguise, but I thought it was cute. I highly doubt it’s in any way original to me, but I hadn’t seen it before.

This made me wonder what other things you could prove this way. I’ve rarely seen the well ordering theorem used as a direct proof method except when you want to make some careful argument about cardinalities (e.g. one way the Continuum Hypothesis is often used is to put a well-ordering on $$\mathbb{R}$$ such that all the initial segments are countable).

For starters, the above proof can relatively easily be turned into a proof of the Teichmüller–Tukey lemma using essentially the same construction:

Let $$X$$ be some set, and let $$L \subseteq \mathcal{P}(X)$$ be some family of sets of finite character. Define the function $$f : X \to \{0, 1\}$$ as follows:

Let $$T = \{y < x: f(y) = 1\}$$.

Let $$f(x) = 1$$ if $$T \cup \{x\} \in L$$, else $$f(x) = 0$$.

Claim: $$S = \{x : f(x) = 1\}$$ is a maximal element of $$L$$.

Proof: First we show that it’s in $$L$$. If not, there is some finite subset $$x_1 < \ldots \x_n \in S$$ such that $$\{x_1, \ldots, x_n\} \not\in L$$. But then $$f(x_n) = 1$$, so with $$T$$  as in our definition of $$f$$,  $$T \cup \{x_n\} \in L$$. Thus every finite subset of this is in $$L$$, and in particular $$\{x_1, \ldots, x_n\} \in L$$, contradicting our assumption.

Now we show it’s maximal: Suppose $$S \cup \{x\} \in L$$. Then we must have $$f(x) = 1$$, because $$T \cup \{x\} \subseteq S \cup \{x\}$$, and families of sets of finite character are closed under taking subsets. Thus $$x \in S$$.

QED

Slightly further adaptation allows us to prove Zorn’s lemma itself via this construction, and I think it actually is a slightly nicer proof than the one I presented before:

Let $$T$$ be some partially ordered set with relation $$\prec$$ such that every chain in $$T$$ has an upper bound.

Let $$<$$ be a well-order on $$T$$ (not necessarily compatible with $$\prec$$\).

Define $$f : T \to \{0, 1\}$$ as $$f(x) = 1$$ if $$y \prec x$$ for every $$y < x$$ such that $$f(y) = 1$$, else $$f(x) = 0$$.

Let $$C = \{x: f(x) = 1\}$$.

Claim: $$C$$ is a chain for $$\prec$$.

Proof: Let $$x, y \in C$$ with $$x \neq y$$. By reordering if necessary we can assume $$x < y$$. Then by construction of $$f$$, we must have $$x \prec y$$.

Thus, by assumption, there is some upper bound for $$C$$, call it $$s$$.

Claim: $$s$$ is maximal.

Proof: We will show that $$s \in C$$. This proves that $$s$$ is maximal because if there were another element $$t > s$$, this would also be an upper bound, which would mean it will also have to be in $$C$$, which contradicts that $$s$$ is an upper bound for $$C$$.

To show that $$s$$ is in $$C$$: We must have $$f(s) = 1$$, because $$\{y : y < x, f(y) = 1 \} \subseteq C\}$$, $$y \preceq s$$ for all $$y \in C$$, and $$y \neq s$$ for $$y < s$$. These are the conditions in our definition of $$f$$, so $$f(s) = 1$$ and thus $$s \in C$$.

QED

Side note 1: Note that all we’ve really done in the above proof is inlined a proof of the Hausdorff maximal principle. This follows fairly straightforwardly from the Teichmüller–Tukey lemma, so having its own proof by this mechanism is not actually super useful.

Side note 2: You may have only seen the well-ordering theorem proven using Zorn’s lemma so this may seem circular, but you can prove it directly from Hartog’s lemma (which does not require the axiom of choice) as follows:

Let $$X$$ be some set, and let $$c$$ be a choice function for subsets of $$X$$. Let $$W$$ be some well ordered set that does not inject into $$X$$. Define $$f : W \to X \cup \{\infty\}$$ as:

If $$X \subseteq \{ f(s) : s < t \}$$ then $$f(t) = \infty$$. Else, $$f(t) = c(X \setminus \{ f(s) : s < t \})$$.

This must eventually hit $$\infty$$ as otherwise it would be injective. Restricted to $$\{t: f(t) \neq \infty\}$$, f gives a bijection between $$X$$ and a well-ordered set, so you can use this to define a well-ordering on $$X$$.

QED

Is this style of proof really any better than the alternatives? I don’t know. You probably still want to use Zorn’s lemma and similar most of the time anyway. I like these proofs though, and they seem like a slightly less messy way to get a feel for transfinite induction.

This entry was posted in Numbers are hard on by .