Talk:Axiom of choice

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Top-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Top Importance
 Field: Foundations, logic, and set theory

Any union of countably many countable sets is itself countable[edit]

My undergraduate maths degree was most of three decades ago, so this must be tentative. But does “Any union of countably many countable sets is itself countable” really need anything more than plain ZF? It seems ‘obvious’ that this can be shown in much the same way that ℚ can be shown to be countable.

Of course I must be wrong. In which case please could this line acquire a source? (Or a sketch explanation under this talk comment.) Thank you. JDAWiseman (talk) 19:36, 29 November 2014 (UTC)

Further thought: what if each set is countable in uncountably many different ways, between which one can’t distinguish? Ahh. But maybe a few words or a source would help those confused as I was. JDAWiseman (talk) 19:46, 29 November 2014 (UTC)

This issue has been discussed before, repeatedly I think. For example, see Talk:Axiom of choice/Archive 2#countable sets. The upshot is that at least the axiom of countable choice is needed to conclude that a countable union of countable sets is countable. JRSpriggs (talk) 13:07, 30 November 2014 (UTC)
Excellent, thank you. I was wrong, I was correct, and you have proved me even more correct. My ‘like ℚ’ argument was wrong. My ‘how choose one of many orderings’ was correct. So far, I hope, we agree. But your archive link adds weight to my suggestion that “a few words or a source would help those confused as I was”. If multiple readers are confused by something in a Wikipedia entry, the entry could be improved.
What words? Perhaps add “(because it is necessary to choose a particular ordering for each of the countably many sets)”. I’m not insisting on those words, but please hear confused readers needing help — and it won’t be just those who have posted in the talk pages, JDAWiseman (talk) 15:49, 30 November 2014 (UTC)
That is a good wording. Feel free to add it to the article. JRSpriggs (talk) 08:17, 1 December 2014 (UTC)
Done. JDAWiseman (talk) 08:26, 1 December 2014 (UTC)

Surjections[edit]

Is the statement "For any two nonempty sets X and Y, there is a surjection X->Y or a surjection Y->X." equivalent to the axiom of choice? GeoffreyT2000 (talk) 04:50, 26 February 2015 (UTC)

I think that the answer is "yes". It is similar to but more complicated than the proof for injections.
Clearly, the axiom of choice implies that one of the surjections exists because X would be equinumerous with an ordinal and Y would be equinumerous with another ordinal. The larger ordinal could be mapped onto the smaller one, so there would be a surjection between X and Y (one way or the other).
To go the other way, suppose X is an arbitrary nonempty set, we will show that it can be well-ordered which implies the axiom of choice.
Let Y=P(X)+, that is the Hartogs number of the powerset of X. Then there is no injection from the ordinal Y to the powerset of X. Thus there is no surjection from X to Y.
So by your hypothesis, there must be a surjection from Y to X. For each element x of X, find the least element y of Y which maps to x. Well order X according to the ordering on the y associated with each x in X. JRSpriggs (talk) 08:01, 26 February 2015 (UTC)

Quantum and Cosmological Axiom application[edit]

This article does not mention at all the quantum and cosmological contributions of the "axiom of choice". Also the quantum cryptography applications of it. -- 2.84.223.244 (talk · contribs) 18:10, 14 April 2015‎ (UTC)

Are there any such applications? It seems unlikely to me. If you know of any, please provide a reference to a reliable source. JRSpriggs (talk) 19:57, 15 April 2015 (UTC)
Unlikely, yes! But there are results linking set theory and physics. Google for "Some Set Theories are More Equal" (I was unable to place a link here for some reason). The reference, by Menachem Magidor, is not published, but still probably reliable. There are even results linking the continuum hypothesis and Bell's theorem (see section 5 in ref). YohanN7 (talk) 11:42, 28 April 2015 (UTC)
We seem to be dealing with "philosophy of set theory" articles here; the question of whether those are "reliable", even if in otherwise reliable journals, is still open. (BTW, as a set theory expert, I assert that the connection between the continuum hypothesis and Bell's theorem is flawed, as the maps do no good unless measurable, and (here, as I'm not a physics expert, I cannot be sure), seem to have no physical significance unless they meet some continuity requirement.) — Arthur Rubin (talk) 17:04, 28 April 2015 (UTC)
I think Magidor's point is this (from his paper):
As to be expected we do not have any definite case in which different set theories have an impact on physical theories but we believe that the possibility that it may happen in the future is not as outrageous as it may sound.
Not outrageous, that is, just very very improbable. There may be flaws in Magidor's reasoning of course. As far as continuity requirement go, we don't even know for sure that space and time is "a continuous background", so it may be tricky to even define "continuity", i.e. a suitable topology on spacetime in which "continuity" make physical' sense.
I don't believe much of this, but it is intriguing that a notable set theorist has taken up the issue. And it is fun to speculate a little, even though this probably is the wrong forum for it. YohanN7 (talk) 17:50, 28 April 2015 (UTC)
The link to your suggested reference is here. JRSpriggs (talk) 04:43, 29 April 2015 (UTC)
Thank you. But note that it is not a suggested reference for the article. Just to what I was referring to on this talk page. YohanN7 (talk) 10:33, 16 June 2015 (UTC)

