You are currently browsing the daily archive for April 4, 2008.

Previously, on “Stone duality”, we introduced the notions of poset and meet-semilattice (formalizing the conjunction operator “and”), as a first step on the way to introducing Boolean algebras. Our larger goal in this series will be to discuss Stone duality, where it is shown how Boolean algebras can be represented “concretely”, in terms of the topology of their so-called Stone spaces — a wonderful meeting ground for algebra, topology, logic, geometry, and even analysis!

In this installment we will look at the notion of lattice and various examples of lattice, and barely scratch the surface — lattice theory is a very deep and multi-faceted theory with many unanswered questions. But the idea is simple enough: lattices formalize the notions of “and” and “or” together. Let’s have a look.

Let (X, \leq) be a poset. If x, y are elements of X, a join of x and y is an element j with the property that for any a \in X,

j \leq a if and only if (x \leq a and y \leq a).

For a first example, consider the poset PX of subsets of X ordered by inclusion. The join in that case is given by taking the union, i.e., we have

S \cup T \subseteq A if and only if (S \subseteq A and T \subseteq A).

Given the close connection between unions of sets and the disjunction “or”, we can therefore say, roughly, that joins are a reasonable mathematical way to formalize the structure of disjunction. We will say a little more on that later when we discuss mathematical logic.

Notice there is a close formal resemblance between how we defined joins and how we defined meets. Recall that a meet of x and y is an element m such that for all a \in X,

a \leq m if and only if (a \leq x and a \leq y).

Curiously, the logical structure in the definitions of meet and join is essentially the same; the only difference is that we switched the inequalities (i.e., replaced all instances of x \leq y by y \leq x). This is an instance of a very important concept. In the theory of posets, the act of modifying a logical formula or theorem by switching all the inequalities but otherwise leaving the logical structure the same is called taking the dual of the formula or theorem. Thus, we would say that the dual of the notion of meet is the notion of join (and vice-versa). This turns out to be a very powerful idea, which in effect will allow us to cut our work in half.

(Just to put in some fine print or boilerplate, let me just say that a formula in the first-order theory of posets is a well-formed expression in first-order logic (involving the usual logical connectives and logical quantifiers and equality over a domain X), which can be built up by taking \leq as a primitive binary predicate on X. A theorem in the theory of posets is a sentence (a closed formula, meaning that all variables are bound by quantifiers) which can be deduced, following standard rules of inference, from the axioms of reflexivity, transitivity, and antisymmetry. We occasionally also consider formulas and theorems in second-order logic (permitting logical quantification over the power set PX), and in higher-order logic. If this legalistic language is scary, don’t worry — just check the appropriate box in the End User Agreement, and reason the way you normally do.)

The critical item to install before we’re off and running is the following meta-principle:

Principle of Duality: If a logical formula F is a theorem in the theory of posets, then so is its dual F’.

Proof: All we need to do is check that the duals of the axioms in the theory of posets are also theorems; then F’ can be proved just by dualizing the entire proof of F. Now the dual of the reflexivity axiom, \forall_{x \in X} x \leq x, is itself! — and of course an axiom is a theorem. The transitivity axiom, \forall_{x, y, z \in X} (x \leq y and y \leq z) implies x \leq z, is also self-dual (when you dualize it, it looks essentially the same except that the variables x and z are switched — and there is a basic convention in logic that two sentences which differ only by renaming the variables are considered syntactically equivalent). Finally, the antisymmetry axiom is also self-dual in this way. Hence we are done. \Box

So, for example, by the principle of duality, we know automatically that the join of two elements is unique when it exists — we just dualize our earlier theorem that the meet is unique when it exists. The join of two elements x and y is denoted x \vee y.

Be careful, when you dualize, that any shorthand you used to abbreviate an expression in the language of posets is also replaced by its dual. For example, the dual of the notation x \wedge y is x \vee y (and vice-versa of course), and so the dual of the associativity law which we proved for meet is (for all x, y, z) (x \vee y) \vee z = x \vee (y \vee z). In fact, we can say

Theorem: The join operation \vee is associative, commutative, and idempotent.

Proof: Just apply the principle of duality to the corresponding theorem for the meet operation.

Just to get used to these ideas, here are some exercises.

  • State the dual of the Yoneda principle (as stated here).
  • Prove the associativity of join from scratch (from the axioms for posets). If you want, you may invoke the dual of the Yoneda principle in your proof. (Note: in the sequel, we will apply the term “Yoneda principle” to cover both it and its dual.)

To continue: we say a poset is a join-semilattice if it has all finite joins (including the empty join, which is the bottom element \bot satisfying \bot \leq a for all a). A lattice is a poset which has all finite meets and finite joins.

Time for some examples.

  • The set of natural numbers 0, 1, 2, 3, … under the divisibility order (x \leq y if x divides y) is a lattice. (What is the join of two elements? What is the bottom element?))
  • The set of natural numbers under the usual order is a join-semilattice (the join of two elements here is their maximum), but not a lattice (because it lacks a top element).
  • The set of subsets of a set X is a lattice. The join of two subsets is their union, and the bottom element is the empty set.
  • The set of subspaces of a vector space V is a lattice. The meet of two subspaces is their ordinary intersection; the join of two subspaces U, W is the vector space which they jointly generate (i.e., the set of vector sums u + w with u \in U, w \in W, which is closed under addition and scalar multiplication).

