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:

  1. (Reflexivity) x \le x for every x \in X;
  2. (Transitivity) For all x, y, z \in X, (x \le y and y \le z) implies x \le z.
  3. (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.

  1. x \wedge x = x (idempotence of meet)
  2. x \wedge y = y \wedge x (commutativity of meet)
  3. (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?