# Choice sets and the axiom of choice

Let $X\neq \emptyset$ be a set. We say ${\cal C} \subseteq {\cal P}(X)\setminus\{\emptyset\}$ is a cover if $\bigcup {\cal C} = X$. A subset $D\subseteq X$ is a choice set for ${\cal C}$ if $|D\cap c| = 1$ for all $c\in C$.

Ramiro de la Vega showed in his nice post that

(S): every cover has a subcover that admits a choice set.

He used the Axiom of Choice to well-order the members of the cover and construct a subcover with a choice set.

Question. Does the statement (S) above imply the Axiom of Choice?

• The assertion "every family of pairwise disjoint nonempty sets has a choice set" is well known to be equivalent to the axiom of choice, in fact, I think it used to be the standard formulation of the axiom of choice. Of course, if $\mathcal C$ is a family of pairwise disjoint nonempty sets, then $\mathcal C$ is a cover of $\bigcup\mathcal C$ with no proper subcover. – bof Nov 13 '17 at 10:09
• To be precise, according to Patrick Suppes, Zermelo stated AC as: "every set of pairwise disjoint nonempty sets has a choice set"... But it's interesting history, of which I was unaware. (Apart from the history I'm naturally biased of course to consider the answer below both shorter and more to the point, you can blame my ego for that :-)) – Franka Waaldijk Nov 13 '17 at 11:53

Let $P\subseteq X\times Y$ be sets such that $\forall x\in X\exists y\in Y[(x,y)\in P]$. We wish to derive from (S) the existence of an $f\subseteq P$ such that $\forall x\in X\exists! y\in Y[(x,y)\in f]$.
Consider the following cover of $P$. Let $\cal{C}$ $:= \{\{(x,y)|y\in Y, (x,y)\in P\}|x\in X\}$. Notice that any subcover of $\cal{C}$ has to be $\cal{C}$ itself.
Let $f$ be a choice set for $\cal{C}$, then trivially $f\subseteq P$ and $\forall x\in X\exists! y\in Y[(x,y)\in f]$.