Exercise · ZW-EQUIVALENCE-RELATION-010 · ★★★ Advanced
Is every symmetric and transitive relation on \(A\) an equivalence relation ?
Choose one option.
A Yes, because every symmetric and transitive relation is reflexive B Yes, if \(A\) has at least two elements C No: \(R=\{(1,1)\}\) on \(\{1,2\}\) is symmetric and transitive but not reflexive, because \((2,2)\notin R\) D No: equality is not symmetric Show answer C. No: \(R=\{(1,1)\}\) on \(\{1,2\}\) is symmetric and transitive but not reflexive, because \((2,2)\notin R\)← Back to the question
Explanation Reflexivity does not follow from the other two. On \(\{1,2\}\), the relation \(\{(1,1)\}\) has no chains that violate symmetry or transitivity, yet \(2\) is not related to itself.
A binary relation \(R\) on \(A\) that is reflexive, symmetric and transitive. It groups the elements of \(A\) that behave alike with respect to some property.
\[\forall a\in A\,(a\,R\,a)\ \wedge\ \forall a,b\in A\,(aRb \Rightarrow bRa)\ \wedge\\ \forall a,b,c\in A\,(aRb\wedge bRc\Rightarrow aRc)\]
More practice problems: equivalence relation ZW-EQUIVALENCE-RELATION-001 Which three properties must a relation R on A satisfy to be an equivalence relation?ZW-EQUIVALENCE-RELATION-002 What does it mean for R to be symmetric?ZW-EQUIVALENCE-RELATION-003 What does reflexivity require?ZW-EQUIVALENCE-RELATION-004 What does transitivity require?ZW-EQUIVALENCE-RELATION-005 Is equality = on a set A an equivalence relation?ZW-EQUIVALENCE-RELATION-006 Let A=\1,2,3,4\ and R=\(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)\. Is R an equivalence relation?ZW-EQUIVALENCE-RELATION-007 On ℤ, let a R b if a-b is even. Is R an equivalence relation?ZW-EQUIVALENCE-RELATION-008 On ℤ, let a R b if a≤ b. Is R an equivalence relation?