Just-do-it proofs

a repository of mathematical know-how

Just-do-it proofs

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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]

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 $ n$th 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\'ela Bollob\'as (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\'as'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]

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]

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]

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]

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 1, 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]

Is there a subset $ A\subset\mathbb{R}^2$ 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 find 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.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Just-do-it proofs

Recent articles

Active forum topics

Recent comments