# Principle of Mathematical Induction/Naturally Ordered Semigroup

## Theorem

Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.

Let $T \subseteq S$ such that $0 \in T$ and $n \in T \implies n \circ 1 \in T$.

Then $T = S$.

### General Result

Let $\struct {S, \circ, \preceq}$ be a naturally ordered semigroup.

Let $p \in S$.

Let $T \subseteq S$ such that:

- $x \in T \implies p \preceq x \land \paren {x \in T \implies x \circ 1 \in T}$

Then:

- $S \setminus S_p \subseteq T$

where:

- $\setminus$ denotes set difference
- $S_p$ denotes the set of all elements of $S$ preceding $p$.

## Proof

Aiming for a contradiction, suppose that $T \subsetneq S$.

That is, $T$ is a proper subset of $S$:

- $T \ne S$

Let $T' = S \setminus T$.

Then by Set Difference with Proper Subset:

- $T' \ne \O$

By axiom $NO1$, $S$ is well-ordered.

By definition of well-ordered set, it follows that $T'$ has a smallest element $x$.

By definition of $T$:

- $0 \in T$

and so by definition of $T'$:

- $0 \notin T'$

so:

- $0 \prec x$

By Sum with One is Immediate Successor in Naturally Ordered Semigroup:

- $1 \preceq x$

By the definition of a naturally ordered semigroup:

- $\exists y \in S: y \circ 1 = x$

Again by Sum with One is Immediate Successor in Naturally Ordered Semigroup:

- $y \prec x$

We have that $x$ is the smallest element of $T'$ and $y \prec x$.

Therefore:

- $y \notin T'$

and so

- $y \in T$

But from the definition of $T$:

- $y \in T \implies y \circ 1 = x \in T$

But then by the definition of $T'$:

- $x \in T' \implies x \notin T$

From this contradiction, it follows that:

- $T = S$

$\blacksquare$

## Also see

## Sources

- 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): $\S 16$: Theorem $16.5$