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

Thread: 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,546
    Thanks
    842

    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; Oct 23rd 2011 at 10: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: Oct 17th 2011, 03:50 PM
  2. Replies: 1
    Last Post: Sep 16th 2011, 02:08 AM
  3. Replies: 2
    Last Post: Apr 24th 2011, 08:01 AM
  4. Replies: 1
    Last Post: Oct 25th 2010, 05:45 AM
  5. Replies: 1
    Last Post: Jun 4th 2010, 11:26 PM

Search Tags


/mathhelpforum @mathhelpforum