In one of my classes I was asked to prove the following theorem.
Given a set $A$, which is a infinite set, another set $B$, which is a subset of $\mathbb{N}$.
If there exists a function/map $f$ s.t. $f: B\to A$, the function $f$ is onto. Then the set $A$ is countable.
Our definition of countable is that a set $X$ is countable if and only if it is numerically equivalent to any subset of $\mathbb{N}$.
Our definition of numerical equivalence is that the set $X$ is numerically equivalent to the set $Y$ if there exists a map $g$ s.t. $g: X\to Y$, which is one-one(injective) and onto(surjective).
Here is my proof:
Consider any element $a$ from $A$. Since $f$ is onto, then there exists a set of inverse image of $a$, call this set $F(a)$.
-
If $F(a)$ has only one element, then we proceed to the another element from $A$, and consider its inverse image.
-
If $F(a)$ has more than one elements, then take the least element from $F(a)$, then processed to another element from $A$.
Iterating this process for all the elements of $A$. We have a set $F(A)$ which is the set of all the inverse image of $A$ satisfying the above conditions.
Define a map $F: A\to F(A)$, then $F$ is both one-one and onto. Thus $A$ is numerically equivalence to $F(A)$ which is a subset of $\mathbb{N}$. Thus the set $A$ is countable.
Is my proof rigorous? If not, can anyone kindly show me how to do this rigorously?
Our professor also mentions we can prove this through Axiom of Choice, but I have no idea how to do that since this is a real-analysis course, and we are not required to do it.
Best Answer
Cardinality is measured by bijections.Since set A is infinite,and we have a surjection from set B to set A,then set B has to have at least as much elements as A(greater than or equal cardinality).Namely $|A| \leq |B|$
Now a fact is that least infinite cardinal is $\aleph_0$ and it is cardinality of natural numbers.
Now we use a fact that any infinite subset of natural numbers is countable to conclude following: $$|\mathbb N|=\aleph_0=|B|$$
Also for any infinite set $X$ it holds that $\aleph_0 \leq |X|$
From equation : $$\aleph_0 \leq |A| \leq |B| = \aleph_0 $$ thus by Bernstein-Schroder theorem we conclude that set A is countable.
If you want justification of any of above results,please leave a comment.They are pretty basic results about infinities