Principle of Finite Induction/One-Based/Proof 2
Jump to navigation
Jump to search
Theorem
Let $S \subseteq \N_{>0}$ be a subset of the $1$-based natural numbers.
Suppose that:
- $(1): \quad 1 \in S$
- $(2): \quad \forall n \in \N_{>0} : n \in S \implies n + 1 \in S$
Then:
- $S = \N_{>0}$
Proof
Let $T$ be the set of all $1$-based natural numbers not in $S$:
- $T = \N_{>0} \setminus S$
Aiming for a contradiction, suppose $T$ is non-empty.
From the Well-Ordering Principle, $T$ has a smallest element.
Let this smallest element be denoted $a$.
We have been given that $1 \in S$.
So:
- $a > 1$
and so:
- $0 < a - 1 < a$
As $a$ is the smallest element of $T$, it follows that:
- $a - 1 \notin T$
That means $a - 1 \in S$.
But then by hypothesis:
- $\paren {a - 1} + 1 \in S$
But:
- $\paren {a - 1} + 1 = a$
and so $a \notin T$.
This contradicts our assumption that $a \in T$.
It follows by Proof by Contradiction that $T$ has no such smallest element.
Hence it follows that $T$ can have no elements at all.
That is:
- $\N_{>0} \setminus S = \O$
That is:
- $S = \N_{>0}$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction: Theorem $1 \text{-} 2$