Equivalence Relations

Equivalence Relation: Definition

Definition: Let \(A\) be a set. A relation \(R\) on \(A\) is called an equivalence relation if it is reflexive, symmetric, and transitive.

Examples

Let \(A=\{-2,-1,1,2,3,4\}\).

  • The relation \(=\) is an equivalence relation.

  • The relation “has the same parity as” is an equivalence relation.

  • The relation “has the same sign as” is an equivalence relation.

  • The relation “has the same sign and parity” is an equivalence relation.

Let \(X\) be the set of books in Babbidge Library with one author. Here are some equivalence relations:

  • Has the same author.

  • Has the same number of pages.

  • Are located on the same floor of the library.

Equivalence Classes

Definition: Let \(A\) be a set and \(R\) a relation on \(A\). For any \(a\in A\), the equivalence class of \(a\) under \(R\), written \([a]\) or \([a]_R\), is the set \[ [a] =\{b\in A : bRa\}. \]

If \(A=\{-2,-1,1,2,3,4\}\) and \(R\) is the relation “has the same parity as” then:

  • \([-2]\) is the set \(\{-2,2,4\}\)
  • \([2]\) is the same set \(\{-2,2,4\}\)
  • \([1]\) is the set \(\{-1,1,3\}\)
  • \([3]\) is the set \(\{-1,1,3\}\)

Equivalence Classes - Examples

If \(X\) is the set of books in Babbidge Library with one author, and \(R\) is the relation “has the same author” then

  • [Ray Bradbury] is the set of books in Babbidge Library with only one author, and that author is Ray Bradbury.

If \(R\) is the relation “has the same number of pages”, then

  • [War and Peace] is the set of books in Babbidge Library (with one author) that have the same number of pages as War and Peace.

Question: why do I insist on books with one author?

Example 11.12 - polynomials

Let \(P\) be the set of polynomials with real coefficients. Define a relation \(R\) on \(P\) by saying that \(fRg\) if \(f\) and \(g\) have the same degree. Then \(R\) is an equivalence relation.

The equivalence class \([x]\) of the polynomial \(x\) consists of all polynomials of degree one.

More generally there is one equivalence class for each degree, and the equivalence class consists of all polynomials of that degree.

Example 11.13 - Congruence

We have seen that \(\equiv\pmod{n}\) is an equivalence relation on \(\mathbb{Z}\).

What are the equivalence classes \([x]\) for \(x\in\mathbb{Z}\)?

Rational numbers

Let \(M\) be the set of pairs \((m,n)\) where \(m\) and \(n\) are integers and \(n\not=0\). Define a relation \((m,n)R(m',n')\) if \(mn'-m'n=0\). What are the equivalence classes?