Surjection from Natural Numbers iff Countable

Theorem

Let $S$ be a non-empty set.

Then $S$ is countable if and only if there exists a surjection $f: \N \to S$.

Corollary 1

Let $T$ be a countably infinite set.

Let $S$ be a non-empty set.

Then $S$ is countable if and only if there exists a surjection $f: T \to S$.

Corollary 2

Let $T$ be a countably infinite set.

Let $S$ be an uncountable set.

Let $f:T \to S$ be a mapping.

Then $f$ is not a surjection.

Proof

Necessary Condition

Suppose that $f: \N \to S$ is a surjection.

By Surjection from Natural Numbers iff Right Inverse, $f$ admits a right inverse $g: S \to \N$.

We have that $g$ is an injection by Right Inverse Mapping is Injection.

Hence the result, by the definition of a countable set.

$\Box$

Sufficient Condition

Suppose that $S$ is countable and non-empty.

Then there is an injection $g: S \to \N$.

By Injection has Surjective Left Inverse Mapping, there is a surjection $f: \N \to S$.

$\blacksquare$

Law of the Excluded Middle

This theorem depends on the Law of the Excluded Middle, by way of Injection has Surjective Left Inverse Mapping.

This is one of the axioms of logic that was determined by Aristotle, and forms part of the backbone of classical (Aristotelian) logic.

However, the intuitionist school rejects the Law of the Excluded Middle as a valid logical axiom.

This in turn invalidates this theorem from an intuitionistic perspective.

Sources

• 2000: James R. Munkres: Topology (2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 7$: Countable and Uncountable Sets: Theorem $7.1$