I'm taking one of my last graduate classes but have been struggling with some reductions in lambda calculus. On our last assignment one of the problems was the following:

This question is on defining the predecessor function $pred$ on the Church numerals.

Let $G = \lambda xgh.(h (g x))$.

Recall that the combinators:

$$\begin{align}K &= \lambda xy.x\\ I &= \lambda x.x\end{align}$$

(a) Reduce $(G f)(K x)$ to its $\beta$-normal form.

(b) Reduce $(G f)((G f)(K x))$ to its $\beta$-normal form.

(c) $pred$ is defined as: $\lambda nfx.(n (G f) (K x) I)$

Show that $$pred\ 3 \stackrel{\alpha\beta}= 2.$$

I really just want to make sure I'm heading in the right direction for (a).

Edit updated work with proper syntax

$(G f) = (\lambda xgh.(h (g x))) f$

$= \lambda gh.(h(gf))$

$(K x) = (\lambda xy.x) x$

$= \lambda y.z$ <-$(\alpha sub)$

$(G f)(K x) = (\lambda gh.(h(g f))) \lambda y.z$

$= \lambda h.(h((\lambda y.z) f))$

edit can the above be simplified to this?

$= \lambda h.(h (z))$


Go through it again. I caught at least one mistake:

You wrote $G f = \lambda x g h. (h (g x)) f$, which is incorrect. You are missing parentheses. It should be: $G f = (\lambda x g h. (h (g x))) f$, which then reduces to $\lambda g h. (h (g f)))$.

It might help if you didn't put the frivolous parentheses around each of the variables. The syntax is not λ(x). <stuff>. It should be written "λx. <stuff>".

Also, by convention, you can group together multiple binders. Instead of $λx. λg. λh. h(gx)$, write it as $λxgh.h(gx)$. The more dots and parentheses in your expression, the more likely you'll screw up a tedious calculation.

  • $\begingroup$ Thanks for replying, I prefer writing in the manner you described just wasn't sure if I was missing something. My Prof. for his own preferences writes it out like I did in my post. I updated my initial post to reflect proper syntax. I still came to a similar result, does that appear to be beta-normal form? edit I did one more beta-redex but not sure if it's legal $\endgroup$ – z0nghits Oct 3 '13 at 21:12
  • 2
    $\begingroup$ Just briefly looking over your edit, you have a line: (Kx)=(λxy.x)x =λy.z <-(αsub). That is an illegal use of α-conversion. There's also no need to α-convert at all. Try it using the more correct expansion: K x = (λxy.x)x = λy.x. Note that x is a free variable now. $\endgroup$ – Tac-Tics Oct 4 '13 at 15:53
  • $\begingroup$ Also, mind your parentheses! (λgh.(h(gf)))λy.z will cause you trauma later on. Try (λgh.(h(gf)))(λy.z) instead (with the parens around the argument. $\endgroup$ – Tac-Tics Oct 4 '13 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.