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: theory: category theory

Topic: An Inverse Functor Shortcut

Chad Nester (May 29 2024 at 12:35):

Here's something fun: Suppose $\varphi$ and $\varphi^{-1}$ are mutually inverse mappings of the sort that might be functors (if they preserve composition, identites, and (co)domains). Then if $\varphi$ is a functor so is $\varphi^{-1}$.

For the proof, we have:

• Composition: $\varphi^{-1}(fg) = \varphi^{-1}( \varphi(\varphi^{-1}(f)) \varphi(\varphi^{-1}(g)) ) = \varphi^{-1}(\varphi( \varphi^{-1}(f) \varphi^{-1}(g) )) = \varphi^{-1}(f)\varphi^{-1}(g)$
• Identities: $1 = \varphi^{-1}(\varphi(1)) = \varphi^{-1}(1)$
• (Co)domains: $\delta_i(\varphi^{-1}(f)) = \varphi^{-1}(\varphi(\delta_i(\varphi^{-1}(f)))) = \varphi^{-1}(\delta_i(\varphi(\varphi^{-1}(f)))) = \varphi^{-1}(\delta_i(f))$

I'm wondering if this is an instance of some more general phenomenon, and if so which one!

Chad Nester (May 29 2024 at 12:41):

This feels like something that everyone might know, but I've only learned it today.

Ralph Sarkis (May 29 2024 at 12:43):

A natural transformation is an isomorphism if and only if each of its components are isomorphisms, and the components of the inverse transformation are the inverses of the corresponding components. I believe that once you can view your "mappings" as morphisms of models in some functorial semantics, then those will be natural transformations, so if they have an inverse, that inverse will also be natural, hence it will also be a "mapping".

Rémy Tuyéras (May 29 2024 at 12:57):

I'm wondering if this is an instance of some more general phenomenon, and if so which one!

I think this appears less mysterious when you regard functions as binary relations. Then, you can observe that a bijective mapping is invariant under

$(x,y) \mapsto (y,x)$

Since the axioms for functors are symmetric (i.e. invariant under the symmetry above), then your observation follows.

Rémy Tuyéras (May 29 2024 at 13:02):

Note that the statement that the axioms are invariant under ... is to be defined rigorously to match your obversation, though

John Baez (May 29 2024 at 13:12):

Chad Nester said:

I'm wondering if this is an instance of some more general phenomenon, and if so which one!

People are most familiar with the phenomenon you pointed out for algebras of a single-sorted [[Lawvere theory]], e.g.:

• monoids
• groups
• rings
• vector spaces
• associative algebras
• Lie algebras

and so on. This is why some books define an isomorphism of groups (for example) to be a homomorphism of groups whose underlying function is 1-1 and onto: it's then automatic that the inverse function is a homomorphism, and some books include this as a theorem.

Morgan Rogers (he/him) (May 29 2024 at 13:23):

I think this works for algebras of an arbitrary monad?

Chad Nester (May 29 2024 at 13:24):

I see! We can recover this as an instance of a similar fact about natural transformations, since functors arise as the model morphisms (which are natural transformations) when working with the theory of categories. I don't think the theory of categories is actually a Lawvere theory, but the idea still works. I think this is also what Ralph is saying.

Morgan Rogers (he/him) (May 29 2024 at 13:25):

If $(A,\alpha),(B,\beta)$ are algebras for $T$ and $h:A \to B$ is a morphism in the base category which is an isomorphism then $h$ is an algebra hom iff $h^{-1}$ is.

Morgan Rogers (he/him) (May 29 2024 at 13:26):

(and dually this works for coalgebras, and doesn't actually use any of the monad/comonad structure so applies to algebras/coalgebras of functors)

Morgan Rogers (he/him) (May 29 2024 at 13:27):

That saves handling any of the details of Lawvere theories, at any rate ;)

Chad Nester (May 29 2024 at 13:28):

I like that it works in settings without a theory/monad correspondence.

Ralph Sarkis (May 29 2024 at 13:29):

Chad Nester said:

I don't think the theory of categories is actually a Lawvere theory

True, maybe what I said is still true for lax natural transformations? (The theory of categories is a partial multi-sorted Lawvere Theory as per Example 6.3 in your paper.)

Todd Trimble (May 29 2024 at 13:29):

Morgan Rogers (he/him) said:

I think this works for algebras of an arbitrary monad?

Sure, it's basically saying that the forgetful functor from the category of algebras is conservative.

Todd Trimble (May 29 2024 at 13:33):

Ralph's comments can then be fitted into this observation.

Todd Trimble (May 29 2024 at 13:35):

Essential algebraicity will not be enough though, not without some qualification what is meant. The theory of posets is essentially algebraic, but the usual forgetful functor from posets to sets is far from conservative.

Chad Nester (May 29 2024 at 13:38):

If we take categories with finite limits as our notion of essentially algebraic theory then the "model morphisms are natural transformations" thing should give us what we want, so I think it's true.

John Baez (May 29 2024 at 13:49):

Todd Trimble said:

Essential algebraicity will not be enough though, not without some qualification what is meant. The theory of posets is essentially algebraic, but the usual forgetful functor from posets to sets is far from conservative.

Just in case anyone found that a bit too heavy duty:

The map from the 2-element poset $0 \le 1$ to the poset where $0 \le 1$ and also $1 \le 0$ is a map of posets, and its underlying function is invertible, but the inverse is not a map of posets. So the forgetful functor from posets to sets doesn't reflect isomorphisms. So posets can't be algebras of any Lawvere theory (in Set).

It's only when I understood this that I learned how to prove easily believable results like "posets are not the algebras of any Lawvere theory", or (using a similar trick) "topological spaces are not the algebras of any Lawvere theory".

Rémy Tuyéras (May 29 2024 at 15:13):

I think this appears less mysterious when you regard functions as binary relations. Then, you can observe that a bijective mapping is invariant under

$(x,y) \mapsto (y,x)$

Since the axioms for functors are symmetric (i.e. invariant under the symmetry above), then your observation follows.

Chad Nester Here is some clarification of my statement:

Let $R\subseteq A\times B$ be a binary relation and let $n$ be a positive integer. Consider a pair of functions as follows:
$F:A^n \to A$
$G:B^n \to B$

We say that $R$ is an $(F,G)$-morphism if the following function is well-defined:

$R^n \to R$
$(x_i,y_i) \mapsto (F(\overline{x}),G(\overline{y}))$

Note that $R$ is an $(F,G)$-morphism iff the symmetric relation $R^{\mathsf{op}}$ is a $(G,F)$-morphism.

My comment was saying that your observation boils down to noticing the following equivalence:

$R$ and $R^{\mathsf{op}}$ are functions iff $R$ is a bijection.