# Subcovers without a choice set

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 \}$.
• @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$. – Ramiro de la Vega Nov 10 '17 at 14:55