Completing the proof using strong induction for $E = \bigcap_{n=1}^\infty E_n $

Question

I want to follow up my previous question.

My original question was:

Fix that $E$ is the set of real numbers $x \in [0,1]$ whose decimal expansion contains only the digits $4$ and $7$. Let $S_n$ be the set consisting of all natural numbers not exceeding $10^n$ whose digits consists only of $4$ or $7$. For example, \begin{equation*} \begin{split} S_1 &= \{4, 7\} \\ S_2 &= \{44, 77, 47, 74\} \\ S_3 &= \{444, 744, 474, 447, 774, 747, 477, 777\} \\ \vdots \end{split} \end{equation*}

I want to prove that $E$ can be defined as: \begin{equation*} E = \bigcap_{n=1}^\infty E_n, \textrm{ where } E_n = \cup_{a \in S_n} \left[\frac{a}{10^n}, \frac{a+1}{10^{n}}\right] \end{equation*}

For instance, \begin{equation*} \begin{split} E_1 &= [0.4, 0.5] \cup [0.7, 0.8] \\ E_2 &= [0.44, 0.45] \cup [0.77, 0.78] \cup [0.47, 0.48] \cup [0.74, 0.75] \\ E_3 &= [0.444, 0.445] \cup [0.447, 0.448] \cup [0.474, 0.475] \cup [0.477, 0.478]\\ &\cup [0.744, 0.745] \cup [0.747, 0.748] \cup [0.774, 0.775] \cup [0.777, 0.778] \\ &\vdots \end{split} \end{equation*}

and I had no idea how I could prove $\bigcap_{n=1}^\infty E_n \subseteq E$. My original question also got a wonderful response, but I eventually came up with an alternative proof. Here is that proof:

Let $y \in \bigcap_{n=1}^\infty E_n$. Then, $y \in E_n$ for each $n$ which implies that $y$ is in exactly one of the closed intervals $\left[\frac{a_n}{10^n}, \frac{a_n+1}{10^{n}}\right]$. Define the decimal expansion of $y$ as $y=0.d_1d_2d_3\ldots\;$. First we show that $d_1$ is either $4$ or $7$. STTC that $d_1 \notin \{4, 7\}$.

1. If $d_1 \in \{0, 1, 2, 3\}$, then $y\le0.4$. If $y<0.4$, then $y\notin E_1$, which is not possible. If $y=0.4$, then $y\notin E_2$, which is also not possible.

2. If $d_1 \in \{5, 6\}$, then $0.5\le y \le 0.7$. If $0.5< y < 0.7$, then $y\notin E_1$, which is not possible. If $y=0.5$ or $y=0.7$, then $y \notin E_2$, which is not possible.

3. If $d_1 \in \{8, 9\}$, then $0.8 \le y< 1$. If $0.8 <y< 1$, then $y\notin E_1$, which is not possible. If $y =0.8$, then $y\notin E_2$, which is also not possible.

Thus, $d_1 \in \{4, 7\}$. Similarly, suppose to the contrary that $d_2 \notin \{4, 7\}$. My idea is that I want to show that if $d_2 \notin \{4, 7\}$, then that would force that either $y \notin E_2$ or $y \notin E_3$, which would signal a definite pattern, which is all I want (no need for a formal induction). Thus:

1. If $d_2 \in \{0, 1, 2, 3\}$, then $0.400 \le y \le 0.740$. If $0.400 \le y < 0.440$, then $y \notin E_2$ which is not possible. If $0.440\le y <0.444$, then $y \notin E_3$. If $0.444 \le y < \dots$,

2. If $d_2 \in \{5, 6\}$, then $0.450 \le y \le 0.770$. If $y = 0.45$, then $y \notin E_3$. If $0.45 < y < 0.47 $, then $y \notin E_2$. If $0.47 \le y < 0.474$, then $y \notin E_3$. If $0.474 \le y \dots$,

3. If $d_2 \in \{8, 9\}$, then $0.480 \le y \le 0.80$.

I haven't developed bullet 3. for $d_2$ because I couldn't even complete the argument in the first two bullets for $d_2$. Can someone please suggest how the argument for $d_2$ can be completed? (Again, no need for formal induction. I just want to develop an argument for $d_2$ that is similar to $d_1$.)

Answer 1

Your inductive step, or maybe your proof as a whole, can perhaps be simplified by one of the following two viewpoints:

1. A dynamical viewpoint

Consider the 10-tupling map $f:[0,1]\to [0,1]$,

$$f:x \mapsto 10x \mod 1,$$

