🔒 Locked

Lambda Beta (theorical computer science)

Started by Snatch Oct 21, 2005 at 3:11 AM 5 replies 1.5k views

Original Post

Oct 21, 2005 at 3:11 AM

I have to prove thate for all s which is an abstraction we have : lambda x.sx = s And I am completly stuck, I have try a prof by induction on t with s = lambda y.t but I can't prove the induction for the abstraction rule. I think about the fixpoint theorem but I am unable to apply it a useful way.Somebody as an idea ? It will be very helpful. Anyway, thank you to all of you who are going to try to do this prof. Best regards.

Roboguy

Oct 21, 2005 at 3:13 AM

This isn't homework, is it?

Snatch

Author

Snatch

Oct 21, 2005 at 3:15 AM

Yes it is !

Roboguy

Oct 21, 2005 at 3:50 AM

Well, you aren't supposed to post homework questions here:

Quote:
From the Math and Physics forum FAQ
3a. How should I ask for help on homework problems?

Since gamedev.net exists to support the game development community, and is not a homework site, please visit another website that is specifically dedicated to math education and homework specifically. Here are a few nice sites:

Math Goodies: Free Interactive Math Lessons, Homework Help, ...

That one is very nice, and has a dedicated homework forum.

Math.com - World of Math Online

Nice site, but I didn't see a forum

Algebra Homework Help at Algebra.com

AAA Math

Mathforum Discussion Groups - active, ongoing discussions on many topics related to math

I could be completely off, as I don't know too much about lambda calculus yet, it's about 0400 hours and I've had little (read: no) experience doing proofs, but I'll give a hint a shot:
s = λy.t
λx.sx = λx.(λy.t)x = (... β-reduction ...) = (... α-conversion ...) = s

ken9514

Oct 21, 2005 at 5:00 AM

rule: (Lx.M)N = M[x:=N]
substitute M with sx: (Lx.sx)N = sN

Snatch

Author

Snatch

Oct 21, 2005 at 5:17 AM

(Lx.sx)N = sN but from this, I must use the eta rule to have :
Lx.sx = s, the problem is that I am not allowed to use the eta rule ( only Lambda Beta ).

Anyway I thank you very much for your answers and I am really sorry about this break of the rules, I will be more careful next time.

grhodes_at_work

Mod

197

grhodes_at_work

Oct 21, 2005 at 2:50 PM

Homework post, closing thread. See Forum FAQ.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.