Archive for the ‘Somewhat philosophical’ Category

Are these the same proof?

September 18, 2010

I have no pressing reason for asking the question I’m about to ask, but it is related to an old post about when two proofs are essentially the same, and it suddenly occurred to me while I was bathing my two-year-old son.

Consider the problem of showing that the product of any k consecutive positive integers (or indeed any integers, not that that is a significant extension) is divisible by k!. I think the proof that most experienced mathematicians would give is the slick one that n(n+1)\dots(n+k-1) divided by k! is \binom {n+k-1}k, and so is the number of ways of choosing k objects from n+k-1 objects. Since the latter must be an integer, so must the former.

One might argue that this is not a complete proof because one must show that \binom{n+k-1}k really is the number of ways of choosing k objects from n+k-1, but that is not hard to do.
(more…)

Advertisements

A little experiment IV

May 8, 2010

I have another experiment that may not add all that much to the previous one, but I’m posting it anyway because I don’t want to waste the (admittedly not huge) effort it has just taken me to follow Jason Dyer’s suggestion and create a presentation using Prezi. If you follow this link, you will be taken to it. If you hover near the bottom of the box, a left arrow and a right arrow will appear, which will allow you to move right or left in an expression that, again, needs to be simplified. I’ve made it a bit easier than the last one, and you also get to see slightly more than one character at a time. There is also a button that allows you to shrink the entire expression so that it fits into the box: obviously if you use that then it counts as giving up on the experiment, but it may be interesting to do the simplification in your head according to the strict rules first and then see what happens to the information in your head when you then click the pan-out button.

Incidentally, I’m not sure that Prezi supports mathematical symbols, so I’ll save you some potential irritation by pointing out in advance that every x is an x rather than a “times”. (There’s one that looks a bit like a “times” because of the unusual spacing.)

I haven’t bothered with a poll this time. If anyone has anything interesting to report, then by all means let me know. Otherwise, think of it as a weird form of entertainment.

If you haven’t done the previous experiment (or even if you have but just want to see the same idea in a different format), you might like to look at the following two pdf files, kindly sent to me by Olivier Gerard, both of which present one chunk per page. In the first file the definition of “chunk” is the same as it was for me, so e^x would have e on one page, ^ on the next and x on the next. In the second, exponents are attached to the previous symbol, so x^2 would be on a single page, and (x+1)^2 would be on five pages of which the fifth would be )^2.

Fully separated version

Version with exponents not separated

A little experiment III

May 7, 2010

This one is a little bit different, and the associated poll questions are rather vague. I am curious to know what effect it would have on our ability to do routine manipulations if we could look at only one symbol at a time. Maybe at some point after the experiment I will say what my motivation is for this, but for now I want to influence what happens as little as possible.

After the fold, you will find a mathematical expression that can be simplified. Usually, one would look at the expression and take in chunks of it at a time, but I have embedded it in a lot of junk, so that that will not be possible. I want it to be easy to find the individual characters that make up the expression, but not easy to look at more than one at a time, so the non-junk characters are quite widely separated, but they are signalled by being enclosed in dollar signs. For example, to convey the expression e^x I would write something like

asdf$e$oijgeqwrfnoifwefhppsd$^$pofiewqt;jklnrewfppas$x$eiorfoi4

Your task, if you feel like participating in the experiment, is to simplify the expression as much as you can in your head. (If you write it down, then obviously it makes it completely pointless for me to have written it in this strange form.) I would then like to hear, in as much detail as you can remember, what thoughts went through your head, and in what order. I am particularly interested in what your eyes were doing and how they interacted with these thoughts. It may not be easy to remember all that, but if you do the best you can then I’ll be happy. (more…)

A little experiment II

May 1, 2010

A few people felt that my experiment about solving the equation x^2+2x+1=x^2 would have been more interesting if the equation had been more interesting. I’m not sure I agree with that: part of my intention was to get some evidence about what we do in a very simple situation. However, I now have another example that I want to know about, and it happens to be a harder one. Not much harder, but harder nevertheless.

One of the byproducts of its being a more interesting equation is that it will be quite a lot harder to encode all possible experiences that people might have and run a vote as I did last time. So I’ve made the vote a little bit vaguer, and I will be interested not just in the numbers but also in people’s descriptions of what they did (as I was first time round). My main aim is to get a fairly complete picture of all the ways that different mathematicians find it natural to think about the problem.

As last time, if you want to take part, then try to keep a close eye on all your thought processes: I’m interested not just in the ones that got you to the answer, but also in the ones that you might have thought about and dismissed. So try not to look at the problem until you are ready to keep track of what your reactions are. The problem will appear immediately after the fold. For the benefit of those who read this using RSS, I’ve also left a bit of space, and I’ve left space between the problem and my discussion of it. (more…)

A little experiment

April 22, 2010

For a long time, a side interest of mine has been how people think when they are doing mathematics. Two difficulties in investigating this general question are (i) that it is quite hard to examine one’s own thought processes reliably (since very often what one remembers of these processes after solving a problem is a very tidied up version of what actually happened) and (ii) that in any case I am just one mathematician with my own particular style and my own little bag of tricks.

I would therefore be grateful to anyone who was prepared to spend about 90 seconds contributing to a little experiment. What you have to do is solve a simple equation that appears just after the fold and pay close attention to your thought processes as you do so. Once you have done that, you can look at further instructions about how to record the result of your participation.

