I'm trying to prove the following statement is equivalent to the Axiom of Choice:

"For any set $A$, there exists a function $F$ with dom $F = ⋃A$ and for each $x ∈ ⋃A$, $x ∈ F(x) ∈ A$." (1)

The resemblance is uncanny to the choice function version of the Axiom of Choice, which I interpret loosely to say that for any collection of nonempty sets, you can pick a member from each set in the collection. This statement (1) seems to be saying that for any set $S$, for each $T ∈ S$, you can pick exactly one "representative" $x ∈ T$.

I managed to show that the Axiom of Choice proves (1), but can't get that (1) proves the Axiom of Choice. I was given advice to try to use this specific form of the Axiom of Choice: "For any relation $R$, there exists a function $f$ with $f ⊆ R$ and dom $f =$ dom $R$." However, I'm not sure how exactly to use (1) to refine any relation $R$ to a function.

Any hints or input would be much appreciated.

  • $\begingroup$ The statement (1) seems to say that given $x \in \bigcup\bigcup A$ you can select $B \in \bigcup A$ with $x \in B \in A$; the last sentence of the third paragraph seems a little off. $\endgroup$ – Carl Mummert Nov 4 '14 at 22:56
  • $\begingroup$ In the future, please search the site before posting. $\endgroup$ – Asaf Karagila Nov 5 '14 at 4:18

If we have an instance $G$ of the axiom of choice, replace each set $B\in G$ with the set of all pairs $B' = \{ \{(0,B), (1,x)\}: x \in B\}$. Note $B'$ is a set of unordered pairs of ordered pairs.

Let $$G' = \bigcup \{ B' : B \in G\} = \{ \{(0,B), (1,x)\} : x \in B \in G\}.$$ Apply your principle to $G'$ to obtain a function $f$ as described in the question.

Then, given $B$, we can define an $x \in B$ as the unique $x$ such that $f(B) = \{(0,B),(1,x)\}$. This gives us a choice function for $G$, which was the goal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.