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: logarithm as left adjoint

Cole Comfort (Feb 16 2021 at 14:55):

Let $\sf Bool$ be the category with objects being the natural numbers and morphisms $n\to m$ being functions $2^n \to 2^m$ .
There is a forgetful functor $2^{(\_)}:{\sf Bool}\to {\sf FinSet}$, which takes Boolean functions $n\to m$, to their underlying functions.
Conversely there exists a semifunctor, ie a functor not preserving identities $\lceil \log_2 (\_)\rceil:{\sf FinSet}\to {\sf Bool}$, taking functions $n\to m$ to their encodings of Boolean functions $\lceil \log_2 n \rceil \to \lceil \log_2 m \rceil$ padded with $0$ s (where $0 \mapsto 0$).

Fix some $n$, then there is a function $\eta_n:n \rightarrowtail 2^{\lceil \log_2 n \rceil}$. Moreover, for any $m$, and function $f:n\to 2^m$ there exists a Boolean function $g:\lceil \log_2 n \rceil\to m$ such that $n \xrightarrow{\eta_n} 2^{\lceil \log_2 n \rceil} \xrightarrow{2^g} 2^m$ is equal to $f$.

This looks a lot like the triangle for the unit of an adjunction, although the map $g$ is not unique and $\lceil \log_2 (\_)\rceil$ is not a functor.

Does anyone know what is going on here? Is there any way in which $2^{(\_)}$ can be seen to be right adjoint to $\lceil \log_2 (\_)\rceil$?

Joshua Meyers (Feb 21 2021 at 05:07):

How is $\lceil \log_2 (\_)\rceil$ defined? I'm not sure what you mean by "encodings of Boolean functions"

John Baez (Feb 21 2021 at 06:28):

Good question! I didn't get it either, but I wasn't brave enough to ask.

Cole Comfort (Feb 21 2021 at 13:22):

I guess I am working in FinOrd, the skeleton of Finset and we have to fix an order the on the points of all the objects beforehand.
Take any function $f:n \to m$. Then to each point $1\to n$, we can assign a natural number $0 \leq i < n$ corresponding to the position in the order.
So this number can be encoded in binary, as an element of $2^{\lceil \log_2 n \rceil}$ , left-padding with $0$ s when necessary.
Similarly, each $f(i)$ also can be encoded in Binary in same way. So you get a function of type $2^{\lceil \log_2 n \rceil} \to 2^{\lceil \log_2 m \rceil}$, or equivalently a Boolean function $\lceil \log_2 n \rceil \to \lceil \log_2 m \rceil$ sending all the unaccoutned for points just to the string of $0$ s.

Jason Erbele (Feb 21 2021 at 17:27):

I'm not sure I understand what the category $\mathsf{Bool}$ is, so I may as well expose my ignorance, and hopefully help others understand what's going on by way of concrete example.

It sounds like a Homset, say, $\mathrm{Hom}_\mathsf{Bool}(3,5)$ is isomorphic to the set of all functions from 3-digit binary numbers to 5-digit binary numbers. Then your forgetful functor $2^{(-)} : \mathsf{Bool} \rightarrow \mathsf{FinOrd}$ takes this $\mathrm{Hom}_\mathsf{Bool}(3,5)$ to $\mathrm{Hom}_\mathsf{FinOrd}(8,32)$.
If that guess is correct, then I further guess that $\lceil \log_2(-) \rceil$ would "promote" $\mathrm{Hom}_\mathsf{FinOrd}(3,5)$ to $\mathrm{Hom}_\mathsf{FinOrd}(4,8)$, and interpret it as $\mathrm{Hom}_\mathsf{Bool}(2,3)$.

Assuming I am right so far, let's consider the function $\eta_n$ in $\mathsf{FinOrd}$ for some example value of $n$. Let's take $n=6$. Then $\eta_6 : 6 \rightarrowtail 8$. I'm assuming this takes $i_6$ to $i_8$ for each $i$ from 0 to 5. This looks to me like what the "promotion" I just mentioned should act. Am I on target with your setup so far?

Joshua Meyers (Feb 21 2021 at 17:29):

I don't know what this is called, but here's one thing I can contribute. A functor $U:D\to C$ is a right adjoint iff for all $d\in D$, the comma category $d/U$ has an initial object. In your case, for each $n\in \mathsf{FinSet}$, the comma category $n/2^{(-)}$ has a weakly initial object. So maybe this could be called some sort of "weak adjunction"?

Joshua Meyers (Feb 21 2021 at 17:32):

@Jason Erbele all that you've wrote is concordant with my understanding. If Cole says it's not right, then I'm also mistaken.

John Baez (Feb 21 2021 at 17:38):

Thanks for explaining that stuff, @Cole Comfort.

