Tricki
a repository of mathematical know-how

Revision of Just-do-it proofs from Thu, 26/03/2009 - 14:44

Quick description

If you are asked to prove that a sequence or a set exists with certain properties, then the best way of doing so may well be just to go ahead and do it: that is, you build the set/sequence up one element at a time, and however you do it you find that it is never difficult to continue building.

Prerequisites

Basic undergraduate mathematics. Transfinite induction for one of the examples.

Example 1

A subset A of the plane is called dense if for every point  x in the plane and for every positive real number  \delta there exists a point  a\in A such that the distance from  x to  a is at most  \delta. Does there exist a dense subset of the plane that contains no three points in a line?

This is an example of a question that is quite hard (though not impossible) if you go about it the wrong way, and almost trivial if you are used to just-do-it proofs. The hard way of solving it is to try to think of a clever definition of a set that works. One might, for instance, start with a very obvious dense set, such as the set of all points with rational coordinates, and use a continuous map to distort it in such a way that no three points lie in a line. But such an approach will need some ingenuity: the continuous map would need to be nice enough for it to be possible to prove that no three rational points had images in a line, which would be a question in number theory; but it couldn't be too nice or there would be three images in a line.

If you are interested in keeping life simple, then the mistake in such an approach is to try to define the whole set at once. What if instead you build it up element by element?

In order to do this, you need to be clear about the conditions that the set must eventually satisfy. These can be written as follows:  \forall x\ \forall \delta>0\ \exists a\in A\ d(x,a)<\delta. (Here,  d(x,a) denotes the distance from  x to  a.) At first it looks challenging to create a set that satisfies all these conditions because there are uncountably many of them, one for each point  x and each  \delta>0. However this appearance is illusory (as it often is), because we can replace this uncountable set of conditions by a countable one: it is enough to prove it for every  \delta of the form  1/n for some positive integer  n, and it is also enough to prove it just for points  x that have rational coordinates. (Then, if you want to find a point in  A that is within  \delta of a point  z in the plane, you first find a point  x in the plane that has rational coordinates such that  d(x,z)<\delta/2, then a positive integer  n such that  1/n<\delta/2 and finally you find a point  a\in A such that  d(x,a)<1/n.)

The set of points within a distance  1/n of a point  x with rational coordinates is an open disc, so we can redescribe our problem as follows: we have a certain countable set of open discs  D_1,D_2,D_3,\dots, and we would like to find a set  A such that every  D_n contains at least one point of  A and no three points of  A lie in a line.

Once reformulated in this very minor way, the problem is perfectly set up for a just-do-it approach. We need  D_1 to contain a point in  A, so let  a_1 be a point in  D_1. We need  D_2 to contain a point in  A, so let  a_2 be a point in  D_2. We need  D_3 to contain a point in  A, so let  a_3 be a point in  D_3, but this time we have to be a tiny bit careful because if  a_1\ne a_2 (which we may as well assume), then  a_3 must not be on the line that contains  a_1 and  a_2. But you can't cover all of  D_3 by a line, so it's easy to pick  a_3 that avoids this line.

In general, suppose that we have chosen distinct points  a_1,a_2,\dots,a_n such that  a_i belongs to  D_i for every  i and no three of the  a_i lie in a line. Can we continue the process? Well, we need  a_{n+1} to belong to  D_{n+1}, to be different from all of  a_1,a_2,\dots,a_n, and not to lie on any of the  \binom n2 lines  L_{ij}, where by this we mean the line that contains  a_i and  a_j. But one cannot cover an open disc with just finitely many points and lines, so there is no difficulty in choosing  a_{n+1}.

(It's pretty obvious that you can't cover an open disc with finitely many points and lines, but it is not quite trivial, so here's an easy proof: since there are only finitely many lines  L_{ij} it is possible to pick a line  L through the centre of  D_{n+1} that is not parallel to any of them. Then we can choose any point of  L as long as it isn't one of the forbidden points or the point of intersection of  L with one of the  L_{ij}. But  L is infinite and this rules out only finitely many points.)

