# Existence of a “diagonal” set in certain set systems

Let $\kappa\geq\aleph_0$ be an infinite cardinal, and suppose that ${\cal A}$ is a collection of subsets of $\kappa$ such that for all $A\in {\cal A}$ we have $|A| = \kappa$ and for $A,B\in {\cal A}$ with $A\neq B$ we have $|A\cap B|<\kappa$. Is there $D\subseteq \kappa$ such that for all $A\in {\cal A}$ we have

1. $A\cap D \neq \emptyset$, and
2. $A \not\subseteq D$

?

• hm, what about $D=\kappa$? – Fedor Petrov Jul 17 '17 at 13:50
• Condition 2 should read $A\cap(\kappa\setminus D)\neq\emptyset$. – Joseph Van Name Jul 17 '17 at 14:38
• Fedor and Joseph are right -- I got condition 2 wrong! Will correct it now. – Dominic van der Zypen Jul 17 '17 at 14:44
• It is a very nice question! – Joel David Hamkins Jul 17 '17 at 16:13
• Thanks Joel! By the way the condition that $|A\cap B|<\kappa$ is necessary to make the question interesting, otherwise one can take any free ultrafilter. – Dominic van der Zypen Jul 17 '17 at 16:35

This is false in general when $\kappa=\omega$. Let $\mathcal{A}=\langle A_\alpha:\alpha<\mathfrak{c}\rangle$ be an almost disjoint family of size continuum, and let $\langle D_\alpha:\alpha<\mathfrak{c}\rangle$ list all subsets of $\omega$.
For each $\alpha<\mathfrak{c}$, one of $A_\alpha\cap D_\alpha$ and $A_\alpha\setminus D_\alpha$ is infinite, so we can shrink $A_\alpha$ to an infinite subset $B_\alpha$ such that either $B_\alpha\subseteq D_\alpha$ or $B_\alpha\cap D_\alpha=\emptyset$. The family $\langle B_\alpha:\alpha<\mathfrak{c}\rangle$ is still almost disjoint, and for any subset $D$ of $\omega$ there is an $\alpha$ such that either $B_\alpha\subseteq D$ or $B_\alpha\cap D=\emptyset$.
• I guess one would arrive at a natural cardinal characteristic by considering the size of the smallest family admitting no such set $D$. Seva's answer shows that this is uncountable, and your argument shows it is defined. I wonder if it is equal to some other well-known cardinal characteristic? Perhaps it is related to the almost-disjointness number and the size of the smallest ultrafilter base. – Joel David Hamkins Jul 17 '17 at 18:24
At least, this is true if $|\mathcal A|=\aleph_0$, and also if $|\mathcal A|<\kappa$.
In the former case ($|\mathcal A|=\aleph_0$) we can write $\mathcal A=\{A_1,A_2,\ldots\}$. Choose now elements $a_1\in A_1$, $a_2\in A_2$, $a_3\in A_3,\ldots$ so that $a_2\notin A_1$ (this is possible as $|A_2|>|A_1\cap A_2|$), then $a_3\notin A_1\cup A_2$ (possible in view of $|A_3|>|(A_1\cup A_2)\cap A_3|$), etc. Taking $D:=\cup_i\{a_i\}$, we get $\{a_i\}\subseteq D\cap A_i\subseteq\{a_1,\ldots,a_i\}\subsetneq A_i$ for each $i\ge 1$.
In the latter case ($|\mathcal A|<\kappa$), for each $A\in\mathcal A$ we have $|\cup_{B\ne A}(A\cap B)|<|A|$, and therefore there exists $a\in A$ with $a\notin \cup_{B\ne A} B$. Thus, $\mathcal A$ admits a system of distinct representatives, and taking $D$ to be the union of all these representatives, we get $D\cap A=\{a\}$, for every $A\in\mathcal A$.