Wednesday, June 21, 2006

How to Divide by Three

I just came across this paper by Peter Doyle and John Conway (though it seems that Conway disowns it!).

Ostensibly it proves something simple: that if there a bijection from A×3 to B×3 (where 3 = {0,1,2}), then there is a bijection from A to B. The catch is that the authors choose not to use the axiom of choice and so must explicitly describe the bijection. It turns out this is a hard problem. Lindenbaum claimed a proof in 1926 but it was 'lost'. Tarski published a proof in 1949 but Conway and Doyle think their proof is probably a rediscovery of Lindenbaum's original.

It's very curious. A priori I'd never have guessed this was a tricky problem.

It seems that the ubiquitous John Baez mentioned this a hundred 'weeks' ago here. Does that man have to have already written on everything that interests me in mathematics!? :-)

3 comments:

Kenny said...

I seem to recall reading on the Foundations of Mathematics e-mail list that this is possible for three but not for two, or something equally crazy. (Of course, it's trivial as long as at least one of A and B is known to be finite.)

sigfpe said...

Actually, it's true for any finite set, not just 3. But 2 is easier and the method needs to be varied a bit for larger finite sets.

David R. MacIver said...

That paper does go on a bit, doesn't it? I'm vaguely interested in the result, but I really can't be bothered to dig through the waffle to hunt down the actual bits where they prove things... :)

Blog Archive