lambda calculus, equalities

Question

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)

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

Yuval Filmus · Answer 1 · 2010-11-23 06:15:58Z

up vote 1 down vote

Try substituting the arguments in the definitions of the combinators.

edited Nov 23 '10 at 6:15

answered Nov 23 '10 at 4:58

Yuval Filmus
25.9k2871

	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

1 Answer