Image of Countable Set under Mapping is Countable
Jump to navigation
Jump to search
Definition
Let $S$ be a countable set.
Let $T$ be a set.
Let $f: S \to T$ be a mapping.
Then the image of $f$ is countable.
Proof
Let $A$ be the image of $f$.
Let $g: S \to A$ be the restriction of $f$ to the cartesian product $S \times A$.
By Surjection by Restriction of Codomain, $g$ is a surjection.
By Surjection from Natural Numbers iff Countable, there exists a surjection $\phi: \N \to S$.
Since the composition of surjections is a surjection, $g \circ \phi: \N \to A$ is a surjection.
Hence, by Surjection from Natural Numbers iff Countable, it follows that $A$ is countable.
$\blacksquare$