11 ms·

Mathematical Existence and the Axiom of Choice

83 points by herodotus 4y ago

mr_gibbins 4y ago
I like Bill Wadge's stuff and this is a great explanation of the axiom of choice. I spent a fair bit of time on ZF set theory + AC working in databases, and AC is essential for data-driven set-theory to function. Bit confused about the unit sphere explanation but then again I'm unfamiliar with the underlying paper.
- algon33 4y ago
  By database do you mean a finite 2d array with column headings? Or something that can be represented by such an object? And its entries are elements of some countable sets? If so, what are you doing using ZFC there?
  - mr_gibbins 4y ago
    Thanks - see comment above.
- zomglings 4y ago
  I'm confused why you would need the Axiom of Choice when working with computable programs. Unless you were proving theorems about possible contents of a database? But even that seems like you wouldn't need the Axiom of Choice. Could you elaborate on what you were doing with ZFC with databases?
  - mr_gibbins 4y ago
    Not to cop out but a HN reply isn't the best place to provide a full explanation. Suffice to say I use the ZF axioms as a basis to teach how sets both differ from and are similar to tables, particularly using the more accessible parts of Stoll's textbook on axiomatic set theory. To give a single example, the axiom schema of replacement is a good analogy for how the output of a SELECT command over a set will also result in a set. In terms of AC, the comment below about how this is actually the AFC is correct, since the sets I am talking about are finite. Of course, set projections or selections are arguably choice functions themselves, which makes them relevant, and ZFC includes AC in order to infer well-orderedness, which tables (after all, collections of sets) can indeed be.
- lupire 4y ago
  That's the Axiom of Finite Choice, not the full Axiom of Choice. https://en.m.wikipedia.org/wiki/Axiom_of_finite_choice https://en.m.wikipedia.org/wiki/Axiom_of_finite_choice
  - mr_gibbins 4y ago
    Yes - you are correct :)
sylware 4y ago
I have always had mixed feelings about this axiom. It feels "2nd level", like it should build upon simpler axioms related to the mathematical object "set" and the mathematical object "function".
- lupire 4y ago
  What do you mean? The Axiom of Choice is a statement about a function on sets. In context, of ZF, it's equivalent to the Well Ordering Principle/Axiom and Zorn's Lemma/Axiom.
- Koshkin 4y ago
  Then it wouldn’t be an axiom, which it, in fact, is, being logically independent from the rest. It is considered somewhat special though, and mathematicians, being nice people, usually indicate whether they rely on it in a proof.
  - sylware 4y ago
    Yep, this is what I meant by "2nd level": it feels like it is not an axiom but a theorem.
