One of my favourites, which isn't on the first page there (I didn't look beyond that) but contains three surprises, is Goodstein's theorem. It has the nice extr

One of my favourites, which isn't on the first page there (I didn't look beyond that) but contains three surprises, is Goodstein's theorem. It has the nice extra feature that it can be explained pretty simply, so here goes. When you write a number down in (say) base 10, what you're really doing is writing it as a sum of [small thing] x [power of 10]. So, e.g., 1234 means 1 x 10^3 + 2 x 10^2 + 3 x 10^1 + 4 x 10^0. "Small thing" means "non-negative integer, less than the base". And of course you can do this in bases other than 10. [EDIT: previous paragraph had a stupid mistake in it; thanks, grannyg00se, for catching it!] But when you do this, the exponents may be large numbers; in particular, they may be larger than the base. So consider the following operation, given a non-negative integer and a base: write the integer as a sum of [small] x [power of base], and then do the same thing to the exponents, and to the exponents in that, etc., until you've got rid of all the numbers >= the base. OK. Now here's a process you can carry out. Take a number. Write it "strongly in base 2" according to the procedure above. Now change all the 2s to 3s, generally making the number much much bigger. Now subtract 1. Now write it "strongly in base 3" again, change all the 3s to 4s, and subtract 1. And again: 4 -> 5, subtract 1. 5 -> 6, subtract 1. If you try this on some not-too-large number, you'll notice that the base-increasing operation typically increases the number hugely, whereas of course subtracting 1 decreases it just a little bit. So here's Goodstein's theorem: start with any number you like and carry out this process; eventually the numbers will stop increasing and you'll end up at 0. (Surprise #1: what a ridiculous idea! Obviously the numbers are increasing really really fast; how can they end up at zero?) It turns out that Goodstein's theorem is actually rather easy to prove, using a bit of machinery from set theory. There's a generalization of the natural numbers called the ordinals, and doing it properly requires some theorems about them, but here's the idea. Replace all the bases with "infinity". Assume some simple rules for comparing expressions full of infinities (e.g., if a<b then (anything finite) x infinity^a < infinity^b); then every time you subtract 1 and re-express your number "strongly in base b", the corresponding thing full of infinities decreases. And of course when you replace all the bases with infinity, the "increase the base by 1" operation does nothing. And now -- and this is the bit that actually needs some set theory -- it turns out that you can't have an infinite decreasing sequence of these things-full-of-infinities (they're "well-ordered"). Which means that eventually you have to end up at zero. (Surprise #2: this is, even when the details are filled in, a startlingly short proof for such a surprising theorem.) All that stuff involving infinities is a bit weird, though. Can't we find a nice proof that works entirely in terms of ordinary finite integers? Once you formalize what "works entirely in terms of ordinary finite integers" means, it turns out that the answer is no! Goodstein's theorem is not provable from the "Peano axioms" describing the natural numbers; you need something stronger to prove it. Such as, in this case, set theory. (Surprise #3: that something so innocuous requires such powerful mathematical machinery to resolve.)