Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Verify the following equalities:

  • Verify the equality $$\mathsf{SIII}=_β\mathsf{I}$$ where $\mathsf{S} = λxyz.(xz)(yz) \quad \mathsf{I}= λx.x$

  • Verify the equality $$\operatorname{twice} (\operatorname{twice}) f x =_β f(f(f(f x)))$$ where $\operatorname{twice} = λfx.f(f x)$

share|cite|improve this question

Try substituting the arguments in the definitions of the combinators.

share|cite|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

I am posting this answer to make solutions more clear. $$ \mathsf{SIII}=_\beta (λxyz.(xz)(yz)) \mathsf{III} =_\beta (\mathsf{II})(\mathsf{II}) $$ Remember that $\mathsf{I}=\lambda x.x$ is the operator that does nothing. This means that for every lambda expression $M$, you have $\mathsf{I}M =_\beta M$.

This implies that: $$\mathsf{II} =_\beta (\lambda x.x)(\lambda x.x)=\lambda x.x = \mathsf{I}$$ And so we have $$ (\mathsf{II})(\mathsf{II}) =_\beta (\mathsf{I})(\mathsf{I}) =_\beta = \mathsf{II} =_\beta \mathsf{I}$$

The second one is easier

$$ \operatorname{twice} \operatorname{twice} f x = \operatorname{twice} (\operatorname{twice} f) x = \operatorname{twice} f (\operatorname{twice} f x) = \operatorname{twice} f f(f(x) = f(f(f(f(x)))) $$

share|cite|improve this answer

Your Answer


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