The pressing down lemma

The pressing down lemma is a ridiculously useful technical lemma from combinatorial set theory. It’s amazing how often you can just set up some machinery, apply the pressing down lemma, and poof. A solution pops out. I’m going to give a simplified version of the lemma and show two nice applications of it to general topology. There are various almost immediate generalisations of the version I’m going to give, but they require me to introduce more new ideas than I want to, and this version will suffice.

Let \(\omega_1\) be the first uncountable ordinal. A function \(f : \omega_1 \to \omega_1 \) is said to be regressive if for every \(x > 0\) we have \(f(x) < x\).

The pressing down lemma: Every regressive \(f : \omega_1 \to \omega_1\) is constant on some unbounded set.
Proof:

Suppose for every \(t < \omega_1\) we had that \(f^{-1}( {t} )\) was bounded. Let \(g(t) = \sup f^{-1} ( { t } )\). Note that if \(x \neq 0 \) and \( x \in f^{-1} ( { t } )\) then \(t = f(x) < g(t)\) (and trivially \(g(0) \neq 0\), so we have \( \forall t t < g(t) \) ). We define a sequence \(x_n\) as follows. Let \(x_0 = 0\). Let \(x_{n+1} = \sup { g(t) : t \leq x_n }\) (there are only countably many \(t \leq x_n\), so this set is bounded above). Now, in particular we have \(x_{n+1} \geq g(x_n) > x_n\)

Now, let \(x = \sup x_n\). We have that \(f(x) < x\), and so that\( f(x) < x_k\) for some k. But then\( x \in g(f(x))\) and so \( x_{k+1} \geq x \) and thus \( x_{k+2} > x \), contradicting that \(x = \sup x_n\).

QED

Note that there’s something special going on here. If we define \(f : \omega \to \omega\) by \(f(0) = 0\) and \(f(n) = n – 1\) for \(n > 0\) then this is a regressive function for which the largest set it is constant on is \({0, 1}\). The pressing down lemma is a genuinely new property of the uncountable case.

Now, let’s give an application of this:

Theorem: Give \(\omega_1\) the order topology and let \(f : \omega_1 \to \mathbb{R}\) be continuous. Then \(f\) is eventually constant (i.e. there is some \(t \in \omega_1\)) such that \(f\) is constant on \([t, \infty)\) ).

Proof:

\(f\) is continuous, so for every t there is some neighbourhood of t such that for s in this neighbourhood we have \(|f(s) – f(t)| < 2^{-(n+1)}\). In particular if \(t > 0\) there is some \(k < t\) such that whenever \(k < s < t\) we have \(|f(s) – f(t)| < 2^{-(n+1)}\). Let \(f(t)\) be the least such \(k\). (and \(f(0) = 0\)). Now, f is regressive, so it’s constant on some unbounded set.

i.e. we can find \(k < \omega_1\) and an unbounded set of \(x\) such that for \(k < s < x\) we have \(|f(s) – f(x)| < 2^{-(n+1)}\). In particular this works for \(k^+\), so we have that \(|f(s) – f(k^+)| \leq 2^{-(n+1)} + 2^{-(n+1)} = 2^{-n}\). Now, because the set of \(x\) for which this works is unbounded, for any s > k we can find x > s for which this works, and so \(|f(s) – f(k^+)| \leq 2^{-n}\)

So, we can find \(t_n\) such that for any \(s \geq x\) we have \(|f(s) – f(t_n)| \leq 2^{-n}\). Let \(t = \sup t_n\).

Now, we have from the above that \(f( [t, \infty) )\) has diameter \(\leq 2^{-n}\) for every \(n\), and so has diameter 0. i.e. it consists of a single point. Hence \(f\) is eventually constant.

QED

Neat, huh? There was essentially no work in there other than trying to figure out how to apply the pressing down lemma.

The next bit is a tiny bit more work, and won’t apply the pressing down lemma directly. Instead we’ll procede via another cool and important lemma in combinatorial set theory.

A collection of sets F is said to be a \(\Delta\)-system with root I if for every distinct \(A, B \in F\) we have \(A \cap B = I\). Note that \(I\) is allowed to be empty.

The \(\Delta\)-system lemma:

Let F be an uncountable collection of finite sets. F contains an uncountable \(\Delta\)-system.

Proof:

By passing to a subset we may assume that |F| = aleph_1. Further we then have that \(|\bigcup F| = \aleph_1\), so by taking an appropriate bijection we may assume that \(\bigcup F \subseteq \omega_1\) and contains no finite ordinals.

Now, enumerate F as \({ U_t : t < \omega_1 }\)

