When a binary relation is connected?

82 Views Asked by At

On this wiki article is claimed that a binary relation $\mathcal R$ on a set $X$ is connected (by definition) if the proposition $$ \tag{1}\label{1}(\forall a)(\forall b)\big((a\in X)\wedge(b\in X)\wedge(a\neq b)\rightarrow(a\mathcal R b)\vee(b\mathcal Ra)\big) $$ is true and then it is there observed that $\mathcal R$ is connected iff the proposition $$ \tag{2}\label{2}(\forall a)(\forall b)\big((a\in X)\wedge(b\in X)\rightarrow(a\mathcal R b)\vee(a=b)\vee(b\mathcal R a)\big) $$ is true.

So, I would like to understand if a connected relation $\mathcal R$ must be reflexive or not since the proposition \eqref{2} confused me a lot: indeed, it seems to me that it implicitly ensures that any $x$ in $X$ is related with it self by $\mathcal R$ so that we could say that $\mathcal R$ is connected if and only if the proposition $$ \tag{3}\label{3}(\forall a)(\forall b)\big((a\in X)\wedge(b\in X)\rightarrow a\mathcal R b\big) $$ is true but I am not really sure about so that I thought to put a question where I ask for elucidation, asking in particular if \eqref{3} is equivalent to \eqref{1} and so if a connected relation must be reflexive. So could someone help me, please?

1

There are 1 best solutions below

4
On BEST ANSWER

The reference article is saying that a relation is connected iff

$\forall a(\forall b(((a\in X\land b\in X)\rightarrow(a\neq b\rightarrow(aRb\ \vee\ bRA))))$, or equivalently as:

$(A\rightarrow(B\rightarrow C))\leftrightarrow(A\land B\rightarrow C)$,

$\forall a(\forall b((a\in X\land b\in X\land a\neq b)\rightarrow(aRb\ \vee\ bRA)))$, your (1).

And conditional disjunction tells us that $(a\neq b\rightarrow(aRb\ \vee\ bRA))$ is equivalent to $(a=b\vee(aRb\ \vee\ bRA))$ and so as the article states, the definition of connected is therefore also equivalent to:

$\forall a(\forall b((a\in X\land b\in X)\rightarrow(a= b \vee (aRb\ \vee\ bRA))))$, your (2).

That is your (1) and (2) are equivalent. And under this definition, we cannot conclude that $R$ is reflexive. That is, if a relation is connected, then it is not necessarily reflexive.

But the article introduces another term, which is strongly connected. A relation is strongly connected iff

$\forall a(\forall b((a\in X\land b\in X)\rightarrow(aRb\ \vee\ bRA)))$, your (3).

And from this definition it is clear that if a relation is strongly connected it is reflexive. Your (3) is not equivalent to (1).