Distance in Cantor space

Question

We have $C = 2^\mathbb{N}$ and we identify the Cantor set with the image of $C$ via:

$ t\colon C \rightarrow [0,1], \left(x_n\right)_n \mapsto \sum_{n=1}^{\infty}\frac{2x_n}{3^n} $
Now if $x,y\in t(C)$ and $\lvert x - y \rvert < 3^{-N}$ for some $N\in \mathbb{N}$ then the first $N$ digits of $x$ and $y$ coincide.

Now intuitively this seems very clear, however I cant seem to formalize it. I tried by contradiction i.e. let $j<N$ s.t $x_j \neq y_j$, and then tried to bound the distance from below but I couldnt finish the bound. How can one prove this?

Answer 1

One can use induction to prove

• $A(N)$ : If $(x_n), (y_n) \in C$ such that $\lvert t((x_n)) - t((y_n)) \rvert < 3^{-N}$, then $x_n = y_n$ for $n \le N$.

As the base case take $N = 0$ for which $A(0)$ it is trivially true.

Now assume that $A(N)$ is true. We prove that $A(N+1)$ is true.

Consider $(x_n), (y_n) \in C$ such that $\lvert t((x_n)) - t((y_n)) \rvert < 3^{-(N+1)}$ which means that $$d := \sum_{n=1}^\infty \frac{2x_n}{3^n} - \sum_{n=1}^\infty \frac{2y_n}{3^n}$$ satiesfies $\lvert d \rvert < 3^{-(N+1)}$.

Using $A(N)$ we get $x_n = y_n$ for $n \le N$ and therefore $$d = \sum_{n=N+1}^\infty \frac{2(x_n-y_n)}{3^n} .$$

Assume that $x_{N+1} \ne y_{N+1}$, w.l.o.g. $x_{N+1} = 1, y_{N+1} = 0$. With $$R = \sum_{n=N+2}^\infty \frac{2(x_n-y_n)}{3^n}$$ we get $$d = \frac{2}{3^{N+1}} + R .$$

We have $$\lvert R \rvert \le \sum_{n=N+2}^\infty \frac{2\lvert x_n-y_n \rvert}{3^n}\le \sum_{n=N+2}^\infty \frac{2}{3^n} = \frac{2}{3^{-(N+2)}}\sum_{n=0}^\infty \frac{1}{3^n} = \frac{2}{3^{-(N+2)}} \frac 3 2 = \frac{1}{3^{-(N+1)}}. $$ Since $R \ge - \lvert R \rvert$, we get $$d \ge \frac{2}{3^{N+1}} - \lvert R \rvert \ge \frac{2}{3^{N+1}} -\frac{1}{3^{N+1}} = 3^{-(N+1)} $$

which is a contradiction.

Answer 2

Here's a detailed proof for $N=1$.

The set $C$ is the disjoint union of $C \cap [0,1/3]$ and $C \cap [2/3,1]$. For points in $C \cap [0,1/3]$, their first base 3 digit is $0$. For points in $C \cap [2/3,1]$, their first base 3 digit is $2$. There is a lower bound of $1/3$ between each point of $C \cap [0,1/3]$ and each point of $C \cap [2/3,1]$, so if $x,y \in C$ have distance $<1/3$ then either both are in $C \cap [0,1/3]$ or both are in $C \cap [2/3,1]$, hence both have the same $1^{\text{st}}$ base 3 digit (I'm tempted to call that a trigit, but I won't).

For $N=2$ one uses that $C$ is equal to the union of its intersection with $2^2=4$ subintervals, namely

• $[0,1/9]$ and $[2/9,3/9]$ and $[6/9,7/9]$ and $[8/9,1]$.

Those $2^2$ intervals corresond to the $2^2$ different assignment of the first $2$ base 3 digits, namely

• $.00$ and $.02$ and $.20$ and $.22$ (respectively).

Any two of these $4$ subintervals have a lower distance bound of $1/3^2$. It follows that if two points of $C$ have the same first $2$ base 3 digits then their distance is $<1/3^2$.

For general value of $N$, the standard middle-thirds construction of $C$ shows (by induction) that $C$ is the disjoint union of its intersections with $2^N$ pairwise disjoint intervals. These $2^N$ intervals correspond bijectively with the $2^N$ possible assignments of a sequence of $N$ zeros and twos, i.e. all possible assignments of the first $N$ digits of the base 3 expansion of an element of $C$. The endpoints of each of these intervals is a rational number with denominator $3^N$, and therefore the distance between two points in two distinct ones of these intervals is bounded below by $3^{-N}$. If two points of $C$ have distance $< 3^{-N}$, it follows that they lie in the same one of those $2^N$ intervals, and hence they have the same first $N$ base 3 digits.