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

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• Oct 23rd 2011, 09:58 AM
Deveno
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).
• Oct 23rd 2011, 10:26 AM
ymar
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.
Show 40 post(s) from this thread on one page
Page 2 of 2 First 12