where one multiplies $x$ by $10$ and removes the integer part (another way of writing it: $f(x) = 10x - \lfloor10x \rfloor$).

Who cares?

Why define this function? It makes most sense in digit form:

if $x = 0.d_1d_2d_3\ldots,\ $ $f(x) = 0.d_2d_3d_4\ldots$

That is, $f$ acts by shifting all the digits up by one, forgetting the first digit.

From this alone, you can very quickly verify the following points, and you only need the first.

1. If $x\in E$, $f(x)\in E$.
2. Moreover, $f: E \to E$ is a 2-to-1 surjection.
3. For any $n\in \mathbb N$, $f(E_{n+1}) = E_n$. ($f(E_1) = [0,1]$.)

Regarding the second step of your induction: (EDITED.)

A consequence of property 3.:

$$ y \in \bigcap_{n=1}^{\infty} E_n \implies \ \forall\,n\geq 2,\ y \in E_n \stackrel{\text{3.}}\implies \ \forall\,n\geq 2,\ f(y) \in f(E_n) = E_{n-1} \implies f(y) \in \bigcap_{n=1}^\infty E_n. $$

I.e.,

$$ y \in \bigcap_{n=1}^{\infty} E_n \implies f(y) \in \bigcap_{n=1}^\infty E_n.\tag{1} $$

Now suppose $y = 0.d_1d_2d_3\ldots \in \bigcap_{n=1}^\infty E_n$. The digits of $f(y)$ are given by

$$f(y) = 0.e_1e_2e_3\ldots \qquad\text{where, for every }n,\ e_n = d_{n+1}.$$

By (1), we know $f(y) \in \bigcap_{n=1}^\infty E_n$ and so, by your "base case," its first digit is in $\{4,7\}$.

But this first digit, $e_1 = d_2$, is simply the second digit of $y$, so you're done: $d_2 \in \{4,7\}$.

Hopefully you can see how this can be generalised to $d_{n+1}$ (apply $f$ more than once). No inductive assumption required!

2. Aside: a fractal geometry viewpoint

$E$ is really just like the (middle-thirds) Cantor set. So any argument that works for the Cantor set should work here as well (the Cantor set can be defined in terms of base 3 [ternary], rather than base 10, expansions).

The big result you are trying to prove is a special case of one in fractal geometry.

to set this up, it is simple to see that $E$ is an attractor of the following contractions, $f_4, f_7: [0,1] \to [0,1],$

$$f_4(x) = \frac{x+4}{10},\qquad f_7(x) = \frac{x+7}{10}$$

(in digit form, these are: $f_i:0.d_1d_2d_3\ldots \; \mapsto 0.\,\underline{i}\,d_1d_2d_3),$

where attractor here means: $E$ is a compact subset of $[0,1]$ ($[0,1]$ being the domain) such that $E = f_4(E) \sqcup f_7(E)$.

From fractal geometry, it is known that attractors are 1) unique and 2) satisfy the following formula.

$$E = \bigcap_{n= 1}^\infty \;\; \bigcup_{(i_1,\ldots,i_n)\in \{4,7\}^n} \underbrace{f_{i_1}\circ f_{i_2}\circ f_{i_3}\circ \cdots \circ f_{i_n}[0,1]}_{\text{first $n$ digits are }i_1,\ i_2,\ldots i_n} $$

Furthermore, $$ E_n = \bigcup_{(i_1,\ldots,i_n)\in \{4,7\}^n} f_{i_1}\circ f_{i_2}\circ f_{i_3}\circ \cdots \circ f_{i_n}[0,1],$$

where this last equality follows by your definition of $E_n$ E.g.,

$$E_1 = f_4[0,1] \cup f_7[0,1]$$ $$E_2 = f_4\circ f_4[0,1] \cup f_4\circ f_7[0,1] \cup f_7\circ f_4[0,1] \cup f_7\circ f_7[0,1] $$

and so on.

In other words, this formula (or its proof) gives you another altenrative proof/viewpoint.

Other key words which apply: iterated function system, self-similar sets.

Answer 2

For each $n$, there exists an $a_n\in S_n$ such that $y\in \left[\frac{a_n}{10^n},\frac{a_n+1}{10^n}\right]$.

The last two digits of $a_{n+2}$ are either $44,47,74$ or $77$.

Without loss of generality assume that the last two digits of $a_{n+2}$ are $44$. We know that $10^{n+2}y\in [a_{n+2},a_{n+2}+1]$, so $10d_{n+1}+d_{n+2}$ is either $44$ or $45$. Therefore $d_{n+1}=4$.