18
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ Disjoint or not? It's your choice. The two versions are equivalent. $\endgroup$ – André Nicolas Oct 8 '12 at 14:06
  • 6
    $\begingroup$ 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. $\endgroup$ – Hagen von Eitzen Oct 8 '12 at 15:34
17
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ My indecisive soul appreciates the axiom. $\endgroup$ – peoplepower Oct 8 '12 at 21:16
  • 5
    $\begingroup$ "The Axiom of Choice is obviously true, the Well–Ordering Principle is obviously false; and who can tell about Zorn’s Lemma." $\endgroup$ – Ben Crowell Oct 8 '12 at 23:16
  • $\begingroup$ sorry if this sound stupid, but what does the 'X' symbol when you wrote A'= A X {A}. Is that the cartesian product?? $\endgroup$ – BYS2 Oct 10 '12 at 6:28
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Oct 10 '12 at 6:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 10 '12 at 6:45
17
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great answer! yes that helped clear some things up! Appreciate the fact that you actually found the 2 equivalent formulations I was thinking about! $\endgroup$ – BYS2 Oct 9 '12 at 9:56
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – BYS2 Oct 9 '12 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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