Joshua Meyers (Feb 21 2021 at 17:38):

My understanding is that $2^{(-)}$ is a full and faithful functor, basically embedding $\mathsf{Bool}$ as a full subcategory of $\mathsf{FinSet}$. $\mathsf{Bool}$ is not what I normally think of as Bool, as the morphisms don't have to respect the Boolean algebra structure of objects, they are just any functions whatsoever. One way I am thinking of this is that a morphism is anything you can do with logic gates. Although this category doesn't adhere to the standard aesthetic "morphisms should preserve structure", I still care about it because it is how computers store natural numbers and maps between them. This adjunction seems to have relevance in that same context --- going back and forth between a computer representation of natural numbers and maps between them, and the "concepts themselves".

John Baez (Feb 21 2021 at 17:42):

Yes: both the names $\mathsf{Bool}$ and $\mathsf{FinOrd}$ as used above confuse the heck out of me. I'd use $\mathsf{Bool}$ either to mean the category of boolean algebras or the category of booleans, the two-element poset with $0 \le 1$. I'd use $\mathsf{FinOrd}$ to mean the category of finite ordinals and order-preserving maps... well, actually I'd use $\Delta_+$ and call it the augmented simplex category, but Wikipedia actually suggests calling it $\mathsf{FinOrd}$.

Cole Comfort (Feb 21 2021 at 17:43):

Yeah I suppose I could have chosen better names to avoid confusion.

John Baez (Feb 21 2021 at 17:43):

But complaining about notation is the past-time of the category theorist... and right now I'm just lying in bed drinking in coffee, waking up and complaining about notation.

Cole Comfort (Feb 21 2021 at 17:46):

Also, I admit this seems very contrived, but it came up and I need to use it

Joshua Meyers (Feb 21 2021 at 22:47):

Here's another example of weird "semi-adjunction"

John Baez (Feb 21 2021 at 23:04):

What's a "semi-adjunction", again?

I occasionally people if they've thought about things like adjunctions where instead of a natural isomorphism of homsets hom(Lx,y) $\cong$ hom(x,Ry) there's just a natural transformation. But that may be some other kind of "semi-adjunction".

Joshua Meyers (Feb 21 2021 at 23:06):

It doesn't have any existing definition that I know of, that's why it's in quotes. I just mean something that's kind of like an adjunction but not quite

Joshua Meyers (Feb 21 2021 at 23:07):

Oh, that's the kind I'm thinking of! Where the natural transformation is not iso

John Baez (Feb 21 2021 at 23:09):

Oh, cool! There should be two fundamentally different kinds, depending on which way the natural transformation goes: from left to right, or from right to left.

John Baez (Feb 21 2021 at 23:09):

Which kind do you have? (There should be different intuitions for the different kinds, but I don't have any intuition for either.)

Cole Comfort (Feb 21 2021 at 23:11):

Well in this case it is none of the above because $\lceil \log_2 (\_)\rceil$ preserves composition, but not identities, so it is not a functor.

Joshua Meyers (Feb 21 2021 at 23:14):

Sorry I'm not being clear. I'm saying that this topic and the one I linked to are both examples of things that are similar to adjunctions but are not adjunctions. The one I linked to is where the natural transformation is not iso. But what makes the construction in this topic not an adjunction is something else: that the corresponding universal property is only weak, as elaborated here

Cole Comfort (Feb 21 2021 at 23:25):

I guess that this really isn't truly a comma category either, because the lack of being a functor. So it is even worse!

Nathanael Arkor (Feb 21 2021 at 23:37):

Joshua Meyers said:

It doesn't have any existing definition that I know of, that's why it's in quotes. I just mean something that's kind of like an adjunction but not quite

This is known as a weak adjunction. See for instance Kainen's Weak adjoint functors or, more recently, Lack–Rosický's Enriched weakness. The concept appears to be missing an nLab page.

Nathanael Arkor (Feb 21 2021 at 23:37):

Instead of asking for a natural isomorphism of hom-sets, one asks for a natural surjection.

Cole Comfort (Feb 21 2021 at 23:41):

I think this is actually a "weak semiadjunction" if that even is a meaningful thing to say

Nathanael Arkor (Feb 21 2021 at 23:42):

It certainly is, though I'm not sure anyone has formally considered them before.

Nathanael Arkor (Feb 21 2021 at 23:43):

(I didn't spot the comments above about not preserving identities.)

Cole Comfort (Feb 21 2021 at 23:43):

I mean, maybe the triangle equations are no longer equivalent to the hom set definition

Cole Comfort (Feb 21 2021 at 23:44):

And who is to say which is the right definition

Nathanael Arkor (Feb 21 2021 at 23:44):

The right definition is the one that fits your examples ;)