3 ms·

> Without the axiom of choice, the product of infinitely many non-empty sets could be empty. This sounds like a stupid question, but I can't really figure it o

by adsche 13y ago

> Without the axiom of choice, the product of infinitely many non-empty sets could be empty. This sounds like a stupid question, but I can't really figure it out: How could it be empty, given your above formula? (Math level: Engineer) Edit: Wait, is it because every set contains the empty set? And without choosing you could end up with the empty set?

ColinWright 13y ago
This is what the axiom of choice is about. It says: Given a collection of non-empty sets, there exists a "choice function" that chooses one element from each set. (AC) The problem is, AC can be used to prove all sorts of counter-intuitive results. The example that turns up here on HN all the time is Banach-Tarski[0][1], but this submission about x^2 being the sum of three periodic functions is another. AC has been proven to be independent of the usual axioms of set theory, so in some sense you can choose whether to believe it or not. If it's true then Banach-Tarski is true. If it's false then you can have infinitely many non-empty sets with an empty Cartesian product. (corrected to read "an empty" instead of the error "a non-empty" - thanks thaumasiotes) Pure math be crazy. And cool. [0] http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox [1] https://www.hnsearch.com/search#request/all&q=banach+tarski https://www.hnsearch.com/search#request/all&q=banach+tarski ---- Edit: No, it's not because of your edit: > ... is it because every set contains the empty set? > And without choosing you could end up with the empty set? Not every set contains the empty set as an element, but every set has the empty set as a subset. We are talking about choosing elements, and the it that says "non-empty set" means that for every individual set we can choose one of its elements. The problem comes in that when there are infinitely many, including possibly uncountably infinitely many, we need to do all these choices "at once" (in some sense).
- thaumasiotes 13y ago
  > If it's false then you can have infinitely many non-empty sets with a non-empty Cartesian product. with an empty Cartesian product, I think?
- adsche 13y ago
  Thanks! Yes, I have seen Banach-Tarski before, here and elsewhere. My confusion was mostly due to not thoroughly remembering what an axiom is... I expected there to be some kind of proof, like an example of a series of non-empty sets that have an empty set as their product. Pure math be crazy. And cool. Indeed pretty cool. Thanks for submitting this fascinating link. Not every set contains the empty set as an element, but every set has the empty set as a subset. Yes, I mixed this up quite badly.
thaumasiotes 13y ago
First things first: > Wait, is it because every set contains the empty set? No. For example, the set {1} contains only one element, the integer 1, and does not contain the empty set. > This sounds like a stupid question, but I can't really figure it out: How could it be empty, given your above formula? The axiom of choice is called an axiom for a reason. It states that the cartesian product of infinitely many non-empty sets contains at least one element. So under the assumption that the axiom of choice is true, obviously, the product of non-empty sets cannot be empty, because that's the definition of the axiom of choice. Conversely, under the assumption that the axiom of choice is false, there must be some infinite collection of non-empty sets for which the cartesian product is empty. Many people (like you!) find this absurd; thinking it's absurd doesn't indicate any problems with your intuition. Now, there's a saying about the axiom of choice: The axiom of choice is obviously true, the well-ordering principle is obviously false, and who can tell about Zorn's lemma? It's a joke; the three items mentioned are all known to be equivalent. The axiom of choice is known to have equally "absurd" consequences. One, referenced in the above joke, is that it is equivalent to the statement All sets have a well-ordering Which can be rephrased: For any set S, all subsets of S contain a least element You might want to reflect on what the least element of the open interval (0,1) would be. (Note, "least" refers to the well-ordering of the set guaranteed to exist by the axiom of choice; it does not refer to the numeric sense in which 3 is less than 4.) The axiom of choice also gives us the Banach-Tarski theorem, which says that a sphere can be divided into a finite number of pieces which can then be rearranged without deformation into two spheres of the same radius. I generally lump anti-choice mathematicians into the same group as constructivists, but theoretically there could be a distinction. There are no known consequences (outside of the various theorems proved using the axiom, all rather abstruse) to believing one way or the other, but it's a rather emotional subject for many people. Why, I couldn't tell you.
- adsche 13y ago
  The axiom of choice is called an axiom for a reason. [...] thinking it's absurd doesn't indicate any problems with your intuition. Thanks, that is exactly what I needed to read :) You might want to reflect on what the least element of the open interval (0,1) would be. Am I right in assuming that I can not find any such element with my "intuition", but the axiom guarantees that there is a least element?

