# Does symmetry and transitivity imply reflexivity for nonempty binary relation?

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?

• No. Any one of the three is independent of the other two. – Brevan Ellefsen Jan 19 at 21:24
• 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. – 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$$)

• Exactly this. Transitivity does not imply that every element of the set belongs to the relation- only reflexivity guarantees this property. – LuuBluum Jan 19 at 21:28
• @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$"? – Zduff Jan 19 at 22:14
• 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$. – 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$$.

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