1
$\begingroup$

I'm reading the book on Injective choice functions by Holz, Podewski and Steffens, and I find it to be at the same time well written and quite difficult. It has almost no examples - and in quite a few situations I wasn't able to come up with examples myself (not due to lack of trying, but rather lack of skill). So that's what this thread is about.

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.

I would like to see examples of the following:

  1. Is there a critical covering on an infinite set $X$ that contains no singletons, and at least one member of the covering is infinite? (Noah Schweber demonstrated here that at least one member of any critical covering has to be finite.)
  2. Is there a critical covering ${\cal U}$ on $\omega$ such that $$\bigcup \{F\in {\cal U}: F\text { is finite}\} \neq \omega$$?

Edit I added label graph-theory because marriages in this context are matchings in a bipartite graph.

$\endgroup$
  • $\begingroup$ For (1), can you let $X$ be $\mathbb{Z}$, and let $\mathcal{U}$ be $\mathbb{Z}$ along with each successive pair of integers? $\endgroup$ – Paul Larson Jul 20 '16 at 15:40
  • $\begingroup$ For (2), can you let $\mathcal{U}$ be $\omega$ along with each set of the form $n \setminus \{0\}$, for $n \geq 2$? $\endgroup$ – Paul Larson Jul 20 '16 at 15:47
  • $\begingroup$ Hi Paul -- thanks for your examples, can you put them in a answer along with a hint of why they are critical? $\endgroup$ – Dominic van der Zypen Jul 20 '16 at 19:39
2
$\begingroup$

For any fixed $n\in\mathbb N,$ there is a critical covering $\mathcal U$ of $\omega$ such that each finite member of $\mathcal U$ contains exactly $n$ elements, and one member of $\mathcal U$ is infinite; moreover, $\bigcup\{F\in\mathcal U:F\text{ is finite}\}\ne\omega.$

Namely, let $$\omega=A\cup B_1\cup B_2\cup B_3\cup\cdots$$ where $A,B_1,B_2,B_3,\dots$ are pairwise disjoint sets, $|A|=1,$ and $|B_i|=n+1$ for each $i,$ and let $$\mathcal U=\{\omega\}\cup\binom{B_1}n\cup\binom{B_2}n\cup\binom{B_3}n\cup\cdots.$$

$\endgroup$
1
$\begingroup$

For (1), I think you can let $X$ be $\mathbb{Z}$ and let $\mathcal{U}$ be $\mathbb{Z}$ along with each successive pair of integers. Then, by symmetry, it doesn't matter which point you pick for $\mathbb{Z}$, but once you have picked this point all the other choices are determined by iteratively picking the one point remaining for those sets with one unpicked point left.

For (2), I think you can let $\mathcal{U}$ be $\omega$ along with each set of the form $n \setminus \{0\}$ for $n \geq 2$. Then the set $\{1\}$ has to pick $1$, the set $\{1,2\}$ has to pick $2$, and so on, leaving $\omega$ to pick $0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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