# 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, 08:58 AM
Deveno
Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
i think you can for $\displaystyle \{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, 09: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 $\displaystyle X\subseteq \{0,1\}^n$. Suppose X spans the space. Then there must be a combination of vectors in X that is equal to $\displaystyle e_i.$ Suppose $\displaystyle e_i\not\in X.$ Then since $\displaystyle X\neq\{0\},$ every vector in X has 1 on some coordinate different from $\displaystyle i$. No combination of such vectors can be equal to $\displaystyle e_i$. Therefore for any $\displaystyle 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