Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

One more transfinite induction problem

  1. Nov 26, 2007 #1
    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.
     

    Attached Files:

  2. jcsd
  3. Nov 26, 2007 #2
    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???
     
    Last edited: Nov 26, 2007
  4. Nov 26, 2007 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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:

    Code (Text):

    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

    [tex]B(v) := \{ \, w \in B \mid w < v \, \}[/tex]

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

    [tex]S := \bigcup_{v \in B} S(v)[/tex]

    or equivalently

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

    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:

    [tex]P(v) := \bigcup_{w < v} N(v) [/tex]

    [tex]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}
    [/tex]

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

    [tex]S := \bigcup_{w < v} N(v)[/tex]


    Or a version with transfinite recursion:

    [tex]A(v) := (v \notin \mathop{\mathrm{Span}}(K \cup S(v)))[/tex]

    [tex]S(v) := \{ \, w \in B \mid w < v \wedge A(w) \, \}[/tex]

    [tex]S := \{ \, v \in B \mid A(v) \, \}[/tex]

    (A for "Add this into S")
     
    Last edited: Nov 26, 2007
  5. Nov 26, 2007 #4
    Ok, I'll try your way too. Thanks. I'm still stuck on the Zorn's Lemma approach though.
     
  6. Nov 26, 2007 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  7. Nov 26, 2007 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  8. Nov 26, 2007 #7
    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.
     
    Last edited: Nov 26, 2007
  9. Nov 26, 2007 #8

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

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

    perhaps you are doing this, but less briefly.
     
  10. Nov 26, 2007 #9
    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!
     
    Last edited: Nov 26, 2007
  11. Nov 27, 2007 #10

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: One more transfinite induction problem
  1. Induction problem (Replies: 1)

  2. Induction problem (Replies: 7)

Loading...