3
$\begingroup$

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?

  • 1
    So how does what you have differ from an ordinary Boolean algebra? Are you omitting one of the distributive laws?2011-10-03
  • 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$)2011-10-03
  • 1
    @bitmask: I think you are looking at a [complemented lattice](http://en.wikipedia.org/wiki/Complemented_lattice), but you'll need to be a bit more precise in terms of what conditions you are placing on your operations.2011-10-03
  • 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?2011-10-03
  • 0
    @Arturo Magidin: In terms of a lattice, I think I have a *complete distributive complemented lattice*. At least what I can find in the definitions from Wikipedia seem to match my requirements. I think the question boils down to: Is *that* the same as a boolean algebra?2011-10-03
  • 0
    @bitmask, a [Boolean algebra](http://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29) can have more than two elements. The main example besides truth values is the Boolean algebra of all subsets of a given base set.2011-10-03
  • 0
    @bitmask: Like I said: *you need to be precise as to what conditions you are placing on your operations*. Boolean algebras and distributive complemented lattices are "the same thing", in the sense that a boolean algebra can be given a canonical structure of distributive complemented lattice; and every complemented lattice can be given a canonical structure as a boolean algebra; and if you start with a boolean algebra and look at the boolean algebra structure of its lattice structure you get back your original, and likewise if you start with a lattice. But "completeness" is usually "extra."2011-10-03
  • 0
    @Arturo Magidin: You know, I cannot accept a comment, right? (Thanks by the way)2011-10-03
  • 0
    @bitmask: You know, you haven't been precise enough for a definitive answer, right? But if you aren't going to do anything else to clarify your question...2011-10-03
  • 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.2011-10-03
  • 0
    @Arturo Magidin, Mariano Suárez-Alvarez: I tried to make the requirements more precise. Please tell me if you need more information.2011-10-03
  • 0
    @bitmask: Are those really *all* the conditions? You don't require idempotence of $+$ and $\cdot$? You don't require the absorption laws? (And how did you get from the rules you are describing to completeness?)2011-10-03
  • 0
    @Arturo Magidin: Doesn't that follow from my last condition together with $a+0 = a$ and $a\cdot 1 = a$? (I got to completeness, because of the monoids)2011-10-03
  • 0
    @Arturo Magidin: $a = a\cdot(a+0) = a\cdot a$ and $a = a+(a\cdot 1) = a+a$2011-10-03
  • 0
    @bitmask: Yes, it was; sorry about that.2011-10-03

1 Answers 1

4

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.

  • 0
    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?2011-10-03
  • 0
    @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).2011-10-03
  • 0
    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?2011-10-03
  • 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.2011-10-03
  • 0
    @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.2011-10-03
  • 0
    @joriki, Arturo Magidin: In that case, I apologise for the confusion and will go with *boolean algebra*.2011-10-03
  • 0
    Could you explain why bitmask's "$+$" does not work as the join of a Boolean algebra? Or are you using a axiomatization of "Boolean algebra" where you want $1\oplus 1=0$? The one I'm familiar with has two operators that are each other's de Morgan duals.2011-10-03
  • 0
    @Hanning: Yes, I am refering the axiomatization of Boolean algebra in which it is a ring under the addition, rather than the axiomatization in which the operations are the join and meets of the lattice structure. Bitmask's $+$ works as the joins, and $\cdot$ as the meet. The definitions I give for $\oplus$ and $\otimes$ are the standard way to go from the lattice presentation to the boolean ring/algebra presentation.2011-10-04