Cross-Relation on Natural Numbers is Equivalence Relation

Theorem

Let $\struct {\N, +}$ be the semigroup of natural numbers under addition.

Let $\struct {\N \times \N, \oplus}$ be the (external) direct product of $\struct {\N, +}$ with itself, where $\oplus$ is the operation on $\N \times \N$ induced by $+$ on $\N$.

The relation $\boxtimes$ defined on $\N \times \N$ by:

$\tuple {x_1, y_1} \boxtimes \tuple {x_2, y_2} \iff x_1 + y_2 = x_2 + y_1$

is an equivalence relation on $\struct {\N \times \N, \oplus}$.

Proof

$\boxtimes$ is an instance of a cross-relation.

We also have that Natural Number Addition is Commutative.

The result therefore follows from Cross-Relation is Equivalence Relation.

$\blacksquare$

Sources

• 1964: W.E. Deskins: Abstract Algebra ... (previous) ... (next): $\S 2.5$: Theorem $2.20$
• 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $4$: Mappings: Exercise $9$