3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I think $D$ should be called $\cal S$ and $\cal S$ should be called $E$ in the example. $\endgroup$ – Bjørn Kjos-Hanssen Nov 7 '17 at 6:52
  • $\begingroup$ You are right! And also about the non-existence of choice sets -- thanks! $\endgroup$ – Dominic van der Zypen Nov 7 '17 at 8:40
  • 2
    $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Nov 7 '17 at 12:35
8
$\begingroup$

Let $\cal S=\{\{1,2\},\{2,3\},\{3,1\}\}$.

Then $\cal S$ has no choice set, whatsoever.

So there is no asymmetry -- not every shy set is contained in a choice set, and not every gregarious set contains a choice set.

$\endgroup$

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.