3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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
    Commented Nov 13, 2017 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
    Commented Nov 13, 2017 at 11:53

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .