4
$\begingroup$

There's the usual mapping $2^\mathbb{N}\mapsto\mathbb{R}_{[0,1)}$ (where $2^\mathbb{N}$ denotes the powerset of $\mathbb{N}$) given by $x\in2^\mathbb{N}\mapsto\sum_{i\in x}\frac{1}{2^i}\in\mathbb{R}$. I'm interested in the inverse $\mathbb{R}_{[0,1)}\mapsto2^\mathbb{N}$, i.e., given $r\in\mathbb{R}$, what's the corresponding $x_r\in2^\mathbb{N}$ that generates it? (Note: I'm just guessing appropriate tags)

Is that $x_r\in2^\mathbb N$ explicitly constructible? Or its characteristic function, i.e., for $r\in\mathbb{R}_{[0,1)}$ and $x_r\mapsto r$, $\chi_r(i)=\left\{{1\ if\ i\in x_r\atop0\ otherwise}\right.$?

Also, poset ordering question as follows. While it's clear that $x_1\subseteq x_2\Longrightarrow r_{x_1}\le r_{x_2}$, what about the inverse? That is, $r_{x_1}\le r_{x_2}\overset?\Longrightarrow x_1\subseteq x_2$. And if not true, got an explicit counterexample?

__Edit__

Firstly, thanks very much Lubin, Manmaid, Ross, Daniel for your elaborate and thoughtful answers/comments. I haven't had time to fully digest everything, but one apparent take-away is the pesky appearance of infinite subsets. And that's got to be an unnecessary artifact: there's no reason why, say, $\frac13=.333\ldots=\sum_{i\in x}\frac1{2^i}$, should require some stupid-large $x\subseteq\mathbb N$ for its representation, whereas the information content of $\frac13$ is ultimately pretty minimal.

And it was Ross' mention of https://en.wikipedia.org/wiki/Dyadic_rational that suggested the culprit. It's the explicit "base 2" representation/expansion which I naively introduced in the above question that I'm now thinking is the problem. Daniel's answer introduces a slightly different expansion, but the same underlying problem remains.

So here's a tentative conjecture for a more general representation, which hopefully maps "simple $r\in\mathbb R$'s" to "simple $x_r\in2^\mathbb N$'s". But the representation algorithm's somewhat more complicated than Daniel's or mine above. And the meaning of the subset-order $x_1\subseteq x_2$ isn't at all obvious.

Consider the usual pair enumeration https://en.wikipedia.org/wiki/Pairing_function whereby $\mathbb{N\times N}\rightarrow\mathbb{N}$. And we can then iterate that for $\mathbb{N^3\rightarrow N}$ (or any finite power, but we just need $3$). So consider some $x\in2^\mathbb N$ and interpret every $i\in x$ as three-component $i=(j,k,m)\mapsto j/k^m$. That is, we decompose $r\in\mathbb R$ into rational components of the form $j/k^m\in\mathbb Q$, with any mix of base k's that's convenient.

Now, as Lubin and Ross previously pointed out, it's still possible to represent, e.g., $\frac12=\frac1{2^2}+\frac1{2^3}+\cdots$. So we need some formal way to distinguish a "canonical representation" $\frac12=\frac1{2^1}$. So I haven't figured that out, nor how to interpret the poset order $x_1\subseteq x_2$, etc.

But I believe the premise, that these pesky infinite subsets should go away (except for transcendental reals) is necessary for any sensible $\mathbb R_{[0,1)}\Leftrightarrow2^\mathbb N$. As per https://en.wikipedia.org/wiki/Scott_domain#Explanation, the poset order is an information order, so you shouldn't have teensy-weensy elements on one side of the $\Leftrightarrow$ corresponding to biggy-wiggy elements on the other side. Somehow, that's got to go. But is the preceding conjecture really the simplest or most straightforward way?

__Edit#2__ Reply (too lengthy for comment) to Ross's comment below, "With your edit I understand even less what you are asking..."

Yeah, sorry about that. In a preceding comment replying to you, I mentioned

"Actually, the constructible bijection's for an explicit correspondence between the universal domains $\mathcal P\omega\Leftrightarrow\mathcal U$ ( where the rhs denotes the universal interval domain, as per https://books.google.com/books?id=epb39s2wgt0C&pg=PA162 )

And I'd thought I'd solved that to my own satisfaction, modulo the kind of bijection I asked for here. That bijection's ultimate purpose is thus a correspondence between sets of integers on the $\mathcal P\omega\equiv2^\mathcal N$ side and half-open real intervals with rational endpoints on the $\mathcal U$ side.

By the way, note that in that $\mathcal U$ domain, any real is the lub of intervals including it. Put another way, the real line corresponds to the collection of total (aka maximal) elements of $\mathcal U$ wrt reverse-inclusion ordering. That is, the smaller the interval, the more information you have about the real it refers to.

The upshot is that for the purposes of this question, I was perfectly happy discussing rational approximations to reals. As per a comment to Manmaid,

...Actually, I simplified the question by neglecting to discuss intervals. If you represent $r_{x_n}\in\mathbb R$ by an $x_n=\lbrace i_1,i_2,\ldots,i_n\rbrace$ containing the first $n$ smallest $i$'s in order, with $i_n$ the largest among them, then you're really representing an interval $[r_{x_n},r_{x_n}+1/2^{i_n})$.

So every time I mentioned "real", my underlying thinking was really "interval" as an element of that $\mathcal U$ domain. But I didn't think it necessary to mention that in the context of the original question. I thought I just needed the requested bijection wrt reals, and then everything would just fall into place wrt $\mathcal U$.

So where'd that go wrong? The bijection's subject to a pesky additional constraint wrt that reverse-inclusion information ordering, which it must respect. Suppose the bijection's $b:\mathcal U\rightarrow2^{\mathcal N}$, and write $u_1\sqsubseteq u_2$ for the $u_1,u_2\in\mathcal U$ poset order, and $x_1\subseteq x_2$ for the $x_1,x_2\in2^\mathcal N$ order. Then $b$ must satisfy $u_1\sqsubseteq u_2\Longrightarrow b(u_1)\subseteq b(u_2)$. (and given that $b$'s one-to-one, the arrow has to go both ways)

