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)