less_less 4y ago
My favorite application of choice, known as ultrafilters: You know those "mathematicians wearing hats" games, where the solution is a Hamming code or some kind of modular arithmetic thing? Here's one where there's no winning strategy. You have N mathematicians wearing hats whose colors are chosen uniformly and independently at random from a set C. They can see each others' hats but not their own. Simultaneously and without communication, each mathematician must guess their own hat color. Everyone who guesses right wins, and everyone who guesses wrong loses. A strategy maps (other mathematicians -> hat color) -> guess of your hat color, or if you're guessing randomly, then a distribution of guesses. No matter what strategy is chosen, N/|C| players win in expectation. There's no trick to improve this, though you can change the distribution of how many players win. For example, you can guarantee that at least floor(N/|C|) of them win. This is neat in that it works even in a derandomized setting, where the strategy must be deterministic and the hats are assigned maliciously by an opponent who knows the strategy. (This setting is easier to work with for infinite C, because you don't need to worry about probability distributions on infinite objects.) But if |C| > N, then you can't guarantee that anyone wins. OK, but what if there are infinitely many mathematicians, and you have the axiom of choice? In that case, there exists a strategy which guarantees that all but finitely many players will win — that is, the overwhelming majority of them will win. This works no matter how big C is, even if C is infinite, even if it's vastly larger than the set of players (eg if it's uncountable but the players are countable). Why? Well, consider the relation that two hat assignments are "almost the same" iff they differ in only finitely many places. This is an equivalence relation, so we can divide the space of hat assignments into equivalence classes. Assuming choice, there is a function F which maps an equivalence class to some element of it. Since these equivalence classes ignore finite differences, everyone can tell what equivalence class E has been assigned even without knowing their own hat color, so can guess their own color according to F(E). By construction this is in E, so it differs from the true assignment in only finitely many places, so all but finitely many players win. (The same holds for finitely many players too, but a strategy where all but finitely many players win is less impressive there.)
- mananaysiempre 4y ago
  > everyone can tell what equivalence class E has been assigned even without knowing their own hat color As is usual for such AC-dependent things, telling the class here is not (Turing) computable, right?
guerrilla 4y ago
> AC by itself implies only vapourware. However these zombie-like objects like the voting scheme are necessary for the smooth functioning of the mathematical universe. Without them the universe is chaotically irregular. So, considering we just covered a bunch of reductio ad absurdum proofs, AC is false and the universe is chaotically irregular. I'm just being rhetorical, as I suspect it's more technical than that but why do people not see things that way? Whenever people talk about AC, all I hear is a bunch of reasons why ZFC is inconsistent or at the very least incoherent in some weaker sense. How is the Banach–Tarski paradox not just a refutation of the ZFC axioms taken as a whole?
- lupire 4y ago
  Yes, the computable, countbale universe is incompatible with ZFC. But ZFC is math, not computation or physics. ZFC is consistent with itself, which is good enough for math. You don't even need AoC to run into this. Even the "tame" smooth functions of classical physics (like f(x)=x^2) are a non-physical approximation to discrete reality.
  - red_trumpet 4y ago
    Bold to assume that reality is discrete.
    - lupire 4y ago
      Even if it's not discrete at the bottom of QFT or something, it is discrete at the level where physics is applied in classical mechanics.
      - posterboy 4y ago
        Bold to assume that "it" is reality. Conversely, classical mechanics is discrete at the level where physics is applied. That it is applied to realia goes without saying. But it is not applied to reality as a whole.
tromp 4y ago
> majority rule. If the voters are v0, v1, v2, … vn-1 then the proposal is accepted if at least n/2+1 are in favour. That's not quite correct for odd n, where a proposal is accepted if at least (n+1)/2 are in favour...
- Karellen 4y ago
  I also don't get: Then we require the following properties to hold: [...] * The result of removing a single voter from a majority is still a majority. I'm not sure how that property always holds.
danbruc 4y ago
But what if there are infinitely many voters v0, v1, v2, … ? What does it mean for there to be a majority in favour? AC implies that there exists an infinitary voting scheme but supplies not a hint about how it could work. This already leaves me confused. I thought the axiom of choice says that it is possible to obtain an [infinite] set of votes from an [infinite] set of voters each with a non-empty set of choices, not that there is a way of combining a single [infinite] set of votes into a voting result. I guess it also says that there is a way to pick one of the votes from the [infinite] set of votes, but how does it imply that this choice can or must conform with the properties we want from a voting scheme?
- carstimon 4y ago
  > I thought the axiom of choice says that it is possible to obtain an [infinite] set of votes from an [infinite] set of voters each with a non-empty set of choices The axiom of choice does say this but, 1) This is not where we are applying the axiom of choice 2) You don't need the axiom of choice here: you can always just pick the "voting set" where everyone votes for choice # 1. The axiom of choice says that the product of infinitely many non-empty sets is empty. This is needed only when you might have a different and non-computable set of choices to make at each step. Where we are applying the axiom of choice here is: the voting scheme is just a rephrasing of an "Ultrafilter on the power set of a set": https://en.wikipedia.org/wiki/Ultrafilter#Ultrafilter_on_the_power_set_of_a_set https://en.wikipedia.org/wiki/Ultrafilter#Ultrafilter_on_the... This is implied by the axiom of choice in a way that requires some working out (and is sketched in wikipedia). But you can roughly see how the axiom of choice comes about if you start trying to construct a voting scheme (the following is just intuition): 1) We know the result if the number of "Nays" or "Yays" is finite. 2) Pick any set of "Yays" so the number of "Nays" and "Yays" is both infinite. Declare this set (arbitrarily) as a victory for either "Nay" or "Yay" 3) The set in (2) implies that a bunch of other sets are either Nay or Yay by the axioms in the article (e.g. flipping all votes flips the outcome, etc) 4) While there are sets we haven't decided on, repeat steps (2) and (3). Of course (4) is the whole tricky part, since you have to describe with this "looping forever" means rigorously... but you can see how the idea of "making infinitely distinct choices" comes up.
