Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

First a quick question regarding the definition of the axiom of choice. Do the sets have to be mutually disjoint nonempty sets or just non-empty? One source states: "For any set X of nonempty sets, there exists a choice function f defined on X." But another source states that the sets have to be mutually disjoint.

Secondly, pardon me if I sound ignorant (I'm learning this as a hobby so I don't have much background or time for it) but isn't it a really obvious/self-evident concept? I mean essentially, it is saying that if you have a collection of non-empty sets, then you can pick an element out of each set. I realize that there are difficulties when we cannot make explicit choices because we cannot create an explicit algorithm for the choice function (for example the collection of all nonempty subsets of the real line), but does that really matter?

I mean just like the number 5, the existence of the function 'f' is purely formal. Math isn't able to fully describe or prove everything but doesn't mean it doesn't exixt.

share|improve this question
7  
Disjoint or not? It's your choice. The two versions are equivalent. –  André Nicolas Oct 8 '12 at 14:06
6  
It's fine if you think it's an obvious property of what you consider sets. After all axioms should convey our notions of what is obvious. For example, it is also obvious that given a set, we also have its powerset; yet this obciusness needs to be put down as an axiom once and for all so that one has a nice formalization of the mental concept of sets. Then again, the existance of choice may not be that obvious - after all it's mainly AC that leads to Banach-Tarski abd similar "paradoxical" theorems. –  Hagen von Eitzen Oct 8 '12 at 15:34
add comment

5 Answers

up vote 17 down vote accepted

