Talk:Axiom of choice

From Wikipedia, the free encyclopedia
Jump to navigation Jump to 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

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). (6/2017, see this Harvard link Jimw338 (talk) 22:28, 20 June 2017 (UTC)) 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)

The examples does not work at all, because an infinite set of shoes or socks is non-sense, and socks that are indistinguishable (by extension) is non-sense as well. An example that involves non-sense confuses rather than makes things clearer. Similarly, " In many cases such a selection [from bins] can be made without invoking the axiom of choice" does not make sense. To spell it out: I have 10 bins with things ... to grab one thing from each why should I invoke some mystical axiom of choice? These examples just makes the issue more complicated. I think the problem is that ZF and ZFC do not deal with matter/things, but with abstract sets. Hence, clearifying examples should be abstract sets. A clarifying example is: From a set of subsets of the natural numbers, one may always select the smallest number in each subset, e.g. in {{4,5,6}, {10,12}, {1,400,617,8000}} the smallest elements are {1,4,10}. In this case, "select the smallest number" is choice function. This works perfectly with the example section. "The difficulty appears when there is no natural choice of elements from each set. If we cannot make explicit choices, how do we know that our set exists? For example, suppose that X is the set of all non-empty subsets of the real numbers. ...."

By the way, the use of "informal" suggests that informal thinking is not concise or even incorrect. There is no reference to any proof of this, hence it should not be taken for granted. I suggest not using informal as a discourse degrading term. -- Bjerke (talk · contribs) 03:08, 28 December 2017‎ (UCT)

A few thoughts, without a clear conclusion:
  • I don't see anything nonsensical about an infinite set of socks or shoes. Why is this "non-sense"?
  • On the other hand, it is perfectly true that ZF(C) does not deal with socks or shoes, per se.
  • More seriously, the notion of indistinguishability of socks is slightly problematic because pure set theory, without urelements, does not admit any absolute indiscernibles (when set theorists talk about indiscernibles, for example in the context of sharps, they almost always mean order-indiscernibles).
  • However, the socks-and-shoes example is standard and sourceable. It does provide useful intuitions, even if they are slightly challenging to translate rigorously to the objects of discourse of ZF(C).
So at the moment I kind of see both sides, and I don't have a firm conclusion to offer. I think socks-and-shoes should probably be mentioned, given that it's so standard, but we should probably offer some sort of caveat. --Trovatore (talk) 22:31, 3 January 2018 (UTC)

Concerning Trovatore's four points:

  1. Could anyone, please, give me an example of an infinite set of socks or shoes? If not, it is non-sense, like the assertion: the moon is made of blue cheese. That is, the example is counter-intuitive because it does not refer to anything (well)known for the apprentice.
  2. Exactly.
  3. Again, could anyone give an example of indiscernable socks? If not, it is counter-intuitive. Moreover, indiscernables is not a trivial concept in math that makes it easier to grasp the axiom of choice. (Cf. Identity of indiscernibles)
  4. That it is standard and sourceable that Maria became pregnant without having sex, does not make it true. So, what useful intuitions do the shoe and socks example actually provide? Please, give me just one argument for the intuition promoting effect of the socks and shoe example.

For these reasons, I revert the section of the article to my proposal again. The two persons who have deleted my change, have not provided any arguments for doing so. — Preceding unsigned comment added by Bjerke (talkcontribs) 08:37, 4 January 2018 (UTC)

Well, Wcherowi writes: "This is not an improvement; your talk argument is very weak." This argument is extremly weak (and subjective). Why is my argument very weak? I have at least given reasons. Wcherowi has not! — Preceding unsigned comment added by Bjerke (talkcontribs) 08:52, 4 January 2018 (UTC)

JRSpriggs writes: "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."

First of all, an example that should introduce something must be taken seriously, else one risks to confuse the unknowlegeable reader. Moreover, it is problematic to introduce non-trivial concepts like indiscernables or indistinguishability when these concepts apparently play a marginal role in the article. That will add to confusion.

But, JRSpriggs also write: "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."

This is an important argument, and it would be nice to have it spelled out in the article. But, I doubt if this should be done in the introduction. — Preceding unsigned comment added by Bjerke (talkcontribs) 10:09, 4 January 2018 (UTC)

I think that the shoes and sock example is quite reasonable for the lede. We can source it to many texts, including "Logic, Induction, and Sets" by Forstner and "Combinatorics and Graph Theory" by Harris, Hirst, and Mossinghoff and "Elements of Set Theory" by Enderton. Indeed, the prevalence of this particular example is a reason to include it in this article. — Carl (CBM · talk) 16:55, 4 January 2018 (UTC)

Now, I think the section is much better. But, there is still a problem with the shoe-sock analogy: To avoid confusion of the apprentice, it is important to explain exactly what the example illustrate? Certainly, it does not (directly) illustrate something about picking one element from each of a collection of sets (which is the context). Rather, it illustrates that sometimes there is no choice function available, and in such cases, the axiom of choice must be invoked.Bjerke (talk) 02:30, 5 January 2018 (UTC)

