5
$\begingroup$

The following math.stackexchange question asked whether there is a name for a certain sort of relation. I have become interested in the question, and no one suggested a name there, so I am asking here instead. Furthermore I would be interested in the name of the category of such relations.

https://math.stackexchange.com/questions/391108/is-there-a-name-for-relations-with-this-property

I repeat the specification from the above link. The relations are those of the form $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions

$$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply that $$x'y' \in \rho$$

By "category of such relations" I mean the category whose objects are such relations $\rho : X_\rho \rightarrow Y_\rho$, and whose morphisms are pairs of functions $(f_X : X_\rho \to X_{\rho'}, \,\, f_Y : Y_\rho \to Y_{\rho'})$ that preserve relatedness, i.e. $xy \in \rho \Rightarrow f_X(x)f_Y(y) \in \rho'$.

I am considering these concepts in the context of John Reynold's work on relational parametricity in type theory.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Whatever they might be called, this looks like an interesting notion. Remark that functions and opposites of functions form such relations. Also remark that the condition is equivalent to saying $\rho = \rho \rho^{op} \rho$ (literally the condition is saying "$\geq$", but "$\leq$" happens to be true for any relation $\rho$). I can't locate my copy of Categories, Allegories to see if Freyd-Scedrov introduce this notion, but I am vaguely reminded of von Neumann regular elements. $\endgroup$
    – Todd Trimble
    Commented Oct 27, 2013 at 14:43
  • $\begingroup$ Interesting, Todd. Indeed operator theory might be a good place to look for an analogy. Perhaps the correct condition there would be $\rho = \rho\rho^*\rho$, where $\rho^*$ is the adjoint of $\rho$. This class would contain the orthogonal operators, for example. $\endgroup$
    – Tom Ellis
    Commented Oct 27, 2013 at 15:28
  • $\begingroup$ I've just posted an answer to the MSE question, but note that such relations are also called difunctional relations. In the category of sets, or any pretopos, they coincide with pullbacks, see for example tac.mta.ca/tac/volumes/27/1/27-01abs.html $\endgroup$
    – Arnaud D.
    Commented Sep 19, 2018 at 14:35
  • $\begingroup$ Robert Harper, in "Reynolds’s Parametricity Theorem, Directly" calls these "zig-zag complete" binary relations (cs.cmu.edu/~rwh/courses/chtt/pdfs/reynolds.pdf). $\endgroup$
    – Tom Ellis
    Commented Jul 3, 2021 at 7:53
  • $\begingroup$ The earliest reference I know of to such relations related to parametricity is "Internalizing Relational Parametricity in the Extensional Calculus of Constructions" by Krishnaswami and Dreyer (2013). $\endgroup$
    – Tom Ellis
    Commented Oct 4, 2022 at 16:00

3 Answers 3

Reset to default
5
$\begingroup$

The set of all relations $\alpha\subset X\times Y$ is a semiheap with respect to the ternary operation $[\alpha_1,\alpha_2,\alpha_3]=\alpha_1\alpha_2^{-1}\alpha_3$ ($\alpha^{-1}$ is $\alpha^{*}$in notation of Tom Ellis and $\alpha^{op}$ by Todd Trimble). Your relation yields $[\rho,\rho,\rho]=\rho$ and is called an idempotent (http://en.wikipedia.org/wiki/Semiheap).

Improve this answer
$\endgroup$
1
  • $\begingroup$ @ Todd Trimble: You are welcome. $\endgroup$
    – Boris Novikov
    Commented Oct 30, 2013 at 13:46
3
$\begingroup$

I have come across such relations in the past, and (in my head) have referred to them as jigsaw relations. The idea is probably best conveyed in the form of a picture, but I will try to explain my thinking.

Let $\rho\colon X\to Y$ be a relation arising from jigsaw pieces in the following way. Think of the elements of $X$ as jigsaw pieces with a 'tab' sticking out of the right edge, the elements of $Y$ as jigsaw pieces with a 'hole' in the left edge, and $xy\in\rho$ as meaning "the tab of $x$ fits exactly into the hole of $y$".

Claim: such a relation satisfies $xy,x'y,xy'\in\rho\implies x'y'\in\rho$.

Proof: if $xy\in\rho$ and $x'y\in\rho$ then the tab of $x'$ must be identical to the tab of $x$ (because they both fit exactly into the hole of $y$), so if $xy'\in\rho$ as well then the tab of $x'$ fits exactly into the hole of $y'$ because the tab of $x$ does. That is, $x'y'\in\rho$ follows from the other three conditions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I like the jigsaw analogy. It seems to fit perfectly. $\endgroup$
    – Tom Ellis
    Commented Oct 30, 2013 at 17:11
2
$\begingroup$

These have probably been invented many times, but they are most typically called difunctional relations. They were introduced and named that by Jacques Riguet in 1948, Relations binaires, fermetures, correspondances de Galois.

A nice paper on them is Lambek's Goursat's Theorem and the Zassenhaus Lemma, which shows that when you have a Mal'cev term (which includes groups, rings, Lie algebras, etc.) that every relation is difunctional, and you can use that to give a unified proof of the Jordan-Hölder theorem. (The unified proof is not new with that paper, but it shows how to effectively use difunctionality.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .