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$. As Bjørn Kjos-Hanssen pointed out, choice sets do not always exist.

What is an example of a set $X$ and a cover ${\cal S}$ such that for no cover ${\cal S}_0 \subseteq {\cal S}$ there is a choice set for ${\cal S}_0$?


Well order $X$ and at stage $\alpha$ let $d_\alpha$ be the first element of $X\setminus \bigcup_{\xi<\alpha}\bigcup\{S \in \mathcal S: d_\xi \in S \}$ (if this set was empty we stop and let $\gamma=\alpha$). Then $D=\{d_\alpha: \alpha <\gamma\}$ is a choice set for the subcovering $\mathcal S_0=\{S \in \mathcal S: S\cap D \neq \emptyset \}$.

| cite | improve this answer | |
  • $\begingroup$ Thank you Ramiro for putting this so clearly & concisely! $\endgroup$ – Dominic van der Zypen Nov 10 '17 at 12:40
  • $\begingroup$ @BjørnKjos-Hanssen: No, it is not the same construction. To see that $|S\cap D|=1$ for $S \in \mathcal S_0$, note that if $d_\xi \in S$ then for each $\alpha>\xi$, $d_\alpha$ was chosen in $X \setminus S$. So $\xi$ is the least index (and hence the only index) for which $d_\xi \in S$. $\endgroup$ – Ramiro de la Vega Nov 10 '17 at 14:55
  • $\begingroup$ I meant to say "largest index" instead of "least index". $\endgroup$ – Ramiro de la Vega Nov 10 '17 at 15:02

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.