5
$\begingroup$

So I'm trying to show that these two sets have the same cardinality, i.e. there is a possible bijection between the two. I'm trying to use the Cantor-Schroeder-Bernstein theorem as I can't explicitly think of a bijection that will work. For this I need to find an injective map each way. I can find an injective mapping between $R$ and the set of infinite sequences of natural numbers. E.g., for each real number $x$, I can associate it with the sequence $S$, where the first element is $2^{n}$ (where $n$ is the greatest integer less than or equal to $x$) if x is nonnegative, and $3^{n}$ if x is negative. Then the rest of the sequence can be the decimal expansion of x in single digits. E.g. the sequence associated with pi through the function would be $(2^{3}, 1,4, etc)$. This is injective, so the first half of Cantor-Schroeder-Bernstein is satisfied. If I can find an injective function going the other way then I am done.

I first thought of something involving turning the digits of the sequence into a real number, but that failed to be injective as my function would not be able to differentiate between the sequences $(1,0,1,0,1,0,...)$ and $(10,10,10,...)$.

Any hints or help? I'm trying to figure it out without resorting to proofs based on cardinal arithmetic or related to the power set of N.

$\endgroup$
3
  • 2
    $\begingroup$ I disagree with the closure as you asked not to use cardinality. You need a separator to cure the problem you identified. One way is to write all the numbers in the sequence in binary and put a $2$ between them, so 4,3,5 would become 1002112101. Put a decimal point in front and you are done. $\endgroup$ Aug 17, 2017 at 17:04
  • $\begingroup$ Brilliant. Somehow I had thought of something a little similar but thought it wouldn't work because the numbers would be infinitely large. I hadn't thought of putting the decimal point at the start! $\endgroup$
    – Franz
    Aug 17, 2017 at 17:14
  • $\begingroup$ You should get a nice bijection if you use continued fractions. $\endgroup$ Aug 17, 2017 at 17:19

4 Answers 4

5
$\begingroup$

You need a separator to cure the problem you identified. One way is to write all the numbers in the sequence in binary and put a $2$ between them, so $4,3,5,1,9$ would become $10021121012121001$. Put a decimal point in front and you are done.

$\endgroup$
3
  • $\begingroup$ My apologies for the downvote, it was $100\%$ inadvertent (4:00 a.m., in the dark, careless fingers). If you care about it, my understanding is that you could simply make an edit, which would then allow me to reverse it. I considered making an incidental edit myself to make this possible, but that seemed wrong somehow. $\endgroup$
    – lulu
    Aug 30, 2021 at 11:47
  • $\begingroup$ @lulu: No worries. I have enough rep I don't care. $\endgroup$ Aug 30, 2021 at 13:36
  • $\begingroup$ Understood! Sorry for the nuisance. $\endgroup$
    – lulu
    Aug 30, 2021 at 15:43
3
$\begingroup$

We know $(0,1)$ has the cardinality of the continuum. Each $x\in (0,1)$ has a decimal expansion $.x_1 x_2 \dots $ The map $x = .x_1 x_2 x_3 \, \dots \to x_1,x_2, x_3,\dots$ is then an injection of $(0,1)$ into $\mathbb N^{\mathbb N}.$

For an injection going the other way: if $n_1, n_2 , \dots \in \mathbb N^{\mathbb N},$ we can map it to the decimal expansion that starts with $n_1$ $1$'s, followed by one $0,$ then followed by $n_2$ $1$'s, followed by one $0,$ etc. For example, $2, 5, 3, 1, 4, 2, \dots$ goes to $.1 1 0 1 1 1 1 1 0 1 1 1 0 1111 0 11 0\dots$

$\endgroup$
3
  • $\begingroup$ Other than wanting to post an answer, why did you reopen this question? The duplicate had an answer for the specific case of a countable set, in particular the case of $\Bbb N$ itself. $\endgroup$
    – Asaf Karagila
    Aug 17, 2017 at 18:24
  • $\begingroup$ @AsafKaragila I didn't vote to reopen because I wanted to answer, although I ended up doing that. I thought the answers at the link you gave were a bit too general and complicated, when we have a nice little problem here whose solution can be patched together with some pretty elementary (and fun) stuff, more in line with the approach of the OP. $\endgroup$
    – zhw.
    Aug 17, 2017 at 18:44
  • $\begingroup$ If I were you, I would also mention at the end that if we had two injections $A \hookrightarrow B$ and $B \hookrightarrow A$ then cardinalities of $A$ and $B$ are the same: $|A| = |B|$. The result is called Cantor-Bernstein theorem $\endgroup$ Oct 13, 2021 at 13:16
2
$\begingroup$

Alternate Approach:

For now, let's assume that $0\not\in\mathbb{N}$ - I'll mention a little more about this later.

Recall the following fact about continued fractions: Infinite continued fractions are in bijective correspondence with irrational numbers.

Therefore, one can associate each sequence of natural numbers with an irrational number. By the uniqueness, this is a bijection and so there is an injective map from the infinite sequences to the set of irrational numbers and there are many more irrational numbers than rational numbers.

Notes:

  1. If you typically assume that $0\in\mathbb{N}$, then just let $\mathbb{N}^+$ be the set of positive natural numbers and there is a bijection between the sequences from $\mathbb{N}$ and $\mathbb{N}^+$ where a sequence $\{a_i\}$ in $\mathbb{N}$ corresponds to the sequence $\{a_i+1\}$ in $\mathbb{N}^+$.

  2. If you don't want to use that there are more irrational numbers than rational numbers, you can just see that this gives an injection from the set of sequences of natural numbers to the continuum of numbers. One can also get a surjection from the sequences of natural numbers to positive real numbers, by mapping a sequence $\{a_i\}$ to the real number $\sum a_i2^{-i}$.

$\endgroup$
2
$\begingroup$

Every real number in $[0,1)$ can be written uniquely as $\sum_{i=1}^{\infty}\frac{a_i}{2^i}$ where each $a_i\in\{0,1\}$ and there are infinitely many $i$ with $a_i=0$.

Let $i_{n}(\alpha)$ be the index of the $n$th zero in that expansion for $\alpha\in[0,1)$.

Then define $$\alpha\mapsto \left\{i_1(\alpha)-1,i_2(\alpha)-i_1(\alpha)-1,i_3(\alpha)-i_2(\alpha)-1,\dots,i_{n+1}(\alpha)-i_{n}(\alpha)-1,\dots\right\}$$

Show that this is one-to-one and onto.

(This assumes natural numbers include $0$, but if they don't, then you can remove all the $-1$s.)

Basically, we are representing a sequence $\{1,2,0,1,3,\dots\}$ as the base $2$ expression:

$$0.101100101110\dots_2$$

$\endgroup$
3
  • $\begingroup$ I think this method is also order-preserving, where the order on the infinite sequences is lexicographic. $\endgroup$ Feb 6, 2021 at 4:49
  • $\begingroup$ "Basically, we are representing a sequence... " I don't understand what is going on here. How does $ \{1,2,0,1,3,\dots\}$ become $0.101100101110\dots_2$? $\endgroup$
    – john
    Nov 17, 2021 at 21:13
  • $\begingroup$ "Every real number in [0,1) can be written uniquely as ∑∞ i=1..∞ a_i/ 2^i where each ai∈{0,1} and there are infinitely many i with a_i=0." What about 0.1111... , this does not have infinitely many i with a_i = 0. $\endgroup$
    – john
    Nov 17, 2021 at 21:19

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.