Proper Subset of Finite Ordinal is Equivalent to Smaller Ordinal
Theorem
Let $n$ be a finite ordinal.
Let $x \subsetneq n$.
Then for some finite ordinal $m < n$:
- $m \sim x$
where $m \sim x$ denotes that $m$ is (set) equivalent to $x$.
That is, every proper subset of a finite ordinal $n$ is equivalent to some finite ordinal smaller than $n$.
Proof
Proof by induction:
For all finite ordinals $n$, let $P \left({n}\right)$ be the proposition:
- $x \subsetneq n \implies \exists m \in \N: m < n: m \sim x$
$P \left({0}\right)$ is vacuously true, as there are no proper subsets of $0 = \varnothing$.
This is our basis for the induction.
Induction Hypothesis
Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 0$, then it logically follows that $P \left({k^+}\right)$ is true.
So this is our induction hypothesis:
- $x \subsetneq k \implies \exists m \in \N: m < k: m \sim x$
Then we need to show:
- $x \subsetneq k^+ \implies \exists m \in \N: m < k^+: m \sim x$
Induction Step
This is our induction step:
Let $x \subsetneq k^+$.
Then either:
- $(1) \quad x \subsetneq k$, in which case the induction hypothesis applies
or:
- $(2) \quad x = k$, in which case the result is trivially true
or:
- $(3) \quad k \in x$.
In case $(3)$, we find a finite ordinal $j \in k$ such that $j \notin x$.
Then we define a mapping $f$ on $x$ as:
- $\forall i \in x: f \left({i}\right) = \begin{cases} i & : i \ne k \\ j & : i = k \end{cases}$
Clearly $f$ is injective and $f$ maps $x$ into $k$.
So the image of $x$ under $f$ is either equal to $k$ or by the induction hypothesis equivalent to some element of $k$.
Consequently, $x$ is always equivalent to some element of $k$.
So $P \left({k}\right) \implies P \left({k^+}\right)$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\forall n \in \N: x \subsetneq n \implies \exists m \in \N: m < n: m \sim x$
$\blacksquare$
Also see
Sources
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 13$: Arithmetic