13 ms·

Choose Your Paradox – the downside of the Axiom of Choice

97 points by rutenspitz 9y ago

deleted 9y ago
[deleted]
danharaj 9y ago
Constructive/Computable insights into variants of choice: https://mathoverflow.net/questions/22990/choice-vs-countable-choice https://mathoverflow.net/questions/22990/choice-vs-countable... The way mathematics is taught it's easy to think that there's only one notion of truth and logical justification. For mathematics of finite objects that can be a very compelling story. Once you let infinity in, and you will because infinity is where all the fun's at, there are a multiplicity of concepts of truth. The axiom of choice is an incredibly powerful statement about infinite objects in a system, namely logic, which is inherently finitary[1]. Any strong statements about how infinity works is going to imply bizarre things to us finite mortals. For example, if you assume the negation of AC then you can prove that there's a collection of nonempty sets whose cartesian product is empty. Equally bizarre! AC and not AC are both independent of ZF, which makes sense because ZF is an axiom system for reasoning about monstrously infinite objects. Stronger infinities are harder and harder to say anything about. In a constructive mathematical universe (yet another notion of truth that's perfectly good), as usual, you have to be careful in how you state the axiom of choice. One formulation is a theorem and another implies law of excluded middle. The latter one ought to be considered the right importation of classical AC into constructive universes [2]. [1] There are infinitary logics but they don't magically allow you to perform infinite amounts of reasoning. All physically plausible logical reasoning is inherently a finite process. [2] https://pdfs.semanticscholar.org/68d6/790cdbfda26cf71311e13756d87f164838da.pdf https://pdfs.semanticscholar.org/68d6/790cdbfda26cf71311e137...
- posterboy 9y ago
  Besides some left leaway you basically claim there is no notion of truth ...so I can't say I believe it to be true. ;)
- monochromatic 9y ago
  Got a link about the Cartesian product theorem?
  - jfarmer 9y ago
    Write down what it means for the Cartesian product of some collection of sets to be nonemtpy. You'll see that it's exactly identical to saying there's a choice function on that collection of sets.
    - js8 9y ago
      I always wondered about the same thing as the PP. But I still have trouble understanding your explanation. Can you be a little more explicit?
      - monochromatic 9y ago
        I found this: https://math.stackexchange.com/questions/101004/the-axiom-of-choice-and-the-cartesian-product https://math.stackexchange.com/questions/101004/the-axiom-of...
      - deleted 9y ago
        [deleted]
- delhanty 9y ago
  >For example, if you assume the negation of AC then you can prove that there's a collection of nonempty sets whose cartesian product is empty. Equally bizarre! Intuitively, that's not "obviously" false to me. Similarly, when I first encountered AC it wasn't obviously true to me.
  - yaks_hairbrush 9y ago
    > Intuitively, that's not "obviously" false to me. That's fair -- intuitions are pretty personal things. It is "obviously" false to me, and Bertrand Russell fairly well articulated the reason why by calling AC the "multiplicative axiom". If you have sets A, B with 3 and 5 elements, respectively, the Cartesian product has 15 elements. So, if we have an infinite series of sets, each with at least one element, I'd expect there to be something in the infinite Cartesian project just by multiplication -- the number of elements should (and I say "should" here to clearly denote my intuition) be in some sense the product of each of the individual numbers of elements. (I avoided the word "cardinality" here explicitly because I'm talking intuitively). The idea that there's a collection of non-empty sets whose Cartesian product is empty is therefore akin to saying that you can multiply numbers bigger than zero and end up with a zero result.
