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

1. ## 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).

2. ## 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.

Page 2 of 2 First 12