3 ms·
Constructive/Computable insights into variants of choice: https://mathoverflow.net/questions/22990/choice-vs-countable-choice https://mathoverflow.net/question
by 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 agoBesides 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 agoGot a link about the Cartesian product theorem?
- jfarmer 9y agoWrite 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 agoI 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 agoI 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.