# Choice sets from above and below

Let $X\neq \emptyset$ be a set and let ${\cal S} \subseteq {\cal P}(X)\setminus\{\emptyset\}$ be a collection of non-empty subsets of $X$. We say $C\subseteq X$ is a choice set for ${\cal S}$ if $|C\cap s| = 1$ for all $s\in S$. Moreover, we say that

1. $D\subseteq X$ is shy if $|D\cap s| \leq 1$ for all $s\in S$; and
2. $E\subseteq X$ is gregarious if $|E \cap s| \geq 1$ for all $s\in S$.

Trivially, $\emptyset$ is shy, and $X$ is gregarious. Zorn's Lemma shows that every shy set is contained in a choice set. (It is straightforward to check that a union of a chain of shy sets is shy; and that a maximal shy set is a choice set.)

But on the other hand, not every gregarious set contains a choice set: Let $X = [0,1]$, $E = X$ and let ${\cal S} = \{]0, \frac{1}{n}[: n\in \mathbb{N}, n\geq 1\}$.

I find this a curious asymmetry that "from below" there is always a choice set, but not necessarily "from above"!

However: Let $D\subseteq X$ be such that $|D\cap s|$ is finite for all $s\in {\cal S}$.

Question. Does $D$ contain a choice set in that case?

• I think $D$ should be called $\cal S$ and $\cal S$ should be called $E$ in the example. – Bjørn Kjos-Hanssen Nov 7 '17 at 6:52
• You are right! And also about the non-existence of choice sets -- thanks! – Dominic van der Zypen Nov 7 '17 at 8:40
• One usually uses this kind of choice set when the sets in S are pairwise disjoint. Otherwise, as the examples show, you cannot necessarily have them, even with the axiom of choice. – Joel David Hamkins Nov 7 '17 at 12:35

Let $\cal S=\{\{1,2\},\{2,3\},\{3,1\}\}$.
Then $\cal S$ has no choice set, whatsoever.