Tricki

## How to change "for all x there exists y" into "there exists y such that for all x"

### Quick description

If you have a statement of the form but what you actually want is the uniform statement , then you may be able to do it if you can strengthen the first statement to say something like "for every the set of such that fails is small". What's more, there are many different notions of smallness that can be used for the purpose. This gives us a general technique for finding mathematical objects that have many different properties simultaneously.

### Prerequisites

Basic concepts of undergraduate mathematics. The precise prerequisites vary from application to application.

### General discussion

If is a statement that involves two variables and , then the statement is distinctly weaker than the statement . Why? Because where the first statement gives you, for each , some such that is true, the second gives you a single that works for every . In many contexts one says in the second case that the statement holds uniformly.

A simple example that illustrates the difference: for every finite set of natural numbers there exists a natural number such that for every . However, it is not the case that there exists a natural number such that every element of every finite set of natural numbers is less than or equal to . To put this a different way: every finite set of natural numbers is bounded above, but there is not a uniform bound.

There are many circumstances in mathematics where one has a statement of the form but what one really wants is its uniform version . In general, as the above example shows, a statement does not imply its uniform version. However, surprisingly often it is possible to make a statement uniform. Indeed, many of the most useful theorems and basic principles that one learns in an undergraduate mathematics course can be regarded as tools for doing precisely that. This article gives several examples of statements that can be made uniform, with a different tool used for each. Much more can be said about the tools themselves: this will be left to other articles.

Some of the examples below are slightly artificial in the sense that although we are trying to prove a statement of the form , one would not normally regard oneself as starting with the statement . But they are still examples of situations where one is trying to prove a uniform statement.

Before we start, let us think about the kinds of conditions that will have to be satisfied if we are to have any hope of changing into . For each , let be the set of all such that . Then what we are asking for is that the sets should have a non-empty intersection. So if, for instance, we find that two of them are disjoint then we are immediately doomed. In the example earlier, was a finite set of positive integers, and the sets all had the form . Any two of these have finite intersection, but the intersection of all of these sets is empty.

If we want the sets to have non-empty intersection, then two things will help us: we would like the sets to be large in some way, and we would like there not to be too many different . It is often easier to think of the complements of the being small, and then what we want is for the union of the not to consist of every .

### Example 1: the reals are uncountable, using nested closed intervals

To prove this assertion, we start with a countable set of real numbers. Our aim is then to find a new real number. That is, we would like to prove the statement . Now it is certainly the case that , but much more is true, since the set of such that is so large.

What precisely is the largeness property that will help us? Once we have established that the reals are uncountable we could comment that the complement of this set is the singleton , so the union of the complements is countable and therefore not equal to . But of course we cannot do that here, since it is precisely what we are trying to prove. Instead, we use the following definition of largeness: a set is large if for every pair of real numbers with there is a pair of real numbers with such that contains the closed interval .

If is the set , then is definitely large in this sense: all we have to do is choose and in such a way that doesn't lie between them.

Now let us show that if are large sets, then they have non-empty intersection. This is true because by the definition of largeness we can build a sequence of closed intervals such that for each , , and . A basic theorem of real analysis asserts that such a sequence of intervals has non-empty intersection. (Indeed, it is not hard to prove that the supremum of the belongs to all the intervals.) Therefore, we are done.

### Example 2: a perfect set is uncountable, using the Baire category theorem

A set of real numbers is called perfect if it is closed and has no isolated points. For example, the Cantor set is perfect, and so is the closed interval . Let us show that a non-empty perfect set must be uncountable. Let be a non-empty perfect set and let be a sequence of elements of . Once again, we would like to prove that there is some element that is not equal to any . For this, we use the Baire category theorem, one version of which states that if is a complete metric space, and is a sequence of dense open subsets of , then the intersection of the is non-empty.

The Baire category theorem in this form gives us a notion of largeness: if we define a set to be large if it has a dense open subset, then an intersection of countably many large sets is non-empty: this assertion justifies our thinking of the sets as large.

To apply this to the problem at hand, we again have an obvious definition of : it should be the set , since is a complete metric space (as it is a closed subset of ), the sets are open in , and our aim is to prove that they have non-empty intersection.

By the Baire category theorem, we will be done if each is dense in . So let be any subset of that is open in . By the definition of the subspace topology, is equal to for some set that is open in . If does not belong to , then must contain some other point in , and hence a point in . And if does belong to , then since is by hypothesis not an isolated point there must be at least one other point of that belongs to and hence to . Therefore, is dense, so we are done.

Note that the sets in the previous proof were also open and dense, so we could regard that proof as an application of the Baire category theorem. However, the sets are sufficiently simple for it to be easier to prove the result directly, especially considering that the Baire category theorem in is proved by means of nested closed intervals.

### Example 3: every measurable additive function is linear

Let be a function from to such that for every and . As discussed in this article about using Zorn's lemma, does not have to be of the form . However, it does if is measurable. We also saw in the post just mentioned that if for some particular , then for every that is a rational multiple of . But we want the same for every real number, and not just for pairs of real numbers with rational ratio.

If the result is false, then we can find a positive and two real numbers and such that . So we will be done if we can prove that for every the values of (when ) are all within of each other.

To do this, let us choose a countable collection of open intervals of width such that every real number belongs to at least one , and let us define to be .

Since each is an inverse image under of an open set, and since is measurable, the sets are measurable. Since the union of the is , at least one of them has positive measure. (Here we are using the fact that a union of countably many sets of measure zero has measure zero.) Thus, at least one set is large in a certain sense, though this is unlike the previous two examples in that the complement of a set of positive measure does not have to be small.

However, for this problem just a modest amount of largeness suffices, because has closure properties that can be used to deduce from the fact that it has positive measure that it is in fact all of . Indeed, if and both belong to , then so does , since lies between and .

In order to do this we use a fundamental result in measure theory, the Lebesgue density theorem, which states that for every set of positive measure and every there is an interval such that the measure of is at least times the measure of . (In other words, is "very dense" inside .) Let us apply this result to , with , and let the resulting interval be . So for of the in we know that .

From this we can show that every in the set belongs to . This is because if , then the fact that is closed under addition implies that for any , either or . If , then for every we have that . So for every , either or . This means that the measure of points in that do not belong to is at least , contradicting the fact that two thirds of the points in belong to .

But if every in belongs to and is closed under addition, then it is a straightforward exercise to prove that every sufficiently large real number belongs to (basically because contains the interval for every and after a while these intervals overlap).

Once we have that for every sufficiently large real number, we have it for all positive real numbers, since, as is very easily checked, is also closed under the operation .