Jump to content

Talk:Axiom of choice/Archive 5

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Archive 1Archive 3Archive 4Archive 5Archive 6

Non-controversial?

"Although originally controversial, it is now used without reservation by most mathematicians.[2]"

I think this statement requires qualification and gives much too rosy a picture of attitudes towards AC. In the first place, I suspect the statement is only true by default - a lot of the use of AC by mathematicians is probably subconscious rather than deliberate. In the second place I imagine many mathematicians prefer to avoid thinking about the matter too much. Thirdly, I think this axiom is of interest to a lot of people who are not mathematicians (e.g. computer scientists or logicians), and that for many of them it remains controversial.

How about something like . "Although it is used either without reservation, or even as a hidden assumption, by most mathematicians, the axiom of choice or the alternatives to it continue to provoke debate and research.".

Or even just

"Although controversial, it is used without reservation by most mathematicians."

or

"Although it is used without reservation by most mathematicians, it can be used to prove results which are controversial."

Or simply remove this sentence and delay discussion of the debate about this axiom to later in the article. (HugoBarnaby (talk) 11:14, 8 September 2010 (UTC))

We do have two references for that sentence: Jech (a classical set theorist) and Martin-Lof (an intuitionist). Here is the relevant quote from Martin-Lof:
Despite the strength of the initial opposition against it, Zermelo’s axiom of choice gradually came to be accepted mainly because it was needed at an early stage in the development of several branches of mathematics, not only set theory, but also topology, algebra and functional analysis, for example. Towards the end of the thirties, it had become firmly established and was made part of the standard mathematical curriculum in the form of Zorn’s lemma.
I will be able to look up Jech's comments when I am in the office later.
In any case, I don't think it would be right to claim that AC is still controversial. Sure, some people still remark about how "surprising" or "unintuitive" the axiom is. But the state of affairs in mathematics is that the axiom of choice is completely mainstream, and it's taught to mathematics majors as an accepted axiom of mathematics (for example, when they prove that every field has an algebraic closure). — Carl (CBM · talk) 11:47, 8 September 2010 (UTC)
In fact, "by most mathematicians" is a slightly misleading understatement. Given the misconception exhibited by Hugobarnaby's comment we may have to make this formulation slightly stronger. Hans Adler 16:37, 8 September 2010 (UTC)


First, I think that the claim "a lot of the use of AC by mathematicians is probably subconscious rather than deliberate" implies that the use of AC is in many cases uncontroversial. If nobody is aware of any problems, then nobody disagrees, so there is no controversy.
Second, here is a quote from Andreas Blass, editor of the Set Theory volume of the "Omega-Bibliography of Mathematical Logic". (We might use a part of it in the article.) He writes in the preface to this volume

In retrospect, it appears that the substance of the controversy [...] was that two different concepts had coexisted under the same name "set" until the axiom of choice brought the difference etween them into shaper focus.
  • One concept is that a set consists of objects that share some property and that all sets should therefore be somehow definable. On the basis of this concept, the axiom of choice is most implausible, since there seems to be no way to define the choice functions whose existence the axiom asserts. [...]
  • The other concept is that a set consists of an entirely abitrary collection of objects and need not admit a definition. This second concept and with it the axiom of choice have gained nearly universal acceptance among set theorists. [...] We accept the axiom of choice because, on the basis of what we mean by "set", the axiom is true. [emphasis added]

(I think this is similar to the chance in the concept of a "function". A few centuries ago, the notion of a function was closely related to the then informal notion of an algorithm or a computation. Today, a function is just a special kind of relation.) --Aleph4 (talk) 16:44, 8 September 2010 (UTC)

I don't feel finding isolated references to books which deny AC is controversial is sufficient to prove it is not. I can find references which say that it is just as easily, including what I take to be books by reputable mathematicians on the subject, for example the blurb on the back cover of Horst Herrlich's book entitled "Axiom of Choice" which is published by Springer. I am more than willing to believe that most set theorists accept AC without qualms, and that it is useful, but I think the sheer volume of literature about it and alternatives to it indicates that it is still controversial. —Preceding unsigned comment added by Hugobarnaby (talkcontribs) 15:13, 11 October 2010 (UTC)

Even if you think that the axiom of choice is true in the real world of set theory, you may still be interested in investigating inner models or set models where AC is replaced by something inconsistent with it such as the axiom of determinacy. So the existence of literature about the negation of AC does not necessarily indicate a lack of belief in it. JRSpriggs (talk) 17:29, 11 October 2010 (UTC)

prepositional calculus?

The page Independence (mathematical logic) says "independent of" and "undecidable from". Whichever preposition we use we should be consistent. Tkuvho (talk) 00:16, 5 October 2010 (UTC)

My recollection is that the standard usage is:
  • "Independent of" T
  • "Undecidable from" T
  • "Independent from" the axioms of T.
Arthur Rubin (talk) 01:15, 5 October 2010 (UTC)
The phrase "the axiom of choice is logically independent from the other axioms of Zermelo–Fraenkel set theory (ZF)" is a little odd. Why does it refer to the "other" axioms? AC is not an axiom of ZF. Tkuvho (talk) 01:24, 5 October 2010 (UTC)
"Zermelo–Fraenkel set theory" is ambiguous — sometimes it (ZF) is taken to exclude the axiom of choice, but usually it (ZFC) is taken to include the axiom of choice. That is, it is frequently an abbreviation of "Zermelo–Fraenkel set theory with the axiom of choice" rather than "Zermelo–Fraenkel set theory without the axiom of choice". JRSpriggs (talk) 09:41, 5 October 2010 (UTC)
yes but the "independence" section currently goes with ZF. Tkuvho (talk) 09:55, 5 October 2010 (UTC)
I think that "ZF" is being introduced (to a possibly unfamiliar reader) as an abbreviation of "other axioms of Zermelo–Fraenkel set theory" rather than of "Zermelo–Fraenkel set theory". JRSpriggs (talk) 10:03, 5 October 2010 (UTC)
I have never heard anyone make a distinction between which preposition is used depending on whether its object is T or "the axioms of T". I also can't think of any good reason for such a distinction.
To my ear "of" just sounds better. --Trovatore (talk) 10:08, 5 October 2010 (UTC)
+1.—Emil J. 10:42, 5 October 2010 (UTC)

Unclear

Does anyone else find the introduction confusing? I feel like a slight rewording could go a long way. Or using formulas like in the German version. -Keith (Hypergeek14)Talk 12:29, 11 October 2010 (UTC)

Currently there are no formulas in the article. Which is somewhat surprising to me, but probably makes it easier to read for most people. If you want formulas, here they are:
asserts the existence of a choice function for a collection of nonempty sets; and
asserts the existence of a set which collects one element from each of a collection of disjoint nonempty sets. Notice that even these formulas would require some further expansion to be strictly in the language of set theory.
If anyone wants to put these into the article, be my guest. JRSpriggs (talk) 18:21, 11 October 2010 (UTC)
They might be a useful addition, but i think the kind of formula he had in mind is an explicit example of a choice function in a case of a (small) finite collection of (small) finite sets. Of course, AC is not required here, but it's a concrete elementary illustration of the notion of a choice function. Tkuvho (talk) 20:09, 11 October 2010 (UTC)
That might be a good idea for the article on choice functions rather than this article. JRSpriggs (talk) 06:26, 12 October 2010 (UTC)

Does Wikipedia keep statistics on the number of hits on specific pages? Today's (Wed, Oct 11, 2010) XKCD strip references this topic. It would be interesting to see if there's an increase in traffic to this page. Pottersson (talk) 14:30, 11 October 2010 (UTC)

Similarly, this article is super confusing. Can someone explain today's xkcd strip based on this? —Preceding unsigned comment added by 216.186.52.213 (talk) 14:58, 11 October 2010 (UTC)

It's a reference to the Banach–Tarski paradox, which relies on the axiom of choice.—Emil J. 15:01, 11 October 2010 (UTC)
It's actually a nontrivial extension of Banach-Tarski to gourds, I expect it has been submitted to Journal of Symbolic Logic. Tkuvho (talk) 20:11, 11 October 2010 (UTC)
IIRC there is an extension of Banach–Tarski which states that any two bounded subsets of R3 with nonempty interior are equidecomposable, which means that the case of pumpkins is already covered.—Emil J. 11:01, 12 October 2010 (UTC)
It's even mentioned in the article, in fact, Banach and Tarski already proved it in this form in the original paper.—Emil J. 11:59, 12 October 2010 (UTC)
OK, that explains why axiom of choice was viewed by 40 thousand viewers yesterday :) Tkuvho (talk) 13:51, 12 October 2010 (UTC)

Pick the left sock ?

