Practical Foundations of Mathematics

Paul Taylor

3.2  Meets, Joins and Lattices

DEFINITION 3.2.1 Let (X, £ ) be a preorder and u Î X. Then u is

(a)

a least element or bottom if "q. u £ q,

(b)

a locally least element if "x,y.x £ y ³ uÞ u £ x (Exercise 3.5),

(c)

a minimal element if "x.x £ uÞ u £ x.

Likewise by reversing the order we say that u is

(d)

a greatest element or top if "g. u ³ g,

(e)

a maximal element if "x.x ³ uÞ u ³ x.

Bottom and top, if they exist, are written ^ and T respectively; if £ is antisymmetric then they are unique. (They are in any case unique up to ~ of Proposition 3.1.10.) The terms maximum and minimum (which are nouns) are also used to mean greatest and least elements, but should be avoided as a source of confusion. Local maxima and minima in the sense of elementary calculus are not formally related to any of these concepts.

EXAMPLES 3.2.2

(a)

False and true are least and greatest formulae under provability ( \vdash ).

(b)

Æ and X are the least and greatest subsets of any set X under Ì .

(c)

If ( £ ) = ( < )È( = ) with < irreflexive, then this definition agrees with the notion of minimality used in Proposition  2.5.6 (Exercise 3.3).

(d)

A lower subset is representable (Definition  3.1.7) iff it has a greatest element.

Meets and joins  

NOTATION 3.2.3 By abuse of notation, for g,q Î X and Á Ì X,

omitted eqnarray* environment

We do not extend the symbol £ to U £ V, but see Exercise  3.55 for three such orders on the set of subsets.

DEFINITION 3.2.4 Let (X, £ ) be a preorder and Á Ì X.

(a)

If g £ Á then we call g a lower bound for Á.

(b)

A greatest lower bound, ie a greatest element of {g|g £ Á} Ì X, the set of lower bounds, if such exists, is called a meet or infimum, and is denoted by ÙÁ; then the set of lower bounds is representable (Definition  3.1.7), namely by the meet.

(c)

Similarly, if Á £ q then we call q an upper bound for Á. A least upper bound, if any, is called a join or supremum, Ú Á.

If £ is antisymmetric then meets and joins, where they exist, are unique. Otherwise they are unique up to ~ from Proposition  3.1.10. See Exercises 3.5, 3.21 and 3.33ff for minimal and locally least upper bounds.

EXAMPLES 3.2.5

(a)

ÚÆ = ^ = ÙX and

Ù Æ = T = ÚX, if these exist.

(b)

If Á = {f,y} then we write Ú Á = fÚy and ÙÁ = fÙy.

(c)

Meets and joins of sets of subsets in the inclusion order are called intersections (Ç) and unions (È) respectively.

(d)

The union or intersection of a family of lower subsets is again lower.

(e)

The Dedekind reals, \realno_D (Remark  2.1.1), have meets and joins with respect to the arithmetical order for all bounded inhabited subsets; these are usually written as inf and sup respectively.

(f)

For the divisibility order on N, the meet and join of two numbers are called their greatest common divisor and least common multiple respectively. The extremal elements are ^ = 1 and T = 0. This conflict with the conventions of logic is resolved by considering ideals (Example  2.1.3(b)), for which I|JÛ J Ì I; this is the contravariant regular representation (Example  3.1.6(f)ff).

(g)

Arbitrary meets and joins in the type W of propositions are found using the guarded quantifiers (Remark  1.5.2):

Ú Á = $f.(f Î Á)Ùf        Ù Á = "f.(f Î Á) Þ f.

(h)

If Á Ì {^,T} is a complemented subset ( ie the predicate (x Î Á) is decidable), then Á has a meet and a join. Indeed there are only four cases to consider, depending on whether each of ^ and T does or does not belong to Á. Intuitionism has nothing to do with the finiteness of {^,T} in this case, but is concerned with the nature of the subset Á (or the predicate characterising it): we need excluded middle to say that {^, T} has meets and joins of all subsets.

DEFINITION 3.2.6 Let f:X® Y be a monotone function between preorders. If u is a meet of Á Ì X then fu is a lower bound of \funf_!(Á) Ì Y by monotonicity of f. (Recall the notation \funf_! from Remark 2.2.7.) Then f preserves the meet if fu is a greatest lower bound.

(If X and Y are posets then of course these meets are unique; the point of stressing preorders and being a meet is that no choice of meet is needed to define preservation, by an argument similar to Lemma  1.2.11. This will be important for limits and colimits in categories, Definition 4.5.10.)

We also say that f creates the meet if (a)  y = Ù\funf_!(Á) exists, (b) there is a unique x Î X (up to ~ ) such that y = f(x) and x £ Á, and, having fixed x, (c) in fact  x = ÙÁ.

Meets and joins of lower sets   The covariant regular representation (by lower sets, Definition  3.1.7) has both meets and joins, but it behaves quite differently with respect to them. Both cases are important.

PROPOSITION 3.2.7 The embedding X¯ (-):X\hookrightarrow shv(X)

(a)

is full and preserves any meets which exist, ie

X¯ æ è Ù Á ö ø = Ç x Î Á  (X¯ x),

since an element g belongs to either side iff g £ Á ;

(b)

but freely adds joins. omitted diagram environment This means that, for any monotone function f:X® Q to a poset which has joins of all subsets, there is a unique join-preserving function p:shv(X)® Q such that p(X ¯ x) = f(x). []

EXAMPLE 3.2.8 In the poset X on the left, u is the join of a and b.

