A serious problem in Bijection in a Algo

Question

If you have seen this part before, ignore the first part and jump to "Change of the algo here" section

In this post I gave this following Algorithm to generate every element of $2^{\mathbb{N}}$ with given a value $x\in \mathbb{R}_{[0,1)}$

let $x\in \mathbb{R}_{[0,1)}$.

1. If $x=1$, then note that $1_{10}=0.\dot{9}_{10}$ and $0.\dot{9}_{10}=0.\dot{1}_2$

2. Otherwise 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$.

3. 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}}$.

I made this part invisible since this part is not needed after the edit:

But one user(Ross Millikam) argued that I ca not generate $0,1,1,1,\dots$ using this algo! So I wrote "take a sequence $a_1=0.49, a_2=0.499,\dots$, in general $a_n=0.499\dots 9$($n\space 9$s)in base $10$. Now generate the algorithm I gave on $a_1,a_2,\dots$. Generated value of $\lim_{n\to\infty} a_n$ is $0,1,1,\dots$. So the algo generates $0,1,1,\dots$."

Is my argument wrong? Is this algo really do represent the bijection between $\mathbb{R}_{[0,1]}$ and $2^{\mathbb{N}}$ ?

One important things to note:

1. $0.4\dot{9}_{10}=0.0\dot{1}_2=0.1_2=0.5_{10}$

Please, I do not need a alternative answer!!! The link gave already have plenty of that!

---

Change of the algo here:

---

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.

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.

Answer 1

Your argument is wrong because $\lim_n a_n = 1/2$, which binary digits are $0.1$ The $k$-th binary digit of number $x$ and the digits after it are discontinuous at $x$ if $x$ is a fraction $n/2^k$ where $n$ is an odd number.

Your algorithm simply computes the sequence of binary digits of real numbers, and as such, it cannot generate sequences that end up with $111...$.

Edit after your last algorithm update with "the structure"

I think the argument is now fundamentally correct. The function $f$ now maps every number that is not of the form $\frac{m}{2^k}$ to the sequence of its binary digits. You are left with countably many numbers without an image, namely the $\frac{m}{2^k}$ (with $m$ odd) and also countably many missing elements of $2^\mathbb{N}$, namely the sequences that end with an constant sequence of $0$ or a constant sequence of $1$. You can easily obtain a bijection between these two countable sets by enumerating their elements.

Good job!

Answer 2

Yes your argument is wrong.

In your algo, you start with $x = \frac{1}{2}$, do the $2x, \{2x\}$ computations. You end up adding $1$ and don't add anything else.

What is $a_1, a_2, \dots$? That is not part of your algo description and is in no way a proof that your algo works.

EDIT: Your $a_i$ only generate finite sets (call them $S_i$) and never the set (call that $S$) which Ross Millikan was talking about.

You generate a countable number of sets $S_i$ whose union is $S$, but never $S$.

The set corresponding to $\lim a_i$ is not $S$.

Answer 3

I programmed a slight generalization of Manmaid's algorithm, as follows (with discussion and examples below that)...

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* ==========================================================================
 * Function:    rtopown ( r, base, n )
 * Purpose:     Returns the first n most significant terms,
 *              i.e., n smallest "exponents",  in the "expansion"
 *              of real number r>=0 such that
 *                r = \sum_i=1^n (coefficient_i)/(base^exponent_i)
 *              with coefficients,exponents returned in the form
 *              x = { k_1, k_2, ..., k_n } subset N
 *              encoded in the k's as k_i = coefficient_i*1000 + exponent_i
 * --------------------------------------------------------------------------
 * Arguments:   r (I)       double containing 0<=r<1 whose
 *                          representation is wanted
 *              base (i)    int containing "base" for expansion
 *              n (i)       int containing number of subset elements
 *              wanted
 * --------------------------------------------------------------------------
 * Returns:    ( int * )    pointer to calloc()'ed array of int's
 *                          containing results, followed by -1.
 *                          If fewer than n required, e.g., r=0.5,base=2
 *                          returns {1001,-1}, then the -1 signals end.
 *                          Any error returns NULL pointer.
 * --------------------------------------------------------------------------
 * Notes:     o See  https://math.stackexchange.com/questions/2383021/
 *              for discussion.
 *            o caller should free() returned pointer after use.
 * ======================================================================= */
/* --- entry point --- */
int *rtopown ( double r, int base, int n ) {
  /* --- allocations and declarations --- */
  double rfrac = r;         /* iterated fractional part */
  int   rint  = 0,          /* integer part */
        expon = 0,          /* current base^expon exponent */
        nterms = 0,         /* #coefs,exponents saved in x[] */
        *x = NULL;          /* ptr to returned set of expons */
  /* --- initialization --- */
  if ( base < 2 ) goto end_of_job;       /* base out-of-bounds */
  if ( r < 0.0  ) goto end_of_job;       /* r out-of-bounds */
  if ( n<0 || n>255  ) goto end_of_job;  /* too many n requested */
  if ( (x = calloc(n+1,sizeof(int)))     /* allocate n+1 ints */
  ==   NULL ) goto end_of_job;           /* quit if calloc() failed */
  /* --- determine k_1,k_2,...,k_n --- */
  for ( expon=1; nterms<n; expon++ ) {   /* each power of base */
    rfrac *= base;                       /* multiply fractional part */
    if ( (rint = (int)(floor(rfrac)+0.1)) /* int part of multiplied frac */
    > 0 ) { x[nterms++] = 1000*rint + expon; /* save coefficient,exponent */
            rfrac -= (double)rint; }     /* save next fractional part */
    if ( rfrac <= 0.0 ) break; }         /* r "expansion" completed */
  /* --- end-of-job --- */
  x[nterms] = (-1);                      /* "trailer record" */
  end_of_job: return ( x );              /* back to caller */
  } /* --- end-of-function rtopown() --- */

