Domain of Injection to Countable Set is Countable

Theorem

Let $X$ be a set, and let $Y$ be a countable set.

Let $f: X \to Y$ be an injection.

Then $X$ is also countable.

Proof

Since $Y$ is countable, there exists an injection $g: Y \to \N$.

From Composite of Injections is Injection, $g \circ f: X \to \N$ is also an injection.

That is, $X$ is countable.

$\blacksquare$