Let $\Delta(\kappa, \mu)$ be the statement: "let $F$ be a family of cardinality $\kappa$ of sets of cardinality less than $\mu$. Then there is a family $G \subset F$ of cardinality $\kappa$ and a set $r$ such that $a \cap b=r$ for every $a,b \in G$".

We know that if $\kappa$ is a regular cardinal and $\lambda^{<\mu} < \kappa$, for every $\lambda < \kappa$ then $\Delta(\kappa, \mu)$ holds. My question is:

Does $\Delta(\kappa, \mu)$ for some regular uncountable $\kappa$ and some uncountable $\mu<\kappa$ imply some weak form of the GCH below $\kappa$?

  • 1
    $\begingroup$ Do you really mean to ask about the GCH at $\kappa$, rather than, say, at the cardinal predecessors of $\kappa$ in the case that $\kappa$ is a successor? For example, in the positive direction your hypothesis is not really a GCH property at $\kappa$ itself, but a GCH property below $\kappa$. $\endgroup$ – Joel David Hamkins May 17 '13 at 0:40
  • 1
    $\begingroup$ Santi, I like this question. I have wondered what assumptions we make when using a delta-system argument. $\endgroup$ – user10290 May 17 '13 at 7:17
  • $\begingroup$ Yes, Joel, I did mean "below $\kappa$". $\endgroup$ – Santi Spadaro May 17 '13 at 14:28

It is a very nice question! The answer is yes, natural instances of the $\Delta$ system property, which hold under GCH, are in fact equivalent to the GCH.

Theorem. $\Delta(\omega_2,\omega_1)$ is equivalent to CH.

Proof: You've pointed out that CH implies the principle, since the hypothesis you mention for this case amounts to $\omega_1^{\lt\omega_1}<\omega_2$, which amounts to CH. So let us consider what happens when CH fails. Let $T=2^{\lt\omega}$ be the tree of all finite binary sequences, and label the nodes of $T$ with distinct natural numbers. Let $F$ be the subsets of $\omega$ arising as the sets of labels occuring on any of $\omega_2$ many branches through $T$. Thus, $F$ has size $\omega_2$, and any two elements of $F$ have finite intersection. I claim that this family of sets can have no $\Delta$-system of size $\omega_2$, and indeed, it can have no $\Delta$-system even with three elements. If $r$ is the root of $a$, $b$ and $c$ in $F$, then $r=a\cap b=a\cap c$, and so $a$ and $b$ branch out at the same node that $a$ and $c$ do, in which case $b$ and $c$ must agree one step longer, so $b\cap c\neq r$. QED

The same idea works for higher cardinals as follows:

Theorem. For any infinite cardinal $\delta$, we have $\Delta(\delta^{++},\delta^+)$ is equivalent to $2^\delta=\delta^+$.

Proof. If $2^\delta=\delta^+$, then your criterion, which amounts to $(\delta^+)^{\lt\delta^+}<\delta^{++}$, is fulfilled, and so the $\Delta$ property holds. Conversely, consider the tree $T=2^{\lt\delta}$, the binary sequences of length less than $\delta$. Let $F$ be a family of $\delta^{++}$ many branches through $T$, regarding each branch $b$ as a subset of $T$, the set of its initial segments. Each such branch has size $\delta$, since the tree has height $\delta$. But for the same reason as before, there can be no $\Delta$ system with even three elements, since the tree is merely binary branching, and so three distinct branches cannot have a common root. This contradicts $\Delta(\delta^{++},\delta^+)$, as desired. QED

Corollary. The full GCH is equivalent to the assertion that $\Delta(\delta^{++},\delta^+)$ for every infinite cardinal $\delta$.

Update. The same idea shows that the hypothesis you mention is optimal: one can reverse the lemma from the conclusion to the hypothesis.

Theorem. The following are equivalent, for regular $\kappa$ and $\mu\lt\kappa$:

  1. $\Delta(\kappa,\mu)$
  2. $\lambda^{\lt\mu}\lt\kappa$ for every $\lambda\lt\kappa$.

Proof. You mentioned that 2 implies 1, and this is how one usually sees the $\Delta$ system lemma stated. For the converse, suppose that $\lambda^{\lt\mu}\geq\kappa$ for some $\lambda\lt\kappa$. Since $\kappa$ is regular and $\mu\lt\kappa$, this implies $\lambda^\eta\geq\kappa$ for some $\eta\lt\mu$. Let $T$ be the $\lambda$-branching tree $\lambda^{\lt\eta}$, which has height $\eta$. Let $F$ be a family of $\kappa$ many branches through this tree, where we think of a branch as the set of nodes in the tree that lie on it, a maximal linearly ordered subset of the tree $T$. Each such branch is a set of size $\eta$. I claim that this family has no subfamily that is $\Delta$ system of size $\lambda^+$. The reason is that because the tree is $\lambda$-branching, if we have $\lambda^+$ many branches with a common root, then at least two of them must extend that root to the next level in the same way, a contradiction to it being a root. Thus, the failure of 2 implies the failure of 1, as desired. QED

| cite | improve this answer | |
  • $\begingroup$ It is interesting! What happens when $\Delta( \delta ^{+++++++}, \delta^+)$ ? $\endgroup$ – user10290 May 17 '13 at 7:22
  • $\begingroup$ Erin - $\Delta( \delta ^{+++++++}, \delta^+) => \Delta( \delta ^{++}, \delta^+)$ $\endgroup$ – Eran May 17 '13 at 10:00
  • $\begingroup$ @Joel - isn't this proof goes just as well assuming ZFC + GCH + KH (Kurepa's Hypothesis)? $\endgroup$ – Eran May 17 '13 at 10:07
  • 1
    $\begingroup$ Very nice, Joel! It's more than I hoped. $\endgroup$ – Santi Spadaro May 17 '13 at 14:27
  • 1
    $\begingroup$ Well, as I said, $\Delta(\omega_2,\omega_2)$ can already be refuted without KH by considering the tree $2^{\lt\omega_1}$, where one has at least $\omega_2$ many branches of size $\omega_1$, but no $\Delta$ system of size 3, and Kurepa trees have nothing to do with it. But I'm not sure why you think this refutes $\Delta(\omega_2,\omega_1)$, and in particular, I dispute your implication in (A). $\endgroup$ – Joel David Hamkins May 18 '13 at 2:10

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.