Talk:Axiom of choice

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 (talk • contribs) 21:54, 26 November 2011 (UTC)