No. What the axiom of choice says is that a choice function does exist, even if it's not defined by any rule, and the reason is precisely that you can "pick" one sock, arbitrarily, from each pair. That's the intuition the example is trying to get across.
Indeed, I like: "What the axiom of choice says is that a choice function does exist, even if it's not defined by any rule ..." It makes it clearer. I add it.
Of course the actual picking is a supertask, but that's OK. Set theory is all about supertasks. --Trovatore (talk)
But, since supertasks are physically impossible [1], they are constitutive for the many of the problems with using physical examples to illustrate set theory issues. Set theory is beyond the physical world (though applicable to it). - Bjerke (talk) 07:30, 6 January 2018 (UTC)
Whether they're physically possible is utterly irrelevant. --Trovatore (talk) 07:33, 6 January 2018 (UTC)
The example is directly and literally about picking one element from an infinite collection of sets, where each of those sets contains one pair of indistinguishable socks. This more to set theory than just sets of sets, and the axiom of choice is not limited to ZFC set theory (the socks could simply be urelements). Separately, the choice function itself is a rule that tells how to make the desired selection - the rule is "use that particular choice function". So when we have the axiom of choice there is always at least one rule that says how to make the desired selection. — Carl (CBM · talk) 15:05, 6 January 2018 (UTC)
Well, I think "rule" connotes some sort of definability. AC guarantees you that a choice function exists, but not that a definable one exists, so there may not be a rule that's expressible without giving a choice function as a parameter. "Rules" can sometimes have parameters, but I think something of the idea can be gotten across by distinguishing "functions given by a rule" from "arbitrary functions". I agree that this language does not nail down the distinction in full detail. --Trovatore (talk) 20:39, 6 January 2018 (UTC)
As everyone here knows, it just opens another can of worms to try to say much about functions "determined by rules" in that sense (cf. definable real number). It's certainly not worth spending a large amount of space in the lede section here about it. I think the current text conveys the point that the example is supposed to convey. — Carl (CBM · talk) 21:40, 6 January 2018 (UTC)
At the same time, there should really be a lower section on definable choice, as in L, and on some rigorous results about the definability of choice functions. — Carl (CBM · talk) 21:55, 6 January 2018 (UTC)

CBM, I have reintroduced "illustrating that the axiom of choice says that a choice function does exist, even if it is not defined by any rule". And also added " In that case, the axiom of choice must be invoked." to the real numbers example. Else, the text does not clearly and explicitly convey "the point that the example is supposed to convey". Trovatore's other formulation concerning the Russell example is perhaps better: "AC guarantees you that a choice function exists, but not that a definable one exists." CBM's fear of opening a can of worms is not relevant. Here, pedagogical clarity is the prime purpose (helping the reader to understand what this is all about), not mathematical precision. By the way, the Russell example is deeply infected with 'worm boxes' anyhow: CBM says that the example is not outside set theory. I was not aware that socks were defined in set theory. Nor was I aware of the physical possibility of infinite sets of pairs of socks that are indistinguishable, even in time and space (except in black holes ... where there is no socks ;-))! Bjerke (talk) 05:28, 8 January 2018 (UTC)

Why do you keep bringing up physics? Physics is irrelevant. These aren't physical socks and shoes; they're Platonic ideal ones, as should be obvious to the reader, and to you. --Trovatore (talk) 05:31, 8 January 2018 (UTC)
I have re-removed the "rule" sentence. The choice function is itself a rule for making the choices - that is the entire point of the axiom of choice, which is to provide the function which gives us the rule. But separately the choice function might be definable, just not by some formula that we expected. For example, it can happen in ZFC that every set is definable, including the choice function on nonempty sets of reals. — Carl (CBM · talk) 11:32, 8 January 2018 (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)

Images at top[edit]

I like the new one, but it has the same technical problem as the old one. Take the colored item. No choice axiom needed for that. -- YohanN7 (talk · contribs) 10:11, 5 April 2017‎ (UTC)

Number of disjoint parts of a group cannot exceed the number of elements of the group itself[edit]

https://mathoverflow.net/questions/22927/why-worry-about-the-axiom-of-choice/22935#22935

Is it true? If so, it would be nice if someone add something about it in the article, something like "The number of disjoint parts of a group cannot exceed the number of elements of the group itself" in the "equivalents" section, and if necessary add a citation and/or a explanation.

To me, a physicist student that only read set theory issues on small articles in the internet, this affimation (even with the explanation in the commentaries below) doesn't sounds like an obvious truth... Haran (talk) 18:14, 20 February 2018 (UTC)

  1. We need either a reference to a reliable source or a proof.
  2. You need to be more careful with your language. I think you mean "set" rather than "group" (as in group theory). And I think you mean the equivalence classes (or parts) in a partition rather than parts (arbitrary subsets, as in a member of the power set). The linked message at mathoverflow.net is not sufficiently clear either. JRSpriggs (talk) 03:59, 2 March 2018 (UTC)
Thank you. The message is not clear to me either, but I understand very few things about this matter... Given that it receveid so many likes there, I thought it was clear enought for sets theorists to check its validity... And, if it was true, turn it in a encyclopedic statement (with the necessaries explanations, sources, etc).... Well, given your answer, probabily it's indeed not so clear at all. Haran (talk) 14:48, 2 March 2018 (UTC)