Tag Archive

You are currently browsing the tag archive for the ‘lattices’ tag.

Lattices and Duality

April 4, 2008 in Posets and Lattices, Propositional Calculus | Tags: inf-lattices, joins, lattices, principle of duality, sup-lattices | by Todd Trimble | 27 comments

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.

Toward Stone Duality: Posets and Meets

April 2, 2008 in Exposition, Posets and Lattices | Tags: lattices, meets, posets, stone duality, yoneda principle | by Todd Trimble | 22 comments

My name is Todd Trimble. As regular readers of this blog may have noticed by now, I’ve recently been actively commenting on some of the themes introduced by our host Vishal, and he’s now asked whether I’d like to write some posts of my own. Thank you Vishal for the invitation!

As made clear in some of my comments, my own perspective on a lot of mathematics is greatly informed and influenced by category theory — but that’s not what I’m setting out to talk about here, not yet anyway. For reasons not altogether clear to me, the mere mention of category theory often scares people, or elicits other emotional reactions (sneers, chortles, challenges along the lines “what is this stuff good for, anyway?” — I’ve seen it all).

Anyway, I’d like to try something a little different this time — instead of blathering about categories, I’ll use some of Vishal’s past posts as a springboard to jump into other mathematics which I find interesting, and I won’t need to talk about categories at all unless a strong organic need is felt for it (or if it’s brought back “by popular demand”). But, the spirit if not the letter of categorical thinking will still strongly inform my exposition — those readers who already know categories will often be able to read between the lines and see what I’m up to. Those who do not will still be exposed to what I believe are powerful categorical ways of thinking.

I’d like to start off talking about a very pretty area of mathematics which ties together various topics in algebra, topology, logic, geometry… I’m talking about mathematics in the neighborhood of so-called “Stone duality” (after the great Marshall Stone). I’m hoping to pitch this as though I were teaching an undergraduate course, at roughly a junior or senior level in a typical American university. [Full disclosure: I’m no longer a professional academic, although I often play one on the Internet 🙂 ] At times I will allude to topics which presuppose some outside knowledge, but hey,that’s okay. No one’s being graded here (thank goodness!).

First, I need to discuss some preliminaries which will eventually lead up to the concept of Boolean algebra — the algebra which underlies propositional logic.

A partial order on a set $X$ is a binary relation (a subset $R \subseteq X \times X$ ), where we write $x \le y$ if $(x, y) \in R$ , satisfying the following conditions:

(Reflexivity) $x \le x$ for every $x \in X$ ;
(Transitivity) For all $x, y, z \in X$ , ( $x \le y$ and $y \le z$ ) implies $x \le z$ .
(Antisymmetry) For all $x, y \in X$ , ( $x \le y$ and $y \le x$ ) implies $x = y$ .

A partially ordered set (poset for short) is a set equipped with a partial order. Posets occur all over mathematics, and many are likely already familiar to you. Here are just a few examples:

The set of natural numbers $0, 1, 2,\ldots$ ordered by divisibility ( $x \le y$ if $x$ divides $y$ ).
The set of subsets of a set $X$ (where $\le$ is the relation of inclusion $A \subseteq B$ of one subset in another).
The set of subgroups of a group $G$ (where again $\le$ is the inclusion relation between subgroups).
The set of ideals in a ring $R$ (ordered by inclusion).

The last three examples clearly follow a similar pattern, and in fact, there is a sense in which every poset P can be construed in just this way: as a set of certain types of subset ordered by inclusion. This is proved in a way very reminiscent of the Cayley lemma (that every group can be represented as a group of permutations of a set). You can think of such results as saying “no matter how abstractly a group [or poset] may be presented, it can always be represented in a concrete way, in terms of permutations [or subsets]”.

To make this precise, we need one more notion, parallel to the notion of group homomorphism. If $X$ and $Y$ are posets, a poset map from $X$ to $Y$ is a function $f: X \to Y$ which preserves the partial order (that is, if $x \le y$ in $X$ , then $f(x) \le f(y)$ in $Y$ ). Here then is our representation result:

Lemma (Dedekind): Any poset $X$ may be faithfully represented in its power set $PX$ , partially ordered by inclusion. That is, there exists a poset map $i: X \to PX$ that is injective (what we mean by “faithful”: the map is one-to-one).

Proof: Define $i: X \to PX$ to be the function which takes $x \in X$ to the subset $\{ a \in X : a \le x \}$ (which we view as an element of the power set). To check this is a poset map, we must show that if $x \le y$ , then $i(x) = \{ a \in X : a \le x \}$ is included in $i(y) = \{ b \in X : b \le y \}$ . This is easy: if $a$ belongs to $i(x)$ , i.e., if $a \le x$ , then from $x \le y$ and the transitivity property, $a \le y$ , hence $a$ belongs to $i(y)$ .

Finally, we must show that $i: X \to PX$ is injective; that is, $i(x) = i(y)$ implies $x = y$ . In other words, we must show that if

