Is there a set $X\neq\emptyset$ and a collection ${\cal F}\subseteq {\cal P}(X)\setminus\{\emptyset\}$ of non-empty subsets of $X$ with the following properties?

  1. $a\in {\cal F} \implies |a|\geq 2$,
  2. $a\neq b\in {\cal F} \implies |a\cap b| \leq 1$, and
  3. there is no function $f: {\cal F} \to X$ such that
    • $f(a) \in a$ for all $a\in {\cal F}$, and
    • if $a, b\in {\cal F}$ with $a\cap b\neq \emptyset$ then $f(a)\neq f(b)$?
  • 2
    $\begingroup$ Of course $fa)\ne f(b)$ if $a\cap b=\emptyset$ so you could have just said $f$ is injective. Your selector can't exist if $|\mathcal F|\gt|X|$ so $\mathcal F=\binom X1+\binom X2$ is a counterexample if $|X|\ge2.$ $\endgroup$ – bof Jan 11 '16 at 14:25
  • $\begingroup$ Sorry forgot criterion 1 $\endgroup$ – Dominic van der Zypen Jan 11 '16 at 16:20

Satisfying the new Condition 1, If $|X|\geqslant4$, let ${\cal F}$ consist of all subsets of $X$ with two elements.

Condition 1 can be weakened. For example, if $X=\{a_{i,j}:1\leqslant i,j\leqslant 3\}$, then the following 12 subsets, each of size 3, satisfy the conditions. $$ \{a_{1,1},a_{1,2},a_{1,3}\},\{a_{2,1},a_{2,2},a_{2,3}\},\{a_{3,1},a_{3,2},a_{3,3}\} $$ $$\{a_{1,1},a_{2,1},a_{3,1}\},\{a_{1,2},a_{2,2},a_{3,2}\},\{a_{1,3},a_{2,3},a_{3,3}\} $$ $$ \{a_{1,1},a_{2,2},a_{3,3}\},\{a_{1,3},a_{2,2},a_{3,1}\} $$ $$ \{a_{1,1},a_{2,3},a_{3,2}\},\{a_{1,3},a_{2,1},a_{3,2}\},\{a_{1,2},a_{2,1},a_{3,3}\},\{a_{1,2},a_{2,3},a_{3,1}\} $$

It seems likely that we can permit any minimum size for sets in ${\cal F}$.

  • $\begingroup$ Provided $|X|\gt1.$ $\endgroup$ – bof Jan 11 '16 at 21:36

Let ${\cal F}$ consist of all subsets with one element and, in addition, the whole set $X$. We must have $f(\{a\})=a$, which leaves no possibility for $f(X)$.


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.