# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## I think, therefore Vector Basis Exists

This is the most fascinating mathematical fact among those that are simple enough for me to understand.

Every vector space has a basis. What’s fascinating is that This fact doesn’t have anything to do with vectors, linearity, etc. It is derived directly from the very Foundations. To prove it, it is sufficient to know these 3 things:
1. Any subset of a linearly independent set is linearly independent. (This is trivial).
2. A set is linearly independent if any finite subset of it is linearly independent. (This is really a definition, not even an axiom).
3. The Axiom of Choice, or its more convenient equivalent – Zorn’s Lemma.

Proof. V is a vector space. L is the set of all linearly independent subsets in V. L is partially ordered by inclusion. Every totally ordered chain C in L has an upper bound B simply given by the union of all sets in C. It may seem obvious that B is linearly independent. It’s not obvious but true. B is linearly independent because any finite subset of B must belong to some set from C which are all from L. Since all chains have upper bounds, by Zorn’s lemma, L has a maximal element B*. This maximal element is linearly independent because it belongs to L. And it is not contained in any other linearly independent subset of V because it’s maximal. So B* is a basis. QED.

It’s easy to see why any v from V can be represented as a (finite) linear combination of vectors from B*. If not, the set B* + v is linearly independent, so it belongs to L and contains B*, which is a contradiction since B* is maximal.

I don’t know how to prove that the basis “chosen” by this proof defines dimension. I.e. that all bases have the same cardinality.

Written by bbzippo

11/05/2009 at 4:00 pm

Posted in math

Tagged with