Size of smallest set in critical covering 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 critical if

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

As Noah Schweber showed in his post, critical coverings of $\omega$ need to contain at least a finite set.

Given $n\in \omega$ is there a critical covering ${\cal U}$ of $\omega$ such that every member of ${\cal U}$ contains at least $n$ elements? (I would also appreciate to know whether it's possible that ${\cal U}$ contains only finitely many finite sets, but this is a side question.)

Answer 1

The answer to your main question is "yes":

• Fix $n$.

• Partition $\omega$ into disjoint $A_i$s, where each $A_i$ has cardinality $n+1$.

• Now let $\mathcal{U}=\{S: \exists i(S\subset A_i, \vert S\vert=n)\}.$

The point is we have broken $\omega$ into finite pieces, and on each finite piece $\mathcal{U}$ has exactly as many elements as there are points in that piece.

---

The answer to your side question, meanwhile, is no:

If $\mathcal{U}$ contains only finitely many finite sets, then let $f$ be a marriage of $\mathcal{U}$ and let $n\in\omega$ be some element not in any finite element of $\mathcal{U}$. We can now - by a similar argument to my previous answer - shift the original marriage $f$ to get one which omits $n$. Similarly, we can omit any bi-infinite subset of $\omega$ which does not intersect any of the finite pieces, or contain all-but-finitely-much of any element of $\mathcal{U}$.