PaulHoule 4y ago
With his constructivist program I wish Steve Wolfram would just grow some balls and firmly reject the Axiom of Choice. (e.g. Mathematica at best can represent a measure subset 0 set of the phony numbers, the numbers that Mathematica can represent are more real than the rest of them.) His whole approach of throw a lot of things at the wall and seeing what sticks is never going to sample all of the objects requiring an infinite choice procedure to find.
- hackandthink 4y ago
  And we should switch to constructive reals in software. IEEE floats suck and mathematicals reals are in general not computable.
  - PaulHoule 4y ago
    I've long held that floating point with a decimal exponent would help a lot more people feel like computing is something they can be a part of. That is, I think the non-professional programmer finds that 0.1 + 0.2 != 0.3 is one of many little problems that adds up to them giving up the possibility of using software to put their skills on wheels. Like many reforms in computing, performance is used as an excuse to maintain the status quo of the priesthood. IBM is the only company in the industry that's taken this seriously, see https://en.wikipedia.org/wiki/Decimal_floating_point https://en.wikipedia.org/wiki/Decimal_floating_point
    - constantcrying 4y ago
      >I've long held that floating point with a decimal exponent You mean IEEE745 Decimals? Decimals also have serious pitfalls. For many applications they are just worse and lead to more problems. In the end they are at least as confusing as floats. And switching to them as the default would make programs generally worse. > Like many reforms in computing, performance is used as an excuse to maintain the status quo of the priesthood. Very silly argument. Performance is not the issue. Floats are useful because of their range. Even if input and output are small, intermediate results can easily be very large and exceed the representable decimals. Every programmer has to learn that the computer does not understand real numbers and that expecting it to is entirely misguided. No different representation will change that.
syzarian 4y ago
There are a lot of seemingly bizarre consequences of the Axiom of Choice. This is well known. Sometimes people haven’t seen a list of bizarre consequences when the Axiom of Choice is dropped. Here’s a nice write up of this: https://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70435#70435 https://mathoverflow.net/questions/20882/most-unintuitive-ap...
- ithinkso 4y ago
  This is not exactly a list when AC is dropped but if one takes as an axiom 'Axiom of Choice is false'
  - syzarian 4y ago
    In a given model the axiom is either true or false. When I say “dropped” I mean “false” in that model. It isn’t true that in all models where choice fails we have fields with no algebraic closure.
    - gizmo686 4y ago
      What about ZF; which is ZFC without the axiom of choice, and notably not ZF¬C, which is ZF with the negation of choice.
      - syzarian 4y ago
        In a given model of ZF either choice is true or it is false. In the absence of the Axiom of Choice you can’t say that not all fields have algebraic closures. What you can say is that there is a model in which there are fields with no algebraic closure.
- ouid 4y ago
  my favorite joke about this is: "the axiom of choice is obviously true, and the well ordering principle is obviously false, but Zorn's lemma? who can say?"
- 4y ago
hackandthink 4y ago
The constructive axiom of choice is fine. It's quite subtle, Per Martin-Löf: "There is therefore a need to investigate how the constructive axiom of choice, validated by the Brouwer-Heyting-Kolmogorov interpretation, is related to Zermelo’s axiom of choice ..." https://michaelt.github.io/martin-lof/One-hundred-years-of-Zermelo-s-axiom-of-choice-what-was-the-problem-with-it-2009.pdf https://michaelt.github.io/martin-lof/One-hundred-years-of-Z...
MarkPNeyer 4y ago
What are the things that “break” if the axiom of choice is false? I’ve been wondering if the axiom of choice has some relationship to an argument for the existence of free will. Not just because they share a name, but because you can think of physics as being a multiplayer game.
ogogmad 4y ago
This is coming from the opposite extreme. In constructive mathematics, abandoning Countable Choice may allow: - The complex numbers to not be closed under square roots. - Space-filling curves to no longer exist. And subtle complications around: - The definition of a real number. The Dedekind and Cauchy real numbers may become non-isomorphic. As it stands, the following has not been validated in constructive mathematics without countable choice: - That the Dedekind real numbers are uncountable. - That if a function over the Dedekind reals has derivative 0 everywhere, then it's constant. On the other hand, the Approximate Intermediate Value Theorem has been proven, but with a weird proof. See here [1] for more. [1] - https://ncatlab.org/nlab/show/countable+choice https://ncatlab.org/nlab/show/countable+choice
loicd 4y ago
The idea that the axiom of choice is guilty of all the non-constructible, weird stuff in mathematics is incorrect. The actual source of non-constructibility is always the law of excluded middle (aka the difference between classical and intuitionistic logics). What is true however is that the axiom of choice amplifies in a non-trivial way the non-constructibility of the law of excluded middle. To pick an analogy, consider the 2022 world cup. There will be a winner, but we don't know it yet. Thus, in a sense, the existence of the winner is non-constructible. In classical logic, we accept as true the following statement: Either France is the winner or the 2022 world cup, or it is not, even though we cannot tell which it is now. This is not a problem, because if we wait a bit, we will be able to determine which it is. The axiom of choice in that analogy amplifies the above non-constructive problem by allowing us to wait an infinite amount of time. In the end, the reason why the axiom of choice 'won' is the same as the reason why classical logic 'won' over intuitionistic logic: because constructibility gets in the way.
- whatshisface 4y ago
  I don't think you can say that classical logic won over intuitionistic logic when the former is thousands of years older and the latter is a growing area of research interest.
