Talk:Axiom of choice

A question on User Talk:CSTAR led to a long discussion of the precise meaning of the independence of the axiom of choice (among other things). By consent of the participants, it was moved here. Gadykozma 20:59, 2 Sep 2004 (UTC). After dying out, it was archived. Gadykozma 13:17, 22 Sep 2004 (UTC)

Do Wikipedia articles assume the axiom of choice unless otherwise mentioned? Or should results which rely on choice be marked as such? --Matthew Woodcraft

They should be marked as such. If they're not, fix them. --Taw

Pretty much anything I write assumes AC. --Zundark, 2001 Dec 16

I think it is polite, when writing about a central theorem like existence of prime ideals or Hahn-Banach, to mention that it depends on AC, but it is really too much to ask to do the detailed bookkeeping and mention AC for every result which depends on one of those theorems. AC is an accepted axiom in mathematics. --AxelBoldt

This last position seems to be modern practice, at least in the areas of mathematics I'm familiar with. Should we have a note to this effect on the main AC page? --Matthew Woodcraft

Yes, we should. If you're feeling in the mood, this article really needs an overhaul. I moved some paragraphs here from the set theory article months ago, but no-one has yet attempted to merge it all into a coherent whole. --Zundark, 2001 Dec 16

Is there any treatment of "life without AC"? I would find this an interesting topic. --Jeff

I would really like to see at least a paragraph in this article about the current status of the controversy regarding the AC. Thanks to the specialist(s) who would add this update! olivier 03:59 Nov 27, 2002 (UTC)

Of course, linguistic abuses can lead to many so-called "paradoxes". For example, "This is not a true statement." seems paradoxical. Yet, the problem is the use of the pronoun "This" which makes the statement self-referential. When things reference themselves, they are no longer first order. The statement is never "within the system" if it references itself. The reference generates a copy of the system, putting the statement outside of the system. Many higher order systems have no know solutions. J. Todd Chapman

There isn't much work in this direction (as opposed to continuum hypothesis). Too much of mathematics relies on this axiom. The proofs which do not rely on it are considered to be constructive, and there is some interest in seing if there is a constructive proof in this sense, but there is no controversy about the axiom of choice - there isn't really much to say about it except that it is independent, nonconcstructive but makes life much easier. Continuum hypothesis is almost irrelevant to everyday mathematics and that is perhaps what makes a big difference.

Might help to mention that AC is provably false in Quine's NF though it holds for all the sets one would encounter in "everyday" maths. I'd do it myself but it's much too long since I studied logic. Tom Holbrook 14:39 10 Jul 2003 (UTC)

The recent edit about stating whether AC is used, and preferring not to use it, is definitely POV. Logicians, and those in constructive mathematics - and of course anyone who wants to compute anything, may agree; but it's not the mainstream approach. Post-Bourbaki, one uses Zorn's Lemma and forgets about it.

Charles Matthews 15:46, 20 Oct 2003 (UTC)

It was my edit, and agreed it's tinged by my set-theorist POV. It is equally POV to state without qualification that AoC is accepted as true (since that's not the point), or that it is of no import whether it is used or not. How about something like "Despite this, a minority of mathematicians..." instead of "Despite this, it is common to..." Onebyone 16:50, 20 Oct 2003 (UTC)

Can be made NPOV by a bit of expansion: eg anyone who wants results true in all toposes etc etc.

Charles Matthews 17:04, 20 Oct 2003 (UTC)

