# Construct a bijection from $\mathbb{R}$ to $\mathbb{R}\setminus S$, where $S$ is countable

Two questions:

1. Find a bijective function from $(0,1)$ to $[0,1]$. I haven't found the solution to this since I saw it a few days ago. It strikes me as odd--mapping a open set into a closed set.

2. $S$ is countable. It's trivial to find a bijective function $f:\mathbb{N}\to\mathbb{N}\setminus S$ when $|\mathbb{N}| = |\mathbb{N}\setminus S|$; let $f(n)$ equal the $n^{\text{th}}$ smallest number in $\mathbb{N}\setminus S$. Are there any analogous trivial solutions to $f:\mathbb{R}\to\mathbb{R}\setminus S$?

-
As far as 1.) is concerned, it is important to remember that bijections only necessarily preserve cardinality. Topological properties are irrelevant. –  user126 Jul 22 '10 at 1:15
@Jason: What you wrote has nothing to do with the axiom of choice. –  Andres Caicedo Jan 16 '11 at 19:09
@Jason: ${\mathbb R}\setminus{\mathbb N}$ obviously has the same size as ${\mathbb R}$; no choice is needed here, and so the same is true for any set of the form ${\mathbb R}\setminus S$, $S$ countable. On the other hand, $\omega_1$ does not inject into ${\mathbb R}$ without choice. –  Andres Caicedo Jan 16 '11 at 20:39
@Jason: What you are saying can be used to prove (without choice) something related: Given a real $r$, we can see it as coding a subset of $\omega$, either via a bijection ${\mathbb R}\to{\mathcal P}({\mathbb N})$, or using, say, continued fractions, or something like that. Anyway, we can then think of $r$ as coding a binary relation on $\omega$ (identifying naturals with pairs of naturals). If the relation is a well-ordering of type $\alpha$, map $r$ to $\alpha$. Else, map $r$ to $0$. This is a surjection of ${\mathbb R}$ onto $\omega_1$. (Cont.) –  Andres Caicedo Jan 16 '11 at 22:31
@Jason: But many reals will be mapped to the same ordinal, and without choice we do not have a canonical way of uniformly selecting one of these reals to form an injection $\omega_1\to{\mathbb R}$. In Solovay's model where all sets of reals are Lebesgue measurable, for example, there is no such injection. –  Andres Caicedo Jan 16 '11 at 22:33

The proof of the Schroeder-Bernstein theorem allows you to get a bijection for 1, since we have an injection $(0,1) \to [0,1]$ and a bijection $f: [0,1] \to [1/4, 3/4] \subset (0,1)$ (say $x \to x/2 +1/4$). The function's definition will be somewhat messy (basically, it depends on how many times you can lift a point under these to injections already defined, and specifically the parity of the number of times), but it'll do it.

For 2, iterate this construction to get a bijection $R \to R - N$. Then given any countable set $S$, define the map of $R$ that interchanges $N$ and $S$ and leaves every other point fixed. Then the composition of the first bijection with this second map is your bijection.

Continuity considerations imply that the map can't be continuous: in 1, for instance, we'd otherwise have that $(0,1)$ is compact, which it's not.

-
should this question have a topology tag? –  Tom Stephens Jul 22 '10 at 1:16
The question itself wasn't topological, but topological considerations show that using standard continuous functions won't work. I'm not sure that the tag is necessary. –  Akhil Mathew Jul 22 '10 at 1:24
Great answer! it took me a while to understand the proof. –  Chao Xu Jul 22 '10 at 1:44
What happens when $\mathbb{N}$ is properly included in the countable set $S$, say $S = \mathbb{Q}$? In this case, your bijection does not seem to be well-defined. (e.g., If your countable bijection $b: \mathbb{N} \rightarrow S$ were to map $0$ to $1/2$ and $1$ to $0$, where would you send $0$?) You seem to want to show that for any countable $S$, you can have a bijection $\mathbb{R} \rightarrow \mathbb{R} - T$ for some countable $T$ that's disjoint from $S$. –  Jason Jan 17 '11 at 6:00

An explicit bijection $(0,1) \to [0,1]$ for part $1$ is given by:

$$f\left(\frac{1}{2}\right) = 0,\quad f\left(\frac{1}{3}\right) = 1,\quad f\left(\frac{1}{n}\right) = \frac{1}{n-2}\ \textrm{for}\ n > 3,$$

$$f(x) = x\ \textrm{for}\ x\ \textrm{not equal to a reciprocal of an integer}$$

For a bijection $\mathbb{R}$ to $\mathbb{R}\setminus S$, we can number the elements of $S$ (because $S$ is countable) as $s_1, s_2, s_3, \dots$ Choose an infinite sequence $t_1, t_2, \dots$ of distinct elements of $\mathbb{R}$, none of which are in $S$. Then define:

$$g(s_i) = t_{2i},\quad g(t_i) = t_{2i+1},\quad g(x) = x\ (\textrm{otherwise}).$$

This is a bijection from $\mathbb{R}$ to $\mathbb{R}\setminus S$.

-

I'm going to give a constructive procedure that hints at generalizations of the cut-and-paste/split function approaches of Akhil/Simon. The top-level idea is that given a countable $S \subseteq \mathbb{R}$ to be deleted, we will find a countably infinite subset $T \subseteq \mathbb{R} \setminus S$. We will then split $T$ into two disjoint sets $A$ and $B$ having size $|S|$ and $|T|$, respectively and identify the deleted $S$ from $\mathbb{R}$ with $A$ and $T$ with $B$. In particular, this will fix all points in $\mathbb{R} \setminus (S \cup T)$ and will send the elements from $S \cup T$ to $A \cup B = T$. The point is that we work with well-orderable subsets of $\mathbb{R}$ which admit nice bijections. (e.g., a well-order order isomporphic to $\mathbb{N}$ can be put into bijective correspondence with $\mathbb{N} \times \{0, 1\}$ by sending the evens $2n$ to $(n, 0)$ and the odds $2n+1$ to $(n, 1)$.) Our desired bijections are thus formed from a cut/paste method where we cut out well-ordered sets, work with bijections of them, and then paste the identity mapping with the induced maps from these bijections as Akhil suggests in his answer and as described below.

(1) First consider any injection $j: \mathbb{N} \rightarrow [0, 1]$ including $0$ and $1$ in the range (e.g., $n \mapsto \frac{1}{n}$ for $n > 0$ and $0 \mapsto 0$). Then we have a $1:1$ correspondence between $\mathbb{N}$ and $C = \text{range}(j)$. Because $C$ includes $0$ and $1$, we have $[0, 1] \setminus C = (0, 1) \setminus C$ so given a bijection $b$ between $C$ and $(0, 1) \cap C$, we can paste together the identity map and $b$ on these respective domains to get a bijection between $[0, 1]$ and $(0, 1)$. Now note that $j$ maps exactly two elements $m, n \in \mathbb{N}$ to the $\text{range}(j)$ that are not in $(0, 1)$, mainly the ones being mapped to $0$ and $1$. Consequently, letting $g: \mathbb{N} \rightarrow \mathbb{N} \setminus \{m, n\}$ be a bijection, say one simply listing the Natural numbers in order that skips $m$ and $n$, you can verify that $j \circ g \circ j^{-1}: C \rightarrow (0, 1) \cap C$ is a well-defined bijection.

(2) For this part, extend your countable bijection $s: \omega \rightarrow S$ to a countable injection $k: \omega + \omega \rightarrow \mathbb{R}$ ($\omega = \mathbb{N}$ and $\omega + \omega$ has an ordering isomorphic to one on $\mathbb{N} \times \{0, 1\}$ given by $(m, i) \leq (n, i)$ when $m \leq n$ and $(m, 0) \leq (n, 1)$ always). The reason such an injection exists is because given a set of Reals that resulted from the subtraction of countably many elements, we can always find a countable number that haven't been removed by iteratively diagonalizing against all the ones in our list, adding each new one obtained by this method to the top of the list so that it too gets diagonalized against in the construction of the next Real not in the list.

Now we have a $1:1$ correspondence between $\omega + \omega$ and $D = \text{range}(k)$. Because $D$ includes all elements in $S$ by construction, we have $\mathbb{R} \setminus D = (\mathbb{R} \setminus S) \setminus D$ so given a bijection $b^*$ between $D$ and $(\mathbb{R} \setminus S) \cap D$, we can paste together the identity map and $b^*$ on these respective domains to get a bijection between $\mathbb{R}$ and $\mathbb{R} \setminus S$. Now note that all elements listed by $k$ at and beyond $\omega$ are in $\mathbb{R} \setminus S$ by the fact that $k$ only lists each element once and already listed all elements in $S$ before $\omega$. Consequently letting $h: \omega + \omega \rightarrow (\omega + \omega) \setminus \omega$ be a bijection, you can verify that $k \circ h \circ k^{-1}: D \rightarrow (\mathbb{R} \setminus S) \cap D$ is a well-defined bijection.

[I realize that this can be technical without knowing about ordinals but just think of $\omega + \omega$ as being the set of Natural numbers with a copy of the Natural numbers on top and $(\omega + \omega) \setminus \omega$ as the top set of Natural numbers. Establishing a bijection between the two sets is similar to establishing a bijection between the set of evens and the set of Natural numbers.]

-