- agalunar 4y ago
  It's interesting that although you can't prove "forall P, P or not P" in intuitionistic logic, you can prove "forall P, not (not (P or not P))". In other words, it can't possibly be the case that P is not either true or false. This is particularly easy to do in Coq: Theorem lem : forall (p : Prop), ~ ~ (p \/ ~p). Proof. tauto. Qed. I personally like the distinction between "this is true" and "this can't possibly be false". If you have a proof of the second, you know why something must be true; if you have a proof of the first, you know how something is true. The rejection of double-negation elimination is more or less the (rather intuitive) idea that knowing why something must be true doesn't automatically mean you know how it's true.
  - loicd 4y ago
    > The rejection of double-negation elimination is more or less the (rather intuitive) idea that knowing why something must be true doesn't automatically mean you know how it's true. Exactly. There is also the matter of efficiency: it is easier to know why something must be true than to know how it's true. Constructibility in mathematics usually means proving things the hard way.
bmitc 4y ago
Regarding mathematical existence, one thing that I have thought about before and don't have an answer for or understanding of is the concept of infinities. In set theory, there are cardinalities that are "infinities of infinities". This is all fine and makes sense within the world of mathematics, as the study of idealized structures. But what makes me curious is that the universe is finite, and thus presumably, contains a finite amount of information. That is, the universe has a finite amount of bits that can be used to represent information. How does this work then? We can represent these sets of cardinality infinities of infinities in our brain and on paper, but representing these sets with all the available bits in the universe is not possible. This seems like a paradox, because our brains and paper are part of the universe. Does anyone have some thoughts on this? Is this a well-discussed problem? Any good references?
- sapiol 4y ago
  We can encode the idea of infinite sets and their relationship to one another with a finite set of symbols. But we can't enumerate those sets. Edit: How is there a paradox?
  - bmitc 4y ago
    > We can encode the idea of infinite sets and their relationship to one another with a finite set of symbols. I have thought about this, but it isn't entirely clear to me. For example, what is the bit encoding of the real numbers? Is it really accurate to say we have an encoding of them by just saying we have the set R? > But we can't enumerate those sets. Well, that's kind of the point of my question. Is this not an issue?
    - sapiol 4y ago
      I emphasize: We can encode THE IDEA or THE ABSTRACTION of infinite sets with a finite set of symbols.
- feoren 4y ago
  Why should the limits of our universe have anything to do with the limits of math? Math is bigger than our universe. If our universe were completely different, math would still be the same. > We can represent these sets of cardinality infinities of infinities in our brain and on paper, but representing these sets with all the available bits in the universe is not possible. This seems like a paradox, because our brains and paper are part of the universe. Eh, I can write a recipe that calls for multiple universes-worth of flour and 600 trillion years in the oven, and I can write that recipe in a minute on an index card that weighs a couple grams. I can write small programs that loop infinitely or (attempt to) use infinite memory. I can write a song that repeats ad infinitum that nobody can ever sing to completion in the entire lifetime of the universe. That's not much different than the words "the Integers" requiring 2 words but describing something that could not possibly be "fully materialized" in any finite universe. Who cares? What those all have in common is that despite being very big or long in some sense, they have low Kolmogorov complexity. It's very easy to describe "recipes" for infinite things that would exceed the bounds of the universe if they were ever fully realized; you don't even need higher cardinalities for that. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity What higher cardinalities do tell us is that there must be some real numbers that have infinite Kolmogorov complexity, and in fact 100% of the real numbers have this property. (Of course all the numbers you have/will ever have heard of are in the remaining 0%.) There are only countably many (the smallest infinity) descriptions in any language (programming or natural), so most reals must not be "describable" at all. We will never be able to meaningfully use any of those numbers, because we couldn't possibly "compute" them -- we can't run the infinitely long program. It's not clear to me that we'd ever be able to learn anything at all about such numbers, or indeed that they "exist" in any meaningful sense.

