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

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?

• No, the axiom of choice does not say that. As an aside, it also never says "you cannot choose without me". Commented Feb 15, 2022 at 4:37
• Take another look at the Axion of Choice: it doesn't say that there exists a function from a generic $A$ to a generic $B$. Rather, it says that there exists a function from a particular type of $A$ to a particular type of $B$ that satisfies a particular property. Commented Feb 15, 2022 at 5:20
• The point of the axiom of choice is to pick a element from each member of an infinite family of sets. You’re not using choice is any manner whatsoever. Commented Feb 15, 2022 at 6:00
• The Axiom of choice guarantees a certain type of function (which can be seen as a choice) when certain conditions are met. Sometimes, one can establish the existence of such functions without having to invoke AC. But there is nothing in any of this means that AC says, in any way whatsoever, that "you cannot show the existence of a function without invoking me". For one thing, axioms don't refer to themselves that way. Sometimes we can prove, using other tools, that the existence of such functions in specific circumstances is closely tied to AC, but those proofs are not AC Commented Feb 15, 2022 at 6:23
• (cont) I think you seriously misunderstand what AC says or what it means. Commented Feb 15, 2022 at 6:26

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.

• Wow, thanks to explain the concept with easy words. I love MSE! Commented Feb 16, 2022 at 4:09
• You also need disjointness in the first version. Commented Feb 16, 2022 at 15:57
• @Logic: No, you do not need disjointness; that's another version, and is equivalent to the one I give. Commented Feb 16, 2022 at 16:24
• What about $\{\{2},\{2,3}\,\{3}}\$? There is no set which contains exactly one element from each set? Commented Feb 16, 2022 at 16:35
• @Logic: oops.${}{}$ Thanks. I'm thinking of the choice function version which is often written with pairwise disjointness... Commented Feb 16, 2022 at 16:36