Induction on Well-Ordered Integral Domain

Theorem

Let $\left({D, +, \times, \le}\right)$ be a well-ordered integral domain.

Let the unity of $D$ be $1$.

Let $S \subseteq D$ be such that:

$1 \in S$

$a \in S \implies a + 1 \in S$

Then:

$D_+^* \subseteq S$

where $D_+^*$ denotes all the elements $d \in D$ such that $P \left({d}\right)$.

That is, $D_+^*$ is the set of all positive elements of $D$.

Proof

Let $S'$ be the set of all elements of $D_+^*$ that are not in $S$:

$S' = D_+^* \setminus S$

Suppose $S'$ is not empty.

Then as $D$ is well-ordered, it follows that $S'$ has a minimal element, which we will call $m$.

Then $m - 1 \notin S'$.

But $1 < m$ as $1 \in S$, and from One Succeeds Zero in Well-Ordered Integral Domain, $1$ is the minimal positive element of $D$.

So $0 < m - 1$ and so $m - 1$ is positive and, because not in $S'$, it follows that $m - 1 \in S$.

By construction of $S$ it follows that $m \in S$.

So $m \in S$ and $m \in S'$, i.e. $m \notin S$.

From this contradiction we deduced that there can therefore be no such $m$.

Hence $D_+^* \setminus S = \varnothing$, and from Set Difference with Superset is Empty Set it follows that $D_+^* \subseteq S$.

$\blacksquare$

Also see

This proof is (trivially) the same as the Principle of Finite Induction, but whereas this one takes as the basis the concept of the well-ordered integral domain, the latter proof uses the naturally ordered semigroup.

Both approaches are tantamount to the same thing, as they both lead (ultimately) to the uniqueness of the set of natural numbers $\N$ and also the set of integers $\Z$.

Sources

• C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 2.8$: Theorem $13$