<p>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.
<br>
(<strong>EDIT</strong>: 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)))$
<br>
Is there a well-known name for the property enjoyed by this relation?  And are there natural examples in mathematics (or in <a href="http://en.wikipedia.org/wiki/Abstract_rewriting_system" rel="nofollow noreferrer">ARS</a>) of relations characterized by this property?</p>

<p>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 <a href="http://mathworld.wolfram.com/Church-RosserProperty.html" rel="nofollow noreferrer">Church-Rosser property</a>, according to which $x\mathsf{R}y$ and $y\mathsf{R}x$ are <em>simultaneously</em> 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.</p>

<p>(I am now <a href="https://math.stackexchange.com/q/645700/65869">cross-posting</a> this with Math.SE, to see if anyone there has an aswer to offer.)</p>

CC BY-SA 3.0
2014-01-18T15:26:18.533Z
Possibly relevant: http://en.wikipedia.org/wiki/Moral_graph
Jukka Suomela
CC BY-SA 3.0
2014-01-18T17:13:27.147Z
IIUC, it will be a symmetric and transitive relation and not very interesting (it might be because you are using the same symbol $R$ for different relations).
Kaveh
CC BY-SA 3.0
2014-01-18T17:42:36.207Z
@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.
J Marcos
CC BY-SA 3.0
2014-01-18T17:51:27.617Z
I would suggest that you move your comment (the formal statement of the property and the example) into the question.
Kaveh
CC BY-SA 3.0
2014-01-18T18:01:50.483Z
Note that any reflexive relation has this property.
David Richerby
CC BY-SA 3.0
2014-01-18T18:21:23.493Z
@DavidRicherby Yes, just like any reflexive relation is also [serial](http://en.wikipedia.org/wiki/Serial_relation)...  Following that line, perhaps the property whose name I'm looking for may be thought of precisely as a weaker version of seriality, by analogy with what it happens with [quasi reflexivity](http://math.stackexchange.com/questions/33954/is-there-a-name-for-this-type-of-binary-relation). But then again, before inventing unwonted terminology I would prefer to check whether an established one already exists. And *interesting* examples are still also welcome!
J Marcos
CC BY-SA 3.0
2014-01-23T16:51:53.733Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-01-28T13:56:08.723Z
@EmilJeřábek That's precisely the reason why I chose to mention Wolfram's version of Church-Rosser instead of the usual notion of _confluence_ that you mentioned, whose relation with my condition would indeed seem much less obvious.
J Marcos
CC BY-SA 3.0
2014-01-28T15:14:25.780Z
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$.
Emil Jeřábek
CC BY-SA 3.0
2014-01-28T15:25:02.227Z
All of which makes sense only because $\to_*$ is reflexive and transitive in this context by definition. The Church–Rosser property in Wolfram’s formulation is equivalent (by an easily proved lemma) to its special case that $w\to_*x$ and $w\to_*y$ imply the existence of $z$ such that $x\to_*z$ and $y\to_*z$.
Emil Jeřábek
CC BY-SA 3.0
2014-01-29T04:08:31.403Z
@EmilJeřábek What you wrote is correct. Let me try a different approach, proposed offline by a colleague. If the property we're discussing happens to fail, then there must be some object $b$ that is an $\mathsf{R}$-successor of a given object $a$ such that all $\mathsf{R}$-successors of $b$ fail to succeed $a$. This means that if we delete $b$ then $a$ won't be able to forward messages to the sucessors of $b$. The property we're discussing represents thus some kind of _robustness_ or _fault tolerance_ if seen as a communication protocol. Is this a known property, say, of _sensor networks_?
J Marcos
<graph-theory><terminology><term-rewriting-systems><modal-logic>
Is there a name for this property of a binary relation?
J Marcos
# Is there a name for this property of a binary relation?

(Asked by: username_0 on 2014-01-18)

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](http://en.wikipedia.org/wiki/Abstract_rewriting_system)) 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](http://mathworld.wolfram.com/Church-RosserProperty.html), 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](https://math.stackexchange.com/q/645700/65869) this with Math.SE, to see if anyone there has an aswer to offer.)

**Tags:** graph-theory, terminology, term-rewriting-systems, modal-logic
> **Comments:**
> **username_1**: Possibly relevant: http://en.wikipedia.org/wiki/Moral_graph  
> **username_2**: IIUC, it will be a symmetric and transitive relation and not very interesting (it might be because you are using the same symbol $R$ for different relations).  
> **username_0**: @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.  
> **username_2**: I would suggest that you move your comment (the formal statement of the property and the example) into the question.  
> **username_3**: Note that any reflexive relation has this property.  
> **username_0**: @DavidRicherby Yes, just like any reflexive relation is also [serial](http://en.wikipedia.org/wiki/Serial_relation)...  Following that line, perhaps the property whose name I'm looking for may be thought of precisely as a weaker version of seriality, by analogy with what it happens with [quasi reflexivity](http://math.stackexchange.com/questions/33954/is-there-a-name-for-this-type-of-binary-relation). But then again, before inventing unwonted terminology I would prefer to check whether an established one already exists. And *interesting* examples are still also welcome!  
> **username_4**: 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.  
> **username_0**: @EmilJeřábek That's precisely the reason why I chose to mention Wolfram's version of Church-Rosser instead of the usual notion of _confluence_ that you mentioned, whose relation with my condition would indeed seem much less obvious.  
> **username_4**: 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$.  
> **username_4**: All of which makes sense only because $\to_*$ is reflexive and transitive in this context by definition. The Church–Rosser property in Wolfram’s formulation is equivalent (by an easily proved lemma) to its special case that $w\to_*x$ and $w\to_*y$ imply the existence of $z$ such that $x\to_*z$ and $y\to_*z$.  
> **username_0**: @EmilJeřábek What you wrote is correct. Let me try a different approach, proposed offline by a colleague. If the property we're discussing happens to fail, then there must be some object $b$ that is an $\mathsf{R}$-successor of a given object $a$ such that all $\mathsf{R}$-successors of $b$ fail to succeed $a$. This means that if we delete $b$ then $a$ won't be able to forward messages to the sucessors of $b$. The property we're discussing represents thus some kind of _robustness_ or _fault tolerance_ if seen as a communication protocol. Is this a known property, say, of _sensor networks_?  

---

## 0 answers