$\{ a \in X : a \le x \} = \{ b \in X: b \le y \}$ ,

then $x = y$ . But, by the reflexivity property, we know $x \le x$ ; therefore $x$ belongs to the set displayed on the left, and therefore to the set on the right. Thus $x \le y$ . By similar reasoning, $y \le x$ . Then, by the antisymmetry property, $x = y$ , as desired. $\Box$

The Dedekind lemma turns out to be extremely useful (it and the Cayley lemma are subsumed under an even more useful result called the Yoneda lemma — perhaps more on this later). Before I illustrate its uses, let me rephrase slightly the injectivity property of the Dedekind embedding $i: X \to PX$ : it says,

If (for all $a$ in $X, a \le x$ iff $a \le y$ ), then $x = y$ .

This principle will be used over and over again, so I want to give it a name: I’ll call it the Yoneda principle.

Here is a typical use. Given elements $x, y$ in a poset $X$ , we say that an element $m$ is a meet of $x$ and $y$ if for all $a \in X$ ,

$a \le m$ if and only if ( $a \le x$ and $a \le y$ ).

Fact: there is at most one meet of $x$ and $y$ . That is, if $m$ and $n$ are both meets of $x$ and $y$ , then $m = n$ .

Proof: For all $a \in X, a \le m$ if and only if ( $a \le x$ and $a \le y$ ) if and only if $a \le n$ . Therefore, $m = n$ by the Yoneda principle. $\Box$

Therefore, we can refer to the meet of two elements $x$ and $y$ (if it exists); it is usually denoted $x \wedge y$ . Because $x \wedge y \le x \wedge y$ , we have $x \wedge y \le x$ and $x \wedge y \le y$ .

Example: In a concrete poset, like the poset of all subsets of a set or subgroups of a group, the meet of two elements is their intersection.

Example: Consider the natural numbers ordered by divisibility. The meet $m = x \wedge y$ satisfies $m \leq x$ and $m \leq y$ (i.e., $m$ divides both $x$ and $y$ ). At the same time, the meet property says that any number which divides both $x$ and $y$ must also divide $m$ . It follows that the meet in this poset is the gcd of $x$ and $y$ .

Here are some more results which can be proved with the help of the Yoneda principle. I’ll just work through one of them, and leave the others as exercises.

$x \wedge x = x$ (idempotence of meet)
$x \wedge y = y \wedge x$ (commutativity of meet)
$(x \wedge y) \wedge z = x \wedge (y \wedge z)$ (associativity of meet)

To prove 3., we can use the Yoneda principle: for all $a$ in the poset, we have

$a \le ( x \wedge y) \wedge z$

iff $( a \le x \wedge y$ and $a \le z )$

iff $( a \le x$ and $a \le y$ and $a \le z )$

iff $( a \le x$ and $a \le y \wedge z )$

iff $a \le x \wedge ( y \wedge z )$ .

Hence, $( x \wedge y) \wedge z = x \wedge ( y \wedge z )$ by Yoneda.

In fact, we can unambiguously refer to the meet of any finite number of elements $x_1, x_2, \ldots, x_n$ by the evident property:

$a \le x_1 \wedge x_2 \wedge \ldots \wedge x_n$ iff $( a \le x_1$ and $a \le x_2$ and $\ldots a \le x_n )$

— this uniquely defines the meet on the left, by Yoneda, and the order in which the $x_i$ appear makes no difference.

But wait — what if the number $n$ of elements is zero? That is, what is the empty meet? Well, the condition “ $a \le x_1$ and $\ldots a \le x_n$ ” becomes vacuous (there is no $a$ for which the condition is not satisfied), so whatever the empty meet is, call it $\top$ , we must have $a \le \top$ for all $a$ . So $\top$ is just the top element of the poset (if one exists). Another name for the top element is “the terminal element”, and another notation for it is ‘ $1$ ‘.

Definition: A meet semi-lattice is a poset which has all finite meets, including the empty one.

Exercises:

Prove that in a meet-semilattice, $x \wedge \top = x$ for all $x$ .
Is there a top element for the natural numbers ordered by divisibility?

	Strong equidistribut… on Platonic Solids and Euler…
	m.s.mohamed ansari on The 54th Carnival of Math…
	Convictions ·… on Continued fraction for e
	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…

M	T	W	T	F	S	S
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Tag Archive

Lattices and Duality

Toward Stone Duality: Posets and Meets

Our other blog

Visitors to this blog

Blog Stats

Wikio Ranking

Current Online Readers

Recent Comments

Top Posts

Archives

Categories

Blogroll

chess

Computers and Technology

Elementary Math Problem Solving

Fun, Humor

Higher Mathematics

Math Education

Non-technical

Opinions

People in Computer Science

People in mathematics

Philosophy & Logic

Physics

Politics, News

Sciences

Useful general links

Useful Math Links

Tag Cloud

Admin/Users Login

Pages