Skip to main content
Logo image

Applied Combinatorics

Section B.14 The Integers as Equivalence Classes of Ordered Pairs

Define a binary relation \(\cong\) on the set \(Z=\nonnegints \times\nonnegints\) by
\begin{equation*} (a,b)\cong (c,d)\quad\textit{iff}\quad a+d=b+c. \end{equation*}
Let \((a,b)\in Z\text{.}\) Then \(a+b=b+a\text{,}\) so \((a,b)\cong(b,a)\text{.}\)
Let \((a,b),(c,d)\in Z\) and suppose that \((a,b)\cong (c,d)\text{.}\) Then \(a+d=b+c\text{,}\) so that \(c+b=d+a\text{.}\) Thus \((c,d)\cong (a,b)\text{.}\)
Let \((a,b), (c,d), (e,f)\in Z\text{.}\) Suppose that
\begin{equation*} (a,b)\cong(c,d)\quad\text{and} \quad (c,d)\cong (e,f). \end{equation*}
Then \(a+d=b+c\) and \(c+f=d+e\text{.}\) Therefore,
\begin{equation*} (a+d)+(c+f) =(b+c)+(d+e). \end{equation*}
It follows that
\begin{equation*} (a+f)+(c+d) =(b+e)+(c+d). \end{equation*}
Thus \(a+f = b+e\) so that \((a,b)\cong(e,f)\text{.}\)
Now that we know that \(\cong\) is an equivalence relation on \(Z\text{,}\) we know that \(\cong\) partitions \(Z\) into equivalence classes. For an element \((a,b)\in Z\text{,}\) we denote the equivalence class of \((a,b)\) by \(\langle (a,b)\rangle\text{.}\)
Let \(\ints\) denote the set of all equivalence classes of \(Z\) determined by the equivalence relation \(\cong\text{.}\) The elements of \(\ints\) are called integers.