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: dual to partial maps

Matteo Capucci (he/him) (Jul 05 2024 at 13:26):

A partial map $X \to Y$ is a span $X \hookleftarrow S \xrightarrow{f} Y$, where $S \hookrightarrow X$ is its domain of definition and $f:S \to Y$ the actual map.
One can dualize this definition: a 'copartial map' is a cospan of the form $X \xrightarrow{f} Q \twoheadleftarrow Y$. In $\bf Set$, if partial maps relax the totality condition of a function, copartial ones kinda relax single-valuedness by allowing $f$ to have many (non-repeating) values, squashed by the quotient $Y \twoheadrightarrow Q$. Of course this intuition is shaky outside of regular categories.

I wonder if anyone has seen something like this around?

Simon Burton (Jul 05 2024 at 13:46):

Here is an example that comes to mind: the projection Y to Q is a covering space, and X is an interval. Then we might be interested in how f lifts to a map from X to Y.

Rémy Tuyéras (Jul 05 2024 at 13:51):

If you restrict your problem to $\mathsf{Set}$, then every surjection $Q \twoheadleftarrow Y$ can be associated with its fiber map $Q \to \mathcal{P}(Y)$ where $\mathcal{P}(Y)$ is the power set on $Y$. This means that your pair $X \mathop{\rightarrow}\limits^{f} Q \twoheadleftarrow Y$ can be seen as a pair of composable functions:

$X \mathop{\rightarrow}\limits^{f} Q \to \mathcal{P}(Y)$

This potentially indicates that you might also want to look at these arrows in a Kleisli category, or in the category of idempotent commutative monoids.

Rémy Tuyéras (Jul 05 2024 at 16:58):

Also, note that you have a function $\iota_Y:\mathcal{P}(Y) \times \mathcal{P}(Y) \to \mathcal{P}(Y)$ that maps

$(A,B) \mapsto A \cap B$

and a function $\mathcal{P}(Y) \to \mathbf{2}$ that says whether a subset of $Y$ is empty or not. If you want to formalize the non-intersection between fibers, you can consider maps $f:X \to \mathcal{P}(Y)$ such that the composite

$X \times X \mathop{\longrightarrow}\limits^{f\times f} \mathcal{P}(Y) \times \mathcal{P}(Y) \to \mathcal{P}(Y) \to \mathbf{2}$

is the equality test function on $X$.

Matteo Capucci (he/him) (Jul 05 2024 at 16:59):

Rémy Tuyéras said:

If you restrict your problem to $\mathsf{Set}$, then every surjection $Q \twoheadleftarrow Y$ can be associated with its fiber map $Q \to \mathcal{P}(Y)$ where $\mathcal{P}(Y)$ is the power set on $Y$. This means that your pair $X \mathop{\rightarrow}\limits^{f} Q \twoheadleftarrow Y$ can be seen as a pair of composable functions:

$X \mathop{\rightarrow}\limits^{f} Q \to \mathcal{P}(Y)$

This potentially indicates that you might also want to look at these arrows in a Kleisli category, or in the category of idempotent commutative monoids.

Yeah this is the multivalued maps interpretation

Matteo Capucci (he/him) (Jul 05 2024 at 17:01):

Simon Burton said:

Here is an example that comes to mind: the projection Y to Q is a covering space, and X is an interval. Then we might be interested in how f lifts to a map from X to Y.

Uhm you made me realize an example of this kind of functions are periodic functions, going from reals to reals quotiented by integer translations

Rémy Tuyéras (Jul 05 2024 at 17:22):

You have another example in $\mathbf{Ring}$ with functions that try to solve the Chinese Remainder Theorem:

$R \to \mathbb{Z}/p\mathbb{Z} \leftarrow \mathbb{Z}/pq\mathbb{Z}$

The reason why these maps make sense is that the section $\mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/pq\mathbb{Z}$ is not even a ring morphism. So the most sensical way to talk about potential solutions for the CRT in the category $\mathbf{Ring}$ is by using the fibers of $\mathbb{Z}/p\mathbb{Z} \leftarrow \mathbb{Z}/pq\mathbb{Z}$

