The $\mathrm{\Delta }$-system lemma: an elementary proof

17 Responses to The $\mathrm{\Delta }$-system lemma: an elementary proof

1. Asaf Karagila says:

   March 21, 2013 at 9:42 am

   The Nile.

   Reply
   • saf says:

     March 21, 2013 at 5:52 pm

     Indeed, we have $a\cap b⊑a$ for all $a,b\in \mathcal{B}$. I wonder why don’t they call it the $\mathrm{\nabla }$-system lemma!

     Reply
     • Asaf Karagila says:

       March 23, 2013 at 6:21 am

       When you are looking at it from the Greek side of the globe, it’s really a $\mathrm{\Delta }$.

       Reply
       • saf says:

         March 23, 2013 at 9:19 am

         According to the convention of drawing ordinals from bottom to up, the equation “$a\cap \delta =a\cap b=b\cap \delta$ for all distinct $a,b\in \mathcal{B}$” corresponds to $\mathrm{\nabla }$.

         Reply
         • Asaf Karagila says:

           March 26, 2013 at 1:21 am

           But maybe this notation was conceived by the same people who decided that forcing should go up?

           Halfway backwards sort of approach…

           $\stackrel{\circ \circ }{⌣}$
2. Andres Caicedo says:

   March 21, 2013 at 10:44 am

   This seems to be the proof in Shelah’s proper forcing book. Congratulations on the Bar-Ilan position, by the way.

   Reply
   • saf says:

     March 21, 2013 at 5:50 pm

     Thanks, Andres.

     I see! Well, the first proof I’ve ever seen to this lemma was given in Gitik’s course in Tel-Aviv, following Hrbacek and Jech; their proof involves iterative applications of the pressing-down lemma. The other proof I know is the elementary submodel proof, which morally is the same as pressing-down. Thus, the above proof-by-induction came to me as a surprise!

     At some point, I thought it may be possible to find another proof that builds on the fact that ${\omega }^{{\omega }_1}$ is separable, yielding a color-by-type map $\psi :[{\omega }_1{]}^{<\omega }\to V_{\omega }$ in a way that an homogeneous set corresponds to a delta-system. However, a counting argument shows that this is impossible.

     Reply
     • Henno Brandsma says:

       June 11, 2013 at 2:52 am

       Isn’t this the proof used in Kunen’s “set theory” book? This I think predates Shelah’s book as well.

       Reply
       • saf says:

         June 11, 2013 at 7:36 am

         Thank you, Henno!
         The proof in Kunen’s book is for the general case of $Delta$-systems, and hence not of this form. However, you are right – Exercise 1 from Chapter II suggests the above proof.

         Reply

3. Pingback: An L-space from a syndetic coloring and a universal binary sequence | Assaf Rinot

4. yogut says:

   October 27, 2013 at 12:31 pm

   It is a silly question but how do you construct the function $f$?

   Reply
   • saf says:

     October 27, 2013 at 12:35 pm

     You can define $g:\kappa \to \kappa$ by recursion on $\alpha <\kappa$, stipulating that $g(\alpha ):=min\{\tau <\kappa \mid {\mathcal{A}}_{\tau }\ne \mathrm{\varnothing }\}\setminus sup(\bigcup \bigcup \{{\mathcal{A}}_i\mid i<sup(g[\alpha ])\})$. Since $\kappa$ is regular and $|{\mathcal{A}}_i|<\kappa$ for all $i<\kappa$, we have $sup(\bigcup \bigcup {\mathcal{A}}_i\mid i<\theta )<\kappa$ for all $\theta <\kappa$, and hence the function $g$ is well-defined. Finally, let $f(\alpha )$ be an arbitrary element of ${\mathcal{A}}_{g(\alpha )}$ for all $\alpha <\kappa$.

     Reply
5. Shir Sivroni says:

   May 5, 2015 at 4:01 am

   In the second part of the induction step:
   If $|{\mathcal{A}}_{\tau }|<\kappa$ can't we just define a regressive function $f:\mathcal{A}\to \kappa$ where $f(A)=min(A)$?
   And then, by fodor's Lemma and the regularity of $\kappa$, we get to the first part of the induction step?

   Reply
   • saf says:

     May 5, 2015 at 7:51 am

     The domain of $f$ is the (rather sparse) set $\mathcal{A}$, so, while you can still think of $f$ as being regressive, the (generalized) Fodor lemma fails in this setup.

     Reply
6. Isaac Gorelic says:

   August 29, 2018 at 5:40 am

   Actually, there is an easier proof (of the Induction step): Either we have a disjoint system of size $\kappa$, or take any maximal disjoint system and some point in its union will belong to $\kappa$ many (other) members of $\mathcal{A}$ (that’s where the regularity of $\kappa$ is needed).

   Reply
7. Carlos López says:

   February 3, 2023 at 6:24 pm

   Hi Assaf,

   Do you know if there is any Ramsey-type theorem that has as consequence the delta system lemma?

   Thanks.

   Reply
   • saf says:

     February 5, 2023 at 12:27 pm

     Hi Carlos,

     Indeed. Given $\mathcal{A}\subseteq [\kappa {]}^n$, for each $a\in \mathcal{A}$, let $⟨a(i)\mid i<n⟩$ denote the increasing enumeration of the elements of $a$. Let us also fix some well-ordering $⊲$ of $\mathcal{A}$. Now define a coloring $c:[\mathcal{A}{]}^2\to \mathcal{P}(n)$ by letting $c(a,b):=\{i<n\mid a(i)\in b\}$ for all $a⊲b$ from $\mathcal{A}$. Let us observe that any $\mathcal{B}\subseteq \mathcal{A}$ that is $c$-homogeneous will form a $\mathrm{\Delta }$-system. Indeed, if $c$ is constant over $\mathcal{B}$ with value, say, $I$, and $a$ denotes its $⊲$-least element, consider the set $r:=\{a(i)\mid i\in I\}$.
     Now, given any set $b$ in $\mathcal{B}$ that is distinct from $a$, since $c(a,b)=I$, it is the case that $r=a\cap b$. Therefore, $r\subseteq \bigcap \mathcal{B}$. In addition, for all $x\ne y$ from $\mathcal{B}$, $|x\cap y|=|c(x,y)|=|I|=|r|$, so, in fact, $x\cap y=r$.

     Reply