# How to “embed” ${2^{\bf N}}$ into ${{\bf R}}$?

Here, Terence Tao writes:

… by using the decimal representation to embed ${2^{\bf N}}$ into ${{\bf R}}$.

What does he mean by "embed"? Is he speaking about constructing an injection ${2^{\bf N}}$ into ${{\bf R}}$? Is says using the "decimal representation"? Shouldn't it be binary representation?

How to "embed" ${2^{\bf N}}$ into ${{\bf R}}$?

• Why should it be the binary representation? – Improve Feb 21 '17 at 17:39
• I suppose he means $2^{\mathbb{N}}$ as the powerset of $\mathbb{N}$. – Fimpellizieri Feb 21 '17 at 17:40
• Yes, he is talking about an injection for $2^N$ inte $R$. Can you do that? What is an element of $2^N$? – fleablood Feb 21 '17 at 17:45
• He uses decimal notation, because in binary notation the map would no longer be injective. – Mark Feb 21 '17 at 17:49
• @Fimpellizieri He might be. But he could also be talking about $2^N$ as the set of all sequences (finite and infinite) of $\{0,1\}$. There's a very natural injection from that to R if you consider a binary decimal expansion. If the poster remembers the injection from P(N) to {sequences of {0,,1}} that can work too but it has a "translation" extra step. – fleablood Feb 21 '17 at 17:50

An element of $\{0,1\}^{\mathbb N}$ is a sequence $(a_0, a_1, a_2, \ldots)$ where each $a_i$ is either $0$ or $1$. Just build a real number out of them.

For instance, the sequence $(1, 0, 0, 1, 1, 1,\ldots)$ is mapped to the real number $0.100111\ldots$. This mapping is injective, i.e., an embedding.

• The map is injective because $0.01111\cdots$ is NOT the same as $0.10000\ldots$. Use decimal notation, not binary. – Mark Feb 21 '17 at 17:44
• @Mark Sorry, my bad. – Noah Schweber Feb 21 '17 at 17:45

He is indeed talking about constructing an injection. However, it's even better than that: $2^\mathbb{N}$ carries a natural topology - even a metric! - and according to that, the injection Tao mentions is continuous.

You ask about using binary vs. decimal - there is a slight issue in using binary: reals with multiple binary expansions. E.g. in binary $0.0111111...=0.100000...$, so the "obvious" map is not injective. Things are easiest in base $>2$ - decimal, or ternary, or whatever you want.

One way to do things via decimal notation would be as follows:

• change each $1$ to a $5$,
E.g. "$0, 1, 1, 0, 1, 0, 0, . . .$" becomes "$0.0550500...$". This is indeed injective, as is easily checked. And there are lots of other ways to do this, too. Tao says to use decimal notation just for simplicity - if you prefer to work in a different base you can, but if you work in binary you need to be careful to ensure injectivity.
One way to do this in binary is to use a different replacement scheme - e.g. replace each "$0$" with "$01$", and each "$1$" with "$10$", so you're using more than one digit. Then e.g. the sequence "$01001101...$" turns into the number $0.0110010110100110...$. This is less elegant, though, than just using a different base.
• Moreover, because $2^\mathbb{N}$ is compact, a continuous injection from $2^\mathbb{N}$ is also an open map onto its range, so it gives a homeomorphism between $2^{\mathbb{N}}$ and a subset of $\mathbb{R}$. – Carl Mummert Feb 21 '17 at 17:52