2
$\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$
  • 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$ – Ross Millikan Aug 17 '17 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 '17 at 17:14
  • $\begingroup$ You should get a nice bijection if you use continued fractions. $\endgroup$ – Michael Burr Aug 17 '17 at 17:19
4
$\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$
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$
1
$\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$
  • $\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 '17 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 '17 at 18:44

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.