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

Jump to navigation
Jump to search

## 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 cancellable, in the sense that:

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

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

and similarly:

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

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

## Proof

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

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \eqclass {b, a} {} \oplus \paren {\eqclass {a, b} {} \oplus \eqclass {c_1, d_1} {} }\) | \(=\) | \(\displaystyle \eqclass {b, a} {} \oplus \paren {\eqclass {a, b} {} \oplus \eqclass {c_2, d_2} {} }\) | adding $\eqclass {b, a} {}$ to both sides | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \paren {\eqclass {b, a} {} \oplus \eqclass {a, b} {} } \oplus \eqclass {c_1, d_1} {}\) | \(=\) | \(\displaystyle \paren {\eqclass {b, a} {} \oplus \eqclass {a, b} {} } \oplus \eqclass {c_2, d_2} {}\) | Integer Addition is Associative | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \eqclass {a + b, a + b} {} \oplus \eqclass {c_1, d_1} {}\) | \(=\) | \(\displaystyle \eqclass {a + b, a + b} {} \oplus \eqclass {c_2, d_2} {}\) | Definition of $\oplus$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \eqclass {c_1, d_1} {}\) | \(=\) | \(\displaystyle \eqclass {c_2, d_2} {}\) | Identity for Addition of Cross-Relation Equivalence Classes on Natural Numbers |

$\blacksquare$

## Sources

- 1964: W.E. Deskins:
*Abstract Algebra*... (previous) ... (next): $\S 2.5$: Corollary $2.25.1$