DonbunEf7 9y ago
Quote: "One possibility is to treat AC as a powerful drug and take it only when necessary. Theorems should come with consumer labels saying what went into them. So if you see a box on the shelf of 'Banach and Tarski’s Miracle Duplicator! Feed Multitudes!', it will say on the back of the box 'Contains AC'." Indeed, many mathematicians are sensitive to this and try to point out when they invoke the Axiom of Choice, and there are other mathematicians who deliberately seek non-AC-powered variants of theorems in order to put them on less nebulous and more constructive ground. Personally, I view AC as another reason to consider more generalized foundations of mathematics. For example, if you know anything about topoi, it turns out that we can view set theory as a topos on a point, and any topos on a complete Boolean algebra comes pre-equipped with an inherent axiom of choice! [0] [0] https://ncatlab.org/nlab/show/axiom+of+choice https://ncatlab.org/nlab/show/axiom+of+choice
soVeryTired 9y ago
>the union of two minorities is a minority, and the intersection of two majorities is a majority Is that a typo? Shouldn't it be the other way around?
- schoen 9y ago
  I think you're right. For example, if you have U={A, B, C, D, and E}, then given minority m₁={A, B} and m₂={B, C}, m₁∩m₂={B} is also a minority. Given majority M₁={A, B, C} and majority M₂={B, C, D}, M₁∪M₂={A, B, C, D} is also a majority. This should be clear in finite sets because |m₁∩m₂|≤|m₁|, while |M₁∪M₂|≥|M₁| (you can only make sets smaller or unchanged by intersecting them with other sets, while you can only make sets larger or unchanged by taking their union with other sets).
  - taejo 9y ago
    Note that this is a definition of majority/minority, not a theorem proved about them. It's indeed true that by definition, there are no majorities for finite sets.
    - schoen 9y ago
      I didn't quite understand your reply. Did you mean to say that there are no majorities for infinite sets? Edit: It sounds elsewhere like the whole point of this may be the distinctive, counterintuitive properties of infinite sets (in this case especially under AC), but I'm continuing to be a bit confused by the presentation and context.
      - soVeryTired 9y ago
        The article has taken the word "majority" and redefined it to be something counterintuitive, and only partly related to the standard use of the word majority. A under "normal" usage, the words majority / minority have this property: > The intersection of two minorities is a minority, and the union of two majorities is a majority As the GP points out in his reply to my original comment, you can get this property from >If a vote is held and the Ayes have it, and then any number of voters switch from Nay to Aye, the Ayes still have it Now the author is redefining the terms minority and majority so they have this property: > The union of two minorities is a minority, and the intersection of two majorities is a majority But that's not possible unless you have infinite votes. As GP points out, it's clearest when you take "minority" to mean finite, and "majority" to mean "infinite, with finite opposition".
