Deductive lambda calculus

Deductive lambda calculus considers what happens when lambda terms are regarded as mathematical expressions. One interpretation of the untyped lambda calculus is as a programming language where evaluation proceeds by performing reductions on an expression until it is in normal form. In this interpretation, if the expression never reduces to normal form then the program never terminates, and the value is undefined. Considered as a mathematical deductive system, each reduction would not alter the value of the expression. The expression would equal the reduction of the expression.

History

Alonzo Church invented the lambda calculus in the 1930s, originally to provide a new and simpler basis for mathematics. However soon after inventing it major logic problems were identified with the definition of the lambda abstraction: The Kleene–Rosser paradox is an implementation of Richard's paradox in the lambda calculus. Haskell Curry found that the key step in this paradox could be used to implement the simpler Curry's paradox. The existence of these paradoxes meant that the lambda calculus could not be both consistent and complete as a deductive system.

Haskell Curry studied of illative (deductive) combinatory logic in 1941. Combinatory logic is closely related to lambda calculus, and the same paradoxes exist in each.

Later the lambda calculus was resurrected as a definition of a programming language.

Introduction

Lambda calculus is the model and inspiration for the development of functional programming languages. These languages implement the lambda abstraction, and use it in conjunction with application of functions, and types.

The use of lambda abstractions, which are then embedded into other mathematical systems, and used as a deductive system, leads to a number of problems, such as Curry's paradox. The problems are related to the definition of the lambda abstraction and the definition and use of functions as the basic type in lambda calculus. This article describes these problems and how they arise.

This is not a criticism of pure lambda calculus, and lambda calculus as a pure system is not the primary topic here. The problems arise with the interaction of lambda calculus with other mathematical systems. Being aware of the problems allows them to be avoided in some cases.

Terminology

For this discussion, the lambda abstraction is added as an extra operator in mathematics. The usual domains, such as Boolean and real will be available. Mathematical equality will be applied to these domains. The purpose is to see what problems arise from this definition.

Function application will be represented using the lambda calculus syntax. So multiplication will be represented by a dot. Also, for some examples, the let expression will be used.

The following table summarizes;

Name	Notation
Lambda abstraction.	[math]\displaystyle{ \lambda v.y }[/math]
Application of the function f to x	[math]\displaystyle{ f\ x }[/math]
Multiplication of a by b	[math]\displaystyle{ a \cdot b }[/math]
Let x in y	[math]\displaystyle{ \operatorname{let} x \operatorname{in} y }[/math]
Mathematical equality	[math]\displaystyle{ m = n }[/math]
Beta reducible equality	[math]\displaystyle{ m \ \underset{\beta}=\ n }[/math]

Interpretation of lambda calculus as mathematics

In the mathematical interpretation, lambda terms represent values. Eta and beta reductions are deductive steps that do not alter the values of expressions.

[math]\displaystyle{ \operatorname{eta-reduct}[X] = X }[/math]

[math]\displaystyle{ \operatorname{beta-reduct}[X] = X }[/math]

Eta reduction as mathematics

An eta-reduct is defined by,

[math]\displaystyle{ x \not \in \operatorname{FV}(f) \to \operatorname{eta-reduct}[\lambda x.(f\ x)] = f }[/math]

In the mathematical interpretation,

[math]\displaystyle{ \operatorname{eta-reduct}[X] = X }[/math]

Taking f to be a variable then,

[math]\displaystyle{ \lambda x.(f\ x) = f }[/math]

or by letting [math]\displaystyle{ f\ x = y }[/math]

[math]\displaystyle{ f\ x = y \iff f = \lambda x.y }[/math]

This definition defines [math]\displaystyle{ \lambda x.y }[/math] to be the solution for f in the equation,

[math]\displaystyle{ f\ x = y }[/math]

Beta reduction as mathematics

A beta reduct is,

[math]\displaystyle{ \operatorname{beta-reduct}[(\lambda x.b)\ z] = b[x:=z] }[/math]

and as,

[math]\displaystyle{ \operatorname{beta-reduct}[X] = X }[/math]

then,

[math]\displaystyle{ (\lambda x.b)\ z = b[x:=z] }[/math]

This rule is implied by the instantiation of quantified variables. If,

[math]\displaystyle{ \forall x: f\ x = y }[/math]

then [math]\displaystyle{ f\ z }[/math] is the expression y with the quantified variable x instantiated as z.

[math]\displaystyle{ f\ z = y[x:=z] }[/math]

so,

[math]\displaystyle{ (\lambda x.y)\ z = y[x:=z] }[/math]

