Proving equivalence of Axiom of Choice

576 Views Asked by At

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.

1

There are 1 best solutions below

15
On

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.