/* ==========================================================================
 * Function:    main ( int argc, char *argv[] )
 * Purpose:     test driver for rtopown()
 * --------------------------------------------------------------------------
 * Arguments:   argc        #command-line args
 *              argv[1]     r    (default: .375)
 *                          Note: r<0 uses -1/r, e.g., -3 for 1/3
 *              argv[2]     base (default: 2)
 *              argv[3]     n    (default: 24)
 * --------------------------------------------------------------------------
 * Returns:     ( int )     always 0
 * --------------------------------------------------------------------------
 * Notes:     o See  https://math.stackexchange.com/questions/2383021/
 *              for discussion.
 * ======================================================================= */
/* --- entry point --- */
int main ( int argc, char *argv[] ) {
  double r = ( argc>1? atof(argv[1]) : 0.375 );
  int base = ( argc>2? atoi(argv[2]) : 2     ),
         n = ( argc>3? atoi(argv[3]) : 24    );
  int   *rtopown(), *x = rtopown((r>=0.?r:-1.0/r),base,n), i=0;
  printf("rtopown(r=%.16f,base=%d,n=%d) =",r,base,n);
  if ( x != NULL ) while ( x[i] >= 0 ) {
    printf("%s%s%d/%d^%02d",(i%7==0?"\n  ":""),(i<1?"   ":" + "),
    x[i]/1000,base,x[i]%1000); i++; }
  printf("\n"); return ( 0 );
  } /* --- end-of-function main() --- */
/* --- end-of-file rtopown.c --- */

So a sample run of the form

bash-4.3$ ./rtopown .875 2
rtopown(r=0.8750000000000000,base=2,n=24) =
     1/2^01 + 1/2^02 + 1/2^03

just indicates that $0.875=\frac1{2^1}+\frac1{2^2}+\frac1{2^3}$, or $(1,1,1,0,0,0,\ldots)$ in preceding notation. But that's just the default "base $2$", so to speak, which is that 2 on the command line. We can also expand .875 in (inverse) powers of 3 or any other base, e.g.,

bash-4.3$ ./rtopown .875 3
rtopown(r=0.8750000000000000,base=3,n=24) =
     2/3^01 + 1/3^02 + 2/3^03 + 1/3^04 + 2/3^05 + 1/3^06 + 2/3^07
   + 1/3^08 + 2/3^09 + 1/3^10 + 2/3^11 + 1/3^12 + 2/3^13 + 1/3^14
   + 2/3^15 + 1/3^16 + 2/3^17 + 1/3^18 + 2/3^19 + 1/3^20 + 2/3^21
   + 1/3^22 + 2/3^23 + 1/3^24

which shows the first 24 terms of $.875=\frac2{3^1}+\frac1{3^2}+\frac2{3^3}+\cdots$. And in (inverse) powers of 4 we again get a simple form,

bash-4.3$ ./rtopown .875 4
rtopown(r=0.8750000000000000,base=4,n=24) =
     3/4^01 + 2/4^02

Note that only in "base 2" are the numerators always 1. Generally, they're $1\le\mbox{numerator}\le\mbox{base}-1$. Nevertheless, it's still entirely Manmaid's original algorithm. He simply checks $2x\ge1$, whereas I'm checking $\mbox{base}\times x\ge1$, and when it is I take that integer part as the numerator for the corresponding term in the expansion.

Now, as per the remarks concerning $(1,0,0,0,\ldots)$ versus $(0,1,1,1,\ldots)$, where some suggested Manmaid's algorithm couldn't generate the latter,...

bash-4.3$ ./rtopown .5 2  
rtopown(r=0.5000000000000000,base=2,n=24) =
     1/2^01

indeed corresponds to $(1,0,0,0,\ldots)$ (and rerunning it won't do anything different:). But

bash-4.3$ ./rtopown .499999999 2
rtopown(r=0.4999999990000000,base=2,n=24) =
     1/2^02 + 1/2^03 + 1/2^04 + 1/2^05 + 1/2^06 + 1/2^07 + 1/2^08
   + 1/2^09 + 1/2^10 + 1/2^11 + 1/2^12 + 1/2^13 + 1/2^14 + 1/2^15
   + 1/2^16 + 1/2^17 + 1/2^18 + 1/2^19 + 1/2^20 + 1/2^21 + 1/2^22
   + 1/2^23 + 1/2^24 + 1/2^25

does correspond to $(0,1,1,1,\ldots)$. So, it's just in the $\underset{x\to0.5}\lim x$ that you get $(1,0,0,0,\ldots)$ for that limit case $x=0.5$. But as you approach the limit you get $(0,1,1,1,\ldots)$ as closely as you like.