The quick and dirty guide to one of the stranger mathematical curiosities.

Motivation!

It’s always worth having motivation for bizarre and abstract mathematical ideas.

As Timothy Gowers, Fields Medalist, puts it in this 2008 article on his blog

If you are building a mathematical object in stages and find that (i) you have not finished even after infinitely many stages, and (ii) there seems to be nothing to stop you continuing to build, then Zorn’s lemma may well be able to help you.

*Like the Nobel Prize in Mathematics.

An infinite dimensional basis?

In linear algebra, we have the idea of a basis. For example, in R³, the vectors (1,0,0), (0,1,0), (0,0,1) can be combined linearly to give any vector in R³. This is helpful. But what about large, infinite-dimensional vector spaces? Do these have a basis? More precisely, is the a subset of the vector space such that every element in the vector space can be constructed out of a finite linear combination in this subset, AND the subset is linearly independent. In our R³ example, every element can be constructed out of (1,0,0) (0,1,0) and (0,0,1), and linear independence is obvious, as we cannot built any one of these with a linear combination of the other two. But in infinite-dimensional spaces the construction of such a basis, called a Hamel basis, is not obvious. We will see how Zorn’s Lemma enables us to do this.

Some intuitive motivation

Zorn’s Lemma follows from the Axiom of Choice. But Axiom of Choice follows from Zorn’s Lemma. So it really doesn’t matter — unless you are a philosopher- which one you assume.

These are slightly weird and wonderful mathematical statements that mathematicians assume are true because they help make sense of very large sets and collections of sets.

You see, we have our ordinary mathematical objects we know and love, like the integers, or real numbers, or geometric objects.

But it turns out these mathematical objects are a bit limited. In fact, they’re just a bit too… small!

Zorn’s Lemma (and the Axiom of Choice) ensure that ‘large sets’, (like the set of all continuous functions or all ‘linear’ functions between two sets) have some properties we’d expect. Importantly, but being very precise statements, they do this with structure. It’s no good in mathematics saying ‘oh, we sort of expect this to be true, so we’ll assume it’. Mathematics is to do with the structure of assumptions and inferences, so we need to assume something precisely.

Axiom of choice tells us, that if we have a collection of sets, then there exists a set which contains one element from each of these sets.

Statement of Zorn’s Lemma

Zorn’s Lemma tells us that:

If in a partially ordered set every totally ordered subset has an upper bound then the set has a maximal element.

An ordering is just a relation like ≤. We need, if a≤b and b≤c then a≤c. Also, if a≤b and b≤a then a=b.

A total ordering is when you can compare any two elements in the set, e.g. the integers. A partial ordering is when you cannot necessarily compare any two elements, e.g. the set {1,2,3,4, “Dog”} you can compare the integers with each other, but you don’t have a comparison for 1 with “Dog”. (or at least one which is sensible!)

A totally ordered subset, then, is a group of objects in the set, in which all elements can be compared. So {1,2,3,4} is a totally ordered subset of {1,2,3,4, “Dog”}. A totally ordered subset is also called a chain. I will be using this notation later.

A maximal element is one which is greater than every element it can be compared with. For example 4 is the maximal element of {1,2,3,4, “Dog”} because of the elements it can be compared with, the integers 1 through 4, it is greater than all of them.

It’s worth noting that there are very many ways to define an ordering! The one you are most familiar with is is probably comparing numbers, but the concepts of orderings are more general than this!

Okay, let’s prove something!

(Health warning: you might find this hard. If you don’t have experience with at least linear algebra, and preferably more, then it may be hard to get more than a birds-eye view of what is going on, and perhaps don’t worry over every detail).

We now prove that every vector space has a Hamel basis.

If we call our Hamel space H, then for any element in our space V, this element ‘v’ can be represented as a linear combination of elements in H. And H’s elements are linearly independent.

In the R³ case again, an element (x,y,z) = x*(1,0,0) + y*(0,1,0) + z*(0,0,1). E.g. (1,2,5) = 1*(1,0,0) + 2*(0,1,0) + 5*(0,0,1).

Also, clearly (1,0,0) cannot be created out of linear combination of (0,1,0) and (0,0,1). Visually, combining movements on the 2d plane cannot give a movement in the vertical direction!

So the set {(1,0,0), (0,1,0), (0,0,1)} is a Hamel basis of R³.

But in infinite dimensional systems things get trickier.

We use Zorn’s Lemma.

We say a subset S is ≤ a subset T if:

• Every element of S is in T
• The elements of both S and T are linearly independent

Let’s check the conditions of Zorn’s Lemma. Is every totally ordered chain bounded? Yes! Consider taking the union of every element in the chain. [note: confusingly, the chain is a set whose elements are sets, and then we compare between sets by looking at their elements in turn.]

Union of every element of the chain: i.e. a set which contains every element which appears in some set in our chain. Clearly every set in the chain is a subset of, a.k.a all its elements are a member of, the union of all sets in the chain. Lets call this new set U.

What about linear independence? Well, if we take N elements from U, we can pinpoint N sets in the chain they were found in. As the chain is totally ordered, the largest of these N sets contains the others. But as this set is in the chain, its elements must be linearly independent.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

Then, by Zorn’s Lemma, there must be a maximal element, i.e. a set which contains the elements of all those sets to which it is comparable, and its elements are linearly independent. That’s because (1) every chain has an upper bound and (2) the set is partially ordered.

Now suppose that this set was not a Hamel basis. Then there is an element not in its ‘span’, i.e. an element, ‘e’, which we cannot construct out of a finite linear combination of its elements. But then, if we append consider the set of all U’s elements and the element ‘e’, this new set is ≥U, because (1) all U’s elements are in this new set, and (2) by assumption this new set is linearly independent.

Thus, our proof is completed, a ‘proof by contradiction’.