I am trying to prove that the set $(0,1)$ is uncountable from "A First Course in Analysis by Yau". I have a question about a particular step.

In the text, the result is proved by contradiction. It is supposed that the set $(0,1)$ is countable, which it is then written that there must exist a bijection $f:\mathbb{N}\rightarrow (0,1)$ (which is ultimately contradicted).

My question is, why does the bijective map have to exist? If we suppose that $(0,1)$ is countable, shouldn't there exist an injective map $g:(0,1)\rightarrow\mathbb{N}$?

  • $\begingroup$ Well, if $f$ is a bijection, what is $f^{-1}$? $\endgroup$ – Asaf Karagila Jun 5 '20 at 13:12
  • $\begingroup$ @AsafKaragila meaning what is the map from $(0,1)\rightarrow\mathbb{N}$? $\endgroup$ – Steven Jun 5 '20 at 13:16
  • $\begingroup$ Meaning what kind of object is that? $\endgroup$ – Asaf Karagila Jun 5 '20 at 13:16
  • $\begingroup$ @AsafKaragila The preimage of $f$? $\endgroup$ – Steven Jun 5 '20 at 13:17
  • 1
    $\begingroup$ Be careful as to whether "Countable" means "countably infinite" or "countable but possibly finite". If you mean "countably infinite", then yes, a bijection must exist between $\mathbb N$ and $X$. $\endgroup$ – Prime Mover Jun 5 '20 at 13:33

There is a 1-1 correspondence between $A$ and $B$, if and only if a) there is an injection from $A$ to $B$ and b) at the same time there is an injection from $B$ to $A$.

So, if you can demonstrate that injection from $(0,1)$ to $\mathbb N$, then yes, you have demonstrated that $(0,1)$ is countable -- but more, you have proved it to be '''countably infinite'''.

  • $\begingroup$ So where does the bijection fit in? $\endgroup$ – Steven Jun 5 '20 at 13:21
  • $\begingroup$ It's a convenient short way to specify the definition of countability: there's an injection in both directions. So if you want to disprove a bijection, you just need to show that there cannot be an injection in one or other of the two directions. $\endgroup$ – Prime Mover Jun 5 '20 at 13:24
  • $\begingroup$ If there is an injection from $A$ to $\mathbb N$, then that proves that the cardinality of $A$ is at most countably infinite. If there is an injection from $\mathbb N$ to $A$, that proves that $A$ is at least countably infinite. So if there is an injection both ways, that is, that there is a bijection, that proves that $A$ is exactly countable infinite. $\endgroup$ – Prime Mover Jun 5 '20 at 13:26
  • $\begingroup$ Sorry, another note of confusion: "1-1 correspondence" is the same thing as "bijection", in case you didn't catch that. $\endgroup$ – Prime Mover Jun 5 '20 at 13:28
  • $\begingroup$ Oh hahah I get you now! $\endgroup$ – Steven Jun 5 '20 at 13:30

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.