Let $B$ and $C$ be non-empty sets. A map $\varphi: B\to C$ is called countable-to-one if for every $c\in C$, $\varphi^{-1}(\{c\})$ is countable. Prove that if such a map exists then $|B|\le \aleph_0|C|$ .

My approach:

Need to prove that $B\preceq \mathbb{N}\times C$, i.e. that there exists an injection from $B$ to $\mathbb{N}\times C$.

Since $\varphi^{-1}(\{c\})$ is countable, there exists an injective function $f:\varphi^{-1}(\{c\})\to \mathbb{N}$. Let $F$ be the set of all fibers $\phi^{-1}(\{c\})$, for all $c\in C$. Let $g_c:\phi^{-1}(\{c\}) \to \mathbb{N}\times C$ be the function defined as $g(b)=(f(b),\phi(b))$, where $b$ is some element in $\varphi^{-1}(\{c\})$, unless $\varphi^{-1}(\{c\})$ is empty. Then $g_c$ is injective. Let $g:=\bigcup\limits_{c\in C} g_c$, then $g$ is the infinite union of injective functions. By the axiom of choice, $g$ is injective.

This implies that $|B|\le \aleph_0|C|$.

Please let me know if this proof is correct or not very much so.

  • 1
    $\begingroup$ I would avoid the notation that you are using with $c_n$ as $\varphi^{-1}({c})$ may be empty. Ideally you want to write an equation like $g(b)=\ldots$ but I suppose it is partly a matter of taste. Apart from that the proof seems to be correct. $\endgroup$ – theindigamer Sep 20 '17 at 4:07
  • $\begingroup$ I've edited my proof (also corrected some errors). $\endgroup$ – sequence Sep 20 '17 at 5:05
  • 1
    $\begingroup$ If the domain of the map $g:\phi^{-1}(\{c\})\subseteq B\to\mathbb N\times C$ is the set $\phi^{-1}(\{c\}),$ then all it shows is that $|\phi^{-1}(\{c\})|\le|\mathbb N\times C|$. $\endgroup$ – bof Sep 20 '17 at 6:29
  • 1
    $\begingroup$ We need a different injective $f_F:F\to \mathbb N$ for each different fiber $F=\varphi^{-1}\{c\}$ of $\varphi.$ Let $G$ be the set of fibers of $\varphi. $ For each $ F \in G$ let $h(F)$ be the set of injections from $F$ into $\mathbb N.$ The Axiom of Choice implies there exists a function $j $ on $G$ such that $j(F)\in h(F)$ for each $F\in G$.... Now let $f_F=j(F)$ . $\endgroup$ – DanielWainfleet Sep 20 '17 at 9:18
  • 1
    $\begingroup$ AC is not needed to prove $g$ is injective. That is immediate from the def'n of $g$.... AC is needed to prove $g$ EXISTS... For each fiber $F$ of $\varphi$ there is a non-empty set $h(F)$ of injections from $F$ into $\mathbb N.$ You need a choice-function $S$ on the set $G$ of all fibers of $\varphi$ such that $s(F)=f_F\in h(F)$ for each $F\in G.$ For $b\in B$ let $F_b=\varphi^{-1} \{\varphi(b)\}$ and let $g(b)=(f_{F_b}(b),\varphi(b))=$ $ (S(F_b)(b),\varphi(b)).$... The notation $S(F_b)(b)$ can be confusing (... $S(F_b)$ is a function)...) so I gave it another name $f_{F_b}$. $\endgroup$ – DanielWainfleet Sep 21 '17 at 6:26

Your Answer

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

Browse other questions tagged or ask your own question.