How to Prove an Equivalence Relation on Z⁺ × Z⁺ (Same-Difference Example)

The Example

Let (a, b) and (c, d) be elements of Z⁺ × Z⁺.

Define: (a, b) ~ (c, d) if a + d = b + c.

Prove that ~ is an equivalence relation on Z⁺ × Z⁺ by verifying reflexivity, symmetry, and transitivity.

You must prove three things on the set of positive-integer pairs Z⁺ × Z⁺:

1. Reflexive

2. Symmetric

3. Transitive

What "on Z⁺ × Z⁺" means

• The base set is Z⁺ × Z⁺.

  An element of this set is a pair like (1, 2), not a single number.

• A relation "on X" is a subset of X × X.

  Here, we're saying the relation is "on Z⁺ × Z⁺", so the relation is a subset of (Z⁺ × Z⁺) × (Z⁺ × Z⁺).

  In plain English: the relation compares pairs to pairs.

The Key Idea that Makes this Relation Easy

The condition

a + d = b + c

is equivalent to

a - b = c - d.

So two pairs are related exactly when they have the same difference (first minus second). Keep "same difference" in your head. It drives the whole situation.

A Picture You Can Hold in Your Head

Imagine a grid with horizontal axis a and vertical axis b.

Each point (a, b) is one element of the base set (Z⁺ × Z⁺).

Points with the same value of a - b lie on the same downward-sloping diagonal.

Example with a - b = 0: (1, 1) (2, 2), (3, 3), ...

Example with a - b = 2: (3, 1), (4, 2), (5, 3), ...

The relation "same difference" groups points by diagonals. Each diagonal is one big group. Those groups do not overlap and they cover all points, which is exactly what an equivalence relation should do.

The grid below is the visualization of the relation's equivalence classes: each diagonal line corresponds to one class.

The grid below is not the full relation grid (Z⁺ × Z⁺) × (Z⁺ × Z⁺), which would compare pairs to pairs and is far too large to draw. Instead, this picture just shows the base set Z⁺ × Z⁺. It's the right way to visualize the equivalence classes, because each downward-sloping diagonal (constant a - b) represents one class.

	1	2	3	4	5
1	(1, 1)	(1, 2)	(1, 3)	(1, 4)	(1, 5)
2	(2, 1)	(2, 2)	(2, 3)	(2, 4)	(2, 5)
3	(3, 1)	(3, 2)	(3, 3)	(3, 4)	(3, 5)
4	(4, 1)	(4, 2)	(4, 3)	(4, 4)	(4, 5)
5	(5, 1)	(5, 2)	(5, 3)	(5, 4)	(5, 5)

Proof that ~ is an equivalence relation

We now prove that the relation is reflexive, symmetric, and transitive. Keep both versions of the condition in mind, as they are interchangeable.

Version A: a + d = b + c

Version B: a - b = c - d

Reflexive

Take any (a, b). We must show (a, b) ~ (a, b).

Using Version A: a + b = b + a By commutativity of addition, the condition holds.

Therefore, (a, b) ~ (a, b). Reflexive. ✓

Symmetric

Assume (a, b) ~ (c, d). We must show (c, d) ~ (a, b).

Using Version A:

a + d = b + c That is,

c + b = d + a

Which is exactly the condition for (c, d) ~ (a, b). Symmetric. ✓

Transitive

Assume (a, b) ~ (c, d) and (c, d) ~ (e, f). We must show (a, b) ~ (e, f)

Using Version A: a + d = b + c and c + f = d + e.

Add these inequalities:

(a + d) + (c + f) = (b + c) + (d + e).

Rearrange both sides

a + f + (c + d) = b + e + (c + d)

Cancel c + d from both sides

a + f = b + e

Which is the condition for (a, b) ~ (e, f). Transitive. ✓

All three properties hold, so ~ is an equivalence relation.

What the Equivalence Classes Look Like

For any (a, b), its class is:

[(a, b)] = {(x, y) ∈ Z⁺ × Z⁺ : x - y = a - b}.

In the grid picture above, that is the entire downward-sloping diagonal with constant difference a - b.

• Difference 0: (1, 1), (2, 2), (3, 3), ...

• Difference 1: (2, 1), (3, 2), (4, 3), ...

• Difference -1: (1, 2), (2, 3), (3, 4), ...

These classes partition Z⁺ × Z⁺: every pair belongs to exactly one diagonal, and different diagonals do not intersect.

---

Need more help with Equivalence Relations? If you’re in Winnipeg and looking for a tutor, Tutor Advance provides expert one-on-one support!

---