# Proving equivalence of Axiom of Choice

I am working on the following question concerning the axiom of choice and one of its many equivalences. Advice as to whether I am on the right track would be appreciated. As a preface, I have looked at most of the other 'axiom of choice' posts on math.stackexchange already so referencing me to them may not help me a whole lot as I am asking this question $after$ having read those posts. In any case, I may have missed something in these posts so please do recommend a post if you think it will help me. Thank you very much for your time, in advance.

We show that the following statement is equivalent to the axiom of choice: For any set $A$, there is a function $F$ with $dom \ F = \bigcup A$ such that $x \in F(x) \in A$ for all $x \in \bigcup A$. Call this statement $S$.

To prove that $S$ is equivalent to the axiom of choice, we show that $S$ holds iff version 4 of the axiom of choice holds (p.151): Let $A$ be a set such that (a) each member of $A$ is a nonempty set, and (b) any two distinct members of $A$ are disjoint. Then there exists a set $C$ containing exactly one element from each member of $A$ (i.e., for each $B \in A$, the set $C \cap B$ is a singleton $\{x\}$ for some $x$. Call this version $S'$.

First, we show that $S \ \implies \ S'$. Assume that $S$ holds and that $A$ is a set such that each member is a nonempty set and any two members of $A$ are disjoint. Then, there is a function $f$ such that $dom \ f = \bigcup A$ and $\forall x \in \bigcup A$ ($x \in f(x) \in A$). We now have $dom \ f \subseteq ran \ f \in A$, and so $ran \ f \neq \emptyset$ by the definition of $A$. Further, we have $ran \ f \ \cap \ B = \{f(x)\}$, for some $x \in A$ and for any $B \in A$. So $ran \ f = C$, and $S'$ holds where $C \cap B$, for any $B \in A$ is a singleton.

• Always lead with the question. People who want to help you would like to figure out quickly whether they can. Later, you can tell us why you are asking, if it's really important. – Thomas Andrews Aug 28 '14 at 4:50

I'm not sure why you have that $\operatorname{dom}(f)\subseteq\operatorname{ran}(f)$. Note that $x\in\operatorname{dom}(f)$ means that $x\in X\in A$, and $F(x)\in A$. Therefore $\operatorname{dom}(f)\subseteq\bigcup A$ and $\operatorname{ran}(f)\subseteq A$.

So you can't quite use $\operatorname{ran}(f)$ to define $C$.

Instead, consider $A'=\{\{A\times X,x\}\mid x\in X\in A\}$, and apply $S$ to $A'$, you get a function which chooses for each $X\in A$ and each $x\in X$ a pair that exactly one element of it is an element of $X$, so you can cook up $C$ as wanted.

• Asaf, thank you for your continuous help (you have answered many of my questions before). However, I don't understand what 'X' (big X) is referring to. Can you please define it? – letsmakemuffinstogether Aug 29 '14 at 3:17
• $X$ is just an element of $A$. – Asaf Karagila Aug 29 '14 at 3:19
• Okay but I am still confused. I don't understand how $x \in dom f$ entails that $x \in X \in A$ for any $X \in A$. I also don't understand why you have $dom f \subseteq \bigcup A$, when $dom f$ is simply equal to $\bigcup A$. I do however understand why it is false that $dom f \subseteq ran f$ and that I was wrong on this. – letsmakemuffinstogether Aug 29 '14 at 3:39
• If $\operatorname{dom}(f)=\bigcup A$, then $x\in\operatorname{dom}(f)$ means $x\in\bigcup A$, which in turn means that for some $X\in A$, $x\in X$. You are correct about $\operatorname{dom}(f)=\bigcup A$, but the point I wrote it for is that the domain and range of $f$ are subsets of different sets, which can easily be disjoint. Therefore they cannot [necessarily] satisfy any inclusion relations between them. Consider the case where $A=\{\{x\}\}$, then $\bigcup A=\{x\}$ and $f(x)=\{x\}$, so the range of $f$ is $\{\{x\}\}$. Is $\{x\}\subseteq\{\{x\}\}$? – Asaf Karagila Aug 29 '14 at 3:45
• Okay, I think there was simply misunderstanding as to quantification as what you were stating is that if $x \in dom f = \bigcup A$ then $x \in X \in A$ for $some \ X \in A$. – letsmakemuffinstogether Aug 29 '14 at 4:13