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?

  • 6
    $\begingroup$ 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. $\endgroup$ – bof Nov 13 '17 at 10:09
  • $\begingroup$ 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 :-)) $\endgroup$ – 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]$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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