It is known that if $f:A\to B$ is injective, then the $\mathrm{Card}(A)\leq\mathrm{Card}(B)$. Similarly if $f$ is surjective, the opposite inequality holds. Can one please show me how to write down a rigorous proof for these facts?
In the particular case of one of the sets being the natural numbers $\mathbb{N}$, how can one proceed to show countability of the other set? Specifically, how to prove the following two statements?
- Suppose there exists a function $f:\mathbb{N}\to A$ which is
onto. This means that for every $x\in A$ there exists
$n\in\mathbb{N}$ such that $f(n)=x$. Prove that $A$ is countable. - Suppose there exists a function $f:A\to\mathbb{N}$ which is
one-to-one. This means that if $x$ and $y$ are in $A$ and $x\neq y$,
then $f(x)\neq f(y)$. Prove that $A$ is countable.
Best Answer
From the definition of cardinality, we can easily prove that if $\;\;A\subseteq B\;\;$then $\;\;Card\;(A)\le Card \;(B)\;.\;$ ( It follows from the fact that the inclusion function of $\;A\;$ is one-one.) ...............................................................................................(1)
Your first question can be answered as follows: Since $\;f\;\;$ is onto , we get , for each $\;\;x\in A\;,\;\;\;\;f^{-1}(x)\;\;$ is a non-empty subset of $\;\mathbb{N}\;.\;$ Since $\;\mathbb{N}\;$is well-ordered we get $\;\;f^{-1}(x)\;\;$ has a unique least element (say) $\;n_{x}\;.\;$ Thus the mapping $\;\theta\;:\;x \mapsto n_{x}\;\;$ is a bijection from $\;A\;$ to $\;\theta(A) \subseteq \mathbb{N}\;.\;$ Hence $\;\;Card\;(A)= Card \;(\theta(A)) \le Card(\mathbb{N}\;.\;$ Therefore $\;\;Card\;(A)\le Card\;(\mathbb{N})\;.\;$
To answer the second question, note that since $\;f\;$is one-one , for each $\;a\in A\;\;$ there is a unique element (say) $\;n_{a}\in \mathbb{N}\;.\;$
Thus the mapping $\;\eta\;:\;a \mapsto n_{a}\;\;$ is a bijection from $\;A\;$ to $\;\eta(A) \subseteq \mathbb{N}\;.\;$
Therefore, $\;\;Card\;(A)= Card \;(\eta(A)) \le Card(\mathbb{N})\;.\;$ Hence $\;\;Card\;(A)\le Card\;(\mathbb{N})\;.\;$