17
$\begingroup$

Since both of them are uncountable sets, we should be able to construct such a map. Am I correct?

If so, then what is the map?

$\endgroup$
  • $\begingroup$ The answer is yes, such a map exists, but I personally don't know if you can actually construct it. $\endgroup$ – jgon May 3 '15 at 8:14
  • 10
    $\begingroup$ They are both uncountable, but it doesn't follow from that that they have the same cardinality. Actually they are equicardinal, so there is a bijection between them. We can prove it easily, but the easy proof isn't constructive. So it isn't so obvious that we should be able to construct a bijection between them. $\endgroup$ – Leonhardt von M May 3 '15 at 8:16
  • $\begingroup$ $|\mathbb{R}|=|\mathbb{R-Q}|$ and we are done $\endgroup$ – JonMark Perry May 3 '15 at 8:17
  • 2
    $\begingroup$ @LeonhardtvonM: When the difference between two sets is countable, it is easy to construct an explicit bijection without appeal to any set theory. Since we have an easy bijection between $(0,1)$ and $\mathbb{R}$, we can fix the countable discrepancies between $[0,1]$ and $(0,1)$, and between $\mathbb{R}$ and $\mathbb{R} \setminus \mathbb{Q}$. $\endgroup$ – user21820 May 3 '15 at 9:47
  • $\begingroup$ @JonMarkPerry That doesn't seem any eaiser than the question itself. $\endgroup$ – Trevor Wilson May 4 '15 at 0:53
14
$\begingroup$

Define $f : [0,1] \to \mathbb{R}$ as follow : if $x \in \mathbb{Q}$, then $f(x) = \pi + x$. If $x$ is irrational, then $f(x) = x$. This function is injective. It is not a bijection.

$\endgroup$
  • 2
    $\begingroup$ You can also just use $f(x) = \sqrt{2} + x$ for rational $x$. $\endgroup$ – user21820 May 3 '15 at 8:44
  • $\begingroup$ As simple as that ! awesome. :) $\endgroup$ – Error 404 May 3 '15 at 8:56
  • $\begingroup$ @VikrantDesai: Yes this answer is perfect for your question since you didn't ask for a bijection. But see the other answers for bijections since that is the more interesting question. $\endgroup$ – user21820 May 3 '15 at 9:50
  • 1
    $\begingroup$ @user21280 yes , surely ! I am going through all of them, couldn't have imagined various such constructions. Maths stack exchange is really an amazing source to learn ! $\endgroup$ – Error 404 May 3 '15 at 9:52
  • 1
    $\begingroup$ You can make this bijective easily though by "bumping" $\mathbb Q + \pi $ to $\mathbb Q + 2\pi$ and so on. That is, if $f$ is such that for $x$ such that $x-n\pi$ is rational for non-negative $n$, define $f(x)=x+\pi$. Otherwise, define $f(x)=x$. This is a bijection. $\endgroup$ – Milo Brandt May 3 '15 at 15:35
17
$\begingroup$

Both sets $[0,1]$ and $[0,1]\setminus\mathbb Q$ have the same cardinality $\mathfrak c=2^{\aleph_0}$, so there is a bijection between them.


If you want write down some explicit bijection, you can use basically the standard Hilbert's hotel argument which shows that if $|A|\ge\aleph_0$ then $|A|+\aleph_0=|A|$.

So let us try to describe some bijection $f \colon [0,1] \to [0,1]\setminus\mathbb Q$.

  • Choose some infinite sequence $x_n$, $n=0,1,2,3,\dots$ of irrational numbers in the interval $[0,1]$.
  • Choose some bijection $g\colon \mathbb N\to\mathbb Q\cap[0,1]$.

Then you can define $f$ as:

  • $f(x_{2n})=x_n$;
  • $f(x_{2n+1})=g(n)$;
  • $f(x)=x$ for $x\in [0,1] \setminus \{x_n; n=0,1,2,\dots\}$

Let me add links to some posts where a very similar ideas can be used to construct a bijection between two given sets:

$\endgroup$
  • 1
    $\begingroup$ You have a typo in that cardinal arithmetic argument. :-) $\endgroup$ – Asaf Karagila May 3 '15 at 8:40
  • $\begingroup$ You meant $|A|+\aleph_0=\aleph_0$, right? Thanks for noticing it, corrected now. $\endgroup$ – Martin Sleziak May 3 '15 at 8:42
