1
$\begingroup$

Question:

Let $R$ be the relation $\{(1,1),(2,3),(2,2),(3,2),(3,3)\}$ on the set $S=\{1,2,3\}$. Is $R$ an equivalence relation? If $R$ is, describe the partition $\mathscr{P}$ determined by $R$ by listing the pieces in $\mathscr{P}$.

Attempt:

$R$ is reflexive since for all $s\in S$ we have that $sRs$. $R$ is symmetric since each pair $(x,y)\in R$ we have that $(y,x)\in R$ also, namely for all $s,s'\in S$ we have that $sRs'\implies s'Rs$. Lastly, and this is what I'm not sure of, $R$ is transitive because the subgraphs $G_1$ and $G_{2,3}$ of the graph $G$ (see below) are Eulerian:

enter image description here

$\endgroup$
2
  • $\begingroup$ How is it that the partition is $\mathscr{P}=\{\{1\},\{2,3\}\}$? $\endgroup$ – Secure Space Sep 12 '13 at 1:30
  • $\begingroup$ Does partition just mean disjoint networks? $\endgroup$ – Secure Space Sep 12 '13 at 2:48
1
$\begingroup$

Except the proof of the transitivity, all you proof are correct. But Eulerness of the relation graph is not a sufficient conditon of transitivity of the relation, as shows a relation $\{(1,2), (2,3),(3,1)\}$ on the same set $S$.

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