Complementation=orthocomplementation? (Distributive lattices)

[Fredrik]

A lattice is a partially ordered set such that every finite set has a least upper bound and a greatest lower bound. The least upper bound of the set {a,b} is denoted by $a\vee b$. The greatest lower bound of the same set is denoted by $a\wedge b$. A lattice is said to be bounded if it has a smallest member and a largest member. They are denoted by 0 and 1 respectively. A lattice is said to be distributive if for all a,b,c, $$\begin{align} a\wedge(b\vee c) &=(a\wedge b)\vee(a\wedge c)\\ a\vee(b\wedge c) &=(a\vee b)\wedge(a\vee c). \end{align}$$ A complementation is a unary operation (on a bounded lattice) $a\mapsto a^\circ$ such that for all a,b, $$\begin{align} \text{(1)} & a^\circ{}^\circ=a\\ \text{(2)} & a\wedge a^\circ=0\text{ and }a\vee a^\circ =1 \end{align}$$ An orthocomplementation is a complementation that satisfies the additional requirement $$\text{(3)}\ a\leq b\ \Rightarrow\ b^\circ\leq a^\circ.$$ I want to know if the following two statements (found in two different books) are equivalent:

1. A complemented distributive lattice is called a Boolean algebra.
2. An orthocomplemented distributive lattice is called a Boolean algebra.

Every orthocomplementation is obviously a complementation. Is it possible to prove that every complementation (on a distributive lattice) is an orthocomplementation?

I haven't made much progress. I just noticed the equivalences $$\begin{align} a\leq b\ &\Leftrightarrow\ a\wedge b=a,\ a\vee b=b\\ b^\circ\leq a^\circ\ &\Leftrightarrow a^\circ\wedge b^\circ =b^\circ,\ a^\circ\vee b^\circ=a^\circ, \end{align}$$ which make me think that the condition that defines an orthocomplementation is equivalent to de Morgan's laws.

 

[micromass]

Hi Frederik!

On a distributive, bounded lattice, you are correct that complementation is orthocomplementation. The point is complementation is unique in distributive lattices (if it exists), that is: for all a, there exists at most one b such that

$$a\wedge b=0~\text{and}~a\vee b=1$$

The proof is not so difficult: take b and c that both satisfy the above law, then

$$b=b\wedge 1=b\wedge (a\vee c)=(b\wedge a)\vee (b\wedge c)=b\wedge c$$

Thus it follows that $b\leq c$. Analogously, we prove that $c\leq b$ and thus b=c.

Note that the condition $a^{\circ \circ}=a$ is automatically satisfied on a distributive lattice. Indeed, we have by definition that $a^{\circ \circ}\wedge a^\circ =0$and $a^{\circ \circ}\vee a^\circ =1$. But by uniqueness, we have that $a^{\circ \circ}=a$.​

OK, now we prove that the DeMorgan Laws hold in a bounded, distributive, complemented lattice. This is very easy. It suffices to show that

$$(a\wedge b)\wedge (a^\circ \vee b^\circ)=0~\text{and}~(a\wedge b)\vee (a^\circ \vee b^\circ )=1$$

and by uniqueness it follows immediately that $(a\wedge b)^\circ=a^\circ \vee b^\circ$.

OK, now we can show that complementation is orthocomplementation:

$$a\leq b~\Leftrightarrow~a=b\wedge a~\Leftrightarrow~a^\circ=b^\circ\vee a^\circ~\Leftrightarrow~b^\circ\leq a^\circ$$

 

[micromass]

Note also that the following holds on distributive lattices:

If b and c are such that

$$a\wedge b=r~\text{and}~a\vee b=s$$

and if

$$a\wedge c=r~\text{and}~a\vee c=s$$

then b=c. We say that "relative complementation is unique (if it exists)". We have used this in the case r=0 and s=1.

The interesting part is that the above is equivalent to distributivity! This follows from the famous pentagon-diamant theorem.

 

[Fredrik]

Thank you very much. I seem to be able to save a lot of time the days that you're around. If I had money, I would do a lot less thinking and hire you to do the rest.

I had already studied the proof that complements are unique in distributive lattices, but for some reason it didn't occur to me to use that uniqueness the way you did. It seems really obvious now that I've seen it.

 

[blue_raver22]

First, let's define de Morgan's laws in terms of the lattice operations:
\begin{align}
(a\vee b)^\circ &= a^\circ\wedge b^\circ\\
(a\wedge b)^\circ &= a^\circ\vee b^\circ
\end{align}

Now, let's assume we have a complementation on a distributive lattice, denoted by the unary operation a\mapsto a^\circ. We can prove that this complementation is also an orthocomplementation by showing that it satisfies the conditions \text{(1)}, \text{(2)}, and \text{(3)}.

\textbf{Condition (1):} We can easily see that this condition holds since a\wedge a = a\vee a = a for any element a in a distributive lattice.

\textbf{Condition (2):} Since we have a complementation, we know that a\wedge a^\circ = 0 and a\vee a^\circ = 1 for any element a in the lattice. This satisfies the conditions for de Morgan's laws, which means that a^\circ is the complement of a in terms of lattice operations.

\textbf{Condition (3):} Now, let's assume that a\leq b. This means that a\wedge b = a and a\vee b = b. Using de Morgan's laws, we have:
\begin{align}
b^\circ &= (a\vee b)^\circ\\
&= (a^\circ\wedge b^\circ)^\circ\\
&= (a^\circ)^\circ\vee (b^\circ)^\circ\\
&= a\vee b^\circ
\end{align}
Similarly, we can show that a^\circ\leq b^\circ. This satisfies the condition \text{(3)} for an orthocomplementation.

Therefore, we can conclude that every complementation on a distributive lattice is also an orthocomplementation, and the two statements in the books are equivalent.