the delta system lemma outside set theory - MathOverflow

the delta system lemma outside set theory

2010-04-15T01:41:43Z

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.

Answer by Joel David Hamkins for the delta system lemma outside set theory

2010-04-15T02:31:38Z

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.

Answer by François G. Dorais for the delta system lemma outside set theory

2010-04-15T03:09:33Z

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) ≤ C^k for some constant C depending on r; he even offered $1000 for a proof or disproof in the case r = 3. (See MR1449752.)

Answer by David R. MacIver for the delta system lemma outside set theory

2010-04-15T09:41:24Z

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$.

Answer by Matti Åstrand for the delta system lemma outside set theory

2010-04-21T15:42:35Z

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: