Today I'll prove the first really profound result in this course: the Adjoint Functor Theorem for Posets. It establishes a deep link between left adjoints and joins, and between right adjoints and meets. This is the climax of Chapter 1: if you survive this lecture, the final one will be a downhill slide!

Last time I showed that left adjoints preserve joins and right adjoints preserve meets - but I only considered "binary" meets and joins: that is, the meets and join of a _pair_ of elements. We can do much better.

Remember, given any subset \$$S \$$ of a poset \$$A \$$, we say the **join** of \$$S \$$ is the least upper bound of \$$S \$$, if it exists. We denote this join by \$$\bigvee S \$$, but don't be fooled by the notation into thinking it always exists. Similarly, the **meet** or greatest lower bound of \$$S \subseteq A \$$ is denoted by \$$\bigwedge S \$$ - if it exists.

Now for two theorems. I suggest that you read the statements of both these theorems and ponder them a bit before reading the proofs. The statements are ultimately more important than the proofs, so don't be demoralized if you find the proofs tricky!

**Theorem.** If a monotone function \$$f: A \to B \$$ is a left adjoint, it preserves joins whenever they exist. That is, whenever a set \$$S \subseteq A \$$ has a join we have

$f (\bigvee S ) = \bigvee \\{ f(a) : \; a \in S\\} .$

Similarly, if a monotone function between posets \$$g : B \to A \$$ is a right adjoint, it preserves meets whenever they exist. That is, whenever a set \$$S \subseteq B \$$ has a meet we have

$g(\bigwedge S) = \bigwedge \\{ g(b) : \; b \in S \\}.$

**Proof.** We'll just prove the first half, since the second works the same way. We'll assume \$$f: A \to B \$$ is a left adjoint, meaning that it _has_ a right adjoint \$$g: B \to A \$$, and we'll show that \$$f\$$ preserves joins whenever they exist. This is very similar to the proof in Lecture 15, but I'll run through the argument again because it's so important. I'll go a bit faster this time!

Suppose \$$S \subseteq A\$$ has a join \$$j = \bigvee S\$$. This implies that \$$a \le j\$$ for all \$$a \in S \$$, so \$$f(a) \le f(j) \$$, so \$$f(j) \$$ is an upper bound of \$$\\{ f(a) : \; a \in S\\} \$$. We just need to show it's the _least_ upper bound of this set. So, suppose \$$b \in B \$$ is any other upper bound of this set. This means that

$f(a) \le b$

for all \$$a \in S \$$, but thanks to the magic of adjoints this gives

$a \le g(b)$

for all \$$a \in S \$$ so \$$g(b) \$$ is an upper bound of \$$S\$$. Since \$$j \$$ is the _least_ upper bound we conclude

$j \le g(b) ,$

but thanks to the magic of adjoints this gives

$f(j) \le b$

so \$$f(j) \$$ is indeed the _least_ upper bound of \$$\\{ f(a) : \; a \in S\\} \$$. \$$\qquad \blacksquare \$$

Okay, that was fun. But now comes the really exciting part: a kind of converse is true too! It's easiest to state when we have lots of joins or meets available. We say a poset **has all joins** if every subset has a join, and similarly for meets:

**Adjoint Functor Theorem for Posets.** Suppose \$$A\$$ is a poset that has all joins and \$$B \$$ is any poset. Then a monotone map \$$f : A \to B \$$ is a left adjoint if and only if it preserves all joins.

Similarly, suppose \$$B\$$ is a poset that has all meets and \$$A \$$ is any poset. Then a monotone map \$$g : B \to A \$$ is a right adjoint if and only if it preserves all meets.

**Proof.** Again we'll prove only the first half. So, we'll assume \$$A\$$ is a poset that has all joins, \$$B \$$ is any poset, and \$$f : A \to B \$$ is a monotone map.

The previous theorem assures us that if \$$f \$$ is a left adjoint it preserves all joins, so we only need to prove the converse.

Suppose that \$$f\$$ preserves all joins. To show it's a left adjoint, we construct its right adjoint \$$g : B \to A \$$ using the formula given in [Lecture 6](https://forum.azimuthproject.org/discussion/1901/lecture-6-chapter-1-computing-adjoints/p1):

$g(b) = \bigvee \\{a \in A : \; f(a) \le b \\} .$

Since \$$A\$$ has all joins, \$$g(b)\$$ is well-defined. To see that \$$g\$$ is a monotone, note that if \$$b \le b' \$$ then

$\\{a \in A : \; f(a) \le b \\} \subseteq \\{a \in A : \; f(a) \le b' \\}$

so

$g(b) = \bigvee \\{a \in A : \; f(a) \le b \\} \le \bigvee \\{a \in A : \; f(a) \le b' \\} = g(b') .$

See why?

Next we show that \$$f\$$ is the left adjoint of \$$g\$$:

$f(a_0) \le b_0 \textrm{ if and only if } a_0 \le g(b_0)$

for all \$$a_0 \in A, b_0 \in B \$$.

To show this, first suppose \$$f(a_0) \le b_0 \$$. Then \$$a_0 \$$ is an element of \$$\\{ a \in A : f(a) \le b_0 \\} \$$, so

$a_0 \le \bigvee \\{ a \in A : f(a) \le b_0 \\} = g(b_0)$

by the definition of \$$g \$$. So, we have \$$a_0 \le g(b_0) \$$ as desired.

Conversely, suppose \$$a_0 \le g(b_0) \$$. Then \$$f(a_0)) \le f(g(b_0)) \$$, so if we can show \$$f(g(b_0)) \le b_0 \$$ then we'll have \$$f(a_0) \le b_0 \$$. For this, note:

$f(g(b_0)) = f( \bigvee \\{a \in A : \; f(a) \le b_0 \\}) = \bigvee \\{f(a) \in B : \; f(a) \le b_0 \\}) \le b_0$

where in the middle step we finally use the fact that \$$f\$$ preserves joins. So, we have \$$a_0 \le g(b_0) \$$ as desired - and we're done! \$$\qquad \blacksquare \$$

So the connection between joins and left adjoints, or meets and right adjoints, is very strong. Next time, in my last lecture on Chapter 1, I'll explain this a bit more.

**[To read other lectures go here.](http://www.azimuthproject.org/azimuth/show/Applied+Category+Theory#Course)**