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 -> 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 -> 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 != 0 and x in f^(-1) {t} then t = f(x) < g(t) (and trivially g(0) != 0, so we have t < g(t) for every t).
We define a sequence x_n as follows. Let x_0 = 0. Let x_{n+1} = sup { g(t) : t <= x_n } (there are only countably many t <= x_n, so this set is bounded above).
Now, in particular we have x_{n+1} >= 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 is in g(f(x)) and so x_{k+1} >= 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 -> omega by f(0) = 0 and f(n) = n - 1 for n > 0 then this is a regressive function which is only constant on {0}. This 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 -> R be continuous. Then f is eventually constant (i.e. there is some t in omega_1 such that f is constant on [t, inf) ).
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')| <= 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')| <= 2^(-n)
So, we can find t_n such that for any s >= x we have |f(s) - f(t_n)| <= 2^(-n). Let t = sup t_n
Now, we have from the above that f( [t, inf) ) has diameter <= 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 |Union F| = aleph_1, so by taking an appropriate bijection we may assume that Union F <= 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} union (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 <= 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 <= 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 <= 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 Union_{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 <= t. Thus U_s cap U_t <= U_s cap (U_t cap t) = U_s cap R <= R. But we know that R <= U_s cap U_t, because we have that R <= U_s cap s <= U_s and R < = U_t cap t <= 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 != A } for prod U_t in F. Then this is an uncountable collection of finite sets, so it contains a delta system. Say D <= 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 != 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' != 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}^N - the cantor set. This shows that we can't directly generalise this, because the theorem proofs 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 easy to check).
There *is* a generalisation of this result about the Cantor set, but that's a story for another day.
Let omega_1 be the first uncountable ordinal. A function f : omega_1 -> 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 -> 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 != 0 and x in f^(-1) {t} then t = f(x) < g(t) (and trivially g(0) != 0, so we have t < g(t) for every t).
We define a sequence x_n as follows. Let x_0 = 0. Let x_{n+1} = sup { g(t) : t <= x_n } (there are only countably many t <= x_n, so this set is bounded above).
Now, in particular we have x_{n+1} >= 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 is in g(f(x)) and so x_{k+1} >= 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 -> omega by f(0) = 0 and f(n) = n - 1 for n > 0 then this is a regressive function which is only constant on {0}. This 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 -> R be continuous. Then f is eventually constant (i.e. there is some t in omega_1 such that f is constant on [t, inf) ).
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')| <= 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')| <= 2^(-n)
So, we can find t_n such that for any s >= x we have |f(s) - f(t_n)| <= 2^(-n). Let t = sup t_n
Now, we have from the above that f( [t, inf) ) has diameter <= 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 |Union F| = aleph_1, so by taking an appropriate bijection we may assume that Union F <= 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} union (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 <= 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 <= 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 <= 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 Union_{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 <= t. Thus U_s cap U_t <= U_s cap (U_t cap t) = U_s cap R <= R. But we know that R <= U_s cap U_t, because we have that R <= U_s cap s <= U_s and R < = U_t cap t <= 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 != A } for prod U_t in F. Then this is an uncountable collection of finite sets, so it contains a delta system. Say D <= 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 != 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' != 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}^N - the cantor set. This shows that we can't directly generalise this, because the theorem proofs 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 easy to check).
There *is* a generalisation of this result about the Cantor set, but that's a story for another day.
posted by David R. MacIver at 12:05 PM
1 Comments:
Isn't the assumption that t is in the range of f necessary for your claim that t < g(t) since for any t not in the range of f, g(t) = 0. For a similar reason I think g(x_n) > x_n is not necessarily true (although x_{n+1} > x_n is true). For example, if f(x) = 0 for x < omega_0 and f(x) = 1 otherwise then it seems to me that x_1 = omega_0 so g(x_1) = 0.
Post a Comment
<< Home