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

Peiyuan Zhu (Dec 24 2022 at 22:09):

Is it reasonable to think about relationally define reflexivity, symmetricity, transitivity in the Rel category, just like injectivity, surjectivity, bijectivity are defined via monic, epic, iso arrows. It is reasonable to constraint the problem as only equality, implication, and composition are legitimate operators involved? I would hope someone to not to show me the answer directly if they already know the answer to this question, but to help me a bit in my thinking process.

Ralph Sarkis (Dec 24 2022 at 22:30):

I am not sure about $\mathbf{Rel}$ as a simple category, but $\mathbf{Rel}$ is also a thin $2$-category or a poset-enriched category. No matter if these terms don't mean anything to you, the important part is that for two morphisms $R,S: X \rightarrow Y$, you can talk about inclusions of one in the other. We say that $R\subseteq S$ if and only if $R(x,y) \implies S(x,y)$ for all $(x,y) \in X\times Y$. Now you can try to figure out a way to use this additional structure to talk about relfexivity, symmetry and transitivity.

Peiyuan Zhu (Dec 24 2022 at 22:31):

What is thin 2-category and poset-enriched category? What's the difference between these and what you would call "simple category"?

Ralph Sarkis (Dec 24 2022 at 22:39):

It is not really important. In short it tells you that the inclusion is a partial order on $\mathrm{Hom}(X,Y)$ (i.e. it is reflexive, transitive and antisymmetric) and it behaves well with composition.

John Baez (Dec 24 2022 at 22:52):

It actually is important.

Ralph Sarkis (Dec 24 2022 at 22:58):

I meant it is not important for now. I first want to see if Peiyuan can find how to characterize reflexivity, symmetry and transitivity using only composition, identities and inclusion. After that, we could dig into the details.

Mike Shulman (Dec 24 2022 at 22:59):