9
$\begingroup$

You can construct such a function in the following steps (it's certainly by far not the only way):

  1. Map the closed interval $[0,1]$ to the open interval $(0,1)$ by the function $$f(x) = \begin{cases} \frac{1}{4} & x = 0\\ \frac{1}{4(n+1)} & x = \frac{1}{4n}, n\in\mathbb Z^+\\ \frac{3}{4} & x = 1\\ 1-\frac{1}{4(n+1)} & x = 1 - \frac{1}{4n}, n\in\mathbb Z^+\\ x & \text{otherwise} \end{cases}$$

  2. Map the interval $(0,1)$ to $\mathbb R$ by the function $$g(x) = \ln(-\ln x)$$

  3. Map $\mathbb R$ to the set of irrational numbers by the function $$h(x) = \begin{cases} x\pi^{n+1} & x = q\pi^n, q\in\mathbb Q, n \in \mathbb N_0\\ x & \text{otherwise} \end{cases}$$

Then the function $F = h\circ g\circ f$ is a bijection from $[0,1]$ to the set of irrational real numbers.

Here I've used the notations $\mathbb Z^+ = \{1,2,3,\ldots\}$ the set of positive integers, and $\mathbb N_0 = \{0,1,2,3,\ldots\}$ the set of positive integers (natural numbers, including $0$).

$\endgroup$
  • 2
    $\begingroup$ Your answer relies on $π$ being transcendental, but how are you going to justify it? My answer is similar in idea to yours but uses primes instead, which only requires elementary number theory. $\endgroup$ – user21820 May 3 '15 at 8:43
  • 3
    $\begingroup$ @user21820: What exactly do you think I have to justify? That $\pi$ is transcendental is a well-known fact; see e.g. Wikipedia. $\endgroup$ – celtschk May 3 '15 at 8:55
  • 3
    $\begingroup$ Yes it is a well-known fact, but it is a sledgehammer. One might open up the proof of cardinal arithmetic to solve this question, but it sheds not much 'concrete' light on the matter since the general case requires the axiom of choice. Similarly, the fact that π is trancendental is totally not elementary and not at all crucial to this question. It's just a strange feeling one gets, as if the real reasons are being hidden away in the claim of the transcendentality of π instead of being proven here. It's not wrong, just strange. $\endgroup$ – user21820 May 3 '15 at 9:05
4
$\begingroup$

Let $p_0 = 0$ and $p_n$ be the $n$-th prime for any $n \in \mathbb{N}^+$.

Let $f:\mathbb{R}\to\mathbb{R}$ such that:

  $f(x) = \cases{ r+\sqrt{p_{n+1}} & \text{if $x = r+\sqrt{p_n}$ for some $n \in \mathbb{N}$ and $r \in \mathbb{Q}$} \\ x & \text{otherwise} }$.

To prove that this function is well-defined, we just need to check that it is impossible to have $a+\sqrt{p_m} = b+\sqrt{p_n}$ for distinct $m,n \in \mathbb{N}^+$ and $a,b \in \mathbb{Q}$, which is clearly the case otherwise $(a-b)^2 = (\sqrt{p_m}-\sqrt{p_n})^2$ $= p_m+p_n-\sqrt{p_mp_n} \notin \mathbb{Q}.$

I leave you to prove that it is a bijection from $\mathbb{R}$ to $\mathbb{R} \setminus \mathbb{Q}$. Then you can compose it with a bijection from $[0,1]$ to $\mathbb{R}$.

$\endgroup$
  • 2
    $\begingroup$ Your answer relies on $\sqrt{p_n}$ being irrational and all linearly independent over $\mathbb Q$, but how are you going to justify it? One might open op the proof of number theory to solve this question, but it sheds not much 'concrete' light on the matter since the general case requires the axiom of choice. It's just a strange feeling one gets, as if the real reasons are being hidden away in the claim of the rational independence of $\{\sqrt{p_n}\}_n$ instead of being proven here. It is not wrong, just strange. $\endgroup$ – Henning Makholm May 3 '15 at 13:45
  • 1
    $\begingroup$ @HenningMakholm: Thanks for making me read my answer again. I found and fixed a small error. Note that it does not at all require independence of all square roots of primes over the rationals, nor does it require the axiom of choice. $\endgroup$ – user21820 May 3 '15 at 14:09
  • 1
    $\begingroup$ @HenningMakholm: Eh wait.. are you implying that you don't actually know whether the axiom of choice is relevant? Then please don't echo anything. My statement about the axiom of choice is correct regarding cardinality, which is not used in celtschk's answer but is necessary for the general form of user59001's answer to work. $\endgroup$ – user21820 May 3 '15 at 14:14
  • 1
    $\begingroup$ @VikrantDesai: Sorry to say but my answer is now sufficiently complete and does not depend on any difficult results that you cannot prove on your own, contrary to Henning's objection. $\endgroup$ – user21820 May 3 '15 at 14:23
  • 1
    $\begingroup$ @HenningMakholm: Correct. Let me rephrase the point I was trying to make. I meant that we can take the proof of that very theorem of cardinal addition, that uses AC, and either attach it to a simple-looking proof of this problem like user59001's, or open up the proof and apply the deductions one by one to this particular problem. In both cases, one gets a complicated proof of a simple theorem that uses assumptions that are completely unnecessary. That is what I mean by sledgehammer. If you still don't like my method despite its simplicity, then by all means use the better odd-even method. =) $\endgroup$ – user21820 May 3 '15 at 14:32
