One more transfinite induction problem

[andytoh]

Let B be a basis for a vector space V (with an uncountable dimension!) over a field F, and let K be a linearly independent subset of V. Prove that there exists a subset S of B such that K U S is a basis for V.

I had to struggle a bit for this one. But I think I got it.

 

[andytoh]

An alternate solution using Zorn's Lemma coming up...

Let A be the collection of all subsets T of V such that for any linearly independent subset K of V containing vectors only from T, there exists a subset S of B so that
K U S is a basis for V. A is nonempty since B is in A. Partially order A by set inclusion. Let C = {C_i} be a totally ordered subcollection of A, and let D= U(C_i). Clearly D is an upper bound of C since every element in C is a subset of D.

Guys, I'm having trouble showing that D is in A. The problem is that any independent set containing elements only from D may be infinite, so the total orderedness of C is not helping. Can anyone pitch in here?

 

[Hurkyl]

Your transfinite induction proof seems very complex; I haven't digested yet to see if I believe it. Here's a simpler method:


Intuitive algorithm:

Let S := { }.
For each element v of B:
   If v is not in the span of K U S, then let S := S U {v}

There are a couple ways to turn this into transfinite induction or recursion. I think the easiest way is to define

$$B(v) := \{ \, w \in B \mid w < v \, \}$$

$$S(v) := \{ \, w \in B(v) \mid w \notin \mathop{\mathrm{Span}} (K \cup B(v)) \, \}$$

$$S := \bigcup_{v \in B} S(v)$$

or equivalently

$$S := \{ \, w \in B \mid w \notin \mathop{\mathrm{Span}} (K \cup B(v)) \, \}$$

The proof that v is in the span of S(v) and that S(v) is linearly independent is straightforward.


For a more literal translation of the intuitive algorithm, define:

$$P(v) := \bigcup_{w < v} N(v)$$

$$N(v) := \begin{cases} P(v) & v \in \mathop{\mathrm{Span}}( K \cup P(v) ) \\ P(v) \cup \{ \, v \, \} & v \notin \mathop{\mathrm{Span}}( K \cup P(v) ) \\ \end{cases}$$

(P for "previous value of S" and N for "next value of S")

$$S := \bigcup_{w < v} N(v)$$


Or a version with transfinite recursion:

$$A(v) := (v \notin \mathop{\mathrm{Span}}(K \cup S(v)))$$

$$S(v) := \{ \, w \in B \mid w < v \wedge A(w) \, \}$$

$$S := \{ \, v \in B \mid A(v) \, \}$$

(A for "Add this into S")

 

[andytoh]

Ok, I'll try your way too. Thanks. I'm still stuck on the Zorn's Lemma approach though.

 

[Hurkyl]

I tend to use the well-ordering principle for most of my axiom of choice needs -- the reason is because I can usually write down an iterative algorithm to produce the answer I want.

In general, I think that if you cannot write down some intuitively simple algorithm like I did, then a well-ordering style proof is going to be much more difficult than it needs to be.

I guess -- the trick is to use transfinite recursion or iteration to 'compute' an answer, and then use transfinite induction to prove that each intermediate stage has the correct properties, and then from there you prove that the answer has the correct properties.

 

[Hurkyl]

An alternate solution using Zorn's Lemma coming up...

Let A be the collection of all subsets T of V such that for any linearly independent subset K of V containing vectors only from T, there exists a subset S of B so that
K U S is a basis for V. A is nonempty since B is in A. Partially order A by set inclusion. Let C = {C_i} be a totally ordered subcollection of A, and let D= U(C_i). Clearly D is an upper bound of C since every element in C is a subset of D.

Guys, I'm having trouble showing that D is in A. The problem is that any independent set containing elements only from D may be infinite, so the total orderedness of C is not helping. Can anyone pitch in here?

Hrm. I'm having a little difficulty deciphering your intent here. Can you summarize your proof, skipping over all of the little details aside from the application of Zorn's lemma?

 

[andytoh]

Ok:

Let A be the collection of all subsets T of V such that for any linearly independent subset K of V containing vectors only from T, there exists a subset S of B so that
K U S is a basis for V. A is nonempty since B is in A. Partially order A by set inclusion. Let C = {C_i} be a totally ordered subcollection of A, and let D= U(C_i). D is an upper bound of C in A (this is where I'm stuck). By Zorn's Lemma, A has a maximal element M.

If M not=V, take v from V-M. Then MU{v} is also in A (this point I've already proven, though it was long), contradicting the maximality of M in A. Thus M=V.

 

[mathwonk]

whats wrong with taking a maximal independent set of form K union S, as above?

perhaps you are doing this, but less briefly.

 

[andytoh]

whats wrong with taking a maximal independent set of form K union S, as above?

Oh daymnn! That's so clever! This must be done for every independent set K, of course, but that's no extra work at all. I was restricting myself to just one partially ordered set A. I never thought of using a family of partially ordered sets A_K. Wow!

 

[mathwonk]

just take your one given independent set K, and consider all independent sets of form KunionS where S is a subset of the basis B. This collection is trivially inductive (take unions as always), hence has a maximal element.

obviously a maximl KunionS spans since otherwise some element of b is not spanned, which means adding it gives a larger independent set. QED.