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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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