Another infinite-dimensional basis question using transfinite induction

[andytoh]

My recent interest in using transfinite induction in linear algebra has led me to pose a new question. (I will use c for the subset symbol)

Question: Use transfinite induction (not Zorn's lemma) to prove that if I is a linearly independent set and G is a set of generators (a spanning set) of an infinite-dimensional vector space V, with I c G, then there exists a basis B for V such that I c B c G.

There are not enough transfinite induction exercises in my set theory and topology textbooks so I had to pose this transfinite induction question myself. I'll give it a go:

Well-order G. Let A be the set of all vectors in G such that there exists a linearly independent set K where I c K c G and A c span(K) . A is non-empty since I c A, and thus there exists such a K. Suppose that the section S_v is a subset of A for some v in G. If v belongs to span(K), then by definition v belongs to A. If instead v does not belong to span(K), then KU{v} is a linearly independent set in V. Now I c KU{v} c G since I c K c G and v is in G. Furthermore,
AU{v} c span(KU{v}) since A c span(K). Thus v is in A. Thus A is an inductive subset of G. By the principle of transfinite induction, we have A = G. Consequently, there exists a linearly independent set B where I c B c G and G c span(B). So then V = span(G) c span(span(B)) = span(B), so that B is a basis for V.

How does this look?

 

[morphism]

Well-order G. Let A be the set of all vectors in G such that there exists a linearly independent set K where I c K c G and A c span(K) . A is non-empty since I c A, and thus there exists such a K (which may be I itself).

Why is A c span(K)?

 

[andytoh]

Why is A c span(K)?

I'm defining my A to have this property, and I'm trying to show that A=G by transfinite induction. I started by saying that A is non-empty because I itself has the property of A (hence such a linearly independent set K exists).

If there is an easier subset property of A, where A is the subset of G (or perhaps we shouldn't use G?) that we want to show is an inductive subset, I'm happy to consider it. But in order to use transfinite induction, we have to define some kind of property of some kind of set (this step I think is the toughest part).

 

[morphism]

My problem was with how you proved that A is non-empty. The way you defined it, having A contain I isn't enough (why is A in span(I)?). We want A to be in the span of a linearly independent set. Maybe I'm misreading it, but I don't think the way you're defining A is very useful.

To be honest I don't think transfinite induction is going to be a very fruitful approach here, at least not if you plan to induct 'upwards' from I to G. Maybe you should try to use an inductive argument to collapse G towards I. At least here you have something to work with, e.g. if G isn't independent, then we can throw out a vector.

 

[andytoh]

I figured that since I c I c G and I c span(I), then we have at least A=I, so A is not empty. Let me think about this more...

To be honest I don't think transfinite induction is going to be a very fruitful approach here, at least not if you plan to induct 'upwards' from I to G. Maybe you should try to use an inductive argument to collapse G towards I. At least here you have something to work with, e.g. if G isn't independent, then we can throw out a vector.

Zorn's Lemma is the best approach, but that's already been done in textbooks (and by many students) so I want to try using transfinite induction here for extra practice. I'll consider your collapsing approach too (I enjoy doing multiple solutions to good problems).

 

[andytoh]

Sticking with my original approach, perhaps I should define my A to be a subset of G-I instead of G. Then A is not empty because any element of G in span(I)-I is in A. I believe the conclusion that A=G-I will also get the job done (after some further explanations).

 

[andytoh]

Well-order G-I. Let A be the set of all vectors in G-I such that there exists a subset K c G, where I U K is a linearly independent subset of G and A c span(I U K). A is non-empty since any vector in G in span(I)-I is in A, and thus there exists such a K (K can be the empty set!). Suppose that the section S_v is a subset of A for some v in G-I. If v belongs to span(I U K), then by definition v belongs to A. If instead v does not belong to span(I U K), then I U K U {v} is a linearly independent subset of G. Now A U {v} c span(I U K U {v}) since A c span(I U K). Thus v is in A. Thus A is an inductive subset of G-I. By the principle of transfinite induction, we have
A = G-I. Consequently, there exists a subset K of G such that I U K is a linearly independent subset of G and (G-I) c span(I U K), which also means that
G c span(I U K). So then V = span(G) c span(span(I U K)) = span(I U K), so that I U K is a basis for V, with I c (I U K) c G.

Because K can be the empty set, I believe this works now. I will try your "collapsing" approach now.

 

[andytoh]

It turns out the "collapsing" approach follows the same pattern as my original "lifting" method, with apparently no advantage of one method over the other.