# lambda calculus, equalities

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)$

-
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

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))))$$

-