6
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ Possibly relevant: en.wikipedia.org/wiki/Moral_graph $\endgroup$ – Jukka Suomela Jan 18 '14 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 Jan 18 '14 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 Jan 18 '14 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$ – Emil Jeřábek Jan 23 '14 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$ – Emil Jeřábek Jan 28 '14 at 15:14

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.