I stress once again that the whole thing should be quick and easy. But please don’t look at the equation until you are ready to start thinking about it and remembering the sequence of your thoughts, since otherwise there is a danger that the tidying-up process will take over and it will be impossible to get a reliable result. (more…)

When is proof by contradiction necessary?

March 28, 2010

It’s been a while since I have written a post in the “somewhat philosophical” category, which is where I put questions like “How can one statement be stronger than an another, equivalent, statement?” This post is about a question that I’ve intended for a long time to sort out in my mind but have found much harder than I expected. It seems to be possible to classify theorems into three types: ones where it would be ridiculous to use contradiction, ones where there are equally sensible proofs using contradiction or not using contradiction, and ones where contradiction seems forced. But what is it that puts a theorem into one of these three categories?

This is a question that arises when I am teaching somebody who comes up with a proof like this. “Suppose that the sequence (a_n) is not convergent. Then … a few lines of calculation … which implies that a_n\rightarrow a. Contradiction.” They are sometimes quite surprised when you point out that the first and last lines of this proof can be crossed out. Slightly less laughable is a proof that is more like this. “We know that |y-x|<\delta. Suppose that |\sin(y)-\sin(x)|\geq\delta. Since the derivative of \sin has absolute value at most 1 everywhere, it follows that |y-x|\geq\delta, which is a contradiction. Therefore, |\sin(x)-\sin(y)|<\delta.” There, it is clearly better to work directly from the premise that |y-x|<\delta via the lemma that |f(x)-f(y)|\leq\|f'\|_\infty |x-y| to the conclusion that |\sin(y)-\sin(x)|<\delta. However, the usual proof of the lemma does use contradiction: one assumes that the conclusion is false and applies the mean value theorem.

The result of all this is that I don’t have a good tip of the form, “If your theorem is like this then try a proof by contradiction, and otherwise don’t.” For the remainder of this post I’ll discuss another couple of examples that show some of the complications that arise. (more…)

A Tricki issue

January 20, 2009

This is a mathematical post rather than a Tricki post, but the title comes from the fact that the issue I want to discuss has arisen because I have made a statement in a Tricki article and can’t quite justify it to my satisfaction.

The article in question is about a useful piece of advice, which is that if one is having trouble proving a theorem, it can help a lot to try to prove rigorously that one’s approach cannot work. Sometimes one realizes as a result that it can work, but sometimes this exercise helps one to discover a feature of the problem that one has been wrongly overlooking. I have a few examples written up, but one of them is giving me second thoughts. (more…)

How can one equivalent statement be stronger than another?

December 28, 2008

It’s been a long time since any mathematical content was posted on this blog. This is in part because I have been diverting my mathematical efforts more to the Tricki (not to mention my own research), and indeed the existence of the Tricki means that this blog will probably become less active, though I may publish some Tricki articles here as well. But there are certain quasi-philosophical questions that I want to discuss and that are better discussed here. I have already written about one of my favourites: when are two proofs essentially the same? Another that is closely related is the question of how it can be that two mathematical statements are equivalent to each other and yet one is clearly “stronger”. This phenomenon will be familiar to all mathematicians, but here is an example that illustrates it particularly well. (The example is also familiar as a good example of the phenomenon). (more…)

What is deep mathematics?

July 25, 2008

Note added 12/9/09: It seems that many people are looking at this post, because Derren Brown claims to have used “deep mathematics” combined with “the wisdom of crowds” to predict the lottery. All I can say is that this is obvious nonsense. Whatever method you use to predict the lottery, the drawing of the balls is a random process, so you will not improve your chances of being correct. Brown has done a clever trick — I won’t speculate about his methods, as I’m not interested enough in them — but his explanation of how he did it is not to be taken seriously.

In this post I shall discuss the proofs of two statements in real analysis, one of which is clearly deeper than the other. My aim is to shed some small light on what it is that we mean when we make that judgment. A related aim is to try to demonstrate that a computer is in principle capable of “having mathematical ideas”. To do these two things I shall attempt to explain how an automatic theorem prover might go about proving the two statements in real analysis: in one case this is quite easy and in the other quite hard but by no means impossible. In the hard case what interests me is the precise ways that it is hard, which I think say something about the notion of depth in mathematics. 
(more…)

When are two proofs essentially the same?

October 4, 2007

A couple of years ago I spoke at a conference about mathematics that brought together philosophers, psychologists and mathematicians. The proceedings of the conference will appear fairly soon—I will give details when they do. My own article ended up rather too long, because I found myself considering the question of “essential equality” of proofs. Eventually, I cut that section, which was part of a more general discussion of what we mean when we attribute properties to proofs, using informal (but somehow quite precise) words and phrases like “neat”, “genuinely explanatory”, “the correct” (as opposed to merely “a correct”), and so on. It is an interesting challenge to try to be as precise as possible about these words, but I found that even the seemingly more basic question, “When are two proofs the same?” was pretty hard to answer satisfactorily. Since it is also a question on which we all have views (since we all have experience of the phenomenon), it seems ideal for a post. You may have general comments to make, but I’d also be very interested to hear of your favourite examples of different-seeming proofs that turn out, on closer examination, to be based on the same underlying idea (whatever that means). (more…)