From ProofWiki
Jump to: navigation, search


Naturally Ordered Semigroup

Let $\left({S, \circ, \preceq}\right)$ be a naturally ordered semigroup.

Let $*$ be the binary operation on $S$ recursively defined by means of the mapping $g_m: S \to T$:

$\forall m, n \in S: n * m = g_m \left({n}\right)$

where $g_m: S \to S$ is the unique mapping that satisfies:

$\forall m \in S: g_m \left({n}\right) = \begin{cases} 0 & : n = 0 \\ g_m \left({r}\right) \circ m & : n = r \circ 1 \end{cases}$

The product of $n$ and $m$ is defined as $n * m \in S$ and the operation $*$ is called multiplication.

Multiplication on Standard Number Systems

Natural Numbers

The multiplication operation in the domain of natural numbers $\N$ is written $\times$.

It is defined as:

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

This can be interpreted as:

$n \times m = +^n m = \underbrace{m + m + \cdots + m}_{\text{$n$ copies of $m$}}$


The multiplication operation in the domain of integers $\Z$ is written $\times$.

Let us define $\left[\!\left[{\left({a, b}\right)}\right]\!\right]_\boxtimes$ as in the formal definition of integers.

That is, $\left[\!\left[{\left({a, b}\right)}\right]\!\right]_\boxtimes$ is an equivalence class of ordered pairs of natural numbers under the congruence relation $\boxtimes$.

$\boxtimes$ is the congruence relation defined on $\N \times \N$ by $\left({x_1, y_1}\right) \boxtimes \left({x_2, y_2}\right) \iff x_1 + y_2 = x_2 + y_1$.

In order to streamline the notation, we will use $\left[\!\left[{a, b}\right]\!\right]$ to mean $\left[\!\left[{\left({a, b}\right)}\right]\!\right]_\boxtimes$, as suggested.

As the set of integers is the Inverse Completion of Natural Numbers, it follows that elements of $\Z$ are the isomorphic images of the elements of equivalence classes of $\N \times \N$ where two tuples are equivalent if the difference between the two elements of each tuple is the same.

Thus multiplication can be formally defined on $\Z$ as the operation induced on those equivalence classes as specified in the definition of integers.

That is, the integers being defined as all the difference congruence classes, integer multiplication can be defined directly as the operation induced by natural number multiplication on these congruence classes.

It follows that:

$\forall a, b, c, d \in \N: \left[\!\left[{a, b}\right]\!\right] \times \left[\!\left[{c, d}\right]\!\right] = \left[\!\left[{a \times c + b \times d, a \times d + b \times c}\right]\!\right]$ or, more compactly, as $\left[\!\left[{ac + bd, ad + bc}\right]\!\right]$.

This can also be defined as:

$n \times m = +^n m = \underbrace{m + m + \cdots + m}_{\text{$n$ copies of $m$}}$

... and the validity of this is proved in Index Laws for Monoids.

Modulo Multiplication

The multiplication operation on $\Z_m$, the set of integers modulo $m$, is defined by the rule:

$\left[\!\left[{a}\right]\!\right]_m \times_m \left[\!\left[{b}\right]\!\right]_m = \left[\!\left[{a b}\right]\!\right]_m$

Although the operation of multiplication modulo $m$ is denoted by the symbol $\times_m$, if there is no danger of confusion, the conventional multiplication symbols $\times, \cdot$ etc. are often used instead.

More usually, though, the notation $a b \left({\bmod\, m}\right)$ is used instead of $\left[\!\left[{a}\right]\!\right]_m \times_m \left[\!\left[{b}\right]\!\right]_m$.

It means the same thing and, although obscuring the true meaning behind modulo arithmetic, is more streamlined and less unwieldy.

See modulo multiplication.

Rational Numbers

The multiplication operation in the domain of rational numbers $\Q$ is written $\times$.

Let $a = \dfrac p q, b = \dfrac r s$ where $p, q \in \Z, r, s \in \Z \setminus \left\{{0}\right\}$.

Then $a \times b$ is defined as $\dfrac p q \times \dfrac r s = \dfrac {p \times r} {q \times s}$.

This definition follows from the definition of and proof of existence of the quotient field of any integral domain, of which the set of integers is one.

Real Numbers

The multiplication operation in the domain of real numbers $\R$ is written $\times$.

From the definition, the real numbers are the set of all equivalence classes $\left[\!\left[{\left \langle {x_n} \right \rangle}\right]\!\right]$ of Cauchy sequences of rational numbers.

Let $x = \left[\!\left[{\left \langle {x_n} \right \rangle}\right]\!\right], y = \left[\!\left[{\left \langle {y_n} \right \rangle}\right]\!\right]$, where $\left[\!\left[{\left \langle {x_n} \right \rangle}\right]\!\right]$ and $\left[\!\left[{\left \langle {y_n} \right \rangle}\right]\!\right]$ are such equivalence classes.

Then $x \times y$ is defined as $\left[\!\left[{\left \langle {x_n} \right \rangle}\right]\!\right] \times \left[\!\left[{\left \langle {y_n} \right \rangle}\right]\!\right] = \left[\!\left[{\left \langle {x_n \times y_n} \right \rangle}\right]\!\right]$.

The operation of multiplication on the real numbers is well-defined.

Complex Numbers

The multiplication operation in the domain of complex numbers $\C$ is written $\times$.

Let $z = a + i b, w = c + i d$ where $a, b, c, d \in \R$.

Then $z \times w$ is defined as $\left({a + i b}\right) \times \left({c + i d}\right) = \left({ac - bd}\right) + i \left({ad + bc}\right)$.

This follows by the facts that:

Real Numbers form Field and thus real multiplication is distributive over real addition
the entity $i$ is such that $i^2 = -1$.


There are several variants on the notation for multiplication:

  • $n \times m$, which is usually used only when numbers are under consideration, e.g. $3 \times 5 = 15$;
  • $nm$, which is most common in algebra, but not with numbers unless parentheses are put round the numbers, e.g. $\left({3}\right)\left({4}\right) = 12$, for obvious reasons;
  • $n \cdot m$ or $n . m$, which have their uses in algebra, but has the danger of being confused with the decimal point.

Also see

Commutativity of Multiplication

On all the above number sets, we have that multiplication is commutative:

Associativity of Multiplication

On all the above number sets, we have that multiplication is associative: