Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Help would be appreciated. The notes are poor on the subject, and im clueless.

Verify the following equalities:

A) SIII=βI, where S is λxyz.(xz)(yz) and I is λx.x

B) twice (twice) f x= β f(f(f(f x))), where twice is λfx.f(f x)

share|improve this question
We'll be more helpful if you don't delete the questions once you've solved them. Also, if it's homework, kindly tag it as such. –  Yuval Filmus Nov 23 '10 at 4:46
Sorry, new to this site, figured it was the kind of thing where once the question is solved you delete it. I'll change it back. The reason i'm asking a similar questio is lambda calc was just not explained well. Every other topic was except for this, so the 2 homework problems with lambda calc are the only ones giving me problems. Your help was amazing last time, i'd really appreciate it if you could do it again. –  jack Nov 23 '10 at 5:25
add comment

1 Answer

Try substituting the arguments in the definitions of the combinators.

share|improve this answer
When I originally tried that I got (x x)(x x) = λx.x and λfx.f(f x)(λfx.f(fx))fx=f(f(f(fx))) –  jack Nov 23 '10 at 6:18
SIII=(II)(II)=II=I –  Yuval Filmus Nov 23 '10 at 6:41
twice twice f x = twice (twice f) x = twice = twice f (twice f x) = twice f f(f(x) = f(f(f(f(x)))) –  Yuval Filmus Nov 23 '10 at 6:43
You just have to keep substituting. –  Yuval Filmus Nov 23 '10 at 6:44
I'm sorry (especially for the necropost), I don't understand your solution to b. you said... twice twice f x = twice (twice f) x -- how is that true? don't you have to apply the first twice before you can link the f to the second twice? After the first step, I find myself with: lambda(x) (twice(twice(x)) –  Daniel Jan 21 '12 at 23:57
show 2 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.