2
$\begingroup$

Yes, the irrationals and the set [0,1] have the same cardinality. Using cardinal arithmetic:

$$\text{card}([0,1]) = \text{card}(\mathbb{R}) = \text{card}(\mathbb{Q} + (\mathbb{R} \setminus \mathbb{Q}) ) = \text{card}(\mathbb{Q}) + \text{card}(\mathbb{R} \setminus \mathbb{Q} ) = \text{card}(\mathbb{R} \setminus \mathbb{Q} )$$

I cannot recall an explicit construction of such a bijection, however.

$\endgroup$
2
$\begingroup$

Let me prove a more general theorem that may be instructive: $\def\nn{\mathbb{N}}$ $\def\power{\mathcal{P}}$

Given any infinite set $S$, there is a bijection from $\power(S)$ to $\power(S) \setminus \{ \{x\} : x \in S \}$.

One could use the full theory of cardinals and cardinal arithmetic, but the proof of that needs the axiom of choice (AC) and hence is necessarily non-constructive. But it is possible to prove an explicit bijection in this case, using only the axiom of countable choice and avoiding AC, as follows:

Let $(a_n)_{n\in\nn}$ be a sequence of distinct elements in $S$, since $S$ is infinite, and let $A = \{ a_n : n \in \nn \}$.

Let $f(X) = \cases{ \{ a_i : i \in [k..m+1] \} & \text{if $X = \{ a_i : i \in [k..m] \}$ for some $k,m \in \nn$ with $k \le m$} \\ \{s,a_0\} & \text{if $X = \{s\}$ for some $s \in S \setminus A$} \\ \{s,a_{m+1}\} & \text{if $X = \{s,a_m\}$ for some $s \in S \setminus A$ and $m \in \nn$} \\ X & \text{otherwise} }$

[For convenience I used "$[k..m]$" to denote "$\{k,k+1,k+2,...,m\}$".]

It can be checked that $f$ is a desired bijection.

As a consequence we will obtain:

There is a bijection between $\power(S) \cup T$ and $\power(S)$ for any disjoint infinite $S,T$ such that there is a bijection between $S$ and $T$.

This corresponds to a special case of cardinal addition, namely $\#(\power(S))+\#(S)=\#(\power(S))$ for infinite $S$, which is enough for a lot of mathematics.

Note

The fact that a countably infinite sequence exists within any infinite set can be proven by considering a sequence of finite subsets with increasing sizes. Each exists and by countable choice we get this sequence. The union of the subsets is countably infinite and we can extract the desired sequence from it by the axiom of induction.

