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.

I was reminded of a quote earlier:

“The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn’s lemma?” — Jerry Bona

I find I am slightly annoyed by this quote, because the equivalence between these three is so direct. I know that they’re equivalent is the joke, but the equivalence is close enough if you look at it the right way then building intuition about one should help you build intuition about the others.

Moreover, I think the way Zorn’s lemma is taught has a problem-solution ordering issue.

Zorn’s lemma, at its core, takes a common style of proof and isolates the boring mechanical parts into a self-contained tool that abstracts them away. This is great, but the problem is that it so effectively supplants the method it’s trying to abstract that nobody teaches that method any more so it feels like it comes out of nowhere.

That method is transfinite induction. Or, induction over infinite well ordered sets.

To explain how to use this, we need to use the following results:

Well ordered induction principle

Let \(X\) be some well ordered set, and let \(P\) be some property of elements of \(X\) such that for all \(x \in X\), if \(P(y)\) holds for all \(y < x\) then \(P(x)\). Then \(P(x)\) holds for all \(x \in X\).

Proof: Suppose not, let \(x\) be the smallest element for which it does not hold. Then it holds for all \(y < x\) by the fact that \(x\) is the smallest. Thus it holds for \(x\) by assumptions on \(P\). This is a contradiction. QED

We can use this much like we would use induction on the natural numbers.

In particular it allows us to define functions recursively: If we can define a function \(f(x)\) in terms of its values for \(y < x\) this allows us to define a function on the whole of \(X\) (consider the property \(P(X)\) = “\(f\) is uniquely defined for all \(y < x\)”

Hartog’s Lemma

Let \(X\) be some set. There is a well-ordered set \(W\) such that there is no injective function \(f: W \to X\).

Note: This doesn’t require the axiom of choice, but without the axiom of choice we can’t then conclude that there is some injective function \(f: X \to W\), because we could use such an injective function to well-order \(X\). This then implies the well-ordering theorem, which implies the axiom of choice.

Proof: I’m only going to sketch this. The core idea is that you define \(W\) as the set of all well-orders of subsets of \(X\), up to order isomorphism. If there were an injective function from \(W\) to \(X\) then we could construct an element \(x \in W\) such that the initial segment \(\{y : y < x\}\) is isomorphic to \(W\). This gives us a function \(f : W \to W\) such that \(f(x) < x\). Then \(x > f(x) > f^2(x) > \ldots\) gives us an infinite decreasing sequence in a well ordered set, which is impossible.

If you didn’t understand that sketch, don’t worry about it. It won’t be on the test. Just trust the theorem.

Putting this all together

Lets see how you use this to prove something that you’d normally prove with Zorn’s lemma: Let’s prove that every vector space has a basis.

Let \(V\) be a vector space and let \(L\) be the set of all linearly independent subsets of \(V\).

Let \(W\) be some well ordered set with no injective functions into \(L\).

Define a function \(f: W \to \mathcal{P}(V)\) recursively as follows:

If \(A = \bigcup\limits_{y < x} f(y) \) spans the whole vector space, let \(f(x) = A\). Else, let \(f(x) = A \cup \{ v \} \) where \(v \in V\) is picked using the axiom of choice to be any element outside the span of \(A\).

The intuition here is that we keep adding in new elements which are linearly independent of the existing elements and we’re going to keep going until we can’t go any further, at which point we must span the whole space.

Claim 1: If \(y < x\) then \(f(y) \subseteq f(x)\).

Proof: This is by construction. We defined \(f(x)\) in terms of a union that contains \(f(y)\).

Claim: \(f(x)\) is always linearly independent.

Proof: Induction! Suppose it’s true for all \(y < x\). Then we can find \(v_1, \ldots, v_n \in f(x)\) linearly dependent. But there are \(y_1, \ldots, y_n\) with \(v_i \in f(y_i)\). But because there are only finitely many \(y_i\) we can find \(y = \max y_i\) such that \(v_1, \ldots, v_n \in f(y)\) (because of the previous claim). So \(f(y)\) is linearly dependent, contradicting the inductive assumption. QED

So actually \(f: W \to L\).

But this means that \(f\) cannot be injective (by choice of \(W\)). So at some point we must have \(y < x\) with \(f(x) = f(y)\). But this can only happen if at some point our choice of \(A\) spanned the whole space. Thus \(f(x)\) must have spanned the whole space, and thus is a linearly independent spanning set. i.e. a basis.

QED

And thus Zorn

It may not be obvious what about vector spaces in the above mattered and what was generalizable in the above, but after you’ve done a few of those it starts to become clearer. Rather than making you sit through that, let me highlight what I think were the salient details:

1. We have some partially ordered set – in this case linearly independent subsets of a vector space, ordered by inclusion.
2. We take our well ordered set and construct a function into that partially ordered set which is strictly increasing until it hits a maximal element.
3. Because the function cannot be injective, it cannot be strictly increasing, so there must be a maximal element.

In the case of a vector space, a maximal linearly independent set must span the whole space (because otherwise you could add in another element), so that maximal element is what we were looking for.

So all we need to know now is when we can construct such a function. What was the property of linearly independent sets that let us do this?

The property was that given our choice of \(f(y)\) for \(y < x\) we were always able to choose \(f(x)\) to be greater than or equal to every \(f(y)\). i.e. we choose \(f(x)\) to be an upper bound.

If every subset of our target partially ordered set had an upper bound, then we could always construct this choice. This is however too strong a condition: e.g. it’s not the case that any two linearly independent subsets have a common upper bound. The sets \(\{v\}\) and \(\{-v\}\) do not for any non-zero \(v\).

However, all we really need is that the sort of sets we get during our transfinite induction have upper bounds.

And the important feature of these sets is that they come from an increasing sequence. In particular, any two elements of them are comparable. They form a chain.

This leads us to the notion required for Zorn’s lemma: We are interested in partially ordered sets such that every chain has an upper bound. This allows us to construct our function, and transfinite induction then gives us a maximal element.

So:

Zorn’s lemma

Let \(T\) be a partially ordered set such that every chain has an upper bound.Then there is some maximal element \(t \in T\). i.e. there is no element \(s \in T\) such that \(t < s\).

Proof:

Our proof will be very similar to our proof for vector space having a basis. The only major difference is that we’ll have to work a little harder at the recursive definition of our increasing function because where for the basis form we could construct the function and then show its output was always in \(L\), here we have to simultaneously construct the function and show that it’s well defined.

In order to do this we’ll introduce a special value \(\infty \not\in T\). If things go wrong and we fail to construct a maximal element we’ll return \(\infty\) instead. This simplifies things to showing that we never return \(\infty\).

First, lets be more explicit about our use of the axiom of choice. Let \(f\) be some choice function. We’re going to define an ‘upper bound’ function \(u(A)\) as follows:

Let \(Q = \{x: y < x \forall y \in A\}\).

Let \(R = \{x: y \leq x \forall y \in A\}\).

If \(Q\) is non-empty, let \(u(A) = f(Q)\), i.e. any element which is strictly greater than all of the elements of \(A\).

Else if \(R\) is non-empty, let \(u(A) = f(R)\) – i.e. any element which is \(\geq\) every element of \(A\).

Else, there are no upper bounds. Return \(\infty\).

Let \(W\) be some well ordered set. Define \(f : W \to T \cup \{\infty\}\) recursively as \(f(x) = \infty\) if \(f(y) = \infty\) for any \(y < x\), else \(f(x) = u(\{f(y): y < x\}))\)

