Every vector space has a basis

If you haven’t seen a Zorn’s lemma argument before, this will probably be bewildering. It is here for the sake of completeness.


Every vector space V has a basis.

Consider the collection of linearly independent sets ordered by inclusion. So if S and T are linearly independent sets, and S\subseteq T, We would say S\leq T. Of course, it may be that we have sets neither of which is a subset of the other. This is totally fine, since we are in a partially ordered set, or poset.

Zorn’s lemma says that if every chain has an upper bound, then there is a maximal element. That is, if we take a bunch of linearly independent sets that are all comparable (one contains the other), and they have an upper bound, then there is a set M which is maximal in the sense that nothing contains it. Such a maximal set must have \mbox{span}(M)=V, for if it didn’t, we could add another element to it from V\setminus\mbox{span}(M), so it wouldn’t be maximal. By virtue of being in the partially ordered set to begin with, M must be linearly independent. As M is linearly independent and spanning, it is by definition a basis.

So we only need to show that every chain has an upper bound. If I have a bunch of linearly independent sets S_\alpha (possibly infinitely many, and a really big infinity too) and they form a chain of containment, we want to find a really big linearly independent set that contains all of the S_\alpha. It turns out that

\displaystyle\bigcup_\alpha S_\alpha

works. Why? We just need to show that it is linearly independent. Well, the trick is that linear combinations have to be finite. So if I had some linear dependence

\lambda_1 s_1+\lambda_2 s_2+\cdots+\lambda_n s_n=0,

There must be some \alpha for which the \{s_1,s_2,\dots,s_n\}\subseteq S_\alpha. But then, since S_\alpha is linearly independent, each of the \lambda_i must be zero as desired.


Zorn’s lemma is always weird if you haven’t done it before. Luckily, you can try your own. Another theorem is that if we have a linearly independent set S, we can extend it to a basis for our vector space. Try to recreate Zorn’s lemma argument. Instead of starting with all linearly independent sets, start with all linearly independent sets which contain S.


6 Responses to Every vector space has a basis

  1. Z Norwood says:

    You suggest repeating the argument to prove that every linearly independent set can be extended to a basis. This is certainly reasonable, but for the following reason I wonder if we can avoid repeating the argument: the existence of a maximal ideal in a nonzero ring (which is proved using a ZL argument very similar to the one you present here) can easily be extended to the stronger statement “Every ideal I in a nonzero ring R is contained in a maximal ideal” simply by pulling a maximal ideal in the quotient ring R/I back to a maximal ideal containing I in R. It seems like something similar should work here.

    I think something similar does work:
    If S is a linearly independent set of a vector space V and \langle S\rangle is the subspace it spans, then the quotient space V/\langle S\rangle has a basis B. I think a set A = (a_i)_{i\in I} of representatives for the fibres* over elements of B (we’re already using AC, so why not use it all the time?) together with S forms a basis for V. Proving that the set A \cup S spans V is straightforward; I think it’s also straightforward to show that A\cup S is linearly independent. For independence, it is essential that A contain one (and no more) element of each fibre, and that S be independent. (I think I’ve worked out the details satisfactorily, but my linear algebra is a bit rusty; so if someone objects to this, please speak up.)

    *What I mean here is a set of elements a_i in V such that for each element b_i \in B, there is exactly one a_i\in A that gets sent to b_i by the quotient map V \to V/\langle S\rangle. I was just too lazy to say that explicitly up there, I guess.

    Btw Andy, Jay might already have told you this, but I’m hoping to join you at UCLA next year. What classes are you taking this term?

    • Z Norwood says:

      Apparently WP doesn’t like “\left”; I guess it wants “\langle” and “\rangle instead.

      • Z Norwood says:

        GAHHH!!!!! Stupid WP. What I meant was:
        Apparently WP doesn’t like “\left<” or “\right>”; I guess it wants “\langle” and “\rangle instead.

    • soffer801 says:

      Zach, a few things:

      First, I edited your post to make it what I think you meant. Let me know if I was wrong.

      By “repeating the argument” what I meant was that you can generalize. The proof I gave is simply the one I suggested starting with \varnothing as your linearly independent set.

      What you seem to have done is taken the first result, and applied the correspondence theorem and AC to pull back a basis. It’s an interesting idea, and works fine, but I suppose I don’t see what you gain from this. You’re still using AC (which is of course unavoidable).

      Jay did not already tell me that. Shame on him. I’m taking the algebra, differential topology, and logic sequences. Let me know if you’re coming to visit.

      • Z Norwood says:

        Thanks for the edits. That looks right.

        Right; I was just suggesting a way to prove the stronger result from your result without doing the same Zorn’s-Lemma argument all over again. But, of course, you probably only mentioned the stronger result to offer the reader a chance to try his/her own ZL argument, which my suggestion avoids. Oh well. I really like it when this sort of thing happens, though: some result turns out to be equivalent to another result that’s obviously stronger. (Leader has talked about this a lot in Ramsey Theory this term, results that prove their generalisations.)

        Psshhh, how typical of Jay. Unfortunately, I doubt I’ll visit. I went to a campus visit last spring, and I’m in England this year, so I probably won’t fly all the way back again. But if I get in again, I’ll see you next summer!

        Good course choices! I’m sure Anton is in (at least) logic with you; tell him I said hi! Who is teaching the logic sequence this year?

  2. Pingback: Every field has an algebraic closure « Andy Soffer

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s