Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to specify a structure that has the basic features of a Boolean algebra but not necessarily restricted to binary sets. However, I observed that I almost have a field except that adding/multiplying the inverse ($-a = a^{-1} =: \bar a$) yields the multiplicative/additive inverse ($a \cdot \bar a = 0$, $a + \bar a = 1$ where I interpret "and" as $\cdot$ and "or" as $+$).

To be more precise: My structure $S$ must satisfy the following:

$(S, +, 0)\text{ is an abelian monoid}$
$(S, \cdot, 1)\text{ is an abelian monoid}$
$\cdot\text{ distributes over }+$
$+\text{ distributes over }\cdot$
$\forall a \in S \exists \bar a \in S:\quad a + \bar a = 1 \;\wedge\; a \cdot \bar a = 0 \;\wedge\; \bar{\bar a} = a$
$\forall a,b \in S:\quad a\cdot(a+b) = a \;\wedge\; a+(a\cdot b) = a$

Is there a name for this structure or am I doing something wrong?

share|improve this question
1  
So how does what you have differ from an ordinary Boolean algebra? Are you omitting one of the distributive laws? –  Henning Makholm Oct 3 '11 at 16:49
1  
I think you are doing something wrong, or have accidentally interchanged the symbols $+$ and $\cdot$, since $a\cdot a^{-1}$ is always equal to $1$. (Hence you would need $1=0$) –  Eric Naslund Oct 3 '11 at 16:54
1  
@bitmask: I think you are looking at a complemented lattice, but you'll need to be a bit more precise in terms of what conditions you are placing on your operations. –  Arturo Magidin Oct 3 '11 at 16:58
1  
@Henning Makholm: In the sense, that I assume(d) that a boolean algebra is only applicable over a binary set that contains exactly 0 and 1. But I'm beginning to suspect, that I'm barking up the wrong tree. Am I? –  bitmask Oct 3 '11 at 17:00
3  
This question, as it stands, is unanswerable because it is not precise. Bitmask, please: try to turn it into one that can be answered. –  Mariano Suárez-Alvarez Oct 3 '11 at 17:27
show 10 more comments

1 Answer

up vote 4 down vote accepted

A set $A$ together with operations $+$ and $\cdot$ that satisfy your conditions will be a boolean algebra under the operations $\oplus$ and $\otimes$ given by $$a\oplus b = (a+b)\cdot (\overline{ab}),\quad a\otimes b = a\cdot b.$$

The only sticking points were the idempotency laws, and you've explained how to get them from your conditions.

Conversely, a Boolean algebra $(A,\oplus,\otimes)$ will satisfy the conditions you ask by defining $$a+b = (a\oplus b) - (a\otimes b),\quad a\cdot b = a\otimes b,\quad \overline{a} = 1-a.$$

So your structure is essentially equivalent to a boolean algebra, which in turn is essentially equivalent to a complemented and distributive lattice.

You state in the comments that you believe it will be a complete lattice. I do not think this is the case. Binary operations give you a way to talk about finitary derived operations, but it makes no sense to talk about "series" or "infinite products" (which you would probably need to define joins and meets of arbitrary sets) in the abstract. Certainly, there are complemented distributive lattices that are not complete; they will provide examples where your conditions hold but that are not complete lattices.

(It seems the comment was rather the result of misuse of terminology, though.)

Added. An example of a complemented distributive lattice that is not complete is given by the collection of all Borel subsets of the real line; that is, let $S$ be the $\sigma$-algebra of Borel subsets of $\mathbb{R}$, let $+$ denote union, let $\cdot$ denote intersection, and let $\overline{a}$ denote complementation in $\mathbb{R}$. Then $(S,+,\emptyset)$ is a monoid, since the union of two Borel sets is Borel; $(S,\cdot,\mathbb{R})$ is a monoid, since the intersection of two Borel subsets is Borel. Since union distributes over intersection and vice versa, $+$ distributes over $\cdot$ and $\cdot$ distributes over $+$. For every Borel subset $a$, $a\cup \overline{a} = \mathbb{R}$ and $a\cap \overline{a} = \emptyset$. And for all Borel subsets $a$ and $b$, $a\cap(a\cup b) = a$, $a\cup(a\cap b) = b$. So the Borel subsets satisfy your conditions; they form a distributive complemented lattice under the operations of union and intersection. But they are not a complete lattice, because they are not closed under arbitrary unions. If we let $A$ be a subset of $\mathbb{R}$ that is not a Borel subset (e.g., a Vitali set), then the family of singletons taken from $A$ has no least upper bound in the collection of Borel subsets: given any Borel subset that contains $A$, the set must properly contain $A$, so you can always "throw away" a single point, showing the set is not a least upper bound.

share|improve this answer
    
But if I have both monoids (together with the restriction that the complement is in the set), you cannot break out of the set, can you? So why is it not complete? –  bitmask Oct 3 '11 at 18:33
    
@bitmask: Completeness requires that the join (and meet) of an arbitrary subset lies in the subset. The operations only give you pairwise (and hence finite) joins and meets. How do you even define an "infinite product" or an "infinite sum"? They need not make sense at all, so you cannot assert that such a thing. For instance, consider the collection of all Borel subsets of $\mathbb{R}$, with $\oplus$ the symmetric difference, $\otimes$ the intersection, and $\overline{\ }$ complementation. This is a Boolean algebra, but is not complete (not closed under arbitrary intersections). –  Arturo Magidin Oct 3 '11 at 18:44
    
I'm sorry, but I don't get it (I'm afraid I used the wrong word). I just want that for all $a, b \in S$ we also have that $a \cdot b \in S$, $a + b \in S$ and $\bar a \in S$. Are we talking about the same thing? Shouldn't that be guaranteed by the condition that we have two monoids? –  bitmask Oct 3 '11 at 18:50
1  
@bitmask: No, you're not talking about the same thing :-). That's closure; you want the set to be closed under these operations. Completeness refers to joins and meets of infinite subsets. –  joriki Oct 3 '11 at 18:53
    
@bitmask: That's not what a "complete lattice" is. A complete lattice is a lattice in which you can take the join/meet of any subset, not just finite subsets. What you are talking about is simply "closure", and has nothing to do with completeness of a lattice. –  Arturo Magidin Oct 3 '11 at 18:53
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.