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$
3
  • 1
    $\begingroup$ I think $D$ should be called $\cal S$ and $\cal S$ should be called $E$ in the example. $\endgroup$ Commented Nov 7, 2017 at 6:52
  • $\begingroup$ You are right! And also about the non-existence of choice sets -- thanks! $\endgroup$ Commented Nov 7, 2017 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$ Commented Nov 7, 2017 at 12:35

1 Answer 1

9
$\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$

You must log in to answer this question.

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