In the course of looking up a link for my last blog entry, I discovered the MAA Writing Awards site, which collects many pdfs of articles that have won MAA writing awards. From browsing it a bit, it seems to be a goldmine of fun math articles.
Monthly Archives: August 2008
I’m a big fan of non-rigorous arguments, especially in calculus and analysis. I think there should be a book cataloging all the beautiful, morally-true-but-not-actually-true proofs that mathematicians have advanced, but until that time I’ll try to at least catalog a few of them on my blog.
This first one is Euler’s original argument for the equality of two expressions (both of which happen to define ):
I’ll also sketch how this can be made rigorous in non-standard analysis.
Why did the chicken cross the island on Lost?
An arithmetic statement is one made up of quantifiers “,” “,” the logical connectives “and,” “or,” “not”, function symbols , , constants , , and variables which are bound by the aforementioned quantifiers.
It is known that there is no algorithm which will decide whether or not an arithmetic statement is true or not. This shouldn’t be surprising, since if there were such an algorithm, it would be able to automatically prove Fermat’s Last Theorem, settle Goldbach’s Conjecture and the Twin Prime Conjecture, etc.
However, if we call a quasi-arithmetic statement one which uses the quantifiers “for all but finitely many ” (denoted “”) and “there exists infinitely many ” (denoted “”) instead of “” and “”, then we do have an algorithm for deciding whether a quasi-arithmetic statement is true or not!
Here’s a puzzle:
You and Bob are going to play a game which has the following steps.
- Bob thinks of some function (it’s arbitrary: it doesn’t have to be continuous or anything).
- You pick an .
- Bob reveals to you the table of values of his function on every input except the one you specified
- You guess the value of Bob’s secret function on the number that you picked in step 2.
You win if you guess right, you lose if you guess wrong. What’s the best strategy you have?
This initially seems completely hopeless: the values of on inputs have nothing to do with the value of on input , so how could you do any better then just making a wild guess?
In fact, it turns out that if you, say, choose in Step 2 with uniform probability from , the axiom of choice implies that you have a strategy such that, whatever Bob picked, you will win the game with probability 1!
In Joel David Hamkin’s paper Supertasks and Computation, he relates the following puzzle: Suppose that you have a countable infinity of dollar bills, and one day you meet the devil, who offers you the following bargain: In the first half minute from now, the devil will give you two dollar bills, and take one from you in return. In the quarter minute after that, the devil again gives you two dollar bills, and takes one from you in return. And so on, in the eighth of a minute after that, and the sixteenth of a minute after that, etc. After a minute, the whole transaction is complete. Should you take this bargain?
The answer is “no” and the reason is that the devil could do the following: Think of the bills you have at the start as being numbered 1, 3, 5, etc. and imagine that the devil has an initial pile of bills numbered 2, 4, 6, etc. Then on the nth transaction, the devil gives you the two lowest-numbered bills from his initial pile and takes bill n from you (one can easily show that you have bill n in your possession at this point). Since the devil takes bill n from you on the nth transaction, he gets all the bills in the end and you end up with nothing.
So, even though you start with infinitely many bills and each transaction produces a net gain of one bill for you, after all the transactions are done you have nothing.
In that puzzle, the devil was able to use a tricky strategy to give you more than he took at each stage and still end up with everything. In the following puzzle, which made the rounds when I was a graduate student, no matter what the devil does, he takes everything from you!
You and the devil are taking a train ride together. The train stops at each ordinal. At stop 0, you have countably infinitely many dollar bills. At each stop, the devil does the following two things (in order):
- If you have nonzero number of dollar bills, the devil takes one and destroys it.
- The devil gives you countably infinitely many dollar bills.
Prove that no matter what the devil does, when the train reaches stop (the first uncountable ordinal), you will have no money.
Suppose that is a continuous function from to and that we have a program which computes it. (Ignore for now exactly what it means to “compute” a real-valued function of the reals. Suffice it to say that almost every natural continuous function you come across is computable). If we want to compute , say to within an accuracy of , how would we do it, and would we need any further information about in order to do it?
The obvious thing to do is to compute a Riemann sum for some large . However, this could be arbitrarily far from the true value of . For example, might be 0 for all , but might curve sharply up in between each and so that its definite integral is arbitrarily close to 1.
However, since is continuous on , it is uniformly continuous. This means that for all there is a such that whenever , . If we could compute a function such for all , whenever , , then we could compute the definite integral of with arbitrary accuracy: If we want to know to within 0.001, then choose so that and we can take , since .
So, one answer to the question “What extra information do we need in order to compute ?” is: a function witnessing ‘s uniform continuity.
In 1998, Alex Simpson showed, building on ideas of Ulrich Berger and others, that another answer is: Nothing!