Co-Null Sets

Often in mathematics one wants to show that certain object exist. While some times the object can be explicitly constructed, this is often achieved by some indirect approach. One very common way of doing this is to apply some form of the axiom of choice which provides, say, a basis for any vector space. Other example is provided in the proof that there are Lebesgue measurable sets on ${{\mathbb R}}$ which are not Borel sets. This is done by a (infinite) counting argument: there are ${2^c}$ measurable sets, where ${c}$ is the cardinality of ${{\mathbb R}}$ (in particular all subsets of the Cantor Set which is uncountable and has measure ${0}$ are Lebesgue measurable sets), but there are only ${c}$ Borel sets in ${{\mathbb R}}$. (On the other hand to prove that not all subset of ${{\mathbb R}}$ is Lebesgue measurable we need the axiom of choice).

A surprisingly fruitful idea in this direction is to prove that the object we are looking for not only exists, but actually most of the objects (in some collection) satisfy the properties we need. More concretely, one can show that there is a point in, say, a measure space satisfying certain property by showing that almost all points in that measure space have the desired property. The concept behind this idea is to have some notion of very large or co-null sets and to prove that the set of points satisfying the property we want is a very large set in the sense introduced. A very important feature of the notion of co-null is that the intersection of co-null sets is still co-null. Then the proof goes by splitting the desired properties into several weaker properties and prove that for each of those weaker properties there is a co-null set of points that satisfies it.
I will present three examples of such notions of co-null sets, which depend on different structures, and include examples of existence proofs using those notions: sets of full measure in a measure space, comeager sets (also known as sets of second category or residual sets) in topological spaces and the more surprisingly example of winning sets in metric spaces.

1. Measure theory

Let ${(X,\mathcal{B},\mu)}$ be a measure space and assume that ${\mu(X)>0}$. A set ${A\in \mathcal{B}}$ has full measure if ${\mu(X\setminus A)=0}$. Thus the notion of co-null set is defined in terms of its complement ${X\setminus A}$, which has to be very small (in measure theory this means of course having ${0}$ measure).
By the definition of measure we have that the intersection of countably many co-null sets is still co-null. Also, since we require ${\mu(X)>0}$ (which is the same as forbidding the trivial case where the measure doesn’t give any information) the empty set is not co-null. As a trivial corollary we have that countable intersections of co-null sets is non-empty. We now illustrate this concept with the proof of existence of normal numbers.

A number ${x\in(0,1)}$ can be written in binary as ${x=0.a_1a_2...a_n...}$. Since we want this representation to be unique we assume that this an infinite sequence and does not terminate in an infinite string of ${1}$‘s, so that ${\frac12}$ is written as ${0.1000...}$.

We say that ${x}$ is ${2}$normal if for any finite binary string ${b_0b_1...b_{n-1}}$, the number of times it appear as a substring of ${a_1a_2...}$ is the expected value, i.e. for any ${n\in {\mathbb N}}$ and ${(b_0,...,b_{n-1})\in \{0,1\}^n}$ we have

$\displaystyle \lim_{N\rightarrow \infty} \frac{|\{k\leq N:a_{k+i}=b_i \forall i\in[n]\}|}N=\frac1{2^n}$

