Natural Number Multiplication is Commutative

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$

As Euclid defined it:

If two (natural) numbers by multiplying one another make certain numbers, the numbers so produced will be equal to one another.

(The Elements: Book VII: Proposition $16$)

Proof 1

Follows directly from the fact that the Natural Numbers form Commutative Semiring.

$\blacksquare$

Proof 2

Proof by induction:

From the definition of natural number multiplication, we have that:

	\(\displaystyle \)	\(\displaystyle \forall m, n \in \N:\)	\(\displaystyle \)	\(\displaystyle m \times 0\)	\(=\)	\(\displaystyle 0\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle m \times n^+\)	\(=\)	\(\displaystyle \left({m \times n}\right) + m\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

For all $n \in \N$, let $P \left({n}\right)$ be the proposition:

$\forall m \in \N: m \times n = n \times m$

Basis for the Induction

From Natural Number Multiplication Commutes with Zero, we have:

$\forall m \in \N: m \times 0 = 0 = 0 \times m$

Thus $P \left({0}\right)$ is seen to be true.

This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 0$, then it logically follows that $P \left({k^+}\right)$ is true.

So this is our induction hypothesis $P \left({k}\right)$:

$\forall m \in \N: m \times k = k \times m$

Then we need to show that $P \left({k^+}\right)$ follows from $P \left({k}\right)$:

$\forall m \in \N: m \times k^+ = k^+ \times m$

Induction Step

This is our induction step:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle m \times k^+\)	\(=\)	\(\displaystyle \left({m \times k}\right) + m\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle m + \left({m \times k}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Natural Number Addition is Commutative
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle m + \left({k \times m}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	from the induction hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle k^+ \times m\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Natural Number Multiplication Commutativity with Successor

So $P \left({k}\right) \implies P \left({k^+}\right)$ and the result follows by the Principle of Finite Induction.

Therefore:

$\forall m, n \in \N: m \times n = n \times m$

$\blacksquare$

Euclid's Proof

Let $A, B$ be two (natural) numbers, and let $A$ by multiplying $B$ make $C$, and $B$ by multiplying $A$ make $D$.

We need to show that $C = D$.

We have that $A \times B = C$.

So $B$ measures $C$ according to the units of $A$.

But the unit $E$ also measures $A$ according to the units in it.

So $E$ measures $A$ the same number of times that $B$ measures $C$.

Therefore from Book VII Proposition 15: Alternate Ratios of Multiples‎ $E$ measures $B$ the same number of times that $A$ measures $C$.

We also have that $A$ measures $D$ according to the units of $B$.

But the unit $E$ also measures $B$ according to the units in it.

Therefore from Book VII Proposition 15: Alternate Ratios of Multiples‎ $E$ measures $B$ the same number of times that $A$ measures $D$.

But we also have that $E$ measures $B$ the same number of times that $A$ measures $C$.

So $A$ measures $C$ and $D$ the same number of times.

Therefore $C = D$.

$\blacksquare$