11
$\begingroup$

The lemma:

Any uncountable set $S$ of finite sets has an uncountable subset $\Delta \subseteq S$ and an $x$ such that $\forall a,b \in \Delta$, if $a \neq b$ then $a \cap b = x$. $\Delta$ is called a $\Delta$-system.

I've seen this lemma used in independence proofs, such as the famous result that the negation of the continuum hypothesis is consistent with ZFC, but it seems like it would be useful in other fields as well. Does anyone have any examples with this lemma outside pure set theory?

See also the finite and generalized infinite versions posted below.

$\endgroup$
5
  • 1
    $\begingroup$ If every member of S is a singleton set, the statement does not hold. Perhaps x is not supposed to be in S? Gerhard "Ask Me About System Design" Paseman, 2010.04.14 $\endgroup$ Apr 15, 2010 at 2:11
  • $\begingroup$ (I fixed the statement of the lemma.) $\endgroup$ Apr 15, 2010 at 2:31
  • $\begingroup$ This question seems related: mathoverflow.net/questions/21245/… $\endgroup$ Apr 15, 2010 at 3:16
  • $\begingroup$ Can't all the elements of $S$ be disjoint? $\endgroup$ Apr 15, 2010 at 3:35
  • $\begingroup$ @Mariano: Yes, then S is itself a ∆-system (x is the empty set). $\endgroup$ Apr 15, 2010 at 3:50

4 Answers 4

8
$\begingroup$

There's a nice application of the lemma to point-set topology (whether or not you consider this to be set theoretic is up to you :-) )

Define the following generalisation of separability:

A topological space X is ccc if every pairwise disjoint collection of non-empty open sets is countable.

It's clear that every separable space is ccc (because you can pick an element of the dense set in each open set), but ccc has the following theorem which makes it better behaved on products (a product of $> 2^{\aleph_0}$ spaces with more than one point is not separable):

Theorem: Let $\{ F_a : a \in A \}$ be a family of topological spaces such that every finite product is ccc. Then $\prod F_a$ is ccc.

Proof:

Let T be an uncountable family of pairwise disjoint non-empty open sets. We can without loss of generality assume T consists of basis elements. Each of these basis elements is a product of sets of the form $U_a \subseteq F_a$ with at most finitely many not equal to $F_a$.

Let $G = \{ \{ a : U_a \neq F_a \} : \prod U_a \in T \}$. This is an uncountable collection of finite sets, so contains a delta system, say with root R.

But we must have the projection of $T$ to $\prod_{a \in R} F_a$ still be disjoint: For any $a \not\in R$ we have $U_a \neq F_a$ for at most one element of T. But products of finitely many $T_a$ are ccc, thus we must have the projection of T (and thus T itself) being countable, contradicting the hypothesis.

QED

This in particular gives us the following corollary:

Theorem: An arbitrary product of separables spaces is ccc.

Proof: A finite product of spearable spaces is separable and thus ccc.

which is interesting because e.g. it tells us that there are compact hausdorff spaces which are not the continuous image of $\{0, 1\}^\kappa$ for any $\kappa$.

$\endgroup$
3
  • 2
    $\begingroup$ Because of the natural correspondence between forcing and topology, this is essentially a special case of the applications suggested by the original poster. However, since the correspondence is not that well known, I think this does count as an application outside set theory. $\endgroup$ Apr 15, 2010 at 16:42
  • 2
    $\begingroup$ Indeed, it's exceptionally close to the way it gets used in set theory, but it is a result of independent interest to the set theoretic connection, so I thought it worth mentioning. $\endgroup$ Apr 15, 2010 at 18:13
  • 4
    $\begingroup$ In fact, the delta lemma is due to Shanin (1948) just in order to prove the ccc result. So it's the first application too! $\endgroup$ Apr 21, 2010 at 17:15
3
$\begingroup$

This doesn't at all answer your question, since this definitely IS coming from pure set theory, but I thought it worthwhile to mention that the Delta system lemma has an important generalization to higher cardinals, which figures just as prominently in many forcing arguments.

Lemma. Any sufficiently large family of small sets contains a large $\Delta$ system. Specifically, if a regular cardinal $\kappa$ is large with respect to an infinite cardinal $\mu$ in the sense that $\nu^{<\mu}<\kappa$ for all $\nu<\kappa$, then every family consisting of $\kappa$ many sets of size less than $\mu$ has a subfamily of size $\kappa$ forming a $\Delta$ system.

That is, if $\{a_{\gamma};\gamma<\kappa\}$ is a family of sets of size less than $\mu$ then there is $A\subseteq\kappa$ of size $\kappa$ and a set $d$ of size less than $\mu$ such that $\{a_{\gamma};\gamma\in A\}$ forms a $\Delta$-system with a root $d$, meaning that $a_{\gamma}\cap a_{\delta}=d$ for any distinct $\gamma,$ $\delta\in A$.

The lemma you state is the case where $\mu=\omega$ and $\kappa=\omega_1$, but this more general version finds numerous applications in various forcing arguments, particularly those involving large cardinals or forcing with infinite conditions.

One can find the proof in Kunen's book on Set Theory, forcing and independence proofs.

$\endgroup$
0
3
$\begingroup$

There is also a finite version of the Δ-Lemma.

For all k, r ≥ 1, there is a positive integer f(k,r) such that any family of k-element sets with at least f(k,r) elements contains a Δ-system consisting of r elements of the original family.

Erdős and Rado originally showed that (r-1)k < f(k,r) < k!(r-1)k. The current best upper bound on f(k,r) is $$Ck!\left(\frac{(\log\log\log k)^2}{\alpha\log\log k}\right)^k$$ for sufficiently large k, where α is any positive constant. Erdős conjectured that f(k,r) ≤ Ck for some constant C depending on r; he even offered $1000 for a proof or disproof in the case r = 3. (See MR1449752.)

$\endgroup$
3
  • 6
    $\begingroup$ I guess one use of the lemma outside set theory is as a particularly hard way to earn $1000... $\endgroup$ Apr 15, 2010 at 3:21
  • $\begingroup$ François, is there a fruitful unification of the finite and generalized infinite versions of the Delta system lemma? I would have in mind a single statement and proof, in the way that Cantor's proof that P(X) is larger than X works for finite X just as well as infinite. $\endgroup$ Apr 15, 2010 at 12:47
  • $\begingroup$ Joel, I can only remember one basic proof, which seems to work for all cases, so I would say yes. (Some finite case refinements are obtained through compactness.) $\endgroup$ Apr 15, 2010 at 14:29
3
$\begingroup$

Joel gave one generalization; there is another generalization to a different direction:

Let $T$ be a $\xi$-stable (complete) first order theory, and $A$ a set in a model of $T$ with $|A|\le\xi$. If $I$ has cardinality $>\xi$, then $I$ has a subset with cardinality $>\xi$, which is an indiscernible set over $A$. (Here $I$ is a set of finite tuples in some model of $T$ that contains $A$.)

The usual $\Delta$-lemma follows from this because the theory of infinite set with empty language is $\omega$-stable, and an indiscernible set in such a model is just as wanted.

I believe this is from Saharon Shelah's Classification Theory (1990).

Wikipedia links:

  1. Stable theory
  2. Indiscernibles
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.