Set is Countable if Cardinality equals Cardinality of Countable Set
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$