It is not hard to modify the above proof to add the condition that every point in  A has rational coordinates.

General discussion

A just-do-it proof is one that builds a sequence  a_1,a_2,\dots that satisfies a sequence of constraints P_1,P_2,\dots, where the  nth constraint,  P_n, is a property of  a_1,\dots,a_n, and where for any sequence  a_1,\dots,a_n that satisfies  P_n it is not hard to prove that there exists  a_{n+1} such that the sequence  a_1,\dots,a_{n+1} satisfies  P_{n+1}. In the example above,  a_1,a_2,\dots were points in the plane and  P_n was the property that  a_i\in D_i for every  i\leq n, the  a_i with  i\leq n are distinct, and no three of those  a_i lie in a line. The notion of a just-do-it proof was crystallized by Béla Bollobás (though it is a sufficiently natural idea that many others will undoubtedly have thought of it for themselves) and reached this author via one of Bollobás's supervisees.

Example 1 is what one might think of as a completely standard just-do-it proof, and there are many results that can be proved easily if one adopts this mentality. In the remainder of this article, we shall give two further examples of the basic just-do-it approach, followed by two examples of problems that are not immediately obviously of the just-do-it type, but which can be converted into ones that are, and finally an example where the building-up process continues transfinitely.

Example 2

Is it possible to colour the positive integers with two colours, red and blue, in such a way that no infinite arithmetic progression is coloured entirely red or entirely blue?

Once again, a very small amount of reformulation is needed to bring out the just-do-it nature of this problem. First, one notes that there are only countably many infinite arithmetic progressions. If we enumerate these as  A_1,A_2,A_3,\dots, then it is enough to construct sequences  r_1,r_2,r_3,\dots and  b_1,b_2,b_3,\dots of positive integers such that for each  i both  r_i and  b_i belong to  A_i and such that no  r_i is equal to any  b_j. If we can do that, then we can colour the  r_i red, the  b_i blue, and all other integers however we like, and each  A_i will contain at least one red point and at least one blue point.

But this is a very easy task. If we have chosen  r_1,\dots,r_n and  b_1,\dots,b_n such that  r_i and  b_i belong to  A_i for each  i\leq n and such that no  r_i is equal to any  b_j, then there is no difficulty in continuing the sequence with  r_{n+1} and  b_{n+1}, since  A_{n+1} is infinite and there are only finitely many numbers that have already been used.

In this case it is quite easy to define a colouring that works, but the just-do-it approach brings out the true nature of the problem: that it is trivial.

Example 3

Is it possible to find exponentially many subsets of  \{1,2,\dots,N\} such that any two of them have symmetric difference of size at least  N/3?

There are clever methods in coding theory for defining such a collection of sets, but these methods were serious mathematical results. Actually, so was the observation that a just-do-it approach would work, but from today's perspective is more or less obvious. All you do is choose a sequence of sets  A_1,A_2,\dots however you like, making sure only that when you choose  A_n the symmetric difference of  A_i and  A_n has size at most  N/3 for every  i<n. When is this easy to do? Well, for a set to have symmetric difference with  A_i of size at most  N/3 you have to choose a set of size at most  N/3 to be the symmetric difference. The number of these is at most  \sum_{k=0}^{N/3}\binom Nk, and it is a straightforward exercise (consider ratios of successive binomial coefficients) to show that this is bounded above by  C^N for some constant  C that is strictly less than 2. Therefore, provided  nC^N<2^N, we can continue the sequence. From this it follows that we can choose exponentially many such sets.

Example 4

Are all real numbers algebraic? That is, is every real number a root of some polynomial with integer coefficients? The answer is of course no, and as is very well known there are two contrasting approaches. One is that of Liouville, which was to prove that no algebraic number can be too well approximated by rationals and then to construct a real (and irrational) number that could be very well approximated by rationals. In a similar spirit, Hermite and Lindemann showed that  e and  \pi are transcendental. The other approach is that of Cantor, who noted that the algebraic numbers form a countable set, while the real numbers are uncountable.

