I have seen a proof that every relation which is symmetric and transitive is also reflexive.

if $A=\{1,2,3\}$ Then if $R=\{(1,2)(2,1)(1,1)\color{blue}{(2,2)}\}$

here $R$ is symmetric and transitive on $A$ but not reflexive right?

Can anyone clear up this confusion for me?

  • $\begingroup$ Is $(3,3)$ in it? Or $(2,2)$? This also shows it's not transitive. $\endgroup$ – user223391 Jul 5 '16 at 16:32
  • $\begingroup$ yes its not there so it is not reflexive...that is my confusion $\endgroup$ – Umesh shankar Jul 5 '16 at 16:33
  • $\begingroup$ What's your confusion? It's not reflexive, you're right. It's also not transitive. $\endgroup$ – user223391 Jul 5 '16 at 16:35
  • 1
    $\begingroup$ You may find this question of interest $\endgroup$ – MPW Jul 5 '16 at 16:35
  • 1
    $\begingroup$ What IS your question? $\endgroup$ – user223391 Jul 5 '16 at 16:39

Every relation that is transitive and symmetric is reflexive on its domain, where the domain $dom(R)$ of a relation $R$ is $$ dom(R) := \{x \mid \exists y\, xRy \} $$ (and where, as usual, $xRy$ means $(x,y) \in R$). This is easy to show: if $x\in dom(R)$, then $xRy$ for some $y$, so $yRx$ by symmetry, and then $xRx$ by transitivity.

The domain of the relation $R$ that you exhibit is just $\{1,2\}$, not all of $A = \{1,2,3\}$.

  • $\begingroup$ ok it is pretty clear now $\endgroup$ – Umesh shankar Jul 5 '16 at 16:41
  • $\begingroup$ so finally does it mean that if a Relation R from Set $A$ to $A$ is symmetric and transitive then it is reflexive if $Dom(R)=A$ $\endgroup$ – Umesh shankar Jul 5 '16 at 16:52
  • 1
    $\begingroup$ @Umeshshankar Yes, exactly. $\endgroup$ – BrianO Jul 5 '16 at 19:27

Foremost, this relation you defined is not transitive because of the following: $2 \sim 1, 1 \sim 2$, but $2$ is not equivalent to $2$, which should be the case under transitivity.

Secondly, every relation that is symmetric and transitive is not necessarily reflexive. Generally the (false) proof proceeds as follows:

$a\sim b$, so then by symmetry $b\sim a$, then by transitivity, $a \sim a$.

However, this argument is based on the fact that $\exists \, b $ such that $a\sim b$, which does not have to be the case.

Consider the relation: $A = \{1, 2, 3\}, R = \{(1,2), (2, 1), (1, 1), (2, 2)\}$. It is symmetric and transitive but not reflexive. Note that there is no such element $b$ where $3 \sim b$.

  • 4
    $\begingroup$ A small quibble: the argument doesn't require that $b \ne a$, just that some $b\sim a$ exists at all. $\endgroup$ – Paul Sinclair Jul 5 '16 at 17:01
  • $\begingroup$ Whoops, thank you for pointing that out! I suppose I was thinking there would be no need to prove reflexivity from symmetry and transitivity if it is already known that $ a \sim a$, but it is a mistake on my part. Edited and corrected. $\endgroup$ – Christian Jul 6 '16 at 3:29

if you tack $A=\{1,2,3\}$ and $R=\{(1,2),(1,1),(2,1),(2,2)\}$ then $R$ is both symetric and transitive relation on $A$ but not reflexive because $(3,3)\not\in R$


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.