ikeboy 9y ago
>But it also implies that ZF is consistent. This sounds nice, too, but is actually a disaster. It means that we can’t prove the consistency of AD with ZF (assuming the consistency of ZF). I don't think this is strictly speaking correct. For instance, Con(ZF) itself trivially implies that ZF is consistent (which is literally what it says). But we can prove that ZF+Con(ZF) is consistent, assuming that ZF itself is consistent. (For that matter, we can prove that ZF+not(Con(ZF)) is consistent, again assuming that ZF itself is consistent. Don't ask.) So just because something implies Con(ZF) doesn't mean we can't prove that it plus ZF is consistent, assuming ZF is consistent. If ZF is allowed access to Con(ZF) it can prove a great many things that ZF alone cannot, without generating any paradoxes, as far as I know. I may be missing something, this always blows my brain.
- kirrent 9y ago
  > But we can prove that ZF+Con(ZF) is consistent Perhaps I'm naive, but doesn't that violate the incompleteness theorem? Surely you could only prove such a statement in ZF + Con(ZF) + Con(ZF + Con(ZF)) or something equivalent? In regards to what you quoted, the incompleteness theorem says that because ZF is provable in AD+ZF then AD is not provable in ZF otherwise ZF would prove its own consistency.
  - ikeboy 9y ago
    You're not proving it formally, you're proving that if ZF is consistent, then that system is consistent as well. > AD is not provable in ZF That's not what it said. It said you can't prove the consistency of AD (presumably AD+ZF). But under the same conditions (assuming Con(ZF) that doesn't rule it out and definitely not for the reason it states. Edit: a meta proof that ZF+Con(ZF) is consistent if ZF is consistent: Suppose it wasn't consistent. Then ZF+Con(ZF) proves anything. But then we can prove not(Con(ZF) from ZF as well: 1. Assume Con(ZF) 2. Prove contradiction using ZF. 3. Therefore, not(Con(ZF)), proof by contradiction. But if ZF proves that it isn't consistent, clearly it can't be consistent. But by assumption ZF is consistent. Therefore, if ZF is consistent, so is ZF+Con(ZF). I think this proof works but again, mind blowing material so I can never be 100%.
ocfnash 9y ago
There are famously-many other axioms that can be added to ZF, and which turn out to be equivalent to Choice. Of the following three equivalent extensions to ZF: * Axiom of Choice * Zorn's Lemma * Well-ordering Principle Jerry Bona quipped: "The Axiom of Choice is obviously true, the Well-ordering Principle obviously false, and who can tell about Zorn's Lemma?"

97 points by rutenspitz 9y ago

deleted 9y ago

[deleted]

Constructive/Computable insights into variants of choice: https://mathoverflow.net/questions/22990/choice-vs-countable-choice https://mathoverflow.net/questions/22990/choice-vs-countable... The way mathematics is taught it's easy to think that there's only one notion of truth and logical justification. For mathematics of finite objects that can be a very compelling story. Once you let infinity in, and you will because infinity is where all the fun's at, there are a multiplicity of concepts of truth. The axiom of choice is an incredibly powerful statement about infinite objects in a system, namely logic, which is inherently finitary[1]. Any strong statements about how infinity works is going to imply bizarre things to us finite mortals. For example, if you assume the negation of AC then you can prove that there's a collection of nonempty sets whose cartesian product is empty. Equally bizarre! AC and not AC are both independent of ZF, which makes sense because ZF is an axiom system for reasoning about monstrously infinite objects. Stronger infinities are harder and harder to say anything about. In a constructive mathematical universe (yet another notion of truth that's perfectly good), as usual, you have to be careful in how you state the axiom of choice. One formulation is a theorem and another implies law of excluded middle. The latter one ought to be considered the right importation of classical AC into constructive universes [2]. [1] There are infinitary logics but they don't magically allow you to perform infinite amounts of reasoning. All physically plausible logical reasoning is inherently a finite process. [2] https://pdfs.semanticscholar.org/68d6/790cdbfda26cf71311e13756d87f164838da.pdf https://pdfs.semanticscholar.org/68d6/790cdbfda26cf71311e137...

posterboy 9y ago
Besides some left leaway you basically claim there is no notion of truth ...so I can't say I believe it to be true. ;)
monochromatic 9y ago
Got a link about the Cartesian product theorem?
- jfarmer 9y ago
  Write down what it means for the Cartesian product of some collection of sets to be nonemtpy. You'll see that it's exactly identical to saying there's a choice function on that collection of sets.
  - js8 9y ago
    I always wondered about the same thing as the PP. But I still have trouble understanding your explanation. Can you be a little more explicit?
    - monochromatic 9y ago
      I found this: https://math.stackexchange.com/questions/101004/the-axiom-of-choice-and-the-cartesian-product https://math.stackexchange.com/questions/101004/the-axiom-of...
    - deleted 9y ago
      [deleted]
delhanty 9y ago
>For example, if you assume the negation of AC then you can prove that there's a collection of nonempty sets whose cartesian product is empty. Equally bizarre! Intuitively, that's not "obviously" false to me. Similarly, when I first encountered AC it wasn't obviously true to me.
- yaks_hairbrush 9y ago
  > Intuitively, that's not "obviously" false to me. That's fair -- intuitions are pretty personal things. It is "obviously" false to me, and Bertrand Russell fairly well articulated the reason why by calling AC the "multiplicative axiom". If you have sets A, B with 3 and 5 elements, respectively, the Cartesian product has 15 elements. So, if we have an infinite series of sets, each with at least one element, I'd expect there to be something in the infinite Cartesian project just by multiplication -- the number of elements should (and I say "should" here to clearly denote my intuition) be in some sense the product of each of the individual numbers of elements. (I avoided the word "cardinality" here explicitly because I'm talking intuitively). The idea that there's a collection of non-empty sets whose Cartesian product is empty is therefore akin to saying that you can multiply numbers bigger than zero and end up with a zero result.

DonbunEf7 9y ago

Quote: "One possibility is to treat AC as a powerful drug and take it only when necessary. Theorems should come with consumer labels saying what went into them. So if you see a box on the shelf of 'Banach and Tarski’s Miracle Duplicator! Feed Multitudes!', it will say on the back of the box 'Contains AC'." Indeed, many mathematicians are sensitive to this and try to point out when they invoke the Axiom of Choice, and there are other mathematicians who deliberately seek non-AC-powered variants of theorems in order to put them on less nebulous and more constructive ground. Personally, I view AC as another reason to consider more generalized foundations of mathematics. For example, if you know anything about topoi, it turns out that we can view set theory as a topos on a point, and any topos on a complete Boolean algebra comes pre-equipped with an inherent axiom of choice! [0] [0] https://ncatlab.org/nlab/show/axiom+of+choice https://ncatlab.org/nlab/show/axiom+of+choice

soVeryTired 9y ago

>the union of two minorities is a minority, and the intersection of two majorities is a majority Is that a typo? Shouldn't it be the other way around?

schoen 9y ago
I think you're right. For example, if you have U={A, B, C, D, and E}, then given minority m₁={A, B} and m₂={B, C}, m₁∩m₂={B} is also a minority. Given majority M₁={A, B, C} and majority M₂={B, C, D}, M₁∪M₂={A, B, C, D} is also a majority. This should be clear in finite sets because |m₁∩m₂|≤|m₁|, while |M₁∪M₂|≥|M₁| (you can only make sets smaller or unchanged by intersecting them with other sets, while you can only make sets larger or unchanged by taking their union with other sets).
- taejo 9y ago
  Note that this is a definition of majority/minority, not a theorem proved about them. It's indeed true that by definition, there are no majorities for finite sets.
  - schoen 9y ago
    I didn't quite understand your reply. Did you mean to say that there are no majorities for infinite sets? Edit: It sounds elsewhere like the whole point of this may be the distinctive, counterintuitive properties of infinite sets (in this case especially under AC), but I'm continuing to be a bit confused by the presentation and context.
    - soVeryTired 9y ago
      The article has taken the word "majority" and redefined it to be something counterintuitive, and only partly related to the standard use of the word majority. A under "normal" usage, the words majority / minority have this property: > The intersection of two minorities is a minority, and the union of two majorities is a majority As the GP points out in his reply to my original comment, you can get this property from >If a vote is held and the Ayes have it, and then any number of voters switch from Nay to Aye, the Ayes still have it Now the author is redefining the terms minority and majority so they have this property: > The union of two minorities is a minority, and the intersection of two majorities is a majority But that's not possible unless you have infinite votes. As GP points out, it's clearest when you take "minority" to mean finite, and "majority" to mean "infinite, with finite opposition".

ikeboy 9y ago

>But it also implies that ZF is consistent. This sounds nice, too, but is actually a disaster. It means that we can’t prove the consistency of AD with ZF (assuming the consistency of ZF). I don't think this is strictly speaking correct. For instance, Con(ZF) itself trivially implies that ZF is consistent (which is literally what it says). But we can prove that ZF+Con(ZF) is consistent, assuming that ZF itself is consistent. (For that matter, we can prove that ZF+not(Con(ZF)) is consistent, again assuming that ZF itself is consistent. Don't ask.) So just because something implies Con(ZF) doesn't mean we can't prove that it plus ZF is consistent, assuming ZF is consistent. If ZF is allowed access to Con(ZF) it can prove a great many things that ZF alone cannot, without generating any paradoxes, as far as I know. I may be missing something, this always blows my brain.

