# Is this set bijective to R?

The set of all infinite sequences with integer entries?

Obviously my set is at least as large as R, but is it larger?

-

Let $S$ be the set of all sequences $${\bf x}:\ {\mathbb N}_{\geq1}\to {\mathbb Z}, \ k\mapsto x_k\ .$$

Any real number $t\in\ ]0,1[\$ has a unique decimal expansion $0. x_1x_2x_3\ldots$ not ending with all nines, and different such $t$'s have different expansions. Therefore we have here an injective map $\phi:\ ]0,1[\ \to S$. As $\ ]0,1[\$ has the same cardinality as ${\mathbb R}$ (e.g., via the bijection $t\mapsto\cot(\pi t)$) this shows that the cardinality of ${\mathbb R}$ is at most equal to the cardinality of $S$.

Conversely: Given an integer sequence ${\bf x}=(x_1, x_2,x_3,\ldots)$ write the numbers $|x_1|$, $|x_2|$, $\ldots$ in binary, then prefix these $0$-$1$-words with a $3$, if $x_k<0$, and with a $4$, if $x_k\geq0$. An example: If $x_{5}=-27$ in decimal then you get the word $311011$. Concatenate the sequence of finite words so obtained to a single infinite sequence $(y_k)_{k\geq1}$, and let $f({\bf x})$ be the real number with decimal expansion $0.y_1y_2y_3\ldots$. Then $f$ is an injective map from $S$ to the positive reals. Therefore the cardinality of this set is at most equal to the cardinality of ${\mathbb R}$.

Altogether we see that $S$ and ${\mathbb R}$ have the same cardinality.

-
That's really a very clever construction, and I see that your function is injective because for any x the greatest any digit can be after the decimal point is 4 + 4 = 8. – Adam Rubinson Nov 1 '12 at 13:53
edit: the most any digit can be is 4 + 1 = 5 – Adam Rubinson Nov 1 '12 at 14:00

Continued fractions are numbers of the form:

$$[c; a_0,a_1,a_2,\ldots] = c+\frac1{a_0+\frac1{a_1+\frac1{a_2+\dots}}}$$

Where $c$ is an integer and $a_i$ are positive integers. It's not a trivial theorem that this is a well-defined, and unique, and in fact every real number has such representation.

Furthermore $r\in\mathbb Q$ if and only if $r=[c; a_0,a_1,\ldots]$ and there exists some $n\in\mathbb N$ such that for $k>n$, $a_k=0$.

That is, the function which takes an infinite sequence of positive integers into its continued fractions is injective into the real numbers. Therefore it does not have a larger cardinality.

Now it is just a matter of observation that since there are countably many integers and countably many positive integers the set of all infinite sequences of integers and set of all sequences of positive integers are of the same cardinality.

It can also be done using cardinal arithmetics:

Let $S$ denote the set of all infinite sequences of integers, we can regard this as the set of all functions from $\mathbb N$ into $\mathbb Z$.

Every function itself is a subset of $\mathbb{N\times Z}$, therefore it is an element of $\mathcal P(\mathbb{N\times Z})$. Because $\mathbb{N\times Z}$ is countable it means that $\mathcal P(\mathbb{N\times Z})$ has the same cardinality as $\mathcal P(\mathbb N)$, which has the same cardinality as $\mathbb R$.

If you already know that $\mathbb R$ has cardinality of at most the set of sequences, we are done. Otherwise, just note that the sequences which have only $0,1$ is a set of the same cardinality as $\mathcal P(\mathbb N)$, and now we are done.

-

Compute $\aleph_0^{\aleph_0}$, where $\aleph_0$ is the cardinal of $\mathbb Z$. First, $$\aleph_0^{\aleph_0} \ge 2^{\aleph_0} = \mathfrak{c},$$ where $\mathfrak{c}$ is the cardinal of $\mathbb R$. Next, $$\aleph_0^{\aleph_0} \le \mathfrak{c}^{\aleph_0} = \big(2^{\aleph_0}\big)^{\aleph_0} = 2^{\aleph_0 \aleph_0} = 2^{\aleph_0} = \mathfrak{c}.$$ Therefore, by Cantor-Bernstein, $\aleph_0^{\aleph_0} = \mathfrak{c}$.

-
Okay, but that's only useful if you are good at cardinal arithmetic (which I am not). I mean I can see how it works but I don't know enough cardinal arithmetic to be fully convinced. – Adam Rubinson Nov 1 '12 at 16:27

If you take your integer entries to be positive, then you get a bijection with the positive irrational numbers through the definition of continued fractions. It is then easily deduced that your set has the same cardinality as $\mathbf R$ (which also follows from other more set-theoretic considerations).

-