It is often stated (even by me on occasion) that Cantor's proof is an abstract existence proof. But a better way of regarding it is as a just-do-it proof, as I shall explain.

Let us take it as read that the algebraic numbers are countable. What then is our task? We have a list  a_1,a_2,\dots of real numbers and we must find a new real number  r that is not equal to any number on our list. This does not look like a just-do-it proof because we are trying to find a single object, the real number r, rather than a sequence. But if you are acquainted with elementary real analysis then you will know that the single-object quality of a real number is somewhat illusory, and that real numbers are intimately tied up with sequences. (An elementary illustration of this is the fact that real numbers can be given by infinite decimal expansions and usually not by finite ones. The rest of the discussion could take place in terms of decimal expansions but I prefer the approach I shall take, which is based on Cantor's first proof that the reals are uncountable.)

One way of specifying a real number is as the unique point that belongs to a nested intersection of closed intervals with widths that tend to zero. That is, one uses the lemma (which is equivalent to the completeness property of the reals) that if u_1\leq u_2\leq\dots and v_1\geq v_2\geq\dots are sequences of real numbers such that v_n-u_n is a non-negative sequence that tends to zero, then there is exactly one real number that belongs to every closed interval [u_n,v_n]. This is useful to us because it allows us to construct a sequence of some kind rather than defining r all at once; it therefore opens up the possibility of a just-do-it proof.

What properties should the sequence of intervals [u_n,v_n] have if we want the intersection not to equal any of the a_n? Well, if we ensure that for each n the number a_n does not belong to the interval [u_n,v_n] then we will certainly have ensured that a_n does not belong to the intersection of all those intervals. Therefore, we will be done if we can construct the intervals [u_n,v_n] in such a way that a_n\notin [u_n,v_n], that [u_{n+1},v_{n+1}]\subset [u_n,v_n] for every n and (less importantly) that the lengths v_n-u_n tend to zero. But this is easy: given any closed interval I and any real number a one can find a closed subinterval J\subset I that does not contain a and has at most half the length of I.

The above proof is inexplicit in the sense that it does not directly specify a transcendental number. However, with a little trouble it can be converted into an algorithm for generating the sequence of intervals, so in that sense it is a constructive proof. (One would have to modify it slightly so that for each polynomial one found good approximations to its roots and then avoided any numbers that were within the margin of error.) But what the proof does not give is a formula for the intersection of the intervals that result.

Example 5

Is there an infinite matrix  (a_{mn}) such that  \lim_n a_{mn}=0 for every  m and  \lim_m a_{mn}=1 for every  n?

We have already seen that problems may need to be reformulated in order to become amenable to the basic just-do-it technique. Up to now the reformulation has been very mild. This example is here to show that sometimes it can be slightly deeper. I will say later more precisely what I mean by this comment.

Let us begin with the observation that we have a countable set of conditions that our matrix must satisfy: its rows must tend to 0 and its columns must tend to 1. The main constraint we face is that if a row and a column intersect then they must take the same value at the point of intersection. There is thus the potential for a just-do-it proof, but in order to make it fit the general description of such proofs we need to choose what order to do the tasks in. This is where the very slight depth arises: effectively we need to prove that the union of the set of all rows and the set of all columns is countable. The simplest way of listing them is to take the first row, then the first column, then the second row, then the second column, and so on.

If we do this then the problem becomes as easy as the other examples above. How can we make the first row tend to 0? The simplest way is to set  a_{1n}=0 for every  n. How can we make the first column tend to 0, given that it must agree with the first row at  a_{11}? The simplest way is to set  a_{11}=0 and  a_{m1}=1 for every  m>1. If we continue in this way then we rapidly see that it produces the example  a_{mn}=0 if  m\leq n and  a_{mn}=1 if  m>n.

One sometimes sees examples such as  a_{m,n}=m/(m+n) given as solutions to this problem. While they too work, they obscure the fact that once again the problem is trivial (in the sense that no serious constraints arise when one tries to build an example).

Here is an exercise. Let  g be any function from  \mathbb{Q}\times\mathbb{Q} to  \mathbb{R}. Prove that there is a function  f from  \mathbb{Q}\times\mathbb{Q} such that for any two rational numbers  \lambda and  \mu the limit of  f(x,\lambda x+\mu), as  x tends to infinity in  \mathbb{Q}, is  g(\lambda,\mu). This problem would be pretty hard to solve with an explicit formula but it is just as easy as all the others if one uses a just-do-it approach.

Example 6

Is there a subset  A\subset\mathbb{R} such that for every positive real number  r there is exactly one pair of points  x,y in  A such that the distance between  x and  y is  r?

The answer to this is yes, but this time the building-up process is transfinite. The set  A is required to satisfy one constraint for each positive real number  r. So we build it up an element at a time, with each new element designed to make sure that some new distance  r occurs. Of course, as we do so, we must be careful that no distance occurs twice.

To make this approach work we must appeal to the well-ordering principle, which tells us that we can ind a well-ordering of the positive real numbers. Moreover, we can do so in such a way that the number of predecessors of each  r in the well-ordering is strictly less than the number of reals. (If the continuum hypothesis is true then the number of predecessors will therefore be countable, but that is not necessary.)

If the positive reals are well-ordered, then we can associate with each one an ordinal  \alpha, which we call its index. Now let us define the elements of  A by induction on these ordinals. Suppose that we have defined a sequence of sets  A_\beta, one for each ordinal less than  \alpha, in such a way that (i) if  \beta<\gamma then  A_\beta\subset A_\gamma, (ii) for each  \beta<\alpha the real number with index  \beta occurs as a distance in  A_\beta, and (iii) no distance occurs more than once in any  A_\beta. We now construct  A_\alpha as follows. If the distance  r with index  \alpha occurs in some  A_\beta with  \beta<\gamma then we let  A_\alpha be the union of all  A_\beta with  \beta<\alpha. Otherwise, we take this union and add an extra point to it in order to create a distance of  r. To do this, we choose an arbitrary point  P in the union and look at the circle of radius  r about  P. We would like to pick a point in this circle to add to our set, since this would give us a distance of  r. However, we must not add a point that causes any of the existing distances to be duplicated. Geometrically speaking, our new point must not lie on any circle about any existing point if the radius of that circle is equal to a distance we already have in the set. But each such circle intersects the circle of radius  r about  P in at most two points, and the number of such circles is easily checked to be less than the cardinality of  \mathbb{R}, which is the cardinality of any circle, so we can find a new point to continue our sequence. Continuing in this way we create the desired set.

Comments

I'm unsure of whether this

I'm unsure of whether this belongs in the article proper, or in a separate article, or just restricted to the comments, but of course one can also use a just-do-it method to construct a set with undesirable properties, as in a proof by contradiction. (The example I'm thinking of right now is in the usual proof of Hilbert's basis theorem, but the general trick is a common one – it's essentially used in Euclid's proof of infinitely many primes.) So the question is, where does this variation on the trick go in the Tricki?

In Example 2,'.....such that

In Example 2,'.....such that no r_i is equal to any b_j.' Do you mean to say '.... such that no r_i is equal to any b_i.'?

No, I need all the to differ

No, I need all the r_i to differ from all the b_i, so that we are free to colour the r_i red and the b_i blue. I called them b_j to emphasize this.

covering a disc

"It's pretty obvious that you can't cover an open disc with finitely many points and lines, but it is not quite trivial, so here's an easy proof: ..."

A simpler proof: it is impossible to cover even a circle with finitely many lines, since a line can intersect a circle at at most 2 points!