# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.7218711,"math_prob":0.9999745,"size":441,"snap":"2019-51-2020-05","text_gpt3_token_len":157,"char_repetition_ratio":0.16475973,"word_repetition_ratio":0.05,"special_character_ratio":0.36734694,"punctuation_ratio":0.06122449,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000077,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-24T01:15:58Z\",\"WARC-Record-ID\":\"<urn:uuid:4e38cc73-aef9-478c-99c8-b0bb1399305c>\",\"Content-Length\":\"116094\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:35f32cca-89e3-4fe1-92ef-26e54d2daa09>\",\"WARC-Concurrent-To\":\"<urn:uuid:5d0719a7-dfef-4554-a053-30d655380f1f>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/285687/subcovers-without-a-choice-set\",\"WARC-Payload-Digest\":\"sha1:IMW6TESHUW2ZLHQAPO6CCKEO7KH3QKLX\",\"WARC-Block-Digest\":\"sha1:WSBY35MCZGRE2ZI6C47MYLMFWRJLMSGL\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250614880.58_warc_CC-MAIN-20200124011048-20200124040048-00393.warc.gz\"}"}