The canonical example of a complemented lattice in discrete mathematics is the power set of a finite set, ordered by the subset relation. This structure is also a Boolean algebra, which is a specific type of complemented, distributive lattice.
A complemented lattice is a bounded lattice where every element has at least one complement. To fully understand this, we need to break down the definitions and then apply them to the power set example.
Understanding the fundamentals
Bounded lattices
A lattice is a partially ordered set where every pair of elements has a unique greatest lower bound (GLB) and a unique least upper bound (LUB).
-
The GLB, or meet, of two elements aa
π
and bb
π
is the largest element that is less than or equal to both aa
π
and bb
π
, denoted as aβ§ba logical and b
πβ§π
.
-
The LUB, or join, is the smallest element that is greater than or equal to both aa
π
and bb
π
, denoted as aβ¨ba logical or b
πβ¨π
.
A lattice is bounded if it has a unique least element, denoted 00
0
, and a unique greatest element, denoted 11
1
.
Complements
In a bounded lattice, an element yy
π¦
is called a complement of an element xx
π₯
if they satisfy the following two conditions:
-
**Meet with complement:**xβ§y=0x logical and y equals 0
π₯β§π¦=0
-
**Join with complement:**xβ¨y=1x logical or y equals 1
π₯β¨π¦=1
A lattice is a complemented lattice if it is bounded and every element in the lattice has at least one complement. Importantly, complements are not always unique in a complemented lattice, although they are in the case of a Boolean algebra.
The power set example
Let's take a finite set, for example, S={a,b,c}cap S equals the set a comma b comma c end-set
π={π,π,π}
. The power set of Scap S
π
, denoted P(S)script cap P open paren cap S close paren
π«(π)
, is the set of all subsets of Scap S
π
.
P(S)={β ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}script cap P open paren cap S close paren equals the set the empty set comma the set a end-set comma the set b end-set comma the set c end-set comma the set a comma b end-set comma the set a comma c end-set comma the set b comma c end-set comma the set a comma b comma c end-set end-set
π«(π)={β ,{π},{π},{π},{π,π},{π,π},{π,π},{π,π,π}}
We can define a lattice on this power set by using the subset relation (βis a subset of or equal to
β
) as the partial order. In this lattice, the meet and join operations correspond to the set operations of intersection (β©intersection
β©
) and union (βͺunion
βͺ
), respectively.
Demonstrating a bounded lattice
To show that P(S)script cap P open paren cap S close paren
π«(π)
is a bounded lattice, we must identify its least and greatest elements, and confirm the existence of meets and joins for any pair of subsets.
-
**Least element (00
0
):** The least element is the empty set, β the empty set
β
. It is a subset of every other set in P(S)script cap P open paren cap S close paren
π«(π)
. For any set AβP(S)cap A is an element of script cap P open paren cap S close paren
π΄βπ«(π)
, β β©A=β the empty set intersection cap A equals the empty set
β β©π΄=β
and β βͺA=Athe empty set union cap A equals cap A
β βͺπ΄=π΄
.
-
**Greatest element (11
1
):** The greatest element is the set S={a,b,c}cap S equals the set a comma b comma c end-set
π={π,π,π}
. Every other set in P(S)script cap P open paren cap S close paren
π«(π)
is a subset of Scap S
π
. For any set AβP(S)cap A is an element of script cap P open paren cap S close paren
π΄βπ«(π)
, Aβ©S=Acap A intersection cap S equals cap A
π΄β©π=π΄
and AβͺS=Scap A union cap S equals cap S
π΄βͺπ=π
.
Thus, the power set lattice is bounded.
Demonstrating complements
To prove that P(S)script cap P open paren cap S close paren
π«(π)
is a complemented lattice, we must show that every element has a complement. In this case, the complement of a subset Acap A
π΄
is its set-theoretic complement, Accap A to the c-th power
π΄π
, which is the set of all elements in Scap S
π
that are not in Acap A
π΄
. Let's verify this for a few examples:
-
**Element {a}the set a end-set
{π}
:**
-
The complement is {a}c=Sβ{a}={b,c}the set a end-set to the c-th power equals cap S β the set a end-set equals the set b comma c end-set
{π}π=πβ{π}={π,π}
.
-
Meet:{a}β©{b,c}=β the set a end-set intersection the set b comma c end-set equals the empty set
{π}β©{π,π}=β
, which is the least element.
-
Join:{a}βͺ{b,c}={a,b,c}the set a end-set union the set b comma c end-set equals the set a comma b comma c end-set
{π}βͺ{π,π}={π,π,π}
, which is the greatest element.
-
So, {b,c}the set b comma c end-set
{π,π}
is the complement of {a}the set a end-set
{π}
.
-
-
**Element {a,c}the set a comma c end-set
{π,π}
:**
-
The complement is {a,c}c=Sβ{a,c}={b}the set a comma c end-set to the c-th power equals cap S β the set a comma c end-set equals the set b end-set
{π,π}π=πβ{π,π}={π}
.
-
Meet:{a,c}β©{b}=β the set a comma c end-set intersection the set b end-set equals the empty set
{π,π}β©{π}=β
, the least element.
-
Join:{a,c}βͺ{b}={a,b,c}the set a comma c end-set union the set b end-set equals the set a comma b comma c end-set
{π,π}βͺ{π}={π,π,π}
, the greatest element.
-
So, {b}the set b end-set
{π}
is the complement of {a,c}the set a comma c end-set
{π,π}
.
-
-
**Element β the empty set
β
:**
-
The complement is β c=Sββ =Sthe empty set to the c-th power equals cap S β the empty set equals cap S
β π=πββ =π
.
-
Meet:β β©S=β the empty set intersection cap S equals the empty set
β β©π=β
.
-
Join:β βͺS=Sthe empty set union cap S equals cap S
β βͺπ=π
.
-
So, Scap S
π
is the complement of β the empty set
β
.
-
For any subset AβP(S)cap A is an element of script cap P open paren cap S close paren
π΄βπ«(π)
, its set-theoretic complement Accap A to the c-th power
π΄π
will satisfy the required conditions because Aβ©Ac=β cap A intersection cap A to the c-th power equals the empty set
π΄β©π΄π=β
and AβͺAc=Scap A union cap A to the c-th power equals cap S
π΄βͺπ΄π=π
. Therefore, every element in the power set lattice has a complement, making it a complemented lattice.
The connection to Boolean algebras
The power set lattice is not just a complemented lattice; it is also a distributive lattice, meaning it satisfies the distributive laws:Aβ©(BβͺC)=(Aβ©B)βͺ(Aβ©C)cap A intersection open paren cap B union cap C close paren equals open paren cap A intersection cap B close paren union open paren cap A intersection cap C close paren
π΄β©(π΅βͺπΆ)=(π΄β©π΅)βͺ(π΄β©πΆ)
Aβͺ(Bβ©C)=(AβͺB)β©(AβͺC)cap A union open paren cap B intersection cap C close paren equals open paren cap A union cap B close paren intersection open paren cap A union cap C close paren
π΄βͺ(π΅β©πΆ)=(π΄βͺπ΅)β©(π΄βͺπΆ)
A complemented and distributive lattice is called a Boolean algebra. In a Boolean algebra, every element has a unique complement. Since the set-theoretic complement is always unique, the power set lattice is a perfect example of a Boolean algebra, which is a specific and widely used type of complemented lattice.
Other examples of complemented lattices
While the power set is the most accessible example, other important complemented lattices exist. Some are distributive, like the power set, while others are not, demonstrating that complements do not necessarily guarantee distributivity.
The lattice of divisors (Dncap D sub n
π·π
)
For a positive integer nn
π
, the set of its positive divisors, Dncap D sub n
π·π
, forms a lattice under the divisibility relation. The GLB is the greatest common divisor (GCD), and the LUB is the least common multiple (LCM). This lattice is complemented if and only if nn
π
is square-free.
Let's examine D6={1,2,3,6}cap D sub 6 equals the set 1 comma 2 comma 3 comma 6 end-set
π·6={1,2,3,6}
.
-
**Least element (00
0
):**11
1
-
**Greatest element (11
1
):**66
6
Let's find the complements:
-
**Element 22
2
:**
-
We need to find xx
π₯
such that gcd(2,x)=1gcd open paren 2 comma x close paren equals 1
gcd(2,π₯)=1
and lcm(2,x)=6lcm open paren 2 comma x close paren equals 6
lcm(2,π₯)=6
.
-
gcd(2,3)=1gcd open paren 2 comma 3 close paren equals 1
gcd(2,3)=1
and lcm(2,3)=6lcm open paren 2 comma 3 close paren equals 6
lcm(2,3)=6
.
-
So, 33
3
is the complement of 22
2
.
-
-
**Element 33
3
:**
-
Similarly, 22
2
is the complement of 33
3
.
-
-
**Element 11
1
:**
-
The complement is 66
6
.
-
-
**Element 66
6
:**
-
The complement is 11
1
.
-
Since every element has a complement, D6cap D sub 6
π·6
is a complemented lattice. Because 6=2Γ36 equals 2 cross 3
6=2Γ3
is square-free, it is also a distributive lattice (and therefore a Boolean algebra).
Now consider D12={1,2,3,4,6,12}cap D sub 12 equals the set 1 comma 2 comma 3 comma 4 comma 6 comma 12 end-set
π·12={1,2,3,4,6,12}
, which is not square-free (12=22Γ312 equals 2 squared cross 3
12=22Γ3
).
-
**Least element (00
0
):**11
1
-
**Greatest element (11
1
):**1212
12
-
Consider the element 44
4
. We need to find xx
π₯
such that gcd(4,x)=1gcd open paren 4 comma x close paren equals 1
gcd(4,π₯)=1
and lcm(4,x)=12lcm open paren 4 comma x close paren equals 12
lcm(4,π₯)=12
.
-
The only element with GCD 11
1
is 11
1
. But lcm(4,1)=4β 12lcm open paren 4 comma 1 close paren equals 4 is not equal to 12
lcm(4,1)=4β 12
.
-
Therefore, 44
4
has no complement in D12cap D sub 12
π·12
, and so D12cap D sub 12
π·12
is not a complemented lattice.
-
The lattice of subspaces of a vector space
For a vector space Vcap V
π
, the set of all subspaces of Vcap V
π
, partially ordered by inclusion, forms a complemented lattice. In this lattice, the meet is the intersection of subspaces, and the join is their vector sum. The least element is the trivial subspace {0}the set 0 end-set
{0}
, and the greatest element is Vcap V
π
itself.
For any subspace Wcap W
π
, its complement is any other subspace Wβ²cap W prime
πβ²
such that Wβ©Wβ²={0}cap W intersection cap W prime equals the set 0 end-set
πβ©πβ²={0}
and W+Wβ²=Vcap W plus cap W prime equals cap V
π+πβ²=π
. From linear algebra, we know that such a subspace Wβ²cap W prime
πβ²
(a complementary subspace) always exists.
This is an important example of a complemented lattice that is not, in general, distributive. For instance, if you consider subspaces of R2R-2
β2
, you can find an example that fails the distributive law. This illustrates that while a distributive complemented lattice is a Boolean algebra, not all complemented lattices are Boolean algebras.