Rémy Tuyéras (Jul 05 2024 at 17:47):

The previous example consider maps $Y \to Q$ where $Y \cong Q \times F$, so you could also look at fibrations. For example, when you have a sequence of fibrations:

$\dots \to E_2 \to E_1 \to E_0 \to B$

then you can consider cospans of the form $\gamma:[0,1] \to B \leftarrow E_0$ to talk about the possible liftings. Such liftings $\gamma':[0,1] \to E_0$ can then be used to form another cospan

$\gamma':[0,1] \to E_0 \leftarrow E_1$

and so on...

EDIT: I realize that's basically Simon's example extended to sequences of arrows, but maybe there is something about compositions of these arrows here

Nathaniel Virgo (Jul 07 2024 at 01:47):

I don't know if this is a useful observation, but we can think of a function $X\to Y$ as assigning to each $y\in Y$ the preimage $f^{-1}(y)\subseteq X$, such that the preimages are disjoint and their union is $X$. Copartial maps relax the disjointness condition, but only insofar as two points in $Y$ are now allowed to have the same preimage - disjoint but overlapping preimages are still not allowed. The union of the preimages still has to be $X$ due to the epimorphism requirement. I don't know if that helps to suggest other examples.

Rémy Tuyéras (Jul 07 2024 at 22:04):

Nathaniel Virgo said:

I don't know if this is a useful observation, but we can think of a function $X\to Y$ as assigning to each $y\in Y$ the preimage $f^{-1}(y)\subseteq X$, such that the preimages are disjoint and their union is $X$. Copartial maps relax the disjointness condition, but only insofar as two points in $Y$ are now allowed to have the same preimage - disjoint but overlapping preimages are still not allowed. The union of the preimages still has to be $X$ due to the epimorphism requirement. I don't know if that helps to suggest other examples.

:thinking: I think your point hints to the fact that there would be no obvious compositions for copartial maps $f:X \to Q \twoheadleftarrow Y$ because sending the disjoint sets of preimages via a second morphism $g:Y \to P \twoheadleftarrow Z$ would now give arbitrary sets of preimages.

This is also suggested by the approach I proposed above with the power set monad, where the only way to make the map $\cap:\mathcal{P}(Y) \times \mathcal{P}(Y) \to \mathcal{P}(Y)$ natural in the variable $Y$ would be to

• either take the contravariant version of the power set monad $\mathcal{P}$ (as opposed to what is usually done with the covariant version)
• or consider inclusions with the covariant version of $\mathcal{P}$.

It's almost like the math would tell us to consider a setting where we look at copartial maps of the form $X \hookrightarrow Q \twoheadleftarrow Y$ only.

Matteo Capucci (he/him) (Jul 08 2024 at 06:50):

Copartial maps compose like cospans just fine since the pushout of an epi is an epi

Matteo Capucci (he/him) (Jul 08 2024 at 06:51):

Nathaniel Virgo said:

I don't know if this is a useful observation, but we can think of a function $X\to Y$ as assigning to each $y\in Y$ the preimage $f^{-1}(y)\subseteq X$, such that the preimages are disjoint and their union is $X$. Copartial maps relax the disjointness condition, but only insofar as two points in $Y$ are now allowed to have the same preimage - disjoint but overlapping preimages are still not allowed. The union of the preimages still has to be $X$ due to the epimorphism requirement. I don't know if that helps to suggest other examples.

What do you mean by 'disjoint but overlapping' :thinking:

Nathaniel Virgo (Jul 08 2024 at 07:03):

Oops, that should have been "distinct but overlapping", i.e. they're only allowed to overlap if they're the same set

Rémy Tuyéras (Jul 08 2024 at 11:01):

Matteo Capucci (he/him) said:

Copartial maps compose like cospans just fine since the pushout of an epi is an epi

Oh yeah, for sure, I was just trying to go with the restriction that your copartial maps would have non repetitive images. I guess you are not really after that property specifically

Jules Hedges (Jul 08 2024 at 12:31):

This construction is faintly familiar to me. I think I came up with it years ago while trying to construct Rel as a category of decorated cospans, using the construction from "A recipe for black box functors"