Exercise 1.1 · Q9: Multiples of 4, and equality, on {0, …, 12}

Basics you need

Part (i): $|a-b|$ is a multiple of 4

1. Remove the absolute value

   $|a-b|$ is either $a - b$ or $-(a-b)$⁠, and a number is a multiple of 4 exactly when its negative is (Basic 1). So

   $$\begin{aligned} (a,b)\in R &\iff |a-b| \text{ is a multiple of 4}\\ &\iff a - b = 4k \text{ for some integer } k. \end{aligned}$$
   The transitive step will add two differences, and signed differences add exactly while absolute values do not. For example $12 - 4 = 8$ and $4 - 8 = -4$ add to $4 = 12 - 8$⁠, but $|8| + |-4| = 12 \ne |12-8|$⁠. So we work with $a - b = 4k$⁠, where $k$ may be negative.
   If $a - b = -4j$⁠, write it as $4(-j)$⁠: $-j$ is still an integer, so it is still of the form $4k$⁠.

2. Reflexive

   For any $a\in A$⁠, $a - a = 0 = 4\cdot 0$⁠. So $(a,a)\in R$ for every $a$⁠, and $R$ is reflexive.

   Every element differs from itself by 0, and 0 is a multiple of 4 (with $k = 0$⁠).
   0 is a multiple of every integer: $0 = 4\cdot 0$⁠.

3. Symmetric

   Suppose $(a,b)\in R$⁠, so $a - b = 4k$ for an integer $k$⁠. Then

   $$b - a = -(a-b) = -(4k) = 4(-k),$$

   and $-k$ is an integer. So $(b,a)\in R$⁠, and $R$ is symmetric.

   Reversing a subtraction only changes its sign, and the negative of a multiple of 4 is again a multiple of 4. We started from $(a,b)\in R$ and derived $(b,a)\in R$⁠.
   Integers are closed under negation: $k\in\Z \Rightarrow -k\in\Z$⁠.

4. Transitive

   Suppose $(a,b)\in R$ and $(b,c)\in R$⁠: $a - b = 4k$ and $b - c = 4m$ for integers $k, m$⁠. Adding,

   $$a - c = (a-b) + (b-c) = 4k + 4m = 4(k+m).$$

   $k + m$ is an integer, so $(a,c)\in R$⁠, and $R$ is transitive. Hence $R$ is an equivalence relation.

   Adding the two equations cancels the middle element $b$⁠, leaving exactly the difference we need. We use two letters $k$ and $m$ because the two differences need not be equal: in the chain $9, 5, 1$ they are $4$ and $4$⁠, but in the chain $12, 4, 8$ they are $8$ and $-4$⁠.
   $4k + 4m = 4(k+m)$⁠, and the sum of two integers is an integer.

5. Find every element related to 1

   We need all $b\in A$ with $|1 - b|$ a multiple of 4. Since $0 \le b \le 12$⁠, the difference $|1-b|$ lies between 0 and 11, so the only possible multiples are 0, 4 and 8:

   $b$	0	1	2	3	4	5	6	7	8	9	10	11	12
   $|1-b|$	1	0	1	2	3	4	5	6	7	8	9	10	11

   Only $b = 1$ (difference 0), $b = 5$ (difference 4) and $b = 9$ (difference 8) qualify. Equivalently, $b - 1 = 4k$ gives $b = 1 + 4k$⁠: $k = 0, 1, 2$ give $1, 5, 9$⁠, while $k = 3$ gives $13 > 12$ and $k = -1$ gives $-3 < 0$⁠, both outside $A$⁠. So

   $$\{b\in A : (1,b)\in R\} = \{1, 5, 9\}.$$
   "The set of all elements related to 1" means every $b$ in $A$ with $(1,b)\in R$⁠, so we must test every $b$⁠, or argue that no other $b$ can work. The table does the first; the formula $b = 1 + 4k$ does the second and shows why the list stops: the next candidates, 13 and $-3$⁠, are not in $A$⁠. The class of 1 is the set of elements that leave remainder 1 when divided by 4.
   For an equivalence relation, the elements related to 1 form the class $[1]$⁠, and any two of them are related to each other: $|5 - 9| = 4$⁠, $|1 - 9| = 8$⁠. Basics: equivalence classes

Part (ii): $a = b$

1. Equality is reflexive, symmetric and transitive

   Reflexive: for every $a\in A$⁠, $a = a$⁠, so $(a,a)\in R$⁠.
   Symmetric: if $(a,b)\in R$ then $a = b$⁠, so $b = a$ and $(b,a)\in R$⁠.
   Transitive: if $(a,b)\in R$ and $(b,c)\in R$ then $a = b$ and $b = c$⁠, so $a = c$ and $(a,c)\in R$⁠.

   So $R$ is an equivalence relation.

   These are the three basic properties of equality itself: every number equals itself, an equation can be read backwards, and two numbers equal to the same number are equal. This relation is $R = \{(0,0),(1,1),\dots,(12,12)\}$⁠, the identity relation on $A$⁠, with exactly 13 pairs.
   Reflexive, symmetric, transitive: Definition 3; equivalence relation: Definition 4 (Section 1.2).

2. Find every element related to 1

   $(1,b)\in R$ means $1 = b$⁠. The only such $b$ is 1 itself, so

   $$\{b\in A : (1,b)\in R\} = \{1\}.$$
   Under equality, each element is related to nothing but itself. So every equivalence class has one element: $[0] = \{0\}$⁠, $[1] = \{1\}$⁠, and so on, 13 classes in all. Compare with part (i), where 1 was also related to 5 and 9.
   Equality is the smallest equivalence relation on any set: every equivalence relation must contain all the pairs $(a,a)$⁠, and equality contains nothing else.

Every fact used, and where it comes from