
Re: Push Down Lemma
Posted:
Feb 8, 2013 11:43 PM


On Feb 8, 9:10 pm, William Elliot <ma...@panix.com> wrote: > On Thu, 7 Feb 2013, Butch Malahide wrote: > > On Feb 7, 3:43 am, William Elliot <ma...@panix.com> wrote: > > > The push down lemma: > > > Can you cite an authoritative source that uses the overblown and > > inappropriate name "push down lemma" for this triviality, or was that > > your own idea? > > No, it was taken from sci.math or some other such source. > > > When I read your subject line, I thought you were > > referring to the celebrated "Pressing Down Lemma" aka Fodor's Lemma: > >http://en.wikipedia.org/wiki/Fodor's_lemma > > The same source also gave the pressing down lemma for omega_1 > > > > Let beta = omega_eta, kappa = aleph_eta. > > > Assume f:beta > P(S) is descending, ie > > > . . for all mu,nu < beta, (mu <= nu implies f(nu) subset f(mu)), > > > f(0) = S and S < kappa. > > > > Then there's some xi < beta with f(xi) = f(xi + 1). > > > If I have correctly deciphered your godawful notation, what you're > > saying amounts to this: If S is an infinite set, then the power set > > P(S) (ordered by inclusion) does not contain any wellordered chain W > > with W > S, and neither of course does its dual. Right. > > Yes, that's a nice description. On the other > hand P(S) can have a nest of length P(S). > > > The most familiar special case is that P(omega), although it contains > > uncountable chains ordered like the reals, contains no chain of type > > omega_1 or omega_1^*. > > > Can the push down lemma be extended to show f is eventually constant? > > Yes, easily, if kappa is regular; no, if kappa is singular. Suppose, > > e.g., that eta = omega and S = omega. Your descending function > > f:omega_{omega} > P(omega) cannot be injective, but neither does it > > have to be eventually constant. For examply, you could have f(mu) = S > > for the first aleph_0 values of mu, f(mu) = S\{0 for the next aleph_1 > > values, f(mu) = S\{0,1} for the next aleph_2 values, and so on. > > Easily? How so for regular kappa that f is eventually constant?
Let kappa be a regular infinite cardinal, identified with its initial ordinal omega_{alpha}
Since kappa is regular, for any function f defined on kappa, there exists X subset kappa, with X = kappa, such that the restriction fX is either injective or constant. Since kappa is an initial ordinal, X is orderisomorphic to kappa.
Now suppose f:kappa > P, an ordered set, and f is monotone. If fX is injective, then fX is a strictly monotone map from X to P; i.e., either P or its dual contains a chain isomorphic to X and therefore to kappa. On the other hand, if fX is constant, it follows from the monotonicity of f and the fact that X is unbounded in kappa that f is eventually constant.
Hence, if kappa is regular, and if P is an ordered set containing no chains of order type kappa or kappa^* [in particular, if P = P(S) where S < kappa], then every monotone function f:kappa > P is eventually constant.