Claim: This function never returns \(\infty\).

Proof by induction:

Suppose this is true for all \(y < x\). Then the set \(\{f(y): y < x\}\) must form a chain, if \(u < v < x\) we picked \(f(v) \geq f(w)\) by our definition of \(u\).

Thus, by our assumption on the partially ordered set \(T\), this set has an upper bound, so \(R\) in our definition of \(u\) is non-empty. This means that \(f(x)\) is chosen to be an element of \(R\) and thus is not \(\infty\).

So we’ve constructed an increasing \(f : W \to T\). By choosing \(W\) appropriately, this cannot be an injection. So find \(y < x\) with \(f(x) = f(y)\). This can only happen if there is no element \(s\) such that \(s > f(y)\). i.e. \(f(y)\) is a maximal element.

QED

Although the details differed, hopefully this should look structurally pretty similar to the more concrete form with the vector space basis.

Why is this useful?

The main reason it’s useful is that the property of chains having upper bounds comes up a lot. In particular it comes up with things that are “essentially finite” in nature. Most applications of Zorn seem to boil down to the following more specific lemma:

Teichmüller–Tukey lemma

Let \(X\) be some set and let \(L \subset \mathcal{P}(X)\) be some family of sets with the property that \(A \in L\) if and only if \(B \in L\) for every finite \(B \subseteq A\).

Then there is some \(A \in L\) such that for all \(x \in X\), \(A \cup \{x\} \not\in L\).

Note: In particular, as we saw in our original proof, the linearly ordered subsets of a vector space satisfy these conditions. Most essentially “algebraic” conditions tend to satisfy it.

Proof:

We consider \(L\) partially ordered by subset inclusion. We’ll show that the union of any chain of sets is in \(L\).

Suppose \(C\) were some chain of sets in \(L\) such that \(\bigcup C \not \in L\). Then we can find a finite set \(\{x_1, \ldots, x_n\} \subseteq \bigcup C\) not in \(L\).

But then we can find \(U_i\) such that \(x_i \in U_i \in C\). Because \(C\) is a chain we can thus find a maximum \(U\). But then \(\{x_1, \ldots, x_n\}\) is a finite subset of \(U\) which is not in \(L\), contradicting the assumption that \(U \in L\).

QED

In parting

Hopefully even if you didn’t follow all the details this demystified Zorn’s lemma a bit.

In general, there is a rich theory of well ordered sets and it seems to often be skipped or deferred until after Zorn’s lemma has already been taught. I can understand why – if you fill in all the details it feels like a pretty complex piece of machinery to be introducing when all you’re going to do is use it to prove Zorn’s lemma and then forget about it.

There’s a lot more to the theory than that though. Some of it is pretty interesting, and some of it I just think is useful in demystifying where a lot of this sort of thing comes from.