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

- All Categories 2.3K
- Chat 500
- Study Groups 19
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 68
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 713

Options

Joins and meets are much more deeply connected to left and right adjoints than I've admitted so far. To dig a little deeper, let's prove this result I mentioned last time:

**Theorem.** Left adjoints preserve joins and right adjoints preserve meets. Suppose \(f : A \to B\) and \(g : B \to A\) are monotone functions between posets. Suppose that \(f\) is the left adjoint of \(g\), or equivalently, \(g\) is the right adjoint of \(f\). If the join of \(a,a' \in A\) exists then so does the join of \(f(a), f(a') \in B\), and

$$ f(a \vee a') = f(a) \vee f(a'). $$ If the meet of \(b,b' \in B\) exists then so does the meet of \(g(b), g(b') \in A\), and

$$ g(b \wedge b') = g(b) \wedge g(b'). $$
**Proof.** First, suppose \( f : A \to B\) is *any* monotone function and the join \(a \vee a'\) exists. By definition, \( a \vee a' \) is the least upper bound of \( a \) and \( a' \), so

$$ a \le a \vee a' \textrm{ and } a' \le a \vee a' . $$ Since \( f \) is monotone this gives

$$ f(a) \le f(a \vee a') \textrm{ and } f(a') \le f(a \vee a') .$$ This says that \( f(a \vee a') \) is an upper bound of \( f(a) \) and \( f(a') \).

To finish the job, we need to bring in our assumption that \( f \) is the left adjoint of \( g \). Let's show that \( f(a \vee a') \) is the *least* upper bound of \( f(a) \) and \( f(a') \). So, suppose \( b \) is any other upper bound of these guys:

$$ f(a) \le b \textrm{ and } f(a') \le b. $$ Since \( f \) is the left adjoint of \( g \), this means

$$ a \le g(b) \textrm{ and } a' \le g(b). $$
This says that \( g(b) \) is an upper bound of \( a \) and \( a' \). Since \( a \vee a' \) is the *least* upper bound, we have

$$ a \vee a' \le g(b) . $$ Since \( f \) is the left adjoint of \( g \), this means

$$ f(a \vee a') \le b. $$
So, \( f(a \vee a') \) is indeed the *least* upper bound of \( f(a) \) and \( f(a') \). This implies that \( f(a) \vee f(a') \) actually exists, and that

$$ f(a \vee a') = f(a) \vee f(a'). $$ The argument that right adjoints preserve meets works exactly the same way, with all the inequalities reversed. \( \quad \blacksquare \)

To check that you understand this material, come up with the similar argument for right adjoints when you're on a boring train or airplane trip - without looking at any notes.

It's worth noting a little spinoff of the argument I gave. If \( f : A \to B \) is *any* monotone function between posets,

$$ f(a) \vee f(a') \le f(a \vee a') $$
when the joins here actually exist. Assuming that \( f \) is a left adjoint gives us the reverse inequality. Similarly, if \( g : B \to A \) is *any* monotone function between posets,

$$ g(b \wedge b') \le g(b) \wedge g(b') $$ when the meets actually exist. Assuming that \( g \) is a right adjoint gives us the reverse inequality.

Our next step will be to strengthen the theorem we proved today. The idea doesn't just apply to "binary" meets and joins - that is, meets and joins of a pair of elements. It applies to meets and joins of *arbitrary* subsets. And when we state it that way, a kind of converse is true too.

Suppose, for example, we have two posets that have all meets and joins. Then a monotone map between them preserves joins of arbitrary subsets *if and only if* it's a left adjoint! And it preserves meets of arbitrary subsets *if and only if* it's a right adjoint!

This is staggeringly beautiful. It's called the "Adjoint Functor Theorem for Posets". We'll prove it next time.

Why does it have that name? It's a special case of a more general theorem about adjoint functors for categories. You see, all our results about posets can be generalized to categories, since:

- posets are a special case of categories,
- monotone functions between posets are a special case of functors between categories,
- Galois connections between posets are a special case of adjoint functors between categories,
- left adjoint monotone functions are a special case of left adjoint functors,
- right adjoint monotone functions are a special case of right adjoint functors,
- meets are a special case of limits, and
- joins are a special case of colimits.

The terms in blue are some of the most important concepts in category theory. Fong and Spivak's strategy is to help you develop an intuition for these concepts by working with posets before diving into more general categories. The Adjoint Functor Theorem, in particular, is rather tricky to prove. But the version for posets is much easier.

## Comments

There's a missing parenthesis in the last part

`\\ f(a') \\)`

. This is repeated a few lines later.`This says that \\( f(a \vee a') \\) is an upper bound of \\( f(a) \\) and \\ f(a') \\). There's a missing parenthesis in the last part `\\ f(a') \\)`. This is repeated a few lines later.`

Thanks, Jared! Fixed.

`Thanks, Jared! Fixed.`

Are the inequalities reversed in the following statements?

Because \( a \vee a' \ge a \) and \( a \vee a' \ge a' \), therefore \( f(a \vee a') \ge f(a) \) and \( f(a \vee a') \ge f(a') \) .

`Are the inequalities reversed in the following statements? > "It's worth noting a little spinoff of the argument I gave. If \\( f : A \to B \\) is _any_ monotone function between posets, > > $$ f(a \vee a') \le f(a) \vee f(a') $$ > > when the joins here actually exist. Assuming that \\( f \\) is a left adjoint gives us the reverse inequality. > Similarly, if \\( g : B \to A \\) is <i>any</i> monotone function between posets, > > $$ g(b \wedge g') \ge g(b) \wedge g(b') $$ > Because \\( a \vee a' \ge a \\) and \\( a \vee a' \ge a' \\), therefore \\( f(a \vee a') \ge f(a) \\) and \\( f(a \vee a') \ge f(a') \\) .`

Matias - good catch! I'll fix those. Also, \(g(b∧g′)\) should be \(g(b∧b′)\).

`Matias - good catch! I'll fix those. Also, \\(g(b∧g′)\\) should be \\(g(b∧b′)\\).`

Explaining this idea in terms of posets gives a nice, detailed and intuitive view of this classic fact about adjoints. Thanks for doing these lectures so thoroughly.

`Explaining this idea in terms of posets gives a nice, detailed and intuitive view of this classic fact about adjoints. Thanks for doing these lectures so thoroughly.`

Thanks, Christian!

`Thanks, Christian!`

I don't understand the final sentence of the proof: why does \( f(a \vee a') = f(a) \vee f(a') \)?

So, \( f(a \vee a') \) is indeed the

leastupper bound of \( f(a) \) and \( f(a') \). This implies that \( f(a) \vee f(a') \) actually exists, and that$$ f(a \vee a') = f(a) \vee f(a'). $$

`I don't understand the final sentence of the proof: why does \\( f(a \vee a') = f(a) \vee f(a') \\)? So, \\( f(a \vee a') \\) is indeed the _least_ upper bound of \\( f(a) \\) and \\( f(a') \\). This implies that \\( f(a) \vee f(a') \\) actually exists, and that \[ f(a \vee a') = f(a) \vee f(a'). \]`

@Charles Clingen

(You can quote a piece of text by putting > and a space before each line. It seems to work even for TeX.)

I believe that step is using the definition of join, no fancy tricks.

\(f(a) \vee f(a')\)

\(= \textrm{The join is defined as the least upper bound of the two objects.}\)

\(= f(a \vee a') \textrm{, which was shown to be the least upper bound.}\)

`@Charles Clingen (You can quote a piece of text by putting > and a space before each line. It seems to work even for TeX.) > So, \\( f(a \vee a') \\) is indeed the _least_ upper bound of \\( f(a) \\) and \\( f(a') \\). This implies that \\( f(a) \vee f(a') \\) actually exists, and that > \[ f(a \vee a') = f(a) \vee f(a'). \] I believe that step is using the definition of join, no fancy tricks. \\(f(a) \vee f(a')\\) \\(= \textrm{The join is defined as the least upper bound of the two objects.}\\) \\(= f(a \vee a') \textrm{, which was shown to be the least upper bound.}\\)`

@ Pete Morcos

Thanks for explaining the last step of the proof. I knew it had to be simple, but I just didn't see it. I have been told more than once by a very wise person that most proofs rely heavily on the use of definitions and I need to make use of that fact. Ah well, practice makes perfect. I really appreciate your clear explanation.

And thank you for explaining a quick way to quote a piece of text too.

You made my day!

`@ Pete Morcos Thanks for explaining the last step of the proof. I knew it had to be simple, but I just didn't see it. I have been told more than once by a very wise person that most proofs rely heavily on the use of definitions and I need to make use of that fact. Ah well, practice makes perfect. I really appreciate your clear explanation. And thank you for explaining a quick way to quote a piece of text too. You made my day!`