Nope, I don't get this either ! If you wear your socks for a few days before putting them in the bins, you could certainly pick out the left ones ! I'll try reading it again.

I suspect the word 'require' is being used in a special sense ?

--195.137.93.171 (talk) 03:34, 13 October 2010 (UTC)

Maybe 'rule' and 'select/specify' need redefinition, too !
I give up !
Yes, XKCD is trying to re-awaken my ageing brain-cells, too !
--195.137.93.171 (talk) 03:43, 13 October 2010 (UTC)
wearing infinitely many pairs of socks simultaneously would require an even stronger foundational commitment than AC. It may be the theme of the next XK. Tkuvho (talk) 04:28, 13 October 2010 (UTC)
Please keep in mind that the shoes-and-socks metaphor is not meant to be an accurate description of a physical, real-world situation. The implicit assumption is that left and right shoes are distinguishable while left and right socks are not. A pair of shoes represents a mathematical set that has an a priori distinguished element, while a pair of socks represents a set in which no particular element is distinguished from any other. The axiom of choice is not a statement about actual shoes and actual socks. —Bkell (talk) 13:49, 13 October 2010 (UTC)
No point telling us here - put it in a note in the article. --Michael C. Price talk 10:27, 20 October 2010 (UTC)

ultrafilter axiom

The existence of an ultrafilter is weaker than AC. I can't seem to find it here. Tkuvho (talk) 08:56, 20 October 2010 (UTC)

Make that a nonprincipal ultrafilter. The existence of a principal ultrafilter on any nonempty set can be proved in ZF alone. JRSpriggs (talk) 09:13, 20 October 2010 (UTC)
OK. Would it be appropriate to mention it here? I am out of my depth in set theory. Tkuvho (talk) 09:41, 20 October 2010 (UTC)
Ultrafilter lemma. — Carl (CBM · talk) 11:19, 20 October 2010 (UTC)
Notice that the section Axiom of choice#Weaker forms already says "Other choice axioms weaker than axiom of choice include the Boolean prime ideal theorem and the axiom of uniformization. The former is equivalent in ZF to the existence of an ultrafilter containing each given filter, proved by Tarski in 1930." in its second paragraph (emphasis added). JRSpriggs (talk) 18:59, 20 October 2010 (UTC)
Good call. I just added it in :) Tkuvho (talk) 19:04, 20 October 2010 (UTC)
Sorry, I should have looked at the edit history before I spoke. Thanks for adding it. JRSpriggs (talk) 19:07, 20 October 2010 (UTC)

Application in physics?

Is there any examples of use in physics? In quantum mechanics, nature appears to have the ability to choose without reason, a.k.a. collapse of the wave function - with or without creating a piece of information. To me, it sounds somewhat related. —Preceding unsigned comment added by 81.216.218.158 (talk) 23:29, 24 October 2010 (UTC)

I cannot imagine any way that the axiom of choice or its negation could affect physics, since any mathematical model of physics should have an isomorphic copy within the constructible universe where the axiom of choice always holds.
In the many-worlds interpretation of quantum mechanics, there is no actual collapse of the wave function and thus no arbitrary "choice" of an experimental outcome. Rather interaction between the system and the outside world (including the observer) creates a quantum entanglement (correlation) between their states. The establishment of this correlation is perceived by the observer as the collapse of the wave function of the system. However, no actual choice is made as both outcomes continue to exist as components of the universal wave function. JRSpriggs (talk) 05:33, 25 October 2010 (UTC)
Why should any mathematical model of physics have an isomorphic copy within the constructible universe? What would you do, for example, if such a model exploits the Hahn-Banach theorem, as is frequently done in quantum physics? Tkuvho (talk) 08:58, 25 October 2010 (UTC)

Rubin & Rubin

I appreciate the addition of my parents' book, but there are two of them:

  1. Equivalents of the Axiom of Choice (North Holland, 1963)
    • Apparently reissued as (Elsevier, April 1970) ISBN-10 0720422256
  2. Equivalents of the Axiom of Choice II (North Holland/Elsevier, July 1985), ISBN-10 0444877088

Arthur Rubin (talk) 06:27, 12 January 2011 (UTC)

(My personal copies say "North Holland", Amazon.com has Elsevier). — Arthur Rubin (talk) 06:45, 12 January 2011 (UTC)

Finite sets

The axiom of choice for finite sets can indeed be proved by induction, using the predicate

P(n) : every finite set with n members, each of whose members is nonempty, has a choice function.

The inductive prof is straightforward: given a set with n+1 members you throw one out, make a choice function for the rest, and then change the function to account for the remaining member. This does not prove countable choice in any way.

There are two reasons that this is better than trying to make a conjunction of formulas and then applying logic. First, less important, few people other than logicians are familiar with formulas, but many people are familiar with induction.

More importantly, using formulas limits us to sets that are externally finite, while the induction proof works for sets that are internally finite. That is: the induction proof shows that every model of ZFC satisfies choice for finite sets, even if that model is ω-nonstandard and has "finite" sets that are not actually finite. For these sets, you can't use the "conjunction" method, because from the metatheory those sets are infinite, and a formula can't have an infinite conjunction. However, because any model of ZFC satisfies all instances of induction, including the one for P above, the model will satisfy the axiom of choice for every set that the model thinks is finite. — Carl (CBM · talk) 12:25, 18 February 2011 (UTC)

