Transitive Relation Compatible with Semigroup Operation Relates Powers of Related Elements

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\mathcal R$ be a transitive relation on $S$ which is compatible with $\circ$.

Let $x, y \in S$ such that $x \mathrel{\mathcal R} y$.

Let $n \in \N_{>0}$ be a strictly positive integer.


Then:

$x^n \mathrel{\mathcal R} y^n$

where $x^n$ is the $n$th power of $x$.


Proof

We proceed by mathematical induction.


By definition of power:

$x^1 = x$
$y^1 = y$

Hence, by assumption:

$x^1 \mathrel{\mathcal R} y^1$


Suppose now that for $n \ge 1$:

$x^n \mathrel{\mathcal R} y^n$

Recall the assumption that $x \mathrel{\mathcal R} y$.

Applying Operating on Transitive Relationships Compatible with Operation to these relations yields:

$x^n \circ x \mathrel{\mathcal R} y^n \circ y$

By definition of power:

$x^{n+1} = x^n \circ x$

and:

$y^{n+1} = y^n \circ y$

The result follows by the Principle of Mathematical Induction.

$\blacksquare$