Blogs, Mathematical Reasoning, MR Study Help

Equivalence Relations and Partitions

As we continue to look at proof, we will be working on showing that sets have different types properties. In this case, we will be showing that a given relation is an equivalence relation, but in other posts, we will be looking at different properties.

Equivalence

Here we let \(R=\left\{(x,y) \in \mathbb{R} \times \mathbb{R}: x-y \in \mathbb{Z}\right\}\). We will show that \(R\) is an equivalence relation. After this, we will find the partition created by the equivalence classes of \(R\). In order to do this, we need to show that the relation satisfies the following properties,

  1. Reflexive, for all \(a \in \mathbb{R}\), we have \(a \mathrel{R} a\).
  2. Symmetric, for all \(a,b \in \mathbb{R}\), if \(a \mathrel{R} b\), then \(b \mathrel{R} a\).
  3. Transitive, for all \(a,b,c \in \mathbb{R}\), if \(a \mathrel{R} b\) and \(b \mathrel{R} c\), then \(a \mathrel{R} c\).

We will, therefore, focus on one of these at a time.

Reflexive

In order to show that the relation \(R\) is reflexive, we have to show that every element in \(\mathbb{R}\) is related to itself. That is we need to show that,

  • \(a \mathrel{R} a\),
  • \((a,a) \in \mathbb{R} \times \mathbb{R}\) and \(a-a \in \mathbb{Z}\).

Now that we’ve written out what we need to show, there isn’t much left to do. We know that \((a,a) \in \mathbb{R} \times \mathbb{R}\) since \(a \in \mathbb{R}\). Furthermore \(a-a=0\), so \(a-a \in \mathbb{R}\). The formal proof that \(R\) is reflexive would be,

Proof

Let \(a \in \mathbb{R}\). Then note that \((a,a) \in \mathbb{R}\times \mathbb{R}\) since \(a \in \mathbb{R}\). Furthermore, \(a-a=0 \in \mathbb{Z}\). Hence \(a \mathrel{R} a\), so \(R\) is reflexive.

Symmetric

In order to show that the relation \(R\) is symmetric, we need to show that if \(a \mathrel{R} b\), then \(b \mathrel{R} a\). That is,

  • We suppose that \((a,b) \in R\). That is, \((a,b) \in \mathbb{R} \times \mathbb{R}\) and \(a-b \in \mathbb{Z}\).
  • That is \(a-b=k\) for some \(k \in \mathbb{Z}\).
  • We need to show that \((b,a) \in \mathbb{R} \times \mathbb{R}\) and \(b-a \in \mathbb{Z}\).
  • We note that \(a-b=k\), then \(b-a=-(a-b)=-k \in \mathbb{Z}\).

We are now ready to combine this together to get our proof.

Proof

Let \(a,b \in \mathbb{R}\) with \(a \mathrel{R} b\). We then know that \((b,a) \in \mathbb{R} \times \mathbb{R}\) since \(a,b \in \mathbb{R}\). Furthermore, \(a-b \in \mathbb{Z}\), so let \(a-b=k\) where \(k \in \mathbb{Z}\). We then have that \(b-a=-(a-b)=-k \in \mathbb{Z}\) since integers are closed under multiplication and \(-1,k \in \mathbb{Z}\). Hence \(b \mathrel{R} a\), so \(R\) is a symmetric relation.

Transitive

In order to show that \(R\) is a transitive relation, we have to show that if \(a \mathrel{R} b\) and \(b \mathrel{R} c\), then \(a \mathrel{R} c\). That is, suppose that \(a,b,c \in \mathbb{R}\), we have

  • Let \(a \mathrel{R} b\) and \(b \mathrel{R} c\).
  • That is, \((a,b) \in \mathbb{R} \times \mathbb{R}\) and \(a-b \in \mathbb{Z}\) and \((b,c) \in \mathbb{R} \times \mathbb{R}\) and \(b-c \in \mathbb{Z}\).
  • That is, \(a-b=k_{1}\) and \(b-c=k_{2}\) for \(k_{1}, k_{2} \in \mathbb{Z}\).
  • We need to show that \(a \mathrel{R} c\).
  • That is, we need \((a,c) \in \mathbb{R} \times \mathbb{R}\) and \(a-c \in \mathbb{Z}\).
  • Note that \(a-c=a-b+b-c=k_{1}+k_{2} \in \mathbb{Z}\).

We are now ready to give our proof.

Proof

Let \(a,b,c \in \mathbb{R}\), \(a \mathrel{R} b\) and \(b \mathrel{R} c\). We then have that \((a,c) \in \mathbb{R} \times \mathbb{R}\) since \(a,c \in \mathbb{R}\). We, furthermore, have that \(a-b=k_{1}\) and \(b-c=k_{2}\) for some integers \(k_{1}\) and \(k_{2}\). Therefore, \(a-c=a-b+b-c=k_{1}+k_{2}\). Since the integers are closed under addition, we have that \(a-c\) is also an integer. Hence \(a \mathrel{R} c\) and \(R\) is a transitive relation.

Combining these

We have now proving that \(\mathrel{R}\) is a reflexive, symmetric and transitive relation. Therefore it is an equivalence relation. Next, we will need to find the equivalence classes.

Equivalence classes

In order to find the equivalence classes, we want to determine some type of definable relation determining when things are related. In this case, we know that \(a \mathrel{R} b\) if \(a-b \in \mathbb{Z}\). Therefore, \(a \mathrel{R} a+k\) for any integer \(k\). As such, we get that the equivalence class of \(a\) is,
\begin{align*}
[a]=\left\{x \in \mathbb{R}: x=a+k \text{ for some } k \in \mathbb{Z}\right\}.
\end{align*}

Now that we know what each equivalence class looks like, we want to determine what the distinct equivalence classes would look like. Note that, if we add 1 to any number, we end up with an equivalent number. Furthermore, 1 is the smallest non-zero number that we can add that would result in an equivalent element. As such, we would know that all the number in \([0,1)\) would represent distinct equivalence classes, because none of these numbers differ by 1 or more. Also, for every real number we can subtract off the integer portion and be left with a decimal between 0 and 1, we get that all real numbers would be equivalent to one of these numbers.

Hence, there is a distinct equivalence class for each \(x \in [0,1)\). Therefore, equivalence classes would partition \(\mathbb{R}\) into the sets
\begin{align*}
A_{x}=\left\{y \in \mathbb{R}:y=x+k \text{ for some } k \in \mathbb{Z}\right\}.
\end{align*}
for all \(x \in [0,1)\).

Conclusion

In this situation we wanted to show that a given relation was an equivalence relation. This meant showing that the relation satisfied three distinct properties. Instead of trying to do everything at once, we broke the problem up and looked at each property individually. Once we knew that we had an equivalence relation, we were able to find the equivalence classes and determine how these would partition the real numbers.

For more help with proofs, make sure to continue working on the other problems we have posted solutions for in Study Help. If you find these helpful, make sure to let other people know about them so that they can get help as well.

1 thought on “Equivalence Relations and Partitions”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.