Surjection from Natural Numbers iff Countable/Corollary 1

Theorem

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$.

Proof

Let $g: T \to \N$ be a bijection from $T$ to $\N$.

By Inverse of Bijection is Bijection, $g^{-1}: \N \to T$ is a bijection from $\N$ to $T$.

Necessary Condition

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

By Composite of Surjections is Surjection, $f \circ g^{-1}:\N \to S$ is a surjection.

By Surjection from Natural Numbers iff Countable, $S$ is a countable set.

$\Box$

Sufficient Condition

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

By Surjection from Natural Numbers iff Countable, there exists a surjection $f: \N \to S$.

By Composite of Surjections is Surjection, $f \circ g:T \to S$ is a surjection.

$\blacksquare$