Let $B$ and $C$ be nonempty sets. Say a map $ \phi : B\to C$ is countable-to-one if for every $c \in C, \phi^{-1}(\{c\})$ is countable. Show that if such a map exists then $|B| \leq \aleph_0|C|.$

Observe that $B = \cup_{c\in C} \phi^{-1}(\{c\})$ ($\phi^{-1}(\{c\})\subseteq B$ for each $c\in C$ and for $b \in B, \phi(b) \in C,$ so $b \in \phi^{-1}(\{\phi(b)\})$) and this union is disjoint since $\phi^{-1}(\{c\})\cap \phi^{-1}(\{d\}) = \emptyset$ for $c\neq d.$ Since each $\phi^{-1}(\{c\})$ is countable, it is either finite or equipotent to $\mathbb{N}$; in either case there is an injection $f_c : \phi^{-1}(\{c\})\to \mathbb{N}$ for each $c\in C$. Define $f : B\to \mathbb{N}\times C, f(d) = (f_c(d), c)$ for $d \in \phi^{-1}(\{c\}), c \in C.$ Observe that $f$ is an injection. Indeed, for any $d\neq e\in B,$ we have two cases: $1) d , e \in \phi^{-1}(\{c\}), c \in C$ or $2) d\in \phi^{-1}(\{g\}), e \in \phi^{-1}(\{h\}), g\neq h \in C.$ In case $1), $ since $d\neq e$ and $f_c$ is an injection, $f_c(d) \neq f_c(e),$ so $f(e) = (f_c(e), e)\neq (f_c(d), c) = f(d).$ Now in case $2), f(d) = (f_g(d), g)\neq (f_h(e), h)$ as $g\neq h.$ Thus $f$ is an injection so $|B|\leq |\mathbb{N}||C| = \aleph_0|C|.$

Is this incorrect (i.e. some parts are incorrect)?


2 Answers 2


I like the idea, but I think your notation in cases 1 and 2 is confusing and sometimes is wrong. For example, you say case 2 is about $d\in\phi^{-1}(\{c\}),e\in\phi^{-1}(\{d\})$, but how can $d$ be an element of $B$ (first part of case 2) and an element of $C$ (second part of case 2) at the same time?

In my opinion you're doing it more complicated than it is: You have an injection $f_c:\phi^{-1}(\{c\})\to\Bbb N$ for each $c\in C$, so you can define $f:B\to\Bbb N\times C$ for each $b\in B$ as $(f_{\phi(b)}(b),\phi(b))$. If you have $b,b'\in B$ such that $(f_{\phi(b)}(b),\phi(b))=(f_{\phi(b')}(b'),\phi(b'))$ then $\phi(b)=\phi(b')$ and therefore $f_{\phi(b)}(b)=f_{\phi(b')}(b')=f_{\phi(b)}(b')$. Since $f_{\phi(b)}$ is an injection, then $b=b'$, so $f$ is an injection.

But, as I said, the idea is good and you solved the problem.


Your function $f$ is fine, but in Case $(2)$ you’re using $d$ for two different things at once. You want $d\in\varphi^{-1}(\{c_1\})$ and $e\in\varphi^{-1}(\{c_2\})$ for distinct $c_1,c_2\in C$. Then you have

$$f(d)=\langle f_{c_1}(d),c_1\rangle\ne\langle f_{c_2}(e),c_2\rangle=f(e)\,,$$

since $c_1\ne c_2$. Once you fix that, $f$ is indeed an injection from $B$ to $\Bbb N\times C$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .