Some subset of a generating set is a basis

[Bipolarity]

I'm having some set theoretic qualms about the following argument for the following statement:

Let V be a vector space of dimension n and let S be a generating set for V. Prove that some subset of S is a basis for V.

The argument is as follows:
If ##V = \{ 0 \} ## then it is trivial since the null set is a basis for V. Otherwise V has dimension greater than zero, so that S is nonempty.

Given that S is nonempty, take a new set S' which is empty. Look at all the vectors in S and chuck them into S' making sure that independence of S' is preserved. A point will come where S has n vectors, at which point it is a basis.

The problem is the termination of this process and the procedure by which vectors in S are taken and chucked into S'. If S is finite, all is well, since we can search through all the elements of S in a finite amount of time. But what if S is infinite?

BiP

 

[WannabeNewton]

You need Zorn's lemma.

 

[Office_Shredder]

If your vector space V is finite dimensional, I don't think you need Zorn's lemma. Let S' be a largest linearly independent subset of S - since V is finite dimensional, this must exist and be of size no larger than n (if V was infinite dimensional we would need Zorn's lemma). Every vector in V can be written as a linear combination of elements of S', because if there was some vector v which wasn't then I could add v to S' and get a larger linearly independent subset of V. Therefore the span of S is simply the span of S' since every linear combination of elements of S can be written as a linear combination of elements of S' - and since the span of S is V, the span of S' must be V, and hence S' is a basis.

 

[Bipolarity]

If your vector space V is finite dimensional, I don't think you need Zorn's lemma. Let S' be a largest linearly independent subset of S - since V is finite dimensional, this must exist and be of size no larger than n (if V was infinite dimensional we would need Zorn's lemma). Every vector in V can be written as a linear combination of elements of S', because if there was some vector v which wasn't then I could add v to S' and get a larger linearly independent subset of V. Therefore the span of S is simply the span of S' since every linear combination of elements of S can be written as a linear combination of elements of S' - and since the span of S is V, the span of S' must be V, and hence S' is a basis.

Why must there exist a maximal linearly independent subset of S?

BiP

 

[Office_Shredder]

Why must there exist a maximal linearly independent subset of S?

BiP

Because there can only exist linearly independent subsets of size 1,...,n. We know there exists a subset of size 1. Either there are or aren't linearly subsets of size n, if there are then they are all maximal and we're done. If there are not, then either there are or there aren't linearly independent subsets of size n-1. If there are, they must be maximal (since we said there aren't any of size n) and we're done. If there aren't any of size n-1, then either there are or aren't any of size n-2. Rinse and repeat.

Again, this heavily relies on the fact that V is finite dimensional, so we can just start at the top and work our way down and be done in finitely many steps.

 

[Jorriss]

You need Zorn's lemma.

I think you need the axiom of choice.

 

[jbunniii]

You need Zorn's lemma.

I think you need the axiom of choice.

I want some of whatever you guys are smoking!

 

[jbunniii]

Let ##v_1## be any nonzero element of ##S##. Then ##\{v_1\}## is trivially a linearly independent set.

For the inductive step, assume ##k < n## and we have chosen ##\{v_1,\ldots,v_k\}## to be linearly independent. There must be some ##s\in S## which is linearly independent of ##\{v_1,\ldots,v_k\}##, for otherwise ##S \subset \text{span}\{v_1,\ldots,v_k\}##, whence ##V = \text{span}(S) \subset \text{span}\{v_1,\ldots v_k\}##. But this is nonsense since ##\text{dim}(V) = n > k##. Therefore, ##\{v_1,\ldots,v_k,s\}## is a linearly independent set containing ##k+1## elements of ##S##.

Thus for any ##k<n##, we can grow the list to ##k+1## elements. Since this applies in particular to ##k=n-1##, we're done.

 

[economicsnerd]

Doesn't it depend on how you define an n-dimensional space?

- If your definition is that all bases are of size n, then the inductive argument is enough.
- If your definition is that there exists a basis of size n, then I'm not sure if there's a good, "direct" way. Anyone?

Of course, the two are equivalent, if you're okay using the dimension theorem. Is that much power needed?

 

[Office_Shredder]

Doesn't it depend on how you define an n-dimensional space?

- If your definition is that all bases are of size n, then the inductive argument is enough.
- If your definition is that there exists a basis of size n, then I'm not sure if there's a good, "direct" way. Anyone?

Of course, the two are equivalent, if you're okay using the dimension theorem. Is that much power needed?

If you reeeaaally don't want to know anything about what a basis is besides the fact that it's linearly independent and spanning, then you probably need to go with the axiom of choice, since the set S' might be infinite as far as you know in this setting. The dimension theorem is way better, and I think very few people would call it "that much power" regardless.

 

[Bipolarity]

Let ##v_1## be any nonzero element of ##S##. Then ##\{v_1\}## is trivially a linearly independent set.

For the inductive step, assume ##k < n## and we have chosen ##\{v_1,\ldots,v_k\}## to be linearly independent. There must be some ##s\in S## which is linearly independent of ##\{v_1,\ldots,v_k\}##, for otherwise ##S \subset \text{span}\{v_1,\ldots,v_k\}##, whence ##V = \text{span}(S) \subset \text{span}\{v_1,\ldots v_k\}##. But this is nonsense since ##\text{dim}(V) = n > k##. Therefore, ##\{v_1,\ldots,v_k,s\}## is a linearly independent set containing ##k+1## elements of ##S##.

Thus for any ##k<n##, we can grow the list to ##k+1## elements. Since this applies in particular to ##k=n-1##, we're done.

This proves the theorem if S is finite. It fails to hold when S is infinite, because induction only extends to the naturals.

BiP

 

[Office_Shredder]

This proves the theorem if S is finite. It fails to hold when S is infinite, because induction only extends to the naturals.

BiP

The induction is not on the size of S though, so he's OK - it's on the size of S'.