For each \(t < \omega_1\) define \(f(t) = \max ( \{0\} \cup (U_t \cap t ) )\) (this set is finite, so has a maximum). Then \(f\) is regressive. (When \(t\) is finite you need the fact that we choose the \(U_t\) so that they contained no finite ordinals, else you might have \(t \subseteq U_t\)). So, by the pressing down lemma, is constant on some unbounded set. So, we have an ordinal s and an unbounded set A such that for \(t \in A\) we have \(\max { U_t \cap t } = s\). In particular \(U_t \cap t \leq s\). Now, \(s\) is countable, and for every \(t\) we have that \(U_t \cap t\) is a finite subset of \(s\). There are only countably many finite subsets of \(s\), and A is uncountable, so for some finite \(R \subseteq s\) we must have that \(U_t \cap t = R\) for uncountably many \(t \in A\). Fix some such R and let A’ be the set of \(t \in A\) such that \(U_t \cap t = R\). Now, by transfinite induction we pick an \(\omega_1\) sequence x_t such that \(x_t\) is in A’ and \(x_t > \sup \bigcup\limits_{s \in A ‘, s < t} F_t\). Let \(D\) be the image of this sequence. Now for \(s, t \in D\) if \(s < t\) we have that \(\max U_s < t\).

Now, let \(s, t \in D\). Say \(s < t\). Then \(U_s \cap U_t = (U_s \cap t) \cap U_t\), because \(U_s \subseteq t\). Thus \(U_s \cap U_t \subseteq U_s \cap (U_t \cap t) = U_s \cap R \subseteq R\). But we know that \(R \subseteq U_s \cap U_t\), because we have that \(R \subseteq U_s \cap s \subseteq U_s\) and \(R \subseteq U_t \cap t \subseteq U_t\).

Hence \(\{ U_t : t \in D \}\) is our desired \(\Delta\)-system, and has root \(R\).

QED

Phew. I have to admit, I don’t think this proof is substantially easier than the proof without the pressing down lemma. However it’s not any harder, and the use of the pressing down lemma clears away a lot of the ugly details.

So. Why do we care about these things? A number of reasons actually, but I don’t know many of them. I’m going to use it to prove the following topological result.

First a definition. A topological space is said to be ccc (countable chain condition) if every pairwise disjoint collection of open sets is countable.

Why do we care about this? Well, it has important connections to the theory of Boolean algebras, and it’s often a good way to test if something is separable – any separable space is ccc, and it’s often easy to see if a space is not ccc. Seeing if it *is* ccc can sometimes be a bit more subtle, and that’s something this theorem will help with. Additionally, it is just a special case of one of the many cardinal invariants we can use to study topological spaces, and it’s one which is remarkably well behaved.

Theorem: Let \({ A_t : t \in I }\) be a collection of topological spaces such that every finite product of them is ccc. Then \(\prod A_t\) is ccc. In particular a product of separable spaces is ccc.

Proof:

This is almost an immediate consequence of the \(\Delta\)-system lemma. Suppose F was an uncountable set pairwise disjoint open subsets of \(A = \prod A_t\). Then we can replace each element of F with some basis element contained in it. Each of these basis elements is a product of open sets \(U_t\) such that for all but finitely many t we have \(U_t = A_t\). Let G be the collection of sets of the form \({ t : U_t \neq A_t }\) for \(\prod U_t \in F\). Then this is an uncountable collection of finite sets, so it contains a \(\Delta\)- system. Say \(D \subseteq G\) is a \(\Delta\)-system with root R.

Now, R is some finite subset of I. So consider \(\prod_{t \in R} U_t\), where the \(U_t\) are chosen from F such that \({ t : U_t \neq A_t }\) is in D. Then because we have that \(\prod U_t \cap \prod V_t = \prod (U_t \cap V_t)\) we have that the products \(\prod_{t \in R} U_t\) are pairwise disjoint (since \(U_t \cap U_t’ \neq \emptyset\) for \(t \not\in R\), as at least one of \(U_t, U_t’\) is equal to \(A_t\)). So we’ve got an uncountable collection of pairwise disjoint open subsets of \(\prod_{t \in R} A_t\), contradicting the hypothesis that all finite products of the \(A_t\) are ccc.

The ‘in particular’ then follows from the fact that separable spaces are ccc, and finite products of separable spaces are separable.

QED

Neat, huh?

As a quick application of this result, recall that every second countable compact Hausdorff space is the continuous image of \(\{0, 1\}^{\mathbb{N}}\) – the Cantor set. This shows that we can’t directly generalise this, because the theorem proves that for any \(A\) we have that \(\{0, 1\}^A\) is ccc. Easy check: The continuous image of a ccc space is ccc. Thus, for example, \(\omega_1 + 1\) with the order topology is not the continuous image of \(\{0, 1\}^A\) for any A, because it is not ccc (this is also easy to check).

There is a generalisation of this result about the Cantor set, but that’s a story for another day.

This entry was posted in Numbers are hard on by .