1
$\begingroup$

I'm stuck at one particular task I'm working on.

Here is the task:

Let R be a transitive and symmetrical relation on $S$. Assume that for all $x \in S$ there is a $y \in S$ so that $xRy$. Prove that $R$ is an equivalence relation.

How can I prove that $R$ is an equivalence relation?

I would appreciate any help.

Thank you.

$\endgroup$
  • 2
    $\begingroup$ Because you are given that $R$ is transitive and symmetric you need only show it is reflexive per the definition of equivalence relation. You know this correct? If so, please state it in your question so people know where you are with the solution. $\endgroup$ – Jeremy Upsal Nov 11 '13 at 18:30
  • 1
    $\begingroup$ Possible duplicate math.stackexchange.com/questions/65102/…. If not, @Dabbish should take a look at the solution given here. $\endgroup$ – Jeremy Upsal Nov 11 '13 at 18:32
2
$\begingroup$

All you need to do here is make the case that $R$ must be reflexive. Since for every $a \in S$ there is $b,$ such that $aRb,$ then by symmetry $bRa$ and by transitivity $aRa.$ Since this holds for every $a\in S$, the relation is necessarily reflexive, and hence, is an equivalence relation.

$\endgroup$
1
$\begingroup$

We know $xRy$. Since it is symmetric $yRx$. Thus $xRy$ and $yRx$ so by transitivity $xRx$. Thus the relation is also reflexive show that it is an equivalence relation.

$\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.