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

  • 2
    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.2012-01-15
  • 0
    @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.2012-01-16
  • 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
    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.2012-01-15
  • 0
    @Henning: I think that the 4th part answers that, no?2012-01-15
  • 0
    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.2012-01-15
  • 0
    @Henning: But my AC argument still holds.2012-01-15
  • 0
    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.2012-01-15
  • 0
    @Carl: I edited the answer, and referred to a question I asked on MO a while ago with essentially asks the same. The answer, as I say here - not without choice.2012-01-15
  • 0
    @Asaf: Perhaps. I see that it could work if you can choose a particular embedding of each countable ordinal into $\mathbb Q$ all at once. But if you could do that, just a single enumeration of $\mathbb Q$ would let you reach a contradiction without using my hypothesized $\phi$.2012-01-15
  • 0
    @Henning: It would still require choice. In fact, it requires more choice than one needs to choose an embedding for every countable ordinal.2012-01-15
  • 0
    @Carl, so your function takes as input a _set_ of sequences in $[0,1]$ and produces as output a single sequence? I have trouble connecting that to your description. Where does your $X$ enter that picture?2012-01-15
  • 0
    @Henning, that was the overall goal. With this question, I was trying to figure out if I could use some consistent way of ordering in able to generate the bijection I mentioned in the comment, since if I have a way to order that countable set of real numbers, I can list them and easily create a bijection to a single such function. Otherwise, I would have to simply say that there exists some such ordering since I know its countable, and choose one for each set using AoC.2012-01-15
  • 0
    @Asaf: Do you have a particular argument for that in mind? If I understand you correctly, you claim that you can use $\phi$ to choose an embedding for each countable ordinal, but it is not clear to me how you would go about that. (Note that it is easy to find a $\phi$ that works for $[0,1]\cap\mathbb Q$, and I don't see where in your argument you use the hypothesis that $\phi$ works for the continuum in general).2012-01-15
  • 0
    @Henning If such choice of bijections exists the countable union of countable ordinals is countable. This may not be true without the axiom of choice.2012-01-15
  • 0
    @Asaf, but how do you get from "$\phi$ exists" to "such choice of bijection exists"? (I assume by the latter you mean a choice of $\mathbb Q$-embeddings for all countable ordinals. Otherwise, I must confess to being completely confused).2012-01-15
  • 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