It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.2K
- Applied Category Theory Course 352
- Applied Category Theory Seminar 4
- Exercises 149
- Discussion Groups 49
- How to Use MathJax 15
- Chat 479
- Azimuth Code Project 108
- News and Information 145
- Azimuth Blog 149
- Azimuth Forum 29
- Azimuth Project 189
- - Strategy 108
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 711
- - Latest Changes 701
- - - Action 14
- - - Biodiversity 8
- - - Books 2
- - - Carbon 9
- - - Computational methods 38
- - - Climate 53
- - - Earth science 23
- - - Ecology 43
- - - Energy 29
- - - Experiments 30
- - - Geoengineering 0
- - - Mathematical methods 69
- - - Meta 9
- - - Methodology 16
- - - Natural resources 7
- - - Oceans 4
- - - Organizations 34
- - - People 6
- - - Publishing 4
- - - Reports 3
- - - Software 21
- - - Statistical methods 2
- - - Sustainability 4
- - - Things to do 2
- - - Visualisation 1
- General 39

Options

Yesterday I spent all day with students trying to figure out the mathematics of "coupling" in biochemistry: for example, the way the cell uses ATP hydrolysis to power other processes. So, sorry - no exercises!

But today I'm up early. Let's get going!

This exercise concerns the concept of an **upper set** of a preorder \(A\): a subset \(U \subseteq A\) such that if \(u\) is in \(U\), so is anything bigger:

$$ \textrm{for all } u, a \in A, \textrm{ if } u \in U \textrm{ and } u \le a \textrm{ then } a \in U .$$ Here's an upper set in the power set \( P(\{1,2,3,4\}) \):

Let \(\mathcal{U}(A)\) be the collection of upper sets of the preorder \(A\). \(\mathcal{U}(A)\) is a poset, ordered by inclusion! That is, given two upper sets \(U , V \subseteq A \) we say \(U \le V\) if \(U \subseteq V \).

The puzzle concerns \(\mathcal{U}(A)\) in a very special case. But \(\mathcal{U}(A)\) always has a lot of nice properties. For example, for any preorder \(A\), \(\mathcal{U}(A)\) is a **complete lattice**: a poset where every subset of has a least upper bound (that is, join) and a greatest upper bound (that is, meet). It's also a **distributive lattice**: joins distribute over meets, and vice versa! Complete distributive lattices are among the best of posets, and a lot of work has been put into understanding them.

This exercise involves another important concept: the "product" of preorders:

Check it out!

Also try the following puzzles, if you haven't already. You can see answers in the comments on Lecture 4 and Lecture 5. Some of us discussed these in great detail: they're good for building your intuition of adjoints.

**Puzzle 11.** Show that if the monotone map \(f: A \to B\) has an inverse \(g : B \to A \) that is also a monotone map, then \(g\) is *both a right adjoint and a left adjoint* of \(f\).

**Puzzle 12.** Find a right adjoint for the function \(f : \mathbb{N} \to \mathbb{N}\) with \(f(a) = 2a \), that is, a function \(g : \mathbb{N} \to \mathbb{N}\) with

$$ f(a) \le b \textrm{ if and only if } a \le g(b) $$ for all \(a,b \in \mathbb{N}\). How many right adjoints can you find?

**Puzzle 13.** Find a left adjoint for \(f\): that is, a function \(g : \mathbb{N} \to \mathbb{N}\) with

$$ g(a) \le b \textrm{ if and only if } a \le f(b) $$ for all \(m,n \in \mathbb{N}\). How many left adjoints can you find?

**Puzzle 14.** Find the function \(g : \mathbb{N} \to \mathbb{N}\) such that \(g(b) \) is the largest possible natural number \(a\) with \(2a \le b\).

**Puzzle 15.** Find the function \(g : \mathbb{N} \to \mathbb{N}\) such that \(g(b)\) is the smallest possible natural number \(a\) with \(b \le 2a\).

**Puzzle 16.** What's going on here? What's the pattern you see, and why is it working this way?

To see *all* the exercises in Chapter 1, go here.

## Comments

Category theorists define a

latticeto be a poset where every finite subset has a meet and a join. (Equivalently, every pair of elements has a meet and a join, and also the poset has a top element and a bottom element.)A lattice is

distributiveif meets distribute over joins and vice versa.Here's a nice distributive lattice. What is it?