OK I stand corrected (but I'm sure you mean ZF when you say ZFC). Still I think my confusion is natural, and the article might address the issue in some way. Compare with the way one proves that (say) any recurrence relation plus initial terms defines a unique infinite sequence: prove by induction that for any finite number of initial terms there is a unique solution, and then define the infinite sequence as the limit of those finite ones. The reason this does not work for choice functions is subtle, and might be highlighted. Marc van Leeuwen (talk) 16:56, 28 February 2011 (UTC)
I agree, and I added a couple sentences to the article. This issue has historically been hard to write about because different editors here prefer different metaphors for why the limiting choice function doesn't have to exist. Please edit my text to make it better. — Carl (CBM · talk) 22:11, 28 February 2011 (UTC)
If X is a countable set of nonempty sets, then from ZF alone one can show that every finite subset of X has a choice function. But this is not the same as giving a distinguished choice function for each finite set. Having such a distinguished choice function for each finite subset would allow one to construct a choice function for X as a whole. (Just choose the element of Xn chosen by the distinguished choice function for {Xk|kn}.) Generally, there are multiple choice functions for (most) finite subsets of X; and choosing one of them to be the distinguished one requires (tah dah) the axiom of choice. JRSpriggs (talk) 07:05, 1 March 2011 (UTC)
Right; the problem is that the is no uniform way, in general, to form the finite choice functions. There are two difficulties adding this to the article. First, the paragraph it's in is already a side comment, and to explain the issue for finite sets we'll need to rearrange things. That can be done. The second problem is word choice. I don't like "distinguished" because the problem is not having a distinguished function for each n; we could declare that the one we constructed to be distinguished, after all. We could even add a constant to the language for each of the finite choice functions, making a definitional expansion of the model, and then the choice functions would each be definable in the expansion. I see the problem as the lack of a (simultaneous, uniform) sequence of distinguished choice functions. So the problem is not with making an infinite number of choices, but with making them simultaneously. The lede of the article is also a little vague about that, as well. — Carl (CBM · talk) 11:44, 1 March 2011 (UTC)

Followup on the finite question. The lead says:

In many cases such a selection can be made without invoking the axiom of choice; this is in particular the case if the number of bins is finite .... for an infinite collection of pairs of socks (assumed to have no distinguishing features), such a selection can only be obtained by invoking the axiom of choice.

But this example implies a similar problem would exist for a finite number of socks? How would you choose a sock from a single pair? -- cheers, Michael C. Price talk 04:50, 25 July 2011 (UTC)

See List of rules of inference#Rules of classical predicate calculus, specifically the rule of existential elimination. Saying that an element exists in a set means that you can choose one of them. Just reach in the bin and pull out a sock. JRSpriggs (talk) 07:05, 25 July 2011 (UTC)
I basically agree with that, but the "reach in the bin and pull out a sock" is not illuminating; the same kind of phrase could be applied to infinitely many pairs (just do it for every pair, independently and simultaneously) where the conclusion would not be justified (without axiom of choice). The crucial point to understand is that for a singleton family, the conclusion of the axiom of choice is almost trivially equivalent to its hypothesis: the conclusion does not hand you a choice function, but just says that one exists, the hypothesis says that an element exists, and having an element or a choice function is essentially the same thing. The existential elimination rule says that the way an existential proposition ∃x φ(x) can be used is to combine it with a proof a φ(b)→ψ with b not occurring in ψ to obtain a proof of ψ. If ψ is "there exists a choice function for the pair" and φ(x) is "x is an element of the pair", then from φ(b) one easily deduces ψ (take the choice function that chooses b and do existential introduction), and combining with the hypothesis ∃x φ(x) "the pair is not empty" one has a proof of ψ. Nothing is actually ever chosen in the proof. Marc van Leeuwen (talk) 16:13, 25 July 2011 (UTC)
I got lost in your answer, but at least you understood why the "reach in the bin and pull out a sock" is not illuminating. Thanks! -- cheers, Michael C. Price talk 16:36, 25 July 2011 (UTC)
The conclusion is justified by the argument, but what that shows is that the axiom of choice is true. It doesn't show you how to derive it from the other axioms. That is, the "sock" argument is correct, but can't be formalized in ZF alone. It does take an argument to see why finite AC can be so formalized. --Trovatore (talk) 18:36, 25 July 2011 (UTC)
If you say the axiom is true then I don't know what you mean by "axiom" and/or "true". I thought the whole point about axioms was that you could accept their negations as valid as well. -- cheers, Michael C. Price talk 21:48, 25 July 2011 (UTC)
Depends on what you mean by valid. Formally, you can add the negation of AC to ZF, and you get a consistent theory, that is one that does not prove 0=1. If you're what Maddy calls a "glib formalist", maybe you'll claim that's all you want, but if the point is analyzed more closely you'll find out that it's not really all you want, even if you think it is.
If on the other hand you have an interpretation in mind, then you are not free to add axioms simply because they don't enable the theory to prove 0=1. You may add only axioms that are true in the intended interpretation.
(That's not to say that axioms that are false in the intended interpretation are useless. They might be true in some other interesting interpretation, as for example ~AC is true in the model L(R).) --Trovatore (talk) 01:11, 26 July 2011 (UTC)

Here is a proof for n=2.

  • hypothesis
    • hypothesis
      • quantifier
        • hypothesis
          • quantifier
            • hypothesis
            • pairing
            • pairing
            • pairing
            • pairing
            • pairing
            • pairing
            • pairing
            • There is a choice function for
        • deduction & generalization
        • existence elimination
    • deduction & generalization
    • existence elimination

deduction & deduction
QED JRSpriggs (talk) 18:20, 26 July 2011 (UTC)

This article is in bad shape

The lede tentatively introduces the Axiom of Choice (AC), then proceeds to show that AC isn't necessary every day. It's as if the axiom is a suspect of crime in the first place. Yes, I do get that impression from the article. The rest of the article goes on in much of the same manner. (We don't need AC if ..., anything AC proves is not really to be trusted...) Any beginner might get the idea that AC is under serious doubt.

My opinion is that the possible philosophical shortcomings of AC - including any of such things as "objects that AC proves exist can't be described" and the behavior of "extremely complicated subsets of the reals (that AC proves to exist but doesn't describe)" - should get a separate article within this category.

This article should be about AC (and perhaps not AC) and its use and its implications and nothing else except links. The "usage" section in the present article is devoted completely to the question of avoiding AC concluding that we can't. If the "questionable" aspects of AC are to remain here I think that some of the consequences of not AC should be here as well. They are a lot more convincing (against themselves) than the "paradoxes" AC itself produces.YohanN7 (talk) 21:34, 6 April 2011 (UTC)

Axiom's are of course never suspect of crime, but the axiom of choice does have a special aspect to it, which causes a qualitative difference between results that can be proved without it and those that cannot (but can be proved using it). Logicians distinguish the Zermelo-Fränkel axioms (ZF) of set theory from Zermelo-Fränkel with the axiom of Choice added (ZFC) to make this distinction explicit; they do not similarly single out other axioms of set theory. The axiom of choice has a form that suggests it might be a theorem of set theory, and people originally thought results (now known to be) equivalent to the axiom of choice could be proved by ordinary logic, without requiring any axiom. We now know that is not true (because the axiom of choice is provably independent of ZF), and these results can only be obtained if one does assume the axiom of choice; since they are equivalent to the axiom, this more or less amounts to assuming the result itself (albeit in a different form). So there is a qualitative difference between "this result is a consequence of basic set theory" (ZF) and "one may safely assume this result to be true" (it won't lead to contradictions, unless set theory should already be contradictory without assuming it).
As for consequences of not AC, these are basically the negations of the properties listed that are equivalent to AC, and of those that are stronger. Whether one considers those shocking is a matter of taste. That not every vector space should have a basis would not disturb me particularly, especially since there are lots of vector spaces where it is clear that specifying a basis is beyond our means anyway (the space of all infinite sequences for instance, or R as a vector space over Q; I suppose though that "not AC" does not imply that these spaces have no basis). That there should be infinite families of non-empty sets whose product is empty appears strange, but this is related to the somewhat mysterious nature of being "non-empty" (at least, I think it does not mean one has an element of the set, but just that any result that can be proved using an arbitrary element of the set, without having to know anything more about it, must be true). Marc van Leeuwen (talk) 17:45, 7 April 2011 (UTC)
Thanks for your reply.
Yes it is certainly true that AC is different from the axioms of ZF. The nonconstructive nature of AC must be pointed out. However, I don't think anyone reading this article or some standard text about it would mistake it for a theorem of ZF. Thats not to say that a bright person not familiar with set theory axioms (like the majority if mathematicians before, say, 1900) couldn't mistake it for a theorem or a statement that is true no matter what. That makes AC a good axiom since, as it turned out, AC is independent of and consistent with ZF. B t w, I think logicians distinguish between ZF and ZFC mostly because they must because they aren't the same. Not that AC is that profoundly different from other axioms. I don't know wether large cardinal axioms or things like V = L can be considered constructive in any way (while determinacy-like axioms probably are?).
When it comes to "not AC" then yes, the negation of the statement of AC (or equivalents) does seem strange to me. (I don't quite follow you in your discussion of "non-emty" though.) Nonetheless, empty cartesian products for some collections of sets and non-empty for other collections of sets? Moreover, there would be "holes" in the power set (of the union of some malfunctioning collection) as far as I can see. Would we want to see the set of all realvalued functions of one real variable empty? Probably not. Given "not AC" logicians will have a huge challenge: Construct explicitely a suitable collection of sets whose cartesian product is clearly empty. These are things I personally find quite difficult to digest.
More problematic are the many theorems of ordinary math that follow directly or indirectly from AC. They will fail or be unprovable. The Hamel basis problem is perhaps not that disturbing, but what about Hahn-Banach on which parts of functional analysis rest? Tychonoffs theorem will definitly have to go and along with it many existence theorems in e.g. differential equations.
What I don't like about the article is that the emphasis is where it is today. I'd like to see a much shorter(!) article containing much more about how to use AC in practice. For one thing there could be a sample proof or two of something suitable where a choice function is involved. Why not? The section "usage" today basically repeats the fact that AC isn't needed for finite collections. (Thats in the lede and in it's own section as well.) Suggestion: Let there be one short section (without any proof or at most an outline) about "finite choice". Suggestion: The section "Nonconstructive aspects" can be shortened. Suggestion: The relationship between AC, Zorns lemma and wellordering can be presented in a new section (with skeleton proofs).
Please note too that I don't claim that the article is incorrect. Nor would I want to remove the fact that AC isn't constructive or it's relashionship to ZF. I wouldn't like to see lengthy arguments either for or against AC. If (and only if) there are sections devoted to this they should at least argue something in favor of AC too. After all, AC and not its negation have been taken for granted even before its conception. YohanN7 (talk) 21:14, 7 April 2011 (UTC)
Just a short reply to some points. Yes, not AC means empty Cartesian products for some collections of non-empty sets and non-empty for other collections of sets. Whenever the non-emptyness of the sets in the collection is obtained by having (i.e., being able to specify) an element of each member, then the product must be non-empty. The set of real-valued functions of one real variable is non-empty, this is implied by ZF, because we can specify an element (say 0) of the real numbers, and thus a function (the zero function). However for certain collections of non-empty sets we know their non-emptiness in a way that does not allow us to specify an element of each set. In ZF one cannot deduce from the non-emptiness of each member the non-emptyness of the product. One cannot deduce either the existence of any collection of non-empty sets whose product must be empty, that's why AC is independent of ZF. So assuming not AC would affirm the existence of some such family with empty product, although it would not point out any specific instance. I'm not enough of a logician to know whether one could concoct a family that is a "best candidate" for having empty product, in the sense that if any product is empty (i.e., if not AC), then this one will be. That is the only sense in which the "huge challenge" you mention makes any sense; don't forget that ZF cannot prove either "AC" or "not AC", so assuming "not AC" does not put one into the obligation of then proving it (which is impossible) any more than assuming "AC" does. There is much subtlety to AC, and please make sure you understand it well if you want to contribute to this article (what you say about holes in the power set makes me think you might not quite). I'm not sure I do, so I'm glad to leave this to more qualified people.
I don't think much very constructive can be done with "not AC", and I certainly would not want to work in such a theory. But that does not imply I have to admit AC, I can be perfectly happy assuming neither; in any case it is an illusion to believe we can arrange for any statement to be either provable or disprovable, however many axioms one is willing to admit. Not having Hahn-Banach or Tychonoffs theorem will not make me sleep any worse at night. Just as vegetarians can choose to live without meat and very comfortably so, mathematicians can decide to work without anything that carries the "requires AC" label; one has to be more modest and refrain from making certain sweeping statements and claiming they are proven, but whatever remains does have an additional quality to it. Personally I can live with knowing both types of statements, but I do care about the "requires AC" distinction. And more so than for any other axiom of set theory, because those more or less define what set theory is about, which (for me) cannot be said about AC. Marc van Leeuwen (talk) 07:44, 8 April 2011 (UTC)
This is not really the place to argue foundational philosophy, so I'll confine myself to noting that yours is wrong :-). It is, on the other hand, the place to discuss the article, and looking at the text in question, I was struck again by the error in this paragraph:
Until the late 19th century, the axiom of choice was often used implicitly, although it had not yet been formally stated. For example, after having established that the set X contains only non-empty sets, a mathematician might have said "let F(s) be one of the members of s for all s in X." In general, it is impossible to prove that F exists without the axiom of choice, but this seems to have gone unnoticed until Zermelo.
There is something of value here that should probably be preserved, which is why I don't simply delete it. Taken literally, though, it's simply nonsense. To say that something cannot be proved without a given axiom, you need to be assuming an axiomatic paradigm for proof in the first place. But the proofs in question were specifically not axiomatic; they were informal, though valid, methods of reasoning.
Not sure yet how to fix it, but the current text is not acceptable in my opinion. --Trovatore (talk) 08:48, 8 April 2011 (UTC)
It was not my intent to discuss foundational philosophy in the first place. Let me rephrase things a bit.
This is a good article with too much emphasis on the nonconstructive nature of AC.
What about my suggestions below for the article?
I'd like to see a much shorter(!) article containing much more about how to use AC in practice. For one thing there could be a sample proof or two of something suitable where a choice function is involved. Why not? The section "usage" today basically repeats the fact that AC isn't needed for finite collections. (Thats in the lede and in it's own section as well.) Suggestion: Let there be one short section (without any proof or at most an outline) about "finite choice". Suggestion: The section "Nonconstructive aspects" can be shortened. Suggestion: The relationship between AC, Zorns lemma and wellordering can be presented in a new section (with skeleton proofs).YohanN7 (talk) 09:55, 8 April 2011 (UTC)
I don't think it will be easy to find good examples for when to use the axiom of choice. In my experience statements that need it are invariably broad sweeping statements of which concrete instances that are of practical use can be proved without using the axiom of choice. For instance, for every vector space that you will actually want to use a basis for, the existence of such a basis will not depend on AC (unless you are trying to do curious things like define a nonzero Q-linear function RQ). But I would certainly appreciate suggestions. Marc van Leeuwen (talk) 12:32, 8 April 2011 (UTC)
Zorns lemma, the wellordering theorem and a set is infinite iff it has a bijection with an infinite subset and existence of right inverses of surjective functions are examples where one must or can use AC directly. Yes, they are broad statements. But they are true nonetheless. The article is full of mentions of such examples that could be expanded.YohanN7 (talk) 14:13, 8 April 2011 (UTC)

Between Cantor and Zermelo: this article is in good shape

The few decades between the introduction of set theory on the one hand, and Zermelo's identification of a "missing" foundational axiom, on the other, mathematicians may have used arguments relying on choice while thinking they are working in a set-theoretic framework. Of course, the most interesting scenario would be if we could actually source such an occurrence. Tkuvho (talk) 09:01, 8 April 2011 (UTC)

I don't understand what distinction you are making. How are arguments that rely on choice not part of a set-theoretic framework? In the motivating picture for set theory, choice is obviously true. --Trovatore (talk) 09:19, 8 April 2011 (UTC)
What I am saying that an argument by a mathematician who is in principle working in a set-theoretic framework, once such a framework had been established by Cantor and Co., can be legitimately described as containing a gap if such an argument implicitly relies on the axiom of choice. I agree that before the creation of set theory, formulating such a reproach is ahistorical. Tkuvho (talk) 09:22, 8 April 2011 (UTC)
Would you say the same thing if it implicitly relies on, say, the axiom of replacement? --Trovatore (talk) 09:29, 8 April 2011 (UTC)
That would depend on whether you can cite a consequence of the axiom of replacement that's as paradoxical as Banach-Tarski. Tkuvho (talk) 18:26, 9 April 2011 (UTC)
Well, Banach–Tarski is certainly surprising on its face, but once you come to terms with how strange the "pieces" are, it doesn't seem so impossible anymore. I really don't see that as a strong intuitive counterposition to the extremely strong intuitive motivation for AC. --Trovatore (talk) 18:44, 9 April 2011 (UTC)
Are we in agreement then that the axiom of replacement does not have the same type of paradoxical consequences as AC? This would lend support to treating AC as one would treat any hidden assumption or hidden lemma. Cauchy's work in analysis is sometimes said to rely on a hidden assumption of uniform continuity. Let's assume for the sake of the argument that we find a paper by Dedekind from the 1890s which implicitly relies upon AC. In other words, a naive set-theoretic framework had already been formulated by then, and presumably Dedekind is pleased with it (he has had numerous contacts with Cantor). I don't see why we can talk about hidden lemmas in Cauchy but not hidden lemmas in Dedekind. Can one seriously claim that they were doing "informal mathematics" and therefore it is ahistorical to detect hidden lemmas? Tkuvho (talk) 19:44, 9 April 2011 (UTC)
Hmm? I thought I was reasonably clear. To be explicit, Banach–Tarski is surprising at first, but not to the extent of casting any doubt on AC, or giving it any special status. --Trovatore (talk) 19:49, 9 April 2011 (UTC)
That only responded to the first part. To respond to the rest of it, on the face of it it's nonsense to talk about a Dedekind paper that implicitly relies on AC. The correct way to phrase it is, if you want to formalize the proof in an axiomatic framework, you can't do it with just ZF. --Trovatore (talk) 19:54, 9 April 2011 (UTC)
Did you ever read the exchange of letters at the end of Stan Wagoner's book? I hope I got the right book; otherwise it's the "axiom of choice" book. At any rate there was a lot of soul-searching at the beginning of 20th century in connection with AC, including Borel and others. I think many people give it special status. This does not mean I don't like it; on the contrary, I do. Go construct the hyperreals without it :) But the paradox is still there. There is a mismatch between a useful formalism on the one hand, and whatever "reality" it is trying to describe, on the other. The mismatch cannot be swept under the rug. Tkuvho (talk) 20:00, 9 April 2011 (UTC)
The text as it exists is still problematic. Pre-ZF, it was impossible to "notice" that AC was "needed" in these proofs, because there was no demarcation of what means of reasoning did not use AC. I'm not trying to "sweep anything under the rug", I'm just saying that the current language is not correct. --Trovatore (talk) 20:07, 9 April 2011 (UTC)
I agree. Incidentally, are you familiar with a use of AC in Cantor? He himself might have used it in one of his constructions. What about the equicardinality of R and R^n? Is it used there? Also, the author's name is Stan Wagon (not wagoner). Tkuvho (talk) 06:12, 10 April 2011 (UTC)

Not being a mathematician, I'm confused..

Next we might try specifying the least element from each set. But some subsets of the real numbers do not have least elements. For example, the open interval (0,1) does not have a least element: if x is in (0,1), then so is x/2, and x/2 is always strictly smaller than x. So this attempt also fails."

It seems to me that if one is looking at sets of real open intervals, then one can specifying the first interval eg (a, b), and then specify the element a+(b-a)/2 within that interval which always is a unique value lying within that interval, obviating AC. Now, I'm sure that there are non-solutions for doing something like that in all cases, but the article doesn't appear to explain what the problem is. (20040302 (talk))

The sentence is just trying to give a simple example that taking the least element is not a general solution to select an element from any non-empty set of real numbers. If you have a collection of non-empty real intervals, then one does not need the axiom of choice to define a choice function, as your argument shows. But if you try to see what happens when for instance applying the general proof, using Zorn's lemma, that all vector spaces have a basis, to the particular case of the real numbers as vector space over the rational numbers, then one quickly runs into very complicated sets of real numbers: typically one needs to select a number that is not a rational linear combination of all previously chosen numbers, where that set of previously chosen numbers can itself be uncountably large (but does not for instance contain any interval of positive length). Such sets from which to choose from are very hard to imagine, and certainly no simple procedure will be able to pinpoint a particular element in them. Marc van Leeuwen (talk) 13:26, 16 April 2011 (UTC)
The best "explanation" for what the problem is would be to look at an example. Consider for instance the unit circle S, and the action on S by a group G consisting of all rational rotations. Namely, these are rotations by angles which are rational multiples of π. Here G is countable while S is uncountable. Hence S breaks up into uncountably many orbits under G. Using the axiom of choice, would could pick a single point from each orbit, obtaining an uncountable subset X of S with the property that all of its translates by G are disjoint from X. In other words, the circle gets partitioned into a countable collection of disjoint sets, which are all pairwise congruent. Now it is easy to convince oneself that the set X could not possibly be measurable, with any reasonable notion of measure. Hence one couldn't expect to find an algorithm to find a point in each orbit, without using the axiom of choice. This is hopefully a more illuminating example than the collection of open intervals. Tkuvho (talk) 18:28, 16 April 2011 (UTC)
Both of you, thanks - I now get that the sentence is a specialised example to demonstrate that when using the function least(x) there are cases where least(x) won't work. Marc, your explanation is far more clear to me (sorry Tkuvho., I don't get why a unit circle is uncountable, or how rotations of a unit circle relates to orbits; please don't explain):- I take it that you are saying that the problem is based on the fact(?!) (i don't really speak maths) that there are sets for which any determined function f(a,...) (aka 'simple procedure') doesn't alway guarantee a single/valid result). AC is both new and interesting to me because it appears at first to be intuitive (one can imagine choosing an element from a set, without needing to know how); however, from my CS experience, it ends up feeling counter-intuitive (not knowing how to choose an element, one would not be able to). I don't doubt that AC is useful, of course, and that choosing to use it for some really tricky stuff is a great way of cutting through a gordian knot! (20040302 (talk) 09:45, 17 April 2011 (UTC))
The example of orbits induced by rational rotation group actions is speciously illustrative. Unlike the prior example of open intervals on the reals, these orbits have a closed form rule for unique choice — take the single element with the smallest rotation away from the positive real axis. (The rational orbits example is more akin to the "every left shoe" example.) kraemer (talk) 05:44, 26 May 2011 (UTC)
Each of the orbits is dense in the circle, so you can't choose "the smallest rotation". In fact, it is in principle impossible to pick one "canonically" without using choice, because that would lead to a non-measurable set. So the example with the orbits is similar to the socks, not the shoes. Tkuvho (talk) 06:40, 26 May 2011 (UTC)
You're right — I misunderstood the example. I was considering the orbits induced by a given rational rotation, where the example discusses the orbit of all rational rotations. It's clearly not possible to determine whether two points are in the same orbit using any finite subset of rational rotations (each orbit is dense around any point), so there can't be a canonical element for an orbit. I'm not sure whether it's worth drilling down on that point in the article — it seems clear enough in retrospect. kraemer (talk) 07:35, 28 May 2011 (UTC)

Put first sentence in TeX math notation

As it was written before, the "is an element of" symbol wasn't showing (at least on my Win 7 machine with Firefox), so I put it in Tex math notation with the raw Wikicode as guide. I'm not a mathematician, so it could well be wrong—I invite you to correct it if so.

Fwiw I can't understand even the beginning of this article. Perhaps it's just me, but it seems that an encyclopedia article should be written to help non-experts understand. (My PhD is physics not math, so I'm a non-expert.) JKeck (talk) 19:56, 23 April 2011 (UTC)

I'm not going to do anything about it just at the moment, but this is one time I have to agree that this sort of complaint is justified. AC is easily enough understood that we should be able to explain it to PhD physicists. It may be as simple as deferring the symbolic expression to something other than the first sentence. JKeck, is the second sentence clear enough to you?
The lead has other problems as well — one that jumped out at me is the final sentence, which at this writing says such a selection can only be obtained by invoking the axiom of choice. That doesn't really make sense. The axiom doesn't "obtain" a selection for you, but merely formalizes the intuition that one must exist. Don't have time to work on it right now, I'm afraid. --Trovatore (talk) 20:54, 23 April 2011 (UTC)
Hi JKeck, making math accessible to physicists is one of my constant preoccupations. Could you be more specific in your question? A while ago I added the bit about socks and shoes, does it help? Tkuvho (talk) 05:08, 24 April 2011 (UTC)
First of all I find it disturbing that the "is an element of" symbol wasn't showing up for JKeck, since there seems to be nothing irregular about the way it was entered (looks like it came from the "Math and logic" collection in the roll-down menu from the edit pages, which gives: ∈). If you have this problems you are probably missing loads of symbols in math articles, since this is the privileged way to represent them. You could try to replace the symbol by ∈ giving ∈ (or by clicking on the symbol in Math and logic yourself, which might resolve some coding issue) to see it that works better. TeX code in WP produces images, which avoids such problems but looks bad in in-line formulas (however much the formulas themselves are of superior quality). If this is really a problem of your local installation, the solution cannot be to change the WP articles.
As for problems understanding, I think you really don't need to understand the axiom of choice unless you are a mathematician interested in foundations. In physics you will never come about a situation where a result depends on the axiom of choice, because it talks about provability in set theory, only. Probably the opening sentence should make this clear. For any reasonable collection of non-empty sets one could encounter in real life, a choice function is easily found without use of axioms, and this is the reason that the axiom seems reasonable, but in mathematics it gets applied in highly abstract and complicated situations, where the "real world" justification for the existence of choice functions no longer suffices.
I flat disagree with you, Marc (not for the first time). The intuitive justification is rock-solid, and the axiom of choice is in fact true (and self-evident) in the Platonic "real" (though non-physical) world of sets. Its independence simply means that it cannot be proved, in first-order logic, from a particular specified collection of axioms.
As to whether non-mathematicians "need" to understand the axiom, I don't see that that's really the point. They can understand the axiom, and some of them want to, and no further justification is required. It is simple enough that we should be able to get the point across. --Trovatore (talk) 06:13, 24 April 2011 (UTC)
Proving the existence of solutions of Einstein field equations can involve functional analysis, which routinely relies on the Hahn-Banach theorem and therefore ultimately on non-constructive foundational material such as the axiom of choice. Besides, why would we discourage a physicist from picking up some math? The rectangles bother me as well. I don't know where JKeck is, but I am at a research university and I am getting the rectangles nonetheless. Tex is much better. As far as the "truth" of the axiom of choice, well, I suggest you consult Errett Bishop. Tkuvho (talk) 06:16, 24 April 2011 (UTC)
Bishop did some great stuff. His philosophy was wrong, though. --Trovatore (talk) 06:17, 24 April 2011 (UTC)
Fine, so long as you acknowledge that you are relying on a particular philosophy. Incidentally, in your philosophy, do sets contain standard and nonstandard members? Tkuvho (talk) 06:19, 24 April 2011 (UTC)
No, of course not. A nonstandard integer, for example, can exist only in the context of an impoverished model, one that cannot recognize that the "integer" is in fact infinite, because it lacks the set of all standard integers to compare it with. For certain purposes, of course, existence in the context of such a model is all you need. --Trovatore (talk) 06:26, 24 April 2011 (UTC)
I respect your opinion but, as you probably already know, I disgree with it. Edward Nelson's axiomatics are better suited for scientific needs than the usual ZFC. Had someone proposed something of that nature before Weierstrassian epsilontics took over, we might well be saying today that the true sets in the Platonic world of sets naturally contain infinitesimals, whereas "impoverished models" (as you put it) such as ZFC are simpler but less useful. Tkuvho (talk) 06:29, 24 April 2011 (UTC)
At least keep the language straight. ZFC is not a model. --Trovatore (talk) 06:31, 24 April 2011 (UTC)
From the viewpoint of category theory, specific set-theoretic axiomatisations can be viewed as models. Tkuvho (talk) 07:52, 24 April 2011 (UTC)
I am not a category theorist, but whatever sense of model you mean there, it's not the one I meant when I said that nonstandard integers make sense only in the context of an impoverished model. Axiomatizations are syntactic and models are semantic; you have to keep them well distinguished from one another. What I meant by "impoverished" is not about what axioms it satisfies, but about what objects it contains. --Trovatore (talk) 07:55, 24 April 2011 (UTC)
When comparing the ZFC axiomatisation and the IST axiomatisation, one can't help noticing that the former is impoverished as compared to the latter. Namely, ZFC cannot express certain distinctions that IST can. Tkuvho (talk) 08:03, 24 April 2011 (UTC)
I wasn't talking about comparing axiomatizations. I was talking about comparing models. --Trovatore (talk) 08:04, 24 April 2011 (UTC)
That's precisely my point. If your starting point is ZFC, then of course AC is going to be true, and there is no such thing as nonstandard elements. However, commitment to ZFC is merely a philosophical choice that can be challenged. Tkuvho (talk) 08:10, 24 April 2011 (UTC)
My commitment is not to ZFC. ZFC is a formal system; I'm not a formalist. Yes, I have a philosophical underpinning that you can argue with. Just please give your arguments using standard language. ZFC is not a "model"; if that isn't clear to you, then I can't tell whether my statements regarding nonstandard integers relative to models were clear to you either. --Trovatore (talk) 08:26, 24 April 2011 (UTC)
Again, the ZFC syntax is too poor to express certain useful distinctions that can be captured in IST. Take, for example, an integer H so huge that H cannot be expressed in the total span allocated to our civilisation, even if each member participates in the effort, and exploits all of the elementary particles in our universe. Such an integer is "infinite" for all practical purposes. IST allows one to distuinguish formally between this type of integer and the kind of integers we are familiar with in the kind of calculations (even very large ones) that are performed by our computers. Obviously in ZFC there is no way of formalizing the property of being "huge" in this sense. It is similarly clear that such distinctions are useful in fields ranging from economics and computer science to physics, and can be exploited to formalize large-scale behavior in a way that cannot be done in ZFC. A researcher is, of course, free to use ZFC as a starting point. What I object to is the claim that his starting point is so obvious as to make it "true". Kronecker did not think the axiom of infinity was "true". We have been trained to think that it is. It may be a useful tool, but how could it be "true" in any serious epistemological sense? Tkuvho (talk) 09:56, 24 April 2011 (UTC)
Well I guess there is one point you guys (?) have made more evident then any arguments I could have put forward: that the axiom of choice is for mathematicians interested in foundations (and maybe for philosophers), not for those interested in natural science. I'll ignore the provocation of talking about truth in the Platonic real (though non-physical) world of sets; it is just necessary to change "the" into "a". Also I would like to note that it is not clear from te above whether IST means intuitive set theory or intuitionistic set theory (a rather different ketlle of fish), or something else still. To get back to the subject of this section, somebody mentioned rectangles, but I can't see any. Could you clarify? Marc van Leeuwen (talk) 13:10, 24 April 2011 (UTC)
You can't change "the" into "a". There is a level-by-level canonical isomorphism candidates for the von Neumann universe (up to a given stage). --Trovatore (talk) 19:04, 24 April 2011 (UTC)
To Marc van Leeuwen: Tkuvho thinks highly of internal set theory ("IST" for short). JRSpriggs (talk) 02:16, 25 April 2011 (UTC)
I really shouldn't be here (I am not a mathematician OR a physicist, and the conversation has gone OT), but for whomever said "For any reasonable collection of non-empty sets one could encounter in real life, a choice function is easily found without use of axioms.", I disagree. Likewise, as I said above, although AC appears at first to be intuitive, I don't think it remains intuitive when one deals with areas concerning the boundaries/limits of knowledge. I am totally aware that I may be 'missing the point', but for many sets in the real world there is no ability to know if they are empty or non-empty to start off with (e.g. the set of all future human visits to α Centauri ), and for many of those sets, there would be no easy way of constructing a choice function. Even within sets for which we know are non-empty, I can envisage a difficulty of finding a choice function. For example, choosing a unique URL from the set of all websites that have URLS. The problem is that not all websites have a home page, or a single page, or a means of choosing a page, and many dynamic pages change every time they are visited, and websites change totally over time, and many urls are redirected (and therefore not unique) etc. Maybe there IS a function for such a choice in that particular example, but I am sure that there ARE plenty of 'real world' sets for which a choice function is not easily found whatsoever. As I understand it, AC allows for us to make the assumption without having to demonstrate it, which is useful for 'moving on' from what maybe a totally irrelevant part of the project/challenge at hand. However, and finally, (and this IS an opinion) I feel that any given assertion of 'existence' or 'truth' (along with any assertions that depend upon it) is only meaningful within the very restricted sense of the contexts and conventions that assert that truth value. Therefore, attempting to put any truth value attached to a given set theory onto real life - without providing a context - is both incongruous and meaningless. (20040302 (talk))
A set of physical objects will be discrete. Indeed, if bounded in time and space, it will be finite. So one should be able to say something like "I choose the first instance of this thing to appear on Earth.". JRSpriggs (talk) 04:59, 26 April 2011 (UTC)
Our measurement of time fails under planck time, and our measurement of space fails under planck length. Within general relativity there are problems with such ideas as 'first' or 'last'. Outside of real world physics, there are still real world problems, concerning 'discrete' identity (see the replacement paradox or the sorites paradox) - there are many views regarding regarding objects and their essence. Choice appears to be easy enough, if one is naiive. addendum: Far more simply though, JRSpriggs, your solution depends upon knowledge: In your example, the knowing of which is the first instance of said thing requires knowing (and recording) the history of it, which is not always available or even possible. As I see it, it is this 'knowability' that is one of the bases of AC - we don't know how to choose, but we can imagine that there is a way of choosing, if we were omniscient. In one sense, doesn't AC sort of assert an omnisicent being who does the choosing for us? "We cannot know how to make a choice (or even more, we may know that there are sets for which we cannot make a choice - 'ineffable sets'), but God can do the choosing for us!" -Just teasing! (20040302 (talk))
If you are sophisticated enough, even 1+1=2 is problematic. You can put 1 parent and 1 parent together, and suddenly you have not 2 but 1+1=3 invidivuals! talk about infinite choice! Tkuvho (talk) 12:47, 26 April 2011 (UTC)
Tkuvho, yes, within the constraint of a convention that 1+1 represents something to do with bisexual reproductive causality then there is nothing wrong with that, though not being a mathematician I'm not sure of the relevance. (20040302 (talk))

Plagiarism?

The Quotes section of the article seems to have been copied from "Philosophy Of Mathematics" by John Francis, page 100. (http://books.google.ca/books?id=DuyMjOwWWnUC&lpg=PA100&ots=UenUNN-A_C&dq=computer%20recreations%20column%20of%20the%20Scientific%20American%2C%20April%201989.&pg=PA100#v=onepage&q=wikipedia&f=false) — Preceding unsigned comment added by 137.122.14.20 (talk) 17:16, 10 November 2011 (UTC)

The section in this article pre-dates the book, so any plagiarism was the other way around. JRSpriggs (talk) 07:47, 11 November 2011 (UTC)

Axiom of Choice for Dummies

Does this axiom have any intuitive consequences? I was just trying to cope with the difference between choosing shoes and socks out of bins myself, and looking at phi, x, psi didn't really do it for me. If the socks example isn't illuminating (because who cares if we get a right or a left sock? Or do we?) then how could you change it to make it illuminating? College level knowledge is awesome, but spreading some kind-of knowledge/ appreciation is nice. — Preceding unsigned comment added by J'odore (talkcontribs) 21:54, 26 November 2011 (UTC)

Yes and no. This largely depends on what you mean by "intuitive". AC gives you the ability to order infinitely large collections of things, which is not something human beings ever do or see or measure. This is the realm of pure math. Let me explain the idea here...
Set theory allows us to pair two sets together, to union a set (get the elements of the elements), to get the power set of a set, and to use a formula to define a set that is a subset of some other set. This lets us build a lot of sets, but it doesn't let us build all the things that must be "sets" by our intuitive comprehension of what a "set" is. For example, if we have no formula that identifies a set, we can't prove that set exists or doesn't exist (we can't even describe it). Most infinite sets in set theory are like this, because there are only countably many formulas (which means most sets, even most countable sets, have no formula which describes them, if you're working in an uncountably large model of set theory). They have to "exist", intuitively, but there are too many of them for us to describe precisely. So when we model set theory we can pretend they exist, or pretend they don't exist, and our theory will be essentially the same. These sets are outside the scope of what we can prove mathematically because we're finite beings.
Assuming AC allows proof that certain undefinable sets with certain properties exist. This allows us to prove, for certain X, that "a set with characteristic X exists" even when it is known impossible for us to define an example. For most mathematicians, AC is intuitively "true", even though the results of AC may occasionally be weird and unintuitive. The bigger question is whether AC is "okay to use" because it proves things without providing examples. But Cohen proved that AC is independent of set theory, which means if set theory is consistent, so is set theory + AC, and so is set theory - AC, so it shouldn't matter. As a result, most mathematicians are happy to use AC, but we generally avoid using it when possible because a proof is "stronger" if you don't need to assume AC is true for the proof to work. TricksterWolf (talk) 18:43, 10 April 2012 (UTC)

Clarifying the status of alternatives to AC

This sentence is marked as needing both clarification and citation: "Unlike the axiom of choice, these alternatives are not ordinarily proposed as axioms for mathematics, but only as principles in set theory with interesting consequences." I've tried to at least clarify with: "…not ordinarily proposed as axioms for general use in mathematics, but only as the foundation of alternative set theories with interesting consequences." The idea here is to make it clear that many consider AC acceptable for proofs outside of set theory, whereas other such as AD (deteriminacy) are treated as explorations within set theory. Trovatore: this clearly doesn't imply that AC and AD have equal standing. If this sentence still doesn't meet with your approval, your options are (1) improve or (2) discuss. !melquiades (talk) 04:27, 3 February 2012 (UTC)

See Moschovakis:

(emphasis added) Moschovakis, Yiannis N. (1980). Descriptive Set Theory. North Holland. p. 422. ISBN 0-444-70199-0.

Basically the problem with your text is that axioms are not the foundation of anything — saying that they are is the formalist error. --Trovatore (talk) 05:28, 3 February 2012 (UTC)
I agree with Trovatore that the use of the term "foundation" here is misleading. Perhaps "starting point" was the intended meaning in the first place? Tkuvho (talk) 08:35, 3 February 2012 (UTC)
The idea is that adopting a new axiom leads to a new set theory. ZF+AC = ZFC set theory; similarly, we might call ZF+AD "ZFD set theory." We make the practical and aesthetic — and thus subjective — judgement that ZFC is the one we want to work with in general mathematics, whereas "ZFD" is merely an interesting curiosity. But both systems are, as far as we know, logically consistent formal systems. That's what I meant by "foundation of an alternative set theory." I'll try another edit without the word "foundation" that seems to be causing concern. Trovatore, if it still doesn't meet with your approval, please suggest an improvement. Wikipedia is about building on each other's work, not tearing it down, not blocking fixes. Wikipedia:BRD is meant for situations where "too many people are discussing endlessly." In this case, I think you could expedite things by simply tweaking my wording. !melquiades (talk) 17:49, 3 February 2012 (UTC)
When an edit is disputed, it is reverted and then discussed. This is the normal cycle. It doesn't even have to be because the second editor thinks the new text is worse — just not better. I feel you overreacted to this normal course of action. --Trovatore (talk) 17:56, 3 February 2012 (UTC)
Yes, I did. Sorry. You may have as well. (Check your second message in the edit history.) !melquiades (talk) 18:15, 3 February 2012 (UTC)
Now, as to the merits — I disagree with you about the "practical, aesthetic, subjective" part. The point, as Moschovakis explains, is that choice is true, whereas determinacy is false. This is not just my opinion; this is what practically any Platonist set theorist will say. Nevertheless such set theorists still study determinacy, for a variety of good reasons. However those reasons are not well covered by the approach you seem to be taking. --Trovatore (talk) 17:59, 3 February 2012 (UTC)
Not all set theorists are Platonists. A Formalist (with whom you may disagree, but like or not, their POV must be respected as well) would see the two systems as epistemological equals and be done with it. I'm not necessarily signed up for either philosophy, but I think it's an open point of debate whether AC can be demonstrated to be "true" in an empirical sense. (What is a Popperian falsification criterion for AC?) Addressing this debate was beyond the scope of my edit. I'm just trying to capture the idea that set theorists can construct many self-consistent systems, even though only ZFC is a candidate for widespread use (or for truth, as you would have it). I tried to keep my wording neutral on the philosophical quesiton. !melquiades (talk) 18:15, 3 February 2012 (UTC)
The thing is that the whole "alternative set theories" approach is not really right. That's not what people who study determinacy are doing. I mean, some of them might be, but it is not the dominant approach. Determinacy tells you about what happens in certain models (L(R) being in some sense the simplest one), and from that you can deduce lots of other stuff. That all works fine inside the dominant ZFC paradigm. --Trovatore (talk) 18:26, 3 February 2012 (UTC)
But isn't Determinacy incompatible with AC? It works inside the ZF paradigm, but can't possibly exist inside ZFC. !melquiades (talk) 18:49, 3 February 2012 (UTC)
AD is incompatible with AC, and ZFD (ZF + AD) is equiconsistent with ZFC + an infinite number of Woodin cardinals, which makes it a higher consistency strength than ZF or ZFC. Arthur Rubin (talk · contribs) 22:07, 3 February 2012 (UTC)
So to the original topic: can anybody further improve upon "alternative set theory," or the rest of the wording in question? It would be nice to quash that "clarification needed," but as a set theory dilettante, I don't think I'm equipped to do it. !melquiades (talk) 06:24, 9 February 2012 (UTC)
The lede seems to have been modified along the lines of what you originally suggested. What are you proposing exactly? Tkuvho (talk) 15:22, 9 February 2012 (UTC)

Interpretation as pointed set

Could you phrase the axiom as "there exists a pointed set over every set"? ᛭ LokiClock (talk) 09:29, 8 March 2012 (UTC)

Depending on how one interprets that, i.e. if you mean a uniform way of associating a basepoint to each nonempty set, then it would be equivalent to the stronger axiom of global choice. JRSpriggs (talk) 19:06, 8 March 2012 (UTC)
How do you mean uniform? It can be interpreted as a nullary operator, but constructing the operator is unnecessary, so I don't see that any pointed set has a way in which it associates the basepoint to the set. I would say "there is a surjection from V to the ordinal numbers." ᛭ LokiClock (talk) 01:21, 9 March 2012 (UTC)
The short answer is, no, you can't phrase it like that. That statement well, adding nonempty in the right place, without which the statement is trivially false is easily proved without AC. JR was explaining how a somewhat different claim, that you might possibly have intended but didn't actually say, might imply AC. --Trovatore (talk) 01:26, 9 March 2012 (UTC)
Okay. So a choice function is uniform because the same function applied to any subset has a result in that subset. But isn't that just a collection of nullary operators you could take as different cases of one function? It doesn't seem like the f(s) definition is equivalent to the direct product definition. ᛭ LokiClock (talk) 01:39, 9 March 2012 (UTC)
No, a choice function is uniform because, whenever you pass it the same subset, you get the same element of that subset. That's what functions do, not just choice functions, but any functions. So your proposed formulation misses the mark because it just says that, given a set, you can get a corresponding pointed set. It doesn't say there's a gadget that, given the same set, always gives you the same pointed set. --Trovatore (talk) 01:48, 9 March 2012 (UTC)
Ah, so the inconsistency comes from the selection of elements in concert. If there were a set with no consistent basepoint, that would obviously extend, but that's already false. ᛭ LokiClock (talk) 02:02, 9 March 2012 (UTC)
To LokiClock: You mentioned "there is a surjection from V to the ordinal numbers" as an equivalent of the axiom of global choice. It is not. Just map each ordinal to itself, and each other set to zero. That is such a surjection, and it does not involve choice.
What you want is either an injection from V to Ord or a surjection from Ord to V. Better still, a bijection between them. JRSpriggs (talk) 07:59, 9 March 2012 (UTC)
Hasty guess. ᛭ LokiClock (talk) 10:25, 9 March 2012 (UTC)

Intro staring with a simple definition?

As Product topology stated:

"The axiom of choice is equivalent to the statement that the product of a collection of non-empty sets is non-empty".

This is more didactic and a less "hermetic" view of the axiom... Can we use it in the article's introduction?

--Krauss (talk) 20:39, 28 May 2012 (UTC)

This doesn't really help the reader if he does not know which definition of product you are referring to, particularly without a suitable link. Tkuvho (talk) 07:21, 29 May 2012 (UTC)
I really don't think that this should be the first of the many equivalent formulations of the axiom of choice that the article should mention: it does not involve a choice of elements in an obvious way, and it depends on the more complex notion of an (infinite) product of sets, something that can be defined in several different ways, see Ordered pair#Defining the ordered pair using set theory. And I think that the second paragraph already does a nice job of explaining the axiom of choice in a non-hermetic way. (I always liked the following formulation of the axiom of choice: "For any partition of a set there exists a subset of that set containing exactly one element from each part of the partition." This is probably one of the "obviously true" formulations.) — Tobias Bergemann (talk) 06:06, 30 May 2012 (UTC)

Refs

I added a new section on AC in constructive math. I hope to keep it relatively short, just a summary of the main issues. I have added references, commented out, for the claims. What reference style is this article supposed to use? Should I just put the refs into footnotes? — Carl (CBM · talk) 14:25, 29 May 2012 (UTC)

The others seem to be in footnotes and/or the bibliography "References".
I wonder if your new section, Axiom of choice#The axiom of choice in constructive mathematics, could be merged with the existing section Axiom of choice#Nonconstructive aspects or at least be made adjacent to each other? JRSpriggs (talk) 22:18, 29 May 2012 (UTC)
I can work on merging them. The other section has a lot of issues in my view, so I will probably rewrite most of it. — Carl (CBM · talk) 00:11, 30 May 2012 (UTC)
I retitled the other section as "Criticism and acceptance". A difficulty I have in mind is that when most mathematicians say "nonconstructive" they don't mean it in the same sense as constructivists do. For example if I explicitly define an object X and then prove (making essential use of the axiom of choice and excluded middle) that X has a certain property P, most mathematicians would call that a "constructive" proof that there is an object with property P. I don't want to try to go into that confusion in the article (who knows if there's even a sensible reference) but at the same time I don't want the article to encourage more confusion.
I also added all the refs for the new section, just putting them into footnotes. — Carl (CBM · talk) 13:24, 30 May 2012 (UTC)

there exists a family

The lede currently states that "for every family (S_i) of nonempty sets there exists a family (x_i) of elements such that for every i, ". Should the fact that the said "family" is actually a set (of the x_i) be emphasized? That seems to be the content of the axiom. Tkuvho (talk) 08:04, 31 May 2012 (UTC)

It is actually a function, unless you add the conditions that the given sets, S_i, are disjoint from each other and that only one of the chosen elements, x_i, is in S_i. JRSpriggs (talk) 08:21, 31 May 2012 (UTC)
Thanks. One would apparently need the axiom schema of replacement, as well. Should "family" be left as is? Tkuvho (talk) 08:26, 31 May 2012 (UTC)
I replaced "family" with "indexed family" to make it clear that we are talking about a function rather than a set. JRSpriggs (talk) 08:53, 31 May 2012 (UTC)
The only problem is that "indexed family" is described as having a set as the image of an index, whereas we want to apply this term to elements, as well. Certainly everything in set theory is a set, but perhaps we want to insist on a useful element/set dichotomy. Tkuvho (talk) 09:22, 31 May 2012 (UTC)

Short story

There is short story called The Axiom of Choice (by David W. Goldman) that was nominated for Nebula Award in 2012. Should that be mentioned? — Preceding unsigned comment added by 178.248.252.213 (talk) 23:59, 20 September 2012 (UTC)

If it won a Nebula, it might be notable enough for its own article, in which case we'd put a disambiguating hatnote on this article. I kind of doubt we want to mention it in the text of this article. --Trovatore (talk) 01:09, 21 September 2012 (UTC)
"“So,” you say, “you can do math either with this axiom or without it?”
“Right.” Kerry stands up.
You remain in your seat. “Then, each mathematician has to choose whether or not to use the Axiom of Choice.”
Kerry pauses and stares at you.
Aleph4 (talk) 07:15, 16 April 2013 (UTC)

Subtle, yet powerfully misleading introduction

The introduction's second paragraph is,

"Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin. In many cases such a selection can be made without invoking the axiom of choice; this is in particular the case if the number of bins is finite, or if a selection rule is available: a distinguishing property that happens to hold for exactly one object in each bin. For example for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate selection, but for an infinite collection of pairs of socks (assumed to have no distinguishing features), such a selection can be obtained only by invoking the axiom of choice."

This is inherently inaccurate: it leads the reader to believe the axiom of choice is not the axiom of choice, insofar as the existence of a selection rule is precisely what the axiom of choice posits. What the author fails to realize is that in a set, all elements are by definition distinguishable; he/she is confusing sets with multisets, in which multiple identical (read: indistinguishable) copies of an element may exist. The capacity to then select a single element from each of an arbitrary collection of sets is what the axiom of choice claims is always possible, that is, it claims there is always a selection rule available. Confusing the reader by suggesting a difference between the axiom of choice and such a selection rule obfuscates the fundamental intuitiveness of the axiom, thereby both making it harder for the reader to understand the statement of, and the great challenges in the implications of, the axiom of choice. — Preceding unsigned comment added by 76.176.189.203 (talk) 19:57, 18 October 2012 (UTC)

The choice of the word rule is intended to get at the intuition of something that can be stated. "Pick the smallest red sock, unless there's a green one at least twice that big, in which case pick the largest yellow sock". The axiom of choice does not guarantee that there's a rule of that sort. If your understanding of "rule" is broad enough to encompass something like "here's an infinite arbitrary table associating sets with elements of sets; the rule is, always pick the one given by the table", then the language is not going to work for you. Do you really think anyone is going to read "rule" in such a way that that would be a candidate? If so, do you have alternative language to propose? --Trovatore (talk) 20:59, 18 October 2012 (UTC)
Even in a universe in which the axiom of choice does not hold, there will be cases in which the existence of a choice function for a particular infinite set of nonempty sets can be proven. That the choice function may exist anyway is what it is trying to say. JRSpriggs (talk) 08:44, 19 October 2012 (UTC)

Maybe so, but the fact remains that neither "an infinite collection of pairs of socks (assumed to have no distinguishing features)", nor a pair "of socks (assumed to have no distinguishing features)" are sets, they are both multisets. The paragraph wants changing. Keithbowden (talk) 18:56, 9 March 2013 (UTC)

The claim that they're multisets strikes me as pretty dubious (maybe you're assuming identity of indiscernibles or something?) but it's certainly true that we don't want readers to go down this (quite irrelevant) path. So let's recap the standard example, and see if there's a way of rephrasing that meets your objection without going off on tangents.
The standard narrative on this goes, if you have an infinite collection of pairs of shoes, then you can pick one shoe from each pair via a rule (e.g. always pick the left shoe), and therefore AC is not needed to prove that a choice function exists.
However, if you have an infinite collection of pairs of socks, because you can't systematically tell a left sock from a right sock, there is no such obvious rule, and AC may be needed to prove such a function exists.
This is such a well-known example that we would probably be remiss not to include it. And it's pretty simple. So there are all the elements; feel free to propose a wording that explains it, does not fall afoul of your objection, and avoids a digression into whether the left sock and the right sock are indiscernible in all respects and if so whether that forces them to be identical. --Trovatore (talk) 20:21, 9 March 2013 (UTC)

Well-ordering theorem or principle?

In the Quotes section, the first quote (by Jerry Bona) refers to the Well-ordering principle which is linked to the Well-ordering theorem, where we are warned that it is Not to be confused with Well-ordering principle. Which is it? If the quote is accurate but the reference should be the theorem (my suspicion), then this should be addressed explicitly. askewchan (talk) 14:42, 12 August 2014 (UTC)

The warning would not be there were there not a lot of people who have said "well-ordering principle" when they meant "well-ordering theorem" (or the reverse). Obviously, Jerry Bona is one of them. An explanation of that would be over-kill and distracting. JRSpriggs (talk) 17:46, 12 August 2014 (UTC)

Proof of Axiom of Choice

The Axiom of Choice assumes are non-empty sets. If a set is given by enumerating its elements, we know when it is not empty and then we can select or choose one of its elements, say the first.

If a set is given by a property its elements share, then you cannot simply state the set is non-empty; you always have to prove it, meaning to identify at least one of its elements. For instance, = = is the least element of is the empty set as it has no elements.

The Axiom of Choice assumes are non-empty sets, so we have already proven they are non-empty, meaning we have already identified at least one element of each .

Then the choice function in the Axiom of Choice could be:

"From each non-empty set choose the first identified element."


Aurelian Radoaca (talk) 15:07, 31 August 2014 (UTC)

"Nonemty" is a premise. You don't prove those. You assume them. YohanN7 (talk) 16:46, 31 August 2014 (UTC)


The Axiom of Choice says are non-empty sets, so you know that.

Given a set , in order to know it is non-empty, you have to identify at least one element (or otherwise prove it is non-empty, in case you cannot identify an element), or else the set may be empty. Is it possible to know a set is non-empty and not being able to identify one element? In either case, in order to know a set is non-empty, you have to prove it.

The Axiom of Choice starts with the assumption that are non-empty sets, so you know they are non-empty.

Aurelian Radoaca (talk) 17:45, 31 August 2014 (UTC)

Let S be the power set of the reals except for the empty set. Now you know they are nonempty. What is your choice function?
You should probably take this to Wikipedia:Reference desk/Mathematics. This page is for discussing the article. YohanN7 (talk) 18:04, 31 August 2014 (UTC)

Any union of countably many countable sets is itself countable

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

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)

Quotes section

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)

Banach-Tarski paradox

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)