# countable-to-one set cardinality

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

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.
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$$.