Question

3. Prove or give a counterexample to the following: For a set A and
binary relation R on A, if R is reflexive and symmetric, then R must
be transitive as well.

Answer 1

Answer provided by https://www.AssignmentExpert.com

Answer on Question #76224 – Math – Discrete Mathematics

Question

Prove or give a counterexample to the following: For a set $A$ and binary relation $R$ on $A$, if $R$ is reflexive and symmetric, then $R$ must be transitive as well.

Solution

This statement is not true.

Consider the set $A = \{a, b, c\}$ and the binary relation

$$R = \{(a, a), (b, b), (c, c), (a, b), (b, a), (b, c), (c, b)\}$$

on $A$. Then $R$ is reflexive because $(a, a), (b, b), (c, c) \in R$, i.e. $(x, x) \in R$ for all $x \in A$. This relation is symmetric because if $(x, y) \in R$ then $(y, x) \in R$ for each $x, y \in A$. But $R$ is not transitive: $(a, b) \in R$ and $(b, c) \in R$ but $(a, c) \notin R$.

**Answer**: $R$ is not transitive.