83 points by herodotus 4y ago

I like Bill Wadge's stuff and this is a great explanation of the axiom of choice. I spent a fair bit of time on ZF set theory + AC working in databases, and AC is essential for data-driven set-theory to function. Bit confused about the unit sphere explanation but then again I'm unfamiliar with the underlying paper.

algon33 4y ago
By database do you mean a finite 2d array with column headings? Or something that can be represented by such an object? And its entries are elements of some countable sets? If so, what are you doing using ZFC there?
- mr_gibbins 4y ago
  Thanks - see comment above.
zomglings 4y ago
I'm confused why you would need the Axiom of Choice when working with computable programs. Unless you were proving theorems about possible contents of a database? But even that seems like you wouldn't need the Axiom of Choice. Could you elaborate on what you were doing with ZFC with databases?
- mr_gibbins 4y ago
  Not to cop out but a HN reply isn't the best place to provide a full explanation. Suffice to say I use the ZF axioms as a basis to teach how sets both differ from and are similar to tables, particularly using the more accessible parts of Stoll's textbook on axiomatic set theory. To give a single example, the axiom schema of replacement is a good analogy for how the output of a SELECT command over a set will also result in a set. In terms of AC, the comment below about how this is actually the AFC is correct, since the sets I am talking about are finite. Of course, set projections or selections are arguably choice functions themselves, which makes them relevant, and ZFC includes AC in order to infer well-orderedness, which tables (after all, collections of sets) can indeed be.
lupire 4y ago
That's the Axiom of Finite Choice, not the full Axiom of Choice. https://en.m.wikipedia.org/wiki/Axiom_of_finite_choice https://en.m.wikipedia.org/wiki/Axiom_of_finite_choice
- mr_gibbins 4y ago
  Yes - you are correct :)

sylware 4y ago

I have always had mixed feelings about this axiom. It feels "2nd level", like it should build upon simpler axioms related to the mathematical object "set" and the mathematical object "function".

lupire 4y ago
What do you mean? The Axiom of Choice is a statement about a function on sets. In context, of ZF, it's equivalent to the Well Ordering Principle/Axiom and Zorn's Lemma/Axiom.
Koshkin 4y ago
Then it wouldn’t be an axiom, which it, in fact, is, being logically independent from the rest. It is considered somewhat special though, and mathematicians, being nice people, usually indicate whether they rely on it in a proof.
- sylware 4y ago
  Yep, this is what I meant by "2nd level": it feels like it is not an axiom but a theorem.

less_less 4y ago

