Just-do-it proofs

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 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 rational point x such that d(x,z)<\delta/2, then a positive integer n such that 1/n<\delta/2, and finally 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 a short 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\cap D_{n+1} 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\cap D_{n+1} 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 remarks: 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.

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 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 least 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 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 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 \null [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 \null [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 \null [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 \null [u_n,v_n] in such a way that a_n\notin [u_n,v_n], that \null [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. 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 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.

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

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 X 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.)

About these ads

23 Responses to “Just-do-it proofs”

  1. Chris Eagle Says:

    In the statement of example six, do you mean R squared rather than R?

  2. Chris Eagle Says:

    You need another condition on the final exercise, otherwise I can just colour the finite sets red and the infinite sets blue.

    Many thanks for both comments — I’ve made changes accordingly.

  3. Isabel Lugo Says:

    In Example 3, you say “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.” Shouldn’t “most” be “least” here?

    Also, I realize that this isn’t the point of the post, but another possible trick might be the trick that is actually used to compute that C, namely that of bounding a sequence by a geometric series. Similarly, certain integrals can be bounded by exponentials, which is useful for the (obviously related) problem of calculating a tail bound for the normal distribution. There are certainly other examples, although I don’t have them at my fingertips.

    Thanks — correction made. And your suggestion would indeed make a suitable Tricks Wiki article. And if you don’t have as many examples as you would like, it shouldn’t stop you as we will be encouraging submission of incomplete articles, provided they are clearly marked as such with a sentence such as “This article needs a few more examples,” or “I have several examples but I do not yet have a clear general description of the method.”

  4. Terence Tao Says:

    It seems that a common theme in all of these examples is that the underlying object one is seeking to construct has a lot of freedom in it, and the constraints one are imposing on it are quite weak or somehow “decoupled” (e.g. they only exclude a measure zero or otherwise “thin” set of possibilities from the ambient or “free” space of possibilities, or the constraints can be satisfied by exercising only a portion of the freedom available [e.g. using just the lower triangular portion of an infinite matrix]).

    Hmm, this brings up a more general suggestion for the Tricks Wiki – in addition to having examples and discussion of situations in which the trick shows some promise of working, one might also want to exhibit examples or general situations in which the trick is not likely to be effective. For instance, in this case, a “just do it” approach fails horribly for the task of constructing Hadamard matrices (orthogonal square matrices with entries +1 and -1) – the constraints are just too global and too algebraic to give one the “wiggle room” one needs for this sort of approach.

  5. gowers Says:

    Terry, by coincidence, though not much of a coincidence, I started writing a page earlier today that would go some way towards following your suggestion. As you pointed out in a comment a few months ago, many tricks are concerned with proving the existence of mathematical objects with certain properties. So I started writing a kind of index page that is aimed at helping people to navigate through the Wiki if they are trying to prove a statement that begins “There exists”. What I’m trying to do is send the reader to appropriate articles (hardly any of which yet exist) given their answers to simple questions about the object they are trying to construct. One obvious question is, “What sort of object is it?” with the answer being something like a matrix, or a group, or a subset of the plane, or a topological space, etc. But another very important one is exactly the issue you’re talking about, of whether one is in a world with many constraints or few, since the kinds of methods one uses are radically different. The two questions are of course related: one wouldn’t use a just-do-it approach to construct a finite group, say.

    One remark I intend to make is that establishing existence is easy if there are few enough constraints, and sometimes also easy if there are many constraints (in the latter case because you don’t have much choice about what to do), which leaves a rather interesting class of problems that are hard because they are somehow in between the two extremes. The problem of finding a Hadamard matrix of order 4n is a good example. Another is the problem, also open, of finding a Hamilton cycle in the bipartite graph that consists of all subsets of size n or n+1 of a set of size 2n+1, with A joined to B if one is a proper subset of the other. There it is easy to get started just building a path, but after a while the constraints become overwhelming. And yet it seems that there are probably several examples, so one isn’t led to any particular construction.

    This phenomenon partly explains another trick — that of proving a stronger result than you need, in order to reduce the size of the space in which you are searching. Of course, finding a suitable strengthening isn’t easy.

  6. Define Radius Server Says:

    [...] Just-do-it proofs [...]

  7. Andrew Stacey Says:

    Example 5 is what I would call a “just write it down” trick! As I started reading it I wondered what could possibly need the sort of construction of the previous examples as one could simply write down a matrix with all the properties required. Maybe this particular example is so well ingrained into my subconscious that I don’t realise how tricky it can be first time one sees it.

    However, to make a serious point on this, there is a slight difference between Example 5 and the others: in Example 5 you construct an actual matrix with actual numbers. The others, while mildly constructive, give a procedure which, if followed, would produce the desired ‘whatever’ but no one is seriously going to follow those steps and the final answer is unguessable without doing so. Of course, this slight difference is probably too slight to mention: if one can see a solution straight away then one doesn’t need a trick but if one can’t then this is a good trick to use to get the solution. Still, bytes are cheap!

  8. gowers Says:

    Andrew, I know what you mean because I happen to be able to remember my first encounter with this question, and my experience bears out what you say since the answer came to me in a flash and not by means of some systematic derivation such as I propose here. However, I think that something just-do-it-like was probably going on in my mind. I might have been asking myself things like, “What do we need to happen?” “How can we achieve it most simply?” “What can interfere with what?” and the feeling of getting it in a flash might have resulted from the fact that after a very small number of stages one is suddenly able to see an explicit description of the final answer. But the just-do-it view of the problem does add something I think, since it gives you a recipe for constructing lots of solutions in a very easy way. (For example, you can enumerate the rows and columns however you like, and you can fill them in however you like as long as you tend to the right limits and don’t change anything you’ve previously decided on.)

    My other thought on this is that I don’t see how a computer would “just write it down” but I do see how a computer could “just do it”.

  9. Ori Says:

    An interesting topic! I was once given the problem of finding a dense set in the plane intersecting any vertical or horizontal line at a single point (at most or exactly, it doesn’t really matter; most solutions to the former lead quite immediately to a solution to the latter). I came up with the idea of rotating Q^2 by an angle whose tangent was irrational, but I now realize the question was more trivial than I had first thought.

  10. elacaraq Says:

    “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.”

    On both wikipedia and mathworld.wolfram.com the well-ordering principle is defined as “every nonempty set of positive integers contains a smallest number.” Maybe I am missing something here, how could that imply positive real numbers could be well ordered?

    Another elementary question I have is: what is the difference between a normal induction and a transfinite induction? Is that in a normal induction, we prove something holds for a chain of sets a_1, a_2,…, a_n, then show it holds for set a_{n+1}, while in transfinite induction, a_n is replaced with the union of all sets before it? Thanks.

  11. Tyler Says:

    elacaraq:

    You can well-order the reals using the well-ordering _theorem_:

    http://en.wikipedia.org/wiki/Well-ordering_theorem

    which is logically equivalent (in ZF set theory) to the axiom of choice. The ordering would have to be very different from the usual ordering of the reals, which is of course very poor (as opposed to well, hehe math humor).

    “Normal” induction is usually meant to only apply to a countable set where each element has an immediate successor, such as the natural numbers. You proceed like this: if I know phi(x), then I also know phi(x+1). But this approach fails as soon as the set has an element that is not the immediate successor of another, even if it’s well-ordered.

    Here’s a simple example of such a set: Let’s take N, the natural numbers, and add the single element B (for “Big number”) which is larger than any element of N. Clearly any nonempty subset still has a least element, so it’s still a well ordered set. But now normal induction fails sometimes — for example, let me define 1 \in N as odd, and then n+1 as (even,odd) iff n is (odd,even). Is B even or odd? I could write a normal inductive proof to show this is a good definition on N, but it fails to hold for B as well.

    The wikipedia entry on transfinite induction splits induction into two types: successor case (as with the natural numbers, the normal way); or the limit case, of which B is an example. But you can also elegantly state transfinite induction as a single case, which planetmath gives:

    http://planetmath.org/encyclopedia/TransfiniteInduction.html

  12. elacaraq Says:

    In the last sentence in above message, I meant a_{n+1} is replaced with the union of all sets before it. Sorry to make the correction here. I wish we could edit our own comments.
    On another note: if the questions are two elementary, please delete them.

  13. Tyler Says:

    I’ve informally written up an abstract framework to capture the unifying concept here:

    http://thetangentspace.com/wiki/index.php?title=Pigeonhole_constructions

    along with a few other examples:
    * a dense set in the plane with no two similar triangles
    * an infinite matrix with no singular subsquares
    * a graph exists for any countably infinite choice of positive degrees

  14. Jose Brox Says:

    Hi Tim!

    I thought we could use some words from Polya in the Introduction Page to the Tricki. I looked at the preface of “How to Solve It” and the paragraph I liked the most for us was this one:

    <>

    – George Polya, How To Solve It: A new aspect of mathematical method. 1944 –

    If you like the idea, I plan to look also into his ‘more serious’ volumes “Mathematics and Plausible Reasoning” (vol1 “Induction and Analogy in Mathematics” and vol2 “Patterns of Plausible Inference”). In any case, I suspect that they can be a source for the Tricki to much greater extent than just quoting…

    Btw, another “concept” (using the term I suggested in the hierarchy I sketched by email) would be the one of “reverse engineering”: If you know what you want your solution to look like, then try to arrive from it to your hypotheses (or to _some acceptable_ hypotheses as well) by a chain of double implications. If any extra assumption was made in the process, just add it to the hyphoteses.

  15. Jose Brox Says:

    (I’m sorry, the paragraph pasted in the window but I think the webpage restrict the use of “<”. Here it goes again)

    ———————
    Studying the methods of solving problems, we perceive
    another face of mathematics. Yes, mathematics has two
    faces; it is the rigorous science of Euclid but it is also
    something else. Mathematics presented in the Euclidean
    way appears as a systematic, deductive science; but
    mathematics in the making appears as an experimental,
    inductive science. Both aspects axe as old as the science of
    mathematics itself. But the second aspect is new in one
    respect; mathematics “in statu nascendi,” in the process
    of being invented, has never before been presented in
    quite this manner to the student, or to the teacher
    himself, or to the general public.
    ——— Polya —————

    Regards!

  16. Anonymous Says:

    Great post!

    There is a typo in example 5:
    “How can we make the first column tend to 0, given that it must agree with the first row at a_{11}?”
    It should say “first column tend to 1.”

    [Thanks very much for pointing that out -- I've corrected it now.]

  17. The forthcoming launch of the Tricki « Gowers’s Weblog Says:

    [...] searches and tags. But even these may leave some articles a bit hard to find. For example, consider my sample article on just-do-it proofs. If you are unfamiliar with the just-do-it technique and have a problem that you find difficult but [...]

  18. Mark Dominus Says:

    There’s an extensive discussion of this technique, in the context of transfinite induction, in Cieselski’s book “Set Theory for the Working Mathematician”. Among the (many) examples are proofs that, R^3 is a union of disjoint circles, but R^2 is not, and that there is a subset of the plane which is intersected in exactly one point by every horizontal line but whose intersection with every vertical line is a dense subset of R.

  19. Jaime Montuerto Says:

    Dear Prof Gowers,

    I have a question that I have been working on for a long time and somehow relates to a lot of articles I’ve read in your blog about Fermat’s little theorem.

    Here’s the question,

    Do all primes divides a Mersenne number? A Mersenne prime divides itself.

    As a counterpoint 7, a Mersenne number itself does not divide any Fermat number, it seems so.

    Thanks!

  20. Dave Futer Says:

    I could be missing something, but it seems that Example 5 is susceptible to a very simple — and not at all deep — “just do it” attack. That is, one can write down the matrix explicitly.

    Take a single, bi-infinite sequence $s_k$ with the property that the sequence approaches 1 as $k \to \infty$, and approaches 0 as $k \to -\infty$. For example, you can let $s_k = 2^k$ for negative $k$, and $s_k = 1 – 2^{-k}$ for positive $k$. Alternately, one can rig something up by rescaling the arctangent function.

    Now, to get the desired matrix, let $a_{mn} = s_{m-n}$. As $m$ goes to infinity, the terms tend to 1, and as $n$ goes to infinity, the terms tend to 0. This solution has the added advantage of a lot of symmetry.

    Or is this explicit way of “just doing it” not a good illustration of the inductive-construction philosophy?

  21. gowers Says:

    Dave, That’s a simple argument, but in a way that’s a prototype of the non-just-do-it approach (in the technical sense of “just do it” that I’m discussing here). Embedded in what you say is the idea (simple, but an idea nevertheless) of making your matrix depend on m-n only. I claim that the just-do-it approach avoids the need for any idea whatsoever. I won’t try to be precise about what I mean by that …

  22. Wikipedia References Says:

    Wikipedia References…

    [...]Just-do-it proofs « Gowers's Weblog[...]…

  23. Don’t do it! | Complex Projective 4-Space Says:

    [...] Sir Timothy Gowers FRS wrote about the usefulness of a particular proof strategy, known as ‘just do it’. He gives [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,420 other followers

%d bloggers like this: