8
$\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.

  • 0
    On the surface it seems similar to how the fact that every surjective map can be inversed to a subset of the domain, I do not recall if this is equivalent or strictly weaker than choice. (I will try to write some proof anyway.)2011-05-08
  • 0
    There is a chance this is a duplicate (I didn't read the question very carefully -I've got to go- so sorry if it's not): http://math.stackexchange.com/q/29772/17722011-05-08
  • 0
    @Apostolos: This seems to be the inverse question. Whether this function requires choice. In here the question is if the existence of this function implies choice.2011-05-08
  • 0
    @Asaf: You are right, but it just happens that to answer the question Carl and I essentially provided an answer to yunone's question (and that's probably the reason I thought they were the same).2011-05-08
  • 0
    @Asaf: Surely "this function requires choice" and "the existence of this function implies choice" are just different ways of saying the same thing?2011-05-08
  • 0
    @IainM: It is a subtle argument which is a very good example of how problematic natural language can be, namely the fact that every infinite set has a countable subset requires countable choice, but it can happen in its absence. Another example is the ultrafilter lemma - which is strictly weaker.2011-05-08
  • 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
    Thanks for your answer Apostolos. Is it necessary that $x\neq y\implies C_x\neq C_y$?2011-05-08
  • 0
    @yunone: Yes it is, because of how $g$ is defined. Assume that we have $x\neq y$ while $C_x=C_y=C$ and there is a $z$ such that $f(z)=C$. Then we would require to somehow *choose* either $x$ or $y$ for $g(z)$, and it is not clear how that would be possible without using some choice. Actually when I first answered the question I link to I missed this fact as well. You can read the comments at my answer there as well as Carl's answer for a different approach that again needs some sort of coding of extra information.2011-05-08
  • 0
    I see, thanks again.2011-05-08
3

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
    How can you go from $\bigcup A$ to $\coprod A$?2011-05-08
  • 0
    Sorry, I answered a wrong question. I have edited my answer, and now it should address your question correctly :-)2011-05-08