My favorite application of choice, known as ultrafilters: You know those "mathematicians wearing hats" games, where the solution is a Hamming code or some kind of modular arithmetic thing? Here's one where there's no winning strategy. You have N mathematicians wearing hats whose colors are chosen uniformly and independently at random from a set C. They can see each others' hats but not their own. Simultaneously and without communication, each mathematician must guess their own hat color. Everyone who guesses right wins, and everyone who guesses wrong loses. A strategy maps (other mathematicians -> hat color) -> guess of your hat color, or if you're guessing randomly, then a distribution of guesses. No matter what strategy is chosen, N/|C| players win in expectation. There's no trick to improve this, though you can change the distribution of how many players win. For example, you can guarantee that at least floor(N/|C|) of them win. This is neat in that it works even in a derandomized setting, where the strategy must be deterministic and the hats are assigned maliciously by an opponent who knows the strategy. (This setting is easier to work with for infinite C, because you don't need to worry about probability distributions on infinite objects.) But if |C| > N, then you can't guarantee that anyone wins. OK, but what if there are infinitely many mathematicians, and you have the axiom of choice? In that case, there exists a strategy which guarantees that all but finitely many players will win — that is, the overwhelming majority of them will win. This works no matter how big C is, even if C is infinite, even if it's vastly larger than the set of players (eg if it's uncountable but the players are countable). Why? Well, consider the relation that two hat assignments are "almost the same" iff they differ in only finitely many places. This is an equivalence relation, so we can divide the space of hat assignments into equivalence classes. Assuming choice, there is a function F which maps an equivalence class to some element of it. Since these equivalence classes ignore finite differences, everyone can tell what equivalence class E has been assigned even without knowing their own hat color, so can guess their own color according to F(E). By construction this is in E, so it differs from the true assignment in only finitely many places, so all but finitely many players win. (The same holds for finitely many players too, but a strategy where all but finitely many players win is less impressive there.)

mananaysiempre 4y ago
> everyone can tell what equivalence class E has been assigned even without knowing their own hat color As is usual for such AC-dependent things, telling the class here is not (Turing) computable, right?

guerrilla 4y ago

> AC by itself implies only vapourware. However these zombie-like objects like the voting scheme are necessary for the smooth functioning of the mathematical universe. Without them the universe is chaotically irregular. So, considering we just covered a bunch of reductio ad absurdum proofs, AC is false and the universe is chaotically irregular. I'm just being rhetorical, as I suspect it's more technical than that but why do people not see things that way? Whenever people talk about AC, all I hear is a bunch of reasons why ZFC is inconsistent or at the very least incoherent in some weaker sense. How is the Banach–Tarski paradox not just a refutation of the ZFC axioms taken as a whole?

lupire 4y ago
Yes, the computable, countbale universe is incompatible with ZFC. But ZFC is math, not computation or physics. ZFC is consistent with itself, which is good enough for math. You don't even need AoC to run into this. Even the "tame" smooth functions of classical physics (like f(x)=x^2) are a non-physical approximation to discrete reality.
- red_trumpet 4y ago
  Bold to assume that reality is discrete.
  - lupire 4y ago
    Even if it's not discrete at the bottom of QFT or something, it is discrete at the level where physics is applied in classical mechanics.
    - posterboy 4y ago
      Bold to assume that "it" is reality. Conversely, classical mechanics is discrete at the level where physics is applied. That it is applied to realia goes without saying. But it is not applied to reality as a whole.

tromp 4y ago

> majority rule. If the voters are v0, v1, v2, … vn-1 then the proposal is accepted if at least n/2+1 are in favour. That's not quite correct for odd n, where a proposal is accepted if at least (n+1)/2 are in favour...

Karellen 4y ago
I also don't get: Then we require the following properties to hold: [...] * The result of removing a single voter from a majority is still a majority. I'm not sure how that property always holds.

danbruc 4y ago

But what if there are infinitely many voters v0, v1, v2, … ? What does it mean for there to be a majority in favour? AC implies that there exists an infinitary voting scheme but supplies not a hint about how it could work. This already leaves me confused. I thought the axiom of choice says that it is possible to obtain an [infinite] set of votes from an [infinite] set of voters each with a non-empty set of choices, not that there is a way of combining a single [infinite] set of votes into a voting result. I guess it also says that there is a way to pick one of the votes from the [infinite] set of votes, but how does it imply that this choice can or must conform with the properties we want from a voting scheme?

carstimon 4y ago
> I thought the axiom of choice says that it is possible to obtain an [infinite] set of votes from an [infinite] set of voters each with a non-empty set of choices The axiom of choice does say this but, 1) This is not where we are applying the axiom of choice 2) You don't need the axiom of choice here: you can always just pick the "voting set" where everyone votes for choice # 1. The axiom of choice says that the product of infinitely many non-empty sets is empty. This is needed only when you might have a different and non-computable set of choices to make at each step. Where we are applying the axiom of choice here is: the voting scheme is just a rephrasing of an "Ultrafilter on the power set of a set": https://en.wikipedia.org/wiki/Ultrafilter#Ultrafilter_on_the_power_set_of_a_set https://en.wikipedia.org/wiki/Ultrafilter#Ultrafilter_on_the... This is implied by the axiom of choice in a way that requires some working out (and is sketched in wikipedia). But you can roughly see how the axiom of choice comes about if you start trying to construct a voting scheme (the following is just intuition): 1) We know the result if the number of "Nays" or "Yays" is finite. 2) Pick any set of "Yays" so the number of "Nays" and "Yays" is both infinite. Declare this set (arbitrarily) as a victory for either "Nay" or "Yay" 3) The set in (2) implies that a bunch of other sets are either Nay or Yay by the axioms in the article (e.g. flipping all votes flips the outcome, etc) 4) While there are sets we haven't decided on, repeat steps (2) and (3). Of course (4) is the whole tricky part, since you have to describe with this "looping forever" means rigorously... but you can see how the idea of "making infinitely distinct choices" comes up.

PaulHoule 4y ago

With his constructivist program I wish Steve Wolfram would just grow some balls and firmly reject the Axiom of Choice. (e.g. Mathematica at best can represent a measure subset 0 set of the phony numbers, the numbers that Mathematica can represent are more real than the rest of them.) His whole approach of throw a lot of things at the wall and seeing what sticks is never going to sample all of the objects requiring an infinite choice procedure to find.

