Relations and functions · Definition

Equivalence relation

set theoryrelations and functions

Before you start you need to know

An equivalence relation formalizes the idea of being equal in some sense among elements of the same set.

Definition

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)\]

Let \(R\) be a relation on \(A\). It is reflexive if \(a\,R\,a\) for all \(a\in A\), symmetric if \(a\,R\,b\) implies \(b\,R\,a\), and transitive if \(a\,R\,b\) and \(b\,R\,c\) imply \(a\,R\,c\). All three properties must hold at once: if any one fails, \(R\) is not an equivalence relation.

Worked example: on \(A=\{1,2,3,4\}\), the relation «has the same parity as» is an equivalence relation. It is reflexive because each number has the same parity as itself, symmetric because sharing parity is mutual, and transitive because if \(a\) and \(b\) share parity, and \(b\) and \(c\) do too, then \(a\) and \(c\) share it. By contrast, \(\le\) is not: it is reflexive and transitive but not symmetric, since \(1\le 2\) while \(2\not\le 1\).

Typical mistake: believing that symmetry and transitivity are enough and that reflexivity follows automatically. If \(a\,R\,b\), symmetry gives \(b\,R\,a\) and transitivity gives \(a\,R\,a\), but only for those \(a\) that appear as a first component of some pair. So reflexivity must be checked separately.

Think about it

To think about: why are symmetry and transitivity not enough to guarantee reflexivity?

Because \(a\,R\,a\) is only obtained for those \(a\) appearing as a first component of some pair; an isolated element may not be related to itself.

Exercises 10

  1. Which three properties must a relation \(R\) on \(A\) satisfy to be an equivalence relation?
  2. What does it mean for \(R\) to be symmetric?
  3. What does reflexivity require?
  4. What does transitivity require?
  5. Is equality \(=\) on a set \(A\) an equivalence relation?
  6. 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?
  7. On \(\mathbb{Z}\), let \(a\,R\,b\) if \(a-b\) is even. Is \(R\) an equivalence relation?
  8. On \(\mathbb{Z}\), let \(a\,R\,b\) if \(a\le b\). Is \(R\) an equivalence relation?
  9. On \(A=\{a,b,c\}\), which of these relations is an equivalence relation?
  10. Is every symmetric and transitive relation on \(A\) an equivalence relation?

What comes next

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.