Domain of Injection to Countable Set is Countable

From ProofWiki
Jump to navigation Jump to search


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.


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.