FWIW: I presume by "simple category" you mean "ordinary category", i.e. not poset-enriched. But "simple" is a bit of a dangerous word to use in the "ordinary" way in mathematics, as mathematicians like to give it complicated meanings. For instance, in the context of [[FOLDS]] a "simple category" means a skeletal one-way category with finite fan-out. (-:O

John Baez (Dec 24 2022 at 23:08):

Ralph Sarkis said:

I meant it is not important for now. I first want to see if Peiyuan can find how to characterize reflexivity, symmetry and transitivity using only composition, identities and inclusion. After that, we could dig into the details.

That makes sense!

Peiyuan Zhu (Dec 28 2022 at 02:26):

When I begin my investigation, I wonder what kind of property shall I aim for? It seems that monic arrows iff injective but surjective implies but isn't identical to epic. So it looks like a weaker condition than the original one is okay, as long as it holds in most cases? (Please again don't give out the answer, just help me to think about it, or explain why this is acceptable, e.g. is it because you're working on a generalization?)

Ralph Sarkis (Dec 28 2022 at 02:45):

Let us start with something else. Do you know about the opposite of a relation? If you have a relation $R\subseteq X\times Y$, the oppoiste of $R$ is a relation $R^{\mathrm{op}} \subseteq Y \times X$ defined by $(y,x) \in R^{\mathrm{op}} \Leftrightarrow (x,y) \in R$.

In $\mathbf{Rel}$, $R$ is a morphism $X \rightarrow Y$ and $R^{\mathrm{op}}: Y \rightarrow X$, so we have composites $R;R^{\mathrm{op}}: X \rightarrow X$ and $R^{\mathrm{op}}; R: Y \rightarrow Y$ (I write composition of relations in diagrammatic order, i.e. $R;R^{\mathrm{op}} = R^{\mathrm{op}} \circ R$).

What does it mean for the first composite to be equal to $\mathrm{id}_X$? What if the second is equal to $\mathrm{id}_Y$? What if both are true?

Peiyuan Zhu (Dec 28 2022 at 02:45):

Conjecture: $R\subset R\circ R^{-1}$ is a generalization of reflexivity. I need to run now but I'll verify this later.

Peiyuan Zhu (Dec 28 2022 at 02:48):

Ralph Sarkis said:

Let us start with something else. Do you know about the opposite of a relation? If you have a relation $R\subseteq X\times Y$, the oppoiste of $R$ is a relation $R^{\mathrm{op}} \subseteq Y \times X$ defined by $(y,x) \in R^{\mathrm{op}} \Leftrightarrow (x,y) \in R$.

In $\mathbf{Rel}$, $R$ is a morphism $X \rightarrow Y$ and $R^{\mathrm{op}}: Y \rightarrow X$, so we have composites $R;R^{\mathrm{op}}: X \rightarrow X$ and $R^{\mathrm{op}}; R: Y \rightarrow Y$ (I write composition of relations in diagrammatic order, i.e. $R;R^{\mathrm{op}} = R^{\mathrm{op}} \circ R$).

What does it mean for the first composite to be equal to $\mathrm{id}_X$? What if the second is equal to $\mathrm{id}_Y$? What if both are true?

Is this related to the question why generalization is acceptable? My personal answer is that category is already a generalization / higher abstraction of many things so it's not a surprise to see a generalization of existing properties.

Peiyuan Zhu (Dec 28 2022 at 02:50):

Peiyuan Zhu said:

Conjecture: $R\subset R\circ R^{-1}$ is a generalization of reflexivity. I need to run now but I'll verify this later.

Actually why not just do $id\subset R$ implies reflexivity.

Ralph Sarkis (Dec 28 2022 at 02:53):

Peiyuan Zhu said:

Is this related to the question why generalization is acceptable?

If by generalization you mean my message about inclusions of relations, yes. These questions are supposed to make clear why inclusions are really nice to talk about for $\mathbf{Rel}$.

Peiyuan Zhu (Feb 27 2023 at 01:29):

Is there any work on algebra of Rel? Something like $T:R_1\times R_2\times R_3\rightarrow R$ that takes several relations and map to one relation

Peiyuan Zhu (Feb 27 2023 at 01:32):

Maybe a generalization of limit into Rel

Jean-Baptiste Vienney (Feb 27 2023 at 03:08):

You can take the sum $R_1 + R_2 + R_3$ it’s defined as the relation which relates $x$ to $y$ if and only if $R_1, R_2$ or $R_3$ relates $x$ to $y$.

Jean-Baptiste Vienney (Feb 27 2023 at 03:09):

You have products but not every limit in $\mathbf{Rel}$

Evan Patterson (Feb 27 2023 at 03:53):

Peiyuan Zhu said:

Is there any work on algebra of Rel? Something like $T:R_1\times R_2\times R_3\rightarrow R$ that takes several relations and map to one relation

This sort of thing is well described by the cartesian bicategory of relations or, better yet, the cartesian double category of relations. In such a structure, you can take products of objects (sets) and products of relations, and then you can look at cells betweens relations, which include maps of the form you describe.

Evan Patterson (Feb 27 2023 at 03:56):

In a paper of mine, I give an exposition of bicategories of relations that is more leisurely than most of the literature on this topic.

Peiyuan Zhu (Feb 27 2023 at 21:27):

Is there anyone familiar with the literature of multivalued mappings? https://encyclopediaofmath.org/wiki/Multi-valued_mapping It looks like Kuratowski, Bouligand has done a lot of work on this a long time ago but all their writings are in French so they're not fathomable to my French level. I'm not sure if there has been more recent work.

Peiyuan Zhu (Feb 27 2023 at 21:27):

(deleted)

Peiyuan Zhu (Feb 27 2023 at 21:29):

(deleted)

Peiyuan Zhu (Feb 28 2023 at 18:29):

For a multivalued mapping $\Gamma:X\rightarrow Y$, how to undertand its small inverse image $\Gamma^+(U)=\{x\in X:\Gamma(x)\subset U\}$ and large inverse image $\Gamma^-(U)=\{x\in X:\Gamma(x)\cap U\ne\emptyset\}$? Why is this structure important? Is there any categorical meaning behind it?

Peiyuan Zhu (Feb 28 2023 at 18:31):

I can understand that it "approximates the inverse" but this is too vague.

Peiyuan Zhu (Feb 28 2023 at 18:52):

They look a lot like the quantifiers http://therisingsea.org/notes/ch2018-lecture13.pdf. Maybe they are exactly quantifiers.