Homomorphism of External Direct Products/General Result

From ProofWiki
Jump to navigation Jump to search


Let $n \in \N_{>0}$.


$\displaystyle \left({\mathcal S_n, \circledcirc_n}\right) := \prod_{k \mathop = 1}^n S_k = \left({S_1, \circ_1}\right) \times \left({S_2, \circ_2}\right) \times \cdots \times \left({S_n, \circ_n}\right)$
$\displaystyle \left({\mathcal T_n, \circledast_n}\right) := \prod_{k \mathop = 1}^n T_k = \left({T_1, \ast_1}\right) \times \left({T_2, \ast_2}\right) \times \cdots \times \left({T_n, \ast_n}\right)$

be external direct products of algebraic structures.

Let $\Phi_n: \left({\mathcal S_n, \circledcirc_n}\right) \to \left({\mathcal T_n, \circledast_n}\right)$ be the mapping defined as:

$\Phi_n: \left({s_1, \ldots, s_n}\right) := \begin{cases} \phi_1 \left({s_1}\right) & : n = 1 \\ \left({\phi_1 \left({s_1}\right), \phi_2 \left({s_2}\right)}\right) & : n = 2 \\ \left({\Phi_n \left({s_1, \ldots, s_{n - 1} }\right), \phi_n \left({s_n}\right)}\right) & : n > 2 \\ \end{cases}$

That is:

$\Phi_n: \left({s_1, \ldots, s_n}\right) := \left({\phi_1 \left({s_1}\right), \phi_2 \left({s_2}\right), \ldots, \phi_n \left({s_n}\right)}\right)$

Let $\phi_k: \left({S_k, \circ_k}\right) \to \left({T_k, \ast_k}\right)$ be a homomorphism for each $k \in \left\{{1, 2, \ldots, n}\right\}$.

Then $\Phi_n$ is a homomorphism from $\left({\mathcal S_n, \circledcirc_n}\right)$ to $\left({\mathcal T_n, \circledast_n}\right)$.


Proof by induction:

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

$\Phi_n: \left({\mathcal S_n, \circledcirc_n}\right) \to \left({\mathcal T_n, \circledast_n}\right)$ is a homomorphism.

Basis for the Induction

$P \left({1}\right)$ is true, as this just says:

$\Phi_1 = \phi_1: \left({S_1, \circ_1}\right) \to \left({T_1, \ast_1}\right)$ is a homomorphism

which holds by hypothesis.

$P \left({2}\right)$ is the case:

$\Phi_2 = \phi_1 \times \phi_2: \left({S_1 \times S_2, \circledcirc_2}\right) \to \left({T_1 \times T_2, \circledast_2}\right)$ is a homomorphism

which has been proved in Homomorphism of External Direct Products.

This is our basis for the induction.

Induction Hypothesis

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

So this is our induction hypothesis:

$\Phi_m: \left({\mathcal S_m, \circledcirc_m}\right) \to \left({\mathcal T_m, \circledast_m}\right)$ is a homomorphism.

Then we need to show:

$\Phi_{m+1}: \left({\mathcal S_{m+1}, \circledcirc_{m+1}}\right) \to \left({\mathcal T_{m+1}, \circledast_{m+1}}\right)$ is a homomorphism.

Induction Step

This is our induction step:

Let $\left({s_1, \ldots, s_{m+1}}\right)$ and $\left({t_1, \ldots, t_{m+1}}\right)$ be arbitrary elements of $\mathcal S_{m+1}$.

\(\displaystyle \) \(\) \(\displaystyle \Phi_{m+1} \left({\left({s_1, \ldots, s_{m+1} }\right) \circledcirc_{m+1} \left({t_1, \ldots, t_{m+1} }\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \Phi_{m+1} \left({\left({\left({s_1, \ldots, s_m}\right), s_{m+1} }\right) \circledcirc_{m+1} \left({\left({t_1, \ldots, t_m}\right), t_{m+1} }\right)}\right)\) Definition of Cartesian Product
\(\displaystyle \) \(=\) \(\displaystyle \left({\Phi_m \left({\left({s_1, \ldots, s_m}\right) \circledcirc_m \left({t_1, \ldots, t_m}\right)}\right), s_{m+1} \circ_{m+1} t_{m+1} }\right)\) Definition of External Direct Product
\(\displaystyle \) \(=\) \(\displaystyle \left({\Phi_m \left({\left({s_1, \ldots, s_m}\right) \circledcirc_m \left({t_1, \ldots, t_m}\right)}\right), \phi_{m+1} \left({s_{m+1} }\right) \ast_{m+1} \phi_{m+1} \left({t_{m+1} }\right) }\right)\) $\phi_{m+1}$ is a Homomorphism
\(\displaystyle \) \(=\) \(\displaystyle \left({\Phi_m \left({s_1, \ldots, s_m}\right) \circledast_m \Phi_m \left({t_1, \ldots, t_m}\right), \phi_{m+1} \left({s_{m+1} }\right) \ast_{m+1} \phi_{m+1} \left({t_{m+1} }\right) }\right)\) Induction Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \Phi_{m+1} \left({s_1, \ldots, s_m, s_{m+1} }\right) \circledast_{m+1} \Phi_{m+1} \left({t_1, \ldots, t_m, t_{m+1} }\right)\) Definition of External Direct Product

So $P \left({m}\right) \implies P \left({m+1}\right)$ and the result follows by the Principle of Mathematical Induction.


$\forall n \in \N_{>0}: \Phi_n: \left({\mathcal S_n, \circledcirc_n}\right) \to \left({\mathcal T_n, \circledast_n}\right)$ is a homomorphism.