Example 5: $2 \mid (a-b)$ is an equivalence relation on $\Z$

Basics you need

Solution

1. Translate the rule into an equation

   By the definition of divisibility (Basic 1),

   $$(a,b)\in R \iff a - b = 2k \ \text{ for some integer } k.$$

   It helps to test the rule on a few pairs before proving anything, just to see what it says:

   Pair $(a,b)$	$a-b$	Written as $2k$⁠?	In $R$⁠?
   $(7,3)$	$4$	$4 = 2\cdot 2$⁠, $k=2$	yes
   $(5,-1)$	$6$	$6 = 2\cdot 3$⁠, $k=3$	yes
   $(-3,11)$	$-14$	$-14 = 2\cdot(-7)$⁠, $k=-7$	yes
   $(4,9)$	$-5$	$-5 = 2\cdot(-2.5)$⁠, but $-2.5 \notin \Z$	no

   Words like "divides" cannot be added or rearranged; equations can. Writing $a-b=2k$ turns every question about $R$ into a question about integers that we can calculate with. The table shows the pattern: the pairs that belong are exactly the ones where $a$ and $b$ have the same parity (both odd or both even). In $(4,9)$ one is even and one is odd, and the gap is odd.
   An integer is even when it equals $2k$ for an integer $k$⁠. So "$2 \mid (a-b)$" and "$a-b$ is even" mean exactly the same thing, and we will use both phrasings.

2. Reflexive: is every integer related to itself?

   We must show $(a,a)\in R$ for every $a\in\Z$⁠. Take any integer $a$⁠. Then

   $$a - a = 0 = 2\cdot 0.$$

   Here $k = 0$⁠, which is an integer. So $2$ divides $a-a$⁠, that is $(a,a)\in R$⁠. Since $a$ was arbitrary, this holds for every integer, and $R$ is reflexive.

   Reflexivity is a statement about all integers, so we use a letter $a$ that could be any of them. The calculation $a-a=0$ never depends on which integer $a$ is, which is what makes the argument valid for all of them at once.
   Zero is even: $0 = 2 \cdot 0$⁠, and 0 is an integer. Many students hesitate here, but 0 satisfies the definition of "even" exactly like 2, 4 or −6 do.

3. Symmetric: if $a$ is related to $b$⁠, is $b$ related to $a$⁠?

   Suppose $(a,b)\in R$⁠. By Step 1 this means $a - b = 2k$ for some integer $k$⁠. We must show $(b,a)\in R$⁠, that is, that $b-a$ is also a multiple of 2. Reverse the subtraction:

   $$b - a = -(a - b) = -(2k) = 2(-k).$$

   Because $k$ is an integer, $-k$ is an integer too. So $b - a = 2\times(\text{an integer})$⁠, which means $2 \mid (b-a)$ and $(b,a)\in R$⁠. Hence $R$ is symmetric.

   Symmetry is an "if … then" statement, so the proof must start from the "if" part, $(a,b)\in R$⁠, and use it. Reversing the order of a subtraction only changes its sign: $b-a$ is always $-(a-b)$⁠. The gap from 5 to −1 is 6 and the gap from −1 to 5 is −6, so both are even.
   Closure under negation (Basic 5): if $k$ is an integer, so is $-k$⁠. That is what lets us call $-k$ "the integer" in the definition $b-a = 2\times$(integer).

4. Transitive: does a chain of two links give a direct link?

   Suppose $(a,b)\in R$ and $(b,c)\in R$⁠. Then there are integers $k$ and $m$ with

   $$a - b = 2k \qquad\text{and}\qquad b - c = 2m.$$

   We need information about $a - c$⁠. Adding the two equations makes $b$ cancel:

   $$(a - b) + (b - c) = a - c, \qquad\text{so}\qquad a - c = 2k + 2m = 2(k + m).$$

   Since $k$ and $m$ are integers, $k+m$ is an integer. So $2 \mid (a - c)$⁠, that is $(a,c)\in R$⁠. Hence $R$ is transitive.

   This answers the textbook's "(Why?)": $a-c$ is even because it is the sum of two even numbers, and $2k + 2m = 2(k+m)$⁠. We add the equations, rather than subtract or multiply them, because adding is the operation that removes the middle element $b$⁠: $-b + b = 0$⁠. Getting rid of $b$ is the goal, since the statement we want, $(a,c)\in R$⁠, does not mention $b$⁠.
   Closure under addition (Basic 5): the sum of two integers is an integer. Use two different letters, $k$ and $m$⁠. The two gaps need not be the same even number (for example $11-5=6$ but $5-(-3)=8$⁠), so writing $2k$ for both would wrongly assume they are equal.

5. Conclude

   $R$ is reflexive (Step 2), symmetric (Step 3) and transitive (Step 4). A relation with all three properties is, by definition, an equivalence relation. So $R$ is an equivalence relation in $\Z$.

   The definition of an equivalence relation is just the list of these three properties. Once each has been proved for arbitrary elements, nothing more is needed.

6. What the relation sorts the integers into

   The textbook continues with an important observation. Every even integer is related to 0, since $e - 0 = e$ is even. No odd integer is related to 0. Likewise every odd integer is related to 1 and no even integer is. So $R$ splits $\Z$ into exactly two groups, called equivalence classes:

   $$[0] = \{\dots,-4,-2,0,2,4,\dots\} = E, \qquad [1] = \{\dots,-3,-1,1,3,5,\dots\} = O.$$

   The two classes do not overlap ($E \cap O = \varnothing$⁠) and together they make up all of $\Z$ ($E \cup O = \Z$⁠). Also $[0] = [2r]$ and $[1] = [2r+1]$ for every $r\in\Z$⁠: any even number is a valid "name" for the even class.

   This is the real meaning of an equivalence relation: it sorts a set into non-overlapping groups of "equivalent" elements. Here the property being shared is parity. The textbook uses this example to introduce equivalence classes for exactly that reason.
   For any equivalence relation, the equivalence classes partition the set: they are disjoint and their union is the whole set. Basics: equivalence classes

Every fact used, and where it comes from