 # Applied Combinatorics

## SectionB.15Properties of the Integers

For the remainder of this chapter, most statements will be given without proof. Students are encouraged to fill in the details.
We define a binary operation $$+$$ on $$\ints$$ by the following rule:
\begin{equation*} \langle(a,b)\rangle+\langle(c,d)\rangle = \langle(a+c,b+d)\rangle. \end{equation*}
Note that the definition of addition is made in terms of representatives of the class, so we must pause to make sure that $$+$$ is well defined, i.e., independent of the particular representatives.
Since $$(a,b)\cong(c,d)\text{,}$$ we know $$a+d=b+c\text{.}$$ Since $$(e,f)\cong(g,h)\text{,}$$ we know $$e+h=f+g\text{.}$$ It follows that $$(a+d)+(e+h) = (b+c)+ (f+g)\text{.}$$ Thus $$(a+e)+(d+h)= (b+f)+(c+g)\text{,}$$ which implies that $$\langle(a,b)\rangle+\langle(e,f)\rangle= \langle(c,d)\rangle+\langle(g,h)\rangle\text{.}$$
In what follows, we use a single symbol, like $$x\text{,}$$ $$y$$ or $$z$$ to denote an integer, but remember that each integer is in fact an entire equivalence class whose elements are ordered pairs of natural numbers.
Next, we define a second binary operation called multiplication, and denoted $$x\times y\text{,}$$ $$x*y$$ or just $$xy\text{.}$$ When $$x=\langle(a,b)\rangle$$ and $$y=\langle(c,d)\rangle\text{,}$$ we define:
\begin{equation*} xy =\langle(a,b)\rangle\langle(c,d)\rangle= \langle(ac+bd, ad+bc)\rangle. \end{equation*}
The integer $$\langle(0,0)\rangle$$ has a number of special properties. Note that for all $$x\in\ints\text{,}$$ $$x+\langle(0,0)\rangle= x$$ and $$x\langle(0,0)\rangle=\langle(0,0)\rangle\text{.}$$ So most folks call $$\langle(0,0)\rangle$$ zero and denote it by $$0\text{.}$$ This is a terrible abuse of notation, since we have already used the word zero and the symbol $$0$$ to denote a particular natural number.
But mathematicians, computer scientists and even real people do this all the time. We use the same word and even the same phrase in many different settings expecting that the listener will make the correct interpretation. For example, how many different meanings do you know for You’re so bad?
If $$x=\langle(a,b)\rangle$$ is an integer and $$y= \langle(b,a)\rangle\text{,}$$ then $$x+y=\langle(a+b,a+b)\rangle=0\text{.}$$ The integer $$y$$ is then called the additive inverse of $$x$$ and is denoted $$-x\text{.}$$ The additive inverse of $$x$$ is also called minus $$x$$. The basic property is that $$x + (-x) = 0\text{,}$$ for every $$x\in \ints\text{.}$$
We can now define a new binary operation, called subtraction and denoted $$-\text{,}$$ on $$\ints$$ by setting $$x-y= x+(-y)\text{.}$$ In general, subtraction is neither commutative nor associative. However, we do have the following basic properties.
Next, we define a total order on $$\ints$$ by setting $$x\le y$$ in $$\ints$$ when $$x=\langle(a,b)\rangle\text{,}$$ $$y=\langle(c,d) \rangle$$ and $$a+d \le b+c$$ in $$\nonnegints\text{.}$$
For multiplication, the situation is more complicated.
Now consider the function $$f:\nonnegints\longrightarrow \ints$$ defined by $$f(n) = \langle(n,0)\rangle\text{.}$$ It is easy to show that $$f$$ is an injection. Furthermore, it respects addition and multiplication, i.e., $$f(n+m)=f(n)+f(m)$$ and $$f(nm)=f(n)f(m)\text{.}$$ Also, note that if $$x\in \ints\text{,}$$ then $$x>0$$ if and only if $$x=f(n)$$ for some $$n\in \nonnegints\text{.}$$ So, it is customary to abuse notation slightly and say that $$\nonnegints$$ is a “subset” of $$\ints\text{.}$$ Similarly, we can either consider the set $$\posints$$ of positive integers as the set of natural numbers that are successors, or as the set of integers that are greater than $$0\text{.}$$
When $$n$$ is a positive integer and $$0$$ is the zero in $$\ints\text{,}$$ we define $$0^n=0\text{.}$$ When $$x\in\ints\text{,}$$ $$x\neq 0$$ and $$n\in\nonnegints\text{,}$$ we define $$x^n$$ inductively by (i) $$x^0=1$$ and $$x^{k+1}=xx^k\text{.}$$