Skip to main content
Logo image

Applied Combinatorics

Section B.8 Multiplication as a Binary Operation

We define a binary operation \(\times\text{,}\) called multiplication, on the set of natural numbers. When \(m\) and \(n\) are natural numbers, \(m\times n\) is also called the product of \(m\) and \(n\text{,}\) and it sometimes denoted \(m*n\) and even more compactly as \(mn\text{.}\) We will use this last convention in the material to follow. Let \(n\in \nonnegints\text{.}\) We define
  1. \(n0=0\text{,}\) and
  2. \(n(k+1)=nk +n\text{.}\)
Note that \(10=0\) and \(01=00+0=0\text{.}\) Also, note that \(11=10+1=0+1=1\text{.}\) More generally, from (ii) and Lemma B.19, we conclude that if \(m,n\neq0\text{,}\) then \(mn\neq0\text{.}\)
Let \(m,n\in \nonnegints\text{.}\) Then
\begin{equation*} m(n+0)=mn = mn +0 = mn+ m0. \end{equation*}
Now assume \(m(n+k) = mn + mk\text{.}\) Then
\begin{align*} m[n+(k+1)] \amp = m[(n+k)+1]=m(n+k)+m\\ \amp =(mn+mk)+m=mn+(mk+m)= mn+m(k+1). \end{align*}
Let \(m,n\in \nonnegints\text{.}\) Then
\begin{equation*} (m+n)0 =0 = 0+0 = m0 + n0. \end{equation*}
Now assume \((m+n)k = mk + nk\text{.}\) Then
\begin{align*} (m+n)(k+1)\amp =(m+n)k+(m+n)= (mk+nk) +(m+n)\\ \amp =(mk+m)+(nk+n)=m(k+1)+n(k+1). \end{align*}
Let \(m,n\in \nonnegints\text{.}\) Then
\begin{equation*} m(n0)= m0 = 0 = (mn)0. \end{equation*}
Now assume that \(m(nk)=(mn)k\text{.}\) Then
\begin{equation*} m[n(k+1)]= m(nk + n)= m(nk) + mn =(mn)k + mn = (mn)(k+1). \end{equation*}
The commutative law requires some preliminary work.
The lemma holds trivially when \(n=0\text{.}\) Assume \(k0= 0k=0\text{.}\) Then
\begin{equation*} (k+1)0 =0 = 0+0= 0k+0=0(k+1). \end{equation*}
\(01=00+0=0 =10\text{.}\) Assume \(k1=1k=k\text{.}\) Then
\begin{equation*} (k+1)1=k1+11=1k+1=1(k+1). \end{equation*}
Let \(m\in \nonnegints\text{.}\) Then \(m0=0m\text{.}\) Assume \(mk=km\text{.}\) Then
\begin{equation*} m (k+1) = mk +m = km+m= km +1m=(k+1)m. \end{equation*}