Skip to main content \(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
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*}
Lemma B.36 .
Proof. Let
\((a,b)\in Z\text{.}\) Then
\(a+b=b+a\text{,}\) so
\((a,b)\cong(b,a)\text{.}\)
Lemma B.37 .
Proof. 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{.}\)
Lemma B.38 .
Proof.
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 .
