Consider a binary relation $\mathsf{R}$ such that $x\mathsf{R}y$ is the case only if there is some $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case.
(EDIT: note that this may be formalized as $\forall x\forall y(x\mathsf{R}y\to\exists z(x\mathsf{R}z\land y\mathsf{R}z)))$
Is there a well-known name for the property enjoyed by this relation? And are there natural examples in mathematics (or in ARS) of relations characterized by this property?

In normal modal logic, the above property characterizes frames axiomatized by the schema $\lozenge\square\alpha\to\lozenge\alpha$ (or, dually, by $\square\alpha\to\square\lozenge\alpha$). It amounts to a stronger version of the Church-Rosser property, according to which $x\mathsf{R}y$ and $y\mathsf{R}x$ are simultaneously the case only if there is a $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case. I have however been unable to determine so far whether there is an established name for the above mentioned property in the literature.

(I am now cross-posting this with Math.SE, to see if anyone there has an aswer to offer.)

  • 1
    $\begingroup$ Possibly relevant: en.wikipedia.org/wiki/Moral_graph $\endgroup$ Commented Jan 18, 2014 at 15:26
  • 1
    $\begingroup$ @Kaveh No, it need not be symmetric. Consider $\mathsf{R}=\{(a,b),(b,b)\}$, for instance. Now, I am not sure I understand what you mean by different relations. The property I am asking about is described at the first paragraph of my question, namely: $\forall x\forall y(x\mathsf{R}y\to\exists z(x\mathsf{R}z\land y\mathsf{R}z))$. The second paragraph of my question simply mentions a weaker, albeit well-known, property. $\endgroup$
    – J Marcos
    Commented Jan 18, 2014 at 17:42
  • 1
    $\begingroup$ I would suggest that you move your comment (the formal statement of the property and the example) into the question. $\endgroup$
    – Kaveh
    Commented Jan 18, 2014 at 17:51
  • 1
    $\begingroup$ The Church–Rosser property as normally stated actually says that if xRy and xRz, then there is w such that yRw and zRw. (This is muddled in Wolfram’s formulation, where $\leftrightarrow_*$ apparently denotes the symmetric transitive closure of $\to$.) I don’t see how this is implied by your condition. $\endgroup$ Commented Jan 23, 2014 at 16:51
  • 1
    $\begingroup$ But the formula mentioned in your question is neither confluence nor the Church–Rosser property in either Wolfram’s or any other usual formulation. $x\leftrightarrow_*y$ does not mean $x\to_* y$ AND $y\to_* x$, it means that there is a sequence $x=x_0,x_1,\dots,x_n=y$ such that for each $i<n$, $x_i\to_*x_{i+1}$ OR $x_{i+1}\to_*x_i$. $\endgroup$ Commented Jan 28, 2014 at 15:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.