Proofs and Equality of Equivalence Classes

Courses in Number Theory require students to prove various theorems. In some cases, as you construct your proof you will find that you need to show that two equivalence classes are the same. In these cases it is useful to remember the relation that is involved. If two elements are related then these elements belong to the same equivalence class.

Consider the following proof exercise:

Show that $x+0=0$ for every $x \epsilon  \mathbb{Z}$

Proof:

Let $x = [a,b]$ and recall that $0 = [1,1]$.

Recall the definition of integer addition i.e. $[r,s] + [t,u] = [r+t, s+u]$.

So,  $x + 0 = [a, b] + [1, 1] = [a+1, b+1]$.

We need to show that $[a+1, b+1]  = [a,b]$.

Recall that  $\mathbb{Z}$ is the set of equivalence classes of R where R is the relation on $\mathbb{X}$ such that $(a,b)R(c,d)$ means $a+d=b+c$ and $\mathbb{X}$ is the set of ordered pairs $(a,b)$ of natural numbers.

$(a+1,b+1)R(a,b)$ since $a+1+b = b+1+a$

Thus, $[a+1,b+1]=[a,b]$ and the result holds.