7
$\begingroup$

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 :)

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ exactly what I was thinking as I was reading this! $\endgroup$
    – DanZimm
    Apr 1 '13 at 2:08
  • 1
    $\begingroup$ @DanZimm, great minds think alike ;-) $\endgroup$
    – vonbrand
    Apr 1 '13 at 2:08
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.