Birkhoff's Representation Theorem.Every finite distributive lattice is isomorphic to the poset of upper sets \(\mathcal{U}(A)\) for some finite poset \(A\).`Category theorists define a **lattice** to be a poset where every finite subset has a meet and a join. (Equivalently, every pair of elements has a meet and a join, and also the poset has a top element and a bottom element.) A lattice is **distributive** if meets distribute over joins and vice versa. Here's a nice distributive lattice. What is it? <center><img src = "https://upload.wikimedia.org/wikipedia/commons/thumb/7/7c/Birkhoff120.svg/500px-Birkhoff120.svg.png"></center> **[Birkhoff's Representation Theorem](https://en.wikipedia.org/wiki/Birkhoff%27s_representation_theorem#The_partial_order_of_join-irreducibles).** Every finite distributive lattice is isomorphic to the poset of upper sets \\(\mathcal{U}(A)\\) for some finite poset \\(A\\).`

That Wikipedia page seems to suggest that the lattice of upper sets for

anylattice is distributive, even if the original lattice isn't; and if the original lattice is distributive, then the two are isomorphic. Playing around with a simple non-distributive lattice with 4 incomparable elements plus a top and bottom, its lattice of upper sets is the isomorphic to the power set of a set of 4 nodes. It doesn't look like it embeds the original lattice, so I don't know if there's any kind of monotonicity argument we can make about the original lattice and its lattice of upper sets, but itfeelslike a closure operator of some kind. Is this a spurious observation, or is there something here?`That Wikipedia page seems to suggest that the lattice of upper sets for _any_ lattice is distributive, even if the original lattice isn't; and if the original lattice is distributive, then the two are isomorphic. Playing around with a simple non-distributive lattice with 4 incomparable elements plus a top and bottom, its lattice of upper sets is the isomorphic to the power set of a set of 4 nodes. It doesn't look like it embeds the original lattice, so I don't know if there's any kind of monotonicity argument we can make about the original lattice and its lattice of upper sets, but it _feels_ like a closure operator of some kind. Is this a spurious observation, or is there something here?`

The meet of a bunch of upper sets is just their intersection, and the join of a bunch of upper sets is just their union.

So the lattice of upper sets is a

sublatticeof the power set: meets and joins in \(\mathcal{U}A\) are the same as meets and joins in \(\mathcal{P}A\)The power set lattice \(\mathcal{P}A\) is always distributive, regardless of what \(A\) is.

Therefore the upper set lattice \(\mathcal{U}A\) is always distributive, regardless of what \(A\) is.

`The meet of a bunch of upper sets is just their intersection, and the join of a bunch of upper sets is just their union. So the lattice of upper sets is a *sublattice* of the power set: meets and joins in \\(\mathcal{U}A\\) are the same as meets and joins in \\(\mathcal{P}A\\) The power set lattice \\(\mathcal{P}A\\) is always distributive, regardless of what \\(A\\) is. Therefore the upper set lattice \\(\mathcal{U}A\\) is always distributive, regardless of what \\(A\\) is.`

Jonathan wrote:

Yes, and I believe a stronger result is true: the upper sets of any preorder form a distributive lattice. To prove this, it would suffice to check that the join of two upper sets is their union, while their meet is their intersection. Since union distributes over intersection, and vice versa, that would do that job.

That's interesting; I'll need to think about that.

Your feeling that there's a closure operator lurking here may be on the right track: I think there's a

monadlurking here. But I think the best way to see this monad is to see the adjunction it comes from:I think a modern statement of Birkhoff's representation theorem says this:

Theorem.Let \(\text{FinPoset}\) be the category of finite posets and monotone maps. Let \(\text{FinDisLat}\) be the category of finite distributive lattices and monotone maps that preserve all meets and joins. Then there is an equivalence of categories$$ \text{FinPoset} \simeq \text{FinDisLat}^{\text{op}} $$ given as follows. For any finite poset \(P\), let

$$ F(P) = \mathrm{hom}_{\text{FinPoset}}(P,\mathbb{B}) $$ be the poset of monotone maps from \(P\) to \(\mathbb{B}\): this is isomorphic to the distributive lattice of all lower sets of \(P\). Conversely, for any finite distributive lattice \(L\), let

$$ G(L) = \mathrm{hom}_{\mathrm{FinDisLat}}(L,\mathbb{B}) $$ be the poset of lattice homomorphisms from \(L\) to \(\mathbb{B}\). These constructions extend to contravariant functors from \(\text{FinPoset}\) to \(\mathrm{FinDisLatt}\) and back, which in fact give adjoint functors

$$ F: \mathrm{FinPoset} \to \mathrm{FinDisLat}^{\mathrm{op}} $$ and

$$ G: \mathrm{FinDisLat}^{\mathrm{op}} \to \mathrm{FinPoset} $$ which in fact form an equivalence of categories.

I haven't carefully checked the above result, so please take it with a grain of salt, but most of it is in here:

Beautiful stuff!

By the way, since I'm a category theorist I define a

latticeto be a poset with nullary meets and joins (that is, a top and bottom element) as well as binary meets and joins, and I define a lattice homomorphism to preserve these. Non-category theorists would say a lattice need only have binary meets and joins, and say aboundedlattice also has a top and bottom element. So, the Wikipedia article throws in the word "bounded" in various places where I have not.`Jonathan wrote: > That Wikipedia page seems to suggest that the lattice of upper sets for any lattice is distributive, even if the original lattice isn't... Yes, and I believe a stronger result is true: the upper sets of any preorder form a distributive lattice. To prove this, it would suffice to check that the join of two upper sets is their union, while their meet is their intersection. Since union distributes over intersection, and vice versa, that would do that job. > [...] and if the original lattice is distributive, then the two are isomorphic. That's interesting; I'll need to think about that. Your feeling that there's a closure operator lurking here may be on the right track: I think there's a _monad_ lurking here. But I think the best way to see this monad is to see the adjunction it comes from: I think a modern statement of Birkhoff's representation theorem says this: **Theorem.** Let \\(\text{FinPoset}\\) be the category of finite posets and monotone maps. Let \\(\text{FinDisLat}\\) be the category of finite distributive lattices and monotone maps that preserve all meets and joins. Then there is an equivalence of categories $$ \text{FinPoset} \simeq \text{FinDisLat}^{\text{op}} $$ given as follows. For any finite poset \\(P\\), let $$ F(P) = \mathrm{hom}_{\text{FinPoset}}(P,\mathbb{B}) $$ be the poset of monotone maps from \\(P\\) to \\(\mathbb{B}\\): this is isomorphic to the distributive lattice of all lower sets of \\(P\\). Conversely, for any finite distributive lattice \\(L\\), let $$ G(L) = \mathrm{hom}_{\mathrm{FinDisLat}}(L,\mathbb{B}) $$ be the poset of lattice homomorphisms from \\(L\\) to \\(\mathbb{B}\\). These constructions extend to contravariant functors from \\(\text{FinPoset}\\) to \\(\mathrm{FinDisLatt}\\) and back, which in fact give adjoint functors $$ F: \mathrm{FinPoset} \to \mathrm{FinDisLat}^{\mathrm{op}} $$ and $$ G: \mathrm{FinDisLat}^{\mathrm{op}} \to \mathrm{FinPoset} $$ which in fact form an equivalence of categories. I haven't carefully checked the above result, so please take it with a grain of salt, but most of it is in here: * Wikipedia, [Birkhoff's Representation Theorem: Functoriality](https://en.wikipedia.org/wiki/Birkhoff%27s_representation_theorem#Functoriality). Beautiful stuff! By the way, since I'm a category theorist I define a **lattice** to be a poset with nullary meets and joins (that is, a top and bottom element) as well as binary meets and joins, and I define a lattice homomorphism to preserve these. Non-category theorists would say a lattice need only have binary meets and joins, and say a **bounded** lattice also has a top and bottom element. So, the Wikipedia article throws in the word "bounded" in various places where I have not.`

if i recall quantum logic (birkhoff and von neumann i think developed that) is a nondistributive lattice. you just cut some pieces off the lattice. i had a book by von neumann on that which someone stole to sell. stone-weirestrass theorem is another nice theorem. some of these are almost basic and simple but are basis of alot of advanced math--from taylor's theorem through harmonic analyses (one of my favorite papers is by G S Mackey Bull AMS around 1980 on group theory and physics) .

`if i recall quantum logic (birkhoff and von neumann i think developed that) is a nondistributive lattice. you just cut some pieces off the lattice. i had a book by von neumann on that which someone stole to sell. stone-weirestrass theorem is another nice theorem. some of these are almost basic and simple but are basis of alot of advanced math--from taylor's theorem through harmonic analyses (one of my favorite papers is by G S Mackey Bull AMS around 1980 on group theory and physics) .`

I believe this is the finite case of the more general duality:

$$ \mathbf{Poset} \simeq \mathbf{AlexandrovTop}^{\text{op}}$$ ...where \(\mathbf{AlexandrovTop}\) is the category of topologies with open sets closed under arbitrary intersections, with continuous maps as morphisms.

Puzzle MD1. Show that \(\mathcal{U}A\) is a topology over \(A\). Specifically, show the following axioms hold (taken from Wikipedia):`> **Theorem.** Let \\(\text{FinPoset}\\) be the category of finite posets and monotone maps. Let \\(\text{FinDisLat}\\) be the category of finite distributive lattices and monotone maps that preserve all meets and joins. Then there is an equivalence of categories > > $$ \text{FinPoset} \simeq \text{FinDisLat}^{\text{op}} $$ > > ... > > I haven't carefully checked the above result, so please take it with a grain of salt ... I believe this is the finite case of the more general duality: $$ \mathbf{Poset} \simeq \mathbf{AlexandrovTop}^{\text{op}}$$ ...where [\\(\mathbf{AlexandrovTop}\\)](https://en.wikipedia.org/wiki/Alexandrov_topology) is the category of topologies with open sets closed under arbitrary intersections, with [continuous maps](https://en.wikipedia.org/wiki/Continuous_function#Continuous_functions_between_topological_spaces) as morphisms. **Puzzle MD1**. Show that \\(\mathcal{U}A\\) is a topology over \\(A\\). Specifically, show the following axioms hold (taken from [Wikipedia](https://en.wikipedia.org/wiki/Topological_space#Definition_via_open_sets)): 1. \\(\varnothing \in \mathcal{U}A\\) 2. if \\(X \subseteq \mathcal{U}A\\) then \\(\bigcup X \in \mathcal{U}A\\) 3. if \\(x,y \subseteq \mathcal{U}A\\) then \\(x \cap y \in \mathcal{U}A\\)`