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}}$?

  • $\begingroup$ Why should it be the binary representation? $\endgroup$ – Improve Feb 21 '17 at 17:39
  • $\begingroup$ I suppose he means $2^{\mathbb{N}}$ as the powerset of $\mathbb{N}$. $\endgroup$ – Fimpellizieri Feb 21 '17 at 17:40
  • $\begingroup$ Yes, he is talking about an injection for $2^N$ inte $R$. Can you do that? What is an element of $2^N$? $\endgroup$ – fleablood Feb 21 '17 at 17:45
  • $\begingroup$ He uses decimal notation, because in binary notation the map would no longer be injective. $\endgroup$ – Mark Feb 21 '17 at 17:49
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.

| cite | improve this answer | |
  • 1
    $\begingroup$ The map is injective because $0.01111\cdots$ is NOT the same as $0.10000\ldots$. Use decimal notation, not binary. $\endgroup$ – Mark Feb 21 '17 at 17:44
  • $\begingroup$ @Mark Sorry, my bad. $\endgroup$ – 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:

  • Take your binary sequence,

  • change each $1$ to a $5$,

  • and put a decimal point at the end.

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.

| cite | improve this answer | |
  • $\begingroup$ 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}$. $\endgroup$ – Carl Mummert Feb 21 '17 at 17:52
  • $\begingroup$ Noah, can you answer this question: math.stackexchange.com/questions/2155108/… It is about something you once said. $\endgroup$ – Please Help Feb 21 '17 at 19:24

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.