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$ .