And that didn't just automatically happen like I'd expected (more accurately, I didn't even think about it until I noticed it wasn't happening). And that unexpected problem got me asking additional stuff seemingly unrelated to the original question, which I guess accounts for your "understand even less what you are asking" remark. (and I hope this helps clear that up a little)

$\endgroup$
  • 2
    $\begingroup$ Don't you think the map you gave $2^{\mathbb{N}}\rightarrow \mathbb{R}_{[0,1]}$is bijective $\endgroup$ – MAN-MADE Aug 5 '17 at 2:17
  • $\begingroup$ @MANMAID yes -- but that's not a constructive statement. While it's clear how to explicitly construct $r\in\mathbb{R}$ corresponding to a given $x\in2^\mathbb{N}$ (exactly like I showed in the question), how do you inversely construct $x$ given $r$? That's the question, as asked in the first sentence of second paragraph. $\endgroup$ – John Forkosh Aug 5 '17 at 2:22
  • 1
    $\begingroup$ @JohnForkosh: It is not bijective, as Lubin shows, so there is not an inverse function. $\endgroup$ – Ross Millikan Aug 5 '17 at 3:08
  • $\begingroup$ @RossMillikan See my comment to Lubin, below. $\endgroup$ – John Forkosh Aug 5 '17 at 3:26
  • 1
    $\begingroup$ With your edit I understand even less what you are asking. The basic correspondence of numbers with their binary expansions works for all the numbers except the dyadic fractions, which is most of them. Most reals don't have anything simple about them. Now you are focused only on the rationals, but not all of them can be written as $j/k^m$ $\endgroup$ – Ross Millikan Aug 5 '17 at 14:08
3
$\begingroup$

First, for any $x\in \mathbb{R}_{[0,1)}$ consider these steps. Let's call it Structure:

  1. Calculate $2x$, if $2x\geq 1$, then fix first number $1$, and if $2x<1$, fix first number $0$. Now calculate $\{2x\}$, the fraction part of $2x$.

  2. Calculate $2\{2x\}$, if $2\{2x\}\geq 1$, then fix second number $1$, and if $2\{2x\}<1$, fix second number $0$. Now calculate $\{2\{2x\}\}$, the fraction part of $2\{2x\}$.

Continue this process. Finally you will get an element of $2^{\mathbb{N}}$.

The construction of a bijective function:

Let $f:\mathbb{R}_{[0,1)}\rightarrow 2^{\mathbb{N}}$

Suppose $x\in \mathbb{R}_{[0,1)}$ is not of the form $\frac{n}{2^m}$, where $n<2^m$ is odd natural number and $m\in \mathbb{N}$, then $f(x)=$ the final sequence you get from the Structure for $x$.

