Let $X$ be an infinite set, and let ${\cal A}\subseteq{\cal P}(X)$ be a family of non-empty sets. We say $S\subseteq X$ is a cover for ${\cal A}$ if $A\cap S \neq \emptyset$ for all $A\in{\cal A}$.

Suppose that we have $A\neq B \in {\cal A}$ implies $|A\cap B|\leq 1$. Is there a cover $M\subseteq X$ for ${\cal A}$ such that for all $m\in M$ the set $M\setminus \{m\}$ is not a cover of ${\cal A}$?


I think I can do one case. Assume that $A_i\subseteq S$, $|A_i|=\aleph_0$ for $i\in I$, and $|A_i\cap A_j|\leq 1$ for $i\neq j$. By a theorem in the paper P. Komjáth: Families close to disjoint ones, Acta Math. Hung. 43 (1984), 199–204, there are cofinite sets $A'_i\subseteq A_i$ such that $\{A'_i:i\in I\}$ is disjoint.

Let $X$ be the following graph on $I$: $\{i,j\}\in X$ iff $(A_i-A'_i)\cap A'_j\neq\emptyset$. Given $i$ there is just finitely many $j$ as above, so there is an orientation of $X$ with all vertices having finite outdegrees. By an old result of Erdos and Hajnal, there is a well ordering $\prec$ of $I$ s. t. each vertex has only finitely many edges of $X$ going down. By transfinite recursion on $\prec$ pick $x_i\in A'_i$ for some $i\in I$ (let $I'$ be the set of those elements of $I$) as follows. If there is $j\prec i$ with $x_j\in A_i$, then set $i\notin I'$. Otherwise, pick $x_i\in A'_i-\bigcup\{A_j-A'_j:j\prec i\}$. This is possible, as the subtracted set is finite by the property of $\prec$. Now $B=\{x_i:i\in I'\}$ is obviously covering. Remove one element of it: $B'=B-\{x_i\}$ for some $i\in I'$. The way of the construction, $x_j\notin A_i$ for $j\prec i$. But there is no $i\prec j$ with $x_j\in A_i-A'_i$ either by the way $x_j$ was chosen, so $B'\cap A_i=\emptyset$.

  • 1
    $\begingroup$ Another easy, case: if ${\cal A}$ is an infinite collection of finite sets, then there is always a minimal covering by Zorn's lemma. $\endgroup$ – Péter Komjáth Aug 3 '17 at 15:24
  • $\begingroup$ Thank you Peter for these cases! As it is a partial answer (but a very valuable one) I hope you don't mind me not accepting yet. $\endgroup$ – Dominic van der Zypen Aug 3 '17 at 19:47
  • $\begingroup$ Yes, that's correct. $\endgroup$ – Péter Komjáth Aug 4 '17 at 21:15
  • $\begingroup$ In P. Komjáth, "Families close to disjoint ones," Acta Math. Hung. 43 (1984), 199–204, you state that you have a generalization of Theorem 2. What is it? And precisely what result of Erdos and Hajnal are you using (so I can look up the proof)? $\endgroup$ – Tri Nov 26 '17 at 20:21

[Incorrect answer, perhaps mendable, perhaps not, sorry, see my comments below]

The answer is yes, the statement is in fact equivalent to AC.

AC is equivalent to "every set of pairwise disjoint nonempty sets has a choice set". So to see that the statement implies AC we can let ${\cal A}\subseteq{\cal P}(X)$ consist of pairwise disjoint sets.

Let $M\subseteq X$ be a minimal cover for ${\cal A}$ , that is: for all $m\in M$ the set $M\setminus \{m\}$ is not a cover of ${\cal A}$. Then $M$ is a choice set for ${\cal A}$. $$ $$ To see that AC implies the statement, we use Zorn's lemma.

For given ${\cal A}\subseteq{\cal P}(X)$ with the property that $A\neq B \in {\cal A}$ implies $|A\cap B|\leq 1$, let $H\subset {\cal P}({\cal A})\times{\cal P}(X)$ be defined by: $$ $$ $$H := \ \{(K,L)\in {\cal P}({\cal A})\times{\cal P}(X)\ |\ L\ \mbox{is a minimal cover for}\ K\ \}$$

$$ $$ We define a partial order on $H$ using set-inclusion: $$(K,L)\leq(K',L'):= K\subseteq K' \wedge L\subseteq L'$$ $$ $$ For $J=(K,L)\in H$ let $J_0=K, J_1=L$ be the coordinate projections.

We verify that every ascending chain in $(H,<)$ has an upper bound. Let $G\subseteq H$ such that $<$ is a total order on $G$. Then the upper bound $T$ for $G$ is given by:

$$T = (\bigcup_{J\in G} J_0, \bigcup_{J\in G} J_1)$$

It is straightforward to see that $\bigcup_{J\in G} J_1$ is again a minimal cover for $\bigcup_{J\in G} J_0$, so indeed $T$ is in $H$.

It is easy to see that there are non-empty ascending chains. By Zorn's lemma, $(H,<)$ contains a maximal element $U=(V,W)$. We claim that $V={\cal A}$, or in other words: $W$ is the desired minimal cover for ${\cal A}$.

To see that $V={\cal A}$, suppose there is $X\in{\cal A}, X\not\in V$.

case 1) $X\cap W \not= \emptyset$. Then $(V\cup\{X\},W)$ is larger than $(V,W)$, contradiction.

case 2) $X\cap W = \emptyset$. Pick $x\in X$. Then $(V\cup\{X\},W\cup\{x\})$ is larger than $(V,W)$, again contradiction.

  • $\begingroup$ aww... it always happens to me that possible flaws occur 5 minutes after I post something. I suddenly see a possible snag in the upper bound argument, but do not have the time to check it out now. Sorry, will come back to this. $\endgroup$ – Franka Waaldijk Nov 26 '17 at 11:01
  • $\begingroup$ It might be necessary (and hopefully sufficient) to demand that the sets which are minimally covered stay stable, in the ascending chain. But I really have to spend some more time on this. $\endgroup$ – Franka Waaldijk Nov 26 '17 at 11:07
  • $\begingroup$ So perhaps the order definition should be: $(K,L)\leq(K',L'):= K\subseteq K' \wedge L\subseteq L'\wedge\forall A\in K\,[|A\cap L|= 1\rightarrow |A\cap L'|=1]$. $\endgroup$ – Franka Waaldijk Nov 26 '17 at 11:13
  • $\begingroup$ Ah but then case 2 fails. Sorry, I have to think better and longer. $\endgroup$ – Franka Waaldijk Nov 26 '17 at 11:16
  • 1
    $\begingroup$ No problem. Everybody makes mistakes. Take your time. Meanwhile, if you feel like it, you have an option to delete your answer and to undelete it later when you know how to fix it. Letting it stay is also OK, just put a remark in the beginning that it is still "work in progress" to spare reader's time $\endgroup$ – fedja Nov 26 '17 at 11:20

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.