Consider a fixed but arbitrary preordered set $X$. Is there a name for those binary relations $R$ on $X$ satisfying the following? They seem to show up a lot. (Note that every such $R$ is necessarily transitive.)

  1. $R(x,y) \rightarrow x \lesssim y$
  2. $R(x,y) \wedge (y \lesssim z) \rightarrow R(x,z)$
  3. $(x \lesssim y) \wedge R(y,z) \rightarrow R(x,z)$


  • The strict $(<)$ and non-strict $(\lesssim)$ order relations on any preordered set $X$.
  • Let $I$ denote an arbitrary non-empty set. Then the set $\mathbb{R}^I$ of functions $I \rightarrow \mathbb{R}$ is partially ordered in the obvious way via the pointwise order: $$f \leq g \iff (\forall i \in I)(f(i) \leq g(i)).$$ Now define a binary relation $R$ on $\mathbb{R}^I$ as follows. $$R(f,g) \iff (\forall i \in I)(f(i) < g(i)).$$ Then $R$ satisfies the conditions of interest. More generally, we can replace $\mathbb{R}$ with any preordered set $X$, and we can replace $<$ with any binary relation on $X$ satisfying 1,2 and 3.

  • (This is the example I'm most interested in.) Let $X$ denote a metric space. Then its powerset $\mathcal{P}(X)$ is partially ordered by inclusion. Define $R$ on $\mathcal{P}(X)$ by asserting that for all $A,B \in \mathcal{P}(X)$, we have $R(A,B)$ iff $A$ is not only contained in $B$, but in fact, it can be "swelled" by some non-zero positive number while remaining contained in $B$. See here for a precise definition; the relation of interest is denoted "$\lhd$" in the link.

  • $\begingroup$ I don't know a name for these. Looks like the idea is: $R(x,y)$ means that $x\lesssim y$ with "some room to spare". $\endgroup$ – Greg Martin Nov 30 '14 at 0:14
  • $\begingroup$ @GregMartin, yep, that's basically the idea. In the original question, I included an irreflexivity axiom, namely $\neg R(x,x).$ I ended up removing it, because the category whose objects are preordered sets equipped such a relation $R$ ends up being better behaved if we omit irreflexivity. But yes, the "room to spare" intuition is definitely where I'm coming from. $\endgroup$ – goblin Nov 30 '14 at 0:21
  • 1
    $\begingroup$ Another example would be where $x\lesssim y$ is the inclusion relation on subsets of some topological space, and $R(x,y)$ if and only if the closure of $x$ is contained in the interior of $y$. $\endgroup$ – Greg Martin Nov 30 '14 at 0:23
  • $\begingroup$ @GregMartin, nice example. Generalizing: given any preordered set $X$ and monotonic functions $\mathrm{cl},\mathrm{int} : X \rightarrow X$ satisfying the axiom $\mathrm{int}(x) \lesssim x \lesssim \mathrm{cl}(x),$ we get such a $R$ relation on $X$ by defining that $R(x,y)$ iff $\mathrm{cl}(x) \lesssim \mathrm{int}(y)$. I wonder if assuming that one or both elements of $\{\mathrm{cl},\mathrm{int}\}$ are idempotent gives us anything further about $R$. $\endgroup$ – goblin Nov 30 '14 at 0:30
  • $\begingroup$ @GregMartin, okay, if $\mathrm{cl}$ is idempotent, then we furthermore have $R(x,y) \rightarrow R(\mathrm{cl}(x),y)$. Similarly with $\mathrm{int}$ on the other side. $\endgroup$ – goblin Nov 30 '14 at 0:35

It would be reasonable to call such things "coreflexive profunctors." Here's why.

The notion of a profunctor comes from category theory. When we specialize to the $\mathrm{Bool}$-enriched case, the following definition is obtained.

Definition 0. Let $P$ and $Q$ denote preordered sets. Then a relation $R : P \nrightarrow Q$ is said to be a ($\mathrm{Bool}$-enriched) profunctor iff the following two axioms hold.

  • $p' \lesssim p, R(p,q) \rightarrow R(p',q)$
  • $R(p,q), q \lesssim q' \rightarrow R(p,q')$

Now we just have to explain what "coreflexive" means:

Definition 1. Let $P$ denote a preordered set, and $R : P \nrightarrow P$ denote a relation. Then:

  • $R$ is reflexive iff $p \lesssim p' \rightarrow R(p,p')$
  • $R$ is coreflexive iff $R(p',p) \rightarrow p \lesssim p'$

Note that if $P$ is just a set, then viewing it as a (discrete) poset, the above notion of reflexivity reduces the usual notion.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.