Now if $x\in \mathbb{R}_{[0,1)}$ is of the form $\frac{n}{2^m}$, where $n<2^m$ is odd natural number and $m\in \mathbb{N}$, then values looks like this: $$\frac{1}{2}\\\frac{1}{4}\space\space\frac{3}{4}\\\frac{1}{8}\space\space\frac{3}{8}\space\space\frac{5}{8}\space\space\frac{7}{8}\\\frac{1}{16}\space\space\frac{3}{16}\space\space\frac{5}{16}\space\space\frac{7}{16}\space\space\frac{9}{16}\space\space\frac{11}{16}\space\space\frac{13}{16}\space\space\frac{15}{16}\\\dots\\\dots\\\dots$$

First fix $f(\frac{1}{2})=(1,1,1,\dots)$. Now calculate the sequence you get from Structure for taking $x=1/2$. Surely you get $(1,0,0,0,\dots)$. Now fix $f(\frac{1}{4})=(1,0,0,0,\dots)$ and $f(\frac{3}{4})=(0,1,1,1,\dots)$. Again calculate the sequence you get from Structure for taking $x=1/4$ and $x=3/4$. Sequence you get are $(0,1,0,0,0,\dots)$ and $(1,1,0,0,0,\dots)$ respectively. You immediately fix $f(\frac{1}{8})=(0,1,0,0,0,\dots)$, $f(\frac{3}{8})=(0,0,1,1,1,\dots)$, $f(\frac{5}{8})=(1,1,0,0,0,\dots)$ and $f(\frac{7}{8})=(1,0,1,1,1,\dots)$.Continue in this way and finally you have $f$ is a bijective mapping.

