Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 David C. Ullrich Posts: 21,553 Registered: 12/6/04
Re: Push Down Lemma
Posted: Feb 7, 2013 11:27 AM

On Thu, 7 Feb 2013 04:13:09 -0800 (PST), Butch Malahide
<fred.galvin@gmail.com> 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
>referring to the celebrated "Pressing Down Lemma" aka Fodor's Lemma:
>
>http://en.wikipedia.org/wiki/Fodor's_lemma
>

>> 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|,

Ignoring the question of whether this has anything to do with
what William meant: I'm very confused. It seems obvious to
me that this is true even without the "well-ordered". But
something you say below explciitly contradicts that...

>and neither of course does its dual. Right. The most
>familiar special case is that P(omega), although it contains
>uncountable chains ordered like the reals,

I'm missing something. How can P(omega) contain
an uncountable chain?

Say W is a chain in P(omega). For every s in W there
exists n(s) in s, such that n(s) is not in s' for any
s' less than s...

Oops, that's wrong - quantifier
confusion. I'll leave the nonsense there just to
be a regular sc.math sort of guy.

Never mind my delusion that this is clearly false.
But how does one see that P(N) contains a chain
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.

Date Subject Author
2/7/13 William Elliot
2/7/13 J. Antonio Perez M.
2/7/13 Butch Malahide
2/7/13 David C. Ullrich
2/7/13 David Hartley
2/7/13 David C. Ullrich
2/8/13 William Elliot
2/8/13 Butch Malahide
2/9/13 William Elliot
2/10/13 Butch Malahide
2/11/13 William Elliot