
a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Let . Can we impose a condition on these vectors so that every vector has a unique decomposition
where and by definition and denotes elementwise conjunction?
The one from linear algebra (a linear combination can be zero only trivially) doesn't work  it's easy to give an example.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Quote:
Originally Posted by
ymar Let
. Can we impose a condition on these vectors so that every vector
has a unique decomposition
where
and by definition
and
denotes elementwise conjunction?
The one from linear algebra (a linear combination can be zero only trivially) doesn't work  it's easy to give an example.
Could you explain more what you mean by "conjunction"? Evidently you don't mean addition modulo two otherwise is just a vector space over and trivially has a basis.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Sorry! I meant logical disjunction. It's my English. Disjunction is called something different in Polish (unless someone really wants to sound smart) and I get confused all the time.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
I thought I'd add something. Let for i=1,...,n be defined in the usual way. Every vector has a unique decomposition
which is easily proven. So it's not that there are no such bases. This one does actually satisfy the linearalgebraic independence condition, but does too, in and yet it doesn't yield unique decompositions.
edit: , and not

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
If no one is replying because I wasn't clear enough, please tell me. I will try to make myself clearer.
Anyway, perhaps you could help me with my web search. I'm not sure if I'm using the correct terms. Is the structure defined above a semimodule over the semiring
Is there an unambiguous name for this semiring? I think it's called a boolean algebra, but I understand this term is ambiguous.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
hi,
first we must show that the space has dimension equal to n.
and then :
we know that every (n independent vectors) represent a base for the space. (the base have a property that every vector from a space can be writen uniquely withe the basis)
thus, the condition is : the vectors u(1) ... u(n) must be independent.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
let be,
n vectors from
we can easily proove that span the space
and are independent => the dimension equal (n)

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Salim, the problem is that this space is not a linear space. How do you define independence and dimension in this space?

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
in the problem is set that s={1,0}^n is vector space?
can you tell me what are the (+,*) operations for this vector space???

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

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
as i think you have recognized ymar, the problem lies in the fact that you only have a boolean algebra, and not a vector space. in particular, {0,1} is not a group under , because there is no inverse for 1. because of this peculiar behavior, linear independence is not a strong enough condition to guarantee the unique decompostion you seek.
i believe the structure you are after is "an idempotent semimodule", although "boolean semimodule" may also turn up some results for you.
a definition i saw of independence was: X is independent if where is the set of linear combinations of X.
the trouble with your set is that , for example is not realizable as any linear combination:
, but then .
this is in stark contrast to linear algebra where a 3element linearly independent set necessarily spans a 3dimensional space.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Thank you, Deveno. This was very helpful. Especially the names of the structure! Now I see that there are lots of papers about it. I was about to believe that no one has tried to do research on them! I'll be looking at them and doing some thinking, and if I have any problems, I'll post here again.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
In case anyone's interested, I have found the following theorem:
Proposition Every Boolean semimodule U has a unique basis.
It's here.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
i think idempotent semimodule bases are unique up to scalability, so if the underlying semiring has only two elements, should be the only possible basis for .
i did not see a proof in the link you posted, just the statement of it.

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}
Quote:
Originally Posted by
Deveno i think idempotent semimodule bases are unique up to scalability, so if the underlying semiring has only two elements,
should be the only possible basis for
.
i did not see a proof in the link you posted, just the statement of it.
I don't see it either. I'm going to try to prove it when I have some free time. Do you think I can manage? I'm after a first course in algebra.