hackandthink 4y ago
And we should switch to constructive reals in software. IEEE floats suck and mathematicals reals are in general not computable.
- PaulHoule 4y ago
  I've long held that floating point with a decimal exponent would help a lot more people feel like computing is something they can be a part of. That is, I think the non-professional programmer finds that 0.1 + 0.2 != 0.3 is one of many little problems that adds up to them giving up the possibility of using software to put their skills on wheels. Like many reforms in computing, performance is used as an excuse to maintain the status quo of the priesthood. IBM is the only company in the industry that's taken this seriously, see https://en.wikipedia.org/wiki/Decimal_floating_point https://en.wikipedia.org/wiki/Decimal_floating_point
  - constantcrying 4y ago
    >I've long held that floating point with a decimal exponent You mean IEEE745 Decimals? Decimals also have serious pitfalls. For many applications they are just worse and lead to more problems. In the end they are at least as confusing as floats. And switching to them as the default would make programs generally worse. > Like many reforms in computing, performance is used as an excuse to maintain the status quo of the priesthood. Very silly argument. Performance is not the issue. Floats are useful because of their range. Even if input and output are small, intermediate results can easily be very large and exceed the representable decimals. Every programmer has to learn that the computer does not understand real numbers and that expecting it to is entirely misguided. No different representation will change that.

syzarian 4y ago

There are a lot of seemingly bizarre consequences of the Axiom of Choice. This is well known. Sometimes people haven’t seen a list of bizarre consequences when the Axiom of Choice is dropped. Here’s a nice write up of this: https://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70435#70435 https://mathoverflow.net/questions/20882/most-unintuitive-ap...

ithinkso 4y ago
This is not exactly a list when AC is dropped but if one takes as an axiom 'Axiom of Choice is false'
- syzarian 4y ago
  In a given model the axiom is either true or false. When I say “dropped” I mean “false” in that model. It isn’t true that in all models where choice fails we have fields with no algebraic closure.
  - gizmo686 4y ago
    What about ZF; which is ZFC without the axiom of choice, and notably not ZF¬C, which is ZF with the negation of choice.
    - syzarian 4y ago
      In a given model of ZF either choice is true or it is false. In the absence of the Axiom of Choice you can’t say that not all fields have algebraic closures. What you can say is that there is a model in which there are fields with no algebraic closure.
ouid 4y ago
my favorite joke about this is: "the axiom of choice is obviously true, and the well ordering principle is obviously false, but Zorn's lemma? who can say?"
4y ago

hackandthink 4y ago

The constructive axiom of choice is fine. It's quite subtle, Per Martin-Löf: "There is therefore a need to investigate how the constructive axiom of choice, validated by the Brouwer-Heyting-Kolmogorov interpretation, is related to Zermelo’s axiom of choice ..." https://michaelt.github.io/martin-lof/One-hundred-years-of-Zermelo-s-axiom-of-choice-what-was-the-problem-with-it-2009.pdf https://michaelt.github.io/martin-lof/One-hundred-years-of-Z...

MarkPNeyer 4y ago

What are the things that “break” if the axiom of choice is false? I’ve been wondering if the axiom of choice has some relationship to an argument for the existence of free will. Not just because they share a name, but because you can think of physics as being a multiplayer game.

ogogmad 4y ago

This is coming from the opposite extreme. In constructive mathematics, abandoning Countable Choice may allow: - The complex numbers to not be closed under square roots. - Space-filling curves to no longer exist. And subtle complications around: - The definition of a real number. The Dedekind and Cauchy real numbers may become non-isomorphic. As it stands, the following has not been validated in constructive mathematics without countable choice: - That the Dedekind real numbers are uncountable. - That if a function over the Dedekind reals has derivative 0 everywhere, then it's constant. On the other hand, the Approximate Intermediate Value Theorem has been proven, but with a weird proof. See here [1] for more. [1] - https://ncatlab.org/nlab/show/countable+choice https://ncatlab.org/nlab/show/countable+choice

loicd 4y ago

