Take the 2-minute tour ×

The story is that in a lattice, there are some elements incomparable, and there exits some elements have overlapping elements. for example, suppose the partial order is defined on inclusion, then e1= {a,b} and e2 = {b,c}, they are incomparable, but they have common element b.

Thus, for this kind of lattice elements, I want to be able to compute the difference between A and B say A - B.. What I can do is that I can define the complementation of the element in the lattice which A - B = A meet complementation of B.

Therefore, my question is that, how to define the subtraction operation in lattice? If I define the subtract with respect of complementation, then how can I actually compute it? I mean I can define the complementation of A is A', where A join A' = top and A meet A' = bot. But this does not give me much information how to actually compute the complementation!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Well, you shouldn't expect to be able to compute the complement in an abstract lattice, because all we're guaranteed in the existence of meets and joins. But from earlier in your question, it seems that you're mostly asking about lattices of sets.

In that case, if Top exists it's a set $X$ and the complement of $A$ is simply $X-A$. Caveat: it's perfectly possible to define a lattice containing $A$ but not $X-A$, but if $X-A$ is in the lattice for every $A$ we say we're working in a complemented lattice; in the case of a lattice of sets with top and bottom, this is even a Boolean algebra.

If the complemented lattice is not of sets, as long as it's bounded and distributive we can show there's only one element $A'$ for each $A$ such that $A$ meet $A'$ is Bottom and $A$ join $A'$ is Top.

If we're in a lattice of sets not bounded above, then we can still define subtraction even without complementation: $A-B$ is just the maximal subset of $A$ which doesn't intersect $B$. A lattice with subtraction must have a bottom, though, since we can define $A-A$.

share|improve this answer
Thanks for your explanation!! Now let's talk bounded distributed lattice. 1. In a complemented lattice, so every A can has at least one complementation? In other words, the complementation of A in complemented lattice is not uniquely defined? 2. Following up point 1, is there the maximum complementation of A? or the least upper bound of A's complementation? –  monica Oct 1 '12 at 5:23
Sorry, I think my description of the follow up questions were wrong. e.g. for point 1, if it is bounded and distributive lattice, you have said A's complementation is uniquely defined~~ But then is there possibility that any element's complementation has at least one complementation and thus has the least upper bound complementation? –  monica Oct 1 '12 at 5:38
In a bounded distributive complemented lattice, the complement operation is called an "involution:" that just means that $A$ is the unique complement of $A$'s complement. Does that answer your question? –  Kevin Carlson Oct 1 '12 at 16:20
I noticed this fact from your previous explanation :) Thanks! My follow up question is that if in some kind of lattice, every element has at least one its complementation, then is there some kind of notion of least upper bound of an element's complementation? Is there some specific terms for this kind of lattice? –  monica Oct 1 '12 at 17:41
Well, in a complete lattice every set of elements has a sup. In general I don't have anything to say except that I imagine you could construct a non-distributive lattice when an element with multiple complements and no greatest complement, and you could probably also come up with an incomplete lattice in which every set of complements does have a least upper bound-though the latter seems trickier. –  Kevin Carlson Oct 1 '12 at 17:59

Your Answer


