Page 2 of 2 FirstFirst 12
Results 16 to 17 of 17

Math Help - a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

  1. #16
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,328
    Thanks
    701

    Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

    i think you can for \{0,1\}^n, especially since you know that spanning is the hard part. it might be more challenging to prove the more general result (an arbitrary idempotent semiring).
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

    OK. It's actually very easy when you know what you want to prove. Unless I'm mistaken of course.

    Let X\subseteq \{0,1\}^n. Suppose X spans the space. Then there must be a combination of vectors in X that is equal to e_i. Suppose e_i\not\in X. Then since X\neq\{0\}, every vector in X has 1 on some coordinate different from i. No combination of such vectors can be equal to e_i. Therefore for any i=1,2,...,n,\, e_i must be in X. If we suppose that X is independent, there can be no other vectors in it.
    Last edited by ymar; October 23rd 2011 at 09:43 AM. Reason: 1-->i
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 17th 2011, 02:50 PM
  2. Replies: 1
    Last Post: September 16th 2011, 01:08 AM
  3. Replies: 2
    Last Post: April 24th 2011, 07:01 AM
  4. Replies: 1
    Last Post: October 25th 2010, 04:45 AM
  5. Replies: 1
    Last Post: June 4th 2010, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum