7.2 Workshop 2 (Reading)

To show that congruence modulo $m$ is an equivalence relation, we need to show it is reflexive, symmetric and transitive.

First we show that $a=b\mod m$ is reflexive. Take any integer $x\in\mathbb{Z}$, and observe that $m|0$, so $m|(x-x)$ for any $m$. By definition of congruence modulo $m$, we have $x=x\mod m$. This shows $x=x\mod m$ for every $x\in\mathbb{Z}$, so $a=b\mod m$ is reflexive.

Next, we will show that $a=b\mod m$ is symmetric. For this, we must show that for all $x,y\in\mathbb{Z}$, the condition $x=y\mod m$ implies that $y=x\mod m$. We use a direct proof. Suppose $x=y\mod m$. Thus $m|(x-y)$ by definition of congruence modulo $m$. Then $x-y=ma$ for some $a\in\mathbb{Z}$ by definition of divisibility. Multiplying both sides by $-1$ gives $y-x=m(-a)$. Therefore $m|(y-x)$, and this means $y=x\mod m$. We’ve shown that $x=y\mod m$ implies that $y=x\mod m$, and this means $a=b\mod m$ is symmetric.

Finally we will show that $a=b\mod m$ is transitive. For this we must show that if $x=y\mod m$ and $y=z\mod m$, then $x=z\mod m$. Again, we use direct proof. Suppose $x=y\mod m$ and $y=z\mod m$. This means $m|(x-y)$ and $m|(y-z)$. Therefore there are integers $a$ and $b$ for which $x-y=ma$ and $y-z=mb$. Therefore, we obtain $(x-y)+(y-z)=x-z=ma+mb$. Consequently, $x-z=m(a+b)$ with $a+b\in\mathbb{Z}$, and so $m|(x-z)$. Hence $x=z\mod m$. This completes the proof that congruence modulo $m$ is transitive.

We have shown that congruence modulo $m$ is reflexive, symmetric and transitive, and hence an equivalence relation.

Recall that a bijective function is both surjective and injective.

• •
  ​

  To show $\sim$ is reflexive, consider the identity function $id_{A}:A\to A$ where $id_{A}(a)=a$ for all $a\in A$. This is a bijective function. Indeed, $id_{A}(a)=id_{A}(b)$ implies $a=b$ for all $a,b\in A$ immediately from the definition of $id_{A}$ so this function is injective. It is also surjective since $y=id_{A}(y)$ for all $y\in A$.

• •
  ​

  For $\sim$ to be symmetric, recall that bijective functions are invertible. Therefore, if $A\sim B$, then there exists a bijection $f:A\to B$. As this is a bijection, there exists $f^{-1}:B\to A$ which is also a bijection meaning $B\sim A$ so $\sim$ is symmetric.

• •
  ​

  For transitivity, recall that the composition of bijective functions is a bijection by Proposition 6.47 so if $A\sim B$ and $B\sim C$, then there exist bijections $f:A\to B$ and $g:B\to C$. Consider $g\circ f:A\to C$. As both $f$ and $g$ are bijections, then $g\circ f$ is also a bijection so $A\sim C$.

We have shown that $\sim$ is reflexive, symmetric and transitive meaning it is an equivalence relation.

Let $\sim$ be a relation over a set $X$.

We first assume that $\sim$ is an equivalence relation and aim to show that it is reflexive and cyclic.

Since $\sim$ is an equivalence relation, we know that $\sim$ is reflexive, symmetric, and transitive. Consequently, $\sim$ is reflexive, so we just need to show that $\sim$ is cyclic.

To prove that $\sim$ is cyclic, let $a,b,c\in X$ where $a\sim b$ and $b\sim c$. We need to show that $c\sim a$. As $a\sim b$ and $b\sim c$ and since $\sim$ is transitive, $a\sim c$. Then, since $\sim$ is symmetric, we see that $c\sim a$, which is what we needed to prove.

Hence, if $\sim$ is an equivalence relation, it is reflexive and cyclic.

On the other hand, assuming $\sim$ is reflexive and cyclic, we can prove that $\sim$ is an equivalence relation. We need to show that $\sim$ is reflexive, symmetric, and transitive. Since we already know by assumption that $\sim$ is reflexive, we just need to show that $\sim$ is symmetric and transitive.

First, we prove that $\sim$ is symmetric. To do so, consider any arbitrary $a,b\in X$ where $a\sim b$ holds. Since $\sim$ is reflexive, we know that $a\sim a$. Therefore, by cyclicity, since $a\sim a$ and $a\sim b$, we learn that $b\sim a$ meaning $\sim$ is symmetric.

Finally, we prove that $\sim$ is transitive. Let $a,b$, and $c$ be any elements of $X$ where $a\sim b$ and $b\sim c$. We need to prove that $a\sim c$. Since $\sim$ is cyclic, from $a\sim b$ and $b\sim c$ we see that $c\sim a$. We’ve already proven $\sim$ is symmetric so we also have $a\sim c$ and so $\sim$ is transitive.

Overall, we have shown that $\sim$ is cyclic and reflexive if and only if it is an equivalence relation.

We first show that $\sim$ is reflexive i.e. …for every $x\in F$. So suppose $x\in F$. Then there exist $a,b\in\mathbb{Z}$ with $b\neq 0$ such that …. Then …since $a,b\in\mathbb{Z}$. So …and thus, $\sim$ is reflexive.

Next we show that $\sim$ is symmetric. So we need to prove that …for every $x,y\in F$. So suppose $x,y\in F$ such that …. Then there exist …where $b,d\neq 0$ such that $x=(a,b)$ and $y=(c,d)$. Since …, we have $(a,b)\sim(c,d)$ and thus …. This means that …. Therefore …and thus $y\sim x$, which proves that $\sim$ is symmetric.

Finally, to show that $\sim$ is transitive, we need to prove that …for all $x,y,z\in F$. So suppose that $x,y,z\in F$ such that …. Then there exist $a,b,c,d,e,f\in\mathbb{Z}$ where …such that $x=(a,b)$, $y=(c,d)$ and $z=(e,f)$. Since $x\sim y$ and $y\sim z$, we have …. This means that …. Thus, …, since $f\neq 0$. Hence,

since $d\neq 0$. Thus, $(a,b)\sim(e,f)$ which means that …. Hence, $\sim$ is transitive.

Having shown that $\sim$ is …, we’ve therefore shown $\sim$ is an equivalence relation on $F$.

(The lines of this proof are numbered to aid your discussion.)

1. (a)
   1. 1.
      ​

      Let $x\in X$. As $\sim$ is an equivalence relation on $X$, then by reflexivity, we necessarily have that $x\sim x$. Therefore $x\in[x]$ by the definition of an equivalence class.

2. (b)
   1. 1.
      ​

      We first show that if $x\sim y$, then $[x]=[y]$. We are therefore showing that two sets are equal so we need to show that $[x]\subseteq[y]$ and vice versa.

   2. 2.
      ​

      Let $a\in[x]$. Then $x\sim a$ by the definition of an equivalence class. By assumption $x\sim y$ and, by the transitivity and symmetry of $\sim$, we therefore have $y\sim a$ so $a\in[y]$. Therefore $[x]\subseteq[y]$

   3. 3.
      ​

      Similarly, if $b\in[y]$, then $y\sim b$ and, by transitivity with $x\sim y$, $x\sim b$ so $b\in[x]$ and $[y]\subseteq[x]$.

   4. 4.
      ​

      We have then shown that if $x\sim y$, then $[x]=[y]$. On the other hand, we assume $[x]=[y]$ and show that $x\sim y$.

   5. 5.
      ​

      By (a), we have that $x\in[x]$ so, as $[x]=[y]$, we have that $x\in[y]$. By definition, this means $x\sim y$.

   6. 6.
      ​

      This completes the proof for (b).

3. (c)
   1. 1.
      ​

      Consider the set $[x]\cap[y]$.

   2. 2.
      ​

      Case 1: $[x]\cap[y]$ is non-empty.

   3. 3.
      ​

      This means there is an element $a\in X$ such that $a\in[x]$ and $a\in[y]$. As $a\in[x]$, then $x\sim a$ so, by (b), $[x]=[a]$. Similarly, $[y]=[a]$. Hence, $[x]=[y]$.

   4. 4.
      ​

      Case 2: $[x]\cap[y]$ is empty.

   5. 5.
   6. 6.
      ​

      As the intersection must be either empty or non-empty, we have covered all possible cases and hence, we must have either $[x]=[y]$ or $[x]\cap[y]=\emptyset$.