Set is Countable if Cardinality equals Cardinality of Countable Set

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $X, Y$ be sets.

Let:

$\card X = \card Y$

where $\card X$ denotes the cardinality of $X$.


If $X$ is countable then $Y$ is countable.


Proof

Assume that $X$ is countable.

By definition of countable set there exists an injection:L

$f: X \to \N$

By definition of cardinality the sets $Y$ and $X$ are equivalent:

$Y \sim X$

Then by definition of set equivalence there exists a bijection:

$g: Y \to X$

By definition of bijection:

$g$ is an injection.

Hence by Composite of Injections is Injection:

$f \circ g: Y \to \N$ is an injection.

Thus by definition:

$Y$ is countable.

$\blacksquare$