by adsche 13y ago

ColinWright 13y ago

This is what the axiom of choice is about. It says: Given a collection of non-empty sets, there exists a "choice function" that chooses one element from each set. (AC) The problem is, AC can be used to prove all sorts of counter-intuitive results. The example that turns up here on HN all the time is Banach-Tarski[0][1], but this submission about x^2 being the sum of three periodic functions is another. AC has been proven to be independent of the usual axioms of set theory, so in some sense you can choose whether to believe it or not. If it's true then Banach-Tarski is true. If it's false then you can have infinitely many non-empty sets with an empty Cartesian product. (corrected to read "an empty" instead of the error "a non-empty" - thanks thaumasiotes) Pure math be crazy. And cool. [0] http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox [1] https://www.hnsearch.com/search#request/all&q=banach+tarski https://www.hnsearch.com/search#request/all&q=banach+tarski ---- Edit: No, it's not because of your edit: > ... is it because every set contains the empty set? > And without choosing you could end up with the empty set? Not every set contains the empty set as an element, but every set has the empty set as a subset. We are talking about choosing elements, and the it that says "non-empty set" means that for every individual set we can choose one of its elements. The problem comes in that when there are infinitely many, including possibly uncountably infinitely many, we need to do all these choices "at once" (in some sense).

thaumasiotes 13y ago
> If it's false then you can have infinitely many non-empty sets with a non-empty Cartesian product. with an empty Cartesian product, I think?
adsche 13y ago
Thanks! Yes, I have seen Banach-Tarski before, here and elsewhere. My confusion was mostly due to not thoroughly remembering what an axiom is... I expected there to be some kind of proof, like an example of a series of non-empty sets that have an empty set as their product. Pure math be crazy. And cool. Indeed pretty cool. Thanks for submitting this fascinating link. Not every set contains the empty set as an element, but every set has the empty set as a subset. Yes, I mixed this up quite badly.

thaumasiotes 13y ago

First things first: > Wait, is it because every set contains the empty set? No. For example, the set {1} contains only one element, the integer 1, and does not contain the empty set. > This sounds like a stupid question, but I can't really figure it out: How could it be empty, given your above formula? The axiom of choice is called an axiom for a reason. It states that the cartesian product of infinitely many non-empty sets contains at least one element. So under the assumption that the axiom of choice is true, obviously, the product of non-empty sets cannot be empty, because that's the definition of the axiom of choice. Conversely, under the assumption that the axiom of choice is false, there must be some infinite collection of non-empty sets for which the cartesian product is empty. Many people (like you!) find this absurd; thinking it's absurd doesn't indicate any problems with your intuition. Now, there's a saying about the axiom of choice: The axiom of choice is obviously true, the well-ordering principle is obviously false, and who can tell about Zorn's lemma? It's a joke; the three items mentioned are all known to be equivalent. The axiom of choice is known to have equally "absurd" consequences. One, referenced in the above joke, is that it is equivalent to the statement All sets have a well-ordering Which can be rephrased: For any set S, all subsets of S contain a least element You might want to reflect on what the least element of the open interval (0,1) would be. (Note, "least" refers to the well-ordering of the set guaranteed to exist by the axiom of choice; it does not refer to the numeric sense in which 3 is less than 4.) The axiom of choice also gives us the Banach-Tarski theorem, which says that a sphere can be divided into a finite number of pieces which can then be rearranged without deformation into two spheres of the same radius. I generally lump anti-choice mathematicians into the same group as constructivists, but theoretically there could be a distinction. There are no known consequences (outside of the various theorems proved using the axiom, all rather abstruse) to believing one way or the other, but it's a rather emotional subject for many people. Why, I couldn't tell you.

adsche 13y ago
The axiom of choice is called an axiom for a reason. [...] thinking it's absurd doesn't indicate any problems with your intuition. Thanks, that is exactly what I needed to read :) You might want to reflect on what the least element of the open interval (0,1) would be. Am I right in assuming that I can not find any such element with my "intuition", but the axiom guarantees that there is a least element?