# Addition of Cross-Relation Equivalence Classes on Natural Numbers is Well-Defined

## 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$.

Let $\boxtimes$ be the cross-relation 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$

Let $\eqclass {x, y} {}$ denote the equivalence class of $\tuple {x, y}$ under $\boxtimes$.

The operation $\oplus$ on these equivalence classes is well-defined, in the sense that:

\(\displaystyle \eqclass {a_1, b_1} {}\) | \(=\) | \(\displaystyle \eqclass {a_2, b_2} {}\) | |||||||||||

\(\displaystyle \eqclass {c_1, d_1} {}\) | \(=\) | \(\displaystyle \eqclass {c_2, d_2} {}\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \eqclass {a_1, b_1} {} \oplus \eqclass {c_1, d_1} {}\) | \(=\) | \(\displaystyle \eqclass {a_2, b_2} {} \oplus \eqclass {c_2, d_2} {}\) |

## Proof

Let $\eqclass {a_1, b_1} {}, \eqclass {a_2, b_2} {}, \eqclass {c_1, d_1} {}, \eqclass {c_2, d_2} {}$ be $\boxtimes$-equivalence classes such that $\eqclass {a_1, b_1} {} = \eqclass {a_2, b_2} {}$ and $\eqclass {c_1, d_1} {} = \eqclass {c_2, d_2} {}$.

Then:

\(\displaystyle \eqclass {a_1, b_1} {}\) | \(=\) | \(\displaystyle \eqclass {a_2, b_2} {}\) | Definition of Operation Induced by Direct Product | ||||||||||

\(\, \displaystyle \land \, \) | \(\displaystyle \eqclass {c_1, d_1} {}\) | \(=\) | \(\displaystyle \eqclass {c_2, d_2} {}\) | Definition of Operation Induced by Direct Product | |||||||||

\(\displaystyle \leadstoandfrom \ \ \) | \(\displaystyle a_1 + b_2\) | \(=\) | \(\displaystyle a_2 + b_1\) | Definition of Cross-Relation | |||||||||

\(\, \displaystyle \land \, \) | \(\displaystyle c_1 + d_2\) | \(=\) | \(\displaystyle c_2 + d_1\) | Definition of Cross-Relation |

Then we have:

\(\displaystyle \tuple {a_1 + c_1} + \tuple {b_2 + d_2}\) | \(=\) | \(\displaystyle \tuple {a_1 + b_2} + \tuple {c_1 + d_2}\) | Commutativity and associativity of $+$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \tuple {a_2 + b_1} + \tuple {c_2 + d_1}\) | from above: $a_1 + b_2 = a_2 + b_1, c_1 + d_2 = c_2 + d_1$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \tuple {a_2 + c_2} + \tuple {b_1 + d_1}\) | Commutativity and associativity of $+$ | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \tuple {a_1 + c_1, b_1 + d_1}\) | \(\boxtimes\) | \(\displaystyle \tuple {a_2 + c_2, b_2 + d_2}\) | Definition of $\boxtimes$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \tuple {\tuple {a_1, b_1} \oplus \tuple {c_1, d_1} }\) | \(\boxtimes\) | \(\displaystyle \tuple {\tuple {a_2, b_2} \oplus \tuple {c_2, d_2} }\) | Definition of $\oplus$ |

$\blacksquare$

## Sources

- 1951: Nathan Jacobson:
*Lectures in Abstract Algebra: I. Basic Concepts*... (previous) ... (next): Introduction $\S 5$: The system of integers - 1964: W.E. Deskins:
*Abstract Algebra*... (previous) ... (next): $\S 2.5$: Theorem $2.22$