The join in the last example is not the naive set-theoretic union of course (and similar remarks hold for many other concrete lattices, such as the lattice of all subgroups of a group, and the lattice of ideals of a ring), so it might be worth asking if there is a uniform way of describing joins in cases like these. Certainly the idea of taking some sort of closure of the ordinary union seems relevant (e.g., in the vector space example, close up the union of U and W under the vector space operations), and indeed this can be made precise in many cases of interest.

To explain this, let’s take a fresh look at the definition of join: the defining property was

x \vee y \leq a if and only if (x \leq a and y \leq a).

What this is really saying is that among all the elements a which “contain” both x and y, the element x \vee y is the absolute minimum. This suggests a simple idea: why not just take the “intersection” (i.e., meet) of all such elements a to get that absolute minimum? In effect, construct joins as certain kinds of meets! For example, to construct the join of two subgroups H \subseteq G, J \subseteq G, take the intersection of all subgroups containing both H and J — that intersection is the group-theoretic closure of the union H \cup J.

There’s a slight catch: this may involve taking the meet of infinitely many elements. But there is no difficulty in saying what this means:

Definition: Let X be a poset, and suppose S \subseteq X. The infimum of S, if it exists, is an element m \in X such that for all a \in X, a \leq m if and only if a \leq s for all s \in S.

By the usual Yoneda argument, infima are unique when they exist (you might want to write that argument out to make sure it’s quite clear). We denote the infimum of S by \inf(S).

We say that a poset X is an inf-lattice if there is an infimum for every subset. Similarly, the supremum of S \subseteq X, if it exists, is an element \sup(S) such that for all a \in X, \sup(S) \leq a if and only if s \leq a for all s \in S. A poset is a sup-lattice if there is a supremum for every subset. [I’ll just quickly remark that the notions of inf-lattice and sup-lattice belong to second-order logic, since it involves quantifying over all subsets S \subseteq X (or over all elements of PX).]

Trivially, every inf-lattice is a meet-semilattice, and every sup-lattice is a join-semilattice. More interestingly, we have the

Theorem: Every inf-lattice is a sup-lattice (!). Dually, every sup-lattice is an inf-lattice.

Proof: Suppose X is an inf-lattice, and let S \subseteq X. Let U = \{u \in X: \forall_{s \in S} s \leq u\} be the set of upper bounds of S. I claim that \inf(U) (“least upper bound”) is the supremum of S. Indeed, from \inf(U) \leq \inf(U) and the definition of infimum, we know that \inf(U) \leq a if a \in U, i.e., \inf(U) \leq a if s \leq a for all s \in S. On the other hand, we also know that if s \in S, then s \leq u for every u \in U, and hence s \leq \inf(U) by the defining property of infimum (i.e., \inf(U) really is an upper bound of S). So, if \inf(U) \leq a, we conclude by transitivity that s \leq a for every s \in S. This completes the proof. \Box

Corollary: Every finite meet-semilattice is a lattice.

Even though every inf-lattice is a sup-lattice and conversely (sometimes people just call them “complete lattices”), there are important distinctions to be made when we consider what is the appropriate notion of homomorphism. The notions are straightforward enough: a morphism of meet-semilattices f: X \to Y is a function which takes finite meets in X to finite meets in Y (f(x \wedge x') = f(x) \wedge f(x'), and f(1) = 1 where the 1’s denote top elements). There is a dual notion of morphism of join-semilattices (f(x \vee x') = f(x) \vee f(x') and f(0) = 0 where the 0’s denote bottom elements). A morphism of inf-lattices f: X \to Y is a function such that f(\inf(S)) = \inf(f(S)) for all subsets S \subseteq X, where f(S) denotes the direct image of S under f. And there is a dual notion of morphism of sup-lattices: f(\sup(S)) = \sup(f(S)). Finally, a morphism of lattices is a function which preserves all finite meets and finite joins, and a morphism of complete lattices is one which preserves all infs and sups.

Despite the theorem above , it is not true that a morphism of inf-lattices must be a morphism of sup-lattices. It is not true that a morphism of finite meet-semilattices must be a lattice morphism. Therefore, in contexts where homomorphisms matter (which is just about all the time!), it is important to keep the qualifying prefixes around and keep the distinctions straight.

Exercise: Come up with some examples of morphisms which exhibit these distinctions.

Our other blog

Visitors to this blog

Blog Stats

  • 357,711 hits

Wikio Ranking

Wikio - Top Blogs - Sciences

Current Online Readers

Recent Comments

Convictions ·… on Continued fraction for e
John Favors on Solution to POW-13: Highly…
Wayne J. Mann on Solution to POW-12: A graph co…
erneststephen on The 54th Carnival of Math…
anhtraisg on p^q + q^p is prime
prof dr drd horia or… on My first post
prof drd horia orasa… on My first post
prof dr mircea orasa… on Inequality with log
notedscholar on Self-referential Paradoxes, In…
prof dr mircea orasa… on Inequality with log
prof dr mircea orasa… on Inequality with log
prof dr mircea orasa… on 2010 in review
kenji on Basic category theory, I
prof dr mircea orasa… on Solution to POW-10: Another ha…
prof drd horia orasa… on Continued fraction for e


April 2008