$\endgroup$
  • $\begingroup$ Thanks MANMAID. Yeah, by inspection that seems to do the trick -- and I'll be programming it, at which time we'll know for sure:). And double-yeah about "finite". Actually, I simplified the question by neglecting to discuss intervals. If you represent $r$ by an $x_n=\lbrace i_1,i_2,\ldots i_n\rbrace$ containing the first $n$ smallest $i$'s in order, with $i_n$ the largest among them, then you're really representing an interval $[r_{x_n},r_{x_n}+1/2^{i_n})$. $\endgroup$ – John Forkosh Aug 5 '17 at 3:36
  • 1
    $\begingroup$ This is wrong. You will never generate the sequences in $2^{\Bbb N}$ that end in an infinite series of $1$s. If $x=\frac 12$ you will generate $1,0,0,0,\ldots$ and no real will generate $0,1,1,1,1,\ldots$. $\endgroup$ – Ross Millikan Aug 5 '17 at 3:38
  • $\begingroup$ @RossMillikan $.5=.49999.....$ (I don't know how to write dot on top of a number) $\endgroup$ – MAN-MADE Aug 5 '17 at 3:44
  • $\begingroup$ @RossMillikan $0.5=0.4\dot{9}$ $\endgroup$ – MAN-MADE Aug 5 '17 at 3:48
  • $\begingroup$ That is true and is essentially the issue your answer misses. If you follow through your algorithm with $x=0.5_{10}=0.1_2$ you will generate the sequence $1,0,0,0,0,\ldots$ which is a valid binary expansion for the number. The problem is that no real number will generate the expansion $0,1,1,1,1,1,\ldots$ if we follow your algorithm, so it does not generate a bijection between the reals in $[0,1)$ and the binary sequences. There are computable algorithms that do this, but you have to deal with the binary expansions that equate to the same reals. $\endgroup$ – Ross Millikan Aug 5 '17 at 3:51
2
$\begingroup$

It looks as if you mean for $\Bbb N$ to be $\{1,2,3,\cdots\}$.
Naively, a function has an inverse only if it’s one-to-one. But your map $2^{\Bbb N}\to[0,1\rangle$, is not one-to-one, since $\frac12$ is the image both of $(1,0,0,\cdots)$ (i.e. the function that’s zero everywhere but at $n=1$) and $(0,1,1,1,1,\cdots)$ (i.e. the function that’s $1$ everywhere but at $n=1$. In more familiar terms, $\frac12=\frac14+\frac18+\frac1{16}+\cdots$
This is just the familiar fact that every real with a terminating decimal (or terminating binary expansion) has a different, nonterminating expansion.

The moral? You can not form an inverse to your function.

$\endgroup$
  • $\begingroup$ But is $\frac12$ the unique exception? Given any subset $x \in 2^\mathbb N$ and its corresponding $r_x \in\mathbb R$, it's clear that the set complement, call it $x^\prime=\mathbb N\setminus x$, corresponds to $r_{x^\prime}=1-r_x$. So your set complement is $ (1,0,0,0,\cdots)^\prime=(0,1,1,1,\cdots)$ and then $\frac12=1-\frac12$ is the unique case. (P.S. yeah, my exact wording implies the natural numbers $\lbrace1,2,3,\cdots\rbrace$ without $0$. But in reality I'm including $0$ and considering $1-\mathbb{R}_{[0,2)}=\mathbb{R}_{[-1,1)}$. No big difference.) $\endgroup$ – John Forkosh Aug 5 '17 at 3:21
  • $\begingroup$ No any rational of the form $\frac a{2^n}$ has this problem because they have a terminating binary expansion and another one that ends in all ones. It is a countably infinite set, which can be dealt with to make a computable bijection. The Schroeder-Bernstein-Cantor theorem guarantees that a bijection exists and one approach is to use it to construct the bijection. $\endgroup$ – Ross Millikan Aug 5 '17 at 3:34
  • $\begingroup$ @Lubin what are you saying is not right (how did you get 2 upvotes, I don't know!) You are saying $x$ and $\lim_{\epsilon\to\ 0} (x-\epsilon)$ are different because of their representation. How will you say $f: \mathbb{R}\rightarrow \mathbb{R}$, $f(x)=x$ is bijective using same logic!! $\endgroup$ – MAN-MADE Aug 5 '17 at 3:36
  • $\begingroup$ @RossMillikan Right, I overlooked that "universal exception" (if you'll pardon the oxymoron:). But thanks for that Schroeder-Bernstein-Cantor reference, which I wasn't aware of, and which seems to adequately establish the bijection existence. I think the two distinct cases you mention simply correspond to choosing between $<$ and $\le$ in MANMAID's algorithm. (And I think we'll be choosing the finite/terminating case.) $\endgroup$ – John Forkosh Aug 5 '17 at 3:52
  • $\begingroup$ @JohnForkosh: S-B-C establishes that there is a bijection. It does not guarantee that the bijection respects order. I can see a simple patch to make a bijection, but it will not make the order on the reals agree with the lexicographic order on the sequences. I haven't found a proof that there is not an order preserving bijection, but I strongly suspect there is not one. $\endgroup$ – Ross Millikan Aug 5 '17 at 4:00
1
$\begingroup$

Consider the Cantor set $C=\{\sum_{n=1}^{\infty}2f(n)3^{-n}: f\in F\}$ where $F$ is the set of all functions $f:\mathbb N\to \{0,1\}.$ For $x\in C$ there is a unique $f_x\in F$ such that $x=\sum_{n=1}^{\infty}2f_x(n)3^{-n},$ and $f_x=f_y\implies x=y.$

So for $x\in C$ let $G(x)=\{n\in \mathbb N: f_x(n)=1\}.$ For $x\in [0,1]$ \ $C$ let $G(x)$ be any member of $2^{\mathbb N}$ that you want, as $G:C\to 2^{\mathbb N}$ is already surjective.

Remark: $G$ is not injective, but neither is the surjection $H(x)=\sum_{i\in x}2^{-i}$ from $2^{\mathbb N}$ to $[0,1]$ in your Q. For example $H(\mathbb N$ \ $\{1\})=H(\{1\})=1/2.$

$\endgroup$
1
$\begingroup$

We can construct an explicit bijection between $[0,1)$ and $2^{\Bbb N}$ as follows. As long as $x$ is not a rational of the form $\frac a{2^n}$ with $1 \le a \lt 2^n$ it has a unique binary expansion so we can match them up. One problem is that numbers of the form $\frac a{2^n}$ have two binary representations, one ending in all $0$s and one ending in all $1$s. The one with all $0$s starts with the finite expansion of $a$ and the one with all $1$s starts with the finite expansion of $a-1$, both padded on the left with zeros to make $n$ bits. The other problem is that we have excluded $1$ from the real interval so we have nothing to match with $1,1,1,1,\ldots $

Given a rational of the form $\frac a{2^n}$ with $a$ odd so the fraction is in lowest terms, let $m$ be the minimum value so that $2^m \gt a$. If $n-m$ is even we will make a correspondence to a sequence with an infinite run of $0$s while if $n-m$ is odd we will make a correspondence to a sequence with an infinite run of $1$s. We let $k=\lfloor \frac {n-m}2 \rfloor$, then the real $\frac a{2^n}$ corresponds to the binary expansion of $\frac a{2^{n-k}}$ using the terminating version if $k$ is even and the infinite $1$s if $k$ is odd. Finally if $a=1$ we push all the expansions down by $1$ to make $1,1,1,1,\ldots $ correspond to $\frac 12$.

$\endgroup$
  • $\begingroup$ Sir, I posted a proof-verification here. I think it is finally complete! (Also you can see the edited answer here) $\endgroup$ – MAN-MADE Aug 5 '17 at 16:17

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.