You are currently browsing the monthly archive for December 2008.

Let be a vector space (over a field), and let be the set of all sets of linearly independent vectors, partially ordered by set inclusion.

Any chain is bounded above by which is a linearly independent set of vectors because any finite subset of must be contained in some element of . Thus, by Zorn’s Lemma there exists at least one maximal element .

Suppose for contradiction that does not span. Then there is some which cannot be expressed as a finite linear combination of elements of . But this implies and , contradicting the maximality of M with respect to inclusion.

So must span, and since it is a linearly independent set, this makes it a basis.

The Cantor-Bernstein Theorem is the intuitively ‘obvious’ result that if given two sets we can inject into and into then there exists a bijection between and . In the notation of cardinalities this states that .

Given how intuitive this result is, the author was surprised to find a really quick and intuitive proof impossible to come by. The temptation is to pursue some sort of ‘tweaking’ method to make into a bijection by altering it a little, but the only obvious ways to do this involved using the axiom of choice, which seemed to be far more powerful than this result should demand.

The author has come across the following two choice-free proofs, the first from Wikipedia, and the second from a Part IA lecture course. Both start with the idea of constructing a bijection by partitioning the domain into two sets such that the function given by

is a bijection.

So this idea reduces the problem to finding a partition such that:

- (to ensure is well defined)
- is a partition of (to ensure is a bijection).

**Solution 1 (Wikipedia, modified):** Let and define recursively for . We now set , a *countable* union.

This ensures the first condition above since , and it ensures the second condition because for any we can either get to it by applying to some element of a finite number of times (in which case manifestly ) or we cannot (in which case so ).

**Solution 2 (P.T. Johnstone lecturing Numbers and Sets in Part IA of the Cambridge Maths Tripos):**

Consider the function , which we have basically designed to be such that if we can take and it will obviously satisfy the required two properties. We are now simply required to find such an .

The nontrivial idea is to then let and consider .

Vacuously by the definition of . But since is inclusion preserving, this implies which by definition of implies , which implies . So and we can take to give a valid bijection.

**Reflection on both proofs**

The idea used in the Wikipedia proof is that is a bijection, so the only thing to fix is and any inconveniences arising from this ‘taking up space’ once we map it into . So the set we eventually reach is the set of things not in or the image under of things which we must throw out of as a result of taking as our bijection on . Obviously, the more things we throw out of , the greater the size of and so the more elements of that are disturbed, and so on. The proof then works on the basis that this process of ‘throwing out’ is a countable one and so taking a countable union of a sequence of sets will suffice. Though this apparently works, I am not completely comfortable with this as a really *intuitive* proof of why the theorem is true. While the picture of the two injections interacting whereby the domain of *erodes* the codomain of until at the end of all time the functions have agreed which elements each is to biject is quite memorable and intuitive, it is not necessarily obvious why the functions must come to an agreement at the end of all time.

I found the second apparently quite different proof very intriguing. The preliminary (natural, but initially odd-looking) idea is setting up this function which takes a subset of and follows it along to a subset of , whose complement it then follows back along to a subset of of (which it complements again). It is then clear that if is a partition of then it is immediately a required partition . So a solution to will solve the problem.

In other words, we need to find such that both and . We now try almost exactly the same line of thought as in the Wikipedia proof. Taking we can trivially achieve the second relation, and since is clearly inclusion preserving, for any . The Wikipedia proof then finished by taking , and here of course (in fact, this argument presented using the notation is, to me, much more convincing).

Why then does Johnstone opt for the more unusual, albeit similar, approach of taking the larger set , a set which ostensibly contains the sets defined above, and then define instead (this works for the same reasons, and will certainly contain the defined in the above paragraph)? For one, this method of proof is more primitive, making no use of the notion of natural numbers. However, this author at present cannot see any other benefits to this approach. It certainly seems on the surface more obscure, difficult to motivate, and difficult to visualise or draw insight from. If the reader can see a good way to motivate this choice of or perhaps an interesting way in which this proof generalises while that relying on taking a countable union fails, I should be very glad to read it.

So in summary, the most intuitive proof of this fundamental theorem I could find was probably the argument from proof 1 in the language of proof 2, but I still don’t feel completely satisfied I know everything there is to know about why this theorem is true.