Anatoly Vorobey (avva) wrote,
Anatoly Vorobey

деление на три (англ.)

Я написал длинный комментарий на Hacker News в ответ на просьбу объяснить языком "для чайников", в чем суть статьи Дойля и Конвея Division by Three. Вот его копия (по-английски):

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? 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 at 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 axiom sort of seemed necessary to do all kinds of advanced math, but was 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 curious), 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.
Tags: математика
  • Post a new comment


    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.