Q.Let $X = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Let $R_1$ be a relation in $X$ given by $R_1 = \{(x, y): x - y \text{ is divisible by } 3\}$ and $R_2$ be another relation on $X$ given by $R_2 = \{(x, y): \{x, y\} \subset \{1, 4, 7\} \text{ or } \{x, y\} \subset \{2, 5, 8\} \text{ or } \{x, y\} \subset \{3, 6, 9\}\}$. Show that $R_1 = R_2$.

Concept: Equivalence Relation Proof — Two relations defined differently on the same set are equal if they contain exactly the same ordered pairs.

Step 1: Understand $R_1$.

$x - y$ divisible by 3 means $x \equiv y \pmod{3}$. On $X = \{1,\dots,9\}$, the residues modulo 3 partition the set into three classes:

$\{1,4,7\}$, $\{2,5,8\}$, $\{3,6,9\}$.

So $(x,y) \in R_1$ iff $x$ and $y$ belong to the same residue class.

Step 2: Understand $R_2$.

$R_2$ explicitly pairs elements only if they lie together in one of those same three subsets: $\{1,4,7\}$, $\{2,5,8\}$, or $\{3,6,9\}$.

Step 3: Compare.

Both relations require $x$ and $y$ to be in the same one of these three groups. Hence every pair in $R_1$ is in $R_2$, and every pair in $R_2$ is in $R_1$.

The key insight is that both $R_1$ and $R_2$ are describing the same thing: two numbers are related if and only if they leave the same remainder when divided by 3. $R_1$ says this directly using divisibility. $R_2$ says it by listing the three groups $\{1,4,7\}$, $\{2,5,8\}$, $\{3,6,9\}$ — which are precisely the numbers that are congruent to $1$, $2$, and $0$ modulo 3 respectively.

To prove two sets are equal, we show $R_1 \subseteq R_2$ and $R_2 \subseteq R_1$.

1. Show $R_1 \subseteq R_2$.

   Take any $(x,y) \in R_1$. By definition, $x - y$ is divisible by 3, meaning $x \equiv y \pmod{3}$.

   Now look at the residues modulo 3 of the numbers in $X$:

   • Numbers congruent to $0$ mod 3: $\{3,6,9\}$
   • Numbers congruent to $1$ mod 3: $\{1,4,7\}$
   • Numbers congruent to $2$ mod 3: $\{2,5,8\}$ Since $x$ and $y$ have the same residue, they must belong to the same one of these three sets. Therefore $\{x,y\}$ is a subset of one of the three listed sets, which is exactly the condition for $(x,y) \in R_2$. So $R_1 \subseteq R_2$.

2. Show $R_2 \subseteq R_1$.

   Take any $(x,y) \in R_2$. Then $\{x,y\}$ is contained in one of the three sets $\{1,4,7\}$, $\{2,5,8\}$, or $\{3,6,9\}$.

   Within each of these sets, all numbers are congruent modulo 3:

   • In $\{1,4,7\}$, each number $\equiv 1 \pmod{3}$
   • In $\{2,5,8\}$, each number $\equiv 2 \pmod{3}$
   • In $\{3,6,9\}$, each number $\equiv 0 \pmod{3}$ Hence $x \equiv y \pmod{3}$, so $x - y$ is divisible by 3. Thus $(x,y) \in R_1$, and $R_2 \subseteq R_1$.

Since $R_1 \subseteq R_2$ and $R_2 \subseteq R_1$, we have $R_1 = R_2$.

Method: Proving Two Relations Are Equal by Mutual Inclusion

When asked to show $R_1 = R_2$ for two relations described in different ways, treat them as sets of ordered pairs and prove each is contained in the other. This double-inclusion technique works for any set-equality claim, not just relations.

Steps

Step 1: Restate both relations in one common language.

Here both descriptions are really about congruence modulo $3$: "$x-y$ divisible by $3$" and "$x,y$ lie in the same listed group" both say $x \equiv y \pmod 3$. Finding the shared underlying idea is what makes the two inclusions routine.

Step 2: Show $R_1 \subseteq R_2$.

Take an arbitrary pair $(x,y) \in R_1$, use its defining property, and deduce it satisfies $R_2$'s condition. (Same residue mod $3$ $\Rightarrow$ both lie in one of the listed classes.)

Step 3: Show $R_2 \subseteq R_1$.

Take an arbitrary $(x,y) \in R_2$ and deduce it satisfies $R_1$'s condition. (Sharing a listed class $\Rightarrow$ same residue $\Rightarrow$ difference divisible by $3$.)

Step 4: Conclude equality.

Two inclusions in opposite directions give $R_1 = R_2$. A quicker equivalent finish: show both relations induce the same partition into equivalence classes — identical partitions mean identical relations.

Common Mistakes

Mistake 1: Proving only one inclusion.

Why it's wrong: showing $R_1 \subseteq R_2$ alone does not prove equality; the two relations could differ if $R_2$ has extra pairs. Correct approach: prove both $R_1 \subseteq R_2$ and $R_2 \subseteq R_1$ (or show they induce the identical partition).

Mistake 2: Miscomputing the residue classes modulo 3.

Why it's wrong: students sometimes group $\{3,6,9\}$ as residue $3$; on division by $3$ these leave remainder $0$, not $3$. A wrong grouping breaks the correspondence between $R_1$ and $R_2$. Correct approach: compute remainders carefully — $\{1,4,7\}\to 1$, $\{2,5,8\}\to 2$, $\{3,6,9\}\to 0$.

Mistake 3: Forgetting that $\{x,y\}\subset\{1,4,7\}$ includes the case $x=y$.

Why it's wrong: a single-element subset like $\{1\}$ still satisfies the subset condition, so the reflexive pairs $(x,x)$ are genuinely in $R_2$. Overlooking this makes $R_2$ look smaller than $R_1$. Correct approach: treat equal-element pairs as included in both relations.