Example 20: Two descriptions of one relation on {1, …, 9}

Basics you need

Solution

1. Sort the elements of $X$ by remainder

   Remainder on division by 3	Elements of $X$	Form
   1	$1 = 3\cdot 0+1$⁠, $4 = 3\cdot 1+1$⁠, $7 = 3\cdot 2+1$	$3q+1$
   2	$2 = 3\cdot 0+2$⁠, $5 = 3\cdot 1+2$⁠, $8 = 3\cdot 2+2$	$3q+2$
   0	$3 = 3\cdot 1$⁠, $6 = 3\cdot 2$⁠, $9 = 3\cdot 3$	$3q$

   So the three groups used in $R_2$ are precisely the sets of elements of $X$ with remainder 1, 2 and 0. Every element of $X$ is in exactly one group.

   This is the "characteristic" of the three sets that the textbook mentions. Naming it precisely (same remainder) turns both directions of the proof into short calculations. The fact that the groups do not overlap and cover $X$ follows from Basic 3: each number has one and only one remainder.
   Every integer has a unique remainder 0, 1 or 2 on division by 3 (Basic 3).

2. Show $R_2 \subset R_1$

   Take any $(x,y)\in R_2$⁠. Then $x$ and $y$ lie in the same group, so they have the same remainder $r$ (Step 1):

   $$x = 3q + r, \quad y = 3q' + r \qquad\text{for some integers } q, q'.$$

   Subtracting,

   $$x - y = (3q + r) - (3q' + r) = 3(q - q'),$$

   and $q - q'$ is an integer. So $x - y$ is divisible by 3, that is $(x,y)\in R_1$⁠. Since $(x,y)$ was an arbitrary element of $R_2$⁠, $R_2 \subset R_1$.

   The remainders are equal, so they cancel when we subtract, leaving a multiple of 3. This handles all three groups at once, since we wrote a general remainder $r$⁠. For example, in $\{2,5,8\}$⁠: $8 - 2 = 6$⁠, $5 - 8 = -3$⁠, $5 - 5 = 0$⁠, all multiples of 3. Note that negative differences and 0 count: $-3 = 3\cdot(-1)$ and $0 = 3\cdot 0$⁠.
   $3 \mid n$ means $n = 3k$ for some integer $k$ (possibly negative or zero). The difference of two integers is an integer. Basics: integers

3. Show $R_1 \subset R_2$

   Take any $(x,y)\in R_1$⁠, so $x - y = 3k$ for some integer $k$⁠. Write $x = 3q + r$ and $y = 3q' + r'$ with remainders $r, r' \in\{0,1,2\}$⁠. Then

   $$r - r' = (x - 3q) - (y - 3q') = (x - y) - 3(q - q') = 3(k - q + q'),$$

   so $r - r'$ is a multiple of 3. But $r$ and $r'$ are each 0, 1 or 2, so $-2 \le r - r' \le 2$⁠. The only multiple of 3 between $-2$ and $2$ is 0. Hence $r = r'$⁠: $x$ and $y$ have the same remainder, so by Step 1 they lie in the same group, and $\{x,y\}$ is a subset of $\{1,4,7\}$⁠, $\{2,5,8\}$ or $\{3,6,9\}$⁠. That is $(x,y)\in R_2$⁠. Hence $R_1 \subset R_2$.

   This is the direction that the textbook passes over quickly, and it needs a reason: why can't two numbers from different groups differ by a multiple of 3? The argument shows that the difference of the remainders would then be $\pm1$ or $\pm2$⁠, which is never a multiple of 3. The trick of squeezing $r - r'$ between $-2$ and $2$ is what forces it to be 0.
   The only multiple of 3 strictly between $-3$ and $3$ is 0. Uniqueness of the remainder (Basic 3).

4. Conclude: $R_1 = R_2$

   We have $R_1 \subset R_2$ (Step 3) and $R_2 \subset R_1$ (Step 2). Therefore $R_1 = R_2$.

   Set equality is exactly mutual inclusion (Basic 1). The figure gives a picture of the same fact: one set of 27 dots, seen in two orders. The left pattern is "difference divisible by 3"; the right pattern is "both in the same group".
   $P = Q \iff P\subset Q \text{ and } Q \subset P$⁠. Basics: sets

5. Count the pairs as a cross-check

   In $R_2$⁠, each group has 3 elements, so it gives $3\times 3 = 9$ ordered pairs (both entries chosen from the group, repeats allowed). Three groups give $3 \times 9 = 27$ pairs. In $R_1$⁠, list by the value of $x - y$⁠:

   $$\begin{aligned} x - y = 0 &: \ 9 \text{ pairs},\\ x - y = \pm 3 &: \ 6 + 6 \text{ pairs},\\ x - y = \pm 6 &: \ 3 + 3 \text{ pairs},\\ \text{total} &: \ 9 + 12 + 6 = 27. \end{aligned}$$
   The proof is already complete, but counting gives an independent sanity check: equal sets must have the same number of elements. The differences $x - y$ for $x, y \in X$ range from $-8$ to $8$⁠, and the multiples of 3 in that range are $0, \pm 3, \pm 6$⁠. For $x - y = 3$ the pairs are $(4,1), (5,2), \dots, (9,6)$⁠, six of them; for $x-y = 6$ they are $(7,1), (8,2), (9,3)$⁠.
   Counting ordered pairs from a 3-element set with repetition allowed: $3\times 3$⁠. Basics: counting choices

Every fact used, and where it comes from