"Division by four"
Feb. 11th, 2018 04:32 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyTwo papers from 2015 I just learned about:
First, "Division by four". So, annoyingly they decided to write this in a pretty nonstandard/confusing manner (I guess as something of a tribute to "Division by three"?), and they leave out some details that if you don't want to figure them out yourself (I didn't manage to) are filled in by the other paper, "Pan Galactic Division" (although they seem to also omit other details later that aren't :P ) but basically:
They give a pretty simple proof, without using the axiom of choice, that (for finite n, and arbitrary cardinals A and B) nA≤nB ↠ A≤B.
(They call the paper "division by 4" as a tribute to "division by 3", even though 4 is actually easier than 3 since you can apply 2 twice...)
Right, "division by 3" just did nA = nB ↠ A=B, it didn't manage to get the stronger inequality result. (Except actually reareading it seems it does give a proof of the inequality version, but it leaves most of the details to the reader?) And this proof seems to be simpler.
One thing worth noting though is that if you feed a bijection into their proof, right if you start with nA = nB, it doesn't turn that into a bijection between A and B. If you want to prove A = B this way you have to do it by turning nA = nB into both A≤B and B≤A and then applying Schroder-Bernstein.
(The authors here make a point of pointing out that they not only don't use AC but also don't use the axiom of power set, but I'm not very clear on what the significance of that is. They also say they don't use the axiom of infinity, though it seems to me to avoid the axiom of infinity you need a slight modification of their proof (which going by what they write about this is I'm assuming what they had in mind) -- i.e. you have to treat the cases "infinite sets exist" and "infinite sets don't exist" separately; in the former case their proof works unmodified, in the latter case there isn't a problem in the first place.)
(They also present a second proof, based on "Pan Galactic Short Division" (their first proof being "Pan Galactic Long Division"), but it's not quite as simple.)
Then at the end they give some history of the problem... apparently proofs of both cancellation laws without AC were published back in 1949 by Tarski, in this paper... I guess that was mentioned back in "Division by 3" but I'd forgotten. That paper looks pretty hard to read! (Maybe it's not, I'll admit I didn't really try...) I'm assuming this proof is simpler.
Anyway I guess the thing most interesting about "Division by 4" is that if you use the first proof given, the Pan Galactic Long Division proof, and you just want to prove the inequality version rather than the equation version, the argument does not, like, at all resemble Schroder-Bernstein. Which seems to me to be pretty different from the previous proofs ("Division by 3", at least as I remember it; and it seems Tarski's also looks like that at least based on a quick glance). It converts an injection from nA to nB into an injection from A to B without doing all sorts of connect-up-the-graph-and-match-things-and-go-forwards-and-backwards stuff. So, that's pretty neat.
First, "Division by four". So, annoyingly they decided to write this in a pretty nonstandard/confusing manner (I guess as something of a tribute to "Division by three"?), and they leave out some details that if you don't want to figure them out yourself (I didn't manage to) are filled in by the other paper, "Pan Galactic Division" (although they seem to also omit other details later that aren't :P ) but basically:
They give a pretty simple proof, without using the axiom of choice, that (for finite n, and arbitrary cardinals A and B) nA≤nB ↠ A≤B.
(They call the paper "division by 4" as a tribute to "division by 3", even though 4 is actually easier than 3 since you can apply 2 twice...)
Right, "division by 3" just did nA = nB ↠ A=B, it didn't manage to get the stronger inequality result. (Except actually reareading it seems it does give a proof of the inequality version, but it leaves most of the details to the reader?) And this proof seems to be simpler.
One thing worth noting though is that if you feed a bijection into their proof, right if you start with nA = nB, it doesn't turn that into a bijection between A and B. If you want to prove A = B this way you have to do it by turning nA = nB into both A≤B and B≤A and then applying Schroder-Bernstein.
(The authors here make a point of pointing out that they not only don't use AC but also don't use the axiom of power set, but I'm not very clear on what the significance of that is. They also say they don't use the axiom of infinity, though it seems to me to avoid the axiom of infinity you need a slight modification of their proof (which going by what they write about this is I'm assuming what they had in mind) -- i.e. you have to treat the cases "infinite sets exist" and "infinite sets don't exist" separately; in the former case their proof works unmodified, in the latter case there isn't a problem in the first place.)
(They also present a second proof, based on "Pan Galactic Short Division" (their first proof being "Pan Galactic Long Division"), but it's not quite as simple.)
Then at the end they give some history of the problem... apparently proofs of both cancellation laws without AC were published back in 1949 by Tarski, in this paper... I guess that was mentioned back in "Division by 3" but I'd forgotten. That paper looks pretty hard to read! (Maybe it's not, I'll admit I didn't really try...) I'm assuming this proof is simpler.
Anyway I guess the thing most interesting about "Division by 4" is that if you use the first proof given, the Pan Galactic Long Division proof, and you just want to prove the inequality version rather than the equation version, the argument does not, like, at all resemble Schroder-Bernstein. Which seems to me to be pretty different from the previous proofs ("Division by 3", at least as I remember it; and it seems Tarski's also looks like that at least based on a quick glance). It converts an injection from nA to nB into an injection from A to B without doing all sorts of connect-up-the-graph-and-match-things-and-go-forwards-and-backwards stuff. So, that's pretty neat.