As beta reduction is implied from eta reduction, there is no contradiction between the two definitions.

Inconsistency with the Principle of Bivalence

Let z be a Boolean; then we can form an equation with no solutions,

[math]\displaystyle{ z = \neg z }[/math]

To solve this equation by recursion, we introduce a new function f defined by,

[math]\displaystyle{ f\ n = \neg (n\ n) }[/math]

where n is an auxiliary variable to hold the recursion value. (We take it that [math]\displaystyle{ \neg }[/math] still returns a Boolean even if it is given a non-Boolean argument.) By an eta-reduction, we obtain,

[math]\displaystyle{ f = \lambda x.\neg (x\ x) }[/math]

And then,

[math]\displaystyle{ \begin{align} f\ f &= (\lambda x.\neg (x\ x)) (\lambda x.\neg (x\ x)) \\ &= \neg ((\lambda x.\neg (x\ x)) (\lambda x.\neg (x\ x))) \\ &= \neg (f\ f) \end{align} }[/math]

Then f f is neither true nor false, and as f f is a Boolean value (on any x, f returns the Boolean [math]\displaystyle{ \neg (x\ x) }[/math]) then we see that f f is neither true nor false; it also demonstrates that negation makes less sense when applied to non-logical values.

Intensional versus extensional equality

Another difficulty for the interpretation of lambda calculus as a deductive system is the representation of values as lambda terms, which represent functions. The untyped lambda calculus is implemented by performing reductions on a lambda term, until the term is in normal form. The intensional interpretation of equality is that the reduction of a lambda term to normal form is the value of the lambda term.

This interpretation considers the identity of a lambda expression to be its structure. Two lambda terms are equal if they are alpha convertible.

The extensional definition of function equality is that two functions are equal if they perform the same mapping;

[math]\displaystyle{ f = g \iff (\forall x f\ x = g\ x) }[/math]

One way to describe this is that extensional equality describes equality of functions, where as intensional equality describes equality of function implementations.

The extensional definition of equality is not equivalent to the intensional definition. This can be seen in the example below. This inequivalence is created by considering lambda terms as values. In typed lambda calculus this problem is circumvented, because built-in types may be added to carry values that are in a canonical form and have both extensional and intensional equality.

Example

In arithmetic, the distributive law implies that [math]\displaystyle{ 2 * (r + s) = 2*r + 2*s }[/math]. Using the Church encoding of numerals the left and right hand sides may be represented as lambda terms.

So the distributive law says that the two functions,

[math]\displaystyle{ \lambda r.\lambda s.2 * (r + s) = \lambda r.\lambda s.2*r + 2*s }[/math]

are equal, as functions on Church numerals. (Here we encounter a technical weakness of the untyped lambda calculus: there is no way to restrict the domain of a function to the Church numerals. In the following argument we will ignore this difficulty, by pretending that "all" lambda expressions are Church numerals.) The distributive law should apply if the Church numerals provided a satisfactory implementation of numbers.

[math]\displaystyle{ \begin{align} \lambda r.\lambda s.\operatorname{mult}\ 2\ (\operatorname{plus}\ r\ s) &= \lambda r.\lambda s.\operatorname{plus}\ (\operatorname{mult}\ 2\ r)\ (\operatorname{mult}\ 2\ s) \\ {\scriptstyle \lambda r.\lambda s.(\lambda m.\lambda n.\lambda f. m\ (n\ f))\ (\lambda f.\lambda x.f\ (f\ x))\ ((\lambda m.\lambda n.\lambda f.\lambda x. m\ f\ (n\ f\ x))\ r\ s)} &= {\scriptstyle \lambda r.\lambda s.(\lambda m.\lambda n.\lambda f.\lambda x. m\ f\ (n\ f\ x))\ ((\lambda m.\lambda n.\lambda f. m\ (n\ f))\ (\lambda f.\lambda x.f\ (f\ x))\ r)\ ((\lambda m.\lambda n.\lambda f. m\ (n\ f))\ (\lambda f.\lambda x.f\ (f\ x))\ s)} \\ \lambda r.\lambda s.\lambda f.\lambda x.r\ f\ (s\ f\ (r\ f\ (s\ f\ x))) &= \lambda r.\lambda s.\lambda f.\lambda x.r\ f\ (r\ f\ (s\ f\ (s\ f\ x))) \end{align} }[/math]

The two terms beta reduce to similar expressions. Still they are not alpha convertible, or even eta convertible (the latter follows because both terms are already in eta-long form). So according to the intensional definition of equality, the expressions are not equal. But if the two functions are applied to the same Church numerals they produce the same result, by the distributive law; thus they are extensionally equal.