$\endgroup$
  • $\begingroup$ How exactly do you get a sequence of as from infiniteness of S, without AC?? $\endgroup$ – Veky May 4 '15 at 7:12
  • $\begingroup$ @Veky: It depends on what system you are working in and how you want to define "infinite". If you want to stay within set theory and define "infinite" as (1) "no bijection with a proper initial segment of the naturals", then you need say (DC) dependent choice. In fact there is a proof using only (CC) countable choice (see proofwiki.org/wiki/Infinite_Set_has_Countably_Infinite_Subset/…). and CC is essentially uncontentious. But if you take "infinite" to mean (2) "there is a subset in bijection with the naturals", then you don't need anything beyond ZF. $\endgroup$ – user21820 May 4 '15 at 8:41
  • $\begingroup$ @Veky: Furthermore, if you work in a more constructive theory than ZF then you can often use (1) without needing even CC, because a sequence would just be the rule for generating it, and certainly you can generate any element of that infinite sequence in finitely many steps. But I'm not going to make precise what kind of more constructive system would work here haha.. $\endgroup$ – user21820 May 4 '15 at 8:42
  • $\begingroup$ First comment can be understood, though I presume usual definitions of infinitude (equipotent with proper subset, or not bijective with n for any n) don't include your version. And retrofitting definitions to include consequences of AC is not really meaningful game... otherwise you could just redefine what "disjoint family of nonempty sets" meant. :-P But second comment is just wrong: even if you could give a rule for constructing any element of sequence, for applying rule 2 in definition of f(X) you need the whole A to decide, not some finite segment of it. $\endgroup$ – Veky May 5 '15 at 4:58
  • $\begingroup$ @Veky: Well if you noticed I included a note in my answer to sketch how to obtain the claimed sequence using CC. For second point, it is possible as I said, not in a purely constructive sense of course (which is what you are referring to). The reason it makes no sense to stick to purely finitely constructible objects is that we a priori assume the truth of classical logic, which is non-constructive already. Furthermore, it is silly if we cannot even tell whether two real numbers are equal, which would be the case in a purely constructive setting. $\endgroup$ – user21820 May 5 '15 at 5:28
2
$\begingroup$

Let $x=0.x_1x_2\dots$ be the base $10$ representation (choosing the ones ending in repeating $9$s rather than repeating zeros.)

Let $p=0.y_1y_2\cdots$ be any (fixed) irrational number in $(0,1)$.

Then $f(x)=0.x_1y_1x_2y_2\dots$ is a $1-1$ function which maps $[0,1]$ to the irrationals, and it is continuous at every number that is not of the form $\frac{n}{10^k}$.

(This map is not, of course, onto.)

$\endgroup$
1
$\begingroup$

There are lots of good answers already, but I thought I might add one more using a flexible method that shows up a lot in descriptive set theory.

Note that $\mathbb{R} \setminus \mathbb{Q}$ is the intersection of countably many dense open sets $(G_n : n \in \mathbb{N})$; just take $G_n = \mathbb{R} \setminus \{q_i\}$ for some enumeration $(q_i : i \in \mathbb{N})$ of the rationals.

Note also that there is an injection from $[0,1]$ to the Cantor space $2^\mathbb{N}$ given by binary expansions. If there is a choice between a binary expansion that is eventually zeroes and another that is eventually ones, take the one that is eventually zeroes. (This injection is not continuous.)

So it suffices to prove the following general fact:

Let $(G_n : n \in \mathbb{N})$ be a sequence of dense open subsets of $\mathbb{R}$. Then there is an injection from $2^\mathbb{N}$ to $\bigcap_{n \in \mathbb{N}} G_n$. (As we will see, there is a continuous injection.)

By recursion, we can define for each finite sequence $s$ of natural numbers a closed interval $I_s$ satisfying the following properties:

  • $I_s$ has length between zero and $2^{-n}$ where $n$ is the length of the finite sequence $s$,

  • $I_t \subset I_s$ whenever $t$ extends $s$,

  • $I_s \cap I_t = \emptyset$ whenever $s$ and $t$ are incompatible, and

  • $I_s \subset G_n$ where $n$ is the length of $s$.

This binary tree of intervals is called a Cantor scheme. If desired, we can define $I_s$ explicitly as $[q_i,q_j]$ where $(i,j)$ is the lexicographically least pair of natural numbers making this interval obey the rules.

Every element $(d_i : i \in \mathbb{N})$ of the Cantor space $2^\mathbb{N}$ determines a branch in this binary tree. Our continuous injection is obtained by mapping $(d_i : i \in \mathbb{N})$ to the unique point in the intersection of the corresponding sequence of closed intervals $$I_{d_0} \supset I_{d_0,d_1} \supset I_{d_0,d_1,d_2} \supset \cdots.$$

$\endgroup$

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.