Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
I'm having trouble understanding why you flagged your own post to say it was one of your own exam questions. If this is an ongoing exam, this seems like a breach of confidence and I advise you to remove your question. If not, then there is no reason to flag it. – mixedmath Nov 30 '12 at 18:14

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.