Tricki
a repository of mathematical know-how

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 \forall x\ \exists y\ P(x,y) but what you actually want is the uniform statement \exists y\ \forall x\ P(x,y), then you may be able to do it if you can strengthen the first statement to say something like "for every x the set of y such that P(x,y) 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 P(x,y) is a statement that involves two variables x and y, then the statement \forall x\ \exists y\ P(x,y) is distinctly weaker than the statement \exists y\ \forall x\ P(x,y). Why? Because where the first statement gives you, for each x, some y such that P(x,y) is true, the second gives you a single y that works for every x. 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 A of natural numbers there exists a natural number m such that n\leq m for every n\in A. However, it is not the case that there exists a natural number m such that every element of every finite set of natural numbers is less than or equal to m. 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 \forall x\ \exists y\ P(x,y) but what one really wants is its uniform version \exists y\ \forall x\ P(x,y). 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 \exists y\ \forall x\ P(x,y), one would not normally regard oneself as starting with the statement \forall x\ \exists y\ P(x,y). 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 \forall x\ \exists y into \exists y\ \forall x. For each x, let U_x be the set of all y such that P(x,y). Then what we are asking for is that the sets U_x 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, x was a finite set of positive integers, and the sets U_x all had the form \{n,n+1,n+2,\dots\}. Any two of these have finite intersection, but the intersection of all of these sets is empty.

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

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

To prove this assertion, we start with a countable set x_1,x_2,x_3,\dots of real numbers. Our aim is then to find a new real number. That is, we would like to prove the statement \exists y\in\mathbb{R}\ \forall n\in\mathbb{N}\ x_n\ne y. Now it is certainly the case that \forall n\in\mathbb{N}\ \exists y\in\mathbb{R}\ x_n\ne y, but much more is true, since the set of y such that x_n\ne y 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 x_n, so the union of the complements is countable and therefore not equal to \mathbb{R}. 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 Y is large if for every pair of real numbers a,b with a<b there is a pair of real numbers c,d with a\leq c<d\leq b such that Y contains the closed interval [c,d].

If Y_n is the set x_n\ne y\}, then Y_n is definitely large in this sense: all we have to do is choose c and d in such a way that x_n doesn't lie between them.

Now let us show that if Y_1,Y_2,\dots 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 [a_n,b_n] such that a_n<b_n for each n, a_1\leq a_2\leq\dots, and b_1\geq b_2\geq\dots. 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 a_n 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 [0,1]. Let us show that a non-empty perfect set must be uncountable. Let X be a non-empty perfect set and let x_1,x_2,x_3,\dots be a sequence of elements of X. Once again, we would like to prove that there is some element y that is not equal to any x_n. For this, we use the Baire category theorem, one version of which states that if X is a complete metric space, and U_1,U_2,\dots is a sequence of dense open subsets of X, then the intersection of the U_n 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 U_n as large.

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

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

Note that the sets Y_n 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 Y_n are sufficiently simple for it to be easier to prove the result directly, especially considering that the Baire category theorem in \mathbb{R} is proved by means of nested closed intervals.

Example 3: every measurable additive function is linear

Let f be a function from \mathbb{R} to \mathbb{R} such that f(x+y)=f(x)+f(y) for every x and y. As discussed in this article about using Zorn's lemma, f does not have to be of the form f(x)=\lambda x. However, it does if f is measurable. We also saw in the post just mentioned that if f(x)=\lambda x for some particular x, then f(y)=\lambda y for every y that is a rational multiple of x. But we want the same \lambda 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 \epsilon and two real numbers x and y such that |x^{-1}f(x)-y^{-1}f(y)|>\epsilon. So we will be done if we can prove that for every \epsilon>0 the values of f(x)/x (when x\ne 0) are all within \epsilon of each other.

To do this, let us choose a countable collection of open intervals I_n of width \epsilon such that every real number belongs to at least one I_n, and let us define A_n to be f(x)/x\in I_n\}.

Since each A_n is an inverse image under f of an open set, and since f is measurable, the sets A_n are measurable. Since the union of the A_n is \mathbb{R}\setminus\{0\}, 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 A_n 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 A_n has closure properties that can be used to deduce from the fact that it has positive measure that it is in fact all of \mathbb{R}\setminus\{0\}. Indeed, if x and y both belong to A_n, then so does x+y, since (f(x)+f(y))/(x+y) lies between f(x)/x and f(y)/y.

In order to do this we use a fundamental result in measure theory, the Lebesgue density theorem, which states that for every set A of positive measure and every \delta>0 there is an interval J such that the measure of A\cap J is at least (1-\delta) times the measure of J. (In other words, A is "very dense" inside J.) Let us apply this result to A_n, with \delta=1/3, and let the resulting interval be J=[a,a+2h]. So for 2/3 of the x in J we know that f(x)/x\in I_n.

From this we can show that every z in the set [2a+h,2a+2h] belongs to A_n. This is because if z\notin A_n, then the fact that A_n is closed under addition implies that for any x, either x\notin A_n or z-x\notin A_n. If z\in [2a+h,2a+2h], then for every x\in[a,a+h] we have that z-x\in[a,a+2h]. So for every x\in[a,a+h], either x\notin A_n or z-x\notin A_n. This means that the measure of points in [a,a+2h] that do not belong to A_n is at least h, contradicting the fact that two thirds of the points in [a,a+2h] belong to A_n.

But if every z in [2a+h,2a+2h] belongs to A_n and A_n is closed under addition, then it is a straightforward exercise to prove that every sufficiently large real number belongs to A_n (basically because A_n contains the interval [(2a+h)k,(2a+2h)k] for every k 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, A_n is also closed under the operation x\mapsto x/2.