This post is another sample Tricks Wiki article, which revisits a theme that I treated on my web page. Imre Leader pointed out to me that I hadn’t completely done justice to the idea, and that the notion of a “just-do-it proof” had some more specific features that I had not sufficiently emphasized. His opinion matters to me since he was the one who told me about the concept. He himself got it from Béla Bollobás: I don’t know whether it goes further back than that. This is a second attempt at explaining it. Imre, if there’s anything you don’t like about this one, then please edit it when it appears on the Tricks Wiki.
Title: Just-do-it proofs.
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 not to use any tricks but just to go ahead and do it: that is, you build the set/sequence up one element at a time, and however you do so you find that it is never difficult to continue building.
Prerequisites: Basic undergraduate mathematics. Ordinals for one example.
Example 1: A subset of the plane is called dense if for every point in the plane and for every positive real number there exists a point such that the distance from to is at most . 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: . (Here, denotes the distance from to .) 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 and each . 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 of the form for some positive integer , and it is also enough to prove it just for points that have rational coordinates. (Then, if you want to find a point in that is within of a point in the plane, you first find a rational point such that , then a positive integer such that , and finally a point such that .)
The set of points within a distance of a point with rational coordinates is an open disc, so we can redescribe our problem as follows: we have a certain countable set of open discs , and we would like to find a set such that every contains at least one point of and no three points of 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 to contain a point in , so let be a point in . We need to contain a point in , so let be a point in . We need to contain a point in , so let be a point in , but this time we have to be a tiny bit careful because if (which we may as well assume), then must not be on the line that contains and . But you can’t cover all of by a line, so it’s easy to pick that avoids this line.
In general, suppose that we have chosen distinct points such that belongs to for every and no three of the lie in a line. Can we continue the process? Well, we need to belong to , to be different from all of , and not to lie on any of the lines , where by this we mean the line that contains and . But one cannot cover an open disc with just finitely many points and lines, so there is no difficulty in choosing .
(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 a short proof: since there are only finitely many lines it is possible to pick a line through the centre of that is not parallel to any of them. Then we can choose any point of as long as it isn’t one of the forbidden points or the point of intersection of with one of the . But 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 has rational coordinates
General remarks: A just-do-it proof is one that builds a sequence that satisfies a sequence of constraints , where the th constraint, , is a property of , and where for any sequence that satisfies it is not hard to prove that there exists such that the sequence satisfies . In the example above, were points in the plane and was the property that for every , the with are distinct, and no three of those lie in a line.
Example 1 is what one might think of as a completely standard just-do-it proof. If you adopt the mentality used in the above proof, then many results that at first look quite hard can in fact be proved extremely easily. In the remainder of this article, we shall give two further examples of the basic just-do-it approach, then 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 , then it is enough to construct sequences and of positive integers such that for each both and belong to and such that no is equal to any . If we can do that, then we can colour the red, the blue, and all other integers however we like, and each will contain at least one red point and at least one blue point.
But this is a very easy task. If we have chosen and such that and belong to for each and such that no is equal to any , then there is no difficulty in continuing the sequence with and , since 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 such that any two of them have symmetric difference of size at least ?
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 however you like, making sure only that when you choose the symmetric difference of and has size at least for every . When is this easy to do? Well, for a set to have symmetric difference with of size at most you have to choose a set of size at most to be the symmetric difference. The number of these is at most , and it is a straightforward exercise (consider ratios of successive binomial coefficients) to show that this is bounded above by for some constant that is strictly less than 2. Therefore, provided , 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 and 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 of real numbers and we must find a new real number 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 , 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 is 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 restnof 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 and are sequences of real numbers such that is a non-negative sequence that tends to zero, then there is exactly one real number that belongs to every closed interval . This is useful to us because it allows us to construct a sequence of some kind rather than defining all at once; it therefore opens up the possibility of a just-do-it proof.
What properties should the sequence of intervals have if we want the intersection not to equal any of the ? Well, if we ensure that for each the number does not belong to the interval then we will certainly have ensured that does not belong to the intersection of all those intervals. Therefore, we will be done if we can construct the intervals in such a way that , that for every and (less importantly) that the lengths tend to zero. But this is easy: given any closed interval and any real number one can find a closed subinterval that does not contain and has at most half the length of .
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 such that for every and for every ?
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. In a moment I will say 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 for every . How can we make the first column tend to 1, given that it must agree with the first row at ? The simplest way is to set and for every . If we continue in this way then we rapidly see that it produces the example if and if .
One sometimes sees examples such as 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 be any function from to . Prove that there is a function from such that for any two rational numbers and the limit of , as tends to infinity in , is . 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.
I should remark that in principle it is possible to use any well-ordered set to index the tasks in a just-do-it approach. This is why I describe the idea of organizing the above construction by alternating between rows and columns as “slightly deep”, since one has to realize that it is a bad idea to do all the rows first and then all the columns. The next example illustrates a just-do-it proof over a more general well-ordered set.
Example 6. Is there a subset such that for every positive real number there is exactly one pair of points in such that the distance between and is ?
The answer to this is yes, but this time the building-up process is transfinite. The set is required to satisfy one constraint for each positive real number . So we build it up an element at a time, with each new element designed to make sure that some new distance 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 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 , which we call its index. Now let us define the elements of by induction on these ordinals. Suppose that we have defined a sequence of sets , one for each ordinal less than , in such a way that (i) if then , (ii) for each the real number with index occurs as a distance in , and (iii) no distance occurs more than once in any . We now construct as follows. If the distance with index occurs in some with then we let be the union of all with . Otherwise, we take this union and add an extra point to it in order to create a distance of . To do this, we choose an arbitrary point in the union and look at the circle of radius about . We would like to pick a point in this circle to add to our set, since this would give us a distance of . 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 about in at most two points, and the number of such circles is easily checked to be less than the cardinality of , 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.
Exercise: Here is a final question that can be solved easily using the technique of Example 6. Can you prove that there is a red/blue colouring of the set of all infinite subsets of the natural numbers, with the following two properties: (i) every infinite set of natural numbers has at least one red subset and at least one blue subset, and (ii) if the symmetric difference of two sets of natural numbers is finite then they have the same colour? (The second condition is there to rule out a well-known and rather straightforward direct application of the axiom of choice to obtain a colouring where two sets have different colours whenever they have a finite symmetric difference that is of odd cardinality.)