Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Left adjoint to monotone function

Kale Evans (Dec 19 2020 at 18:10):

What's the process by which one can find the left adjoint for a given monotone function?

For example, excercise 1.95 in Dr. Spivak and Dr. Fong's book asks if there exists a left adjoint mapping from the integers to the reals , for the monotone function ceil(x/3).

Apart from trying out a bunch of stuff, I'm having a hard time figuring out a method for systemically finding such a function. Playing around with the inequalities in the definition for left and right adjoints doesn't seem to net anything definitive, and even the proof in the book uses contradiction to prove one doesn't exist by trying out a couple of variables.

I'm assuming there is some proof that makes this easier perhaps, but I'm looking for the intuitive approach. Any ideas? Thanks

Dan Doel (Dec 19 2020 at 18:44):

Proving that something doesn't exist (or generally is false) 'by contradiction' isn't the same as "proof by contradiction". E.G. the intuitionistic definition of $¬A$ is $A → ⊥$, where $⊥$ can only be proved by exhibiting a contradiction. This is kind of a common misconception.

The first strategy I use for other cases is that if $F ⊣ G$, then $F = \mathsf{Ran}_G 1$. Then I try using a formula for Kan extensions, like $\mathsf{Ran}_G F X = \int_A \mathsf{hom}(X, G(A)) ⋔ F(A)$. If you can make sense of those things, then you can read off what the adjoint should be. But I'm not sure how well it works in this situation.

Dan Doel (Dec 19 2020 at 18:48):

If I were to guess meanings for all that, I would say $g(n) = \mathsf{min}\{ x | n \leq \mathsf{ceil}(x/3) \}$

Dan Doel (Dec 19 2020 at 18:50):

So, you use the formula to guess like that, then check if it works as the left adjoint.

Dan Doel (Dec 19 2020 at 18:58):

The obvious problem is that the 'power' $\mathsf{hom}(X, G(A))⋔ F(A)$ doesn't literally make sense here, I think, but my guess was that in conjunction with the end, you could write it as something that overall does make sense (and would be equivalent to some weaker form of Kan extension that does actually make sense).

Matteo Capucci (he/him) (Dec 19 2020 at 19:47):

For monotone functions the adjoint functor theorem has a very easy form: Screenshot-from-2020-12-19-20-46-39.png

Matteo Capucci (he/him) (Dec 19 2020 at 19:51):

There's a good explanation of this on John's blog, in his series trekking through the book you mentioned: https://forum.azimuthproject.org/discussion/2031/lecture-16-chapter-1-the-adjoint-functor-theorem-for-posets

Matteo Capucci (he/him) (Dec 19 2020 at 19:53):

