Answer to Question #148130 in Discrete Mathematics for Promise Omiponle

Question

Let A be a countable set, and B is another set. Assume further that there exists an onto function f:A->B. Is B necessarily countable? Provide a full justification for your answer.

Answer 1

How the proof proceeds depends on how you define "countable". A nonempty set $B$

is countable if either:

1) there exists a one-to-one function $f:B\to \mathbb{N}$

or

2) there exists an onto function $g:\mathbb{N} \to B$

It turns out these are equivalent, so go with the second.

Since $A$ is countable there exists an onto function $g:\mathbb{N}\to A$ , and by hypothesis there is an onto function $f:A\to B$ . The composition $f ∘g:\mathbb{N}\to B$  is onto, so that B

B is countable.