9
$\begingroup$

One of my favorite formulations of the Axiom of Choice is that for any nonempty family $A$ of nonempty sets, there is a choice function $F\colon A\to\cup A$ such that $F(X)\in X$ for each $X\in A$.

Using this, I was able to prove that there is also a function $f\colon\cup A\to A$ such that $x\in f(x)\in A$ for all $x\in\cup A$. I did this by considering any $x\in\cup A$, and letting $B_x=\{X\in A\mid x\in X\}$, and then letting $C=\{t\in\mathscr{P}(A)\mid \exists_{x\in\cup A}t=B_x\}$, i.e. $C$ is the set of all $B_x$. Now each $B_x$ is nonempty, so there is a choice function $F$ such that $F(B_x)\in B_x$ for each $B_x$. Defining $f(x)=F(B_x)$, I have $x\in f(x)\in A$ for every $x\in\cup A$. I suppose this is what I mean by a "backwards" choice function, even though it's not really one.

Is this equivalent to AC? That is, if for any set $A$, there exists a function $f\colon\cup A\to A$ such that $x\in f(x)\in A$ for all $x\in\cup A$, then AC holds? I couldn't immediately see a way to imply the Axiom of Choice, in any equivalent formulation assuming that the above is true for any set $A$. Is it just a one way implication? Thanks.

  • 1
    @IainM: I would read "this function requires choice" as $AC \implies \exists f$ while "the existence of this function implies choice" as $\forall A \exists f \implies AC$, so they would be converses.2011-05-08

3 Answers 3

7

An answer to a related question I gave some time ago happens to answer your question. I'm posting it here as well:

This is equivalent to the axiom of choice. Take a set $X$ of non-empty sets. Let the set $X'= X\cup\{\{x\} : x\in\bigcup X\}$ and for every $x\in\bigcup X$ take $C_x=\{y\in X' : x\in y\}$. Observe that if $x\neq y$ then $C_x\neq C_y$ since $\{x\}\in C_x$ while $\{x\}\notin C_y$. The set $A=\{C_x : x\in\bigcup X\}$ is a set through the axiom of replacement and you have that $\bigcup A=X'$. If there is a function $f:X'\to A$ satisfying the statement you wrote you have a choice function $g$ for $X$, namely $g(y)=x\iff f(y)=C_x$.

  • 0
    I see, thanks again.2011-05-08
4

Yes. Define A' = \{(a,b) : b \in a \in A\}. Then for any $a \in A$ we have \{a\} \in \bigcup A' (taking the definition of the ordered pair to be $(a,b) = \{\{a\},\{a,b\}\}$). So if $g$ is a backwards-choice function on A', $g(\{a\})$ is an ordered pair $(a,f(a))$, where $f(a) \in a$. So the $f$ defined in this way is a choice function on $A$ (with the usual definition).

2

No, this construction works perfectly in ZF.

HINT: Write your $f$ as the composition: $\bigcup A \rightarrow \coprod A \rightarrow A$, where $\coprod A$ is the disjoint sum of elements of $A$.


Sorry, I answered a wrong question. I think the answer to your question is: yes, they are equivalent.

Consider any surjection $f \colon A \rightarrow B$, and, without loss of generality, assume that both $A$ and $B$ are disjoint. Then form a family $F = \{ \{a, f(a)\} \colon a \in A \}$. Since $f$ is surjective, $\bigcup F = A \cup B$. So, thanks to your axiom, there is a function $h \colon A \cup B \rightarrow F$ such that $b \in h(b)$. There is also an obvious projection $p = \{\langle t, a \rangle \colon a \in t\} \colon F \rightarrow A$ --- that is $p(\{a, b\}) = a$. Composing these two functions with the obvious injection $\iota_B \colon B \rightarrow A \cup B$ gives a section of $f$, that is $p \circ h \circ \iota_B \colon B \rightarrow A$, what is just another formulation of AC (i.e. every surjection has a section).

  • 0
    Sorry, I a$n$swered a wrong question. I have edited my answer, and now it should address your question correctly :-)2011-05-08