Let $X$ and $Y$ denote sets. Then a relation $X \rightarrow Y$ is, by definition, a subset of $X \times Y$. Dually, we can define that a "corelation" $X \rightarrow Y$ is a partitioning of $X \uplus Y.$

General Question. Where can I learn more about corelations?

Here's a list of specific questions that I am interested in.

  1. Can corelations can be composed in a sensible way? If so:

  2. Do they constitute the arrows of a poset-enriched dagger category $\mathrm{cRel}$, in the same way that relations constitute the arrows of $\mathrm{Rel}$? If so, is this an allegory?

  3. What are the mappings in $\mathrm{cRel},$ by which I mean the arrows $f : X \rightarrow Y$ such that $\mathrm{id}_X \leq f^\dagger \circ f$ and $f \circ f^\dagger \leq \mathrm{id}_Y.$

  4. Can $\mathrm{Set}$ be viewed as a wide subcategory of $\mathrm{cRel}$?

  5. What are the pre-orders in $\mathrm{cRel}$? By which I mean the endomorphisms $f : X \rightarrow X$ such that $\mathrm{id}_X \leq f$ and $f \circ f \leq f.$

  6. What are the equivalence relations? By which I mean the pre-orders $f$ such that $f^\dagger = f.$

To reiterate: what I'd really like to know is, where can I learn more?

  • 2
    $\begingroup$ If $\mathcal{C}$ is a regular category, then there is an allegory $\mathbf{Rel}(\mathcal{C})$. In particular $\mathbf{Set}^\mathrm{op}$ is a regular category, so there is an allegory $\mathbf{Rel}(\mathbf{Set}^\mathrm{op})$. $\endgroup$ – Zhen Lin Feb 13 '14 at 10:48
  • $\begingroup$ @ZhenLin, thanks; any idea what $\mathbf{Rel}(\mathbf{Set}^{\mathrm{op}})$ looks like concretely? $\endgroup$ – goblin Feb 13 '14 at 10:49
  • $\begingroup$ The morphisms are as you describe, though more usually described as a quotient of $X \amalg Y$ than a partition. Composition is defined by pushout and image factorisation. $\endgroup$ – Zhen Lin Feb 13 '14 at 10:51
  • $\begingroup$ Assume $\alpha:X-Y$ and $\beta:Y-Z$ corelations, i.e. jointly epic cospans (e.g. $X\to \alpha \leftarrow Y$) in ${\bf Set}$. Then $\alpha$ can also be regarded as the graph consisting of full cliques (the partitioned classes) on $X+Y$. The pushout of the cospan, say $\gamma$, joins together all the connected components of the union graph of $\alpha$ and $\beta$, then finally for the composition $\alpha\beta$ you still have to forget all components that lie fully in $Y$. $\endgroup$ – Berci Feb 14 '14 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.