\documentclass{article}
\usepackage{amsmath}
\usepackage{amsthm}

\newtheorem{thm}{Theorem}

\title{Equivalence Relations}
\author{Doug Baldwin}
\date{Spring 2021}


\begin{document}

\maketitle

Let $\sim$ be the relation on the integers whereby $a \sim b$ if and only if $a - b = 3k$ for some integer $k$ (i.e., $a-b$ is divisible by  3).

\begin{thm}
Relation $\sim$ as defined above is an equivalence relation.
\end{thm}

\begin{proof}
We will prove that $\sim$ is an equivalence relation by showing that it is reflexive, symmetric, and transitive.

To show that $\sim$ is reflexive, we need to show that $a \sim a$ for all integers $a$. So let $a$ be an integer. Then $a - a = 0 = 3 \times 0$ so $a \sim a$. Thus $\sim$ is reflexive.

To show that $\sim$ is symmetric, suppose $a$ and $b$ are integers and $a \sim b$, i.e., $a - b = 3k$ for some integer $k$. Then $b - a = -3k = 3(-k)$. Since $k$ is an integer, so is $-k$, and thus $b - a$ is divisible by 3 and so $b \sim a$. We have now shown that $\sim$ is symmetric.

To show that $\sim$ is transitive, let $a$, $b$, and $c$ be integers such that $a \sim b$ and $b \sim c$. Thus $a - b = 3k$ for some integer $k$ and $b - c = 3n$ for some integer $n$. Now
\begin{align*}
(a-b) + (b-c) &= 3k + 3n \\
a - c &= 3(k+n)
\end{align*}
Since integers are closed under addition, we have shown that $a - c$ is divisible by 3, and so $a \sim c$. Therefore $\sim$ is transitive.

We have now shown that $\sim$ is reflexive, symmetric, and transitive, and therefore that $\sim$ as defined above is an equivalence relation.
\end{proof}
\end{document}