Division By Three (2006)

by frozenport • 12 years ago

42 21 12 years ago

frozenport• 12 years ago

"Their failure to give anything of a proof must have frustrated Sierpinski, for it appears that twenty years later he still did not know how to divide by three."

transfire• 12 years ago

Could someone give a layman's overview of this paper?

ronaldx3• 12 years ago

As best as I understand, they've proven the following:

If 3x = 3y, then x = y.

(and that's all)

They claim: "In this paper we show that it is possible to divide by three,"

and they've done this in the sense that dividing something by 3 has only one unique solution - i.e. dividing by 3 will never give you an ambiguous result.

This may seem obvious to anyone who is past kindergarten. But, the point of the paper is that they've done this from the ground up: starting with the fundamental Zermelo–Fraenkel axioms (and without using the modestly-controversial axiom of choice) https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...

mjw• 12 years ago

So the "kindergarten obvious" statement is:

"For all natural numbers x and y, if 3x = 3y, then x = y"

An equally trivial but rather more abstract way to phrase this is in the category of finite sets:

"For all finite sets x and y, whenever there's a bijection between the product x cross 3 and the product y cross 3, then there's a bijection between x and y". (Here "3" represents any set of cardinality 3, but typically chosen to be the set {0,1,2} where 0 = {}, 1 = {0}, 2 = {0,1}).

What's (apparently!) not so trivial, is when you remove the "finite" restriction from the above, and you want to show it holds for all sets, including those of various infinite cardinalities. Actually constructing the bijection seems like it would require an infinite number of arbitrary choices, which is why it's impressive they don't rely on the axiom of choice.

ronaldx3• 12 years ago

Since I made some genuine effort to answer the parent query, I would be curious to hear why I'm attracting significant downvotes?

lisper2• 12 years ago

If 3x = 3y, then x = y. (and that's all)

No, that's not quite all. They prove it 1) even if x and y are infinite and 2) without resorting to the axiom of choice. It is those two things that make it interesting.

falcor84• 12 years ago

They prove division by 3 preserves bijection between arbitrary sets without using the axiom of choice.

From the intorduction: "For any sets A and B, if there is a one-to-one correspondence between 3 × A and 3 × B then there is a one-to-one correspondence between A and B. Here 3 denotes the standard three-element set {0, 1, 2} and × denotes Cartesian product."

There are a few related links and explanations on the arxiv trackbacks page - http://arxiv.org/tb/math/0605779

anatoly2• 12 years ago

Say you have three identical bags of blue marbles (same number of blue marbles in each one), and three identical bags of red marbles (same number of red marbles in each one, but maybe not the same as blue, you don't know yet).

Now you empty all 6 bags onto a large table, and you try to pair off blue marbles with red ones, and you discover that after you're done there're no extra red or blues left. So you know that the total number of reds is the same as total number of blues.

It's then obvious to you - just because you can divide this "total number" by 3 - that _one_ bag of blue marbles you started out with has the same number as one bag of red marbles. This is completely trivial so far.

But what if you didn't understand very well what "numbers" and "division" are. Or you know what, let's say you understand it, but _I_ don't. I don't trust all these numbers, I was never good at math, when I divide the same two numbers I get a different answer every time. Spare me all that. I just want you to prove to me that one bag of blue is the same as one bag of red by _matching_ them in pairs.

I already believe you that three bags of blue are the same together as three bags of red, because we matched them off in pairs. Let's say that each marble has the number of its bag etched on it: 1,2,3, besides the color (Blue or Red). So B1 is a blue marble from the first bag, etc. Right now on the table we have all the B1,B2,B3 paired off with R1,R2,R3. If you could just take them and somehow turn it into a matching of just all B1 with all R1, that would convince me that one bag of blue is the same size as one bag of red.

Maybe when we were matching all the blues with all the reds we were lucky, and B1's just got matched with R1's by chance. But probably not! Easy to fix though, right? You just try to change the pairings a bit to make it easy to convince me. Look at some B1 marble, what's it paired with? If R1, it's already good to go. But maybe it's paired off with say R2. Then find some spare R1 and exchange the R2 with R1. But actually, there's no "spare R1", they're all in pairs already. If that R1 you found was paired with B2 or B3, then by exchanging you just made things better by making a new B1-R1 connection. But if it was paired with another B1, all you did was make a new B1-R1 connection and destroy an old one.

So it's not _completely_ trivial, but it's still pretty easy for you to convince me that there's the same number of B1's as R1's. You keep rearranging pairs, trying to create new B1-R1 pairs but not destroy old ones. If you think about it a little bit, you'll see that you're guaranteed to succeed and eventually pair off all the B1's with all the R1's, because after all you know there's the same number of each, because you _can_ divide by 3. Only I can't, and want to see this very explicit demonstration.

So far so good. Now we go to set theory, where bags of marbles may be of infinite size, and then they're called "infinite sets". Contrary to what your intuition may tell you, it turns out that infinities come in different shapes and sizes, and one infinite bag of marbles may be larger than another. What does it mean to say that it's larger though, if you can't count them? (they're infinite, if you try counting, you'll never stop). Although we can't count infinite bags of marbles, we can still "pair them off" by showing some formula or algorithm that says which marbles go in pairs with which ones. Suppose you have one bag of blue marbles, and each is marked with some odd number: 1,3,5,7... all the way to infinity. And you have a bag of red marbles, each is marked with an even number: 2,4,6,8... all the way to infinity. Then it's easy to see that even though they're infinite and you can't "count" each bag, they're the same size: you can pair 1 with 2, 3 with 4, 5 with 6... all the way to infinity, and you'll have no extra left in either bag.

Sometimes though you could have an infinite bag of blues and an infinite bag of reds, and no matter which way you try to pair them off with each other, even after all the blues found their partners, all the way to infinity, there're still reds left without a partner. If this happens, you say that the infinite bag of reds is larger than the infinite bag of blues. You can't match them in pairs, reds are always going to remain in surplus. The first person to find such different infinities was the German mathematician Cantor. About 140 years ago he proved that if blues are all the natural numbers 1,2,3... and the reds are all the real numbers (all the possible decimal fractions, including the ones where the decimal digits just never stop), then you can't pair them off - the infinity of reals is larger than the infinity of naturals.

Coming back to the marbles... if our B1,B2,B3 and R1,R2,R3 could all be infinite, what does it make of the "problem"? We can still say that the three blue bags are the same in size (because for infinite bags of marbles "same in size" just means "can be matched in pairs"), and so are the three red bags. We can still say that when we mix all the six bags together (well, with infinite bags this becomes more like a metaphor) we can match all the blues with all the reds. And it still kinda looks reasonable that if that happens, then just B1 and just R1 can also be matched in pairs.

But we can no longer prove this just trivially by dividing by 3, because we can't really count the marbles in any of the bags, they're infinite. The other method of proving this though, the one where I asked you to explicitly engineer for me a B1-R1 pairing out of the larger pairing of all the six bags... that can still work. It's much trickier to carry out with infinite sets. You can't just say - take any B1 nor paired with R1, look for another R1 not paired with B1, now exchange the reds in these two pairs, and carry on in this fashion until you're done. With infinite bags, it becomes much trickier to prove that you can do this every time, and you need some way to ensure that "carry on until you're done" actually carries you to the end of the task, instead of getting you stuck in some sub-infinity of pairings without finishing all of them. But it _can_ be done. It requires some intricate arguments and constructions, but it can be done, and this paper shows how. First, it looks at a much easier case when you only (metaphorically) "divide by two": that is, you start with B1,B2 and R1,R2, and a match in pairs of the mix of them all, and out of that mix you isolate just a B1-R1 match. Turns out that with infinite sets, it's much easier with two bags against two bags than with three against three (with normal finite bags, it's about the same). After it shows you how to do that, the paper proceeds to prove the much trickier case of three bags against three.

OK, so who needs this? (cont'd in the next comment)

anatoly2• 12 years ago

(cont'd)

OK, so who needs this? Well, this paper is beautiful on its own, but it's not particularly important to many other mathematicians. The reason is that in set theory there's something famously called an "Axiom of Choice" that basically allows you to handle infinite sets and their pairings much more easily than without it. The Axiom of Choice used to be somewhat controversial in the beginning of the 20th century. What happened during that time was that people realized they could look at set theory (and in fact at all of mathematics) much more rigorously than before by coming up with some basic axioms and showing how everything else follows from them. This is something that had been practiced in geometry ever since Euclid, but not really in other parts of mathematics, and around the beginning of the 20th century people started doing the same thing not just with points and lines, but also with numbers and sets and functions. When they tried to _formalize_ set theory - that is, take the usual stuff people have been doing with sets and figure out how to bring it all down to a handful of very obvious axioms - they discovered that all the axioms were completely obvious (as wanted!) except one, the Axiom of Choice, that sort of seems necessary to do all kinds of advanced math, but is not as obviously true as others. See, the Axiom of Choice is not _explicit_: it says something like - under certain conditions - "a matching in pairs between these two sets exists, but I'm not showing you what it is explicitly, I'm just telling you it exists". When it tells you that, it kinds looks reasonable that these two sets should be of the same "size", intuitively, so you're glad that the Axiom of Choice settles the matter by just claiming that a matching exists; but at the same time you may feel a little uneasy about the fact that the matching is not described with some formula or algorithm or anything, you're just told it exists and that's it.

Anyway, with time mathematicians pretty much accepted the Axiom of Choice as a vital part of their mathematical toolkit. Even though some very non-intuitive things can be proved using it (look up the Banach-Tarski paradox if you're interested), it's much better to have it than not. And with the Axiom of Choice, the whole problem of proving that bags of marbles B1 and R1 are of the same size becomes trivial, even when they're infinite. You don't need to carefully engineer a B1-R1 matching out of the larger one between all the six bags; the Axiom of Choice sort of gives you the firepower to just claim that this B1-R1 matching exists, and call it a day. Nearly all mathematicians are satisfied with this, because for them set theory is no more than a convenient tool to carry out their investigations into _other_ things, like numbers, geometric spaces and what not. It's only people who study _set theory itself_ (and call themselves, appropriately enough, set theorists) that are still interested in understanding just how much the Axiom of Choice is needed. These people appreciate much more than other mathematicians a proof of some fact in an _explicit_ way, not requiring the Axiom of Choice, even if it's trivial when using the Axiom. So the paper about "dividing by 3" is an example of this sort of investigation: do we really need the Axiom of Choice to prove that B1 and R1 are of the same size? Turns out we don't, and we can do this explicitly with a rather complicated, yet beautiful, construction. To mathematicians as a whole, this result is largely meaningless; to set theorists, it's a minor theorem of some interest, though even they, I think, probably would look at it more as an interesting puzzle with a beautiful solution. And that, by itself, is nothing to sneer at.

sfermigier• 12 years ago

I find it disturbing that, as stated in the first footnote, John Conway can be listed as an author of the paper, against his approval (or despite his non-approval).

What if someone gets hurt because of this paper and Mr Conway's responsibility is engaged ?

gweinberg• 12 years ago

Is there something special about 3? I would think the result would be true for any positive finite n.

gjm11• 12 years ago

The authors say (1) that division by 2 is much easier (though not trivial) and (2) that their methods generalize to enable you to divide by any other odd number (and hence, together with division by 2, to divide by any positive integer).

So what's special about 3 is that it's the smallest tricky case and that once you've done it you've effectively done everything.

Division By Three (2006)

Related Stories