Complementation=orthocomplementation? (Distributive lattices)

  • Thread starter Fredrik
  • Start date
In summary, we discussed the definition of a lattice and its properties, including the least upper bound and greatest lower bound. We also talked about bounded lattices and distributive lattices. We then introduced the concept of complementation and orthocomplementation in bounded lattices and how they relate to each other. We proved that on a distributive, bounded lattice, complementation is equivalent to orthocomplementation. We also showed how DeMorgan's laws hold in a bounded, distributive, and complemented lattice. Finally, we discussed the uniqueness of relative complementation and its equivalence to distributivity.
  • #1
Fredrik
Staff Emeritus
Science Advisor
Gold Member
10,877
422
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).
\end{align}
[/tex] A complementation is a unary operation (on a bounded lattice) [itex]a\mapsto a^\circ[/itex] such that for all a,b, [tex]
\begin{align}
\text{(1)} & a^\circ{}^\circ=a\\
\text{(2)} & a\wedge a^\circ=0\text{ and }a\vee a^\circ =1
\end{align}
[/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]
\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}[/tex] which make me think that the condition that defines an orthocomplementation is equivalent to de Morgan's laws.
 
Physics news on Phys.org
  • #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:
  • #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.
 
  • #4
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:
  • #5


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.
 

Related to Complementation=orthocomplementation? (Distributive lattices)

1. What is complementation in distributive lattices?

Complementation is a mathematical operation in distributive lattices that involves finding the element that, when combined with a given element, results in the identity element (e.g. 0 for join operation and 1 for meet operation). In simpler terms, it is the inverse operation of join (or meet) in a distributive lattice.

2. What is orthocomplementation in distributive lattices?

Orthocomplementation is a special type of complementation in distributive lattices where the element's complement is unique and can be determined by a specific rule (e.g. De Morgan's law). It is commonly found in Boolean algebras, which are a type of distributive lattice.

3. How does complementation and orthocomplementation relate to each other?

In distributive lattices, complementation and orthocomplementation are closely related as orthocomplementation can be seen as a special case of complementation. Orthocomplementation is a more specific type of complementation that satisfies additional properties such as uniqueness and De Morgan's law.

4. What are the applications of complementation and orthocomplementation in science?

Complementation and orthocomplementation have various applications in science, particularly in fields that involve logical reasoning and set theory. They are commonly used in computer science, quantum mechanics, and formal logic to name a few.

5. Are complementation and orthocomplementation the same in all types of lattices?

No, complementation and orthocomplementation may differ in different types of lattices. For example, in non-distributive lattices, orthocomplementation may not satisfy De Morgan's law, making it different from complementation. It is important to consider the type of lattice when discussing complementation and orthocomplementation.

Similar threads

  • Linear and Abstract Algebra
Replies
18
Views
1K
Replies
4
Views
279
  • Introductory Physics Homework Help
Replies
20
Views
422
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
0
Views
535
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Replies
3
Views
299
  • Linear and Abstract Algebra
Replies
15
Views
1K
  • Linear and Abstract Algebra
Replies
23
Views
2K
  • Linear and Abstract Algebra
Replies
10
Views
1K
Back
Top