1
$\begingroup$

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]$?

-Thanks

  • 0
    Sure, just added it.2012-01-16

1 Answers 1

5

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.

  • 0
    @Henning: Firstly, as the accepted answer to my MO question shows, it is possible to have that no $\phi$ as we look for here exists, but $DC(\omega_1)$ holds - which means we can choose for every countable ordinal a bijection with $\omega$ (and thus injection into $\mathbb Q$). As for the question how to get from $\phi$ to choice of bijections, thinking about it it no longer seems obvious. I will have to think about it a little bit before coming back with an answer.2012-01-16