0
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.