It doesn’t matter whether you require the sets to be pairwise disjoint or not: the two versions are equivalent. To see this, suppose that you have only the version for pairwise disjoint sets, and let $\mathscr{A}$ be any set of non-empty sets. For each $A\in\mathscr{A}$ let $A'=A\times\{A\}$, and let $\mathscr{A}'=\{A':A\in\mathscr{A}\}$; then $\mathscr{A}'$ is a set of pairwise disjoint non-empty sets, so it has a choice function $\varphi:\mathscr{A}'\to\bigcup\mathscr{A}'$ such that $\varphi(A')\in A'$ for each $A'\in\mathscr{A}'$. But then $\varphi(A')=\langle a,A\rangle$ for some $a\in A$, so $\pi\circ\varphi$ is a choice function for $\mathscr{A}$, where $\pi$ is the projection function that picks out the first component of an ordered pair.

The axiom of choice does seem self-evident at first sight, but it has some consequences that are far from self-evident and indeed seem very unlikely at first sight. For instance, you might like to read about the Banach-Tarski paradoxical decomposition of the sphere. And it turns out that it is neither a consequence of nor in conflict with the usual axioms of set theory: it is independent of them, but also consistent with them.

share|improve this answer
4  
My indecisive soul appreciates the axiom. –  peoplepower Oct 8 '12 at 21:16
5  
"The Axiom of Choice is obviously true, the Well–Ordering Principle is obviously false; and who can tell about Zorn’s Lemma." –  Ben Crowell Oct 8 '12 at 23:16
    
sorry if this sound stupid, but what does the 'X' symbol when you wrote A'= A X {A}. Is that the cartesian product?? –  BYS2 Oct 10 '12 at 6:28
1  
@BYS2: Yes, it is. So $A'=\{\langle a,A\rangle:a\in A\}$. This is a standard trick to convert an arbitrary family of sets into a family of pairwise disjoint sets, by attaching to each of the original sets a distinct label, so to speak. Here the label attached to the set $A$ is $A$ itself: each member of $A$ gets tagged with that label, turning $a$ into $\langle a,A\rangle$. –  Brian M. Scott Oct 10 '12 at 6:32
1  
@BYS2: No, that’s just a standard set-theoretic notation for an ordered pair. I prefer it to the older $(a,A)$, but if you’re more comfortable with the latter, go ahead and use it instead. –  Brian M. Scott Oct 10 '12 at 6:45
show 3 more comments

For finite $X$ it is certainly obvious. For countably infinite $X$, it is less obvious, and for uncountable $X$, it is not obvious at all; it becomes a highly abstract statement about the intended properties of certain highly abstract objects in a highly abstract theory.

share|improve this answer
    
thanks for your comment! –  BYS2 Oct 9 '12 at 9:56
add comment

There are many equivalent formulations for the axiom of choice. You must refer to the following two:

  1. For every collection of non-empty sets $\cal A$, there exists a function such that $f(A)\in A$ for all $A\in\cal A$.
  2. For every collection of pairwise disjoint sets, $\cal A$, there exists $C$ such that $C\cap A$ is a singleton, for all $A\in\cal A$.

Generally speaking, however, when requiring a choice function to exist we do not mind if the sets are not disjoint.

For the second question, the axiom of choice is indeed very intuitive. It seems so obvious that we can do that. In fact, in some constructive set theories the axiom of choice is in fact a theorem. However there are so many counterintuitive consequences which follow from this axiom that people were rejecting it outright from the beginning.

The fact that we cannot write an explicit choice matters because when we write a proof we need to refer to an object, and we cannot refer to this object if we cannot prove it exists. So if we can write it, then it exists and all is fine; but if it cannot be written explicitly? What then? Then you need an axiom to assert its existence.

Mathematics may or may not exist in a platonic sense. We don't know that. We also don't like our mathematics to be based on pure belief. We prefer it would be based on deduction. Even if something exists, but we cannot prove that, then it does not help anyone.

share|improve this answer
    
Great answer! yes that helped clear some things up! Appreciate the fact that you actually found the 2 equivalent formulations I was thinking about! –  BYS2 Oct 9 '12 at 9:56
add comment

The two statements of choice given are equivalent; if some element occurs in more than one set, then the choice function could pick it both times, so we might as well give it different names in each of these two sets, reducing to the mutually disjoint case in which the existence of a choice function is equivalent to one in the original setup. This is slightly vague, but should be the right idea in principle. (Brian M. Scott's answer is far more explicit about this).

I would agree, subjectively, that the axiom of choice is "obvious". That's sort of the point of axioms - they're statements that you think any sensible mathematical model should satisfy, so you assume them instead of proving them. After all, you have to assume at least one statement to prove any others. However (and this is a very big however), the axiom of choice is discussed more than many other axioms, and even not assumed by some people, because it has highly counter-intuitive consequences, such as the Banach-Tarski theorem. This should lead one to wonder whether it is really so "obvious" that the axiom of choice should be true, as it has consequences which, in a similar sense, should "obviously" not be true!

A word on your final sentence; there are axioms inherent in the various definitions of $5$, just less controversial ones. Ideally, nothing should be assumed without being explicit about the fact that you're assuming it.

share|improve this answer
    
Ahh ok, thanks for explaining my first question in plain English! I just selected the answer with the most votes as the correct one but I do think yours was great! –  BYS2 Oct 9 '12 at 9:58
add comment

There are some great answers for your first part, but let me add something for your second part:

One of the reasons the AoC seems "obvious" is that the mathematics used by physicists to describe "our universe" depends on it (constructing ortho-normal bases of Hilbert spaces in Quantum Mechanics/Quantum Field Theory, etc). This doesn't meant that the more formal mathematical systems are any less correct, nor that we won't use a non-AoC based system for some later physical model, but so far math in the "real world" uses the AoC very frequently.

share|improve this answer
1  
I don't think this is right. You need AC to prove that every vector space has a basis. But in the physical examples you're referring to, I think the basis can always be explicitly constructed, so AC is not needed. If AC is used in a proof in physics-related cases like these, it's a convenience, not a necessity. I definitely don't believe that anything stronger than countable choice can have any physical significance, because all measurements of our physical world are representable as rational numbers, and there are only countably many rationals. The real number system is just a convenience. –  Ben Crowell Oct 8 '12 at 23:22
    
The axiom of choice is equivalent to the assertion that every vector space has a Hamel basis. This is not the same as an orthonormal basis for a Hilbert space. Most spaces I heard from physicists are things like $L^2$ which has a Schauder basis without the axiom of choice. –  Asaf Karagila Oct 9 '12 at 10:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.