$1$ Introduction to Lambda Calculus

In this section, we will present a brief introduction to untyped lambda calculus.

The main purpose is to introduce the notions of alpha$-$equivalence and betaequivalence, which are subsequently used in typed lambda calculus.

$1\mathrm{.}1$ Lambda Terms

Let V be an infinite and enumerable set of objects called variables. The set of

lambda terms is the smallest subset A of $($V $\backslash$cup $\{(,),.,\backslash$lambda $\})$ such that:

$1.$ V $$ A$,$

$2.$ If M$,$ N in A$,$ then $($MN$)$ in A$,$

$3.$ If x in V and M in A$,$ then $(\backslash$lambda x$.$M$)$ in A$.$

Alternatively, A is the set inductively generated by the generating system whose

universe is V $\backslash$cup $\{(,),.,\backslash$lambda $\}$ and whose set of rules is:

x in V

x in A

M in A N in A

$($MN$)$ in A

x in V M in A

$(\backslash$lambda x$.$M$)$ in A

We will highlight some conventions to abbreviate the use of parentheses in

expressions. Outer parentheses are always omitted whenever possible. The

application is left associative. Thus, MNP abbreviates $($MN$)$P$.$ Application

has precedence over abstraction$.$ Thus, $\backslash$lambda x$.$MN abbreviates $\backslash$lambda x$.($MN$).$ Finally,

successive abstractions are combined into a single and associated from the right:

$\backslash$lambda x$.\backslash$lambda y$.$M abbreviates $\backslash$lambda x$.(\backslash$lambda y$.$M$).$

$1$

Set of Subterms

Now, we will illustrate how to define functions recursively on the set A$.$ The

following definition appears well$-$formed. However, it is important to highlight

that a certain detail was overlooked, that the generating system is either freely

generated or has the property of unique readability. This implies that a term

can only be formed from the rules in one unique way. For each x and for each

M$,$ N in A$,$ let st : A $->2$

A such that:

$1.$ st$($x$)=\{$x$\},$

$2.$ st$(($MN$))=$ st$($M$)\backslash$cup st$($N$)\backslash$cup $\{($MN$)\},$

$3.$ st$((\backslash$lambda x$.$M$))=$ st$($M$)\backslash$cup $\{(\backslash$lambda x$.$M$)\}.$

For each M in A$,$ we say that st$($M$)$ is the set of the subterms of M$.$

Free Variables

For each x in V and each M$,$ N in A$,$ let st : A $->2$

V

such that:

$1.$ free$($x$)=\{$x$\},$

$2.$ free$(($MN$))=$ free$($M$)\backslash$cup free$($N$),$

$3.$ free$((\backslash$lambda x$.$M$))=$ free$($M$)\{$x$\}.$

For each M in A$,$ we say that free$($M$)$ is the set of the free variables of M$.$

Closed Term or Combinator

A term M in A is a combinator $($or closed$)$ if free$($M$)=.$

$2$ Substitution

Let$$s define a partial function that leads terms into terms. If M and N are

terms and x is a variable, we denote by M$[$x :$=$ N$]$ the term obtained from M

by substituting every free occurrence of x in M with N$.$ Formally, we define:

x$[$x :$=$ N$]=$ N$,$

y$[$x :$=$ N$]=$ y$,$ if x $=$ y$,$

$($P Q$)[$x :$=$ N$]=($P$[$x :$=$ N$])($Q$[$x :$=$ N$]),$

$(\backslash$lambda xP$)[$x :$=$ N$]=\backslash$lambda x$.$P$,$

$(\backslash$lambda y$.$P$)[$x :$=$ N$]=\backslash$lambda y$($P$[$x :$=$ N$]),$ if x $=$ y$.$

This definition, for example, implies that $(\backslash$lambda x$.(\backslash$lambda y$.$x$))[$x :$=$ y$]$ equals $(\backslash$lambda y$.$y$),$

which is contrary to the expectation we might have regarding the notion of

$2$

substitution. Subsequently, we establish a side condition called $\backslash$alpha $-$equivalence

to legitimize when a substitution makes sense.

The next lemma illustrates how to establish properties involving the syntactic entities, the $\backslash$lambda $-$terms, of Lambda Calculus.

Lemma $1\mathrm{.}1.$ For every x in V and for all M$,$ N in A$,$ if x $/$ in free$($M$),$ then

M$[$x :$=$ N$]=$ M$.$

Proof. The proof is by induction on $|$M$|.$

Case $1$: M in V $.$

In this case, M $=$ x because x $$ in free$($M$),$ where M$[$x :$=$ N$]=$ M$.$

Case $2$: There exist P$,$ Q in A such that M $=($P Q$).$

Since x $$ in free$($M$),$ then x $$ in free$($P$)$ and x $$ in free$($Q$).$ Therefore, by the

induction hypothesis, P$[$x :$=$ N$]=$ P and Q$[$x :$=$ N$]=$ Q$.$ Hence,

$($P Q$)[$x :$=$ N$]=($P$[$x :$=$ N$]$Q$[$x :$=$ N$])=($P Q$).$

Case $3$: There exists P in A such that M $=(\backslash$lambda x$.$P$).$

In this case, $(\backslash$lambda x$.$P$)[$x :$=$ N$]=\backslash$lambda x$.$P$.$

Case $4$: There exists y $=$ x and P in $\backslash$Lambda such that M $=(\backslash$lambda y$.$P$).$

Since x $$ in free$($M$),$ then x $$ in free$($P$).$ By the induction hypothesis, P$[$x :$=$ N$]=$

P$.$ Therefore,

$(\backslash$lambda y$.$P$)[$x :$=$ N$]=\backslash$lambda y$.($P$[$x :$=$ N$])=\backslash$lambda y$.$P$.$

We now define when a substitution is properly defined. Let M and N be

terms and x a variable. We say that N can substitute x in M$,$ and we write

M$[$x :$=$ N$],$ if for every free variable y in M$,(\backslash$lambda y$.$P$)$ is a subterm of M$,$ that

is$,$ if $(\backslash$lambda y$.$P$)$ in st$($M$),$ then y is not free in P$,$ or in other words, any subterm

of M that can capture a free variable of N does not contain x as one of its free

variables.

$3$ Exercise $1$

For every x $=$ y in V and every M$,$ N$,$ L in $\backslash$Lambda $,$ if

$($i$)$ x $/$ in free$($L$)$ or y $/$ in free$($M$),$ and

$($ii$)$ M$[$x :$=$ N$],$ N$[$y :$=$ L$]$ and M$[$x :$=$ N$][$y :$=$ L$],$

then

$($a$)$ M$[$y :$=$ L$]$ andM$[$y :$=$ L$][$x :$=$ N$[$y :$=$ L$]],$ and

$($b$)$ M$[$x :$=$ N$][$y :$=$ L$]=$ M$[$y :$=$ L$][$x :$=$ N$][$y :$=$ L$].$

Proof. The proof is by induction on $|$M$|.$

Case $1$: M in V $.$

Prove!

Case $2$: There exists P in A such that M $=(\backslash$lambda x$.$P$).$

Prove!

Case $3$: There exists P in A and z in V $\{$x$,$ y$\}$ such that M $=(\backslash$lambda z$.$P$).$

Prove!

Case $4$: Prove the remaining case$($s$).$

$3$