5 ms·

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

ronaldx 13y 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_theory https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...
- mjw 13y 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.
  - jessaustin 13y ago
    I'm reminded of a professor who told us that we shouldn't distract ourselves with the concept of "infinity". I'm pretty sure he would have felt the same way about kindergartners.
- ronaldx 13y ago
  Since I made some genuine effort to answer the parent query, I would be curious to hear why I'm attracting significant downvotes?
  - winstonsmith 13y ago
    I don't know -- I didn't downvote you, but you might want to edit to indicate that x and y are not necessarily finite sets. (For finite sets, the result is trivial.)
    - ronaldx 13y ago
      Thanks. I think mjw's comment, and yours, now correctly cover this :)
- lisper 13y 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 13y 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 http://arxiv.org/tb/math/0605779
anatoly 13y 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)

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_theory https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_t...

mjw 13y 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.
- jessaustin 13y ago
  I'm reminded of a professor who told us that we shouldn't distract ourselves with the concept of "infinity". I'm pretty sure he would have felt the same way about kindergartners.
ronaldx 13y ago
Since I made some genuine effort to answer the parent query, I would be curious to hear why I'm attracting significant downvotes?
- winstonsmith 13y ago
  I don't know -- I didn't downvote you, but you might want to edit to indicate that x and y are not necessarily finite sets. (For finite sets, the result is trivial.)
  - ronaldx 13y ago
    Thanks. I think mjw's comment, and yours, now correctly cover this :)
lisper 13y 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 13y 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 http://arxiv.org/tb/math/0605779

anatoly 13y 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)