Lattices and Categories
The subsets of a set permit operations quite similar to those performed on numbers.
If for the moment we denote the union of two subsets A, B by A + B and their
intersection by AB, a notation that will not be used later (despite some historical
precedents), then we have laws like AB = BA, A(B + e) = AB + Ae, similar to the
familiar laws of arithmetic, as well as new laws such as A + A = A, A + Be =
(A + B)(A + e). The algebra formed in this way is called a Boolean algebra, after
George Boole who introduced it around the middle of the 19th century, and who
made the interesting observation that Boolean algebras could also be used to describe
the propositions of logic.
The more general notion of a lattice was first used towards the end of the
19th century by Richard Dedekind to study the relations between ideals in rings
of numbers. The lattice concept helps to unify a number of disparate ideas and
this chapter deals with the basic properties of lattices in Sections 3.1 and 3.2 and
Boolean algebras in Section 3.4. The latter have recently found applications in
switching theory, but we shall not enter on this aspect. We shall concentrate on
applications to algebra, and describe such important ideas as chain conditions in
the general setting of partially ordered sets.
Section 3.3 introduces categories, which provide a succinct way of describing
many aspects of groups and are also of use in other parts of algebra.
3.1 Definitions; Modular and Distributive Lattices
The definitions relating to partially ordered sets (see Conventions on Terminology,
p. xi) form the foundation for much that follows. Whereas sets of numbers, like N or
Q, are totally ordered, this property is not shared by most partially ordered sets.
Examples are the set &(S) of all subsets of a set S (with more than one element) rela-
tive to inclusion, or the set N of natural numbers relative to divisibility. In both these
cases any two members have a least upper bound or supremum, briefly sup; given x, y,
there exists z such that (i) x ::: z, y ::: z and (ii) for any z', x ::: z', y ::: z' ::::} z ::: z'.
Dually, any two members have a greatest lower bound or infimum, briefly inf,
defined similarly. Thus if X and Yare subsets of S, their sup is X U Y and their
inf is X n Y. If m, n are natural numbers, their sup (relative to divisibility) is their
least common multiple while their inf is their highest common factor.
51
,52 Lattices and Categories
A partially ordered set in which any two elements have a supremum and an
infimum is called a lattice. The sup of x, y is written x v y and is called the join of
x and y; their inf is written x /\ y and is called the meet of x and y. It is clear that
the lattice concept is self-dual, so that the dual of a lattice, obtained by reversing
the ordering, is again a lattice. As examples of lattices we have the set N of natural
numbers under divisibility, as well as 9(5), the set of all subsets of 5 under inclusion;
further, every totally ordered set is trivially a lattice, with x /\ y = x, x v y = y if
x .:s y.
Partially ordered sets are often represented as directed graphs: the elements of the
set form the vertices, and edges are drawn so that a < b holds precisely when b is
higher than a and there is a descending path from b to a. Such diagrams are
mainly used for finite sets; for N or Z the structure can be hinted at in a partial dia-
gram, but the case of Q or R would be more difficult. Some examples are given in
Figures 3.1-3.3, where Figures 3.1 and 3.2 are lattices, but Figure 3.3 is not.
A lattice may be regarded as a set with two binary operators, V and /\. These
operators satisfy a number of laws, reminiscent of the laws governing addition
and multiplication of numbers, and these laws can be used to give an alternative
definition of lattices.
Figure 3.1
Figure 3.2
, 3.1 Definitions: Modular and Distributive Lattices 53
Figure 3.3
Proposition 3.1.1. Let L be a lattice. Then for any a, b, c E L,
a V (b V c) = (a V b) V c, a /\ (b /\ c) = (a /\ b) /\ c, (associative law) (3.1.1)
a vb = b V a, a /\ b = b /\ a, (commutative law) (3.1.2)
a /\ (a V b) = a, a V (a /\ b) = a, (absorptive law) (3.1.3)
a V a = a, a /\ a = a. (idempotent law) (3.l.4)
Conversely, if L is a set with two binary operators V, /\ satisfying (3.1.1)-(3.1.3), then
(3.1.4) also holds and a partial ordering may be defined on L by the rule
a .:::: b if and only if a V b = b. (3.l.5)
Relative to this ordering L is a lattice such that the join of a, b is a V b and the meet is
a /\ b.
Proof. By the definition of a V b as sup we see that the unique sup of a, b can be
written as either a V b or b V a, and a similar remark applies to a /\ b, so (3.1.2)
follows. Likewise the sup of a, b, c may be written as a V (b V c) or (a V b) V c,
hence (3.1.1) holds. Now (3.1.3) follows because a /\ b .:::: a':::: a V b, and (3.1.4) is
a trivial consequence of the definition, but we observe that it also follows from
(3.1.3): if in the first Equation (3.1.3) we replace b by a /\ a we get
a = a /\ [a V (a /\ a)] = a /\ a, by the second Equation (3.1.3). This proves the
first idempotent law; the second follows by duality.
Now let L be a set with two operators V, /\ satisfying (3.1.1)-(3.1.3); then (3.1.4)
also holds, as we have just seen, and moreover,
a V b = b {} a /\ b = a. (3.l.6)
For if a V b = b, then by (3.1.3), a /\ b = a /\ (a V b) = a, and the converse follows
by duality (and the commutative law (3.1.2)). If we define the relation '.::::' by
(3.1.5), we have a partial ordering: if a .:::: b, b.:::: c, then a V b = b, b V c = c;
hence by (3.1.1), c = b V c = (a V b) V c = a V (b V c) = a V c, so a .:::: c. Further,
a.:::: a by (3.1.4), and if a .:::: b, b.:::: a, then b = a V b = b V a = a, by (3.1.2).
The subsets of a set permit operations quite similar to those performed on numbers.
If for the moment we denote the union of two subsets A, B by A + B and their
intersection by AB, a notation that will not be used later (despite some historical
precedents), then we have laws like AB = BA, A(B + e) = AB + Ae, similar to the
familiar laws of arithmetic, as well as new laws such as A + A = A, A + Be =
(A + B)(A + e). The algebra formed in this way is called a Boolean algebra, after
George Boole who introduced it around the middle of the 19th century, and who
made the interesting observation that Boolean algebras could also be used to describe
the propositions of logic.
The more general notion of a lattice was first used towards the end of the
19th century by Richard Dedekind to study the relations between ideals in rings
of numbers. The lattice concept helps to unify a number of disparate ideas and
this chapter deals with the basic properties of lattices in Sections 3.1 and 3.2 and
Boolean algebras in Section 3.4. The latter have recently found applications in
switching theory, but we shall not enter on this aspect. We shall concentrate on
applications to algebra, and describe such important ideas as chain conditions in
the general setting of partially ordered sets.
Section 3.3 introduces categories, which provide a succinct way of describing
many aspects of groups and are also of use in other parts of algebra.
3.1 Definitions; Modular and Distributive Lattices
The definitions relating to partially ordered sets (see Conventions on Terminology,
p. xi) form the foundation for much that follows. Whereas sets of numbers, like N or
Q, are totally ordered, this property is not shared by most partially ordered sets.
Examples are the set &(S) of all subsets of a set S (with more than one element) rela-
tive to inclusion, or the set N of natural numbers relative to divisibility. In both these
cases any two members have a least upper bound or supremum, briefly sup; given x, y,
there exists z such that (i) x ::: z, y ::: z and (ii) for any z', x ::: z', y ::: z' ::::} z ::: z'.
Dually, any two members have a greatest lower bound or infimum, briefly inf,
defined similarly. Thus if X and Yare subsets of S, their sup is X U Y and their
inf is X n Y. If m, n are natural numbers, their sup (relative to divisibility) is their
least common multiple while their inf is their highest common factor.
51
,52 Lattices and Categories
A partially ordered set in which any two elements have a supremum and an
infimum is called a lattice. The sup of x, y is written x v y and is called the join of
x and y; their inf is written x /\ y and is called the meet of x and y. It is clear that
the lattice concept is self-dual, so that the dual of a lattice, obtained by reversing
the ordering, is again a lattice. As examples of lattices we have the set N of natural
numbers under divisibility, as well as 9(5), the set of all subsets of 5 under inclusion;
further, every totally ordered set is trivially a lattice, with x /\ y = x, x v y = y if
x .:s y.
Partially ordered sets are often represented as directed graphs: the elements of the
set form the vertices, and edges are drawn so that a < b holds precisely when b is
higher than a and there is a descending path from b to a. Such diagrams are
mainly used for finite sets; for N or Z the structure can be hinted at in a partial dia-
gram, but the case of Q or R would be more difficult. Some examples are given in
Figures 3.1-3.3, where Figures 3.1 and 3.2 are lattices, but Figure 3.3 is not.
A lattice may be regarded as a set with two binary operators, V and /\. These
operators satisfy a number of laws, reminiscent of the laws governing addition
and multiplication of numbers, and these laws can be used to give an alternative
definition of lattices.
Figure 3.1
Figure 3.2
, 3.1 Definitions: Modular and Distributive Lattices 53
Figure 3.3
Proposition 3.1.1. Let L be a lattice. Then for any a, b, c E L,
a V (b V c) = (a V b) V c, a /\ (b /\ c) = (a /\ b) /\ c, (associative law) (3.1.1)
a vb = b V a, a /\ b = b /\ a, (commutative law) (3.1.2)
a /\ (a V b) = a, a V (a /\ b) = a, (absorptive law) (3.1.3)
a V a = a, a /\ a = a. (idempotent law) (3.l.4)
Conversely, if L is a set with two binary operators V, /\ satisfying (3.1.1)-(3.1.3), then
(3.1.4) also holds and a partial ordering may be defined on L by the rule
a .:::: b if and only if a V b = b. (3.l.5)
Relative to this ordering L is a lattice such that the join of a, b is a V b and the meet is
a /\ b.
Proof. By the definition of a V b as sup we see that the unique sup of a, b can be
written as either a V b or b V a, and a similar remark applies to a /\ b, so (3.1.2)
follows. Likewise the sup of a, b, c may be written as a V (b V c) or (a V b) V c,
hence (3.1.1) holds. Now (3.1.3) follows because a /\ b .:::: a':::: a V b, and (3.1.4) is
a trivial consequence of the definition, but we observe that it also follows from
(3.1.3): if in the first Equation (3.1.3) we replace b by a /\ a we get
a = a /\ [a V (a /\ a)] = a /\ a, by the second Equation (3.1.3). This proves the
first idempotent law; the second follows by duality.
Now let L be a set with two operators V, /\ satisfying (3.1.1)-(3.1.3); then (3.1.4)
also holds, as we have just seen, and moreover,
a V b = b {} a /\ b = a. (3.l.6)
For if a V b = b, then by (3.1.3), a /\ b = a /\ (a V b) = a, and the converse follows
by duality (and the commutative law (3.1.2)). If we define the relation '.::::' by
(3.1.5), we have a partial ordering: if a .:::: b, b.:::: c, then a V b = b, b V c = c;
hence by (3.1.1), c = b V c = (a V b) V c = a V (b V c) = a V c, so a .:::: c. Further,
a.:::: a by (3.1.4), and if a .:::: b, b.:::: a, then b = a V b = b V a = a, by (3.1.2).
