The Axiom of Choice is defined by Mcdonald, A Course in Real Analysis as follows:

"Suppose that $C$ is a collection of non-empty sets. Then there exists a function $f: C \rightarrow \bigcup\limits_{A\in C}A$ such that $f(A)\in A$ for each $A \in C$."

I don't understand what it means for a function to exist between a collection and a union of sets in the collection. Also, how do we know that putting $A$ into the function returns an element of $A$?

  • 1
    $\begingroup$ $S=\cup_{A \in C}A$ is a set, isn’t it? So you can consider functions $C \rightarrow S$. For the second part of your question, the fact that we can choose $f$ as such (ie for all $A$, $f(A) \in A$) is exactly the axiom of choice. $\endgroup$ – Mindlack Sep 2 at 17:05
  • 3
    $\begingroup$ It isn't "for some", but "for all". $\endgroup$ – Gae. S. Sep 2 at 17:06
  • $\begingroup$ @ Mindlack Yes, I understand a function is mapping between sets. I don't understand what it means in this case. For the second part, it seems arbitrary. $\endgroup$ – senior_data_scientist Sep 2 at 17:07
  • $\begingroup$ If you know what an equivalence relation on a given set $X$ is, maybe you can check out this: link. Because these kind of things you come a cross very often in all sorts of areas and very often you very much by definition need such a function to be able to pick a representative of any given equivalence class. Again, just if you are already familiar with this concept. $\endgroup$ – hal4math Sep 2 at 17:40

Perhaps an example will help.

Let $C = \{\{1,2\},\{2,3\},\{3,4\}\}$.

Notice that $\bigcup_{A \in C} A = \{1,2\} \cup \{2,3\} \cup \{3,4\} = \{1,2,3,4\}$.

The axiom of choice asserts, for this example, that

There exists a function $f : C \to \bigcup_{A \in C} A$ such that $f(A) \in A$ for each $A \in C$.

And this statement is true, as you can easily verify on your own without even applying the axiom of choice, by simply choosing correct values of the function $f$, which I will leave it for you to fill in: $$\begin{align*} f(\{1,2\}) &= ? \quad\text{(choose some element of the set $\{1,2\}$)} \\ f(\{2,3\}) &= ? \quad\text{(choose some element of the set $\{2,3\}$)}\\ f(\{3,4\}) &= ? \quad\text{(choose some element of the set $\{3,4\}$)} \end{align*} $$

The hard part comes when the set $C$ is infinite. In this case, you cannot always write down the infinitely many choices to be made in order to specify the choice function $f$. The Axiom of Choice is nonetheless verifying that this function exists, despite our inability to write it down.

  • $\begingroup$ Thanks, I understand the mapping issue now for question 1. Regarding the second question: it seems very hand-wavy that we can obviate the selection issue by simply stating that "yes we can select something from a set". What am I missing? $\endgroup$ – senior_data_scientist Sep 2 at 17:26
  • $\begingroup$ You're not missing anything. Axioms are like that. Think about Euclid's axioms for points and lines in the plane, think about Euclid's parallel postulate: that's kind of hand-wavy too, especially if you remember that Euclid did not have Descartes' coordinate geometry at hand like we do. $\endgroup$ – Lee Mosher Sep 2 at 17:28
  • $\begingroup$ Of course, we don't want to just make up axioms if we don't have to. The whole idea behind axiomatic mathematics it to try to pin down the rock bottom set of axioms that are needed on which the proofs of mathematical theorems can be built. $\endgroup$ – Lee Mosher Sep 2 at 17:30
  • $\begingroup$ Ah, so there is some element of "belief" then. At some point, we just have to believe a thing or it all falls apart? $\endgroup$ – senior_data_scientist Sep 2 at 17:32
  • $\begingroup$ You could take that point of view, although that's getting a bit too philosophical for me. Another point of view is that sometimes, if the axioms for a particular logical system are simple enough, then they can actually be verified. So, for example, the Axiom of Choice can be verified for a finite set $C$ by a simple induction argument (assuming that you accept Peano's Axioms for natural numbers and induction !!!!) $\endgroup$ – Lee Mosher Sep 2 at 17:34

The axiom says that from a collection of sets, you can choose one element in every set, by means of function.

So the domain of the function is the collection, and the range is the set of elements contained in the members of the collection.


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.