Let $\kappa$ be an infinite cardinal and let ${\cal S}$ be a collection of non-empty subsets of $\kappa$ such that $|{\cal S}| = \kappa$. A map $f:{\cal S} \to \kappa$ is said to be a choice function if $f(S)\in S$ for all $S\in{\cal S}$.

This post is about injective choice functions. For the existence of an injective choice function, it is easy to see that Hall's condition is necessary:

For any subset ${\cal T}\subseteq {\cal S}$ we have $|{\cal T}| \leq |\bigcup {\cal T}|$.

However, this condition is not sufficient: Pick $\kappa = \omega$ and set $${\cal S} = \big\{\{n\}:n\in\omega\big\} \cup\big\{\omega\big\}.$$ It is easily verified that Hall's condition holds for ${\cal S}$, but ${\cal S}$ has no injective choice function. Informally speaking, the problem with ${\cal S}$ is that it has lots of small sets.

For any infinite cardinal $\kappa$ and any collection ${\cal S}$ of non-empty subsets of $\kappa$ such that $|{\cal S}| = \kappa$ we set ${\cal S}_{<\kappa} = \{S\in{\cal S}: |S|<\kappa\}$.

Question. If Hall's condition holds for ${\cal S}$ and $|{\cal S}_{<\kappa}|<\kappa$, does ${\cal S}$ have an injective choice function?

  • $\begingroup$ You can consider your example as subsets of $\omega_1$ (adding some big junk to make it of size $\aleph_1$). Now it would have only a few small sets but still has no injective choice function. $\endgroup$ – Ramiro de la Vega Jul 26 '17 at 11:29
  • $\begingroup$ You have to reformulate the question as each family satisfying the Hall condition can be embedded into a family satisfying the condition in the question. $\endgroup$ – Péter Komjáth Jul 26 '17 at 11:31
  • $\begingroup$ There is a vast literature of this by Milner, Nash-Williams, and especially by Aharoni. See, e.g,Aharoni, R.; Nash-Williams, C. St. J. A.; Shelah, S. A general criterion for the existence of transversals. Proc. London Math. Soc. (3) 47 (1983), no. 1, 43–68. $\endgroup$ – Péter Komjáth Jul 26 '17 at 11:35
  • $\begingroup$ Thanks Ramiro and Peter for your comments! I'm not sure whether to delete the question, or Ramiro could you add your comment as an answer so we can close this thread? Either is fine for me $\endgroup$ – Dominic van der Zypen Jul 26 '17 at 11:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.