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: injection endofunctor on surjections

Asad Saeeduddin (Mar 05 2022 at 20:26):

Hi there. I was wondering the following:

1. Is there such a thing as a category of surjective functions?
2. For every set X, do injections out of X induce an endofunctor on the category of surjections? (i.e. does every surjection A -> B induce a surjection from the set of injections X -> A to the set of injections X -> B, subject to appropriate conditions?)
3. Does this extend to a functor from the category of sets and arbitrary functions to the endofunctor category on the category of surjective functions?
4. Can we generalize this away from the category of sets and speak of (perhaps suitably restricted) epis and monos?

Asad Saeeduddin (Mar 05 2022 at 20:59):

My guesses are:

1. Yes
2. Yes (think of the surjection A -> B as a B-indexed partition of A into non-empty sets, and of injections X -> B and X -> A as X-sized subsets of the index set and disjoint union of the partitions respectively)
3. Probably
4. Probably not for just epis and monos, maybe for regular epis or something like that?

John Baez (Mar 06 2022 at 15:51):

Could you spend a bit more time explaining how a surjection $f: A \to B$ is supposed to act to turn an injection $i: X \to A$ into an injection $j: X \to B$? Can you give me some sort of formula for $j$ in terms of $f$ and $i$?

For some reason I'm not understanding your description, even though I am familiar with how one can think of a surjection $f: A \to B$ as a $B$-indexed partition of $A$ into nonempty subsets, namely the fibers $f^{-1}(b)$ for $b \in B$.

Asad Saeeduddin (Mar 07 2022 at 12:35):

@John Baez It turns out that I was simply wrong! I was not thinking carefully enough about surjections. But I hope that I am at least wrong in an interesting way...

The way that I was thinking of a surjection was as a "two part" thing. The first part of a surjection $A \twoheadrightarrow B$ is simply a function $image : A \to B$. The second part is a function $preimage : B \to \mathcal{P}_{\geq 1}(A)$ (to non-empty subsets of $A$), subject to the constraints:

• $\forall\ (a : A)\ .\ \{a\} \subseteq preimage (image(a))$
• $\forall\ (b : B)\ .\ \mathcal{P}_{\geq 1}(image)(preimage(b)) \subseteq \{b\}$

These I think form a category whose composition and identity involve the monad structure of the non-empty powerset monad $\mathcal{P}_{\geq 1}$ (whose unit I actually implicitly utilize in the equations above).

Now, precisely as you pointed out, a surjection $A \twoheadrightarrow B$ and an injection $X \rightarrowtail A$ do not in general induce an injection $X \rightarrowtail B$. This is because an arbitrary injection $X \rightarrowtail A$ need not "respect" the partition induced by the surjection, since it can map multiple elements of $X$ to elements of the same partition in $A$. When composed with the $image$ of the surjection, injectivity is lost.

It's worth noting however that the composition of a surjection with an injection that "respects its partition" (by mapping distinct elements of its domain to elements of distinct partitions), is in fact an injection.

Hopefully I have managed so far to avoid screwing up again, I would really appreciate correction if not!

So the trouble with my proposal above is that, given a surjection $A \twoheadrightarrow B$, one can't construct the $image$ of a surjection $(X \rightarrowtail A) \twoheadrightarrow (X \rightarrowtail B)$ (in some sense $X \rightarrowtail A$ is "too large"). But (I believe) there is no difficulty with the "other half"!

That is to say, one can define a mapping of $preimage$ s $(B \to \mathcal{P}_{\geq 1}(A)) \to (X \rightarrowtail B) \to \mathcal{P}_{\geq 1}(X \rightarrowtail A)$, and interpret it as an endofunctor on the Kleisli category of the non-empty powerset monad. Given a partition of $A$, and an $|X|$ -sized subset of its indexing set $B$, we obtain all the $|X|$ -sized subsets of $A$ in which each selected partition is represented uniquely. There is always at least one such subset, by virtue of the partition consisting of non-empty subsets.

It is also worth noting that every injection $i : X \rightarrowtail A$ in the image of this mapping is a "partition respecting" injection of the sort discussed above.

I was wondering if this perhaps suggests that one can have an honest endofunctor on "partial surjections"? I.e. the output surjection simply neglects to act on any injections that do not respect the partition induced by the input surjection.

Asad Saeeduddin (Mar 07 2022 at 13:36):

For whatever reason I started by thinking about surjections, but I also wonder if there is an analogous "two part" characterization of injections.

Suppose we say $(-)_{*}$ is the "maybe monad" $X_{*} \mapsto X \uplus \{*\}$ with injections $nothing : X_{*}$ and $just : X \to X_{*}$ (the unit of the monad). Let's equip each set $X_{*}$ with a partial order whose only non-trivial inequations are $nothing \leq just(x)$ for each $x \in X$.

So now we might define an injection $A \rightarrowtail B$ to consist of a function $image : A \to B$ and a function $preimage : B \to A_{*}$, subject to the conditions:

