I've seen a few answers to this, like here and but they are not satisfying to me (possibly too advanced).

The definitions in my book are as follows:

  • A binary relation $\mathrel{R}$ on two sets $A$ and $B$ is a subset of $A \times B$, whose elements can be written $a \mathrel{R} b$.
  • When we say $\mathrel{R}$ is binary relation on $A$, we mean that $R$ is a subset of $A \times A$.
  • The relation $R$ is transitive if $a \mathrel{R} b$ and $b \mathrel{R} c$ imply $a \mathrel{R} c$, for all $a,b,c \in A$.
  • The relation $R$ is symmetric if $a \mathrel{R} b$ implies $b \mathrel{R} a$.

Browsing Math Stack it appears those definitions are standard. Consider the following question: if a nonempty relation is symmetric and transitive, is it also reflexive?

I say yes. But in a discussion with a peer, they provide the example: consider the relation $R$ on $A$ where $A = \{0,1,2\}$ but $R = \{(0,1), (0,2), (1,0), (2,0), (2,1), (1,2)\}$. They claim this relation is transitive but I say no, because in order for it to be so we need $0 \mathrel{R} 1$ and $1 \mathrel{R} 0$ to imply $0 \mathrel{R} 0$, but clearly $(0, 0) \notin R$.

Who's right? And is it possible to generate such a nonempty relation?

  • $\begingroup$ No. Any one of the three is independent of the other two. $\endgroup$ – Brevan Ellefsen Jan 19 at 21:24
  • $\begingroup$ The reflexivity of the relation is here to ensure that any element is in relation with another one. It makes perfect sense from a linguistic point of view right ? If someone has relation with no one, then maybe he should no be part of the group. $\endgroup$ – J.F Jan 19 at 21:40

You can produce relation that is both transitive and symetric but not reflexive b considering $R=\{(0,1), (1,0), (1,1), (0,0)\}$ on the set $X=\{0,1,2\}$.

(the problem here is that $(2,2)\not\in R$)

  • 2
    $\begingroup$ Exactly this. Transitivity does not imply that every element of the set belongs to the relation- only reflexivity guarantees this property. $\endgroup$ – LuuBluum Jan 19 at 21:28
  • $\begingroup$ @Ispil 's comment is what answered my question. But let me just make sure. So, just because (w.r.t this answer post) there does not exist some $x \mathrel{R} 2$ does not mean that $R$ is not transitive? And if that is true, doesn't that mean that my definition of transitivity is off "... for all $a, b, c \in A$"? $\endgroup$ – Zduff Jan 19 at 22:14
  • 1
    $\begingroup$ The definition for transitivity is an implication: that if $aRb$ and $bRc$ then $aRc$. If there's no $aRb$ and $bRc$, then the implication is true regardless of the truth of $aRc$. $\endgroup$ – LuuBluum Jan 20 at 5:32

The example by your peer is indeed not transitive, as you pointed out. A correct counterexample would be $\{(0,0),(0,1),(1,0),(1,1)\}$ on the set $\{0,1,2\}$.

More can be said, though. Let $R$ be a transitive symmetric relation on $A$. Then for all $a\in A$ such that $aRb$ for some $b\in A$, we have $aRa$. Indeed, by symmetry $aRb$ and $bRa$ and by transitivity $aRa$.

  • $\begingroup$ Is my definition of transitivity incorrect then, since it states "... for all $a,b,c \in A$"? $\endgroup$ – Zduff Jan 19 at 22:16
  • $\begingroup$ I don't understand why you suddenly think your definition is incorrect. $\endgroup$ – SmileyCraft Jan 19 at 22:17
  • $\begingroup$ I don't understand why you think the thought was "sudden". $\endgroup$ – Zduff Jan 19 at 23:17

a) your peer is incorrect with their example, as also stated by you and SmileyCraft, because $(0,0)\notin R$.

generalizing the example given by GF.:

b) still, not every binary symmetric relation $R$ on $A$ that is symmetric and transitive is also reflexive. The relation $R$ would be reflexive if $(X,X)\in R$ for all $X\in A$. Symmetry and transitivity only guarantee that IF $(X,Y) \in R$ for a given $X\in A$ THEN also $(Y,X) \in R$ by symmetry and $(X,X) \in R$ by transitivity. However, there can be some $X\in A$ for which there is no $(X,Y) \in R$ or $(Y,X) \in R$ for any $Y\in A$.

symmetry, transitivity and reflexivity together are the defining properties of an equivalence class.


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.