# Selection problem in a collection of non-empty sets

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)$?
• 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.$ – bof Jan 11 '16 at 14:25
• Sorry forgot criterion 1 – Dominic van der Zypen Jan 11 '16 at 16:20

## 2 Answers

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}$.

• Provided $|X|\gt1.$ – 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)$.