# Do functions whose domains are infinite sets sequentially or simultaneously map their elements

Here are two equivalent definitions of the axiom of choice

Let $x$ be a set. Suppose that if $y,w \in x$, then $y \neq \varnothing$ and $y\cap w = \varnothing$. Then there is a set $z$ such that if $y \in x$, then $y \cap z$ contains a single element.

and

Let $I$ be a nonempty, indexing set and let $\{A_i\}_{i\in I}$ be a family of nonempty sets indexed by $I$. Then there is a function $f: I \rightarrow \bigcup_{i \rightarrow I} A_i$ such that $f(i) \in A_i$ for all $i \in I$.

The text says with regards to the first definition that if we want to choose one element from each set in an infinite family of nonempty sets, we must make the choices simultaneously instead of sequentially. I would like to know where in either definition it can be understood that the elements are chosen at the same time rather than one-by-one, or is this just mere terminology as to be didactily correct yet mathematically irrelevant.

The author also mentions that in proving that if $f: A \rightarrow B$ is surjective, then $f$ has a right inverse, one element $a \in A$ is chosen simultaneously such that $b = f(a)$, which leads me to also wonder if whenever we say, "Let $a \in A$ such that $b = f(a)$", we mean that the elements in $A$ are being simultaneously mapped by $f$ to a $b$; and if that's true, then when would $f$ sequentially map the elements in $A$ to some of the elements in $B$?

I know my issue with understanding how the elements are chosen is so trivial as to be a mere distracting quibble, but I really want some clarification. Note that this is not an axiom of choice question, since I'm really just curious as to how the elements are selected and in what ways do we distinctly want elements to be sequentially or simultaneously chosen.

• Do you mean "collection" instead of "set" for the first definition? Also should $z\in x$? Dec 29, 2015 at 18:14
• The words "collection," family," and "set" are synonyms. Also, $z$ does not necessarily have to be an element of $x$. Dec 29, 2015 at 18:20
• It's more like what you said -- mere terminology just so you don't get any misconceptions, but in the bigger scheme of things mathematically irrelevant. Re surjections, again there's no notion of "time" involved. Dec 29, 2015 at 18:38
• @BenedictVoltaire The whole point to the axiom of choice (The existence of a choice function), is that there are problems with constructing a choice function. The Author of states that these problems arise on page 121 of your textbook.(maybe 141 pdf version) So to counteract these problems you "magically" wish a choice function into existence(this is the simultaneous choices you are making). Also the author says you cannot make your choices one at a time.(same page) due to physically constraint (time, energy, etc). Dec 29, 2015 at 20:18
• @BenedictVoltaire OK "irrelevant" is a strong term (yours!), perhaps too strong. What the text means is that the choices are made independently. It's not a recursion, for example, nor is it as in the Axiom of Dependent Choice (a corollary of AC) where you build a choice function along a relation, and each choice depends on the choices made for at predecessor steps. In terms of the 2nd formulation, if e.g. $I=\Bbb N$, the choice made for $n$ doesn't depend on the choices made for the $i<n$. Dec 30, 2015 at 9:14

The difference between choosing things "simultaneously" and choosing them "sequentially" is that when you choose them sequentially, your later choices are allowed to depend on your previous ones. This is the difference between countable choice and dependent choice.

But this has nothing to do with functions. A function's values are fixed in "Platonic reality"; they aren't "chosen" in any sense.

If $A$ is a non-empty set, to choose an element of $A$ means that we have some new constant symbol $a$ and we assert that $a\in A$. This is also known as existential instantiation. We prove, or assume that $\exists x(x\in A)$, then we can "instantiate" the existential quantifier and obtain "an actual element of $A$".1

We can repeat this finitely many times, so this essentially means that we can choose from finitely many sets at once.2

Using the axiom of choice, in however formulation of it that you want, given a family of sets $\{A_i\mid i\in I\}$ there is a function, $f$ such that $f(i)\in A_i$. This means that we have a term describing an element of $A_i$. Since $f$ does it for all $i\in I$ it means that simultaneously we chose elements from each $A_i$.

If you want to really get formal, then the family of sets is itself a function $A$ with domain $I$ such that for all $i\in I$, $A(i)$ is a non-empty sets. But at this point it becomes an obstruction to the intuitive understanding of the term "choose simultaneously from all the sets in $\{A_i\mid i\in I\}$", so I'll stop.

1. (with quotation marks, because what does it even mean an actual element of $A$?)

2. (I am cheating you here, from a mathematically correct point of view; but intuitively this is how I think about that, and how I explain my students when we first talk about AC.)

• I like your post, but a quick question: If we are choosing an element $a \in A$, why is it an existential element as opposed to an arbitrary but fixed element $a \in A$, so that the quantifier shifts from $\exists$ to $\forall$? In other words, how do you mean by "choosing" an element in $A$ as opposed to choosing an arbitrary but fixed element in $A$? Or is it clear from the context that you need $a$ to be existential for the sole reason as to make your point? Dec 29, 2015 at 18:21
• What is an arbitrary element? That's the point. When you talk about something formally, you have to appeal to some formal language at some point. What is a non-empty set? It's just a set $A$ that we can prove/assert that $\exists x(x\in A)$; but we don't have any reasonable way to pick an element from it because our language is not equipped for that. So we extend it by a new constant symbol, say $a$, and we assert that $a\in A$. So now we have a constant symbol to denote a fixed, but arbitrary element of $A$. Dec 29, 2015 at 18:26

The axiom of choice chooses somewhat magically. So I doubt either a sequential description or a simultaneous one would give a good picture of how the choosing operates. For example:

$I=\mathbb{R}$ and $\{A_i\}_{i\in I}$ where $A_i=\mathbb{R}$. The axiom of choice states that there exist a choice function $f:I\to \bigcup_{i\in I}A_i$ where $f(i)\in A_i$. (Note that $\bigcup_{i\in I}A_i=\mathbb{R}$)

But what this specific description I gave is saying, is that there exist a function with domain $\mathbb{R}$ and range $\mathbb{R}$. So a list of choice functions could be:

1. $f(x)=x$
2. $f(x)=\sin{x}$
3. $f(x)= e^x$
4. $\int e^{x^2}dx$

etc. Being that I wouldn't describe the the function $f(x)=e^x$ as a sequential choice of numbers on the real line, I don't think sequential choice making is the best description. (I would simply view $e^x$ as more of a magical description that if you ask for the value of $x$ at $f(x)$ I can tell you, but neither you nor I have the time to go through and look at them all.)

Here is the thing with the axiom of choice. You don't know how the choices are being made. You don't know how they look like. You just assume that you can make one. That is it. So asking how a choice is being made is pointless unless you are talking about finitely, or countably many choices, which are easier to deal with.