Nation J.B. - Notes On Lattice Theory (2008)
Nation J.B. - Notes On Lattice Theory (2008)
J. B. Nation
University of Hawaii
Introduction
In the early 1890’s, Richard Dedekind was working on a revised and enlarged
edition of Dirichlet’s Vorlesungen über Zahlentheorie, and asked himself the following
question: Given three subgroups A, B, C of an abelian group G, how many different
subgroups can you get by taking intersections and sums, e.g., A + B, (A + B) ∩ C,
etc. The answer, as we shall see, is 28 (Chapter 7). In looking at this and related
questions, Dedekind was led to develop the basic theory of lattices, which he called
Dualgruppen. His two papers on the subject, Über Zerlegungen von Zahlen durch
ihre größten gemeinsamen Teiler (1897) and Über die von drei Moduln erzeugte
Dualgruppe (1900), are classics, remarkably modern in spirit, which have inspired
many later mathematicians.
“There is nothing new under the sun,” and so Dedekind found. Lattices, espe-
cially distributive lattices and Boolean algebras, arise naturally in logic, and thus
some of the elementary theory of lattices had been worked out earlier by Ernst
Schröder in his book Die Algebra der Logik. Nonetheless, it is the connection be-
tween modern algebra and lattice theory, which Dedekind recognized, that provided
the impetus for the development of lattice theory as a subject, and which remains
our primary interest.
Unfortunately, Dedekind was ahead of his time in making this connection, and
so nothing much happened in lattice theory for the next thirty years. Then, with
the development of universal algebra in the 1930’s by Garrett Birkhoff, Oystein Ore
and others, Dedekind’s work on lattices was rediscovered. From that time on, lattice
theory has been an active and growing subject, in terms of both its application to
algebra and its own intrinsic questions.
These notes are intended as the basis for a one-semester introduction to lattice
theory. Only a basic knowledge of modern algebra is presumed, and I have made no
attempt to be comprehensive on any aspect of lattice theory. Rather, the intention
is to provide a textbook covering what we lattice theorists would like to think every
mathematician should know about the subject, with some extra topics thrown in
for flavor, all done thoroughly enough to provide a basis for a second course for the
student who wants to go on in lattice theory or universal algebra.
It is a pleasure to acknowledge the contributions of students and colleagues to
these notes. I am particularly indebted to Michael Tischendorf, Alex Pogel and the
referee for their comments. Mahalo to you all.
Finally, I hope these notes will convey some of the beauty of lattice theory as I
learned it from two wonderful teachers, Bjarni Jónsson and Bob Dilworth.
1. Ordered Sets
Note
(d) ∼
= (e)
(d) (e)
Figure 1.1
is close enough for government purposes. In particular, we can now generate lots of
examples of ordered sets using Hasse diagrams, as in Figure 1.1.
The natural maps associated with the category of ordered sets are the order
preserving maps, those satisfying the condition x ≤ y implies f (x) ≤ f (y). We
say that P is isomorphic to Q, written P ∼ = Q, if there is a map f : P → Q
which is one-to-one, onto, and both f and f −1 are order preserving, i.e., x ≤ y iff
f (x) ≤ f (y).
With that we can state the desired representation of any ordered set as a system
of sets ordered by containment.
Theorem 1.1. Let Q be an ordered set, and let φ : Q → P(Q) be defined by
φ(x) = {y ∈ Q : y ≤ x}.
a b c
c a b
P Figure 1.2 Pd
(3) If
a0 ≥ a1 ≥ a2 ≥ . . .
in P, then there exists k such that an = ak for all n ≥ k.
Proof. The equivalence of (2) and (3) is clear, and likewise that (1) implies (2).
There is, however, a subtlety in the proof of (2) implies (1). Suppose P fails (1) and
that S ⊆ P has no minimal element. In order to find an infinite descending chain in
S, rather than just arbitrarily long finite chains, we must use the Axiom of Choice.
One way to do this is as follows.
3
Let f be a choice function on the subsets of S, i.e., f assigns to each nonempty
subset T ⊆ S an element f (T ) ∈ T . Let a0 = f (S), and for each i ∈ ω define
ai+1 = f ({s ∈ S : s < ai }); the argument of f in this expression is nonempty
because S has no minimal element. The sequence so defined is an infinite descending
chain, and hence P fails (2).
The conditions described by the preceding lemma are called the descending chain
condition (DCC). The dual notion is called the ascending chain condition (ACC).
These conditions should be familiar to you from ring theory (for ideals). The next
lemma just states that ordered sets satisfying the DCC are those for which the
principle of induction holds.
Lemma 1.3. Let P be an ordered set satisfying the DCC. If ϕ(x) is a statement
such that
(1) ϕ(x) holds for all minimal elements of P , and
(2) whenever ϕ(y) holds for all y < x, then ϕ(x) holds,
then ϕ(x) is true for every element of P .
Note that (1) is in fact a special case of (2). It is included in the statement of the
lemma because in practice minimal elements usually require a separate argument
(like the case n = 0 in ordinary induction).
The proof is immediate. The contrapositive of (2) states that the set F = {x ∈
P : ϕ(x) is false} has no minimal element. Since P satisfies the DCC, F must
therefore be empty.
We now turn our attention more specifically to the structure of ordered sets.
Define the width of an ordered set P by
where |A| denotes the cardinality of A.1 A second invariant is the chain covering
number c(P), defined to be the least cardinal γ such that P is the union of γ chains
in P. Because no chain can contain more than one element of a given
S antichain, we
must have |A| ≤ |I| whenever A is an antichain in P and P = i∈I Ci is a chain
covering. Therefore
w(P) ≤ c(P)
for any ordered set P. The following result, due to R. P. Dilworth [2], says in
particular that if P is finite, then w(P) = c(P).
1 Note that the width function w(P) does not distinguish, for example, between ordered sets
which contain arbitrarily large finite antichains and those which contain a countably infinite an-
tichain. For this reason, in ordered sets of infinite width it is sometimes useful to consider the
function µ(P), which is defined to be the least cardinal κ such that κ + 1 > |A| for every antichain
A of P. We will restrict our attention to w(P).
4
Theorem 1.4. If w(P) is finite, then w(P) = c(P).
Our discussion of the proof will take the scenic route. We begin with the case
when P is finite, using H. Tverberg’s nice proof [11].
Proof in the finite case. We need to show c(P) ≤ w(P), which is done by induction
on |P |. Let w(P) = k, and let C be a maximal chain in P. If P is a chain,
w(P) = c(P) = 1, so assume C 6= P. Because C can contain at most one element of
any maximal antichain, the width w(P −C) is either k or k−1, and both possibilities
can occur. If w(P − C) = k − 1, then P − C is the union of k − 1 chains, whence P
is a union of k chains.
So suppose w(P − C) = k, and let A = {a1 , . . . , ak } be a maximal antichain in
P − C. As |A| = k, it is also a maximal antichain in P. Set
P = L ∪ U = C1 ∪ · · · ∪ Ck
is a union of k chains.
So now we want to consider an infinite ordered set P of finite width k. Not
surprisingly, we will want to use one of the 210 equivalents of the Axiom of Choice!
(See H. Rubin and J. Rubin [9].) This requires some standard terminology.
Let P be an ordered set, and let S be a subset of P . We say that an element
x ∈ P is an upper bound for S if x ≥ s for all s ∈ S. An upper bound x need not
belong to S. We say that x is the least upper bound for S if x is an upper bound
for S and x ≤ y for every upper bound y of S. If the least upper bound of S exists,
then it is unique. Lower bound and greatest lower bound are defined dually.
Theorem 1.5. The following set theoretic axioms are equivalent.
(1) (Axiom of Choice) If X is a nonempty set, then there is a map φ :
P(X) → X such that φ(A) ∈ A for every nonempty A ⊆ X.
(2) (Zermelo well-ordering principle) Every nonempty set admits a well-
ordering (a total order satisfying the DCC ).
(3) (Hausdorff maximality principle) Every chain in an ordered set P can
be embedded in a maximal chain.
5
(4) (Zorn’s Lemma) If every chain in an ordered set P has an upper bound in
P, then P contains a maximal element.
(5) If every chain in an ordered set P has a least upper bound in P, then P
contains a maximal element.
given in (2).
6
not satisfiable. But ∆0 ∪ ∆1 is satisfiable, say by a truth assignment ν. If ν(ϕ) = T ,
this contradicts the choice of ∆0 , while ν(¬ϕ) = T contradicts the choice of ∆1 . So
the claim holds.
Now define a truth assignment µ as follows. For each sentence symbol p ∈ S,
define
µ(p) = T iff p ∈ ∆ .
Now we claim that for all ϕ ∈ S, µ(ϕ) = T iff ϕ ∈ ∆. This will yield µ(ϕ) = T for
all ϕ ∈ Σ, so that Σ is satisfiable.
To prove this last claim, let G = {ϕ ∈ S : µ(ϕ) = T iff ϕ ∈ ∆}. We have S ⊆ G,
and we need to show that G is closed under the operations ¬, ∧ and ∨, so that
G = S.
(1) Suppose ϕ = ¬β with β ∈ G. Then, using the first claim,
Hence ϕ = ¬β ∈ G.
(2) Suppose ϕ = α ∧ β with α, β ∈ G. Note that α ∧ β ∈ ∆ iff α ∈ ∆ and β ∈ ∆.
For if α ∧ β ∈ ∆, since {α ∧ β, ¬α} is not satisfiable we must have α ∈ ∆, and
similarly β ∈ ∆. Conversely, if α ∈ ∆ and β ∈ ∆, then since {α, β, ¬(α ∧ β)} is not
satisfiable, we have α ∧ β ∈ ∆. Thus
Hence ϕ = (α ∧ β) ∈ G.
(3) The case ϕ = α ∨ β is similar to (2).
We return to considering an infinite ordered set P of width k. Let S = {cxi : x ∈
P, 1 ≤ i ≤ k}. We think of cxi as corresponding to the statement “x is in the i-th
chain.” Let Σ be all sentences of the form
for x ∈ P , and
You should check that Ri is a partial order extending ≤. By Lemma 1.8 each Ri
can be extended to a total order ≤i extending ≤. To see that ≤ is the intersection
of the ≤i ’s, suppose x y. Since ϕ is an embedding, then ϕ(x)i ϕ(y)i for some
i. Thus ϕ(x)i > ϕ(y)i , implying y Ri x and hence y ≤i x, or equivalently x i y (as
x 6= y), as desired.
Thus the order on P is the intersection of κ total orders if and only if P can be
embedded into the direct product of κ chains, yielding (1).
S
For (2), assume P = j∈J Cj with each Cj a chain. Then, for each j ∈ J, the
ordered set O(Cj ) of order ideals of Cj is also a chain. Define a map ϕ : P →
Q
j∈J O(Cj ) by (ϕ(x))j = {y ∈ Cj : y ≤ x}. (Note ∅ ∈ O(Cj ), and (ϕ(x))j = ∅
is certainly possible.) Then ϕ is clearly order-preserving. On the other hand, if
x y in P and x ∈ Cj , then x ∈ (ϕ(x))j and x ∈ / (ϕ(y))j , so (ϕ(x))j * (ϕ(y))j and
ϕ(x) ϕ(y). Thus P can be embedded into a direct product of |J| chains. Using
(1), this shows d(P ) ≤ c(P ).
Now we have three invariants defined on ordered sets: w(P ), c(P ) and d(P ).
The exercises will provide you an opportunity to work with these in concrete cases.
We have shown that w(P ) ≤ c(P ) and d(P ) ≤ c(P ), but width and dimension are
independent. Indeed, if κ is an ordinal and κd its dual, then κ × κd has width |κ|
but dimension 2. It is a little harder to find examples of high dimension but low
width (necessarily infinite by Dilworth’s theorem), but it is possible (see [6] or [8]).
This concludes our brief introduction to ordered sets per se. We have covered
only the most classical results of what is now an active field of research, supporting
its own journal, Order.
9
Exercises for Chapter 1
1. Draw the Hasse diagrams for all 4-element ordered sets (up to isomorphism).
2. Let N denote the positive integers. Show that the relation a | b (a divides b)
is a partial order on N . Draw the Hasse diagram for the ordered set of all divisors
of 60.
3. A partial map on a set X is a map σ : S → X where S = dom σ is a subset of
X. Define σ ≤ τ if dom σ ⊆ dom τ and τ (x) = σ(x) for all x ∈ dom σ. Show that
the collection of all partial maps on X is an ordered set.
4. (a) Give an example of a map f : P → Q which is one-to-one, onto and
order-preserving, but not an isomorphism.
(b) Show that the following are equivalent for ordered sets P and Q.
(i) P ∼= Q (as defined before Theorem 1.1).
(ii) There exists f : P Q such that f (x) ≤ f (y) iff x ≤ y. ( means the map
is onto.)
(iii) There exist f : P → Q and g : Q → P , both order-preserving, with gf = idP
and f g = idQ .
5. Find all order ideals of the rational numbers Q with their usual order.
6. Prove that all chains in an ordered set P are finite if and only if P satisfies
both the ACC and DCC.
7. Find w(P), c(P) and d(P) for
(a) an antichain A with |A| = κ, where κ is a cardinal,
(b) Mκ , where κ is a cardinal, the ordered set diagrammed in Figure 1.3(a).
(c) an n-crown, the ordered set diagrammed in Figure 1.3(b).
(d) P(X) with X a finite set,
(e) P(X) with X infinite.
a1 a2 a3 an
c1 cκ
b1 b2 b3 bn
Figure 1.3
References
1. K. Bogart, R. Freese and J. Kung, Eds., The Dilworth Theorems, Birkhäuser, Boston, 1990.
2. R. P. Dilworth, A decomposition theorem for partially ordered sets, Annals of Math. 51 (1950),
161–166.
3. R. Freese, J. Ježek and J. B. Nation, Free Lattices, Mathematical Surveys and Monographs,
vol. 42, Amer. Math. Soc., Providence, R. I., 1995.
4. F. Galvin, A proof of Dilworth’s chain decomposition theorem, Amer. Math. Monthly 101
(1994), 352–353.
5. K. Gödel, Die Vollständigkeit der Axiome des logischen Funktionenkalküls, Monatsh. Math.
Phys. 37 (1930), 349–360.
6. J. B. Nation, D. Pickering and J. Schmerl, Dimension may exceed width, Order 5 (1988),
21–22.
7. M. A. Perles, On Dilworth’s theorem in the infinite case, Israel J. Math. 1 (1963), 108–109.
8. M. Pouzet, Généralisation d’une construction de Ben-Dushnik et E. W. Miller, Comptes
Rendus Acad. Sci. Paris 269 (1969), 877–879.
9. H. Rubin and J. Rubin, Equivalents of the Axiom of Choice II, Studies in Logic and the
Foundations of Mathematics, vol. 116, North-Holland, Amsterdam, 1985.
10. E. Szpilrajn, Sur l’extension de l’ordre partiel, Fund. Math. 16 (1930), 386–389.
11. H. Tverberg, On Dilworth’s decomposition theorem for partially ordered sets, J. Combinatorial
Theory 3 (1967), 305–306.
11
2. Semilattices, Lattices and Complete Lattices
The most important partially ordered sets come endowed with more structure
than that. For example, the significant feature about PO(X) for Theorem 1.7 is
not just its partial order, but that it is closed under intersection. In this chapter we
will meet several types of structures which arise naturally in algebra.
A semilattice is an algebra S = (S, ∗) satisfying, for all x, y, z ∈ S,
(1) x ∗ x = x,
(2) x ∗ y = y ∗ x,
(3) x ∗ (y ∗ z) = (x ∗ y) ∗ z.
In other words, a semilattice is an idempotent commutative semigroup. The symbol
∗ can be replaced by any binary operation symbol, and in fact we will most often
use one of ∨, ∧, + or ·, depending on the setting. The most natural example of
a semilattice is (P(X), ∩), or more generally any collection of subsets of X closed
under intersection. Thus the semilattice PO(X) of partial orders on X is naturally
contained in (P(X 2 ), ∩).
Theorem 2.1. In a semilattice S, define x ≤ y if and only if x ∗ y = x. Then
(S, ≤) is an ordered set in which every pair of elements has a greatest lower bound.
Conversely, given an ordered set P with that property, define x ∗ y = g.l.b. (x, y).
Then (P, ∗) is a semilattice.
Proof. Let (S, ∗) be a semilattice, and define ≤ as above. First we check that ≤ is
a partial order.
(1) x ∗ x = x implies x ≤ x.
(2) If x ≤ y and y ≤ x, then x = x ∗ y = y ∗ x = y.
(3) If x ≤ y ≤ z, then x ∗ z = (x ∗ y) ∗ z = x ∗ (y ∗ z) = x ∗ y = x, so x ≤ z.
Since (x ∗ y) ∗ x = x ∗ (x ∗ y) = (x ∗ x) ∗ y = x ∗ y) we have x ∗ y ≤ x; similarly
x ∗ y ≤ y. Thus x ∗ y is a lower bound for {x, y}. To see that it is the greatest lower
bound, suppose z ≤ x and z ≤ y. Then z ∗ (x ∗ y) = (z ∗ x) ∗ y = z ∗ y = z, so
z ≤ x ∗ y, as desired.
The proof of the converse is likewise a direct application of the definitions, and
is left to the reader.
12
A semilattice with the above ordering is usually called a meet semilattice, and as
a matter of convention ∧ or · is used for the operation symbol. In Figure 2.1, (a)
and (b) are meet semilattices, while (c) fails on several counts.
φ(x) = {y ∈ S : y ≤ x}.
example, the sets {1, 2}, {1, 3} and ∅ do not form a subsemilattice of (P({1, 2, 3}), ∩).
13
(2) x ∧ y = y ∧ x and x ∨ y = y ∨ x,
(3) x ∧ (y ∧ z) = (x ∧ y) ∧ z and x ∨ (y ∨ z) = (x ∨ y) ∨ z,
(4) x ∧ (x ∨ y) = x and x ∨ (x ∧ y) = x.
The first three pairs of axioms say that L is both a meet and join semilattice. The
fourth pair (called the absorption laws) say that both operations induce the same
order on L. The lattice operations are sometimes denoted by · and +; for the sake
of consistency we will stick with the ∧ and ∨ notation.
An example is the lattice (P(X), ∩, ∪) of all subsets of a set X, with the usual
set operations of intersection and union. This turns out not to be a very general
example, because subset lattices satisfy the distributive law
(D) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
M3 N5
Figure 2.2
a/b = {x ∈ L : b ≤ x ≤ a}
a/0 = {x ∈ L : x ≤ a}
1/a = {x ∈ L : a ≤ x}
The latter notations are used irrespective of whether L actually has a least element
0 or a greatest element 1.2
One further bit of notation will prove useful. For a subset A of an ordered set P,
let Au denote the set of all upper bounds of A, i.e.,
Au = {x ∈ P : x ≥ a for all a ∈ A}
\
= 1/a.
a∈A
A` = {x ∈ P : x ≤ a for all a ∈ A}
\
= a/0.
a∈A
Let us consider the question of when a subset A of an ordered set P has a least
upper bound. Clearly Au must be nonempty, and this will certainly be the case if P
has a greatest element. If moreover it happens that Au has a greatest lower bound
z in P, then in fact z ∈ Au , i.e., a ≤ z for all a ∈ A, because each a ∈ A is a lower
bound for Au . Therefore by definition z is the least
W upper bound of A. In this case
we say that the join of A exists, and write z = A (treating the join as a partially
defined operation). V
But if S is a finite meet semilattice with a greatest element, then Au exists for
every A ⊆ S. Thus we have the following result.
Theorem 2.4. Let S be a finite meet semilattice with greatest element 1. Then S
is a lattice with the join operation defined by
^ ^
x ∨ y = {x, y}u = (1/x ∩ 1/y).
This result not only yields an immediate supply of lattice examples, but it pro-
vides us with an efficient algorithm for deciding when a finite ordered set is a lattice:
2 There are several commonly used ways of denoting interval sublattices; the one we have adopted
is as good as any, but hardly universal. The most common alternative has a/b = [b, a], a/0 = (a]
and 1/a = [a). The notations ↓ a for a/0 and ↑ a for 1/a are also widely used.
15
if P has a greatest element and every pair of elements has a meet, then P is a lattice.
The dual version is of course equally useful.
Every finite subset of a lattice has a greatest lower bound and a least upper bound,
but these bounds need not exist for infinite subsets. Let us define a complete
V lattice
to be an ordered setWL in which every subset A has a greatest lower bound A and a
least upper bound A.3 Clearly every finite lattice is complete, and every complete
lattice is a lattice with 0 and 1 (but not conversely). Again P(X) is a natural (but
not very general) example of a complete lattice, and Sub(G) is a better one. The
rational numbers with their natural order form a lattice which is not complete.
Likewise, a complete meet semilattice is an ordered set S with a greatest element
and
V the property that every nonemptyV subset A of S has a greatest lower bound
A. By convention, we define ∅ = 1, the greatest element of S. The analogue of
Theorem 2.4 is as follows.
Theorem 2.5. If L is a complete meet semilattice, then L is a complete lattice with
the join operation defined by
_ ^ ^ \
A= Au = ( 1/a).
a∈A
x∈S
or
Y ⊆ S =⇒ z ∈ S
with x, z ∈ X and Y ⊆ X. (Note that the first type of rule is a degenerate case
of the second, taking Y = ∅.) A subset D of X is said to be closed with respect to
these rules if ϕ(D) is true for each ϕ ∈ Σ. The closure rules corresponding to our
previous examples are:
(i) all rules Y ⊆ S =⇒ z ∈ S where z is an accumulation point of Y ,
(ii) the rule 1 ∈ S and all rules
x ∈ S =⇒ x−1 ∈ S
{x, y} ⊆ S =⇒ xy ∈ S
with x, y ∈ G,
(iii) 0 ∈ S and all rules {x, y} ⊆ S =⇒ ax + by ∈ S with a, b scalars,
(iv) for all pairs with x < y in P the rules y ∈ S =⇒ x ∈ S,
(v) for all x, y ∈ <n and 0 < t < 1, the rules {x, y} ⊆ S =⇒ tx + (1 − t)y ∈ S.
So the closure rules just list the properties that we check to determine if a set S is
closed or not.
The following theorem makes explicit the connection between these ideas.
Theorem 2.6. (1 ) If C is a closure system on a set X, then the map ΓC : P(X) →
P(X) defined by \
ΓC (A) = {D ∈ C : A ⊆ D}
c∈S
17
where c ∈ Γ(∅), and all rules
Y ⊆ S =⇒ z ∈ S
with z ∈ Γ(Y ). Then a set D ⊆ X satisfies all the rules of ΣΓ if and only if
Γ(D) = D.
(3 ) If Σ is a set of closure rules on a set X, let CΣ be the collection of all subsets
of X which satisfy all the rules of Σ. Then CΣ is a closure system.
In other words, the collection of all closed sets of a closure operator forms a
complete lattice, and the property of being a closed set can be expressed in terms of
rules which are clearly preserved by set intersection. It is only a slight exaggeration
to say that all important lattices arise in this way. As a matter of notation, we will
also use CΓ to denote the lattice of Γ-closed sets, even though this particular variant
is skipped in the statement of the theorem.
Proof. Starting with a closure system C, define ΓC as above. Observe that ΓC (A) ∈ C
for any A ⊆ X, and Γ(D) = D for every D ∈ C. Therefore ΓC (ΓC (A)) = ΓC (A), and
the other axioms for a closure operator hold by elementary set theory.
Given a closure operator Γ, it is clear that Γ(D) ⊆ D iff D satisfies all the rules
of ΣΓ . Likewise, it is immediate because of the form of the rules that CΣ is always
a closure system.
Note that if Γ is a closure operator on a set X, then the operations on CΓ are
given by
^ \
Di = Di
i∈I i∈I
_ [
Di = Γ( Di ).
i∈I i∈I
For example, in the lattice of closed subsets of a topological space, the join is the
closure of the union. In the lattice of subgroups of a group, the join of a collection
of subgroups is the subgroup generated by their union. The lattice of order ideals
is somewhat exceptional in this regard, because the union of a collection of order
ideals is already an order ideal.
One type of closure operator is especially important. If A = hA, F, Ci is an
algebra, then S ⊆ A is a subalgebra of A if c ∈ S for every constant c ∈ C, and
{s1 , . . . , sn } ⊆ S implies f (s1 , . . . , sn ) ∈ S for every basic operation f ∈ F . Of
course these are closure rules, so the intersection of any collection of subalgebras of
A is again one.4 For a subset B ⊆ A, define
\
Sg(B) = {S : S is a subalgebra of A and B ⊆ S}.
4 If A has no constants, then we have to worry about the empty set. We want to allow ∅ in the
subalgebra lattice in this case, but realize that it is an abuse of terminology to call it a subalgebra.
18
By Theorem 2.6, Sg is a closure operator, and Sg(B) is of course the subalgebra
generated by B. The corresponding lattice of closed sets is CSg = Sub A, the lattice
of subalgebras of A.
Galois connections provide another source of closure operators. These are rele-
gated to the exercises not because they are unimportant, but rather to encourage
you to grapple with how they work on your own.
For completeness, we include a representation theorem.
Then L is isomorphic to C∆ .
Lemma 2.8. If a lattice L satisfies the DCC, then every element of L is a join of
finitely many join irreducible elements.
Proof. Suppose some element of L is not a join of join irreducible elements.W Let x
be a minimal such element. Then x is not itself join irreducible, so x = F for
W theWminimality of x, each f ∈ F
some finite set F of elements strictly below x. By
is the join of a finite set Gf ⊆ J(L). Then x = f ∈F Gf , a contradiction.
If L also satisfies the ACC, then join irreducible elements can be identified as
those which cover a unique element, viz.,
_
q∗ = {x ∈ L : x < q}.
The representation of lattices satisfying both chain conditions (in particular, finite
lattices) as a closure system is quite straightforward.
F ⊆ S =⇒ q ∈ S
W
where q is join irreducible, F is a finite subset of J(L), and q ≤ F . (Include the
degenerate cases p ∈ S =⇒ q ∈ S for q ≤ p in J(L).) Then L is isomorphic to
the lattice CΣ of Σ-closed sets.
Proof. Define order preserving maps f : L → CΣ and g : CΣ → L by
A completion (L, φ) is join dense if φ(P ) is join dense in L, i.e., for every x ∈ L,
_
x = {φ(p) : φ(p) ≤ x}.
It is not hard to see that every completion of P contains a join dense completion.
For, given
W a completion (L, φ) of P, let L0 be the set of allWelements of L of the
form {φ(p) : p ∈ A} for some subset A ⊆ P , including ∅ = 0. Then L0 is
a complete join subsemilattice of L, and hence a complete lattice. Moreover, L0
contains φ(p) for every p ∈ P , and (L0 , φ) is a join dense completion of P. Hence
we may reasonably restrict our attention to join dense completions.
Our first example of a join dense completion is the lattice of order ideals O(P).
Order ideals are the closed sets of the closure operator on P given by
[
O(A) = a/0,
a∈A
20
and the embedding φ is given by φ(p) = p/0. Note that the union of order ideals is
again an order ideal, so O(P) obeys the distributive law (D).
Another example is the MacNeille completion M(P), a.k.a. normal completion,
completion by cuts [2]. For subsets S, T ⊆ P recall that
S u = {x ∈ P : x ≥ s for all s ∈ S}
T ` = {y ∈ P : y ≤ t for all t ∈ T }.
The MacNeille completion is the lattice of closed sets of the closure operator on P
given by
M (A) = (Au )` ,
i.e., M (A) is the set of all lower bounds of all upper bounds of A. Note that M (A)
is an order ideal of P. Again the map φ(p) = p/0 embeds P into M(P).
Now every join dense completion V meets in P: if A ⊆ P and A
V preserves all existing
has a greatest lower bound b = A in P, then φ(b) = φ(A) (see Exercise 10). The
MacNeille completion has the nice property
W that it also preserves all existingW
joins in
P: if A has a least upper bound c = A in P, then φ(c) = c/0 = M (A) = φ(A).
In fact, every join dense completion corresponds to a closure operator on P .
Theorem 2.10. Let P be an ordered set. If Φ is a closure operator on P such that
Φ({p}) = p/0 for all p ∈ P , then (CΦ , φ) is a join dense completion of P, where
φ(p) = p/0. Conversely, if (L, φ) is a join dense completion of P, then the map Φ
defined by _
Φ(A) = {q ∈ P : φ(q) ≤ φ(a)}
a∈A
The least and greatest members of K(P) are the order ideal completion and the
MacNeille completion, respectively.
Theorem 2.11. K(P) is a complete lattice with least element O and greatest ele-
ment M .
Proof. The condition Γ({p}) = p/0 implies that O(A) ⊆ Γ(A) for all A ⊆ P , which
makes O the least element of K(P). On the other hand, for any Γ ∈ K(P), if b ≥ a
for all a ∈ A, then b/0 = Γ(b/0) ⊇ Γ(A). Thus
\
Γ(A) ⊆ (b/0) = (Au )` = M (A),
b∈Au
C(x) = {c ∈ C : x c} ,
D(x) = {d ∈ D : x d} .
We have shown that one of these two sets is nonempty for each x ∈ L. If C(x) 6= ∅,
let f (x) be its largest element (using the ACC); otherwise let f (x) be the least
element of D(x) (using the DCC). Now for any x ∈ L, either x f (x) or x f (x),
so f has no fixed point.
It remains to check that f is order preserving. Suppose x ≤ y. If C(x) 6= ∅ then
f (x) ∈ C and f (x) y (else f (x) ≥ y ≥ x); hence C(y) 6= ∅ and f (y) ≥ f (x).
So assume C(x) = ∅, whence f (x) ∈ D. If perchance C(y) 6= ∅ then f (y) ∈ C, so
f (x) ≤ f (y). On the other hand, if C(y) = ∅ and f (y) ∈ D, then x f (y) (else
y ≥ x ≥ f (y)), so again f (x) ≤ f (y). Therefore f is order preserving.
References
1. A. C. Davis, A characterization of complete lattices, Pacific J. Math. 5 (1955), 311–319.
2. H. M. MacNeille, Partially ordered sets, Trans. Amer. Math. Soc. 42 (1937), 90–96.
3. J. B. Nation and A. Pogel, The lattice of completions of an ordered set, Order 14 (1996), 1–7.
4. A. Tarski, A lattice-theoretical fixpoint theorem and its applications, Pacific J. Math. 5 (1955),
285–309.
5. M. Ward, The closure operators of a lattice, Annals of Math. 43 (1942), 191–196.
25
3. Algebraic Lattices
In this section we want to focus our attention on the kind of closure operators
and lattices which are associated with modern algebra. A closure operator Γ on a
set X is said to be algebraic if for every B ⊆ X,
[
Γ(B) = {Γ(F ) : F is a finite subset of B}.
Equivalently, Γ is algebraic if the right hand side RHS of the above expression is
closed for every B ⊆ X, since B ⊆ RHS ⊆ Γ(B) holds for any closure operator.
A closure rule is said to be finitary if it is a rule of the form x ∈ S or the form
F ⊆ S =⇒ z ∈ S with F a finite set. Again the first form is a degenerate case of
the second, taking F = ∅. It is not hard to see that a closure operator is algebraic
if and only if it is determined by a set of finitary closure rules (see Theorem 3.1(1)).
Let us catalogue some important examples of algebraic closure operators.
(1) Let A be any algebra with only finitary operations – for example, a group,
ring, vector space, semilattice or lattice. The closure operator Sg on A such that
Sg(B) is the subalgebra of A generated by B is algebraic, because we have a ∈ Sg(B)
if and only if a can be expressed as a term a = t(b1 , . . . , bn ) for some finite subset
{b1 , . . . , bn } ⊆ B, in which case a ∈ Sg({b1 , . . . , bn }). The corresponding complete
lattice is of course the subalgebra lattice Sub A.
(2) Looking ahead a bit (to Chapter 5), the closure operator Cg on A × A such
that Cg(B) is the congruence on A generated by the set of pairs B is also algebraic.
The corresponding complete lattice is the congruence lattice Con A. For groups
this is isomorphic to the normal subgroup lattice; for rings, it is isomorphic to the
lattice of ideals.
(3) For ordered sets, the order ideal operator O is algebraic. In fact we have
[
O(B) = {O({b}) : b ∈ B}
for all B ⊆ P .
(4) Let S = (S; ∨) be a join semilattice with a least element 0. A subset J of S
is called an ideal if
(1) 0 ∈ J,
(2) x, y ∈ J implies x ∨ y ∈ J,
(3) z ≤ x ∈ J implies z ∈ J.
26
An ideal J is a principal ideal if J = x/0 for some x ∈ S. Since ideals are defined
by closure rules, the intersection of a set of ideals of S is again one.1 The closure
operator I on S such that I(B) is the ideal of S generated by B is given by
_
I(B) = {x ∈ S : x ≤ F for some finite F ⊆ B}.
(a) (b)
Figure 3.1
from which equality follows. Thus CΓ will be an algebraic lattice if we can show that
the closures of finite sets are compact. W
Let F be a finite subset of X. If Γ(F ) ≤ Ai in CΓ , then
_ [ [ [
F ⊆ Ai = Γ( Ai ) = {Γ(G) : G finite ⊆ Ai }.
as desired.
An element a ∈ L is called an atom if a 0, and a coatom if 1 a. Theorem 3.7
shows that every atom in an upper continuous lattice is compact. More generally,
if a/0 satisfies the ACC in an upper continuous lattice, then a is compact.
We know that every element x in an algebraic lattice can be expressed as the
join of x/0 ∩ Lc (by definition). It turns out to be at least as important to know
how x can be expressed as a meet of other elements. We say that an element q V in a
complete lattice L is completely meet irreducible if, for every subset S of L, q = S
implies q ∈ S. These are of course the elements which cannot be expressed as the
proper meet of other elements. Let M ∗ (L) denote theVset of all completely meet
irreducible elements of L. Note that 1 6∈ M ∗ (L) (since ∅ = 1 and 1 6∈ ∅).
Theorem 3.8. Let q ∈ L where L is a complete lattice. The following are equiva-
lent.
(1) Vq ∈ M ∗ (L).
(2) {x ∈ L : x > q} > q.
(3) There exists q ∗ ∈ L such that q ∗ q and for all x ∈ L, x > q implies x ≥ q ∗ .
V
The connection between (2) and (3) is of course q ∗ = {x ∈ L : x > q}. In a
finite lattice, q ∈ M ∗ (L) iff there is a unique element q ∗ covering q, but in general
we need the stronger property (3). V
A decomposition of an element a ∈ L is a representation a = Q where Q is
a set of completely meet irreducible elements of L. An element in an arbitrary
lattice may have any number of decompositions, including none. A theorem due
to Garrett Birkhoff says that every element in an algebraic lattice has at least one
decomposition [1].
32
Theorem 3.9. If L V is an algebraic lattice, then M ∗ (L) is meet dense in L. Thus
for every x ∈ L, x = (1/x ∩ M ∗ (L)).
V
Proof. Let m = (1/x ∩ M ∗ (L)), and suppose x < m. Then there exists a c ∈ Lc
with c ≤ m and c 6≤ x. Since c is compact, we can use Zorn’s Lemma to find
an element q which is maximal with respect to q ≥ x, q 6≥ c. For any y ∈ L,
y > q implies y ≥ q ∨ c, so q is completely meet irreducible with q ∗ = q ∨ c. Then
q ∈ 1/x ∩ M ∗ (L) implies q ≥ m ≥ c, a contradiction. Hence x = m.
It is rare for an element in an algebraic lattice to have a unique decomposition. A
somewhat weaker V propertyVis for an element to have an irredundant decomposition,
meaning a = Q but a < (Q − {q}) for all q ∈ Q, where Q is a set of completely
meet irreducible elements. An element in an algebraic lattice need not have an
irredundant decomposition either. Let L be the lattice consisting of the empty
set and all cofinite subsets of an infinite set X, ordered by set inclusion. This
satisfies the ACC so it is algebraic. The completely meet irreducible elements of
L are its coatoms, the complements of one element subsets of X. The meet of
any infinite collection of coatoms is 0 (the empty set), but no such decomposition
is irredundant. Clearly also these are the only decompositions of 0, so 0 has no
irredundant decomposition.
A lattice is strongly atomic if a > b in L implies there exists u ∈ L such that a ≥
u b. A beautiful result of Peter Crawley guarantees the existence of irredundant
decompositions in strongly atomic algebraic lattices [3].
Theorem 3.10. If an algebraic lattice L is strongly atomic, then every element of
L has an irredundant decomposition.
If L is also distributive, we obtain the uniqueness of irredundant decompositions.
Theorem 3.11. If L is a distributive, strongly atomic, algebraic lattice, then every
element of L has a unique irredundant decomposition.
The finite case of Theorem 3.11 is the dual of Theorem 8.6(c), which we will
prove later.
The theory of decompositions was studied extensively by Dilworth and Crawley,
and their book [4] contains most of the principal results.
References
1. G. Birkhoff, Subdirect unions in universal algebra, Bull. Amer. Math. Soc. 50 (1944), 764–768.
2. G. Birkhoff and O. Frink, Representations of sets by lattices, Trans. Amer. Math. Soc. 64
(1948), 299–316.
3. P. Crawley, Decomposition theory for nonsemimodular lattices, Trans. Amer. Math. Soc. 99
(1961), 246–254.
4. P. Crawley and R. P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall, Englewood Cliffs,
N. J., 1973.
5. R. Freese, W. A. Lampe and W. Taylor, Congruence lattices of algebras of fixed similarity
type, I, Pacific J. Math. 82 (1979), 59–68.
6. G. Grätzer and E. T. Schmidt, Characterizations of congruence lattices of abstract algebras,
Acta Sci. Math. (Szeged) 24 (1963), 34–59.
34
4. Representation by Equivalence Relations
So far we have no analogue for lattices of the Cayley theorem for groups, that
every group is isomorphic to a group of permutations. The corresponding represen-
tation theorem for lattices, that every lattice is isomorphic to a lattice of equivalence
relations, turns out to be considerably deeper. Its proof uses a recursive construction
technique which has become a standard tool of lattice theory and universal algebra.
An equivalence relation on a set X is a binary relation E satisfying, for all x, y, z ∈
X,
(1) x E x,
(2) x E y implies y E x,
(3) if x E y and y E z, then x E z.
We think of an equivalence relation as partitioning the set X into blocks of E-related
elements, called equivalence classes. Conversely, any partition of X into a disjoint
union of blocks induces an equivalence relation on X: x E y iff x and y are in the
same block. As usual with relations, we write x E y and (x, y) ∈ E interchangeably.
The most important equivalence relations are those induced by maps. If Y is
another set, and f : X → Y is any function, then
G(y) G(x)
r t
G(x) G(y)
p q
F (x ∨ y)
Figure 4.1
Now (1) says that G(z) ∩ U 2 = F (z). Since F is one-to-one, this implies G
is also. Note that for z, z 0 ∈ L we have z ∧ z 0 ≥ x iff z ≥ x and z 0 ≥ x, and
symmetrically for y. Using this with conditions (1)–(7), it is not hard to check that
G(z ∧ z 0 ) = G(z) ∩ G(z 0 ). Hence, G is a weak representation of L, and clearly
(U, F ) v (V, G).
Sublemma 2. Let λ be a limit ordinal, and for ξ < λ let (Uξ , Fξ ) be weak S repre-
sentations of L such that α < β < λ implies (Uα , Fα ) v (Uβ , Fβ ). Let V = ξ<λ Uξ
S
and G(x) = ξ<λ Fξ (x) for all x ∈ L. Then (V, G) is a weak representation of L
with (Uξ , Fξ ) v (V, G) for each ξ < λ.
37
Proof. Let ξ < λ. Since Fα (x) = Fξ (x) ∩ Uα2 ⊆ Fξ (x) whenever α < ξ and Fξ (x) =
Fβ (x) ∩ Uξ2 whenever β ≥ ξ, for all x ∈ L we have
[
G(x) ∩ Uξ2 = Fγ (x) ∩ Uξ2
γ<λ
[
= (Fγ (x) ∩ Uξ2 )
γ<λ
= Fξ (x).
Thus (Uξ , Fξ ) v (V, G). Since F0 is one-to-one, this implies that G is also.
It remains to show that G is a meet homomorphism. Clearly G preserves order,
so for any x, y ∈ L we have G(x ∧ y) ⊆ G(x) ∩ G(y). On the other hand, if
(u, v) ∈ G(x) ∩ G(y), then there exists α < λ such that (u, v) ∈ Fα (x), and there
exists β < λ such that (u, v) ∈ Fβ (y). If γ is the larger of α and β, then (u, v) ∈
Fγ (x) ∩ Fγ (y) = Fγ (x ∧ y) ⊆ G(x ∧ y). Thus G(x) ∩ G(y) ⊆ G(x ∧ y). Combining
the two inclusions gives equality.
Now we want to use these two sublemmas to construct a type 3 representation of
L, i.e., a weak representation which also satisfies G(x∨y) = G(x)◦G(y)◦G(x)◦G(y).
Start with an arbitrary weak representation (U0 , F0 ), and consider the set of all
quadruples (p, q, x, y) such that p, q ∈ U0 and x, y ∈ L and (p, q) ∈ F0 (x ∨ y).
Arrange these into a well ordered sequence (pξ , qξ , xξ , yξ ) for ξ < η. Applying the
sublemmas repeatedly, we can obtain a sequence of weak representations (Uξ , Fξ )
for ξ ≤ η such that
(1) if ξ < η, then (Uξ , Fξ ) v (Uξ+1 , Fξ+1 ) and (pξ , qξ ) ∈ Fξ+1 (xξ ) ◦ Fξ+1 (yξ ) ◦
Fξ+1 (xξ ) ◦ Fξ+1 (yξ ); S S
(2) if λ ≤ η is a limit ordinal, then Uλ = ξ<λ Uξ and Fλ (x) = ξ<λ Fξ (x) for
all x ∈ L.
Let V1 = Uη and G1 = Fη . If p, q ∈ U0 , and x, y ∈ L and p F0 (x ∨ y) q, then
(p, q, x, y) = (pξ , qξ , xξ , yξ ) for some ξ < η, so that (p, q) ∈ Fξ+1 (x) ◦ Fξ+1 (y) ◦
Fξ+1 (x) ◦ Fξ+1 (y). Consequently,
such that Gn (x∨y) ⊆ Gn+1 (x)◦Gn+1 (y)◦Gn+1 (x)◦Gn+1 (y) for all n ∈ w, x, y ∈ L.
38
S S
Finally, let W = n∈w Vn and H(x) = n∈ω Gn (x) for all x ∈ L, and you get a
type 3 representation of L.
Since the proof involves transfinite recursion, it produces a representation (X, F )
with X infinite, even when L is finite. For a long time one of the outstanding
questions of lattice theory was whether every finite lattice can be embedded into
the lattice of equivalence relations on a finite set. In 1980, Pavel Pudlák and Jı́ři
Tůma showed that the answer is yes [6]. The proof is quite difficult.
Theorem 4.2. Every finite lattice has a representation (Y, G) with Y finite.
One of the motivations for Whitman’s theorem was Garrett Birkhoff’s observa-
tion, made in the 1930’s, that a representation of a lattice L by equivalence relations
induces an embedding of L into the lattice of subgroups of a group. Given a rep-
resentation (X, F ) of L, let G be the group of all permutations on X which move
only finitely many elements, and let Sub G denote the lattice of subgroups of G.
Let h : L → Sub G by
pAq
pBrCsBq
rBpAqBs
B B
p q
A
Figure 4.2
On the other hand, Jónsson gave a slight variation of the proof of Theorem
4.1 which shows that every modular lattice has a type 2 representation [4], [1].
Combining this with Lemma 4.4, we obtain the following.
Theorem 4.5. A lattice has a type 2 representation if and only if it is modular.
The modular law (M ) plays an important role in lattice theory, and we will see
it often. Note that (M ) fails in the pentagon N5 . It was invented in the 1890’s by
Richard Dedekind, who showed that the lattice of normal subgroups of a group is
modular. The modular law is equivalent to the equation,
(M 0 ) x ∧ ((x ∧ y) ∨ z) = (x ∧ y) ∨ (x ∧ z).
It is easily seen to be a special case of (and hence weaker than) the distributive law,
(D) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z),
where
ci = (aj ∨ ak ) ∧ (bj ∨ bk )
for {i, j, k} = {0, 1, 2}. The Arguesian law is (less obviously) equivalent to a lattice
inclusion,
p A0 r A1 q
p B0 s B1 q.
A0 A1
A2
C1 t C0
p q
B2
B0 B1
s
Figure 4.3
41
Mark Haiman has shown that the converse is false: there are Arguesian lattices
which do not have a type 1 representation [2], [3]. In fact, his proof shows that lat-
tices with a type 1 representation must satisfy equations which are strictly stronger
than the Arguesian law. It follows, in particular, that the lattice of normal sub-
groups of a group also satisfies these stronger equations. Interestingly, P. P. Pálfy
and Laszlo Szabó have shown that subgroup lattices of abelian groups satisfy an
equation which does not hold in all normal subgroup lattices [5].
The question remains: Does there exist a set of equations Σ such that a lattice
has a type 1 representation if and only if it satisfies all the equations of Σ? Haiman
proved that if such a Σ exists, it must contain infinitely many equations. In Chapter
7 we will see that a class of lattices is characterized by a set of equations if and only
if it is closed with respect to direct products, sublattices, and homomorphic images.
The class of lattices having a type 1 representation is easily seen to be closed under
sublattices and direct products, so the question is equivalent to: Is the class of all
lattices having a type 1 representation closed under homomorphic images?
References
1. P. Crawley and R. P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall, Englewood Cliffs,
New Jersey, 1973.
2. M. Haiman, Arguesian lattices which are not linear, Bull. Amer. Math. Soc. 16 (1987), 121–
124.
3. M. Haiman, Arguesian lattices which are not type-1, Algebra Universalis 28 (1991), 128–137.
4. B. Jónsson, On the representation of lattices, Math. Scand. 1 (1953), 193–206.
5. P. P. Pálfy and Cs. Szabó, An identity for subgroup lattices of abelian groups, Algebra Univer-
salis 33 (1995), 191–195.
6. P. Pudlák and J. Tůma, Every finite lattice can be embedded in the lattice of all equivalences
over a finite set, Algebra Universalis 10 (1980), 74–95.
7. P. Whitman, Lattices, equivalence relations and subgroups, Bull. Amer. Math. Soc. 52 (1946),
507–522.
43
5. Congruence Relations
“You’re young, Myrtle Mae. You’ve got a lot to learn, and I hope you never
learn it.”
– Vita in “Harvey”
You are doubtless familiar with the connection between homomorphisms and
normal subgroups of groups. In this chapter we will establish the corresponding ideas
for lattices (and other general algebras). Borrowing notation from group theory, if X
is a set and θ an equivalence relation on X, for x ∈ X let xθ denote the equivalence
class {y ∈ X : x θ y}, and let
We can define lattice operations naturally on the equivalence classes of ker h, viz.,
if θ = ker h, then
xθ ∨ yθ = (x ∨ y)θ
(§)
xθ ∧ yθ = (x ∧ y)θ.
The homomorphism property shows that these operations are well defined, for if
(x, y) ∈ ker h and (r, s) ∈ ker h, then h(x ∨ r) = h(x) ∨ h(r) = h(y) ∨ h(s) = h(y ∨ s),
whence (x ∨ r, y ∨ s) ∈ ker h. Moreover, L/ ker h with these operations forms an
algebra L/ ker h isomorphic to the image h(L), which is a sublattice of K. Thus
L/ ker h is also a lattice.
Theorem 5.1. First Isomorphism Theorem. Let L and K be lattices, and let
h : L → K be a lattice homomorphism. Then L/ ker h with the operations defined by
(§) is a lattice L/ ker h, which is isomorphic to the image h(L) of L in K.
Let us define a congruence relation on a lattice L to be an equivalence relation θ
such that θ = ker h for some homomorphism h.1 We have see that, in addition to
1 This is not the standard definition, but we are about to show it is equivalent to it.
44
being equivalence relations, congruence relations must preserve the operations of L:
if θ is a congruence relation, then
and analogously for meets. Note that (†) is equivalent for an equivalence relation θ
to the apparently weaker, and easier to check, condition
(†0 ) x θ y implies x ∨ z θ y ∨ z.
For (†) implies (†0 ) because every equivalence relation is reflexive, while if θ has
the property (†0 ) and the hypotheses of (†) hold, then applying (†) twice yields
x ∨ r θ y ∨ r θ y ∨ s.
We want to show that, conversely, any equivalence relation satisfying (†0 ) and the
corresponding implication for meets is a congruence relation.
Theorem 5.2. Let L be a lattice, and let θ be an equivalence relation on L satisfying
x θ y implies x ∨ z θ y ∨ z,
(‡)
x θ y implies x ∧ z θ y ∧ z.
Define join and meet on L/θ by the formulas (§). Then L/θ = (L/θ, ∧, ∨) is a lattice,
and the map h : L → L/θ defined by h(x) = xθ is a surjective homomorphism with
ker h = θ.
Proof. The conditions (‡) ensure that the join and meet operations are well defined
on L/θ. By definition, we have
Note that the universal relation and the equality relation on L2 are both con-
gruence relations; they are the greatest and least elements of Con L, respectively.
Also, since x θ y if and only if x ∧ y θ x ∨ y, a congruence relation is determined by
the ordered pairs (a, b) with a < b which it contains.
A congruence relation θ is principal if θ = con(a, b) for some pair a, b ∈ L. The
principal congruence relations are join dense in Con L: for any congruence relation
θ, we have
_
θ = {con(a, b) : a θ b}.
It follows from the general theory of algebraic closure operators that principal
congruence W relations are compact, but this can be shown directly as follows: if
con(a, b) ≤ i∈I θi , then there exist elements c1 , . . . , cm and indices i0 , . . . , im such
that
a θi0 c1 θi1 c2 . . . θim b ,
W
whence (a, b) ∈ θi0 ∨ . . . ∨ θim and thus con(a, b) ≤ 0≤j≤m θij .
One of the most basic facts about congruences says that congruences of L/θ
correspond to congruences on L containing θ.
Theorem 5.4. Second Isomorphism Theorem. If θ ∈ Con L, then Con (L/θ)
is isomorphic to the interval 1/θ in Con L.
2 The corresponding statement is true for any equationally defined class of algebras, including
and likewise for meets. Thus S is a congruence relation on L/θ. This gives us an
order preserving map g : 1/θ → Con L/θ.
The definitions make f and g inverse maps, so they are in fact isomorphisms.
It is interesting to interpret the Second Isomorphism Theorem in terms of homo-
morphisms. Essentially it corresponds to the fact that if h : L K and f : L → M
are homomorphisms with h surjective, then there is a homomorphism g : K → M
with f = gh if and only if ker h ≤ ker f .
A lattice L is called simple if Con L is a two element chain, i.e., |L| > 1 and L has
no congruences except equality and the universal relation. For example, the lattice
Mn is simple whenever n ≥ 3. A lattice is subdirectly irreducible if it has a unique
minimum nonzero congruence relation, i.e., if 0 is completely meet irreducible in
Con L. So every simple lattice is subdirectly irreducible, and N5 is an example of
a subdirectly irreducible lattice which is not simple .
The following are immediate consequences of the Second Isomorphism Theorem.
Corollary. L/θ is simple if and only if 1 θ in Con L.
Corollary. L/θ is subdirectly irreducible if and only if θ is completely meet irre-
ducible in Con L.
Now we turn our attention to a decomposition of lattices which goes back to
R. Remak in 1930 (for groups) [7]. In what follows, it is important to remember
that the zero element of a congruence lattice is the equality relation.
V
Theorem 5.5.QIf 0 = i∈I θi in Con L, then L is isomorphic to a sublattice of the
direct product i∈I L/θi , and each of the natural homomorphisms πi : L → L/θi is
surjective.
47
Q
Conversely, if L is isomorphic to a sublattice of a direct product i∈I Ki and each
∼
V the projection homomorphisms πi : L → Ki is surjective, then Ki = L/ ker πi and
of
i∈I ker πi = 0 in Con L.
1 h1, 1i
x hx, zi hz, xi
y hy, zi hz, yi
0 h0, 0i
N5 L
Figure 5.1
Next we should show that subdirectly irreducible lattices are indeed those which
have no proper subdirect decomposition.
m(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z).
Then it is easy to see that m(x, y, z) is a majority polynomial, in that if any two
variables are equal then m(x, y, z) takes on that value:
m(x, x, z) = x
m(x, y, x) = x
m(x, z, z) = z.
t0 = m(x, x, z) = x
tk = m(x, z, z) = z
x = t0 α ∧ β t1 α ∧ γ t2 α ∧ β . . . tk = z
w(x) = (. . . (((x ∧ s1 ) ∨ s2 ) ∧ s3 ) . . . ) ∨ sk
x ∨ y = r0 ≥ r1 ≥ · · · ≥ rk = x ∧ y
y ∨ z = s0 ≥ s1 ≥ · · · ≥ sm = y ∧ z
x ∨ y ∨ z = r0 ∨ y ∨ z ≥ r1 ∨ y ∨ z ≥ · · · ≥ (x ∧ y) ∨ y ∨ z = y ∨ z.
y ∧ z = (x ∨ y) ∧ y ∧ z ≥ r1 ∧ y ∧ z ≥ · · · ≥ rk ∧ y ∧ z = x ∧ y ∧ z.
Combining the two new sequences with the original one for y R z, we get a sequence
from x ∨ y ∨ z down to x ∧ y ∧ z. Hence x ∧ y ∧ z R x ∨ y ∨ z. By the observations
above, x ∧ z R x ∨ z and x R z, so R is transitive.
Now we must check (‡). Let x R y as before, and let z ∈ L. Replacing wj (t) by
uj (t) = wj (t) ∨ z, we obtain a sequence from x ∨ y ∨ z down to (x ∧ y) ∨ z. Thus
(x ∧ y) ∨ z R x ∨ y ∨ z, and since (x ∧ y) ∨ z ≤ (x ∨ z) ∧ (y ∨ z) ≤ x ∨ y ∨ z, this
implies x ∨ z R y ∨ z. The argument for meets is done similarly, and we conclude
that R is a congruence relation, as desired.
The condition of Theorem 5.9 is a bit unwieldy, but not as bad to use as you
might think. Let us look at some consequences of the theorem.
51
W
Corollary. If θi ∈ Con L for i ∈ I, then (x, y) ∈ i∈I θi if and only if there exist
finitely many rj ∈ L and ij ∈ I such that
x ∨ y = r 0 ≥ r1 ≥ · · · ≥ r k = x ∧ y
and rj θij rj+1 for 0 ≤ j < k.
At this point we need some basic facts about distributive algebraic lattices (like
Con L). W Recall that an element p of a complete lattice is completely join irreducible
W Q implies p = q for some q ∈ Q. An element p is completely join prime if
if p =
p ≤ Q implies p ≤ q for some q ∈ Q. Clearly every completely join prime element
is completely join irreducible, but in general completely join irreducible elements
need not be join prime.
Now every algebraic lattice has lots of completely meet irreducible elements (by
Theorem 3.9), but they may have no completely join irreducible elements. This hap-
pens, for example, in the lattice consisting of the empty set and all cofinite subsets of
an infinite set (which is distributive and algebraic). However, such completely join
irreducible elements as there are in a distributive algebraic lattice are completely
join prime!
Theorem 5.10. The following are equivalent for an element p in an algebraic dis-
tributive lattice.
(1) p is completely join prime.
(2) p is completely join irreducible.
(3) p is compact and (finitely) join irreducible.
Proof. Clearly (1) implies (2), and since every element in an algebraic lattice is a
join of compact elements, (2) implies (3). W
Let p be compact
W and finitely join irreducible, and assume p ≤ Q. As p is
compact,Wp ≤ WF for some finite subset F ⊆ Q. By distributivity, this implies
p = p ∧ ( F ) = q∈F p ∧ q. Since p is join irreducible, p = p ∧ q ≤ q for some q ∈ F .
Thus p is completely join prime. (Cf. Exercise 3.1)
We will return to the theory of distributive lattices in Chapter 8, but let us now
apply what we know to Con L. As an immediate consequence of the Corollary to
Theorem 5.9 we have the following.
Theorem 5.11. If a ≺ b, then con(a, b) is completely join prime in Con L.
The converse is false, as there are infinite simple lattices with no covering rela-
tions. However, for finite lattices, or more generally principally chain finite lattices,
the converse does hold. A lattice is principally chain finite if every principal ideal
c/0 satisfies the ACC and DCC. This is a fairly natural finiteness condition which
includes many interesting infinite lattices, and many results for finite lattices can be
extended to principally chain finite lattices with a minimum of effort. Recall that if
x is a join irreducible element in such a lattice, then x∗ denotes the unique element
such that x x∗ .
52
Theorem 5.12. Let L be a principally chain finite lattice. Then every congruence
relation on L is the join of completely join irreducible congruences. Moreover, ev-
ery completely join irreducible congruence is of the form con(x, x∗ ) for some join
irreducible element x of L.
Proof. Every congruence relation is a join of compact congruences, and every com-
pact congruence is a join of finitely many congruences con(a, b) with a > b. In a prin-
cipally chain finite lattice, every chain in a/b is finite by ExerciseW1.5, so there exists a
covering chain a = r0 r1 · · · rk = b. Clearly con(a, b) = 0≤j<k con(rj , rj+1 ),
and these latter are completely join prime by Theorem 5.11. Thus every congruence
relation on L is the join of completely join irreducible congruences con(r, s) with
r s.
Now let a b be any covering pair in L. By the DCC for a/0, there is an element
x which is minimal with respect to the properties x ≤ a and x b. Since any
element strictly below x is below b, the element x is join irreducible and x∗ = x ∧ b.
It is also true that a = x ∨ b, since b < x ∨ b ≤ a, and it follows easily from these
two facts that con(a, b) = con(x, x∗ ).
We will return to congruence lattices of principally chain finite lattices in Chap-
ter 10.
(d) (e) (f )
Figure 5.2
W
2. An element p of a lattice L is join prime if for any finite subset F of L, p ≤ F
implies p ≤ f for some f ∈ F . Let P(L) denote the set of join prime elements of L,
and define
x∆y iff x/0 ∩ P(L) = y/0 ∩ P(L).
53
Prove that ∆ is a congruence relation on L.
3. Let X be any set. Define a binary relation on P(X) by A ≈ B iff the symmetric
difference (A−B)∪(B −A) is finite. Prove that ≈ is a congruence relation on P(X).
4. Lattice terms are defined in the proof of Theorem 6.1.
(a) Show that if p(x1 , . . . , xn ) is a lattice term and h : L → K is a homomor-
phism, then h(p(a1 , . . . , an )) = p(h(a1 ), . . . , h(an )) for all a1 , . . . , an ∈ L.
(b) Show that if p(x1 , . . . , xn ) is a lattice term and θ ∈ Con L and ai θ bi for
1 ≤ i ≤ n, then p(a1 , . . . , an ) θ p(b1 , . . . , bn ).
(c) Let p(x1 , . . . , xn ) and q(x1 , . . . , xn ) be lattice terms, and let h : L K be a
surjective homomorphism. Prove that if p(a1 , . . . , an ) = q(a1 , . . . , an ) for all
a1 , . . . , an ∈ L, then p(c1 , . . . , cn ) = q(c1 , . . . , cn ) holds for all c1 , . . . , cn ∈ K.
5. Show that each element of a finite distributive lattice has a unique irredundant
decomposition. What does this say about subdirect decompositions of finite lattices?
6. Let θ ∈ Con L.
(a) Show that x y implies xθ yθ or xθ = yθ.
(b) Prove that if L is a finite semimodular lattice, then so is L/θ.
(c) Prove that a subdirect product of semimodular lattices is semimodular.
7. Prove that Con L1 × L2 ∼ = Con L1 × Con L2 . (Note that this is not true
for groups; see Exercise 9.)
8. Let L be a finitely generated lattice, and let θ be a congruence on L such that
L/θ is finite. Prove that θ is compact.
9. Find the congruence lattice of the abelian group Zp × Zp , where p is prime.
Find all finite abelian groups whose congruence lattice is distributive. (Recall that
the congruence lattice of an abelian group is isomorphic to its subgroup lattice.)
For Exercises 10 and 11 we refer to §3 (Universal Algebra) of Appendix 1.
10. Let A = hA; F, Ci be an algebra.
(a) Prove that if h : A → B is a homomorphism and θ = ker h, then for each
f ∈ F,
(b) Prove that (U) is equivalent to the apparently weaker condition that for all
f ∈ F and every i,
(c) Show that if θ ∈ Eq A satisfies (U), then the natural map h : A → A/θ is a
homomorphism with θ = ker h.
Thus congruence relations, defined as homomorphism kernels, are precisely equiva-
lence relations satisfying (U).
54
11. Accordingly, let Con A = {θ ∈ Eq A : θ satisfies (U)}.
(a) Prove that ConWA is aVcomplete sublattice of Eq A. (In particular, you
must show that and are the same in both lattices.)
(b) Show that Con A is an algebraic lattice.
References
1. R. P. Dilworth, The structure of relatively complemented lattices, Ann. of Math. 51 (1950),
348–359.
2. N. Funayama and T. Nakayama, On the distributivity of a lattice of lattice-congruences, Proc.
Imp. Acad. Tokyo 18 (1942), 553–554.
3. G. Grätzer and E. T. Schmidt, On congruence lattices of lattices, Acta Math. Acad. Sci.
Hungar. 13 (1962), 179–185.
4. A. Huhn, On the representation of distributive algebraic lattices II, Acta Sci. Math. (Szeged).
(1989).
5. K. A. Kearnes, Atomicity and Nilpotence, Canadian J. Math. 42 (1990), 1–18.
6. M. Ploščica, J. Tuma and F. Wehrung, Congruence lattices of free lattices in nondistributive
varieties, Coll. Math. (to appear).
7. R. Remak, Über die Darstellung der endlichen Gruppen als Untergruppen direkter Produckte,
Jour. für Math. 163 (1930), 1–44.
8. E. T. Schmidt, The ideal lattice of a distributive lattice with 0 is the congruence lattice of a
lattice, Acta Sci. Math. (Szeged). 43 (1981), 153–168.
9. M. Tischendorf, On the representation of distributive semilattices, Algebra Universalis 31
(1994), 446-455.
10. F. Wehrung, A uniform refinement property of certain congruence lattices, Proc. Amer. Math.
Soc. (to appear).
55
6. Free Lattices
56
lattices, free modular lattices, and free Arguesian lattices, since each of these laws
can be written as a lattice equation.
Theorem 6.1. For any nonempty set X, there exists a free lattice generated by X.
The proof uses three basic principles of universal algebra. These correspond for
lattices to Theorems 5.1, 5.4, and 5.5 respectively. However, the proofs of these
theorems involved nothing special to lattices except the operation symbols ∧ and ∨;
these can easily be changed to arbitrary operation symbols. Thus, with only minor
modification, the proof of this theorem can be adapted to show the existence of free
algebras in any nontrivial equational class of algebras.
Basic Principle 1. If h : A B is a surjective homomorphism, then B ∼= A/ ker h.
Basic Principle 2. If f : A → B and g : A C are homomorphism with g
surjective, and ker g ≤ ker f , then there exists h : C → B such that f = hg.
f
A B
g h
C
Figure 6.1
V
Basic Principle 3. If ψ = i∈I θi in Con A, then A/ψ is isomorphic to a
subalgebra of the direct product Πi∈I A/θi .
With these principles in hand, we proceed with the proof of Theorem 6.1.
Proof of Theorem 6.1. Given the set X, define the word algebra W (X) to be the set
of all formal expressions (strings of symbols) satisfying the following properties:
(1) X ⊆ W (X),
(2) if p, q ∈ W (X), then (p ∨ q) and (p ∧ q) are in W (X),
(3) only the expressions given by the first two rules are in W (X).
Thus W (X) is the absolutely free algebra with operation symbols ∨ and ∧ generated
by X. The elements of W (X), which are called terms, are all well-formed expressions
in the variables X and the operation symbols ∧ and ∨. Clearly W (X) is an algebra
generated by X, which is property (II) from the definition of a free lattice. Because
two terms are equal if and only if they are identical, W (X) has the mapping property
(III). On the other hand, it is definitely not a lattice. We need to identify those
pairs p, q ∈ W (X) which evaluate the same in every lattice, e.g., x and (x ∧ (x ∨ y)).
The point of the proof is that when this is done, properties (II) andV(III) still hold.
Let Λ = {θ ∈ Con W (X) : W (X)/θ is a lattice}, and let λ = Λ. We claim
that W (X)/λ is a lattice freely generated by {xλ : x ∈ X}.
57
By Basic Principle 3, W (X)/λ is isomorphic to a subalgebra of a direct product
of lattices, so it is a lattice.3 Clearly W (X)/λ is generated by {xλ : x ∈ X}, and
because there exist nontrivial lattices (more than one element) for X to be mapped
to in different ways, x 6= y implies xλ 6= yλ for x, y ∈ X.
Now let L be a lattice and let f0 : X → L be any map. By the preceding
observation, the corresponding map h0 : X/λ → L defined by h0 (xλ) = f0 (x)
is well defined. Now f0 can be extended to a homomorphism f : W (X) → L,
whose range is some sublattice S of L. By Basic Principle 1, W (X)/ ker f ∼ = S so
ker f ∈ Λ, and hence ker f ≥ λ. If we use ε to denote the standard homomorphism
W (X) W (X)/λ with ε(u) = uλ for all u ∈ W (X), then ker f ≥ ker ε = λ. Thus
by Basic Principle 2 there exists a homomorphism h : W (X)/λ → L with hε = f
(see Figure 6.2). This means h(uλ) = f (u) for all u ∈ W (X); in particular, h
extends h0 as required.
f
W (X) L
ε h
W (X)/λ
Figure 6.2
It is easy to see, using the mapping property (III), that if F is a lattice freely
generated by X, G is a lattice freely generated by Y , and |X| = |Y |, then F ∼ = G.
Thus we can speak of the free lattice generated by X, which we will denote by
FL(X). If |X| = n, then we also denote this lattice by FL(n). The lattice FL(2)
has four elements, so there is not much to say about it. But FL(n) is infinite for
n ≥ 3, and we want to investigate its structure.
The advantage of the general construction we used is that it gives us the existence
of free algebras in any variety; the disadvantage is that it does not, indeed cannot,
tell us anything about the arithmetic of free lattices. For this we need a result due
to Thoralf Skolem [15] (reprinted in [16]), and independently, P. M. Whitman [18]
in 1941.4
3 This is where we use that lattices are equationally defined. For example, the class of integral
domains is not equationally defined, and the direct product of two or more integral domains is not
one.
4 The history here is rather interesting. Skolem, as part of his 1920 paper which proves the
Lowenheim-Skolem Theorem, solved the word problem not only for free lattices, but for finitely
presented lattices as well. But by the time the great awakening of lattice theory occurred in the
1930’s, his solution had been forgotten. Thus Whitman’s 1941 construction of free lattices became
the standard reference on the subject. It was not until 1992 that Stan Burris rediscovered Skolem’s
solution.
58
Theorem 6.2. Every free lattice FL(X) satisfies the following conditions, where
x, y ∈ X and p, q, p1 , p2 , q1 , q2 ∈ FL(X).
(1) x ≤ y iff x = y.
(2) x ≤ q1 ∨ q2 iff x ≤ q1 or x ≤ q2 .
(3) p1 ∧ p2 ≤ x iff p1 ≤ x or p2 ≤ x.
(4) p1 ∨ p2 ≤ q iff p1 ≤ q and p2 ≤ q.
(5) p ≤ q1 ∧ q2 iff p ≤ q1 and p ≤ q2 .
(6) p = p1 ∧ p2 ≤ q1 ∨ q2 = q iff p1 ≤ q or p2 ≤ q or p ≤ q1 or p ≤ q2 .
Finally, p = q iff p ≤ q and q ≤ p.
Condition (6) in Theorem 6.2 is known as Whitman’s condition, and it is usually
denoted by (W).
Proof of Theorem 6.2. Properties (4) and (5) hold in every lattice, by the definition
of least upper bound and greatest lower bound, respectively. Likewise, the “if ”
parts of the remaining conditions hold in every lattice.
We can take care of (1) and (2) simultaneously. Fixing x ∈ X, let
_
Gx = {w ∈ FL(X) : w ≥ x or w ≤ F for some finite F ⊆ X − {x}}.
Then X ⊆ Gx , and Gx is closed under W joins and meets, so Gx = FL(X). Thus every
w ∈ FL(X) is either above x or below F for some finite F ⊆ X − {x}. W Properties
(1) and (2) will follow if we can show that this “or” is exclusive: x F for all
finite F ⊆ X − {x}. So let h0 : X → 2 (the two element chain) be defined by
h0 (x) = 1, and h0 (y) = 0 for y ∈ X − {x}. This map extends to a homomorphism W
h : FL(X) → W 2. For every finite F ⊆ X − {x} we have h(x) = 1 0 = h( F ),
whence x F . V
Condition (3) is the dual of (2). Note that the proof shows x G for all finite
G ⊆ X − {x}.
Whitman’s condition (6), or (W), can be proved using a slick construction due
to Alan Day [3]. This construction can be motivated by a simple example. In the
lattice of Figure 6.3(a), the elements a, b, c, d fail (W); in Figure 6.3(b) we have
“fixed” this failure by making a ∧ b c ∨ d. Day’s method provides a formal way of
doing this for any (W)-failure.
Let I = u/v be an interval in a lattice L. We define a new lattice L[I] as follows.
The universe of L[I] is (L − I) ∪ (I × 2). Thus the elements of L[I] are of the form
x with x ∈/ I, and (y, i) with i ∈ {0, 1} and y ∈ I. The order on L[I] is defined by:
x ≤ y if x ≤L y
(x, i) ≤ y if x ≤L y
x ≤ (y, j) if x ≤L y
(x, i) ≤ (y, j) if x ≤L y and i ≤ j.
59
(u, 1) a b
u a b (u, 0)
(v, 1)
c d v c d (v, 0)
(a) (b)
Figure 6.3
It is not hard to check the various cases to show that each pair of elements in L[I]
has a meet and join, so that L[I] is indeed a lattice.5 Moreover, the natural map
κ : L[I] L with κ(x) = x and κ((y, i)) = y is a homomorphism. Figure 6.4 gives
another example of the doubling construction, where the doubled interval consists
of a single element {u}.
Now suppose a, b, c, d witness a failure of (W) in FL(X). Let u = c ∨ d, v = a ∧ b
and I = u/v. Let h0 : X → FL(X)[I] with h0 (x) = x if x ∈ / I, h0 (y) = (y, 0) if
y ∈ I, and extend this map to a homomorphism h. Now κh : FL(X) → FL(X) is
also a homomorphism, and since κh(x) = x for all x ∈ X, it is in fact the identity.
Therefore h(w) ∈ κ−1 (w) for all w ∈ FL(X). Since a, b, c, d ∈/ I, this means h(t) = t
for t ∈ {a, b, c, d}. Now v = a ∧ b ≤ c ∨ d = u in FL(X), so h(v) ≤ h(u). But we can
calculate
Theorem 6.2 gives us a solution to the word problem for free lattices, i.e., an
algorithm for deciding whether two lattice terms p, q ∈ W (X) evaluate to the same
element in FL(X) (and hence in all lattices). Strictly speaking, we have an eval-
uation map ε : W (X) → FL(X) with ε(x) = x for all x ∈ X, and we want to
decide whether ε(p) = ε(q). Following tradition, however, we suppress the ε and
ask whether p = q in FL(X).
5 Thisconstruction yields a lattice if, instead of requiring that I be an interval, we only ask that
it be convex, i.e., if x, z ∈ I and x ≤ y ≤ z, then y ∈ I. This generalized construction has also
proved very useful, but we will not need it here.
60
(u, 1)
u
(u, 0)
(a) (b)
Figure 6.4
6 The algorithm for the word problem, and other free lattice algorithms, can be efficiently
programmed; see Chapter XI of [6]. These programs have proved to be a useful tool in the
investigation of the structure of free lattices.
61
Note that it follows from (W) that no element of FL(X) is properly both a meet
and a join, i.e., every element is either meet irreducible or join irreducible. Moreover,
the generators are the only elements which are both meet and join irreducible. It
follows that the generating set of FL(X) is unique. This is very different from the
situation say in free groups: the free group on {x, y} is also generated (freely) by
{x, xy}.
Each element w ∈ FL(X) corresponds to an equivalence class of terms in W (X).
Among the terms which evaluate to w, there may be several of minimal length (total
number of symbols), e.g., (x ∨ (y ∨ z)), ((y ∨ x) ∨ z), etc. Note that if a term p can
be obtained from a term q by applications of the associative and commutative laws
only, thenWp and q have the same length. This allows us to speak of the length of a
term t = ti without specifying the order or parenthesization of the joinands, and
likewise for meets. We want to show that a minimal length term for w is unique
up to associativity and commutativity. This is true for generators, so by duality it
suffices to consider the case when w is a join.
W
Lemma 6.4. Let t = ti in W (X), where each ti is either a generator or a meet.
Assume that ε(t) = w and ε(ti ) = wi under the evaluation map ε : W (X) → FL(X).
If t is a minimal length term representing w, then the following are true.
(1) Each ti is of minimal length.
(2) The wi ’s are pairwise incomparable.
V
(3) If ti is not a generator, so ti = j tij , then ε(tij ) = wij w for all j.
V
Proof. Only
V (3) requires explanation. Suppose wi = wij in FL(X), corresponding
to ti = tij in W (X). Note that wi ≤ wij for all j. If for some j0 we also had
wij0 ≤ w, then _ _
w= wi ≤ wij0 ∨ wk ≤ w,
k6=i
W
whence w = wij0 ∨ k6=i wk . But then replacing ti by tij0 would yield a shorter term
representing w, a contradiction.
If A and B are finite subsets of a lattice, we say that A refines B, written A B,
if for each a ∈ A there exists b ∈ B with a ≤ b. We define dual refinement by C D
if for each c ∈ C there exists d ∈ D with c ≥ d; note that because of the reversed
order of the quantification in the two statements, A B is not the same as B A.
The elementary properties of refinement can be set out as follows, with the proofs
left as an exercise.
Lemma 6.5. The refinement relation has the following properties.
W W
(1) A B implies A ≤ B.
(2) The relation is a quasiorder on the finite subsets of L.
(3) If A ⊆ B then A B.
(4) If A is an antichain, A B and B A, then A ⊆ B.
62
(5) If A and B are antichains with A B and B A, then A = B.
(6) If A B and B A, then A and B have the same set of maximal elements.
The preceding two lemmas are connected as follows.
W W
Lemma 6.6. Let w = 1≤i≤k wi = 1≤j≤m uj in FL(X). If each wi is either a
V
generator or a meet wi = j wij with wij w for all j, then
{w1 , . . . , wm } {u1 , . . . , un }.
W
Proof. For each i we have wi ≤ uj .VIf wi is a generator, this implies wi ≤ uk for
some k by TheoremV6.2(2). WIf wi = wij , we apply Whitman’s condition (W) to
the inclusion wi = wij ≤ uk = w. Since we are given that wij w for all j, it
must be that wi ≤ uk for some k. Hence {w1 , . . . , wm } {u1 , . . . , un }.
W W
Now let t = ti and s = sj be two minimal length terms which W evaluate
W
to w in FL(X). Let ε(ti ) = wi and ε(sj ) = uj , so that w = wi = uj
in FL(X). By Lemma 6.4(1) each ti is a minimal length term for wi , and each
sj is a minimal length term for uj . By induction, these are unique up to as-
sociativity and commutativity. Hence we may assume that ti = sj whenever
wi = uj . By Lemma 6.4(2), the sets {w1 , . . . , wm } and {u1 , . . . , un } are antichains
in FL(X). By Lemma 6.4(3), the elements wi satisfy the hypothesis of Lemma 6.6,
so {w1 , . . . , wm } {u1 , . . . , un }. Symmetrically, {u1 , . . . , un } {w1 , . . . , wm }. Ap-
plying Lemma 6.5(5) yields {w1 , . . . , wm } = {u1 , . . . , un }, whence by our assumption
above {t1 , . . . , tm } = {s1 , . . . , sn }. Thus we obtain the desired uniqueness result.
Theorem 6.7. The minimal length term for w ∈ FL(X) is unique up to associa-
tivity and commutativity.
This minimal length term is called the canonical form of w. The canonical form
of a generator is just x. The proof of the theorem has shown that if w is a proper
join, then its canonical form is determined by the conditions of Lemma 6.4. If w is
a proper meet, then of course its canonical form must satisfy the dual conditions.
The proof of LemmaW6.4 gives us an algorithm for finding the canonical form of
a lattice term. Let t = ti in W (X), where each ti is either a generator or a meet,
and suppose that we have already put each ti into canonical form, which we can do
inductively. This will guarantee that condition (1) ofVLemma 6.4 holds when we are
done. For each ti which is not a generator, say ti = tij , check whether any tij ≤ t
in FL(X);
W if so, replace ti by tij . Continue this process until you have an expression
u = ui which satisfies condition (3). Finally, check whether uiW≤ uj in FL(X)
for any pair i 6= j; if so, delete ui . The resulting expression v = vi evaluates to
the same element as t in FL(X), and v satisfies (1), (2) and (3). Hence v is the
canonical Wform of t.
If w = wi canonically in FL(X), then the elements wi are called the canonical
joinands of w (dually, canonical meetands). It is important to note that these
elements satisfy the refinement property of Lemma 6.6.
63
W
Corollary. If w is a proper join in FL(X) and w = U , then the set of canonical
joinands of w refines U .
This has an important structural consequence, observed by Bjarni Jónsson [9].
Theorem 6.8. Free lattices satisfy the following implications, for all u, v, a, b, c ∈
FL(X):
(SD∨ ) if u = a ∨ b = a ∨ c then u = a ∨ (b ∧ c),
The implications (SD∨ ) and (SD∧ ) are known as the semidistributive laws.
Proof. We will prove that FL(X) satisfies (SD∨ ); then (SD∧ ) follows by duality.
We may assume that u is a proper join, for otherwise u is join irreducible and the
implication is trivial. So let u = u1 ∨ . . . ∨ un be the canonical join decomposition.
By the Corollary above, {u1 , . . . , un } refines both {a, b} and {a, c}. Any ui which is
not below a must be below both b and c, so in fact {u1 , . . . , un } {a, b ∧ c}. Hence
_
u= ui ≤ a ∨ (b ∧ c) ≤ u ,
(a) (b)
Figure 6.5
p(x1 , . . . , xn ) = q(x1 , . . . , xn ) implies p(h0 (x1 ), . . . , h0 (xn )) = q(h0 (x1 ), . . . , h0 (xn )).
References
1. G. Birkhoff, On the structure of abstract algebras, Proc. Cambridge Phil. Soc. 31 (1935),
433–454.
2. P. Crawley and R. A. Dean, Free lattices with infinite operations, Trans. Amer. Math. Soc. 92
(1959), 35–47.
3. A. Day, A simple solution of the word problem for lattices, Canad. Math. Bull. 13 (1970),
253–254.
4. A. Day, Splitting lattices generate all lattices, Algebra Universalis 7 (1977), 163–170.
5. R. A. Dean, Component subsets of the free lattice on n generators, Proc. Amer. Math. Soc. 7
(1956), 220–226.
6. R. Freese, J. Ježek, and J. B. Nation, Free Lattices, Mathematical Surveys and Monographs,
vol. 42, Amer. Math. Soc., Providence, 1995.
7. R. Freese and J. B. Nation, Projective lattices, Pacific J. Math. 75 (1978), 93–106.
8. V. A. Gorbunov, Canonical decompositions in complete lattices, Algebra i Logika 17 (1978),
495–511,622. (Russian)
9. B. Jónsson, Sublattices of a free lattice, Canad. J. Math. 13 (1961), 256–264.
10. R. McKenzie, Equational bases and non-modular lattice varieties, Trans. Amer. Math. Soc.
174 (1972), 1–43.
11. J. B. Nation, Finite sublattices of a free lattice, Trans. Amer. Math. Soc. 269 (1982), 311–337.
12. J. B. Nation, On partially ordered sets embeddable in a free lattice, Algebra Universalis 18
(1984), 327–333.
13. J. B. Nation and J. H. Schmerl, The order dimension of relatively free lattices, Order 7 (1990),
97–99.
14. H. L. Rolf, The free lattice generated by a set of chains, Pacific J. Math. 8 (1958), 585–595.
15. T. Skolem, Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit und Beweisbarkeit
mathematischen Sätze nebst einem Theoreme über dichte Mengen, Videnskapsselskapets skrifter
I, Matematisk-naturvidenskabelig klasse, Videnskabsakademiet i Kristiania 4 (1920), 1–36.
16. T. Skolem, Select Works in Logic, Scandinavian University Books, Oslo, 1970.
17. Yu. I. Sorkin, Free unions of lattices, Mat. Sbornik 30 (1952), 677–694. (Russian)
18. Ph. M. Whitman, Free lattices, Ann. of Math. (2) 42 (1941), 325–330.
67
7. Varieties of Lattices
2 If a variety V of algebras (1) has only finitely many operation symbols, (2) is finitely based,
and (3) is generated by its finite members, then the word problem for FV (X) is solvable. This
result is due to A. I. Malcev for groups; see T. Evans [7].
70
so that (f (p), f (q) ∈ ker h. Thus ker h is fully invariant.
Conversely, assume that θ is a fully invariant congruence on FL(X). If θ =
1Con FL(X) , then θ is fully invariant and FL(X)/θ is relatively free for the trivial
variety T. So without loss of generality, θ is not the universal relation. Let k :
FL(X) → FL(X)/θ be the canonical homomorphism with ker k = θ. Let V be the
variety determined by the set of equations Σ = {p ≈ q : (p, q) ∈ θ}. To show that
FL(X)/θ is V-freely generated by {xθ : x ∈ X}, we must verify that
(1) FL(X)/θ ∈ V, and
(2) if M ∈ V and h0 : X → M , then there is a homomorphism h : FL(X)/θ →
M such that h(xθ) = h0 (x), i.e., hk(x) = h0 (x) for all x ∈ X.
For (1), we must show that the lattice FL(X)/θ satisfies every equation of Σ, i.e.,
that if p(x1 , . . . , xn ) θ q(x1 , . . . , xn ) and w1 , . . . , wn are elements of FL(X), then
p(w1 , . . . , wn ) θ q(w1 , . . . , wn ). Since there is an endomorphism f of FL(X) with
f (xi ) = wi for all i, this follows from the fact that θ is fully invariant.
To prove (2), let g : FL(X) → M be the homomorphism such that g(x) = h0 (x)
for all x ∈ X. Since M is in V, g(p) = g(q) whenever p ≈ q is in Σ, and thus
θ = ker k ≤ ker g. By the Second Isomorphism Theorem, there is a homomorphism
h : FL(X)/θ → M such that hk = g, as desired.
It follows that varieties of lattices are in one-to-one correspondence with fully
invariant congruences on FL(ω). The consequences of this fact can be summarized
as follows.
Theorem 7.3. The set of all lattice varieties ordered by containment forms a lattice
Λ dually isomorphic to the lattice of all fully invariant congruences of FL(ω). Thus
Λ is dually algebraic, and a variety V is dually compact in Λ if and only if V =
V (Σ) for some finite set of equations Σ.
Going back to statement (2) of Theorem 7.1, the third way of looking at varieties
is model theoretic: a variety is a class of lattices closed under the operators H
(homomorphic images), S (sublattices) and P (direct products). Now elementary
arguments show that, for any class K,
PS(K) ⊆ SP(K)
PH(K) ⊆ HP(K)
SH(K) ⊆ HS(K).
Thus the smallest variety containing a class K of lattices is HSP(K), the class of all
homomorphic images of sublattices of direct products of lattices in K. We refer to
HSP(K) as the variety generated by K. We can think of HSP as a closure operator,
but not an algebraic one: Λ is not upper continuous, so it cannot be algebraic (see
Exercise 5). The many advantages of this point of view will soon become apparent.
71
Lemma 7.4. Two lattice varieties are equal if and only if they contain the same
subdirectly irreducible lattices.
Proof. Recall from Theorem 5.6 that every lattice L is a subdirect product of subdi-
rectly irreducible lattices L/θ with θ completely meet irreducible in Con L. Suppose
V and K are varieties, and that the subdirectly irreducible lattices of V are all in
K. Then for any X the relatively free lattice FV (X), being a subdirect product of
subdirectly irreducible lattices FV (X)/θ in V, is a subdirect product of lattices in
K. Hence FV (X) ∈ K and V ⊆ K. The lemma follows by symmetry.
This leads us directly to a crucial question: If K is a set of lattices, how can
we find the subdirectly irreducible lattices in HSP(K)? The answer, due to Bjarni
Jónsson, requires that we once again venture into the world of logic.
Let us recall that a filter (or dual ideal) of a lattice L with greatest element 1 is
a subset F of L such that
(1) 1 ∈ F ,
(2) x, y ∈ F implies x ∧ y ∈ F ,
(3) z ≥ x ∈ F implies z ∈ F .
For any x ∈ L, the set 1/x is called a principal filter. As an example of a nonprincipal
filter, in the lattice P(X) of all subsets of an infinite set X we have the filter F of all
complements of finite subsets of X. A maximal proper filter is called an ultrafilter.
We want to describe an important type of congruence relation on direct products.
Let Li (i ∈ I) be lattices, and let F be a filter on the lattice
Q of subsets P(I). We
define an equivalence relation ≡F on the direct product i∈I Li by
x ≡F y if {i ∈ I : xi = yi } ∈ F.
Q Li (i ∈ I) and an ultrafilter U
Proof. Suppose we have a collection of lattices
on P(I). The elements of the ultraproduct Q i∈I Li /Q ≡U are equivalence classes
of elements of the direct product.
Q Let µ : Li → Li / ≡U be the canonical
homomorphism, and let πj : Li → Lj denote the projection map. We will prove
the following claim, which includes Theorem 7.6.
Q
Claim. Let h : W Q (X) → i∈I Li be a homomorphism, and let ϕ be a well formed
formula. Then ( Li / ≡U , µh) |= ϕ if and only if {i ∈ I : (Li , πi h) |= ϕ} ∈ U .
We proceed by induction on the complexity of ϕ. In view of the observations
above (e.g., DeMorgan’s Laws), it suffices to treat equations, and, ¬ and ∀. The
first three are quite straightforward.
Q
Note that for a, b ∈ Li we have µ(a) = µ(b) if and only if {i : πi (a) = πi (b)} ∈
U . Thus, for an equation p ≈ q, we have
Y
( Li / ≡U , µh) |= p ≈ q iff µh(p) = µh(q)
iff {i : πi h(p) = πi h(q)} ∈ U
iff {i : (Li , πi h) |= p ≈ q} ∈ U.
.
For a conjunction α and β, using A ∩ B ∈ U iff A ∈ U and B ∈ U , we have
Y Y Y
( Li / ≡U , µh) |= α and β iff ( Li / ≡U , µh) |= α and ( Li / ≡U , µh) |= β
iff {i : (Li , πi h) |= α} ∈ U and {i : (Li , πi h) |= β} ∈ U
iff {i : (Li , πi h) |= α and β} ∈ U.
.
For a negation ¬α, using the fact that A ∈ U iff I − A ∈
/ U , we have
Y Y
( Li / ≡U , µh) |= ¬α iff ( Li / ≡U , µh) 6|= α
iff {i : (Li , πi h) |= α} ∈
/U
iff {j : (Lj , πj h) 6|= α} ∈ U
iff {j : (Lj , πj h) |= ¬α} ∈ U.
75
.
Finally, we consider the case when ϕ has the Q form ∀xγ. First, assume A = {i :
(Li , πi h) |= ∀xγ} ∈ U , and let g : W (X) → Li be a homomorphism such that
µg|X−{x} = µh|X−{x} . This means that for each y ∈ X − {x}, the set By = {j :
πj g(y) = πj h(y)} ∈ T U . Since Fγ is a finite set and U is closed under intersection,
it follows that B = y∈Fγ −{x} By = {j : πj g(y) = πj h(y) for all y ∈ Fγ − {x}} ∈
U . Therefore A ∩ B = {i : (Li , πi h) |= ∀xγ and πi g|FγQ −{x} = πi h|Fγ −{x} } ∈ U .
Hence
Q {i : (Li , πi g) |= γ} ∈ U , and so by induction ( Li / ≡U , µg) |= γ. Thus
( Li / ≡U , µh) |= ∀xγ, as desired.
Conversely, suppose A = {i : (Li , πi h) |= ∀xγ} ∈ / U . Then the complement
I − A = {j : (Lj , πj h) 6|= ∀xγ} ∈ U . For each j ∈ I − A, there is a homomorphism
gj : W (X)Q→ Lj such that gj |X−{x} = πj h|X−{x} and (Lj , gj ) 6|= γ. Let g :
W (X) → Li be a homomorphism
Q gj for all j ∈ I − A. Then
such that πj g = Q
µg|X−{x} = µh|X−{x} but ( Li / ≡U , µg) 6|= γ. Thus ( Li / ≡U , µh) 6|= ∀xγ.
This completes the proof of Lemma 7.6.
To our operators H, S and P let us add a fourth: Pu (K) is the class of all
ultraproducts of lattices from K. Finally we get to answer the question: Where do
subdirectly irreducibles come from?
Theorem 7.7. Jónsson’s Lemma. Let K be a class of lattices. If L is subdirectly
irreducible and L ∈ HSP(K), then L ∈ HSPu (K).
Proof.QNow L ∈ HSP(K) means that there are lattices Ki ∈ K (i ∈ I), a sublattice
S of i∈I Ki , and a surjective homomorphism h : S L. If we also assume that
L is finitely subdirectly irreducible (this suffices), then ker h is meet irreducible in
Con S. Since Con S is distributive, this makes ker h meet prime. Q
For any J ⊆ I, let πJ be the kernel of the projection of S onto j∈J Kj . Thus
for a, b ∈ S we have a πJ b iff aj = bj for all j ∈ J. Note that H ⊇ J implies
πH ≤ πJ , and that πJ∪K = πJ ∧ πK .
Let H = {J ⊆ I : πJ ≤ ker h}. By the preceding observations,
(1) I ∈ H and ∅ ∈/ H,
(2) H is an order filter in P(I),
(3) J ∪ K ∈ H implies J ∈ H or K ∈ H.
However, H need not be a (lattice) filter. Let us therefore consider
By Zorn’s Lemma, Q contains a maximal member with respect to set inclusion, say
U . Let us show that U is an ultrafilter.
If not, then by Lemma 7.5(2) there exists A ⊆ I such that A and I − A are both
not in U . By the maximality of U , this means that there exists a subset X ∈ U
such that A ∩ X ∈ / H. Similarly, there is a Y ∈ U such that (I − A) ∩ Y ∈
/ H. Let
76
Z = X ∩ Y . Then Z ∈ U , and hence Z ∈ H. However, A ∩ Z ⊆ A ∩ X, whence
A∩Z ∈/ H by (2) above. Likewise (I − A) ∩ Z ∈
/ H. But
(A ∩ Z) ∪ ((I − A) ∩ Z) = Z ∈ H,
References
1. K. Baker, Finite equational bases for finite algebras in a congruence-distributive equational
class, Advances in Math. 24 (1977), 207–243.
2. K. Baker and A. W. Hales, From a lattice to its ideal lattice, Algebra Universalis 4 (1974),
250–258.
3. J. L. Bell and A. B. Slomson, Models and Ultraproducts: an Introduction, North-Holland,
Amsterdam, 1971.
4. G. Birkhoff, On the lattice theory of ideals, Bull. Amer. Math. Soc. 40 (1934), 613–619.
5. G. Birkhoff, On the structure of abstract algebras, Proc. Cambridge Phil. Soc. 31 (1935),
433–454.
79
6. R. Dedekind, Über die drei Moduln erzeugte Dualgruppe, Math. Annalen 53 (1900), 371–403.
7. T. Evans, Some connections between residual finiteness, finite embeddability and the word
problem, J. London. Math. Soc. (2) 2 (1969), 399–403.
8. T. Frayne, A. Morel and D. Scott, Reduced direct products, Fund. Math. 51 (1962), 195–228.
9. R. Freese, Free modular lattices, Trans. Amer. Math. Soc. 261 (1980), 81–91.
10. C. Herrmann, Uber die von vier Moduln erzeugte Dualgruppe, Abh. Braunschweig. Wiss. Ges.
33 (1982), 157–159.
11. B. Jónsson, Algebras whose congruence lattices are distributive, Math. Scand. 21 (1967), 110–
121.
12. R. Kruse, Identities satisfied by a finite ring, J. Algebra 26 (1973), 298–318.
13. J. Los, Quelques remarques, théorèmes et problèmes sur le classes définissables d’algèbras,
Mathematical interpretations of formal systems, North-Holland, Amsterdam, 1955.
14. R. McKenzie, Equational bases for lattice theories, Math. Scand. 27 (1970), 24–38.
15. R. McKenzie, Finite equational bases for congruence modular varieties, Algebra Universalis
24 (1987), 224-250.
16. G. McNulty, How to construct finite algebras which are not finitely based, Universal Algebra
and Lattice Theory (Charleston, S.C., 1984), Lecture Notes in Math., vol. 1149, Springer,
Berlin-New York, 1985, pp. 167–174.
17. J. B. Nation, A counterexample to the finite height conjecture, Order 13 (1996), 1–9.
18. S. Oates and M. B. Powell, Identical relations in finite groups, J. Algebra 1 (1964), 11–39.
80
8. Distributive Lattices
In this chapter and the next we will look at the two most important lattice
varieties: distributive and modular lattices. Let us set the context for our study of
distributive lattices by considering varieties generated by a single finite lattice. A
variety V is said to be locally finite if every finitely generated lattice in V is finite.
Equivalently, V is locally finite if the relatively free lattice FV (n) is finite for every
integer n > 0.
Theorem 8.1. If L is a finite lattice and V = HSP(L), then
|FV (n)| ≤ |L||L| .
n
We should note that not every locally finite lattice variety is generated by a finite
lattice.
Now it is clear that there is a unique minimum nontrivial lattice variety, viz., the
one generated by the two element lattice 2, which is isomorphic to a sublattice of
any nontrivial lattice. We want to show that HSP(2) is the variety of all distributive
lattices.
Lemma 8.2. The following lattice equations are equivalent.
(1) x ∧ (y ∨ z) ≈ (x ∧ y) ∨ (x ∧ z)
(2) x ∨ (y ∧ z) ≈ (x ∨ y) ∧ (x ∨ z)
(3) (x ∨ y) ∧ (x ∨ z) ∧ (y ∨ z) ≈ (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z)
1 The kernels of distinct homomorphisms need not be distinct, of course, but that is okay.
n
is sometimes useful to view this argument constructively: FV (X) is the sublattice of L|L|
2 It
(x ∨ y) ∧ (x ∨ z) = [(x ∨ y) ∧ x] ∨ [(x ∨ y) ∧ z]
= x ∨ (x ∧ z) ∨ (y ∧ z)
= x ∨ (y ∧ z)
whence (2) holds. Thus (1) implies (2), and dually (2) implies (1).
Similarly, applying (1) to the left hand side of (3) yields the right hand side, so
(1) implies (3). Conversely, assume that (3) holds in a lattice L. For x ≥ y, equation
(3) reduces to x ∧ (y ∨ z) = y ∨ (x ∧ z), which is the modular law, so L must be
modular. Now for arbitrary x, y, z in L, meet x with both sides of (3) and then use
modularity to obtain
x ∧ (y ∨ z) = x ∧ [(x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z)]
= (x ∧ y) ∨ (x ∧ z) ∨ (x ∧ y ∧ z)
= (x ∧ y) ∨ (x ∧ z)
since x ≥ (x ∧ y) ∨ (x ∧ z). Thus (3) implies (1). (Note that since (3) is self-dual,
the second argument actually makes the first one redundant.)
In the first Corollary of the next chapter, we will see that a lattice is distributive
if and only if it contains neither N5 nor M3 as a sublattice. But before that, let us
look at the wonderful representation theory of distributive lattices. A few moments
reflection on the kernel of a homomorphism h : L 2 should yield the following
conclusions.3
Lemma 8.3. Let L be a lattice and h : L 2 = {0, 1} a surjective homomorphism.
Then h−1 (0) is an ideal of L, h−1 (1) is a filter, and L is the disjoint union of h−1 (0)
and h−1 (1).
Conversely, if I is an ideal of L and F a filter such that L = I ∪F ˙ (disjoint
union), then the map h : L → 2 given by
0 if x ∈ I,
h(x) =
1 if x ∈ F.
is a surjective homomorphism.
This raises the question: When is the complement L − I of an ideal a filter? The
answer is easy. A proper ideal I of a lattice L is said to be prime if x ∧ y ∈ I implies
3 This is one point where we really don’t want to assume that L has a 0 and 1. So in this
chapter, an ideal of a lattice means a nonempty subset I such that x ∨ y ∈ I whenever x, y ∈ I,
and z ∈ I whenever z ≤ x ∈ I. A filter is defined dually.
82
x ∈ I or y ∈ I. Dually, a proper filter F is prime if x ∨ y ∈ F implies x ∈ F or
y ∈ F . It is straightforward that the complement of an ideal I is a filter iff I is a
prime ideal iff L − I is a prime filter.
This simple observation allows us to work with prime ideals or prime filters (in-
terchangeably), rather than ideal/filter pairs, and we shall do so.
Theorem 8.4. Let D be a distributive lattice, and let a b in D. Then there exists
a prime filter F with a ∈ F and b ∈
/ F.
Proof. Now 1/a is a filter of D containing a and not b, so by Zorn’s Lemma there
is a maximal such filter (with respect to set containment), say M . For any x ∈
/ M,
the filter generated by x and M must contain b, whence b ≥ x ∧ m for some m ∈ M .
Suppose x, y ∈ / M , with say b ≥ x ∧ m and b ≥ y ∧ n where m, n ∈ M . Then by
distributivity
b ≥ (x ∧ m) ∨ (y ∧ n) = (x ∨ y) ∧ (x ∨ n) ∧ (m ∨ y) ∧ (m ∨ n).
Now let D be any distributive lattice, and let TD = {ϕ ∈ Con D : D/ϕ ∼ = 2}.
TheoremT8.4 says that if a 6= b in D, then there exists ϕ ∈ TD with (a, b) ∈
/ ϕ,
whence TD = 0 in Con D, i.e., D is a subdirect product of two element lattices.
Corollary. The two element lattice 2 is the only subdirectly irreducible distributive
lattice. Hence D = HSP(2).
Theorem 8.5. Let D be a distributive lattice, and let S be the set of all prime filters
of D. Then the map φ : D → P(S) by
φ(x) = {F ∈ S : x ∈ F }
is a lattice embedding.
Proof. In a distributive lattice, every join irreducible element is join prime, because
p ≤ x ∨ y is the same as p = p ∧ (x ∨ y) = (p ∧ x) ∨ (p ∧ y).
For any finite lattice, the map φ : L → O(J(L)) given by φ(x) = x/0 ∩ J(L)
is order preserving (in fact, meet preserving) and one-to-one. To establish the
isomorphism of (2), we need to know that for a distributive lattice it is onto. If D is
distributive
W and I is an order ideal Wof J(D), then for p ∈ J(D) we have by (1) that
p ≤ I iff p ∈ I, and hence I = φ( I).
The join decomposition of (3) is then obtained by taking A to be the set of
maximal elements of a/0 ∩ J(D).
It is clear that the same proof works if D is an algebraic distributive lattice
whose compact elements satisfy the DCC. In Theorem 10.6 we will characterize
those distributive lattices isomorphic to O(P) for some ordered set P.
As an application, we can give a neat description of the free distributive lattice
FD (n) for any finite n, which we already know to be a finite distributive lattice. Let
X = {x1 , . . . , xn }. Now it is not hard to see that any element
W in a free distributive
lattice can be written as a join of meets of generators, w = wi with wi = xi1 ∧. . .∧
xik . Another easy argument shows that the meet V of a nonempty
V proper subset of
the generators is join prime in FD (X); note that ∅ = 1 and X = 0 do not count.
(See Exercise 3). Thus the set of join irreducible elements of FD (X) is isomorphic
to the (dual of, but it is self-dual) ordered set of nonempty, proper subsets of X, and
the free distributive lattice is isomorphic to the lattice of order ideals of that. As
an example, FD (3) and its ordered set of join irreducibles are shown in Figure 8.1.
Dedekind [6] showed that |FD (3)| = 18 and |FD (4)| = 166. Several other small
values are known exactly, and the rest can be obtained in principle, but they grow
quickly (see Quackenbush [10]). While there exist more accurate expressions, the
simplest estimate is an asymptotic formula due to D. J. Kleitman:
n
log2 |FD (n)| ∼ .
bn/2c
The representation by sets of Theorem 8.5 does not preserve infinite joins and
meets. The corresponding characterization of complete distributive lattices which
have a complete representation as a lattice of subsets is derived from work of Alfred
Tarski and S. Papert [9], and was surely known to both of them. W An element p of
a complete lattice L is said to be completely join prime if p ≤ X implies p ≤ x
84
x y z
x y z
References
1. M. E. Adams and J. Sichler, Lattices with unique complementation, Pacific J. Math. 92 (1981),
1–13.
2. H. J. Bandelt, Complemented continuous lattices, Arch. Math. (Basel) 36 (1981), 474–475.
3. H. J. Bandelt and R. Padmanabhan, A note on lattices with unique comparable complements,
Abh. Math. Sem. Univ. Hamburg 48 (1979), 112–113.
88
4. G. Birkhoff and M. Ward, A characterization of Boolean algebras, Ann. of Math. 40 (1939),
609–610.
5. B. Davey and H. Priestley, Introduction to Lattices and Order, Cambridge University Press,
Cambridge, 1990.
6. R. Dedekind, Über die drei Moduln erzeugte Dualgruppe, Math. Annalen 53 (1900), 371–403.
7. R. P. Dilworth, Lattices with unique complements, Trans. Amer. Math. Soc. 57 (1945), 123–
154.
8. E. V. Huntington, Sets of independent postulates for the algebra of logic, Trans. Amer. Math.
Soc. 5 (1904), 288–309.
9. S. Papert, Which distributive lattices are lattices of closed sets?, Proc. Cambridge Phil. Soc.
55 (1959), 172–176.
10. R. Quackenbush, Dedekind’s problem, Order 2 (1986), 415–417.
11. V. N. Saliı̆, A compactly generated lattice with unique complements is distributive, Mat. Za-
metki 12 (1972), 617–620. (Russian)
12. V. N. Saliı̆, A continuous uniquely complemented lattice is distributive, Fifth All-Union Conf.
Math. Logic, Abstracts of Reports, Inst. Mat. Sibirsk. Otdel. Akad. Nauk SSSR, Novosibirsk,
1979, p. 134. (Russian)
13. M. H. Stone, The theory of representations of Boolean Algebras, Trans. Amer. Math. Soc. 40
(1936), 37–111.
14. V. N. Saliı̆, Lattices with unique complements, Translations of the Amer. Math. Soc., vol. 69,
Amer. Math. Soc., Providence, R. I., 1988.
89
9. Modular Lattices
To dance beneath the diamond sky with one hand waving free ...
–Bob Dylan
The modular law was invented by Dedekind to reflect a crucial property of the
lattice of subgroups of an abelian group, or more generally the lattice of normal
subgroups of a group. In this chapter on modular lattices you will see the lattice
theoretic versions of some familiar theorems from group theory. This will lead us
naturally to consider semimodular lattices.
Likewise, the lattice of submodules of a module over a ring is modular. Thus our
results on modular lattices apply to the lattice of ideals of a ring, or the lattice of
subspaces of a vector space. These applications make modular lattices particularly
important.
The smallest nonmodular lattice is N5 , which is called the pentagon. Dedekind’s
characterization of modular lattices is simple [3].
Theorem 9.1. A lattice is modular if and only if it does not contain the pentagon
as a sublattice.
Theorem 9.2. A modular lattice is distributive if and only if it does not contain
the diamond as a sublattice.
x y∨z
x ∧ (y ∨ z)
z
y ∨ (x ∧ z)
y x∧z
y∧z
Figure 9.1: FL(2 + 1)
verify that it is correct.1 The interval between the two elements above is a diamond
in FM (3), and the corresponding elements will form a diamond in L.
The details go as follows. The middle elements of our diamond should be
[x ∧ (y ∨ z)] ∨ (y ∧ z) = [x ∨ (y ∧ z)] ∧ (y ∨ z)
[y ∧ (x ∨ z)] ∨ (x ∧ z) = [y ∨ (x ∧ z)] ∧ (x ∨ z)
[z ∧ (x ∨ y)] ∨ (x ∧ y) = [z ∨ (x ∧ y)] ∧ (x ∨ y)
where in each case the equality follows from modularity. The join of the first pair
of elements is (using the first expressions)
1 Recall from Chapter 7, though, that F (n) is infinite and has an unsolvable word problem
M
for n ≥ 4.
91
x y z
µa (x) = x ∧ a
νb (x) = x ∨ b.
Dedekind showed that these maps play a special role in the structure of modular
lattices.
Theorem 9.3. If a and b are elements of a modular lattice L, then µa and νb are
mutually inverse isomorphisms, whence (a ∨ b)/b ∼
= a/(a ∧ b).
Proof. Clearly, µa and νb are order preserving. They are mutually inverse maps by
modularity: for if x ∈ (a ∨ b)/b, then
νb µa (x) = b ∨ (a ∧ x) = (b ∨ a) ∧ x = x
a = a0 ≺ a1 ≺ · · · ≺ an = b.
δ(x) = n if 0 = c0 ≺ c1 ≺ · · · ≺ cn = x.
By Theorem 9.4, δ is well defined. For semimodular lattices the properties of the
dimension function can be summarized as follows.
Theorem 9.5. If L is a semimodular lattice and every principal ideal has only finite
maximal chains, then the dimension function on L has the following properties.
(1) δ(0) = 0,
(2) x > y implies δ(x) > δ(y),
(3) x y implies δ(x) = δ(y) + 1,
(4) δ(x ∨ y) + δ(x ∧ y) ≤ δ(x) + δ(y).
Conversely, if L is a lattice which admits an integer valued function δ satisfying (1)–
(4), then L is semimodular and principal ideals have only finite maximal chains.
Proof. Given a semimodular lattice L in which principal ideals have only finite
maximal chains, properties (1) and (2) are obvious, while (3) is a consequence of
Theorem 9.4. The only (not very) hard part is to establish the inequality (4). Let x
and y be elements of L, and consider the join map νx : y/(x ∧ y) → (x ∨ y)/x defined
by νx (z) = z ∨ x. Recall that, by semimodularity, u v implies u ∨ x v ∨ x. Hence
νx takes maximal chains in y/(x ∧ y) to maximal chains in (x ∨ y)/x. So the length
of (x ∨ y)/x is at most that of y/(x ∧ y), i.e.,
Figure 9.3
0 = c0 ≺ c1 ≺ · · · ≺ cn = 1
0 = d0 ≺ d1 ≺ · · · ≺ dn = 1.
Then there is a permutation π of the set {1, . . . , n} such that ci /ci−1 is projective
to dπ(i) /dπ(i)−1 for all i.
Proof. Again we use induction on n. We may assume c1 6= d1 , for otherwise the
result follows by induction. Then c1 /0 transposes up to (c1 ∨ d1 )/d1 , and d1 /0
transposes up to (c1 ∨ d1 )/c1 .
Let c1 ∨ d1 = e2 ≺ e3 ≺ · · · ≺ en = 1 be a maximal chain in 1/(c1 ∨ d1 ). By
induction, there is a permutation σ of {2, . . . , n} such that ci /ci−1 is projective to
eσ(i) /eσ(i)−1 if σ(i) 6= 2, and ci /ci−1 is projective to e2 /c1 = (c1 ∨ d1 )/c1 if σ(i) = 2.
Similarly, there is a permutation τ of {2, . . . , n} such that dj /dj−1 is projective
to eτ (j) /eτ (j)−1 if τ (j) 6= 2, and dj /dj−1 is projective to e2 /d1 = (c1 ∨ d1 )/d1 if
τ (j) = 2. Now just check that the permutation π of {1, . . . , n} given by
−1
τ σ(k) if k > 1 and σ(k) 6= 2
π(k) = 1 if k > 1 and σ(k) = 2
−1
τ (2) if k = 1
C e2 D
c1 d1
Figure 9.4
H = H0 / H1 / . . . / Hm = G
K = K0 / K1 / . . . / Kn = G.
H ∩ K / H ∩ K1 / H ∩ K2 / . . . H ∩ G = H / H1 / . . . / G.
a = q 1 ∧ . . . ∧ q m = r1 ∧ . . . ∧ r n
is an irredundant decomposition.
V V
Proof. Let a = Q = R be two irredundant finite V decompositions (dropping
the subscripts temporarily). Fix q ∈ Q, and let q = (Q − {q}). By modularity,
q ∨ q/q ∼
= q/q ∧ q = q/a. Since q is meet V irreducible
V in L, this implies that a is meet
irreducible in q/a. However, a = q ∧ R = r∈R (q ∧ r) takes place in q/a, so we
must have a = q ∧ r for some r ∈ V R.
Next we observe
V that a = r ∧ (Q − {q}) is irredundant. For if not, we would
have a = r ∧ S irredundantly for some proper subset V S ⊂V Q − {q}. Reapplying
the first argument to V the two decompositions a = r ∧ S = Q with the element
r, we obtain a = q 0 ∧ S for some q 0 ∈ Q, contrary to the irredundance of Q.
It remains to show that |Q| = |R|. Let Q = V {q1 , . . . , qm } say.VBy the first part,
there is an element r1 ∈ R such that a = r1 ∧ (Q − {q1 }) = R irredundantly.
Applying the argument to these two V decompositions and V q2 , there is an element
r2 ∈ R such that a = r1 ∧ r2 ∧ (Q − {q1 , q2 }) = V R. Moreover, r1 and r2
are distinct, for otherwise we would
V have a = r 1 ∧ (Q − {q1 , q2 }), contradicting
the irredundance of a = r1 ∧ (Q − {q1 }). Continuing, we can replace q3 by an
element r3 of R, distinct from r1 and r2 , and so forth. After m steps, we obtain
a = r1 ∧ · · · ∧ rm , whence R = {r1 , . . . , rm }. Thus |Q| = |R|.
With a bit of effort, this can be improved to a simultaneous exchange theorem.
V V
Theorem 9.10. If a is an element of a modular lattice and a = Q = R are
two irredundant finite decompositions of a, then for each q ∈ Q there is an r ∈ R
such that ^ ^
a = r ∧ (Q − {q}) = q ∧ (R − {r}).
The proof of this, and much more on the general theory of decompositions in
lattices, can be found in Crawley and Dilworth [2]; see also Dilworth [5].
Now Theorems 9.9 and 9.10 are exactly what we want in a finite dimensional mod-
ular lattice. However, in algebraic modular lattices, finite decompositions into meet
irreducible elements need not coincide with the (possibly infinite) decomposition
into completely meet irreducible elements given by Birkhoff’s Theorem. Consider,
for example, the chain C = (ω + 1)d , the dual of ω + 1. This satisfies the ACC, and
hence is algebraic. The least element of C is meet irreducible, but not completely
99
meet irreducible. In the direct product C n , the least element has a finite decom-
position into n meet irreducible elements, but every decomposition into completely
meet irreducibles is necessarily infinite.
Fortunately, the proof of Theorem 9.9 adapts nicely to give us a version suitable
for algebraic modular lattices.
V
Theorem 9.11. Let a be an element of a modular lattice. If a = Q is a finite, V
irredundant decomposition into completely meet irreducible elements, and a = R
is another decomposition into meet irreducible
V elements, then there exists a finite
subset R0 ⊆ R with |R0 | = |Q| such that a = R0 irredundantly.
The application of Theorem 9.11 to subdirect products is immediate.
Corollary. Let A be an algebra such that Con A is a modular lattice. If A has
a finite subdirect decomposition into subdirectly irreducible algebras, then every ir-
redundant subdirect decomposition of A into subdirectly irreducible algebras has the
same number of factors.
A more important application is to the theory of direct decompositions of con-
gruence modular algebras. (The corresponding congruences form a complemented
sublattice of Con A.) This subject is treated thoroughly in McKenzie, McNulty
and Taylor [9].
Let us close this section by mentioning a nice combinatorial result about finite
modular lattices, due to R. P. Dilworth [4].
Theorem 9.12. In a finite modular lattice L, let Jk (L) be the set of elements which
cover exactly k elements, and let Mk (L) be the set of elements which are covered by
exactly k elements. Then |Jk (L)| = |Mk (L)| for any integer k ≥ 0.
In particular, the number of join irreducible elements in a finite modular lattice
is equal to the number of meet irreducible elements.
We will return to modular lattices in Chapter 12.
References
1. G. Birkhoff, Lattice Theory, First edition, Colloquium Publications, vol. 25, Amer. Math. Soc.,
Providence, R. I., 1940.
2. P. Crawley and R. P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall, Englewood Cliffs,
N. J., 1973.
3. R. Dedekind, Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler, Fest-
schrift der Herzogl. technische Hochschule zur Naturforscher-Versammlung, Braunschweig (1897),
Reprinted in “Gesammelte mathematische Werke”, Vol. 2, pp. 103–148, Chelsea, New York,
1968.
4. R. P. Dilworth, Proof of a conjecture on finite modular lattices, Ann. of Math. 60 (1954),
359–364.
5. R. P. Dilworth, Structure and Decomposition Theory, Proceedings of Symposia on Pure Math-
ematics: Lattice Theory, vol. II, Amer. Math. Soc., Providence, R. I., 1961.
6. G. Grätzer, Equational classes of lattices, Duke Jour. Math. 33 (1966), 613–622.
7. B. Jónsson, Equational classes of lattices, Math. Scand. 22 (1968), 187–196.
8. B. Jónsson and I. Rival, Lattice varieties covering the smallest non-modular variety, Pacific J.
Math. 82 (1979), 463–478.
9. R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, vol. I, Wadsworth and
Brooks-Cole, Belmont, CA, 1987.
10. H. Wielandt, Eine Verallgemeinerung der invarianten Untergruppen, Math. Zeit. 45 (1939),
209–244.
101
10. Finite Lattices and their Congruence Lattices
In this chapter we want to study the structure of finite lattices, and how it is
reflected in their congruence lattices. There are different ways of looking at lattices,
each with its own advantages. For the purpose of studying congruences, it is useful
to represent a finite lattice as the lattice of closed sets of a closure operator on its
set of join irreducible elements. This is an efficient way to encode the structure, and
will serve us well.1
The approach to congruences taken in this chapter is not the traditional one. It
evolved from techniques developed over a period of time by Ralph McKenzie, Bjarni
Jónsson, Alan Day, Ralph Freese and J. B. Nation for dealing with various specific
questions (see [1], [4], [6], [7], [8], [9]). Gradually, the general usefulness of these
methods dawned on us.
In the simplest case, recall that a finite distributive lattice L is isomorphic to
the lattice of order ideals O(J(L)), where J(L) is the ordered set of nonzero join
irreducible elements of L. This reflects the fact that join irreducible elements in a
distributive lattice are join prime. In a nondistributive lattice, we seek a modification
which will keep track of the ways in which one join irreducible is below the join of
others. In order to do this, we must first develop some terminology.
Rather than just considering finite lattices, we can include with modest addi-
tional effort a larger class of lattices satisfying a strong finiteness condition. Recall
that a lattice L is principally chain finite if no principal ideal of L contains an infi-
nite chain (equivalently, every principal ideal x/0 satisfies the ACC and DCC). In
Theorem 11.1, we will see where this class arises naturally in an important setting.2
Recall that if X, Y ⊆ L, we say that X refines Y (written X Y ) if for each
x ∈ X there exists y ∈ Y with x ≤ y. It is easy to see that the relation is a
quasiorder (reflexive and transitive), but not in general antisymmetric. Note X ⊆ Y
implies X Y .
If q ∈ J(L) is completely join irreducible, let q∗ denote the unique element of
L with q q∗ . Note that if L is principally chain finite, then q∗ exists for each
q ∈ J(L).
1 For an alternate approach, see Appendix. 3
2 Many of the results in this chapter can be generalized to arbitrary lattices. However, these
generalizations have not yet proved to be very useful unless one assumes at least the DCC.
101
W
W expression of a ∈ L is a finite set B such that a = B. A join expression
A join
a = B is minimal ifWit is irredundant and B cannot be properly refined, i.e.,
B ⊆ J(L) and a > b∗ ∨W (B − {b}) for each bW∈ B. An equivalent way to write this
technically is that a = B minimally if a = C and C W B implies B ⊆ C.
A join coverW of p ∈ L is a finite set A such that p ≤ A. A join cover A of p
is minimal if A isWirredundant and A cannot be properly refined to another join
cover of p, i.e., p ≤ B and B A implies A ⊆ B.
We define a binary relation D on J(L) as follows: p D q if there exists x ∈ L
such that p ≤ q ∨ x but p 6≤ q∗ ∨ x. This relation will play an important role in our
analysis of the congruences of a principally chain finite lattice.3
The following lemma summarizes some properties of principally chain finite lat-
tices and the relation D.
Lemma 10.1. Let L be a principally chain finite lattice.
(1) If b 6≤ a in L, then there exists p ∈ J(L) with p ≤ b and p 6≤ a.
(2) Every join expression in L refines to a minimal join expression, and every
join cover refines to a minimal join cover.
(3) For p, q ∈ J(L) we have p D q if and only if q ∈ A for some minimal join
cover A of p.
Proof. (1) Since b 6≤ a and b/0 satisfies the DCC, the set {x ∈ b/0 : x 6≤ a} has at
least
W one minimal element p. Because y < p implies y ≤ a for any y ∈ L, we have
{y ∈ L : y < p} ≤ p ∧ a < p, and hence p ∈ J(L) with p∗ = p ∧ a. W
(2) Suppose L contains an element s with a join representation s = F which
does not refine to a minimal one. Since the DCC holds in s/0, there W is an element
t ≤ s minimal with respect to having a join representation t = A which fails to
refine to a minimal one.
W Clearly t is join reducible, and there is a proper, irredundant
join expression t = B with B A.
Let B = {b1 , . . . , bk }. Using the DCC on b1 /0, we can find c1 ≤ b1 such that
t = c1 ∨b2 ∨. . .∨bk , but c1 cannot be replaced by any lower element: t > u∨b2 ∨. . . bk
whenever u < c1 . Now apply the same argument to b2 and {c1 , b2 , . . . , bk }. After k
such steps we obtain a join cover C which refines B and is minimal pointwise: no
element can be replaced by a (single) lower element.
The elements of C may not be join irreducible, but each element of C is strictly
below t, and hence has a minimal join expression. ChooseSa minimal join expression
Ec for each c ∈ C. It is not hard to check that E = c∈C Ec is a minimal join
expression for t, and E C B A, which contradicts the choice W of t and B.
Now let u ∈ L and W let A be a join cover of u, i.e., u ≤ A. We can find
B ⊆ A such that u ≤ B irredundantly. As above, refine B to a pointwise minimal
3 Note that D is reflexive, i.e., p D p for all p ∈ J(L). The relation D, defined similarly
except that it requires p 6= q, is also important, and D stands for “D or equal to.” For describing
congruences, it makes more sense to use D rather than D.
102
join cover
S C. Now we know that minimal join expressions exist, so we may define
E = c∈C Ec exactly as before. Then E will be a minimal join cover of u, and again
E C B A.
(3) Assume p D q, and let x ∈ L be such that p ≤ q ∨ x but p 6≤ q∗ ∨ x. By (2),
we can find a minimal join cover A of p with A {q, x}. Since p 6≤ q∗ ∨ x, we must
have q ∈ A.
Conversely, if A is a minimal Wjoin cover of p, and q ∈ A, then we fulfill the
definition of p D q by setting x = (A − {q}).
Theorem 10.2. If L is a principally chain finite lattice, then the map φ with φ(x) =
{p ∈ J(L) : p ≤ x} is an isomorphism of L onto the lattice of compact Γ-closed
subsets of J(L).
W
Proof. Note that if x = A is a minimal join expression, then φ(x) = Γ(A), so φ(x)
is indeed a compact Γ-closed set. The map φ is clearly order preserving, andWit is
one-to-one by part (1) of Lemma 10.1. Finally, φ is onto because Γ(F ) = φ( F )
for each finite F ⊆ J(L).
Lemma 10.6. The following are equivalent for a distributive algebraic lattice D.
(1) D is isomorphic to the lattice of order ideals of an ordered set.
(2) Every element of D is a join of completely join prime elements.
(3) Every compact element of D is a join of (finitely many) join irreducible
compact elements.
Now it is not hard to find lattices where these conditions fail. Nonetheless,
distributive algebraic lattices with the properties of Lemma 10.6 are a nice class
(including all finite distributive lattices), and it behooves us to try to represent each
of them as Con L for some principally chain finite lattice L. We need to begin by
seeing how QL can be recovered from Con L.
106
Theorem 10.8. Let D be a distributive algebraic lattice which is isomorphic to
O(P) for some ordered set P. Then there is a principally chain finite lattice L such
that D ∼
= Con L.
Proof. We must construct L with QL ∼ = P. In view of Theorem 10.3 we should try
to describe L as the lattice of finitely generated closed sets of a closure operator on
an ordered set J. Let P 0 and P 1 be two unordered copies of the base set P of P,
disjoint except on the maximal elements of P. Thus J = P 0 ∪ P 1 is an antichain,
and p0 = p1 if and only if p is maximal in P. Define a subset C of J to be closed if
{pj , q k } ⊆ C implies pi ∈ C whenever p < q in P and {i, j} = {0, 1}. Our lattice L
will consist of all finite closed subsets of J, ordered by set inclusion.
It should be clear that we have made the elements of J atoms of L and
p i ≤ pj ∨ q k
whenever p < q in P. Thus pi D q k iff p ≤ q. (This is where you want only one copy
of each maximal element). It remains to check that L is indeed a principally chain
finite lattice with QL ∼ = P, as desired. The crucial observation is that the closure of
a finite set is finite. We will leave this verification to the reader.
Theorem 10.8 is due to R. P. Dilworth in the 1940’s, but his proof was never
published. The construction given is from George Grätzer and E. T. Schmidt [5].
We close this section with a new look at a pair of classic results. A lattice is said
to be relatively complemented if a < x < b implies there exists y such that x ∧ y = a
and x ∨ y = b.5
Theorem 10.9. If L is a principally chain finite lattice which is either modular
or relatively complemented, then the relation D is symmetric on J(L), and hence
Con L is a Boolean algebra.
Proof. First assume L is modular, and let p D q with p ≤ q ∨ x but p 6≤ q∗ ∨ x.
Using modularity, we have
(q ∧ (p ∨ x)) ∨ x = (q ∨ x) ∧ (p ∨ x) ≥ p,
p = p ∧ (q ∨ x) ≤ p ∧ (p∗ ∨ x) = p∗ ∨ (x ∧ p) = p∗ ,
not be.
107
Hence p∗ = q∗ = 0, and given x such that p ≤ q ∨ x, p 6≤ x, we want to find y
such that q ≤ p ∨ y, q 6≤ y. Using the ACC in q ∨ x/0, let y be maximal such that
x ≤ y < q ∨ x and p 6≤ y. If y < p ∨ y < q ∨ x, then the relative complement z of
p ∨ y in q ∨ x/y satisfies z > y and z 6≥ p, contrary to the maximality of y. Hence
p ∨ y = q ∨ x, i.e., q ≤ p ∨ y. Thus q D p.
Finally, if D is symmetric, then QL is an antichain, and thus O(QL ) is isomorphic
to the Boolean algebra P(QL ).
A lattice is simple if |L| > 1 and L has no proper nontrivial congruence relations,
i.e., Con L ∼ = 2. Theorem 10.9 says that a subdirectly irreducible, modular or
relatively complemented, principally chain finite lattice must be simple.
In the relatively complemented case we P get even more. Let Li (i ∈ I) be a collec-
tion of lattices with 0. The direct sum Li is the sublattice of the direct product
consisting of all elements which are only finitely non-zero. Combining Theorems
10.2 and 10.9, we obtain relatively easily a fine result of Dilworth [2].
Theorem 10.10. A relatively complemented principally chain finite lattice is a
direct sum of simple (relatively complemented principally chain finite) lattices.
Proof. Let L be a relatively complemented principally chain finite lattice. Then
every element of L is a finite join of join irreducible elements, every join irreducible
element is an atom, and the D relation is symmetric, i.e., p D q implies p ≡ q. We
Ṡ
can write J(L) as a disjoint union of ≡-classes, J(L) = i∈I Ai . Let
_
Li = {x ∈ L : x = F for some finite F ⊆ Ai }.
P to show that the Li ’s are ideals (and hence sublattices) of L, and that
We want
L∼= i∈I Li . W
The crucial technical detail is this: if p ∈ J(L), F ⊆ J(L) is finite, and p ≤ F ,
then p ≡ f for some f ∈ F . For F can be refined to a minimal join cover G of p,
and since join irreducible elements are atoms, we must have G ⊆ F . But p D g (and
hence p ≡ g) for each g ∈ G.
NowW we can show that each Li is W an ideal of L. Suppose y ≤ x ∈ Li . Then
x = F for some F ⊆ Ai , and y = H for some H ⊆ J(L). By the preceding
observation, H ⊆ Ai , and thus
P y ∈ Li . W
Define a map φ : L → i∈I Li by φ(x) = (xi )i∈I , where xi = (x/0 ∩ Ai ).
There are several things to check: that φ(x) is only finitely nonzero, that φ is one-
to-one and onto, and that it preserves meets and joins. None is very hard, so we
will only do the last one, and leave the rest to the reader.
We want to show that φ preserves joins, i.e., that (x ∨ y)i = xi ∨ yi . It suffices
to show that if p ∈ J(L) and p ≤ (x ∨ y)i , then p ≤ xi ∨ yi . Since Li is an ideal,
we have p ∈ Ai . Furthermore, since p ≤ x ∨ y, there is a minimal join cover F of p
refining {x, y}. For each f ∈ F , weWhave f ≤ x or f ≤ y, and p D f implies f ∈ Ai ;
hence f ≤ xi or f ≤ yi . Thus p ≤ F ≤ xi ∨ yi .
108
Exercises for Chapter 10
1. Do Exercise 1 of Chapter 5 using the methods of this chapter.
2. Use the construction from the proof of Theorem 10.8 to represent the distribu-
tive lattices in Figure 10.1 as congruence lattices of lattices.
References
1. A. Day, Characterizations of finite lattices that are bounded-homomorphic images or sublat-
tices of free lattices, Canad. J. Math 31 (1979), 69–78.
2. R. P. Dilworth, The structure of relatively complemented lattices, Ann. of Math. 51 (1950),
348–359.
110
3. R. Freese, Finitely presented lattices: canonical forms and the covering relation, Trans. Amer.
Math. Soc. 312 (1989), 841–860.
4. R. Freese and J. B. Nation, Covers in free lattices, Trans. Amer. Math. Soc. 288 (1985), 1–42.
5. G. Grätzer and E. T. Schmidt, On congruence lattices of lattices, Acta Math. Acad. Sci.
Hungar. 13 (1962), 179–185.
6. B. Jónsson and J. B. Nation, A report on sublattices of a free lattice, Coll. Math. Soc. János
Bolyai 17 (1977), 233–257.
7. R. McKenzie, Equational bases and non-modular lattice varieties, Trans. Amer. Math. Soc.
174 (1972), 1–43.
8. J. B. Nation, Lattice varieties covering V (L1 ), Algebra Universalis 23 (1986), 132–166.
9. J. B. Nation, An approach to lattice varieties of finite height, Algebra Universalis 27 (1990),
521–543.
111
11. Geometric Lattices
Now let us consider how we might use lattices to describe elementary geometry.
There are two basic aspects of geometry: incidence, involving such statements as
“the point p lies on the line l,” and measurement, involving such concepts as angles
and length. We will restrict our attention to incidence, which is most naturally
stated in terms of lattices.
What properties should a geometry have? Without being too formal, surely we
would want to include the following.
(1) The elements of a geometry (points, lines, planes, etc.) are subsets of a given
set P of points.
(2) The set P of all points is an element of the geometry, and the intersection
of any collection of elements is again one.
(3) There is a dimension function on the elements of the geometry, satisfying
some sort of reasonable conditions.
If we order the elements of a geometry by set inclusion, then we obtain a lattice in
which the atoms correspond to points of the geometry, every element is a join of
atoms, and there is a well-behaved dimension function defined. With a little more
care we can show that “well-behaved” means “semimodular” (recall Theorem 9.6).
On the other hand, there is no harm if we allow some elements to have infinite
dimension.
Accordingly, we define a geometric lattice to be an algebraic semimodular lattice
in which every element is a join of atoms. As we have already described, the points,
lines, planes, etc. (and the empty set) of a finite dimensional Euclidean geometry
(<n ) form a geometric lattice. Other examples are the lattice of all subspaces of
a vector space, and the lattice Eq X of equivalence relations on a set X. More
examples are included in the exercises.1
We should note here that the geometric dimension of an element is generally
one less than the lattice dimension δ: points are elements with δ(p) = 1, lines are
1 The basic properties of geometric lattices were developed by Garrett Birkhoff in the 1930’s [2].
Similar ideas were pursued by K. Menger, F. Alt and O. Schreiber at about the same time [10].
Traditionally, geometric lattices were required to be finite dimensional, meaning δ(1) = n < ∞.
The last two examples show that this restriction is artificial.
112
elements with δ(l) = 2, and so forth.
A lattice is said to be atomistic if every element is a join of atoms.
Theorem 11.1. The following are equivalent.
(1) L is a geometric lattice.
(2) L is an upper continuous, atomistic, semimodular lattice.
(3) L is isomorphic to the lattice of ideals of an atomistic, semimodular, prin-
cipally chain finite lattice.
This is true if L is modular, and also for L = Eq X with X finite ([5] and [7]). It
is known that w1 ≤ wk always holds for for 1 ≤ k < n ([1] and [4]). But a general
resolution of the conjecture still seems to be a long way off.
5. Show that the lattice for plane Euclidean geometry (<2 ) is not modular. (Hint:
Use two parallel lines and a point on one of them.)
6. (a) Let P and L be nonempty sets, which we will think of as “points” and
“lines” respectively. Suppose we are given an arbitrary incidence relation ∈ on P ×L.
Then we can make P ∪ L ∪ {0, 1} into a partially ordered set K in the obvious way,
interpreting p ∈ l as p ≤ l. When is K a lattice? atomistic? semimodular? modular?
subdirectly irreducible?
(b) Compare these results with Hilbert’s axioms for a plane geometry.
(i) There exists at least one line.
(ii) On each line there exist at least two points.
(iii) Not all points are on the same line.
(iv) There is one and only one line passing through two given distinct points.
7. Let L be a geometric lattice,
W and let A denote the set of atoms of L. A subset
S ⊆ A is independent if p 6≤ (S − {p}) for all p ∈ S. A subset B ⊆ A is a basis for
L if B is independent and ∨B = 1.
(a) Prove that L has a basis.
(b) Prove that if B and C are bases for L, then |B| = |C|.
(c) Show that the sublattice generated by an independent set S is isomorphic
to the lattice of all finite subsets of S.
8. A lattice is atomic if for every x > 0 there exists a ∈ L with x ≥ a 0. Prove
that every element of a complete, relatively complemented, atomic lattice is a join
of atoms.
116
9. Let I be an infinite set, and let X = {pi : i ∈ I}∪{q
˙ i : i ∈ I}. Define a subset
S of X to be closed if S = X or, for all i, at most one of pi , qi is in S. Let L be the
lattice of all closed subsets of X.
(a) Prove that L is a relatively complemented algebraic lattice with every ele-
ment the join of atoms.
(b) Show that the compact elements of L do not form an ideal.
(This example shows that the semimodularity hypothesis of Theorem 11.1 cannot
be omitted.)
10. Prove that Eq X is relatively complemented and simple.
References
1. J. G. Basterfield and L. M. Kelly, A characterization of sets of n points which determine n
hyperplanes, Proc. Camb. Phil. Soc. 64 (1968), 585–588.
2. G. Birkhoff, Abstract linear dependence and lattices, Amer. J. Math. 57 (1935), 800–804.
3. R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. 51 (1950),
161–166.
4. C. Greene, A rank inequality for finite geometric lattices, J. Comb. Theory 9 (1970), 357–364.
5. L. H. Harper, The morphology of partially ordered sets, J. Combin. Theory Ser. A 17 (1974),
44–58.
6. J. Hashimoto, Direct, subdirect decompositions and congruence relations, Osaka J. Math. 9
(1957), 87–112.
7. W. N. Hsieh and D. J. Kleitman, Normalized matching in direct products of partial orders,
Stud. Appl. Math. 52 (1973), 258–289.
8. L. Libkin, Direct decompositions of atomistic algebraic lattices, Algebra Universalis 33 (1995),
127–135.
9. S. Mac Lane, A lattice formulation for transcendence degrees and p-bases, Duke Math. J. 4
(1938), 455–468.
10. K. Menger, F. Alt, and O. Schreiber, New foundations of projective and affine geometry, Ann.
of Math. 37 (1936), 456–482.
117
12. Complemented Modular Lattices
Traditionally, complemented modular lattices are the alii 1 of lattices, and sub-
directly irreducible geometric modular lattices are the alii nui 2 . In this chapter we
will see why.
Lemma 12.1. Every complemented modular lattice is relatively complemented.
Proof. Let c be a complement of x in a modular lattice, and let a ≥ x ≥ b. Consider
the element z = a ∧ (b ∨ c), and note that z = b ∨ (a ∧ c) by modularity. Then
x ∧ z = x ∧ (b ∨ c) = b ∨ (x ∧ c) = b ∨ 0 = b, and dually x ∨ z = a. Thus z is a relative
complement of x in a/b.
Theorem 12.2. Every algebraic complemented modular lattice is geometric.
Proof. Let L be an algebraic complemented modular lattice. We need to show that
the atoms of L are join dense, i.e., a > b implies that there is an atom p with
p ≤ a and p b. But we know that L is weakly atomic, so there exist elements
c, d such that a ≥ c d ≥ b. Let p be a relative complement of d in c/0. Then
c/d = (p ∨ d)/d ∼= p/(p ∧ d) = p/0, whence p is an atom. Also p ≤ c ≤ a, while
p d implies p b.
The next result, though not needed in the sequel, is quite nice. It is due to Bjarni
Jónsson [2], extending O. Frink [1].
Theorem 12.3. Every complemented modular lattice can be embedded in a geomet-
ric modular lattice.
Sketch of Proof. Let L be a complemented modular lattice. Let F(L) denote the
lattice of filters of L ordered by reverse set inclusion, i.e., F ≤ G iff F ⊇ G. Since L
has a 0, every filter of L is contained in a maximal (w.r.t. set inclusion) filter; hence
F(L) is atomic (every nonzero element contains an atom). However, F(L) is dually
algebraic, so we form the ideal lattice I(F(L)), which is algebraic and is still atomic
(but Wit may not be atomistic). Let A denote the set of atoms of I(F(L)), and let
A = A, so that A is the ideal of F(L) generated by the maximal filters. Then the
1 Hawaiian chiefs.
2 Hawaiian big chiefs.
118
sublattice K = A/0 of I(F(L)) is modular, algebraic, and atomistic, whence it is
geometric. W
It remains to show that L is embedded into K by the map h(x) = {F ∈ A : x ∈
F }. This is a nontrivial (but doable) exercise.
Since every geometric modular lattice is a direct product of subdirectly irreducible
ones, the following lemma comes in handy.
Lemma 12.4. A geometric modular lattice is subdirectly irreducible if and only if
for each pair of distinct atoms p, q there is a third atom r such that p, q and r
generate a sublattice isomorphic to M3 .
Proof. First, suppose that the condition of the lemma holds in a geometric modular
lattice L. Since a geometric lattice is relatively complemented, every nontrivial
congruence relation on L collapses some atom to 0. The condition implies that
if one atom collapses to 0, then they all do. Thus the congruence µ generated
by collapsing all the atoms to 0 is the unique minimum nontrivial congruence of
L, making it subdirectly irreducible. (In fact, µ collapses every finite dimensional
quotient a/b of L; unless the lattice is finite dimensional, this is not the universal
congruence. See exercise 3.)
Conversely, assume that L is subdirectly irreducible. Then the compact elements
of L form a simple, principally chain finite lattice; otherwise, as in the proof of
Theorem 11.5, Lc would be a proper direct sum and L would be a direct product.
Thus |QLc | = 1, and for any two atoms p, q of L there is a sequence of atoms with
p = p0 D p1 D . . . D pn = q.
Therefore, by induction, it will suffice to prove the following two claims.
(i) If p, q and r are atoms of L with p D q D r, then p D r.
(ii) If p and q are distinct atoms with p D q, then there is an atom s such that
p, q and s generate a diamond.
Let us prove (ii) first. If p and q are distinct and p D q, then by definition there is
an element x ∈ L such that p ≤ q ∨ x but p q∗ ∨ x = x. Note that, by modularity,
q ∨ x x and hence p ∨ x = q ∨ x. Set s = x ∧ (p ∨ q). Since p ∨ q has dimension
2 and p x, we have s 0. Now p x implies p ∧ s ≤ p ∧ x = 0. Similarly
q x and that implies q ∧ s = 0, while p 6= q gives p ∧ q = 0. On the other hand,
p ∨ s = (p ∨ x) ∧ (p ∨ q) = p ∨ q, and similarly q ∨ s = p ∨ q. Thus p, q and s generate
an M3 .
To prove (i), assume p D q D r. Without loss of generality, these are distinct,
and hence by (ii) there exist atoms x and y such that p, q, x generate a diamond
and q, r, y likewise. Set z = (p ∨ r) ∧ (x ∨ y). Then
r ∨ z = (p ∨ r) ∧ (r ∨ x ∨ y)
= (p ∨ r) ∧ (x ∨ q ∨ y)
= (p ∨ r) ∧ (p ∨ q ∨ y) ≥ p.
119
Now there are two possibilities. If p z, then p D r via z, and we are done. So
assume p ≤ z. Then p ≤ x ∨ y and x ∨ y has dimension 2, so x ∨ y = p ∨ x = q ∨ x.
But then q ≤ x ∨ y, whence x ∨ y = q ∨ y also, i.e., the tops of the two diamonds
coincide. In particular p, q and r join pairwise to x ∨ y, so that again p D r.
It turns out that dimension plays an important role in subdirectly irreducible
geometric lattices. We define the dimension of a geometric lattice L to be the
length of a maximal chain in L. Thus δ(L) = δ(1) if δ(1) = n < ∞; more generally,
δ(L) = |B| where B is a basis for L (see exercise 11.7).
Of course 2 is the only geometric lattice with δ(L) = 1. Geometric lattices with
δ(L) = 2 are isomorphic to Mκ for some cardinal κ, and these are simple whenever
κ > 2.
Subdirectly irreducible geometric modular lattices with δ(L) > 2 correspond to
projective geometries of geometric dimension ≥ 2. In particular, for δ(L) = 3 they
correspond to projective planes. Projective planes come in two types: arguesian and
nonarguesian. The nonarguesian projective planes are sort of strange: we can con-
struct lots of examples of them, but there is no really good representation theorem
for them.
On the other hand, a theorem of classical projective geometry translates as fol-
lows.
Theorem 12.5. Every subdirectly irreducible geometric modular lattice with δ(L) ≥
4 is arguesian.
Now we are ready for the best representation theorem of them all, due to Birkhoff
and Frink (but based on older ideas from projective geometry). Recall that the lat-
tice of subspaces of any vector space is a subdirectly irreducible geometric arguesian
lattice.
Theorem 12.6. Let L be a subdirectly irreducible geometric arguesian lattice with
δ(L) = κ ≥ 3. Then there is a division ring D such that L is isomorphic to the
lattice of all subspaces of a κ-dimensional vector space over D.
A later version of these notes will include a proof of Theorem 12.6, but not this
one.
References
1. O. Frink, Complemented modular lattices and projective spaces of infinite dimension, Trans.
Amer. Math. Soc. 60 (1946), 452–467.
2. B. Jónsson, Modular lattices and Desargues’ theorem, Math. Scand. 2 (1954), 295–314.
3. J. von Neumann, Continuous Geometries, I. Halperin, ed., Princeton University Press, Prince-
ton, 1960.
121
Appendix 1: Cardinals, Ordinals and Universal Algebra
In these notes we are assuming you have a working knowledge of cardinals and
ordinals. Just in case, this appendix will give an informal summary of the most
basic part of this theory. We also include an introduction to the terminology of
universal algebra.
1. Ordinals
Let C be a well ordered set, i.e., a chain satisfying the descending chain condition
(DCC). A segment of C is a proper ideal of C, which (because of the DCC) is
necessarily of the form {c ∈ C : c < d} for some d ∈ C.
Lemma. Let C and D be well ordered sets. Then
(1) C is not isomorphic to any segment of itself.
(2) Either C ∼= D, or C is isomorphic to a segment of D, or D is isomorphic
to a segment of C.
We say that two well ordered sets have the same type if C ∼ = D. An ordinal is
an order type of well ordered sets. These are usually denoted by lower case Greek
letters: α, β, γ, etc. For example, ω denotes the order type of the natural numbers,
which is the smallest infinite ordinal. We can order ordinals by setting α ≤ β if
α∼ = β or α is isomorphic to a segment of β. There are too many ordinals in the
class of all ordinals to call this an ordered set without getting into set theoretic
paradoxes, but we can say that locally it behaves like one big well ordered set.
Theorem. Let β be an ordinal, and let B be the set of all ordinals α with α < β,
ordered by ≤. Then B ∼
= β.
For example, ω is isomorphic to the collection of all finite ordinals.
Recall that the Zermelo well ordering principle (which is equivalent to the Axiom
of Choice) says that every set can be well ordered. Another way of putting this is
that every set can be indexed by ordinals,
X = {xα : α < β}
for some β. Transfinite induction is a method of proof which involves indexing a set
by ordinals, and then applying induction on the indices. This makes sense because
the indices satisfy the DCC.
In doing transfinite induction, it is important to distinguish two types of ordinals.
β is a successor ordinal if {α : α < β} has a largest element. Otherwise, β is called
a limit ordinal. For example, every finite ordinal is a successor ordinal, and ω is a
limit ordinal.
122
2. Cardinals
We say that two sets X and Y have the same cardinality, written |X| = |Y |,
if there exists a one-to-one onto map f : X → Y . It is easy to see that “having
the same cardinality” is an equivalence relation on the class of all sets, and the
equivalence classes of this relation are called cardinal numbers. We will use lower
case german letters such as m, n and p to denote unidentified cardinal numbers.
We order cardinal numbers as follows. Let X and Y be sets with |X| = m and
|Y | = n. Put m ≤ n if there exists a one-to-one map f : X Y (equivalently, if
there exists an onto map g : Y X). The Cantor-Bernstein theorem says that this
relation is anti-symmetric: if m ≤ n ≤ m, then m = n, which is the hard part of
showing that it is a partial order.
Theorem. Let m be any cardinal. Then there is a least ordinal α with |α| = m.
m + n = |X ∪ Y |
m · n = |X × Y |
mn = |{f : Y → X}|
The finer points of the arithmetic can get complicated, but that will not bother
us here. The following facts are used frequently.
Theorem. Let X be an infinite set, P(X) the lattice of subsets of X, and Pf (X)
the lattice of finite subsets of X. Then |P(X)| = 2|X| and |Pf (X)| = |X|.
A fine little book [2] by Irving Kaplansky, Set Theory and Metric Spaces, is easy
reading and contains the proofs of the theorems above. The book Introduction
to Modern Set Theory by Judith Roitman [4] is recommended for a slightly more
advanced introduction.
1 Again, there are too many cardinals to talk about the “set of all cardinals”.
123
3. Universal Algebra
Once you have seen enough different kinds of algebras: vector spaces, groups,
rings, semigroups, lattices, even semilattices, you should be driven to abstraction.
The proper abstraction in this case is the general notion of an “algebra”. Univer-
sal algebra is the study of the properties which different types of algebras have in
common. Historically, lattice theory and universal algebra developed together, more
like Siamese twins than cousins. In these notes we do not assume you know much
universal algebra, but where appropriate we do use its terminology.
An operation on a set A is just a function f : An → A for some n ∈ ω. An algebra
is a system A = hA; Fi where A is a nonempty set and F is a set of operations on
A. Note that we allow infinitely many operations, but each has only finitely many
arguments. For example, lattices have two binary operations, ∧ and ∨. We use
different fonts to distinguish between an algebra and the set of its elements, e.g., A
and A.
Many algebras have distinguished elements, or constants. For example, groups
have a unit element e, rings have both 0 and 1. Technically, these constants are
nullary operations (with no arguments), and are included in the set F of operations.
However, in these notes we sometimes revert to a more old-fashioned notation and
write them separately, as A = hA; F, Ci, where F is the set of operations with at
least one argument and C is the set of constants. There is no requirement that
constants with different names, e.g., 0 and 1, be distinct.
A subalgebra of A is a subset S of A which is closed under the operations, i.e.,
if s1 , . . . , sn ∈ S and f ∈ F, then f (s1 , . . . , sn ) ∈ S. This means in particular that
all the constants of A are contained in S. If A has no constants, then we allow the
empty set as a subalgebra (even though it is not properly an algebra). Thus the
empty set is a sublattice of a lattice, but not a subgroup of a group. A nonempty
subalgebra S of A can of course be regarded as an algebra S of the same type as A.
If A and B are algebras with the same operation symbols (including constants),
then a homomorphism from A to B is a mapping h : A → B which preserves the
operations, i.e., h(f (a1 , . . . , an )) = f (h(a1 ), . . . , h(an )) for all a1 , . . . , an ∈ A and
f ∈ F. This includes that h(c) = c for all c ∈ C.
A homomorphism which is one-to-one is called an embedding, and sometimes
written h : A B or h : A ≤ B. A homomorphism which is both one-to-one and
onto is called an isomorphism, denoted h : A ∼ = B.
These notions directly generalize notions which should be perfectly familiar to
you for say groups or rings. Note that we have given only terminology, but no
results. The basic theorems of universal algebra are included in the text, either
in full generality, or for lattices in a form which is easy to generalize. For deeper
results in universal algebra, there are several nice textbooks available, including A
Course in Universal Algebra by S. Burris and H. P. Sankappanavar [1], and Algebras,
Lattices, Varieties by R. McKenzie, G. McNulty and W. Taylor [3].
124
References
1. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Springer-Verlag, New
York, 1980.
2. I. Kaplansky, Set Theory and Metric Spaces, Allyn and Bacon, Boston, 1972.
3. R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, vol. I, Wadsworth and
Brooks-Cole, Belmont, CA, 1987.
4. J. Roitman, Introduction to Modern Set Theory, Wiley, New York, 1990.
125
Appendix 2: The Axiom of Choice
128
Appendix 3: Formal Concept Analysis
In this situation, the lattice of closed sets Cπσ ⊆ P(A) is dually isomorphic to
Cσπ ⊆ P(B), and we say that R establishes a Galois connection between the πσ-
closed subsets of A and the σπ-closed subsets of B.
Of course, Cπσ is a complete lattice. Moreover, every complete lattice can be
represented via a Galois connection.
Theorem. Let L be a complete lattice, A a join dense subset of L and B a meet
dense subset of L. Define R ⊆ A × B by a R b if and only if a ≤ b. Then, with σ
and π defined as above, L ∼
= Cπσ (and L is dually isomorphic to Cσπ ).
In particular, for an arbitrary complete lattice, we can always take A = B = L. If
L is algebraic, a more natural choice is A = Lc and B = M ∗ (L) (compact elements
and completely meet irreducibles). If L is finite, the most natural choice is A = J(L)
and B = M (L). Again the proof of this theorem is elementary.
Formal Concept Analysis is a method developed by Rudolf Wille and his col-
leagues in Darmstadt (Germany), whereby the philosophical Galois connection be-
tween objects and their properties is used to provide a systematic analysis of cer-
tain very general situations. Abstractly, it goes like this. Let G be a set of “ob-
jects” (Gegenstände) and M a set of relevant “attributes” (Merkmale). The relation
I ⊆ G × M consists of all those pairs hg, mi such that g has the property m. A
concept is a pair hX, Y i with X ⊆ G, Y ⊆ M , X = π(Y ) and Y = σ(X). Thus
129
hX, Y i is a concept if X is the set of all elements with the properties of Y , and
Y is exactly the set of properties shared by the elements of X. It follows (as in
exercise 12, Chapter 2) that X ∈ Cπσ and Y ∈ Cσπ . Thus if we order concepts by
hX, Y i ≤ hU, V i iff X ⊆ U (which is equivalent to Y ⊇ V ), then we obtain a lattice
B(G, M, I) isomorphic to Cπσ .
A small example will illustrate how this works. The rows of Table A1 correspond
to seven fine musicians, and the columns to eight possible attributes (chosen by a
musically trained sociologist). An × in the table indicates that the musician has
that attribute.1 The corresponding concept lattice is given in Figure A2, where the
musicians are abbreviated by lower case letters and their attributes by capitals.
Table A1.
I=M J
B W
Cl o Co F
b=r m a h e
Figure A2
1 To avoid confusion, androgynous rock stars were not included.
130
Formal concept analysis has been applied to hundreds of real situations outside
of mathematics (e.g., law, medicine, psychology), and has proved to be a useful tool
for understanding the relation between the concepts involved. Typically, these ap-
plications involve large numbers of objects and attributes, and computer programs
have been developed to navigate through the concept lattice. A good brief intro-
duction to concept analysis may be found in Wille [2] or [3], and the whole business
is explained thoroughly in Ganter and Wille [1].
Likewise, the representation of a finite lattice as the concept lattice induced by
the order relation between join and meet irreducible elements (i.e., ≤ restricted to
J(L) × M (L)) provides and effective and tractable encoding of its structure. As an
example of the method, let us show how one can extract the ordered set QL such
that Con L ∼ = O(Q(L)) from the table.
Given a finite lattice L, for g ∈ J(L) and m ∈ M (L), define
g%m if g m but g ≤ m∗ , i.e., g ≤ n for all n > m,
m&g if m g but m ≥ g∗ , i.e., m ≥ h for all h < g,
glm if g % m and m & g.
Note that these relations can easily be added to the table of J(L) × M (L).
These relations connect with the relation D of Chapter 10 as follows.
Lemma. Let L be a finite lattice and g, h ∈ J(L). Then g D h if and only if there
exists m ∈ M (L) such that g % m & h.
Proof. If g D h, then there exists x ∈ L such that g ≤ h ∨ x but g h∗ ∨ x. Let m
be maximal such that m ≥ h∗ ∨ x but m g. Then m ∈ M (L), g ≤ m∗ , m ≥ h∗
but m h. Thus g % m & h.
Conversely, suppose g % m & h. Then g ≤ m∗ ≤ h ∨ m while g m = h∗ ∨ m.
Therefore g D h.
As an example, the table for the lattice in Figure A2 is given in Table A3. This is
a reduction of the original Table A1: J(L) is a subset of the original set of objects,
and likewise M (L) is contained in the original attributes. Arrows indicating the
relations %, & and l have been added. The Lemma allows us to calculate D
quickly, and we find that |QL | = 1, whence L is simple.
I=M Cl J Co B W F
b=r × × l l & × l
o × l × × % %
m × × × & × l l
h l & × & × l ×
e l & l × l × ×
a × l × × l × l
131
Table A3.
References
1. B. Ganter and R. Wille, Formale Begriffsanalyse: Mathematische Grundlagen, Springer-
Verlag, Berlin-Heidelberg, 1996.
2. R. Wille, Restructuring lattice theory: an approach based on hierarchies of concepts, Ordered
Sets, I. Rival, ed., Reidel, Dordrecht-Boston, 1982, pp. 445–470.
3. R. Wille, Concept lattices and conceptual knowledge systems, Computers and Mathematics
with Applications 23 (1992), 493–515.
132