KAIST POW 2012-18 : Diagonal

Diagonal

 Let $r_1$, $r_2$, $r_3$,... be a sequence of all rational numbers in $(0,1)$ except finitely many numbers. Let $r_j=0.a_{j,1} a_{j,2} a_{j,3} \cdots$ be a decimal representation of $r_j$. (For instance, if $r_j = \frac{1}{3} = 0.3333\cdots$, then $a_1,k = 3$ for any $k$. Prove that the number $0.a_{1,1} a_{2,2} a_{3,3} a_{4,4} \cdots $ given by the main diagonal cannot be a rational number.

 
  Lemma 1. Suppose that $x=a_1 a_2 \cdots $ and $y=b_1 b_2 \cdots $. If $1<|a_i - b_i|<9 $ for some $i\in \mathbb{N}$, then $x \neq y$.

Let $n$ be the smallest index such that $1<|a_n - b_n| <9$. Say $a_n = b_n +p$. If $a_i=b_i$ for all $i<n$, $x-y \geq p*10^{-n} - \sum_{i=n+1}^\infty 9*10^{-i} = (p-1)*10^{-n} > 0$. So $x \neq y$. Otherwise, say $m$ be the smallest index such that $a_m \neq b_m$. If $a_m > b_m$, $x-y > 10^{-m} - \sum_{i=m+1}^\infty 9*10^{-i} + (9+k)*10^{-n} = (9+k)*10^{-n} >0$. Otherwise, $y-x > 10^{-m} - \sum_{i=m+1}^\infty 9*10^{-i} + (9-k)*10^{-n} = (9-k)*10^{-n} >0$. Therefore, $x \neq y$. 

 Lemma 2. A number is rational if and only if a decimal representation of the number has a periodic part after some indices. 

 Converse is trivial. Let $x$ be a rational. Then we can construct decimal representations of $x$ by an algorithm. If $x=q/p$ for some $p,q$, $$q = g_1 * p + r_1$$ $$10r_1 = g_2 * p + r_2$$ $$\cdots$$ $$10r_n =g_n * p + r_{n+1}$$ where $r_n \leq p$ for all $n\in \mathbb{N}$ to satisfy $0 \leq g_n \leq 9$. Then $0.g_1 g_2 \cdots $ is a decimal representation. By pigeon hole principle, there exist $k, l < p$ such that $r_k = r_l$, thus $g_{k+1} = g_{l+1}$. So $x=0.g_1 g_2 \cdots \dot{g_{k+1}} \cdots \dot{g_{l+1}}$.

 Proof. Let $b_i = a_{i,i}$. Assume the contrary that $0.b_1 b_2 \cdots $ is rational. Then there is a periodic part given by $0.b_1 \cdots b_k \dot{b_{k+1}} \cdots \dot{b_{l+l}}$ for some $k,l \in \mathbb{N}$.

 Define a subset of $\mathbb{Q}\cap(0,1)$ by $X_n = \{0.b_1 \cdots b_k \dot{c_{k+1}} \cdots \dot{c_{k+nl}} | c_i=0,...,9 , 1<|c_i - b_i|<9$ for all $k < i \leq k+nl\}$. Let $X=\cup_{n=1}^\infty$. Since $|X_n|$ goes to infinity, $X$ is a infinite subset of $\mathbb{Q}\cap(0,1)$ even though it contains no $r_i$ with $i>k$ by Lemma 1 above. This contradict to $\{r_i\}$ covers all rationals in $(0,1)$ excepts finitely many numbers. Therefore, $0.b_1 b_2 \cdots $ is not rational.