A normal number is a real number whose infinite sequence of digits in every base $b$ is distributed uniformly in the sense that each of the $b$ digit values has the same natural density $\frac{1}{b}$, also all possible $b^2$ pairs of digits are equally likely with density $\frac{1}{b^2}$, all $b^3$ triplets of digits equally likely with density $\frac{1}{b^3}$, etc.

Using the Borel–Cantelli lemma, Borel proved the normal number theorem:

Theorem. Almost all real numbers are normal, in the sense that the set of non-normal numbers has Lebesgue measure zero.

But counterintutively we know just a very few number of such normal real numbers. This is mainly because Borel's proof is not constructive.

My questions are:

1- Does Borel's proof use axiom of choice? If yes, is this use really essential? In the other words, does Borel's theorem hold even when axiom of choice fails or it possible to have few normal real numbers, say a set of Lebesgue measure zero for such numbers?

2- Is Borel's proof really non-constructive? If yes, what is the source of non-constructiveness in Borel's proof for existence of normal numbers? Axiom of choice or something else?

  • 2
    $\begingroup$ I believe that the answer to the first answer is "no", but I'm not sure, as I haven't seen Borel's proof. In either case, I am fairly certain methods of this paper can be used to prove it without any appeal to choice glyc.dc.uba.ar/santiago/papers/absnor.pdf $\endgroup$
    – Wojowu
    Oct 2 '15 at 17:02
  • $\begingroup$ @Wojowu So why is Borel's proof non-constructive? $\endgroup$ Oct 2 '15 at 17:17
  • 3
    $\begingroup$ There are plenty of ways to do non-constructive proofs without AC. Euclid proved 2300 years ago that there exists a prime larger than $10!!!!!!!!!!!!!!!!!!!!!!!!!$ but to this day there is no explicit example of one. That proof works in PA or maybe even less. $\endgroup$ Oct 2 '15 at 17:51
  • 4
    $\begingroup$ @Wojowu: It is now known that the early school of measure theory (Borel, Lebesgue, Baire) who were very opposed to the axiom of choice did in fact use the axiom of dependent choice implicitly. But what Nate said is true. The lack-of-constructiveness is not due to the axiom of choice, as much as it is due to the law of excluded middle. $\endgroup$
    – Asaf Karagila
    Oct 2 '15 at 17:58
  • 2
    $\begingroup$ I don't know the details of Borel's proof off the top of my head, but I suspect his proof was actually constructive in principle (he may use general theorems which are nonconstructive in full generality, but in the cases that he is applying them their proofs can easily be made constructive). Any description of his proof as "nonconstructive" is probably in an informal sense, meaning that the proof does not explicitly write down an example, even if it is possible to chase through the steps of the proof to find such an example. $\endgroup$ Oct 2 '15 at 18:11

The fact that almost all reals are normal in base $b$ is an application of the Strong Law of Large Numbers. Write the base $b$ expansion as $X = \sum_{i=1}^\infty b^{-i} D_i$ where $X$ is uniform on $[0,1]$ and $D_i$ are iid with $P(D_i = y) = 1/b$ for $y = 0,1,\ldots,b-1$. The Strong Law of Large Numbers applied to the indicators $I(D_i = y)$ says that for each $y = 0,1,\ldots, b-1$, $$\lim_{N \to \infty} \dfrac{1}{N} \sum_{i=1}^N I(D_i=y) = \dfrac{1}{b} $$ The proof (e.g. using fourth moments) makes no use of Axiom of Choice, as far as I can see. If $S_N = \sum_{i=1}^N (I(D_i=y) - 1/b)$, you use independence and Cauchy-Schwarz to get a bound $\mathbb E[S_N^4) \le K N^2$, which implies $\mathbb E \sum_N (S_N/N)^4 \le \sum_N K/N^2 < \infty$, and therefore $\sum_N (S_N/N)^4 < \infty$ almost surely, and in particular $S_N/N \to 0$ almost surely.

EDIT: To make this more explicit, we can say $$\mathbb P\left(\dfrac{|S_N(b,y)|}{N} > \epsilon\right) < \dfrac{K(b)}{\epsilon^4 N^2}$$ Moreover, the event $|S_N(b,y)|/N > \epsilon$ is equivalent to $X$ belonging to an explicit union of intervals in $[0,1]$ of total length $< K(b)/(\epsilon^4 N^2)$. We can construct a function $N(\eta, \epsilon, b)$ for $\eta, \epsilon > 0$ so that $$\sum_{N > N(\eta, \epsilon, b)} \mathbb P\left(\dfrac{|S_N(b,y)|}{N} > \epsilon\right) < \eta$$

If we take $\epsilon = 1/M$ and $\eta = 2^{-b-M} \delta/b$, we get

$$ \sum_{M=1}^\infty \sum_{b=2}^\infty \sum_{y=0}^{b-1} \sum_{N > N(1/M, 2^{-b-M} \delta/b)} \mathbb P\left(\dfrac{|S_N(b,y)|}{N} > \dfrac{1}{M} \right) < \delta $$

Thus we have an explicit sequence of intervals in $[0,1]$ with total length $< \delta$, and every point in the complement of the union of those intervals is normal in every base. For convenience, let's reindex these intervals as $J_n$, $n = 1,2,3,\ldots$.

Now, how do we arrange (without Axiom of Choice) to find points in $G = [0,1] \backslash \bigcup_n J_n$? One way is to construct a nested sequence of closed intervals $G_n$ as follows. We will ensure that $m(G_n \cap G) > (1-(2-2^{-n})\delta) m(G_n)$ and $G_n \cap \bigcup_{j\le n} J_j = \emptyset$. Then the limit of the left endpoints of $G_n$ as $n \to \infty$ is in $G$, as desired.

Start with the interval $G_0 = [0,1]$.
Given $G_{n-1}$, $G_{n-1} \backslash J_n$ is either a single interval $A$ (plus perhaps a single point, which we ignore) or the union of two intervals $A \cup B$. If it's a single interval $A$, we have $m(A \cap G) = m(G_{n-1} \cap G) > (1-(2-2^{-n+1}) \delta) m(A)$. If it's two intervals, $m(A \cap G) + m(B \cap G) > (1-(2-2^{-n+1}) \delta) (m(A) + m(B))$, so

$$\max\left(\dfrac{m(A \cap G)}{m(A)}, \dfrac{m(B \cap G)}{m(B)}\right) > 1-(2-2^{-n+1}) \delta$$ and we choose whichever of $A$ and $B$ gives the largest quotient here (in case of a tie, for definiteness take the one on the left). We want $G_n$ to be closed, so take a slightly smaller closed interval, still maintaining $m(G_n \cap G) > (1 - (2 - 2^{-n})) \delta$. This gives the desired construction.

  • 4
    $\begingroup$ Well, any measure theoretic argument should make use of some axiom of choice (otherwise, it is impossible to construct the usual Lebesgue measure. See this post for example). Although I never seriously looked into it, I keep reading over various places that most of real analysis can be done with DC (Axiom of Dependent Choice). So the original post should have asked whether Borel's proof uses AC beyond DC? $\endgroup$
    – Burak
    Oct 2 '15 at 20:32
  • 2
    $\begingroup$ @Burak: You don't necessarily need to actually construct Lebesgue measure in full generality to make a measure-theoretic argument that a specific set is nonempty because it has positive measure. It may be that every instance in which that argument would appear to use DC, in the application to the specific sets you are looking at you can write down explicit choice functions. $\endgroup$ Oct 2 '15 at 20:40

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.