Power of Element/Semigroup

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \oplus}$ be a magma.

Let $a \in S$.

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

Let $\tuple {a_1, a_2, \ldots, a_n}$ be the ordered $n$-tuple defined by $a_k = a$ for each $k \in \N_n$.


Then:

$\displaystyle \bigoplus_{k \mathop = 1}^n a_k = \oplus^n a$

where:

$\displaystyle \bigoplus_{k \mathop = 1}^n a_k$ is the composite of $\tuple {a_1, a_2, \ldots, a_n}$ for $\oplus$
$\oplus^n a$ is the $n$th power of $a$ under $\oplus$.


Proof

The proof will proceed by the Principle of Mathematical Induction on $\N$.

Let $T$ be the set defined as:

$\displaystyle T := \set {n \in \N: \bigoplus_{k \mathop = 1}^n a_k = \oplus^n a}$


First, recall the definition of the composite of $\tuple {a_1, a_2, \ldots, a_n}$ for $\oplus$:

$\displaystyle \bigoplus_{k \mathop = 1}^n a_k = \begin{cases} a: & n = 1 \\ \map {\oplus_m} {a_1, \ldots, a_m} \oplus a_{m + 1}: & n = m + 1 \end{cases}$


Secondly, recall the definition of the $n$th power of $a$ under $\oplus$:

$\forall n \in \N_{>0}: \oplus^n a = \begin{cases} a & : n = 1 \\ \paren {\oplus^m a} \oplus a & : n = m + 1 \end{cases}$


Basis for the Induction

We have that:

\(\displaystyle \bigoplus_{k \mathop = 1}^1 a_k\) \(=\) \(\displaystyle a_1\) Definition of Composite of $\paren {a_1}$
\(\displaystyle \) \(=\) \(\displaystyle a\) Definition of $\tuple {a_1, a_2, \ldots, a_n}$: $\forall k \in \N_n: a_k = a$
\(\displaystyle \) \(=\) \(\displaystyle \oplus^1 a\) Definition of Power of Element of Semigroup


So $1 \in T$.

This is our basis for the induction.


Induction Hypothesis

It is to be shown that, if $j \in T$ where $j \ge 1$, then it follows that $j + 1 \in T$.

This is the induction hypothesis:

$\displaystyle \bigoplus_{k \mathop = 1}^j a_k = \oplus^j a$


It is to be demonstrated that it follows that:

$\displaystyle \bigoplus_{k \mathop = 1}^{j + 1} a_k = \oplus^{j + 1} a$


Induction Step

This is our induction step:


\(\displaystyle \bigoplus_{k \mathop = 1}^{j + 1} a_k\) \(=\) \(\displaystyle \map {\oplus_j} {a_1, \ldots, a_j} \oplus a_{j + 1}\) Definition of Composite of $\left({a_1, \ldots, a_j, a_{j+1} }\right)$
\(\displaystyle \) \(=\) \(\displaystyle \paren {\bigoplus_{k \mathop = 1}^j a_k} \oplus a_{j + 1}\) Definition of Composite of $\tuple {a_1, \ldots, a_j}$
\(\displaystyle \) \(=\) \(\displaystyle \paren {\oplus^j a} \oplus a_{j + 1}\) Induction Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \paren {\oplus^j a} \oplus a\) Definition of $\tuple {a_1, a_2, \ldots, a_{j + 1} }$: $\forall k \in \N_{j + 1}: a_k = a$
\(\displaystyle \) \(=\) \(\displaystyle \oplus^{j + 1} a\) Definition of Power of Element of Semigroup


So $k \in T \implies k + 1 \in T$ and the result follows by the Principle of Mathematical Induction:

$\displaystyle \forall n \in \N: \bigoplus_{k \mathop = 1}^n a_k = \oplus^n a$


Notation

Let $\paren {S, \circ}$ be a semigroup.

Let $a \in S$.

Let $\circ^n a$ be the $n$th power of $a$ under $\circ$.


The usual notation for $\circ^n a$ in a general algebraic structure is $a^n$, where the operation is implicit and its symbol omitted.

In an algebraic structure in which $\circ$ is addition, or derived from addition, this can be written $n a$, that is, $n$ times $a$.


Thus:

$a^1 = \circ^1 a = a$

and in general:

$\forall n \in \N_{>0}: a^{n + 1} = \circ^{n + 1} a = \paren {\circ^n a} \circ a = \paren {a^n} \circ a$


When the operation is addition of numbers or another commutative operation derived from addition, the following symbology is often used:

$n a = \begin{cases} a & : n = 1 \\ \paren {n - 1} a + a & : n > 1 \end{cases}$

Sometimes, for clarity, $n \cdot a$ is preferred to $n a$.


Sources