Can't we choose any particular element from $^{A}B$ without the axiom of choice?

Question

In "Elements of Set Theory" by Herbert B. Enderton, pg. 52

For sets $A$ and $B$ we can form the collection of functions $F$ from $A$ into $B$. Call the set of all such functions $^{A}B$: $$^{A}B=\{F\;|\;F \;\text{is a function from} \;A\; \text{into} \;B\}$$ If $F:A\to B$, then $F\subseteq A\times B$, and so $F \in \mathscr P(A\times B)$. Consequently we can apply a subset axiom to $\mathscr P(A\times B)$ to construct the set of all functions from $A$ into $B$.

We can form a set of all functions from $A$ to $B$, but the existence of choice axiom says we can not select any particular element from $^{A}B$ without the axiom (so we can do this only by the choice axiom, not by subset axiom). Do I understand correctly?

Answer 1

There are multiple versions of the Axiom of Choice; you could write an entire book just listing different equivalent ways of stating it. Unfortunately, you would not be able to get it published, because someone already beat you to it

(In fact, you could write two books)

Here is one version:

Let $\mathcal{X}$ be a set whose elements are pairwise disjoint nonempty sets. Then there exists a set $A$ such that $A$ contains exactly one element of each $X\in\mathcal{X}$.

A slightly different (but equivalent) version is:

Let $\mathcal{X}$ be a set whose elements are nonempty sets. Then there exists a function $f\colon \mathcal{X}\to\bigcup \mathcal{X}$ such that $f(X)\in X$ for every $X\in\mathcal{X}$.

Here, $\bigcup\mathcal{X} = \{z\mid\exists X\in X( z\in X)\}$. We think of the function $f$ as a "choice function" that "chooses" an element of $X$ for each $X\in\mathcal{X}$.

Now, the Axiom of Choice tells you that under certain conditions, you are guaranteed the existence of a certain function. We need it because there are situations where we cannot guarantee/prove the existence of such a function using just the other axioms. (Exactly when can be a subtle matter; intuitively, if you need to make an infinite number of decisions in selecting the elements, and there is no finite way of specifying them all, you will probably need the Axiom of Choice to ensure you can do it).

But the Axiom of Choice does not say "you must use the Axiom of Choice to ensure such a function exists". That would be a form of affirming the consequent, a logical fallacy. While (correctly) invoking the Axiom of Choice will ensure that its conclusion (existence of a choice function) holds, it may be possible for the conclusion to hold without having invoked the Axiom of Choice. In short: it is true that from $P$ and $P\to Q$ you may deduce $Q$. But it may be possible to deduce $Q$ without ever using that $P\to Q$ holds.

This does not mean that without the Axiom of Choice you can never "make choices". It is possible to prove the existence of such functions in some circumstances without having to invoke the Axiom of Choice. For example, if all elements of $\mathcal{X}$ are nonempty subsets of $\mathbb{N}$, we can say "let $f$ be the function that takes each set $X\in\mathcal{X}$ to its smallest element." One can make this precise in the language of set theory; because we have a way to specify the value of $f$ at each and every element of $\mathcal{X}$, this will give a function and we do not need the Axiom of Choice. Another example is to take, for example, a nonempty set $A$, and let $\mathcal{X} = \{A\times\{n\}\mid n\in\mathbb{N}\}$. Then we can specify a function by saying: "let $a_0$ be an element of $A$. Then define $f$ as $f(A\times\{n\}) = (a_0,n)$." Again, we do not need the Axiom of Choice to guarantee this function exists, and is a "choice function."

So we may not need the Axiom of Choice to ensure the existence of a choice function in some specific instances.

(Analogy: Euclid's 5th Postulate guarantees that under certain circumstances, two lines will meet; but it may be possible to ensure that two specific lines meet without having to invoke the 5th posulate. It's just that you can't always guarantee it under the certain circumstances, so sometimes you will need to use it.)

Now on the matter at hand: you do not need the Axiom of Choice in any way. One can write down a sentence in the language of Set Theory that says "this set is a function from $A$ to $B$". This gives you a property that you can use in the Axiom of Subsets to ensure that, starting with $\mathcal{P}(A\times B)$, you already know is a set, you can construct the set of all sets that are functions from $A$ to $B$. We are even able to exhibit specific elements of this set without the Axiom of Choice, provided that you do not have $A$ nonempty and $B$ empty: if $B$ is nonempty, let $b_0\in B$ be an arbitrary element (this is existential instantiation, which does not need the Axiom of Choice); then define the set $A\times\{b_0\}$. I leave it to you to verify that this is a function from $A$ to $B$ when $B$ is nonempty. If $B$ is empty, then we must also have $A$ empty and then $\varnothing$ is a function from $A$ to $B$. In either case, we have exhibited elements of ${}^AB$ (as you write it) without having to use the Axiom of Choice.