#### Howdy, Stranger!

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

Options

# Exercises and Puzzles 5 - Chapter 1

edited May 2018

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.

• Options
1.
edited April 2018

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?

Birkhoff's Representation Theorem. Every finite distributive lattice is isomorphic to the poset of upper sets $$\mathcal{U}(A)$$ for some finite poset $$A$$.

Comment Source: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\$$. 
• Options
2.
edited April 2018

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?

Comment Source: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?
• Options
3.

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.

Comment Source: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.
• Options
4.
edited April 2018

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:

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.

Comment Source: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. 
• Options
5.
edited April 2018

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) .

Comment Source: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) . 
• Options
6.
edited April 2018

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}$$ 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):

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$$
Comment Source:> **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\$$