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 which are not Borel sets. This is done by a (infinite) counting argument: there are measurable sets, where is the cardinality of (in particular all subsets of the Cantor Set which is uncountable and has measure are Lebesgue measurable sets), but there are only Borel sets in . (On the other hand to prove that not all subset of 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 be a measure space and assume that . A set has full measure if . Thus the notion of co-null set is defined in terms of its complement , which has to be very small (in measure theory this means of course having 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 (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 can be written in binary as . Since we want this representation to be unique we assume that this an infinite sequence and does not terminate in an infinite string of ‘s, so that is written as .
We say that is –normal if for any finite binary string , the number of times it appear as a substring of is the expected value, i.e. for any and we have
where, . This notion can be defined for basis other than , and so for any we can write in basis uniquely by where and not ending in infinitely many . Then is -normal if for any and we have
Finally we say that a number is normal if it is -normal for all .
Constructing explicitly normal numbers is a hard problem, although there are nice results concerning -normal numbers for a single . In particular, it is an open problem to determine whether constants such as , , and are normal.
We will now prove that normal numbers exist, by showing that the set of normal numbers has full measure in . As immediate corollaries we get that each number in is the sum of two normal numbers, and each number of 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 , the set of -normal numbers has full measure. If so, then the countable intersection of all for also has full measure. To prove that has full measure we note that if and only if the condition (1) is satisfied for all and . Since is countable and for each the set is finite, it is sufficient to prove that the set of numbers that satisfy (1) for a single and has full measure, because again the (countable) intersection of those that respect (1) for and will also have full measure. We consider the sets
and let be the characteristic function of . In the Lebesgue measure, or uniform distribution in , the expectation is just the measure of which is clearly . Notice that now the condition (1) is equivalent to the statement
The fact that the set of points that respect (2) has full measure would be a direct application of the (Strong) Law of Large Numbers, if all were independent. This is not always true (if then and are usually not independent) however – using the notation – if the set is disjoint from we have that and are independent and so are its characteristic functions.
Thus we have for each congruence class the functions are independent and so, for each , applying the Law of Large Numbers we get
We can now sum this last equation for to get what (2) and this concludes the proof that has full measure and so do the set of normal numbers.
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 in some topological space is nowhere dense if for all open set , the intersection is not dense in . Equivalently is nowhere dense if the interior of its closure, , 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 a meager set of full measure, and so the complement is a residual set of measure. This classical fact is explored in this discussion.
We now use this notion to prove the following (also classical) theorem:
Recall that 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 be the set of all for which there is (depending on ) such that for all . We shall prove that is nowhere dense, but let’s first derive theorem 1 from the that fact.
Let be differential at some point, say . Define the function , by if and . By construction is continuous in the compact set and so it is bounded. If is a natural number which bounds , then . We conclude that the residual set contains only nowhere differentiable functions.
We now prove that is indeed nowhere dense by contradiction: if is not nowhere dense then the closure of contains an open set. Assume that . We can find such that is piecewise linear with finitely many linear pieces of slope . One way to do this is to first find, using Weierstrass theorem, a polynomial in and then find . Then is the limit of some sequence, say of functions in .
Let be the smallest piece in which is linear (of slope ). Let big enough such that . Let such that for all . Then is in some interval where is linear. We have:
With this contradiction we conclude that 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 be a metric space and be a subset. Let be constants. Bob chooses any open ball with radius . Then Alice chooses a ball with radius . Then Bob chooses a ball with radius , then Alice chooses a ball with radius and so on. Let be the (single) point in the intersection of all balls . If then Alice wins the game. Otherwise Bob wins. If Alice can force a victory, then the set is called -winning.
We then call a set -winning if it is -winning for all . It turns out that, for any , the set of numbers which are not normal in basis is a winning set (despite having zero measure) for any , and the set of badly approximable numbers (or numbers with bounded denominators in its expansion in continuous fraction) is also a -winning set (despite being meager) for .
Thus it may be surprising that the countable intersection of -winning sets is still -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 to be -winning it must be dense, otherwise in the first turn, Bob chooses a ball disjoint from and immediately wins the game. Also, the Hausdorff dimension of a winning set in is always , which tells us immediately that some sets cannot hope to be winning.
A number is badly approximable if there is some such that for all rational . 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 such that for any rational number , the number (say) is bad approximable. This is of course a particular case of the fact that for any countable set , there are such that all points in are badly approximable. And this is an immediate corollary of the fact that badly approximable numbers form a -winning set (call it ) for any , because any in the winning set satisfies the desired property (note that translations of winning sets are still winning).