Prove that the statement implies the Axiom of Choice

Question

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.

Answer 1

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

Answer 2

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