The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Push Down Lemma
Replies: 10   Last Post: Feb 11, 2013 4:00 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Butch Malahide

Posts: 894
Registered: 6/29/05
Re: Push Down Lemma
Posted: Feb 8, 2013 11:43 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Feb 8, 9:10 pm, William Elliot <> wrote:
> On Thu, 7 Feb 2013, Butch Malahide wrote:
> > On Feb 7, 3:43 am, William Elliot <> 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:
> >'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 well-ordered 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 f|X
is either injective or constant. Since kappa is an initial ordinal, X
is order-isomorphic to kappa.

Now suppose f:kappa --> P, an ordered set, and f is monotone. If f|X
is injective, then f|X 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 f|X 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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.