Relations and functions · Definition

Equivalence class

set theoryrelations and functions

Before you start you need to know

An equivalence class gathers into a single block the elements that an equivalence relation regards as equal.

Definition

Given an equivalence relation \(R\) on \(A\) and an element \(a\in A\), the equivalence class \([a]\) is the set of all \(x\in A\) with \(x\,R\,a\).

\[[a]=\{x\in A : x\,R\,a\}\]

Equivalence classes form a partition of \(A\): every element belongs to some class, and two classes are either equal or disjoint. Moreover, \(x\in[a]\) if and only if \([x]=[a]\). That is why the set of classes \(A/R\), called the quotient set, counts the ways of being equal without repetition.

Worked example: on \(A=\{1,2,3,4,5,6\}\), the relation «has the same parity as» has two classes, \([1]=\{1,3,5\}\) and \([2]=\{2,4,6\}\). So \(A/R\) has 2 elements, even though \(A\) has 6.

Typical mistake: reading \([a]\) as if it were the element \(a\). The class is a subset of \(A\), and the same class can be named with different representatives: \([1]=[3]=[5]\) in the example above.

Think about it

Can two distinct equivalence classes share elements?

No: two classes are either equal or disjoint.

Exercises 10

  1. What is the equivalence class \([a]\)?
  2. What is the quotient set \(A/R\)?
  3. Does \(a\) belong to its own class \([a]\)?
  4. On \(\{1,2,3,4,5,6\}\) with the relation «same parity», how many equivalence classes are there?
  5. If \(x\in[a]\), what holds?
  6. On \(\mathbb{Z}\), let \(a\,R\,b\) if \(a-b\) is a multiple of 3. What is \([0]\)?
  7. On \(\mathbb{Z}\), let \(a\,R\,b\) if \(a\) and \(b\) leave the same remainder when divided by 3. How many equivalence classes are there?
  8. Let \(A=\{1,2,3,4\}\) and \(R\) an equivalence relation with classes \(\{1,2\}\) and \(\{3,4\}\). What is \([2]\)?
  9. On \(A=\{a,b,c\}\), the equivalence relation is equality. How many classes are there?
  10. If \([a]\cap[b]\neq\varnothing\), what holds?

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.