This is a significant problem, as it means that the intensional value of a lambda-term may change under extensionally valid transformations. A solution to this problem is to introduce an omega-rule,

• If, for all lambda-expressions t we have [math]\displaystyle{ f\ t \ \underset{\beta}=\ g\ t }[/math], then [math]\displaystyle{ f \ \underset{\beta}=\ g }[/math].

In our situation, "all lambda-expressions" means "all Church numerals", so this is an omega-rule in the standard sense as well. Note that the omega-rule implies the eta-rule, since [math]\displaystyle{ f\ t \ \underset{\beta}=\ (\lambda x.f\ x)\ t }[/math] by a beta-reduction on the right side.

Set theoretic domain

Lambda abstractions are functions of functions. A natural step is to define a domain for the lambda abstraction as a set of all functions.

The set of all functions from a domain D to a range R is given by K in,

[math]\displaystyle{ f \in K \iff (\forall x : x \in D \implies f\ x \in R) }[/math]

Then the (imaginary) definition of the set of all functions of functions is given by F in,

[math]\displaystyle{ f \in F \iff (\forall x : x \in F \implies f\ x \in F) }[/math]

This definition cannot be formulated in an axiomatic set theory; and this naive equation, even if it could be written in a set theory, has no solutions.

Now lambda calculus is defined by beta reductions and eta reductions. Interpreting reduction as defining equality gives an implicit domain for the lambda calculus. The rules are,

• Every lambda abstraction has one value.
• The beta reduction of a lambda term has the same value.
• The eta reduction of a lambda term has the same value.
• Alpha convertible lambda terms are equal.
• [If the omega-rule is present] "omega-equivalent" lambda terms are equal.
• If two lambda terms can not be shown to be equal by the above rules, they are not equal.

If two lambda terms may be reduced to normal form then the Church–Rosser theorem may be used to show that they are equal if their normal forms are alpha convertible.

If one or both of the terms are not normalizing then the undecidability of equivalence shows that in general there is no algorithm to determine if two lambda terms are equal. In general this makes it impossible to know what the distinct elements of the lambda calculus domain are.

Example: No solutions → one solution

For example the equation [math]\displaystyle{ x = \neg x }[/math] may be coded with Church encoding and using Curry's Y combinator as,

[math]\displaystyle{ \operatorname{not}_1 = \lambda p.\lambda a.\lambda b.p\ b\ a }[/math]

[math]\displaystyle{ (\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))) (\lambda p.\lambda a.\lambda b.p\ b\ a) }[/math]

And the recursion is,

[math]\displaystyle{ (\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x))\ (\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x)) }[/math]

[math]\displaystyle{ (\lambda p.\lambda a.\lambda b.p\ b\ a)\ ((\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x))\ (\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x))) }[/math]

[math]\displaystyle{ \lambda a.\lambda b.((\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x))\ (\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x)))\ b\ a }[/math]

...

[math]\displaystyle{ \lambda a.\lambda b.(\lambda a.\lambda b.((\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x))\ (\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x)))\ b\ a)\ b\ a }[/math]

... (beta and then eta reduction)

[math]\displaystyle{ (\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x))\ (\lambda x.(\lambda p.\lambda a.\lambda b.p\ b\ a)\ (x\ x)) }[/math]

Which is the first line and will recurse indefinitely. The expression never reduces to normal form. However every lambda term in the reduction represents the same value. This value is distinct from the encodings for true or false. It is not part of the Boolean domain but it exists in the lambda calculus domain.

Example: Multiple solutions → one solution

Using division and signed numbers, the Y combinator may be used to define an expression representing a whole number square root. The Church encoding may also be extended further to rational and real numbers, so that a real square root may be defined. The Church-Turing thesis implies that any computable operator (and its operands) can be represented in lambda calculus.

Using such an encoding,

[math]\displaystyle{ x^2 = n \Rightarrow x = \frac{n}{x} \Rightarrow f\ x = \frac{n}{x} \land Y\ f = x }[/math]

Using the implementation of divide then,

[math]\displaystyle{ Y (\operatorname{divide} n) }[/math]

represents two values in the domain of the signed numbers, if n is not equal to zero. However it is a lambda expression so has only one value in the lambda calculus domain. Beta reduction of this lambda term never reaches normal form. However it represents a value, so a single value in the lambda calculus domain represents two values in the signed number domain.

See also

• Lambda calculus
• Let expression
• Church encoding