Some subset of a generating set is a basis

  • Thread starter Bipolarity
  • Start date
  • #1
775
1
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
 

Answers and Replies

  • #2
WannabeNewton
Science Advisor
5,803
531
You need Zorn's lemma.
 
  • #3
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,819
135
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.
 
  • #4
775
1
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
 
  • #5
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,819
135
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.
 
  • #8
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,393
180
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.
 
  • #9
269
24
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?
 
  • #10
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,819
135
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.
 
  • #11
775
1
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
 
  • #12
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,819
135
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'.
 

Related Threads on Some subset of a generating set is a basis

Replies
2
Views
2K
Replies
4
Views
1K
Replies
5
Views
3K
Replies
4
Views
3K
  • Last Post
Replies
7
Views
4K
Replies
3
Views
3K
  • Last Post
Replies
7
Views
888
Replies
2
Views
2K
Replies
2
Views
1K
  • Last Post
Replies
3
Views
2K
Top