# Set Finite iff Surjection from Initial Segment of Natural Numbers

## Theorem

Let $S$ be a set.

Then $S$ is finite if and only if for some $n \in \N$ there exists a surjection $f: \N_{< n} \to S$.

Here, $\N_{< n}$ denotes an initial segment of $\N$.

## Proof

### Necessary Condition

Suppose that $S$ is finite.

By definition, this means there exists a bijection $f: \N_{< n} \to S$.

Then $f$ is a fortiori also the sought surjection.

$\Box$

### Sufficient Condition

Let $f: \N_{< n} \to S$ be a surjection.

Define $g: S \to \N_{< n}$ by:

- $g (s) := \min f^{-1} (s)$

where $f^{-1} (s)$ is the preimage of $s$ under $f$.

Note that $f^{-1} (s)$ is not empty because $f$ is a surjection.

By the Well-Ordering Principle, $f^{-1} (s) \subseteq \N$ has a smallest element.

Hence $g$ is well-defined.

Next we show that $g$ is injective.

So suppose that $g(s) = g(s')$ for some $s, s' \in S$:

\(\ds g(s)\) | \(=\) | \(\ds g(s')\) | ||||||||||||

\(\ds \implies \ \ \) | \(\ds f \left({ g(s) }\right)\) | \(=\) | \(\ds f \left({ g(s') }\right)\) | |||||||||||

\(\ds \implies \ \ \) | \(\ds s\) | \(=\) | \(\ds s'\) | Definition of $g$ |

Hence $g$ is injective.

Then by Injection to Image is Bijection, $S$ is equivalent to a subset of $\N_{<n}$.

By Subset of Finite Set is Finite, it follows that $S$ is finite.

$\blacksquare$

## Sources

- 2000: James R. Munkres:
*Topology*(2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 6$: Finite Sets: Corollary $6.7$