where, ${[n]:=\{0,1,...,n-1\}}$. This notion can be defined for basis other than ${2}$, and so for any ${m\in {\mathbb N}}$ we can write ${x\in(0,1)}$ in basis ${m}$ uniquely by ${\displaystyle x=\sum_{k=1}^\infty \frac{a_k}{m^k}}$ where ${0\leq a_k and not ending in infinitely many ${a_k=m-1}$. Then ${x}$ is ${m}$-normal if for any ${n\in {\mathbb N}}$ and ${(b_0,...,b_{n-1})\in [m]^n}$ we have

$\displaystyle \lim_{N\rightarrow \infty} \frac{|\{k\leq N:a_{k+i}=b_i \forall i\in[n]\}|}N=\frac1{m^n}\ \ \ \ \ (1)$

Finally we say that a number is normal if it is ${m}$-normal for all ${m\in{\mathbb N}}$.

Constructing explicitly normal numbers is a hard problem, although there are nice results concerning ${m}$-normal numbers for a single ${m}$. In particular, it is an open problem to determine whether constants such as ${\pi}$, ${e}$, ${\sqrt{2}}$ and ${\zeta(3)}$ are normal.

We will now prove that normal numbers exist, by showing that the set of normal numbers has full measure in ${(0,1)}$. As immediate corollaries we get that each number in ${(0,2)}$ is the sum of two normal numbers, and each number of ${(0,1)}$ is the product of two normal numbers, which are much stronger results than just existence of normal numbers.

The idea is to prove that, for each fixed ${m\in {\mathbb N}}$, the set ${\mathcal{N}_m}$ of ${m}$-normal numbers has full measure. If so, then the countable intersection of all ${\mathcal{N}_m}$ for ${m\in {\mathbb N}}$ also has full measure. To prove that ${\mathcal{N}_m}$ has full measure we note that ${x\in \mathcal{N}_m}$ if and only if the condition (1) is satisfied for all ${n\in {\mathbb N}}$ and ${(b_0,...,b_{n-1})\in [m]^n}$. Since ${{\mathbb N}}$ is countable and for each ${n}$ the set ${[m]^n}$ is finite, it is sufficient to prove that the set of numbers that satisfy (1) for a single ${n\in {\mathbb N}}$ and ${(b_0,...,b_{n-1})\in [m]^n}$ has full measure, because again the (countable) intersection of those ${x\in (0,1)}$ that respect (1) for ${n\in {\mathbb N}}$ and ${(b_0,...,b_{n-1})\in [m]^n}$ will also have full measure. We consider the sets

${\displaystyle A_k:=\left\{x=\sum_{j=1}^\infty \frac{a_j}{m^j}\in (0,1):a_{k+i}=b_i \forall i\in[n]\right\}}$

and let ${f_k}$ be the characteristic function of ${A_k}$. In the Lebesgue measure, or uniform distribution in ${(0,1)}$, the expectation ${\mathop{\mathbb E}(f_k)}$ is just the measure of ${A_k}$ which is clearly ${m^{-n}}$. Notice that now the condition (1) is equivalent to the statement

$\displaystyle \lim_{N\rightarrow \infty}\frac1N\sum_{k=1}^Nf_k(x)=\frac1{m^n}=\mathop{\mathbb E}(f_k) \ \ \ \ \ (2)$

The fact that the set of points ${x\in(0,1)}$ that respect (2) has full measure would be a direct application of the (Strong) Law of Large Numbers, if all ${f_k}$ were independent. This is not always true (if ${n>1}$ then ${f_k}$ and ${f_{k+1}}$ are usually not independent) however – using the notation ${a+B:=\{a+b:b\in B\}}$ – if the set ${k_1+[n]}$ is disjoint from ${k_2+[n]}$ we have that ${A_{k_1}}$ and ${A_{k_2}}$ are independent and so are its characteristic functions.

Thus we have for each congruence class${\mod n}$ the functions ${f_k}$ are independent and so, for each ${j\in[n]}$, applying the Law of Large Numbers we get

$\displaystyle \lim_{N\rightarrow \infty}\frac1N\sum_{k=1}^Nf_{kn+j}(x)=\mathop{\mathbb E}(f_k)=\frac1{m^n}\qquad\qquad \text{a.e. }x\in(0,1)$

We can now sum this last equation for ${j\in[n]}$ to get what (2) and this concludes the proof that ${\mathcal{N}_m}$ has full measure and so do the set of normal numbers.

2. Topology

We will now use a different structure, namely topology, to construct a another notion of co-null set and then use that notion to prove existence of continuous functions that are nowhere differentiable.

A set ${A}$ in some topological space is nowhere dense if for all open set ${U}$, the intersection ${A\cap U}$ is not dense in ${U}$. Equivalently ${A}$ is nowhere dense if the interior of its closure, ${int(\overline{A})}$, is empty. A set is called meager if it is the countable union of nowhere dense sets. From this definition we immediately get that the countable union of meager sets is meager. Finally we call a set residual if its complement is meager, and residual sets will play the role of full measure sets. An important feature of that analogy is that countable intersection of residual sets is still a residual set.

The other important desired property is that the empty set is not residual, or in other words, the space itself is not meager. Thus we will reduce our attention only to such spaces. A very useful tool to determine if a given space is meager or not is given by the Baire Category Theorem, which states that a complete metric space is never meager.

We remark that the two notions of co-null sets–full measure and residual–are somehow “independent”, in the sense that we can have in ${{\mathbb R}}$ a meager set of full measure, and so the complement is a residual set of ${0}$ measure. This classical fact is explored in this discussion.

We now use this notion to prove the following (also classical) theorem:

Theorem 1 There exist continuous functions in ${[0,1]}$ which are nowhere differentiable, i.e., for any ${x\in [0,1]}$, the limit that defines the derivative at ${x}$ don’t exist.

Recall that ${C[0,1]}$ with the sup distance is a complete metric space, so by the Baire category theorem it is not meager. We will show that the set of nowhere differentiable functions is residual, and thus is non-empty.

Let ${E_n}$ be the set of all ${f\in C[0,1]}$ for which there is ${x_0\in [0,1]}$ (depending on ${f}$) such that ${|f(x)-f(x_0)|\leq n|x-x_0|}$ for all ${x\in [0,1]}$. We shall prove that ${E_n}$ is nowhere dense, but let’s first derive theorem 1 from the that fact.

Let ${f\in C[0,1]}$ be differential at some point, say ${x_0\in [0,1]}$. Define the function ${g}$, by ${g(x)=\frac{f(x)-f(x_0)}{x-x_0}}$ if ${x\neq x_0}$ and ${g(x_0)=f^\prime(x_0)}$. By construction ${g}$ is continuous in the compact set ${[0,1]}$ and so it is bounded. If ${n}$ is a natural number which bounds ${g}$, then ${f\in E_n}$. We conclude that the residual set ${C[0,1]\setminus \bigcup E_n}$ contains only nowhere differentiable functions.

We now prove that ${E_n}$ is indeed nowhere dense by contradiction: if ${E_n}$ is not nowhere dense then the closure of ${E_n}$ contains an open set. Assume that ${B(f,r)\subset \overline{E_n}}$. We can find ${g\in B(f,r)}$ such that ${g}$ is piecewise linear with finitely many linear pieces of slope ${\pm 2n}$. One way to do this is to first find, using Weierstrass theorem, a polynomial ${p}$ in ${B(f,R/2)}$ and then find ${g\in B(p,r/2)}$. Then ${g}$ is the limit of some sequence, say ${\{g_k\}_k}$ of functions in ${E_n}$.

Let ${[a,b]}$ be the smallest piece in which ${g}$ is linear (of slope ${\pm 2n}$). Let ${k}$ big enough such that ${\|g-g_k\|<(b-a)n/2}$. Let ${x_0\in [0,1]}$ such that ${|g_k(x)-g_k(x_0)|\leq n|x-x_0|}$ for all ${x\in [0,1]}$. Then ${x_0}$ is in some interval ${[c,d]}$ where ${g}$ is linear. We have:

$\displaystyle \begin{array}{rcl} n(d-c)&=&|g(d)-g(c)|-n(d-c)\\ &=&|g(d)-g_k(d)+g_k(d)-g_k(c)+g_k(c)-g(c)|-n(d-c)\\ &<& (b-a)n+|g_k(c)-g_k(d)|-n(c-d) \leq|g_k(c)-g_k(d)|\\ &\leq& |g_k(c)-g_k(x_0)|+|g_k(x_0)-g_k(d)|\leq n(d-c)\end{array}$

With this contradiction we conclude that ${E_n}$ must be nowhere dense.

3. Metric spaces

A third and not so classic example of a co-null notion is that of Winning Sets, introduced by Schmidt in 1966. The structured spaces we consider for this are the metric space. We now describe a game with two players, Alice and Bob, who take turns choosing open balls in a topological space. This game gives a definition for set to be winning.

Let ${X}$ be a metric space and ${J\subset X}$ be a subset. Let ${0<\alpha,\beta<1}$ be constants. Bob chooses any open ball ${B_0\subset X}$ with radius ${\rho_0}$. Then Alice chooses a ball ${B_1\subset B_0}$ with radius ${\rho_1=\alpha\rho_0}$. Then Bob chooses a ball ${B_2\subset B_1}$ with radius ${\rho_2=\beta\rho_1}$, then Alice chooses a ball ${B_3\subset B_2}$ with radius ${\rho_3=\alpha\rho_2}$ and so on. Let ${x}$ be the (single) point in the intersection of all balls ${B_n}$. If ${x\in J}$ then Alice wins the game. Otherwise Bob wins. If Alice can force a victory, then the set ${J}$ is called ${(\alpha,\beta)}$-winning.

We then call a set ${J}$ ${\alpha}$-winning if it is ${(\alpha,\beta)}$-winning for all ${\beta\in(0,1)}$. It turns out that, for any ${b\geq2}$, the set of numbers which are not normal in basis ${b}$ is a ${\alpha}$ winning set (despite having zero measure) for any ${0<\alpha<1/2}$, and the set of badly approximable numbers (or numbers with bounded denominators in its expansion in continuous fraction) is also a ${\alpha}$-winning set (despite being meager) for ${0<\alpha< 1/2}$.

Thus it may be surprising that the countable intersection of ${\alpha}$-winning sets is still ${\alpha}$-winning. This is proved by proving a strategy for Alice, using the strategies that grant her the victory in each of the winning sets we are intersecting. Also the empty set is clearly not winning, so we have that countable intersections of winning sets is non-empty.

A simple observation is that, for ${J}$ to be ${(\alpha,\beta)}$-winning it must be dense, otherwise in the first turn, Bob chooses a ball ${B_0}$ disjoint from ${J}$ and immediately wins the game. Also, the Hausdorff dimension of a winning set in ${{\mathbb R}^n}$ is always ${n}$, which tells us immediately that some sets cannot hope to be winning.

A number ${x\in {\mathbb R}}$ is badly approximable if there is some ${c>0}$ such that ${\left|x-\frac pq\right|\geq\frac c{q^2}}$ for all rational ${\frac pq}$. This can be prove to be equivalent to having the partial denominators in the continuous fraction bounded. We now use the definition of winning sets and its properties to prove the following: There exist real numbers ${x}$ such that for any rational number ${r}$, the number ${x+r\pi}$ (say) is bad approximable. This is of course a particular case of the fact that for any countable set ${A}$, there are ${x}$ such that all points in ${x+A}$ are badly approximable. And this is an immediate corollary of the fact that badly approximable numbers form a ${\alpha}$-winning set (call it ${B}$) for any ${0<\alpha<1/2}$, because any ${x}$ in the winning set ${\bigcap_{a\in A} (B-a)}$ satisfies the desired property (note that translations of winning sets are still winning).