Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complementation=orthocomplementation? (Distributive lattices)

  1. Jun 26, 2011 #1


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 [itex]a\vee b[/itex]. The greatest lower bound of the same set is denoted by [itex]a\wedge b[/itex]. 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, [tex]\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).
    [/tex] A complementation is a unary operation (on a bounded lattice) [itex]a\mapsto a^\circ[/itex] such that for all a,b, [tex]
    \text{(1)} & a^\circ{}^\circ=a\\
    \text{(2)} & a\wedge a^\circ=0\text{ and }a\vee a^\circ =1
    [/tex] An orthocomplementation is a complementation that satisfies the additional requirement [tex]\text{(3)}\ a\leq b\ \Rightarrow\ b^\circ\leq a^\circ.[/tex] 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 [tex]
    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}[/tex] which make me think that the condition that defines an orthocomplementation is equivalent to de Morgan's laws.
  2. jcsd
  3. Jun 26, 2011 #2
    Hi Frederik! :smile:

    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

    [tex]a\wedge b=0~\text{and}~a\vee b=1[/tex]

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

    [tex]b=b\wedge 1=b\wedge (a\vee c)=(b\wedge a)\vee (b\wedge c)=b\wedge c[/tex]

    Thus it follows that [itex]b\leq c[/itex]. Analogously, we prove that [itex]c\leq b[/itex] and thus b=c.

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

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

    [tex](a\wedge b)\wedge (a^\circ \vee b^\circ)=0~\text{and}~(a\wedge b)\vee (a^\circ \vee b^\circ )=1[/tex]

    and by uniqueness it follows immediately that [itex](a\wedge b)^\circ=a^\circ \vee b^\circ[/itex].

    OK, now we can show that complementation is orthocomplementation:

    [tex]a\leq b~\Leftrightarrow~a=b\wedge a~\Leftrightarrow~a^\circ=b^\circ\vee a^\circ~\Leftrightarrow~b^\circ\leq a^\circ[/tex]
    Last edited: Jun 26, 2011
  4. Jun 26, 2011 #3
    Note also that the following holds on distributive lattices:

    If b and c are such that

    [tex]a\wedge b=r~\text{and}~a\vee b=s[/tex]

    and if

    [tex]a\wedge c=r~\text{and}~a\vee c=s[/tex]

    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.
  5. Jun 26, 2011 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    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.
    Last edited: Jun 26, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook