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$ Nov 7, 2017 at 6:52
  • $\begingroup$ You are right! And also about the non-existence of choice sets -- thanks! $\endgroup$ 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$ 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.