Using a choice function to find an inverse for $F\colon A\to P(B)$

Question

Let $A$ and $B$ be arbitrary non-empty sets and let $F\colon A\to P(B)$, be an arbitrary function which covers $B$ in the sense that $\forall b \in B$, $\exists a \in A$ such that $b \in F(a)$ holds.

Using axiom of choice show there exists a function $G: B \rightarrow A$ ,such that for all $b\in B$, $b \in F(G(b))$

Answer 1

For $b\in B$ let $C(b):=\{a\in A\mid b\in F(a)\}$. Then $S:=\{C(b)\mid b\in B\}$ is a nonempty (because $B$ is nonempty) set of nonempty (because $\forall b\in B\colon \exists a\in A\colon b\in F(a)$) sets. By AC there is a function $f$ defined on $S$ such that $f(s)\in s$ for all $s\in S$. Define $G(b) = f(C(b))$. Then $f(C(b))\in C(b)$ implies $b\in F(f(C(b)))=F(G(b))$.

Answer 2

The axiom of choice states that given a collection of non-empty sets $\mathcal A=\{A_i\mid i\in A\}$ there is a function such that $F(A_i)\in A_i$. Such $F$ is called a choice function for the family $\cal A$. It should be remarked that there are plenty of instances where the axiom of choice is really needed for proving that such function exists for a certain family.

So now suppose that $F\colon A\to P(B)$ as described. By the covering property we have that for every $b\in B$ the set $A_b=\{a\in A\mid b\in F(a)\}$ is non-empty. Therefore the family $\{A_b\mid b\in B\}$ is a family of non-empty sets, and by the axiom of choice there is a choice function defined for it.

Let $g$ be a choice function from the family $\{A_b\mid b\in B\}$, we have that $g(A_b)\in A_b$. Let now $G(b)=g(A_b)$, and we have that $G(b)\in A_b$ so by definition $b\in F(G(b))$, as wanted.

---

It is impossible to solve this question with a weak choice principle (namely an assertion implied by the axiom of choice, but not equivalent to the axiom of choice).

To see this note that if $\{A_i\mid i\in I\}$ is a family of non-empty sets we can take the function $F\colon\bigcup_{i\in I}A_i\to P(I)$ defined as $F(a)=\{i\in I\mid a\in A_i\}$. Then $F$ covers $I$ because for every $i\in I$ we have some $a\in A_i$ and then $i\in F(a)$ for such $a$.

Suppose that $G\colon I\to\bigcup_{i\in I}A_i$ is such that $F(G(i))=i$ then $G(i)\in A_i$ and therefore $G$ is a choice function for $\{A_i\mid i\in I\}$.

So if the principle of "splitting a covering function" holds every family of non-empty sets has a choice function, i.e. the axiom of choice holds.