You are here
Homecomplemented lattice
Primary tabs
complemented lattice
Let $L$ be a bounded lattice (with $0$ and $1$), and $a\in L$. A complement of $a$ is an element $b\in L$ such that
$a\land b=0$ and $a\lor b=1$.
Remark. Complements may not exist. If $L$ is a nontrivial chain, then no element (other than $0$ and $1$) has a complement. This also shows that if $a$ is a complement of a nontrivial element $b$, then $a$ and $b$ form an antichain.
An element in a bounded lattice is complemented if it has a complement. A complemented lattice is a bounded lattice in which every element is complemented.
Remarks.

In a complemented lattice, there may be more than one complement corresponding to each element. Two elements are said to be related, or perspective if they have a common complement. For example, the following lattice is complemented.
$\xymatrix{&1\ar@{}[ld]\ar@{}[d]\ar@{}[rd]&\\ a\ar@{}[rd]&b\ar@{}[d]&c\ar@{}[ld]\\ &0&}$ Note that none of the nontrivial elements have unique complements. Any two nontrivial elements are related via the third.

If a complemented lattice $L$ is a distributive lattice, then $L$ is uniquely complemented (in fact, a Boolean lattice). For if $y_{1}$ and $y_{2}$ are two complements of $x$, then
$y_{2}=1\land y_{2}=(x\lor y_{1})\land y_{2}=(x\land y_{2})\lor(y_{1}\land y_{2% })=0\lor(y_{1}\land y_{2})=y_{1}\land y_{2}.$ Similarly, $y_{1}=y_{2}\land y_{1}$. So $y_{2}=y_{1}$.
Mathematics Subject Classification
06C15 no label found06B05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new image: informationtheoreticdistributedmeasurement4.2 by rspuzio
new image: informationtheoreticdistributedmeasurement4.1 by rspuzio
new image: informationtheoreticdistributedmeasurement3.2 by rspuzio
new image: informationtheoreticdistributedmeasurement3.1 by rspuzio
new image: informationtheoreticdistributedmeasurement2.1 by rspuzio
Apr 19
new collection: On the InformationTheoretic Structure of Distributed Measurements by rspuzio
Apr 15
new question: Prove a formula is part of the Gentzen System by LadyAnne
Mar 30
new question: A problem about Euler's totient function by mbhatia
new problem: Problem: Show that phi(a^n1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia
new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz
Comments
Lattices and power sets
Hi!
A small question:
Which additional properties are necessary/sufficient to make a lattice $(L, <)$ isomorphic to a power set (\Pot(M), \subsetneq)?
Ok, the following properties are necessary:
 complete (every subset has an infimum and a supremum)
 complemented
 distributive
But what set of properties is sufficient?
Re: Lattices and power sets
A complemented distributive lattice is a Boolean algebra. A complete Boolean algebra A is lattice isomorphic to the power set of some set S if A is atomic (every element of A has an atom below it). You can show that S is in fact the set of all atoms of A. Check out the book Intro to Lattices and Order by Davey and Priestley.
Re: Lattices and power sets
Ok, so this would mean, a lattice that is
 complete and
 complemented and
 distributive and
 atomic
is orderisomorphic to a power set. Any such isomorphism will identify the atoms of the lattice with the singletons of the power set.
Are all the four requirements are necessary? Don't have the book at hand...
Re: Lattices and power sets
I think so. I saw a counterexample in the book if, say, the atomic condition is dropped. I'll find out.
Re: Lattices and power sets
I found the counterexample:
Consider the power set of the reals R. Consider the Boolean subalgebra A of R generated by the following intervals
(oo, a)
[b,c}
[d,oo)
empty set
where a,b,c,d are reals.
Then A is complete and atomless, and A is not lattice isomorphic to any power set of a set.
Re: Lattices and power sets
Hi, thanks, but..
Sorry I don't get it!
Do you mean a < b < c < d ?
Do you mean A \subseteq R or A \subseteq \Pot(R) ?
With (oo, a), [b, c), [d, oo) \in A ?
or (oo, a), [b, c), [d, oo) \subseteq A ?
Maybe a supgenerated subset of the power set \Pot(R) ??
Regards, Schneemann.
Re: Lattices and power sets
Sorry for the sloppiness. First, a, b, c, d are arbitrary real numbers, there are no specific orderings on these numbers. Second, the Boolean subalgebra A I am refering to is the set of all finite unions of those intervals that I mentioned. You can show that A is indeed a Boolean algebra under union and intersection and complementation, etc... Furthermore, it is complete. You can derive that A is atomless by using a proof of contradiction.
Re: Lattices and power sets
At the beginning I thought you mean a, b, c, d to be fixed numbers. I'm still not sure, but now I think you mean this set:
S := { (oo,b)  b in RR }
cup { [a, b)  a, b in RR }
cup { [a,oo)  a in RR }
cup { emptyset }
Now A is generated from S by building finite unions.. right? Ok, I'll think about that. Thanks!
Regards. Schneemann