Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been trying to find a way to consistently generate bijections between $\mathbb{N}$ and countable sets of Real numbers in $[0,1]$. Given any such set, by definition there is a bijection to the natural numbers, but I am wondering about a general method that can be used for any such set.

The best idea I had so far is the following: Choose a bijection $f: \mathbb{N}\to\mathbb{Q}\cap[0,1]$ such that $f(1)=0$ and $f(2)=1$. I will attempt to use this bijection to construct, from a countable set $X$ of real numbers in $[0,1]$, a list $x_1,x_2,x_3\dots$ containing every number in $X$. At any step $n\ge2$, the set $\{f(1),f(2)\dots f(n)\}$ partitions the interval $[0,1]$ into a finite number of intervals. At the $n$th step, then, proceed as follows: If $f(n)\in X$, append $f(n)$ to the list. Then, some interval in the partition of $[0,1]$ generated by $\{f(1),f(2)\dots f(n-1)\}$ has been split by $f(n)$ into two intervals $A$ and $B$. If either $A$ or $B$ contains only a finite number of points from $X$, order the points in that set by the standard order on the real numbers, and append the elements of that set to the list. If both $A$ and $B$ contain only a finite number of points, then $A\cup B\cup f(n)$ does as well, so the numbers have already been added and can be ignored.

It seems like this could work. Specifically, it works on such countable subsets as $\{0\}\cup\{1/n:n\in\mathbb{N}\}$ (or on similar subsets of irrational numbers). However, I have no idea how I could show that it works. Can anyone show that this does/does not work? Does anyone know a better method for ordering countable subsets of $[0,1]$?


share|cite|improve this question
One set that your construction doesn't work on is $X=\{x\in[0,1]\mid \sqrt 2-x \in \mathbb Q\}$. Then each of your intervals will always contain infinitely many points, and you never get to add anything to your enumeration. – Henning Makholm Jan 15 '12 at 21:41
@HenningMakholm, Carl: Should think be tagged with [axiom-of-choice]? I'm not sure, but I tend to favor. If one of you (or any other reader) thinks that it should be, please tag it as such. – Asaf Karagila Jan 16 '12 at 0:16
Sure, just added it. – Carl Jan 16 '12 at 6:50
up vote 5 down vote accepted

If you want to find a definable way to describe bijections between countable subsets of $[0,1]$ and $\mathbb N$ there is none, unless you are willing to use the axiom of choice (to some degree at least), with it this is quite the black box since we can just choose a bijection in advance and finish. Otherwise, we may not be able to have this.

This should not be very surprising since there are only countably many ways to nicely define something, while there are continuum many of these subsets. This means that not many of those can be caught under such a uniform description of a bijection.

As I mention this requires some choice. Why? It requires the axiom of choice to have that there is a sequence of bijections between every countable ordinal and $\mathbb N$, although these sets are countable, choosing a bijection for each ordinal is impossible without the axiom of choice.

Even without the axiom of choice every countable ordinal is embeddable in $\mathbb Q$, and therefore in $\mathbb Q\cap[0,1]$. If one could just define nicely such bijections, one could construct the sequence of bijections without the use of the axiom of choice; contradiction the theorem that it is possible to have a model of set theory in which there is no sequence like this.

The consequence of the last two paragraphs is that without using the axiom of choice one cannot just have a uniform way of defining bijections between $\mathbb N$ and countable subsets of $[0,1]$, where by uniform way I mean of course $\varphi:\big\{A\subseteq[0,1]\big| |A|=\aleph_0\big\}\to[0,1]^\mathbb N$ which sends each countable subset to a bijection.

For the last matter, I refer you to this question on MathOverflow which essentially asks the same question - whether or not we can choose bijections for every countable subset, the answer is of course not without choice.

share|cite|improve this answer
I think what the question asks for is proof that there exists a function $\phi:\mathcal P([0,1])\to \mathbb N \to [0,1]$ such that $\phi(X)$ is a bijection $\mathbb N\to X$ whenever $X\subseteq [0,1]$ is countable. Which is easy enough given AC, but appears to be nontrivial without it. – Henning Makholm Jan 15 '12 at 21:50
@Henning: I think that the 4th part answers that, no? – Asaf Karagila Jan 15 '12 at 22:05
well, yes, but "nicely decribed" is not very rigorous. Under my interpretation of the question, it would be okay if $\phi$ mapped a "not nicely described" $X$ to a "not nicely described" bijection, and then your counting argument seems to be unavailable. – Henning Makholm Jan 15 '12 at 22:12
@Henning: But my AC argument still holds. – Asaf Karagila Jan 15 '12 at 22:16
My goal was to show that there exists a function $\phi:\mathcal P(\mathbb N \to [0,1]) \to \{\mathbb N \to [0,1]\}$ that is a bijection on the countable subsets without using the axiom of choice. It seems like that is impossible though according to Asaf's last comment. – Carl Jan 15 '12 at 22:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.