(Moderator mode on :robot: : I see you cross-posted this question in two unrelated topics. To open a new topic there's a button next to 'reply' aptly named 'new topic'. No worries for now! Just telling you for the next time)

Dan Doel (Dec 19 2020 at 20:44):

Hey, my method worked. :smile:

Kale Evans (Dec 20 2020 at 04:13):

Thanks @Matteo Capucci and @Dan Doel .

I'll take a look at John's blog on the topic. Though I was hoping to figure out a method without using a theorem to do so for starters. I will make sure to open a new topic next time, sorry about that.

@Dan Doel I have never worked with Kan extensions before. So I'd have to research that to get an idea of that way of a solution. thank you for bringing it to my attention!

Though, I have to imagine there is a simpler way to find it, given that stuff hasn't been covered in the book at the time this question was posed

Dan Doel (Dec 20 2020 at 04:40):

Well, you can look at other definitions and guess. But what I described is a completely mechanical process, aside from educated guesses about what the various bits mean. In some scenarios what they mean is well known, and you don't really have to guess, just check that the formula works.

Nathaniel Virgo (Dec 20 2020 at 05:41):

Here's a way that I found helpful, for visualising what's going on if not for doing formal proofs. I'll use the adjoint pair from exercise 1.99 as an example.

Start by drawing the function f, the left adjoint, like this:

image.png

What we're going to do is interpret this diagram as a preorder, where we interpret those blue arrows as being part of the preorder, e.g. the element $2\in P$ is above the element $1\in Q$. To do that we have to add a bunch more arrows, to make sure the arrows are closed under composition.

image.png

In other words, we're defining a new preorder that contains $P$ and $Q$ disjointly, and where for $p\in P$ and $q\in Q$ we say $p\le q$ iff $f(p)\le q$. (This new preorder is the collage of a $\mathsf{Bool}$-profunctor - I think that terminology is introduced later in the book.)

Now in this new preorder, the set $\{q\in Q\mid p\le q\}$ is an upper set of the original $Q$. In fact, it's given by ${\uparrow}f(p)$. Because of this, if someone handed us this preorder (along with the information about which elements came from $P$ and which came from $Q$), we could still extract the original monotone map $f$ by defining it as $f(p) = \inf\{q\in Q\mid p\le q\}$. (I guess Fong and Spivak would write that as $\bigwedge\{q\in Q\mid p\le q\}.$)

We could also try to go the other way, and define a function $g(q) = \sup\{ p\in P\mid p\le q \}$. In general, this might not exist, because suprema (i.e. joins) might not exist. But if $f$ has a right adjoint then this procedure will find it. Because of this, you should just be able to look at the diagram above, which we constructed from $f$, and read off the function $g$.

This is basically the preorder version of the fact that for adjoint functors $F\colon\mathcal{C}\to\mathcal{D}$ and $G\colon\mathcal{D}\to\mathcal{C}$ we have a natural isomorphism $\mathcal{C}(F{-},{=})\cong \mathcal{D}({-},G{=}).$

The only slightly annoying thing about this is that the left adjoint is the one that goes from left to right, and the right adjoint goes from right to left. I try to remember it as "left adjoint = lower adjoint," i.e. the one defined by an infimum.

Kale Evans (Dec 20 2020 at 17:28):

@Nathaniel Virgo thank you for your message. I'm looking to understand this diagram first. With regards to the first part and blue arrows, isn't it $1 \in Q$ is above $2 \in P$ given the blue arrow goes from 2 to 1, I.e $2 \leq 1$?

John Baez (Dec 20 2020 at 18:19):

Kale Evans said:

Thanks Matteo Capucci and Dan Doel .

I'll take a look at John's blog on the topic. Though I was hoping to figure out a method without using a theorem to do so for starters.

I hope you'll find my explanation pretty simple. I just phrased the method of finding an adjoint as a theorem because it is, in fact, true that this method always works. It's not too hard to show.

Nathaniel Virgo (Dec 21 2020 at 04:29):

Kale Evans said:

Nathaniel Virgo thank you for your message. I'm looking to understand this diagram first. With regards to the first part and blue arrows, isn't it $1 \in Q$ is above $2 \in P$ given the blue arrow goes from 2 to 1, I.e $2 \leq 1$?

It's maybe a bit confusing that in this example the elements of $P$ and $Q$ are both called "1", "2" and "3". We have to think of them as elements of two different sets, even though they have the same names. When we form the new preorder we have to include the two preorders disjointly, so in this example there will be two "1" elements and two "2" elements, and indeed the "1" that comes from $Q$ is above the "2" that comes from $P$. In the second image, I tagged them with the name of the preorder they came from, so rather than saying "$2 \le 1$" we can say "$2_P \le 1_Q$".

Nathaniel Virgo (Dec 21 2020 at 04:35):

Ah, I see, there was also a typo in my post. I've corrected it. You're right, it should say that $1\in Q$ is above $2\in P$, although that's kind of bad notation - $2_P\le 1_Q$ is better.

Kale Evans (Dec 22 2020 at 04:09):

@John Baez By the way, the linked to blog was explained extremely well, and I certainly found the proofs easy to follow along to. Thank you so much!