Question

Let a relation R be defined in the set \(\mathbb{N} \times \mathbb{N}\) as follows: \((a, b) R (c, d)\) if and only if \(a + d = b + c\). Prove that R is an equivalence relation.

Hint:

When proving an equivalence relation, always address the three properties—reflexive, symmetric, and transitive—separately and clearly. For relations involving equations, algebraic manipulation is the key to proving symmetry and transitivity.

Answer 1

Step 1: Understanding the Concept:
An equivalence relation is a binary relation on a set that satisfies three properties: reflexivity, symmetry, and transitivity. We need to prove that the given relation R on the set \(\mathbb{N} \times \mathbb{N}\) satisfies all three properties.
The relation is defined as: \((a, b) R (c, d) \iff a + d = b + c\). This can also be written as \(a - b = c - d\).
Step 2: Key Formula or Approach:
To prove that R is an equivalence relation, we must show:
1. Reflexivity: \((a, b) R (a, b)\) for all \((a, b) \in \mathbb{N} \times \mathbb{N}\).
2. Symmetry: If \((a, b) R (c, d)\), then \((c, d) R (a, b)\) for all \((a, b), (c, d) \in \mathbb{N} \times \mathbb{N}\).
3. Transitivity: If \((a, b) R (c, d)\) and \((c, d) R (e, f)\), then \((a, b) R (e, f)\) for all \((a, b), (c, d), (e, f) \in \mathbb{N} \times \mathbb{N}\).
Step 3: Detailed Explanation:
1. Proof of Reflexivity:
We need to check if \((a, b) R (a, b)\).
According to the definition of R, this means we must check if \(a + b = b + a\).
Since addition is commutative in the set of natural numbers \(\mathbb{N}\), the condition \(a + b = b + a\) is always true.
Therefore, R is reflexive.
2. Proof of Symmetry:
Assume that \((a, b) R (c, d)\).
By the definition of R, this means \(a + d = b + c\).
We need to prove that \((c, d) R (a, b)\), which means we need to show that \(c + b = d + a\).
Starting with our assumption: \[ a + d = b + c \] By the commutative property of addition, we can rewrite this as: \[ d + a = c + b \] \[ c + b = d + a \] This is exactly the condition for \((c, d) R (a, b)\).
Therefore, R is symmetric.
3. Proof of Transitivity:
Assume that \((a, b) R (c, d)\) and \((c, d) R (e, f)\).
From \((a, b) R (c, d)\), we have: \[ a + d = b + c \quad \cdots (1) \] From \((c, d) R (e, f)\), we have: \[ c + f = d + e \quad \cdots (2) \] We need to prove that \((a, b) R (e, f)\), which means we need to show that \(a + f = b + e\).
Adding equation (1) and equation (2): \[ (a + d) + (c + f) = (b + c) + (d + e) \] \[ a + d + c + f = b + c + d + e \] We can cancel \(c\) and \(d\) from both sides of the equation.
\[ a + f = b + e \] This is the condition for \((a, b) R (e, f)\).
Therefore, R is transitive.
Step 4: Final Answer:
Since the relation R is reflexive, symmetric, and transitive, it is an equivalence relation on the set \(\mathbb{N} \times \mathbb{N}\).