Intuition for why the Power Set Axiom can not be used to derive the Axiom of Choice

Question

Using the Axiom of Replacement, every set E, with elements e, has a mirror set E' with the property :

$$ E' := \{\langle E,e\rangle \mid e \in E \} $$

Again using the Axiom of Replacement, for any set S, with elements E, there is a set S'' containing mirror sets :

$$ S'' := \{E' \mid E \in S \} $$

Applying the Axiom of Union to the set S'' gives a set US:

$$ US= \{\langle E,e\rangle : E \in S \land e \in E \} $$

Now apply the Axiom of Power Set to US to produce a set PUS and assume that the set PUS contains every conceivable subset of US. This appears reasonable since the Cantor proof of the difference in Cardinality of $\mathbb{N}$ and $Power(\mathbb{N})$ uses this assumption.

$$ PUS = \{ \text{all conceivable subsets of US containing elements of the form $\langle E,e\rangle$}: E \in S \land e \in E \}$$

Using the Axiom of Comprehension (Kunen), those subsets of PUS that are functions :

$$f : S \mapsto \bigcup S \land f = \{\langle E,e\rangle : (e \in E \land E \in S \land \text{only 1 element e from each E appears}) \} $$

i.e. are Choice Functions, can be split off from PUS to form a new set ACPUS:

$$ ACPUS = \{ \text{all conceivable choice functions for the set S} \} $$

Question : What is the intuition for why the Power Set Axiom considered to say "containing every conceivable subset" can not be used to derive the set ACPUS, which contains every conceivable axiom of choice function for the set S (i.e. why can't ACPUS always be non empty - if it was always non empty then AC would not be independent of ZF, presumably, since there would always be a choice function) ? The above reasoning also appears to show that "AC is not independent of ZF if the Cantor proof is true", so all help gratefully appreciated.

Answer 1

The axioms of ZF don't say that all conceivable sets are present. In fact, they don't mention "conceivable" at all. They have nothing to say about what we can conceive.

The axiom of power set says that, given a set $A$, there is a set $P(A)$ containing all subsets of $A$, but here (as in all of mathematics) "all" means "all in the universe of discourse", and that might not include everything you regard as conceivable. (Tangential remark: It could also be the other way around. The universe of discourse might contain sets that I can't conceive, perhaps because they're too random to think about or focus on.)

The only guarantee ZF gives you about sets actually being in the universe of discourse is the information in the existence axioms (especially but not exclusively, the axiom scheme of separation).

Part of the intuition underlying the axiom of choice is exactly to make sure the universe of discourse contains some things (like choice functions) that we can't describe explicitly and thus can't get from the other axioms.

Your argument could probably be turned into a philosophical reason for believing that the axiom of choice is true, but being true is quite different from being deducible from the ZF axioms.

If you want an axiom system in which your argument can be carried out, that axiom system would have to include a notion of "conceivable" and enough axioms about conceivability to justify the steps in your argument.

Answer 2

Andreas wrote a wonderful answer. Let me present his argument in a different light.

The role of the axioms of $\sf ZF$ is to prove that certain sets exist. But existence is relative to a universe of set theory, or a universe of mathematics for that matters.

Power set simply says that given a fixed universe of set theory, and a set $A$ in that universe, there is one set which collects all of the subsets of $A$ in that universe.

It is true that $\sf ZF$ is so expressive and strong as a foundation of mathematics that much of what we, as people, can conceive in some explicit way turns up to have an interpretation and a representation in the set theoretic foundation of $\sf ZF$. But this doesn't mean that this is how we go about doing mathematics.

Consider a choice function selecting an element from every non-empty subset of $\Bbb R$. Which rational number it chose? Which transcendental number was chosen? Which number is chosen from the Vitali set which is defined from that function? If the function is "so conceivable", then this should be too.

The fact of the matter is that you can't build something out of nothing. It is often a helpful crutch, philosophically speaking, to work in a static and fixed universe of mathematics. What's there is there, and what's not is not. So it's not about conceivable, it's about which sets are available.

Unfortunately, though, without the Axiom of Choice, it is not guaranteed that choice functions are available to us.

Answer 3

To add a bit to the good answers already posted:

The reasoning in your question is correct in drawing a connection between the Axiom of Choice ($AC$) and the notion of “largeness” or “maximality” of powerset. In that regard, you might be interested in this paper by Jose Ferreiros.

We have an intuitive notion of perhaps wanting the powerset of $X$ to be “maximal” in the sense described by Paul Bernays (quoted in aforementioned paper) when articulating the notion of a “maximal” powerset of $\mathbb{N}$:

One views a set of integers as the result of infinitely many independent acts deciding for each number whether it should be included or excluded. We add to this the idea of the totality of these sets.

That is, every subset that could possibly be generated by “flipping a coin” independently for each number to decide whether it’s in or out.

The problem is that while this notion of “maximality” is intuitively clear (or at least it seems so to me), there is no way (at least no known way) to formally describe and axiomatize it in first-order logic. The Powerset Axiom only says that in a given model of $\mathsf{ZF}$, there is a set whose members are exactly those subsets of $X$ which actually exist in the model; it does not provide any guarantee of which subsets exist in the model.

But, as Ferreiros’s paper describes, the Axiom of Choice guarantees us, if not “maximality”, at least a certain notion of “largeness” of powerset over and above what’s guaranteed by the Comprehension Axiom Schema. Namely, $AC$ guarantees that $\mathcal{P}(X \times \bigcup X)$ does indeed include an element which is a choice function for $X$. Conversely, without an explicit Axiom of Choice, there can be models of $\mathsf{ZF}$ in which the choice functions don’t necessarily exist, i.e. $\mathcal{P}(X \times \bigcup X)$ doesn’t necessarily include a subset which would constitute a choice function for $X$.