Quotes section[edit]

Why is there a quotes section? It seems to run afoul of WP:TRIV. Comparable articles don't have a quotes section. It doesn't impart any useful information about the subject to the reader. This section ought be removed. 108.30.151.98 (talk) 19:08, 15 June 2015 (UTC)

The quotes section belongs because AC is kind of controversial and the quotes expresses some of the (sometimes) strong sentiments about it in a clever way that no dry technical section could convey to the average reader. The idea that quotes do not belong in WP is just nonsense. YohanN7 (talk) 13:49, 17 June 2015 (UTC)

The informal example about sock and shoes is invalid.[edit]

The Axiom of Choice holds true for this example. A set is a collection of different elements. So: Take an empty set, put two (i.e. a pair of) indistinguishable socks in it and you get a set with just one sock. Thus there's no problem with picking a sock from a set containing just one sock. — Preceding unsigned comment added by BostX (talkcontribs) 17:53, 2 August 2015 (UTC)

As for socks, any two socks can be distinguished, if only by their location at some particular time.
For sets, by the axiom of extensionality any two sets must be distinguishable by one containing an element which the other does not. However, for any specific criterion which might be used to distinguish sets, there will be (in some models of ZF set theory) two distinct sets which cannot be distinguished from one another by that particular criterion. That is why we need the axiom of choice. JRSpriggs (talk) 07:02, 3 August 2015 (UTC)
> As for socks, any two socks can be distinguished, if only by their location at some particular time.
Wrong. We operate on sets of indistinguishable socks:
[..] for an infinite collection of pairs of socks (assumed to have no distinguishing features).
Being at location X and being at locations Y is a distinguishing feature. But such a feature is explicitelly ruled out. So a set of indistinguishable socks can contain eiher no sock or just one sock. It would be better to use some other example, e.g.:
One can select the left shoe from any (even infinite) collection of shoe pairs but one cannot select a shoe which was produced at first because the shoe factory produces all the left and right shoes at once on parallel runing production lines. Such a selection can be obtained only by invoking the axiom of choice.
— Preceding unsigned comment added by BostX (talkcontribs) 19:20, 6 January 2016‎
Zermelo–Fraenkel set theory is about the von Neumann universe which contains only pure sets. So, strictly speaking, neither shoes nor socks can be discussed in ZFC. However, the example was used to give the reader, unfamiliar with set theory, the general idea of distinguishable and indistinguishable things. The example should not be taken too seriously.
The important point which I made was in my second paragraph where I said, "... for any specific criterion which might be used to distinguish sets, there will be (in some models of ZF set theory) two distinct sets which cannot be distinguished from one another by that particular criterion.". Consequently, the axiom of choice is not a redundancy. If there are models of ZF, then there are models of ZF¬C (as well as models of ZFC). JRSpriggs (talk) 03:47, 7 January 2016 (UTC)

Banach-Tarski paradox[edit]

The text currently says "it is impossible to construct the required decomposition of the unit ball in ZF, but also impossible to prove there is no such decomposition." However, this to me looks like an internal contradiction. If we let the statement P be "it is impossible to construct the required decomposition", then the text is saying "P holds, but it is impossible to prove P." I am quite certain that that is NOT what we want to say, but I am not entirely sure how the sentence should be rephrased. KarlFrei (talk) 16:06, 25 November 2016 (UTC)

Well, no, there's no internal contradiction there per se. There are definitely true statements that are impossible to prove in a given formal theory — see Gödel's incompleteness theorems.
However it is true that the given wording is problematic, because it's not clear what it means to "construct a decomposition in ZF". It would be better to say that it is impossible to prove in ZF that there is such a decomposition, but it is also impossible to prove in ZF that there is not. --Trovatore (talk) 01:43, 26 November 2016 (UTC)
Both horns of this dilemma (it is impossible to construct the required decomposition of the unit ball in ZF, but also impossible to prove [in ZF] there is no such decomposition) can be proved, but only in a theory stronger than ZF (unless ZF is inconsistent). JRSpriggs (talk) 11:06, 26 November 2016 (UTC)
That's true, or at least could be true, once you say what it means to "construct ... in ZF". If you mean just "prove existence in ZF", then the statement is true, but arguably misleading because of the word "construct". If you want the word "construct" to be used in some more substantive sense, then there may be something more to prove, depending on what sense you mean. --Trovatore (talk) 19:46, 26 November 2016 (UTC)