Talk:Axiom of choice

(Rated B-class, Top-importance)

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

Axiom of choice has been listed as a level-4 vital article in Mathematics. If you can improve it, please do. This article has been rated as B-Class.

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)

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 (talk • contribs) 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 (talk • contribs) 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:

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.
Exactly.
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)
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 (talk • contribs) 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 (talk • contribs) 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 (talk • contribs) 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)

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)

We need either a reference to a reliable source or a proof.
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)

Cartesian Product[edit]

The page says that the Axiom of choice is equivalent to the Cartesian Product of two sets existing. This does not seem to be the case, since forming a subset of the Cartesian Product seems to be the controversial (relative to intuition) point. That the subset can be formed, given the Cartesian Product, may be guaranteed by the Axiom schema of specification from standard ZF theory, but since people reading this article may not be experts on this (or since the steps in mathematical reasoning should be clear), it seems as this point could be emphasized or clarified. (Or correct me if I'm wrong) — Preceding unsigned comment added by 24.52.124.254 (talk) 14:27, 1 October 2018 (UTC)

You are misreading the article. The axiom of choice is equivalent to the non-emptiness of Cartesian products of infinitely many (NOT JUST TWO) non-empty sets. JRSpriggs (talk) 02:28, 2 October 2018 (UTC)

Okay, but do you agree that there is a gap in the mention of the Cartesian Product, to then actual examples? The given example was {{4,5,6}, {10,12}, {1,400,617,8000}}, and then it immediately jumps to the chosen set {4,10,1}, with no explanation of how a Cartesian product could possibly apply.

To remove the gap, it seems you'd point out that the Cartesian product of these sets includes 24 elements, like (4,10,1), (6,12,8000), (5, 10, 617), etc., and that one of these elements, (4,10,1), has been picked out, and then rendered as a non-ordered set, {4,10,1}.

It also seems to a non-expert that being able to "pick out" an element of an existing infinite set might be as difficult as establishing the infinite set exists at all.

The Cartesian product is the set of all possible choice functions. Does that clarify things? That is essentially its definition, although the phrase "choice function" is not usually used in the definition.

Constructing choice functions is easy, if the given set of non-empty sets is finite. The problem is that making an infinite number of choices arbitrarily would require an infinite amount of time which we do not have. Choosing a systematic method of making choices is something which we could do, IF such a systematic method exists.

In any case, once a single choice function is obtained, one can make many others by modifying the value of the function wherever. JRSpriggs (talk) 21:56, 30 October 2018 (UTC)

Axiom of non-choice[edit]

"Redirected from Axiom of non-choice"... however, "non-choice" does not appear anywhere in the article. DAVilla (talk) 21:17, 22 June 2019 (UTC)

~~No one uses "axiom of non-choice" as far as I know. So what should it redirect to?~~

~~This article has a section on Axiom of choice#Stronger forms of the negation of AC which is probably as close as one can get to that.~~ JRSpriggs (talk) 08:21, 23 June 2019 (UTC)

Should the redirect Axiom of non-choice be deleted? Or perhaps be turned back into an article (Old revision of Axiom of non-choice)? – Tea2min (talk) 09:14, 23 June 2019 (UTC)

If I understood JRSpriggs right, the text of the Old revision should be included in Axiom of choice. I agree with that; the redirect should then go to the new subsection. However, shouldn't that be part of section Axiom of choice#Weaker forms, since AC implies ANC, but not vice versa? - Jochen Burghardt (talk) 20:22, 23 June 2019 (UTC)

Until I read the later comments, I did not realize that this redirect had previously been an article. After reading that article, I changed the redirect back into the article and added a line about this being a theorem in classical ZF. Please excuse my ignorance of constructive set theory.

I would not merge that article into this one because this one is about classical set theory, not constructive set theory. But we could add a link to it. JRSpriggs (talk) 01:21, 24 June 2019 (UTC)

Actually, I think that "axiom of non-choice" is a misleading name for that theorem. (1) It is not an axiom in classical set theory. (2) It is not denying choice, but merely avoiding using it. JRSpriggs (talk) 01:32, 24 June 2019 (UTC)

Ok for me. I'd also appreciate if you'd add a link (e.g. a sentence in section Axiom of choice#In constructive mathematics, including your above remarks about the name). - If you have a source available confirming the provability in ZF, could you add it at Axiom of non-choice? I see that the replacement axiom easily matches the "non-choice" axiom, but I don't see immediately the latter's proof from that. - Jochen Burghardt (talk) 10:24, 24 June 2019 (UTC)

I think the simple path here is just to delete the redirect, unless this is a term that's actually used in the wild. Such redirects are "mostly harmless", but not completely; it has some potential to mislead people into thinking the "axiom of non-choice" is some particular thing (especially if someone links to it), and it's spawning noise in this talk page. --Trovatore (talk) 18:28, 24 June 2019 (UTC)

Oh, I didn't see that this is now apparently an article. Is that term really used? I have some familiarity with that milieu but not an awful lot. --Trovatore (talk) 18:29, 24 June 2019 (UTC)

anhducwiki

Saturday, February 29, 2020