|
|
|
|
|
|
|
|
|
|
Following is an excerpt from Textbooks of mathematical logic say that a proof is a sequence of statements, each of which either follows from previous statements in the sequence or from agreed axioms unproved but explicitly stated assumptions that in effect define the area of mathematics being studied. This is about as informative as describing a novel as a sequence of sentences, each of which either sets up an agreed context or follows credibly from previous sentences. Both definitions miss the essential point: that both a proof and a novel must tell an interesting story. They do capture a secondary point, that the story must be convincing, and they also describe the overall format to be used, but a good story line is the most important feature of all. Very few textbooks say that. Most of us are irritated by a movie riddled with holes, however polished its technical production may be. I saw one recently in which an airport is taken over by guerrillas who shut down the electronic equipment used by the control tower and substitute their own. The airport authorities and the hero then spend half an hour or more of movie time-several hours of story time-agonizing about their inability to communicate with approaching aircraft, which are stacking up in the sky overhead and running out of fuel. It occurs to no one that there is a second, fully functioning airport no more than thirty miles away, nor do they think to telephone the nearest Air Force base. The story was brilliantly and expensively filmed-and silly. That didn't stop a lot of people from enjoying it: their critical standards must have been lower than mine. But we all have limits to what we are prepared to accept as credible. If in an otherwise realistic film a child saved the day by picking up a house and carrying it away, most of us would lose interest. Similarly, a mathematical proof is a story about mathematics that works. It does not have to dot every i and cross every t; readers are expected to fill in routine steps for themselves just as movie characters may suddenly appear in new surroundings without it being necessary to show how they got there. But the story must not have gaps, and it certainly must not have an unbelievable plot line. The rules are stringent: in mathematics, a single flaw is fatal. Moreover, a subtle flaw can be just as fatal as an obvious one. Let's take a look at an example. I have chosen a simple one, to avoid technical background; in consequence, the proof tells a simple and not very significant story. I stole it from a colleague, who calls it the SHIP/DOCK Theorem. You probably know the type of puzzle in which you are given one word (SHIP) and asked to turn it into another word (DOCK) by changing one letter at a time and getting a valid word at every stage. You might like to try to solve this one before reading on: if you do, you will probably understand the theorem, and its proof, more easily. Here's one solution:
There are plenty of alternatives, and some involve fewer words. But if you play around with this problem, you will eventually notice that all solutions have one thing in common: at least one of the intermediate words must contain two vowels. O.K., so prove it. I'm not willing to accept experimental evidence. I don't care if you have a hundred solutions and every single one of them includes a word with two vowels. You won't be happy with such evidence, either, because you will have a sneaky feeling that you may just have missed some really clever sequence that doesn't include such a word. On the other hand, you will probably also have a distinct feeling that somehow "it's obvious." I agree; but why is it obvious? You have now entered a phase of existence in which most mathematicians spend most of their time: frustration. You know what you want to prove, you believe it, but you don't see a convincing story line for a proof. What this means is that you are lacking some key idea that will blow the whole problem wide open. In a moment I'll give you a hint. Think about it for a few minutes, and you will probably experience a much more satisfying phase of the mathematician's existence: illumination. Here's the hint. Every valid word in English must contain a vowel. It's a very simple hint. First, convince yourself that it's true. (A dictionary search is acceptable, provided it's a big dictionary.) Then consider its implications....
O.K., either you got it or you've given up. Whichever of these you did, all professional mathematicians have done the same on a lot of their problems. Here's the trick. You have to concentrate on what happens to the vowels. Vowels are the peaks in the SHIP/DOCK landscape, the landmarks between which the paths of proof wind. In the initial word SHIP there is only one vowel, in the third position. In the final word DOCK there is also only one vowel, but in the second position. How does the vowel change position? There are three possibilities. It may hop from one location to the other; it may disappear altogether and reappear later on; or an extra vowel or vowels may be created and subsequently eliminated. The third possibility leads pretty directly to the theorem. Since only one letter at a time changes, at some stage the word must change from having one vowel to having two. It can't leap from having one vowel to having three, for example. But what about the other possibilities? The hint that I mentioned earlier tells us that the single vowel in SHIP cannot disappear altogether. That leaves only the first possibility: that there is always one vowel, but it hops from position 3 to position 2. However, that can't be done by changing only one letter! You have to move, in one step, from a vowel at position 3 and a consonant at position 2 to a consonant at position 3 and a vowel at position 2. That implies that two letters must change, which is illegal. Q.E.D., as Euclid used to say. The proof having its shortcomings, in the course of time it led to an illuminating discussion which resulted in an attempt to place it into a formal framework. As if it might help! Following are a few original Lewis Carroll's puzzles. See if you can find other applications of the above deduction. Should you discover a new statement I would be happy to hear from you. Solutions to most of the puzzles have been kindly provided by Judd A. Schorr.
A few word ladders have been suggested by visitors to the site: By James Mathews: By Priest:
By yours truly:
Copyright © 1996-2008 Alexander Bogomolny
FISH GOAT CROSS JUMP MUNCH SWIM GIRL GOD LIKE MOM FALL sty five bread ink nose smile dry soup no solution lid no solution coins pie rich miser rye (no solution) (no solution) ape abel bread hot hair beast oak navy shelf fish bravo (no solution) (no solution) mine (no solution) two pink white bird crust (Lewis Carroll supplied no solution to this puzzle. The one below was sent to me by Brice on August 6, 2007.) kettle
Copyright © 1996-2008 Alexander Bogomolny |
| 28677924 |  |
|