The idea that the axiom of choice is guilty of all the non-constructible, weird stuff in mathematics is incorrect. The actual source of non-constructibility is always the law of excluded middle (aka the difference between classical and intuitionistic logics). What is true however is that the axiom of choice amplifies in a non-trivial way the non-constructibility of the law of excluded middle. To pick an analogy, consider the 2022 world cup. There will be a winner, but we don't know it yet. Thus, in a sense, the existence of the winner is non-constructible. In classical logic, we accept as true the following statement: Either France is the winner or the 2022 world cup, or it is not, even though we cannot tell which it is now. This is not a problem, because if we wait a bit, we will be able to determine which it is. The axiom of choice in that analogy amplifies the above non-constructive problem by allowing us to wait an infinite amount of time. In the end, the reason why the axiom of choice 'won' is the same as the reason why classical logic 'won' over intuitionistic logic: because constructibility gets in the way.

whatshisface 4y ago
I don't think you can say that classical logic won over intuitionistic logic when the former is thousands of years older and the latter is a growing area of research interest.
agalunar 4y ago
It's interesting that although you can't prove "forall P, P or not P" in intuitionistic logic, you can prove "forall P, not (not (P or not P))". In other words, it can't possibly be the case that P is not either true or false. This is particularly easy to do in Coq: Theorem lem : forall (p : Prop), ~ ~ (p \/ ~p). Proof. tauto. Qed. I personally like the distinction between "this is true" and "this can't possibly be false". If you have a proof of the second, you know why something must be true; if you have a proof of the first, you know how something is true. The rejection of double-negation elimination is more or less the (rather intuitive) idea that knowing why something must be true doesn't automatically mean you know how it's true.
- loicd 4y ago
  > The rejection of double-negation elimination is more or less the (rather intuitive) idea that knowing why something must be true doesn't automatically mean you know how it's true. Exactly. There is also the matter of efficiency: it is easier to know why something must be true than to know how it's true. Constructibility in mathematics usually means proving things the hard way.

bmitc 4y ago

Regarding mathematical existence, one thing that I have thought about before and don't have an answer for or understanding of is the concept of infinities. In set theory, there are cardinalities that are "infinities of infinities". This is all fine and makes sense within the world of mathematics, as the study of idealized structures. But what makes me curious is that the universe is finite, and thus presumably, contains a finite amount of information. That is, the universe has a finite amount of bits that can be used to represent information. How does this work then? We can represent these sets of cardinality infinities of infinities in our brain and on paper, but representing these sets with all the available bits in the universe is not possible. This seems like a paradox, because our brains and paper are part of the universe. Does anyone have some thoughts on this? Is this a well-discussed problem? Any good references?

sapiol 4y ago
We can encode the idea of infinite sets and their relationship to one another with a finite set of symbols. But we can't enumerate those sets. Edit: How is there a paradox?
- bmitc 4y ago
  > We can encode the idea of infinite sets and their relationship to one another with a finite set of symbols. I have thought about this, but it isn't entirely clear to me. For example, what is the bit encoding of the real numbers? Is it really accurate to say we have an encoding of them by just saying we have the set R? > But we can't enumerate those sets. Well, that's kind of the point of my question. Is this not an issue?
  - sapiol 4y ago
    I emphasize: We can encode THE IDEA or THE ABSTRACTION of infinite sets with a finite set of symbols.
feoren 4y ago
Why should the limits of our universe have anything to do with the limits of math? Math is bigger than our universe. If our universe were completely different, math would still be the same. > We can represent these sets of cardinality infinities of infinities in our brain and on paper, but representing these sets with all the available bits in the universe is not possible. This seems like a paradox, because our brains and paper are part of the universe. Eh, I can write a recipe that calls for multiple universes-worth of flour and 600 trillion years in the oven, and I can write that recipe in a minute on an index card that weighs a couple grams. I can write small programs that loop infinitely or (attempt to) use infinite memory. I can write a song that repeats ad infinitum that nobody can ever sing to completion in the entire lifetime of the universe. That's not much different than the words "the Integers" requiring 2 words but describing something that could not possibly be "fully materialized" in any finite universe. Who cares? What those all have in common is that despite being very big or long in some sense, they have low Kolmogorov complexity. It's very easy to describe "recipes" for infinite things that would exceed the bounds of the universe if they were ever fully realized; you don't even need higher cardinalities for that. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity What higher cardinalities do tell us is that there must be some real numbers that have infinite Kolmogorov complexity, and in fact 100% of the real numbers have this property. (Of course all the numbers you have/will ever have heard of are in the remaining 0%.) There are only countably many (the smallest infinity) descriptions in any language (programming or natural), so most reals must not be "describable" at all. We will never be able to meaningfully use any of those numbers, because we couldn't possibly "compute" them -- we can't run the infinitely long program. It's not clear to me that we'd ever be able to learn anything at all about such numbers, or indeed that they "exist" in any meaningful sense.