omitted diagram environment

In shv(X), on the right, {a,b} is a new ``formal'' join of this pair. []

Theorem 3.9.7 shows how to add new joins, but keep specified old ones.

Diagrams   It is often more convenient to define meets and joins with respect to arbitrary functions Á® X instead of just subsets Á Ì X.

DEFINITION 3.2.9 A diagram in a poset X is a function to X from a set Á, or a monotone function from a poset or preorder. We call Á the shape of the diagram, and write x_i for the value of the function at i Î Á and x_(-):Á® X for the function as a whole.

Then q Î X is an upper bound for the diagram if "i.x_i £ q, ie q bounds the image, {x_i|i:Á} Ì X. We write Ú_i x_i for the join (least upper bound) of the diagram, and similarly Ù_ix_i for the meet.

The notations xÚy and xÙy are, strictly speaking, examples of a join and a meet of a diagram of shape 2 = {·  ·} rather than of a subset. We shall study certain non-discrete diagrams in the next section.

Any diagram has the same meets and joins as its image. Indeed it has the same joins as the down-closure of its image, and more generally we can say exactly when a comparison between diagrams induces the same joins. This result will be used in Corollary 3.5.13.

PROPOSITION 3.2.10 Let U:J® Á be monotone. Then the following are equivalent:

(a)

U is cofinal: "i.$j.i £ U(j);

(b)

for every preorder X, diagram x_(-):Á® X and element q Î X, q is an upper bound for {x_i|i:Á} iff it is an upper bound for {x_U(j)|j:J};

(c)

for all such diagrams the minimal upper bounds coincide;

(d)

for all such diagrams the locally least upper bounds coincide;

(e)

for all such diagrams the least upper bounds coincide.

PROOF: The proof is easy except for (e)Þ (a). For this case we use the representation by lower sets, so let X = shv(Á) and x_i = Á¯ i. Then q is an upper bound of {x_i|i:Á} iff q = Á, and of the subset {x_U(j)|j:J} iff \rightadj_!(J) Ì q, so Á must be the lower closure of \rightadj_!(I). []

Lattices   Now we shall give an algebraic characterisation of finite meets and joins, motivated by the logical connectives Ù and Ú (Section 1.4). Gottfried Leibniz defined order in terms of joins, and Johann Lambert recognised the idempotent law. Ernst Schröder was the first to see that the distributive law was not automatic. These laws, plus associativity, commutativity and the units for lattices, express the structural rules of logic (Definition  1.4.8), as do the reflexivity and transitivity axioms for a preorder. Antisymmetry, on the other hand, is a side-effect of the algebraic formulation of logic in terms of lattices.

PROPOSITION 3.2.11 Let (X, £ ) be a poset with a greatest element (T) and meets of pairs (xÙy). Then the operation Ù:Xx X® X is

associative: xÙ(yÙz) = (xÙy)Ùz, commutative: xÙy = yÙx, idempotent: xÙx = x, and T is a unit: TÙx = x = xÙT.

Moreover x £ y iff xÙy = x. Conversely if (X,T,Ù) satisfies these laws then this condition defines a partial order for which Ù is the binary meet and T the greatest element. []

DEFINITION 3.2.12 Such a structure is called a semilattice; a function which preserves Ù and T is called a semilattice homomorphism, and is therefore monotone. Notice that the algebraic laws do not force the direction of the order relation: Ú and ^ satisfy them as well. When we speak of an algebraic structure as a join- or meet-semilattice we are therefore imposing the direction by convention.

Since finitary meets and joins are characterised by the same laws and each alone can uniquely determine the order, there must be an additional law forcing the two orders to coincide. It suffices to say that x,y £ xÚy, where £ is the relation defined by Ù, or vice versa . Eliminating the inequality, either of these conditions is known as the absorptive law:

xÙ(xÚy) = x    and    xÚ(xÙy) = x.

The nullary cases, yÙ^ = ^ and yÚT = T, follow from these (with x = ^,T) and the unit laws.

PROPOSITION 3.2.13 Let (X, £ ) be a poset with finite meets and joins. Then (X,^,Ú) and (X,T,Ù) are both semilattices, and the absorptive laws hold. Conversely, if (X,^,Ú,T,Ù) obeys both sets of semilattice laws and either of the absorptive laws then the orders agree and the meets and joins are as given. Then X is called a lattice; lattice homomorphisms by definition preserve ^, Ú, T, and Ù. []

The logical connectives obey another law:

DEFINITION 3.2.14 A lattice is distributive if

omitted eqnarray* environment

where LHS £ RHS hold in an arbitrary lattice. In fact one can be derived from the other in the context of the lattice laws, and we have already stated the nullary versions ( xÙ^ = ^ and xÚT = T). Whereas expressions in the theory of lattices may need many nested brackets, the distributive laws give rise to the disjunctive normal form, eg

There are also major applications of lattices to the structure theory of algebra. The lattices of congruences of certain familiar theories, notably groups, rings and vector spaces, obey the modular law (Exercise  3.24), which is weaker than distributivity and was first identified by Richard Dedekind (1900). This gives a sense in which these algebras are made of ``building blocks,'' of which the dimension of a vector space and the Jordan-Hölder theorem for groups are examples.

We shall return to lattices with arbitrary meets and joins in Section  3.6. Semilattices will be used in Theorem  3.9.1 to describe Horn theories (Remark  1.7.2ff). Now we shall turn from finitary meets and joins to those which are in a sense ``purely infinitary.''