Critical coverings of $\omega$

Question

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal U}\to X$ is called a choice function if $f(A)\in A$ for all $A\in {\cal U}$. A marriage is an injective choice function.

We say that ${\cal U}$ is critial if

1. there is a marriage $f:{\cal U}\to X$, and
2. every marriage $f:{\cal U}\to X$ is surjective.

Is there a critical covering of $\omega$ consisting of infinite sets only?

Answer 1

The answer is no.

If $\mathcal{U}$ is a covering of $\omega$ such that a marriage exists, then $\mathcal{U}$ is countable. Set $\mathcal{U}=\{U_i: i\in\omega\}$, and suppose each $U_i$ is infinite. Then (for $k$ fixed) let

• $a_0$ be the least element of $U_0$ greater than $k$, and

• $a_{n+1}$ be the least element of $U_{n+1}$ which is greater than $a_n$.

The map $U_i\mapsto a_i$ is a marriage whose range does not intersect $\{0, 1, . . ., k\}$, and in particular is not surjective.

A similar trick can be done to avoid an infinite set of elements: replace "least" with "second least" in the above.