While reading the section on countability from Ralph Boa's book 'A Primer on real functions', I came across this sentence 'While those sets cannot be counted can be thought of 'bigger' than those that can be counted. This made me wonder if the following is true 'For any countable set A and an u countable set B, does there exist an injection from A to B?

Now my above conjecture obviously reduces to commenting on existence of injection from $\mathbb{N}$ to $B$(as defined above ), as any countable set has a bijection with the set of natural numbers . Now I am unable to proceed. Please help.Thanks.


We define $f\colon \Bbb N\to B$ by recursion - and a bit of choice:

Let $n\in\Bbb N$. Assume we have already defined $f(k)$ for all $k\in\Bbb N$ and $k<n$. Then the set $B_n:=\{\,f(k)\mid k<n\,\}$ is a finite subset of $B$. As $B$ is not countable, certainly $B_n\subsetneq B$ and there exists an element $y\in B\setminus B_n$. Define $f(n)=y$.

In the end, this defines an injective map $f\colon \Bbb N\to B$. (This map is certainly not surjective as $B$ was assumed uncountable)


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.