# Prove that the statement implies the Axiom of Choice

Prove that the following statement implies the Axiom of Choice:

Let $C$ is a set (of sets) and $B$ is a set such that for all $c \in C$, there exists a $b \in B$ such that $b \not\in c$. Then there is a function $F: C \to B$ such that $F(c) \not\in c$.

In other words, we're given an "anti-choice" function that gives us elements not in each set.

Any "usual" formulation of the Axiom of Choice (choice function, non-empty Cartesian product, Zorn's, etc.) is fine.

Attempt at solution: The usual formulations of the AC involve picking out elements out of sets. However, here we are given a way of picking out things not in a set.

My first attempt was to show the existence of a choice function. So let $A$ be a set (of sets). Applying $F$ to this domain gives us an element in $B$ (unspecified so far) not in $A$. So here is where I get stuck. Given an element not in $a \in A$, I don't see how I can map this to an element in $a$.

Something a little more clever must be done.

For each element $a \in A$, I considered the union of $A-\{ a \}$ (call this mapping $g$). Let's call $$C = \{ \cup (A-\{ a \}) \mid a \in A \}$$

and set $B$ to be $\cup A$. If the sets in $A$ were disjoint, then $F \circ g$ would give us the desired choice function. But for disjoint sets, I am again stuck.

• $\big\{a\times\{a\}:a\in A\big\}$ is a pairwise disjoint family that corresponds in an obvious and natural way to $A$ itself. (This is a standard trick for ‘disjointing’ a family.) – Brian M. Scott Dec 14 '12 at 10:46
• @BrianM.Scott: Oh nice, I have not seen this trick before! Well I think that solved my problem. If you add that as an answer, I'd be happy to upvote. – tskuzzy Dec 14 '12 at 10:49
• I can do that; it’ll take a couple of minutes. – Brian M. Scott Dec 14 '12 at 10:52

$\big\{a\times\{a\}:a\in A\big\}$ is a pairwise disjoint family that corresponds in an obvious and natural way to $A$ itself. (This is a standard and very useful trick for ‘disjointing’ a family of sets.)
It is enough to show that for every non-empty set $X$ there is a choice function on $P(X)\setminus\{\varnothing\}$.
Use this formulation to show that this is actually a choice function from the complement set, i.e. set $C=P(X)\setminus X$ and $B=X$, and $F(Y)\notin Y$ is exactly a choice function from $X\setminus Y$.