Skip to main content

Section 2.6 Equivalence Relations

In this section we will talk about relations. A relation, loosely speaking, is a way two things are connected to each other, and there are many different ways that things can be related. The relation “=” is an example, two things are related via “=” if they are actually equal. Another example is the relationship that one number is at most another, and we write \(a\leq b\) when we want to say \(a\) and \(b\) are related in this way. A less mathematical example is the relation “daughter of,” so for example “\(a\) is the daughter of \(b\text{,}\)” let's denote this relationship by \(a\sim b\text{.}\)

Now we give a precise definition of a relation.

Definition 2.6.1.

A relation \(R\) on a set \(S\) is just a subset of \(S\times S\text{.}\) Given \(a,b\in S\text{,}\) we write \(aRb\) if \((a,b)\in R\text{.}\)

This may seem like a strange way of defining relations, but this definition encapsulates what we do when we define a relation: a relation is a specific way of pairing up elements of a set. In the earlier example, the daughter-of relation is the set of all pairs of people \((a,b)\) where \(a\) is the daughter of \(b\text{.}\) Another familiar example is \(\leq\text{:}\) we declare \(a\leq b\) if the pair \((a,b)\) is among the set of pairs where \(a\) is at most \(b\text{.}\)

Below we mention some important properties relations can have:

Definition 2.6.2.

Let \(S\) be a set. Let \(\sim\) be a relation on \(S\text{.}\) We say \(\sim\) is

  • reflexive if \(a\sim a\) for all \(a\in S\text{,}\)

  • symmetric if for all \(a\) and \(b\) in \(S\text{,}\) we have \(a\sim b \Longleftrightarrow b\sim a\text{,}\) and

  • transitive if for all \(a\text{,}\) \(b\text{,}\) \(c\) in \(S\text{,}\) we have

    \begin{equation*} a\sim b\sim c\Longrightarrow a\sim c\text{.} \end{equation*}

If \(\sim\) satisfies all three of these properties, we say \(\sim\) is an equivalence relation.

The relations we discussed earlier satisfy different combinations of these properties.

\item Equality is an equivalence relation. We also showed last week that \(\equiv \mod m\) is an equivalence relation. \item \(\leq\) is reflexive and transitive but not symmetric (\(1\leq 2\) but \(2\not\leq 1\)). \item The daughter-of relation \(\sim\) is not symmetric: if \(a\) is the daughter of \(b\text{,}\) then \(b\) is certainly not the daughter of \(a\text{,}\) and it is certainly not reflexive since no one is the daughter of themselves. Also,and the daughter-of relation is not transitive (if \(a\) is the daughter of \(b\) and \(b\) is the daughter of \(c\text{,}\) that does not mean \(a\) is the daughter of \(c\)).

The moral here is that a relation does not necessarily satisfy all or any of the three properties above. So whenever we define a relation, we need to check these properties carefully.

Note 2.6.4. Disproving properties.

Remember that to disprove a statement like \(\forall x\;\; P\text{,}\) you want to prove the negation, which is \(\exists x\mbox{ s.t. } \bar{P}\text{.}\) Hence, to disprove a property like symmetry, it suffices to just find one pair \(a\) and \(b\) for which \(a\sim b\) but \(b\not\sim a\text{.}\) In the previous example, clearly \(\leq\) does not satisfy symmetry for more than just the numbers \(1\) and \(2\text{,}\) but to verify that symmetry fails, we only need to show it fails for one pair.

Why care? Relations and equivalence relations come about when there is a collection of objects and you would like to treat many of them as really the same object. Take for example the rational numbers \(\mathbb{Q}\text{,}\) these are the sets of fractions \(\frac{p}{q}\) where \(p\in\mathbb{Z}\) and \(q\in \mathbb{N}\text{.}\) But notice that the notation \(\frac{p}{q}\) is really just an ordered pair, we could have also just written \((p,q)\text{.}\) But we know that several fractions should give the same number, that is \(\frac{2}{1}=\frac{4}{2}\text{.}\) Really what we're doing here is defining an equivalence relation “=” by saying \(\frac{p}{q}=\frac{r}{s}\) if there is an integer \(a\) so that either \((p,q)=(ar,as)\) or \((r,s)=(ap,aq)\text{.}\) We will also see in the next chapter that functions are also relations. You'll see more important examples in future classes.

Definition 2.6.5.

If \(\sim\) is an equivalence relation on a set \(S\) and \(x\in S\text{,}\) the equivalence class of \(x\) is

\begin{equation*} \cl(x) = \{y\in S : x\sim y\}\text{.} \end{equation*}

The set of equivalence classes is the set \(X/{\sim} = \{\cl(x) : x\in S\}\text{.}\) This set comes with a map \(\cl \colon X \to X/{\sim}\text{.}\)

As long as \(X \neq \varnothing\) the map \(\cl\) is a surjection.

Consider the relation on people that \(a\sim b\) if \(a\) and \(b\) were born in the same country. One can check this is an equivalence relation. What if we want to describe the equivalence classes? We could just say “they are the sets \(\cl(x)\) where \(x\) ranges over all people” but this is not helpful in general; this says no more about the relation or what the classes look like than making the same statement about any other relation. A more natural way of describing the equivalence classes is that they are just the sets of people born in a given country, that is, they are the sets \(A_x\) of people born in country \(x\) as \(x\) ranges over all countries.

Note that in the previous example, the relation partitioned people into disjoint groups based on their country of birth. This happens with all equivalence relations.

Consider the equivalence relation on \(\mathbb{Z}\) defined by \(\equiv \mod m\) where \(m\in\mathbb{N}\text{.}\) What are the equivalence classes? If \(x\in \mathbb{Z}\text{,}\) then the equivalence class associated to \(x\) is

\begin{align*} \cl(x) \amp =\{ y\in\mathbb{Z} : x\equiv y \mod m\}\\ \amp = \{y\in\mathbb{Z} : y=x+mj\mbox{ for some integer } j\}\\ \amp = \{x+mj : j\in\mathbb{Z}\}\text{.} \end{align*}

Notice that for each \(x\) there is \(i\in \{0,1,...,m-1\}\) so that \(x\equiv i\mod m\text{,}\) and so \(\cl(x) = \cl(i)\text{.}\) Thus, all equivalence classes are one of

\begin{equation*} \cl(0),\cl(1),...,\cl(m-1) \end{equation*}

that is, they are the sets of arithmetic progressions of the form \(...,i-2m,i-m,i,i+m,i+2m,..\text{.}\) for some \(i\in \{0,1...,m-1\}\text{.}\) Observe that \(i \mapsto \cl(i)\) defines a bijection from \(\Z/m = \{0,1,\dots,m\}\) to the set \(\{\cl(0),\dots,\cl(m-1)\}\text{.}\) In this way, we think of \(\Z/m\) as the “set of integers, modulo \(m\text{.}\)”