If A is a denumerable set, and there exists a surjective function from A to B, then B is denumerable

Question

I am having some trouble solving the following homework question and some help would be greatly appreciated!!

Q: Prove that if $A$ is a denumerable set, and there exists a surjective function from $A$ to $B$, then $B$ is denumerable.

My intuition:

Since $A$ is denumerable, we can write $A$ as ${a1,a2,a3...}$. Furthermore, since there is a surjective function from $A$ to $B$, then every element of $B$ is mapped to an element of $A$. Thus, it makes sense to say that since $A$ is denumerable and every element of $B$ is being mapped to $A$, then $B$ is denumerable. Thus, we can write $B$ as ${b1,b2,b3...}$.

This seems logical however I feel as though it is not a complete and mathematical proof. Help would be greatly appreciated to make this informal reasoning more in line with what mathematicians expect!

Thank you :)

Answer 1

The case $A=\emptyset $ is trivial, so we may dispose of it. Based on the formulation of what you are trying to prove, it seems the meaning of denumerable for you is that of a set that is either finite or has the same cardinality as $\mathbb N$. So, prove first that a set $S\ne \emptyset $ is denumerable if, and only if, there exists a surjection $f:\mathbb N \to S$.

Now, if $g:A\to B$ is surjective and $A$ is denumerable, then there exists a surjection $f:\mathbb N \to A$. The composition of surjective functions is surjective, thus $g\circ f:\mathbb N \to B$ is a surjection, so $B$ is denumerable.

Answer 2

There is a surjective function $f \colon \mathbb{N} \to A$, and another one $g \colon A \to B$. Then the composition $g \circ f \colon \mathbb{N} \to B$ is also surjective, and so $B$ is denumerable.

Answer 3

You are definitely on the right track here. However, what you have failed to consider for this proof to be complete is what to do with the elements of $B$ mapped to by several elements of $A$.

As an example, let's call the surjective function $f$, and let's say $f(a_1) = f(a_2) = f(a_3)$. Then your $b_1, b_2$ and $b_3$ will be the same element, and what you have is not really an indexing of $B$.

To counteract this, set $b_1 = f(a_1)$, then for each new index $i$ you can say that $b_i$ is $f(a_j)$ where $j$ is the lowest index such that $f(a_i)\in B$ has not yet been assigned an index.

Now to show that you have indexes on all elements of $B$, take any one of them (let's say the element $b$). This is mapped to by $f$, so the set $f^{-1}(\{b\})$ is non-empty. Thus there has to be a lowest index $k$ such that $f(a_k) = b$. By the method of giving elements of $B$ indices, by the time you got to $k$, you must have given an index to $b$. And there you go, $b$ has an index.

Of course, indexing of the set $B$ is really just a bijection with (possibly a finite subset of) $\Bbb N$, which is what denumerability is all about.

Answer 4

You can simplify your proof by creating a surjection $f : \mathbb N \to B$ which is the composite map $g \circ h$ where $h : \mathbb N \to A$ and $g : A \to B$.

However, to be denumerable (this, I take to mean at most countable, since $f = ( x \in A \mapsto 1 )$ is a surjective map from $A \to \{ 1 \}$), your instructor may define it as requiring an injection from $B$ to $\mathbb N$.

So take the preimage $f^{-1}(b)$ for each $b \in B$ and select the smallest natural number $n$ mapped to $b$. You can verify that the function $F(b) = \min ( f^{-1}(b) )$ is an injection.

Answer 5

Proposition 3 and Proposition 4 below takes care of what Ittay Weiss left as an exercise in his answer.

---

Proposition 1: Let $h : \mathbb{N} \to S$ be a surjective mappping that is injective on the initial segment $[0,n]$. If $h([0,n]) \ne S$ then there exist a surjective $h^{'} : \mathbb{N} \to S$ that agrees with $h$ on $[0,n]$ and is injective on $[0,n+1]$ satisfying $h([0,n+1]) \subset h^{'}([0,n+1]) $.
Proof
Let $m \gt n$ be smallest integer such that $h(m) \notin h([0,n])$. If $m = n+1$ then $h$ restricted to $[0,n+1]$ is injective and there is nothing to do. Otherwise, the transposition $\sigma = (n+1 \;\;\;\; m)\;$ is a (simple) bijective transformation of $\mathbb{N}$. It is easy to argue that defining $h^{'} = h \circ \sigma$ completes the proof. $\qquad \blacksquare$

Definition: A surjective mapping $f : \mathbb{N} \to S$ is said to be surjective at infinity if for all $n \in \mathbb{N}$ $f([0,n]) \ne S$.

Proposition 2: Let $h : \mathbb{N} \to S$ be surjective at infinity and injective on the initial segment $[0,n]$. Then there exist a surjective at infinity function $h^{'} : \mathbb{N} \to S$ that agrees with $h$ on $[0,n]$ and is injective on $[0,n+1]$ satisfying $h([0,n+1]) \subset h^{'}([0,n+1])$.
Proof: Adapt the proof of Proposition 1 to this setting.

Proposition 3: Let $f : \mathbb{N} \to S$ be surjective at infinity. Then there exists a bijective correspondence between $\mathbb{N}$ and $S$.
Proof
Let $f_0$ denote $f$, a trivially injective function on the singleton $[0,0]$. By the above arguments, it is easy to see that there is a sequence of functions $f_n$ each injective on the initial segment $[0,n]$. Let ${f_n}^{'}$ denote $f_n$ restricted to $[0,n]$. Everything is in place to take the inductive (direct) limit of the ${f_n}^{'}$, defining a function $\bar f : \mathbb{N} \to S$. It is easy to check that $\bar f$ is a bijection. $\qquad \blacksquare$

Proposition 4: Let $f: \mathbb{N} \to S$ be surjective and $N \ge 0$ be given so that $f([0,N]) = S$. Then there exist a $n \le N$ and a bijective function $\bar f$ that maps $[0,n]$ to $S$.
Proof: Exercise.