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 is a binary relation (a subset ), where we write if , satisfying the following conditions:
- (Reflexivity) for every ;
- (Transitivity) For all , ( and ) implies .
- (Antisymmetry) For all , ( and ) implies .
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 ordered by divisibility ( if divides ).
- The set of subsets of a set (where is the relation of inclusion of one subset in another).
- The set of subgroups of a group (where again is the inclusion relation between subgroups).
- The set of ideals in a ring (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 and are posets, a poset map from to is a function which preserves the partial order (that is, if in , then in ). Here then is our representation result:
Lemma (Dedekind): Any poset may be faithfully represented in its power set , partially ordered by inclusion. That is, there exists a poset map that is injective (what we mean by “faithful”: the map is one-to-one).
Proof: Define to be the function which takes to the subset (which we view as an element of the power set). To check this is a poset map, we must show that if , then is included in . This is easy: if belongs to , i.e., if , then from and the transitivity property, , hence belongs to .
Finally, we must show that is injective; that is, implies . In other words, we must show that if
then . But, by the reflexivity property, we know ; therefore belongs to the set displayed on the left, and therefore to the set on the right. Thus . By similar reasoning, . Then, by the antisymmetry property, , as desired.
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 : it says,
If (for all in iff ), then .
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 in a poset , we say that an element is a meet of and if for all ,
if and only if ( and ).
Fact: there is at most one meet of and . That is, if and are both meets of and , then .
Proof: For all if and only if ( and ) if and only if . Therefore, by the Yoneda principle.
Therefore, we can refer to the meet of two elements and (if it exists); it is usually denoted . Because , we have and .
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 satisfies and (i.e., divides both and ). At the same time, the meet property says that any number which divides both and must also divide . It follows that the meet in this poset is the gcd of and .
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.
- (idempotence of meet)
- (commutativity of meet)
- (associativity of meet)
To prove 3., we can use the Yoneda principle: for all in the poset, we have
iff and and
Hence, by Yoneda.
In fact, we can unambiguously refer to the meet of any finite number of elements by the evident property:
iff and and
— this uniquely defines the meet on the left, by Yoneda, and the order in which the appear makes no difference.
But wait — what if the number of elements is zero? That is, what is the empty meet? Well, the condition “ and ” becomes vacuous (there is no for which the condition is not satisfied), so whatever the empty meet is, call it , we must have for all . So 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 ‘‘.
Definition: A meet semi-lattice is a poset which has all finite meets, including the empty one.
- Prove that in a meet-semilattice, for all .
- Is there a top element for the natural numbers ordered by divisibility?