0
$\begingroup$

Let R be a relation on a given nonempty set A. State the necessary and sufficient condition for R to be an equivalence relation on A.

My attempt

The conditions for any equivalence relation are Transitivity, Symmetric and Reflexive.

Reflexive : For all elements $x\in A$, $xRx$. Therefore, this is a necessary condition.

Symmetric : If $aRb$, then $bRa$. Since this is conditional, it should be a sufficient condition.

Transitivity : If $aRb$ and $bRc$, then $aRc$. Since this is conditional, it should be a sufficient condition.

Am I correct?

$\endgroup$
  • 1
    $\begingroup$ This is the definition of an equivalence relation, rather than a "necessary and sufficient" condition. Is there more context to the exercise ? $\endgroup$ – beauby Nov 15 '12 at 6:07
  • $\begingroup$ Suppose transitivity was a sufficient condition. Then if a relation is transitive, it is an equivalence relation. The relation "is taller than" is transitive: if Jim is taller than Bob and Bob is taller than Frank then Jim is taller than Frank. It is not, however, reflexive, which you've claimed is a necessary condition. Contradiction. We have a problem. $\endgroup$ – crf Nov 15 '12 at 6:08
  • $\begingroup$ Incidentally, I'm not sure that your distinction between conditional and unconditional statements makes very much sense. $\endgroup$ – crf Nov 15 '12 at 6:09
  • $\begingroup$ I copied the question as it exactly was. it was a finals question, and no extra context. $\endgroup$ – Yellow Skies Nov 15 '12 at 6:09
  • $\begingroup$ @SingaporeanDude. Well, for $R$ to be reflexive, symmetric and transitive is, strictly speaking, necessary and sufficient for it to be an equivalence relation, but I find the wording a bit weird. $\endgroup$ – beauby Nov 15 '12 at 6:10
2
$\begingroup$

A definition provides a condition which is both necessary and sufficient. So when we write,

Definition. An equivalence relation on a nonempty set is a relation which is reflexive, symmetric, and transitive.

We are saying that this is a single condition which is both necessary and sufficient for a relation to be considered an equivalence relation. We can break it up into three different conditions if we like, each of which would also be both necessary and sufficient.

$\endgroup$
  • $\begingroup$ I guess you are right.. That must be a poorly worded question. To think it came out in such a major test. $\endgroup$ – Yellow Skies Nov 15 '12 at 6:15
  • $\begingroup$ Well, I mean, it's not false to say "the necessary and sufficient condition for a relation to be an equivalence relation is that it satisfies reflexivity, symmetry, and transitivity". But it is a strangely worded question—I would usually just ask for "the definition". $\endgroup$ – crf Nov 15 '12 at 6:17

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.