How's that? I haven't mentioned topoi because (I don't understand them and) "system" is fine for the general reader. Onebyone 16:09, 25 Oct 2003 (UTC)

From the article: Jerry Bona once said: "The Axiom of Choice is obviously true...

Who is Jerry Bona? Kevin Saff 18:29, 23 Mar 2004 (UTC)

I've never heard of him either, but the joke itself is famous, and he invented it, then he deserves the credit. -- Walt Pohl 02:48, 24 Mar 2004 (UTC)

I agree, though the statement seems phrased to imply that Jerry Bona is more famous than the joke, if that makes sense. I guess this is Jerry Bona. Maybe it could read something like Jerry Bona, a UIC math professor, famously cracked, "The Axiom of Choice..."

Something which might be worth mentioning is that at least some of these consequences of the axiom of choice have been shown to imply the axiom as well (Tychonoff's theorem, for example). I'm not sure which other ones do or don't though. Kevinatilusa

Additionally, is conjectures really the right category to put this under? Calling it a conjecture seems to imply that it could be proven someday, which isn't the case here. Kevinatilusa

I agree; it should be removed from that category (or is it topoi? :)). --66.219.81.52 00:23, 16 Jun 2004 (UTC)

I've removed the conjectures tag, since there are independence results making that misleading. Charles Matthews 07:40, 16 Jun 2004 (UTC)

This doesn't seem right to me... first the article says:

For example, a proof could use a set S that was previously demonstrated to be non-empty and claim "because S is non-empty, let x be one of the members of S." Here, the use of x requires the axiom of choice.

This doesn't require AC, does it? X consists of one set, S, and as stated in example 1.:

1. Let X be any finite collection of non-empty sets.

Then f can be stated explicitly (out of set A choose a, ...), since the number of sets is finite.

--66.219.81.52 00:23, 16 Jun 2004 (UTC)

The example does require the axiom of choice. I'm not sure what your second question is talking about, though. Little x in the example has nothing to do with the big X, which is a set, that you are talking about. Anyway, from a set theory book this is just about as classic as an example can get.

Given a set X that is nonempty, there exists x in X. This requires only predicate calculus, not the axiom of choice.

To use the element in X requires the axiom of choice. Check out this quote from Hayden and Kennison:

"Choose ab\in Ab [...] This fallacious argument looks reasonable because of a subtle ambiguity in the phrase 'choose ab\in Ab.' It is certianly true that givewn any non-empty set S, on can 'choose' an element s\in S. This follows from the fact that there exists and x such that x\in S (as S is non-empty), and from our convention about choosing an entity e for which P(e) whenever it is true that there exists an x such that P(x). Thus, for any one of the sets, Ab, we can 'choose' ab\in Ab. But there is no way we can legitimately 'choose' a dependent variable ab for all b\in B. What is needed is a 'choice function' that will enable us to make many choices simultaneously." (Zermelo-Fraenkel Set Theory, 1968, p. 50f)

Note, the above quote is from a book and is not covered by FDL. MShonle 05:33, 25 Jun 2004 (UTC)

I hope to clear this up very precisely. Given a nonempty set X1, producing an element x in X1 requires only existential instantiation. Similarly, given any finite family of disjoint nonempty sets X = {X1, X2, X3, ...XN}, it does not require the axiom of choice to construct a set that contains one element form each XJ in X. This is only finite reiteration all of which can be done in ZF. Now suppose X is an infinite family of disjoint nonempty sets. If we know of a rule by which we can choose a unique element from each set ( "choose the least element" if they are so ordered or something like that) then again we do not need the axiom of choice. It is when we can not construct the set that we need the axiom of choice, which is existential rather than constructive. Thus he says we need the axiom to make many (infinitely many) choices simultaneously.

) By the way, assuming there are only finitely many nonempty boxes, I can easily choose a single element from each using only ZF. This article is misleading.

If no one has a problem with this, I would like to add another equivalent formulation of the AC. Stated in its most compact form: "Given infinite sets A and B, every bijective mapping from A to B has an inverse." It's a different take on the principle. Any objections? Tim 19:54, 2004 Oct 8 (UTC)

Huh?? Maybe you meant that for every surjective mapping f : A --> B there is an "inverse" g : B --> A such that f(g(x)) = x for x ∈ B? As you state it, it doesn't seem equivalent to AC at all. Michael Hardy 20:24, 8 Oct 2004 (UTC)

Arrg. I always get "bijective" "surjective" and "injective" mixed up. I'll have to go back and look at it a little longer. This isn't my formulation, so I'll have to get a little for clarification before I add it... Tim 00:04, 2004 Oct 10 (UTC)

Epimorphisms split. Well, that's more compact.

Actually there are books full of equivalents.

Charles Matthews 20:25, 8 Oct 2004 (UTC)

Here, the use of a requires the axiom of choice.

As others have noted, this statement from the article is misleading if not false. Unless we are using intuitionist logic, "S is not empty", or "¬(∀x: ¬[x ∈ S])", implies "There is a value x in S", or "∃x s.t. x ∈ S". And using this value x, we could find other values; from the properties of the set S we could find out all kinds of things about x, with all kinds of implications; in short, there are some uses of a that do not require the axiom of choice.

On the other hand, the quote from Hayden and Kennison discusses a particular sort of use of a which is not permitted: We cannot rewrite statements of the form ∀x: [∃y s.t. P(x,y)] as ∃f s.t. [∀x: P(x,f(x))] without the axiom of choice. If we could, then the axiom of choice would follow: Let's say we have a set X of non-empty sets. Then ∀x in this set, ∃y s.t. y∈x. By this rule of inference we wish to show implies the axiom of choice, we have ∃f s.t. [∀x: f(x)∈x]. But that is the same as our second statement of the axiom of choice, completing the proof.

So here, Skolemization on a requires the axiom of choice.

- Jrn 01:31, 17 Oct 2004 (UTC), a non-mathematician who wants to be contradicted