• $\forall\ (a : A)\ .\ just(a) \leq preimage (image (a))$
• $\forall\ (b : B)\ .\ image_{*}(preimage(b)) \leq just(b)$

Does this make any sense?

Asad Saeeduddin (Mar 07 2022 at 16:42):

I'd conjecture there is a "lattice" of monotone maps $[1,1], [0,1], [1, *], [0,*] : \mathbf{Set} \to \mathbf{Ord}$. If one composes with a discarding of the preorder structure, we also end up with a lattice of monads $\mathbf{Set} \to \mathbf{Set}$ and their morphisms. A brief description of the functors is:

• $[1, 1]$ maps any set to the discrete preorder on that set
• $[0,1]$ maps any set to the set obtained by adjoining a point, and equips it with the preorder in which every element covers the point
• $[1, *]$ maps any set to the set of its non-empty subsets, and equips it with the preorder of inclusion
• $[0, *]$ maps any set to its powerset, and equips it with the preorder of inclusion

The bottom of the lattice is $[1, 1]$ and the top is $[0, *]$, and we can interpret each inequation in the lattice as both a monad morphism and a natural transformation of $\mathbf{Ord}$ -valued functors

All of this is to say the following: it seems like we can generalize from the typical hierarchy of "function, injection, surjection, bijection" to pairs of coalgebras of two functors drawn from the lattice described above (viewed as endofunctors on $\mathbf{Set}$), subject to a condition similar to the ones I stated above, but expressed in terms of the meet of the relevant functors. The notion of composition for each such variety of arrow involves the meet of the two selected monads.

This lets one somewhat mechanically define sensible notions of "partial function", "multi-valued surjection", etc, and suggests a framework in which suitably annotated arrows of a type theory are given pairs of "forward" and "backwards" semantics. So a "total surjection" can be run forwards on an input to calculate a precise result, or run backwards on an output to obtain a family of inputs that produce it. Or a "multi-valued injection" can be run on an input to calculate a family of results, or run backwards on an output in some family of results to obtain which (if any) input produces it.

Asad Saeeduddin (Mar 07 2022 at 16:42):

I also wonder if all of this can be transported to arbitrary topoi...

Morgan Rogers (he/him) (Mar 08 2022 at 08:43):

I gather that Ord is a category of preorders rather than a category of ordinals? :joy:
What's the motivation for that naming system?
It seems like you're missing an adjointness condition here. After all, a function completely determines its inverse image, so we can't take an arbitrary pair of coalgebras.

The things you suggest towards the end are probably true, but the framework you're proposing carries around a lot of baggage which is avoided by just using relations instead, so if you think there's something in it you'll need to look for some directions where it gets deeper. What's your own motivation for thinking about these things?

Asad Saeeduddin (Mar 08 2022 at 12:51):

@Morgan Rogers (he/him)

I gather that Ord is a category of preorders rather than a category of ordinals?

Yes, exactly! I am unfortunately not very familiar with mathematical parlance and found the name from the Wikipedia page for "category of preorders". Is there a more standard name for this?

What's the motivation for that naming system?

You can imagine the functor [x, y] to be imbuing a given set with the preorder (in fact lattice) of "at-least x-sized, and at-most y-sized" subsets under inclusions. I notate (perhaps poorly) an infinite size as $*$.

It seems like you're missing an adjointness condition here. After all, a function completely determines its inverse image, so we can't take an arbitrary pair of coalgebras.

It is true that you need an adjointness condition, this is precisely what I was referring to by:

subject to a condition similar to the ones I stated above, but expressed in terms of the meet of the relevant functors

So the idea is that the relationship between an arbitrary function and its inverse image is no different from the relationship between an injection and its inverse image: both are characterized by a Galois connection, just for different preorders in the lattice.

What's your own motivation for thinking about these things?

My motivation for thinking about such things is "computationally feasible" reversible programming. It is true that a function, or a multi-valued injection, or a partial surjection, etc. all have inverses in some abstract sense, but this is usually not computationally accessible. If one instead reformulates all these things as simple pairs of functions, it becomes easy to embed this framework in a language that is not a priori designed to work with relations, or to give a type theory semantics using these paired coalgebras.

You say that it is easy to just use relations, but I'm not sure how easy it is to work with infinite relations on a computer in the standard sense of "a subset of the cartesian product". It seems to me that to make the problem tractable one has to rely on the relation being a "functional relation" in some sense, and to switch from an explicit pairing of inputs and outputs to a perspective where the outputs (resp. inputs) latently associated with given inputs (resp. outputs) are revealed by computation.

Asad Saeeduddin (Mar 08 2022 at 13:22):

so if you think there's something in it you'll need to look for some directions where it gets deeper

There is certainly much I haven't said but suspect of such categories, and the relationships between them (e.g. being monoidal, cartesian, sometimes closed, sometimes not-quite-closed-but-cotensored) that is relevant to our ability to interpret suitably typed programs in them. I haven't expended much effort on working this out yet though, given that I have a tendency to screw up basic things and am still trying to verify whether the setup outlined above makes sense.