Natural Number Multiplication is Commutative/Proof 1

From ProofWiki
Jump to: navigation, search

Theorem

The operation of multiplication on the set of natural numbers $\N$ is commutative:

$\forall x, y \in \N: x \times y = y \times x$


Proof

Natural number multiplication is recursively defined as:

$\forall m, n \in \N: \begin{cases} m \times 0 & = 0 \\ m \times \left({n + 1}\right) & = m \times n + m \end{cases}$

From the Principle of Recursive Definition, there is only one mapping $f$ satisfying this definition; that is, such that:

$\forall n \in \N: \begin{cases} f \left({0}\right) = 0 \\ f \left({n + 1}\right) = f \left({n}\right) + m \end{cases}$

Consider now $f'$ defined as $f' \left({n}\right) = n \times m$.

Then by Zero is Zero Element for Natural Number Multiplication:

$f' \left({0}\right) = 0 \times m = 0$

Furthermore:

\(\displaystyle f' \left({n + 1}\right)\) \(=\) \(\displaystyle \left({n + 1}\right) \times m\)
\(\displaystyle \) \(=\) \(\displaystyle n \times m + m\) Natural Number Multiplication Distributes over Addition
\(\displaystyle \) \(=\) \(\displaystyle f' \left({n}\right) + m\)

showing that $f'$ also satisfies the definition of $m \times n$.

By the Principle of Recursive Definition it follows that:

$m \times n = n \times m$

$\blacksquare$


Sources