2
$\begingroup$

I am going through beta reduction in lambda calculus . And beta reduction to my understanding is an act of substitution like in the following :

$ (\lambda x.P) M $ is said to be beta reduced to : $ [M/x]P $

So then my course was led to encoding the Booleans in lambda calculus . And the following two expressions were used to encode the true and false boolean expressions :

$ \lambda xy.x$ for true denoted by T

and $ \lambda xy.y$ for false denoted by F

The basic idea behind constructing these expressions is to find expressions that analogically mimic the "and" operation if the "application" is the couterpart of "and"

So , for the above two expressions the book says $TT = T $ ,$ FF = F $, $TF= F $ , $FT=F $.

I tried to do the beta reduction for ($ \lambda xy.x$ )($ \lambda xy.x$ ), which means [ $ \lambda xy.x$ /$x$]$ \lambda xy.x$ .

I could break $ \lambda xy.x$ as $\lambda x . \lambda y.xy $ but I am unable to find how to use this to advantage to get the final reduction .

How to carry on the reduction from here so as to prove that ($ \lambda xy.x$ )($ \lambda xy.x$ ) = $ \lambda xy.x$ ?

$\endgroup$
  • 1
    $\begingroup$ You misread/misheard/misunderstood what the exercise was. $T$ expects two parameters (in a curried sense). You can intuit that there will be trouble because $TT$ expect three parameters while $T$ only expects two. More formally, you can readily verify that $TXY=X$ for any terms $X$ and $Y$. If $TT=T$ then you'd have $XZ=TXYZ=TTXYZ=TYZ=Y$ which would mean $XZ=Y$ no matter what $X$, $Z$, and $Y$ were. I suspect the exercise is to find a lambda term $A$ such that $A$ behaves like "and", i.e. $ATT=T$ and $ATF=AFT=AFF=F$. $\endgroup$ – Derek Elkins Mar 3 '18 at 21:29
  • $\begingroup$ @DerekElkins : I think there is a big probability that I have misinterpreted the content and I will check it and try to understand again . Thanks a lot. $\endgroup$ – Agnivesh Singh Mar 3 '18 at 23:40
2
$\begingroup$

It is helpful to look at $\lambda$ abstractions as functions, e.g. $T \equiv \lambda x y. x$ "is" a function that takes $2$ variables as arguments ($x,y$; those between "$\lambda$" and ".") and returns the first of them - $x$ (expression after the "."). On the other hand, we define $F$ to also take $2$ arguments and return the second one - $y$.

In this sense, $\beta$-reduction is a process of evaluating a function at given values (the ones that abstraction is applied to). One should be careful about $\alpha$-renaming and have in mind currying, but we will not go into that here.

Let's now define the $AND$ operator.

What does it take as arguments? We can also think of it as a function, and therefore it must take $2$ arguments (truth values), so we would define it something like \begin{equation} AND := \lambda a b.\ <body,\ i.e. what\ it\ returns>. \end{equation}

What does it need to return? If it receives $T$ and $T$ for it's arguments, it must return $T$. Otherwise, it returns $F$.

Constructing the body. Having in mind that $a$ and $b$ will be substituted with $T$ or $F$, we can use them in the body of $AND$. We will use their property of returning the first or second argument. Consider the following definition; \begin{equation} AND := \lambda a b.\ a\ b\ F \end{equation} Upon receiving its arguments $a$ and $b$, operator $AND$ is returning the application of its first argument (and we know it will be a "function" of $2$ arguments that returns either its first or the second argument) onto its second argument and $F$. Therefore, if the first argument ($a$) happens to be $T$, we return the second argument ($b$) as a solution (in other words, the result of $AND\ T\ b$ is $b$). If the first argument ($a$) happens to be $F$, we return $F$.

Cases. There are $4$ cases that can happen.

  • $AND\ F\ F$. This will evaluate as follows: \begin{equation} (\lambda a b.\ a\ b\ F)\ F\ F = F\ F\ F = (\lambda x y.\ y)\ F\ F = F \end{equation}
  • $AND\ F\ T$. This will evaluate as follows: \begin{equation} (\lambda a b.\ a\ b\ F)\ F\ T = F\ T\ F = (\lambda x y.\ y)\ T\ F = F \end{equation}
  • $AND\ T\ F$. This will evaluate as follows: \begin{equation} (\lambda a b.\ a\ b\ F)\ T\ F = T\ F\ F = (\lambda x y.\ x)\ F\ F = F \end{equation}
  • $AND\ T\ T$. This will evaluate as follows: \begin{equation} (\lambda a b.\ a\ b\ F)\ T\ T = T\ T\ F = (\lambda x y.\ x)\ T\ F = T \end{equation}

This is a somewhat friendly $\lambda$-calculus workflow I presented here, but I think it is the right approach for someone who is starting to learn about it and needs some intuitive notes on its nature.

For further research, following links should be useful as a starting point;

$\endgroup$

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.