kirrent 9y ago
> But we can prove that ZF+Con(ZF) is consistent Perhaps I'm naive, but doesn't that violate the incompleteness theorem? Surely you could only prove such a statement in ZF + Con(ZF) + Con(ZF + Con(ZF)) or something equivalent? In regards to what you quoted, the incompleteness theorem says that because ZF is provable in AD+ZF then AD is not provable in ZF otherwise ZF would prove its own consistency.
- ikeboy 9y ago
  You're not proving it formally, you're proving that if ZF is consistent, then that system is consistent as well. > AD is not provable in ZF That's not what it said. It said you can't prove the consistency of AD (presumably AD+ZF). But under the same conditions (assuming Con(ZF) that doesn't rule it out and definitely not for the reason it states. Edit: a meta proof that ZF+Con(ZF) is consistent if ZF is consistent: Suppose it wasn't consistent. Then ZF+Con(ZF) proves anything. But then we can prove not(Con(ZF) from ZF as well: 1. Assume Con(ZF) 2. Prove contradiction using ZF. 3. Therefore, not(Con(ZF)), proof by contradiction. But if ZF proves that it isn't consistent, clearly it can't be consistent. But by assumption ZF is consistent. Therefore, if ZF is consistent, so is ZF+Con(ZF). I think this proof works but again, mind blowing material so I can never be 100%.

ocfnash 9y ago

There are famously-many other axioms that can be added to ZF, and which turn out to be equivalent to Choice. Of the following three equivalent extensions to ZF: * Axiom of Choice * Zorn's Lemma * Well-ordering Principle Jerry Bona quipped: "The Axiom of Choice is obviously true, the Well-ordering Principle obviously false, and who can tell about Zorn's Lemma?"