Minimal covering sets for infinite set systems (Q1999754): Difference between revisions

Given a set \(V\) and a collection \(\mathcal H\) of non-empty subsets of \(V\), \(M \subseteq V\) is a covering set if \(M \cap A \neq \emptyset\) for all \(A \in \mathcal H\). \(M\) is a minimal covering set if \(M\) is a covering set and no proper subset of \(M\) is a covering set. Covering sets are the topic of a question raised by \textit{T. Banakh} and \textit{D. van der Zypen} [Discrete Math. 342, No. 11, 3043--3046 (2019; Zbl 1419.05156)]. If \(r\) is a fixed natural number and \(\mathcal H\) is a system of sets with the property that \(|A \cap B| \leq r\) for all distinct \(A,B \in \mathcal H\), must \(\mathcal H\) have a minimal covering set? In 1937, E.W. Miller show that if \(\mathcal H\) is a collection of infinite sets with the intersection property in the question, then \(\mathcal H\) is 2-chromatic. Erdoős and Hajnal generalized this in [\textit{P. Erdős} and \textit{A. Hajnal}, Acta Math. Acad. Sci. Hung. 12, 87--123 (1961; Zbl 0201.32801)]. In this paper, the author applies some of the techniques of Erdős and Hajnal [loc. cit.] to investigate some specific instances of this problem where additional information about the set system \(\mathcal H\) is available. He finds criteria that guarantee an affirmative answer to the question and also shows that, consistently, there are systems \(\mathcal H\) with small intersections that do not have minimal covering sets. As a sample, the following conditions on \(\mathcal H\) guarantee the existence of a minimal covering set: \begin{itemize} \item[1.] \(\mathcal H\) consists of finite sets. \item[2.] \(S\) is a set, \(\mu\) is an infinite cardinal, \(\mathcal H\) consists of \(\mu\)-sized subsets of \(S\), and there is a natural number \(r\) so that \(|A \cap B| \leq r\) for all distinct \(A,B \in \mathcal H\). \item[3.] \(S\) is a set, \(\mu\) is an infinite cardinal, \(\mathcal H\) consists of \(\mu\)-sized subsets of \(S\), and there is a well-ordering \(\prec\) of \(\mathcal H\) so that \(A \not\subseteq \bigcup\{B : B \prec A\}\) for all \(A \in \mathcal H\). \item[4.] \(S\) is a set, \(\mathcal H\) consists of subsets of \(S\), there is a natural number \(r\) so that \(|A \cap B| \leq r\) for all distinct \(A,B \in \mathcal H\), and there is a \(T \subseteq S\) so that \(A \cap T\) is both non-empty and at most countable for all \(A \in \mathcal H\). \item[5.] The \(\omega_1\) version of Martin's axiom holds, \(S\) consists of countable limit ordinals, and \(\mathcal H = \{A_\xi : \xi \in S\}\) is so that \(A_\xi\) is a cofinal subset of \(\xi\) with order type \(\omega\). \item[6.] GCH holds, \(S\) is a set, \(\mu\) is an uncountable regular cardinal, \(\omega \leq \tau < \mu\), \(\square_\lambda\) is true for all singular cardinals \(\lambda\) with cofinality at most \(\tau\), \(\mathcal H\) consists of \(\mu\) sized subsets of \(S\), and \(|A \cap B| < \tau\) for all distinct \(A,B \in \mathcal H\). \end{itemize} The paper also contains the following situations where \(\mathcal H\) has no minimal covering set. \begin{itemize} \item[1.] \(\mathcal H = \{A_0,A_1,\cdots\}\), the \(A_n\) are strictly decreasing, and \(\bigcap_n A_n = \emptyset\). \item[2.] \(\mathcal H = \langle A_\alpha : \alpha < \omega_1 \text{ is a limit ordinal}\rangle\) is a \(\clubsuit\)-sequence. \end{itemize} They also show that there is a system \(\mathcal H\) of almost disjoint countable sets that has no minimal covering. A greater disparity of size does not necessarily help. They prove that, consistent with a supercompact cardinal, there is a family \(\mathcal H\) consisting of \(\aleph_1\) sized subsets of \(\omega_{\omega+1}\) where distinct \(A, B \in \mathcal H\) have finite intersection, but \(\mathcal H\) has no minimal covering set.