0
$\begingroup$

Let $R$ be a relation, $R: A\rightarrow A$ where $R$ is both symmetric and transitive. Then prove or disprove the following:

($\forall x \in A \ \exists y \in A: \ (xRy)) \rightarrow$ ($R$ is an equivalence relation).

To be an equivalence relation, $R$ must be reflexive, symmetric, and transitive. We are given that $R$ is symmetric and transitive, but do not know if it is reflexive.

Since $R$ is symmetric, we can also say: if ($\forall y \in A \ \exists x \in A$ such that $yRx$) -- right?

And since $R$ is transitive, we can also say: $\forall x, y, z \in A$, if $(xRy \land yRz) \to xRz$.

However, this leaves us with insufficient evidence that R is reflexive, thus we can't prove that it is an equivalence relation.

I'm stuck.

$\endgroup$
  • $\begingroup$ You might want to clarify whether you have been explicitly given as part of the problem that $R$ is symmetric and transitive, or whether you were inferring that from the statement of the problem you give in your first paragraph. You might also wish to enclose math expressions in dollar signs. This allows you to use \in within the dollar signs to get $\in$ and will make your question much more pleasant to read. $\endgroup$ – C Monsour Apr 20 '18 at 23:55
  • $\begingroup$ Finally, if you can't prove that $R$ is an equivalence relationship, you probably want to change gears and attempt to disprove it by constructing a counterexample. $\endgroup$ – C Monsour Apr 20 '18 at 23:56
  • $\begingroup$ As a reminder, in the statement of transitivity that if $x,y,z\in A$ and if $xRy$ and $yRz$ then $xRz$.... remember that $x,y,z$ do not need to be distinct. It could be the case that they all refer to the same element, or as is specifically useful for this specific example that the first and third elements refer to the same element. $\endgroup$ – JMoravitz Apr 21 '18 at 0:01
2
$\begingroup$

Let $\;a\in A\;$ . Then there exists $\;y\in A\;$ s.t. $\;aRy\;$ , but then also $\;yRa\;$ , and since the relation is transitive

$$aRy\;\;\text{and}\;\;yRa\;\implies aRa$$

and the relation is reflexive.

$\endgroup$

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.