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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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 \}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you Ramiro for putting this so clearly & concisely! $\endgroup$
    – Dominic van der Zypen
    Commented Nov 10, 2017 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
    Commented Nov 10, 2017 at 14:55
  • $\begingroup$ I meant to say "largest index" instead of "least index". $\endgroup$
    – Ramiro de la Vega
    Commented Nov 10, 2017 at 15:02

You must log in to answer this question.

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