HTML reading edition · 32 source pages · Open the source PDF

The Lambda-Calculus is Nominal Algebraic

Murdoch J. Gabbay1 and Aad Mathijssen2,3

1 Introduction

The λ-calculus is fundamental in the study of logic and computation. Partly this is because it is a tool to study functions and functions are an important object of study in this field. Partly this is because the λ-calculus seems to be, for homo sapiens, an ergonomic formal syntax.

Definition 1

λ-terms g, h, k are inductively defined by

g ::= a | λa.g | gg | c.

In this paper we will write -[a↦ → -] as shorthand for (λa.-)-. Thus g[a↦ →h] stands for (λa.g)h and not for the term resulting from ‘substituting h for a in g’ (we write that as g[h/a], see Definition 44).

The λ-calculus represents functions in programming languages [25, 31], logic [7, 20], theorem-provers [3, 24], higher-order rewriting [5], and much more besides. However, the ‘λ’ in the λ-calculus has proved resistent to a treatment in universal algebra [8]. For example the property that

“(λa.g)[b↦ →h] = λa.(g[b↦ →h]) when a does not occur free in h”

cannot be represented in an algebraic framework, at least not obviously so, because of the freshness condition ‘a does not occur free in h’ which is necessary to avoid ‘accidental capture’ by λ. Similarly for the property “λa.(ga) = g when a does not occur free in g”.

Nominal algebra is a form of universal algebra enriched with primitive constructs to handle names, binding, and freshness conditions — just like those that appear in informal specifications of the λ-calculus and other languages with binders. Nominal algebra has the feature that, thanks to the enriched constructs, it allows fully formal algebraic reasoning which is pleasingly close to informal practice, including explicit reasoning on α-renaming and freshness side-conditions.

(var↦→) ⊢ a[a↦ →X] = X(#↦→) a#Z ⊢ Z[a↦ →X] = Z(app↦→) ⊢ (Z′Z)[a↦ →X] = (Z′[a↦ →X])(Z[a↦ →X])(abs↦→) b#X ⊢ (λb.Z)[a↦ →X] = λb.(Z[a↦ →X])(id↦→) ⊢ Z[a↦ →a] = Z
Figure 1. Axioms of ULAM

In this paper we introduce ULAM (Figure 1), a nominal algebra theory for the untyped λ-calculus. The axioms of ULAM make fundamental use of characteristic ‘nominal’ features of nominal algebra:

• We use nominal unknowns Z, Z′, and X to represent unknown elements. Instantiation of nominal unknowns does not avoid capture; see Definition 11.

• Freshness conditions a#Z, b#X, and b#Z are a framework to prevent ‘accidental capture’ of names by binders.

We shall prove that ULAM is sound and complete with respect to a model constructed out of λ-terms quotiented by αβ-equivalence; the rest of the paper makes these observations formal.

Nominal techniques subscribe to a mathematical view according to which names are first-class entities in the denotation. This was used, for example, to develop the Gabbay-Pitts И quantifier and the Gabbay-Pitts model of α-abstraction [17]. A traditional view is that names arise as a syntax for talking about inputs to functions, and therefore they range over elements of the underlying domain.1 The λ-calculus expresses this latter idea. With ULAM our nominal algebraic axiomatisation of the λ-calculus we make a novel connection between the two worlds; the axioms of ULAM express the properties that must be added to convert a nominal-style atom into a λ-calculus style variable, and a nominal-style abstraction into a λ-calculus binding.

Map of the paper. Section 2 introduces nominal algebra, giving basic definitions and results about syntax, freshness conditions, equality, and nominal algebra theories. Section 3 introduces the syntax and operational semantics of the untyped λ-calculus. Section 4 proves that ULAM is sound and complete (Subsections 4.1 and 4.2), and that it is conservative over the native nominal terms theory of α-equivalence (Subsection 4.3). The most technical material in this paper is concentrated in the proofs in Subsection 4.2. Finally, Section 5 discusses related and future work.

2 Nominal algebra

2.1 The syntax of nominal terms

We define a syntax of nominal terms. It is tailored to our application to the untyped λ-calculus; see elsewhere for general treatments [32, 13, 14, 23].

Definition 2

Fix the following:

• A countably infinite set of atoms A. We let a, b, c, . . . range over atoms. These model λ-calculus variables.

We use a permutative convention that a and b range permutatively over atoms unless stated otherwise. For example in (#ab) from Figure 3, and in (perm) from Figure 4, a and b range over any two distinct atoms.

• A countably infinite collection of unknowns. We let X, Y, Z, T, U, . . . range over unknowns. These represent unknown elements in nominal algebra axioms.

We also use a permutative convention that X and Y range permutatively over unknowns. In Figure 1 we make a fixed but arbitrary choice of unknown. That is, ULAM contains five axioms — not infinitely many for every possible a, b, X, Z, and Z′ — but the choice is immaterial for all practical purposes as we shall see in (ax) of Figure 4 and in Definition 25.

• A possibly infinite collection of constant symbols c ∈ C.

Unknowns, atoms, and other distinct syntactic classes, are assumed disjoint.

Remark 3

For the reader’s convenience we provide Figure 2: a ‘cheat-sheet’ linking in a single list concepts from informal practice to some of the main definitions and lemmas which will soon follow. This list, by its nature, contains forward references.

We can now set about building the machinery of nominal algebra.

- a is an atom. It represents an object-level variable symbol. - X is an unknown. It represents a meta-variable. - π · t is a permutative renaming of the atoms in t. We use this to provide a ‘naturally capture-avoiding’ theory of α-equivalence. π · X has the intuition of ‘permute π in whatever X is instantiated to’. - tσ is t with meta-variables substituted, we can think of this as in- stantiation. If π · X appears in t then π acts on σ(X) and the result is included in tσ. - a#t asserts a freshness. It has the intuition ‘a cannot be free in t’. a#X has the intuition of ‘a is fresh for whatever X is instantiated to’.
Figure 2. Cheat-sheet for intuitive reading of notation
Definition 4

A permutation π of atoms is a bijection on atoms with finite support meaning that for some finite set of atoms π(a) ≠ a, and for all other atoms π(a) = a. In words: For ‘most’ atoms π is the identity.

Definition 5

Let terms t, u, v be inductively defined by:

t ::= a | π · X | λa.t | tt | c.

We write syntactic identity of terms t, u as t ≡u to distinguish it from ‘=’ the derivable equality-in-freshness-context we construct in Subsection 2.3. Note that if π = π′ then π · X ≡π′ · X, since permutations are represented by themselves. Also note that we do not quotient terms in any way.

We give some intuition of terms:

• An atom a represents a λ-calculus variable symbol.

• We call π · X a moderated unknown. This represents an unknown term, on which a permutation of atoms will be performed when X is instantiated. The use of permutations provides primitive support for α-equivalence.

• t′t represents the usual λ-calculus application.

• λa.t represents the usual λ-abstraction. Recall from the Introduction that we write t[a↦ →u] as shorthand for (λa.t)u, for example in Figure 1.

A typed version of this syntax is possible; the interaction between atoms, unknowns, permutations, and λ-abstraction raises subtle and unexpected issues which have been investigated independently in the general framework of nominal rewriting [12]. Types would cause no essential difficulties for the results which follow.

2.2 Permutation, substitution and freshness

We need some more notation to talk about permutations (Definition 4).

Definition 6

As usual we write id for the identity permutation, π-1 for the inverse of π, and π ◦π′ for the composition of π and π′, i.e. (π ◦π′)(a) = π(π′(a)). id is also the identity of composition: id ◦π = π and π ◦ id = π. Importantly, we shall write (a b) for the permutation that swaps a and b, i.e. the permutation that maps a to b and vice versa, and maps all other c to themselves; note that this is the same permutation as (b a). We may drop ◦ between swappings, writing for example (a b) ◦ (b c) as (a b)(b c); this is a standard notation in the theory of permutations. We may write X as shorthand for id · X.

Definition 7

We write a ∈π when π(a) ≠ a. We extend this inductively to a ∈t as follows:

a ∈aa ∈π a ∈π · Xa ∈t′a ∈t′ta ∈t a ∈t′t a ∈λa.ta ∈t a ∈λb.t

If a ∈t is not derivable write a ∉t. We read ‘a ∈’ as ‘a occurs in’.

We also write X ∈t when X occurs anywhere in t, and X ∉t otherwise. Occurrence is literal, for example a ∈λa.a and a ∈ (a b) · X.

Definition 8

Define a permutation action π · t inductively by:

π · a ≡π(a) π · (π′ · X) ≡(π ◦π′) · X π · λa.t ≡λ(π(a)).(π · t)π · (t′t) ≡(π · t′)(π · t) π · c ≡c.

Intuitively π propagates through the structure of t until it reaches an atom or a moderated unknown. Note that in the clause for λ, π acts also on the ‘a’. Following Cheney (verbal communication) we say that the permutation action is inherently capture-avoiding, meaning that it can act uniformly and will not require special behaviour for binders. For example:

(a b) · λa.X ≡λb.(a b) · X
Lemma 9

π · (π′ · t) ≡ (π ◦π′) · t and id · t ≡t.

Proof

By an easy induction on the structure of t using the fact that composition of permutations is just composition of functions and so is associative.

■

Definition 10

We call a substitution σ a function from unknowns to terms. We write [t1/X1, . . . , tn/Xn] for the substitution mapping Xi to ti for 1 ≤i ≤n, and mapping Y to Y for all other Y .

Definition 11

Define a substitution action tσ inductively by:

aσ ≡a (π · X)σ ≡π · σ(X) (λa.t)σ ≡λa.(tσ)(t′t)σ ≡(t′σ)(tσ) cσ ≡c.

We may call tσ an instance of t.

For example:

(λa.X)[a/X] ≡λa.(X[a/X]) ≡λa.a
(λb.(a b) · X)[a/X] ≡λb.(((a b) · X)[a/X]) ≡λb.((a b) · (X[a/X])) ≡λb.(a b) · a ≡λb.b
Xσ ≡σ(X)

The final example is direct from the definition and Lemma 9; σ(X) is ‘the function σ applied to X’, whereas Xσ is shorthand for (id · X)σ.

Intuitively, σ propagates through the structure of t until it reaches an atom or a moderated unknown. σ ‘evaporates’ on an atom a, and on π · X it instantiates X to σ(X) — then the permutation acts on σ(X).

Substitution does not avoid capture; (λa.X)[a/X] ≡λa.a. There is an deliberate analogy here with context substitution, which is the substitution used when we write ‘let - be a in λa.-’, or ‘suppose t is a in λa.t’; we obtain λa.a. Moderated unknowns behave exactly like the ‘hole’ - in syntactic contexts — except that an unknown can occur multiple times in a nominal term; unknowns occur in terms with a moderating permutation because this is needed, along with freshness contexts, to manage α-equivalence.

Recall from Definition 11 that (π · X)σ ≡π · σ(X). This extends easily to all terms:

Lemma 12

(π · t)σ ≡π · (tσ).

Proof

By induction on t. The only interesting case if when t ≡π′ · X. Then unpacking definitions

(π · (π′ · X))σ ≡(π ◦π′) · σ(X) and π · ((π′ · X)σ) ≡π · (π′ · σ(X)).

The result follows by Lemma 9. ■

(#ab)a#bπ-1(a)#X (#X) a#π · X(#λa)a#λa.ta#t(#λb)a#λb.ta#t′ a#t (#app) a#t′t(#c)a#c
Figure 3. Freshness derivation rules for nominal terms
Definition 13

A freshness (assertion) is a pair a#t of an atom and a term. We call a freshness of the form a#X (so t ≡X) primitive. We write ∆and ∇ for (finite, and possibly empty) sets of primitive freshnesses and call them freshness contexts.

We may drop set brackets in freshness contexts, e.g. writing a#X, b#Y for {a#X, b#Y }. Also, we may write a, b#X for a#X, b#X. We write a ∈ ∆when a#X ∈ ∆for some X, and X ∈ ∆when a#X ∈ ∆for some a.

Definition 14

We define derivability on freshnesses in natural deduction style [19] by the rules in Figure 3. In accordance with our permutative convention, a and b range over distinct atoms.

Remark 15

A sequent style presentation of Figure 3 is also possible; for example (#X) becomes ∆⊢π-1(a)#X ∆⊢a#π · X and we need a new rule [a#X ∈∆] ∆⊢a#X where the ‘X’ in the bottom line is shorthand for id·X and square brackets indicate a side-condition.

Definition 16

We write ∆ ⊢a#t when a derivation of a#t exists using the rules of Figure 3, such that the assumptions are elements of ∆. In words, we say “a#t is derivable from ∆”. We usually write ∅⊢a#t as ⊢a#t.

For example ⊢a#λb.b, ⊢a#λa.a, and a#X ⊢a#X(λa.Y):

(#ab)a#b(#λb)a#λb.b(#λa)a#λa.aa#X(#λa)a#λa.Y(#app)a#X(λa.Y )

The example of ⊢a#λa.a demonstrates that a#t, whose intuitive reading is ‘is not free in’, differs from a ∉t, whose intuitive reading is ‘does not occur in’.

The derivation rules are completely syntax-directed. Therefore:

Lemma 17

1. ∆⊢a#b always.

2. If ∆⊢a#X then a#X ∈∆.

3. If ∆⊢a#π · X then ∆⊢π-1(a)#X.

4. ∆⊢a#λa.t always.

5. If ∆⊢a#λb.t then ∆⊢a#t.

6. If ∆⊢a#t′t then ∆⊢a#t′ and ∆⊢a#t.

7. ∆⊢a#c always.

Proof

By an easy induction on the structure of the derivation rules in Figure 3. ■

We can strengthen the freshness context ∆in freshness derivations:

Theorem 18

If c#Z, ∆⊢a#t and c ∉t then ∆⊢a#t.

Proof

We transform a derivation of c#Z, ∆⊢a#t into a derivation of ∆⊢a#t:

• If c#Z, ∆⊢a#X by assumption then a#X ∈c#Z, ∆. Since a ≠ c, we know a#X ∈ ∆, and we conclude ∆ ⊢a#X by assumption. The case of a#Z is similar.

• (#X): Suppose c#Z, ∆⊢a#π · X is derived using (#X). Then c#Z, ∆⊢π-1(a)#X. By assumption c ∉π · X, so π(c) = c. Since also a ≠ c, we know π-1(a) ≠ c. By the inductive hypothesis and the simple fact that c ∉X we obtain ∆ ⊢π-1(a)#X. We conclude ∆ ⊢a#π · X using (#X). The case of a#π · Z is similar.

• (#ab), (#λa) and (#c) carry over directly.

• (#λb) and (#app) are straightforward using the inductive hypothesis and the following facts: if a ∉λb.t then a ∉t, and if a ∉t′t then a ∉t′ and a ∉t.

■

Freshness context weakening also holds and is part of a more general result; see Theorem 21.

Equivariance is a characteristic property of nominal techniques. Equivariance arises from the use nominal techniques make of permutations as opposed to renamings (possibly non-bijective functions on atoms). Intuitively, equivariance states that if something is true, then it should remain true if we permute atoms. Formally we write:

Lemma 19

If ∆⊢a#t then ∆⊢π(a)#π · t.

Proof

By induction on the structure of derivations of a#t from ∆. The only non-trivial case is (#X). Suppose a#π′ · X is derived from π′-1(a)#X using (#X). We must show that π(a)#(π ◦π′) · X. This follows from (π ◦π′)-1(π(a))#X. It is a fact that (π ◦π′)-1(π(a)) = π′-1(a). The result follows. ■

Lemma 19 is part of a collection of equivariance properties and these are responsible for much of the technical convenience of the nominal treatment of names. See for example [32, Lemma 2.7], [13, Lemma 20], [16, Appendix A], and [17, Lemma 4.7].

We can extend the substitution action to freshness contexts:

Definition 20

We write

∆σ for {a#σ(X) | a#X ∈∆}.

Intuitively read this as ‘apply σ to every X in ∆’.

We write ∆′ ⊢∆σ when ∆′ ⊢a#σ(X) for every a#X ∈∆.

Note that ∆σ need not be a freshness context, because it might contain a#t for t not an unknown.

Theorem 21

For any ∆′, ∆, σ, if ∆⊢a#t and ∆′ ⊢∆σ then ∆′ ⊢a#tσ.

As a corollary, if ∆⊢a#t and ∆⊆∆′ then ∆′ ⊢a#t.

Proof

The structure of natural deduction derivations is such that the conclusion of one derivation may be ‘plugged in’ to an assumption in another derivation, if assumption and conclusion are syntactically identical. The structure of all the rules except for (#X) is such that if unknowns are instantiated by σ nothing need change.

For the case of (#X) we use Lemma 19. The corollary follows taking σ(X) ≡ id · X for all X. ■

2.3 Equality, axioms and theories

Definition 22

We call a pair t = u an equality (assertion). We call the pair ∇⊢t = u of a freshness context ∇ and an equality t = u an axiom. We may write ∅⊢t = u as ⊢t = u.

We call a set of axioms T a theory. The theories needed in this paper are:

• CORE: the empty set of axioms.

• ULAM: the axioms from Figure 1.

Remark 23

Theory ULAM axiomatises a non-extensional λ-calculus. An extensional version is obtained if we add the following axiom to Figure 1:

(η) a#Z ⊢λa.(Za) = Z

We see no difficulties with extending the results of this paper to the extensional case.

Remark 24

A word on the history of the ideas behind ULAM: ULAM grew out of SUB [15], which was based on a nominal rewrite system for the λ-calculus [13, Example 43], which was itself based on an example signature used in nominal unification [32, Example 2.2]. The axioms of ULAM directly and deliberately identify nominal abstraction [a]t (notation in the style of [32, 15]) with λ-abstraction λa.t, and nominal substitution sub(t, u) with λ-calculus application tu. In [32, 13, 15] term-formers such as λ-abstraction and application exist separately and a sort-system ensures for example that the t in sub(t, u) is an abstraction:

• λ is a unary term-former. It takes a nominal abstraction as an argument and returns a term of base sort. In the style of [15, 32] we write that it has arity ([A]T)T.

• Substitution is a binary term-former sub with arity ([A]T, T)T.

The direct identification of nominal abstraction with λ-abstraction, and substitution with application, is possible because terms of ULAM are unsorted (i.e. all terms have base sort, including abstractions) and because nominal algebra allows us to assert the relevant equalities in a logical framework.

Definition 25

Define derivability on equalities in natural deduction style by the rules in Figure 4. We write ∆ ⊢T t = u when a derivation of t = u exists using these rules such that:

• for each instance of (ax∇⊢t=u), ∇⊢t = u is an axiom from T.

• in the derivations of freshnesses (introduced by instances of (ax∇⊢t=u) and (perm)) the freshness assumptions used are from ∆only.

We write ∅⊢T t = u as ⊢T t = u.

We briefly discuss the most interesting rules of Figure 4:

• (perm). This rule provides us with a concise way to express α-equivalence. See Lemma 28 and Theorem 49 for formal expressions of this intuition.

(refl)t = tt = u (symm) u = tt = u u = v (tran) t = vt = u(congλ)λa.t = λa.ut′ = u′t = u (congapp) t′t = u′ua#t b#t (perm) (a b) · t = t∇σ(ax∇⊢t=u)π · tσ = π · uσ[a#X] ∆··· t = u (fr) (a ∉t, u)t = u
Figure 4. Derivation rules for nominal equality

• (ax∇⊢t=u). This rule formally expresses how we obtain instances of axioms: instantiate unknowns by terms (using substitutions) and rename atoms (using permutations) such that the hypotheses are corresponding instances of freshness conditions of the axiom. In this rule σ ranges over substitutions, π ranges over permutations, and ∇σ stands for the hypotheses {a#σ(X) | a#X ∈∇}.

The reader might expect the premise of the axiom rule to be π · ∇σ instead of ∇σ. It turns out that both versions are correct, because of Lemma 19: ∆⊢∇σ if and only if ∆ ⊢π · ∇σ for any ∆.

• (fr). This rule allows us to introduce a fresh atom into the derivation. In (fr) the square brackets denote discharge in the sense of natural deduction, for example as in implication introduction [19]; ∆denotes the other assumptions of the derivation of t = u. In sequent style (fr) would be a#X, ∆⊢t = u ∆⊢t = u (a ∉t, u).

We will always be able to find a fresh atom, no matter how unknowns are instantiated, since all our syntax is finite and can never mention more than finitely many atoms.

To provide some intuition for these rules, we give a number of examples.

Example 26

The (perm) rule allows us to show standard α-equivalence properties such as ⊢CORE λa.a = λb.b and ⊢CORE λa.λb.(ab) = λb.λa.(ba):

(#ab)a#b(#λb)a#λb.b(#λa)b#λb.b(perm)λa.a = λb.b(#λa)a#λa.(ba)(#λb)a#λb.λa.(ba)(#λa)b#λb.λa.(ba)(perm)λa.λb.(ab) = λb.λa.(ba)

Note that we use λa.a ≡ (a b) · λb.b and λa.λb.(ab) ≡ (a b) · λb.λa(ba) in the conclusions of the derivations.

Example 27

We give a full derivation of ⊢ULAM (λb.(λa.b))a = λc.a. We use the shorthand from the Introduction to write for example (λb.(λa.b))a as (λa.b)[b↦ →a].

Π =(#ab)a#b(#λb)a#λc.b(#λa)c#λc.b(perm)λa.b = λc.b(congλ)λb.λa.b = λb.λc.b(refl)a = a(congapp)(λa.b)[b↦ →a] = (λc.b)[b↦ →a]
Π′ =(#ab)c#a(axabs↦→)(λc.b)[b↦ →a] = λc.(b[b↦ →a])(axvar↦→)b[b↦ →a] = a(congλ)λc.(b[b↦ →a]) = λc.a(tran)(λc.b)[b↦ →a] = λc.a
Π Π′(tran)(λa.b)[b↦ →a] = λc.a

The examples above do not showcase the full power of nominal terms, because we are not reasoning on terms containing unknowns. The raison d’étre of nominal terms is their unknowns and how their interaction with permutations and freshness allow us to manage α-conversion. We now consider examples of derivations with α-renaming and freshness in the presence of unknowns:

Lemma 28

b#X ⊢CORE X[a↦ →T] = ((b a) · X)[b↦ →T]

Proof

De-sugaring we must derive (λa.X)T = (λb.(b a) · X)T from b#X:

b#X(#X)a#(b a) · X(#λb)a#λb.(b a) · X(#λa)b#λb.(b a) · X(perm)λa.X = λb.(b a) · X(refl)T = T(congapp)(λa.X)T = (λb.(b a) · X)T

The instance of (perm) relies on the fact that (b a) · λa.X ≡λb.(b a) · X.

■

Lemma 29 (Substitution Lemma).
a#Y ⊢ULAM Z[a↦ →X][b↦ →Y ] = Z[b↦ →Y ][a↦ →X[b↦ →Y ]].

The usual proof of the substitution lemma is by induction on Z but now Z is just a formal symbol and part of the syntax — but instead, the axioms of ULAM capture this behaviour.

Proof

By (tran) it suffices to derive

((λa.Z)X)[b↦ →Y ] = ((λa.Z)[b↦ →Y ])(X[b↦ →Y ])

and

((λa.Z)[b↦ →Y ])(X[b↦ →Y ]) = (λa.(Z[b↦ →Y ]))(X[b↦ →Y ])

from a#Y . The first part follows by axiom (app↦→). The second part can be derived as follows:

a#Y(axabs↦→)(λa.Z)[b↦ →Y ] = λa.(Z[b↦ →Y ])(refl)X[b↦ →Y ] = X[b↦ →Y ](congapp)((λa.Z)[b↦ →Y ])(X[b↦ →Y ]) = (λa.(Z[b↦ →Y ]))(X[b↦ →Y ])

■

The following lemma formally connects the usual use of substitution to handle α-renaming, with the unusual treatment of α-renaming which is primitive to nominal terms, based on permutations.

Lemma 30

b#Z ⊢ULAM Z[a↦ →b] = (b a) · Z.

Proof

We sketch the derivation:

b#Z ···As for Lemma 28 Z[a↦ →b] = ((b a) · Z)[b↦ →b](axid↦→)((b a) · Z)[b↦ →b] = (b a) · Z(tran)Z[a↦ →b] = (b a) · Z

■

Remark 31

Axiom (id↦→) is equivalent to Lemma 30. That is, we can derive Z[a↦ →a] = Z using Lemma 30:

[b#Z]1··· As for Lemma 28 Z[a↦ →a] = ((b a) · Z)[b↦ →a][b#Z]1(#X)a#(b a) · Z(Lemma 30)((b a) · Z)[b↦ →a] = Z(tran)Z[a↦ →a] = Z(fr)1Z[a↦ →a] = Z

In this derivation the superscript number one 1 is an annotation associating the instance of the rule (fr) with the assumption it discharges in the derivation. Note how we use (fr) to generate a ‘fresh atom’.

Lemma 32

If a#X for every unknown in t, and a ∉t, then ⊢a#t.

Proof

By an easy induction on t using the rules in Figure 3. ■

Definition 33

We write ds(π, π′) for the set {a | π(a) ≠ π′(a)}, the difference set of permutations π and π′. We write ∆ ⊢ ds(π, π′)#X for a set of proof-obligations ∆ ⊢a#X, one for each a ∈ ds(π, π′).

Remark 34

Figure 4 contains some redundancy; (refl) may be emulated using (fr) and (tran) as follows:

···a#(a b) · t···b#(a b) · t(perm)t = (a b) · t···a#t···b#t(perm)(a b) · t = t(tran)t = t(fr) for all unknowns in t t = t

Here a, b are chosen fresh (so a ∉t and b ∉t). The vertical dots elide derivations described in Lemma 32.

It is convenient in a logic of equality to be able to derive that t = t without ‘going round the houses’ with (tran) and (fr), so we include both (perm) and (refl).

(perm) and (refl) are both instances of the following rule:

ds(π, π′)#t (dsrefl) π · t = π′ · t

Here ds(π, π′)#t is shorthand for the set of a#t for all a ∈ ds(π, π′), if any. This rule looks complicated, so we do not use it in Figure 4.

We can derive syntactic criteria for determining equality in CORE. These will be useful later:

Theorem 35

∆⊢CORE t = u precisely when one of the following hold:

1. t ≡a and u ≡a.

2. t ≡π · X and u ≡π′ · X and ∆⊢ ds(π, π′)#X.

3. t ≡λa.t′ and u ≡λa.u′ and ∆⊢CORE t′ = u′.

4. t ≡λa.t′ and u ≡λb.u′ and ∆⊢b#t′ and ∆⊢CORE (b a) · t′ = u′.

5. t ≡t′t and u ≡u′u and ∆⊢CORE t′ = u′ and ∆⊢CORE t = u.

6. t ≡ c and u ≡ c.

Proof

See [15, Corollary 2.32] or [23, Corollary 2.5.4]. ■

Corollary 36 (Consistency).

For all ∆ there are t and u such that ∆⊬CORE t = u.

Proof

By Theorem 35, ∆⊢CORE a = b is never derivable. ■

Corollary 37 (Decidability).

It is decidable whether ∆⊢CORE t = u is true or not.

Proof

By an easy induction on t, using the syntactic criteria of Theorem 35. ■

A number of properties on freshnesses also hold for equalities of any theory T. For instance we can strengthen the freshnesses context ∆in equational derivations:

Lemma 38

If c#Z, ∆⊢T t = u and c ∉t and c ∉u, then ∆⊢T t = u.

Proof

We extend the derivation with (fr). ■

Also we may permute atoms and instantiate unknowns in equational derivations:

Lemma 39

If ∆⊢T t = u then ∆⊢T π · t = π · u.

Proof

By induction on the structure of the rules of Figure 4. ■

Theorem 40

For any T, ∆′, ∆, σ, if ∆⊢T t = u and ∆′ ⊢∆σ then ∆′ ⊢T tσ = uσ.

As a corollary, if ∆⊢T t = u and ∆⊆∆′ then ∆′ ⊢T t = u.
Proof

Analogous to the proof of Theorem 21.

In the case that σ mentions a ‘fresh’ atom used in an instance of (fr), we rename that atom to be ‘fresher’. The inductive hypothesis is valid also for the ‘freshened’ derivation because of the mathematical principle of ZFA equivariance ([16, Appendix A] or [17]); induction on a measure of the depth of derivations is also possible, subject to uninteresting lemmas that renaming atoms does not change depth. ■

3 Untyped λ-terms

Definition 41

We call a term ground when it mentions no unknowns. Ground terms are inductively characterised by the grammar in Definition 1.

It is no coincidence that ground terms are characterised by Definition 1; as discussed in Subsection 2.1 the syntax of nominal terms used in this paper is specialised to the intended application.

The rest of this section sketches a formal development of the syntax and operational semantics of λ-terms and αβ-reduction, and links it to the ‘nominal’ exposition. For more detailed treatments of λ-terms and αβ-reduction see elsewhere [2, 6].

Definition 42

Define the free atoms fa(g) inductively by:

fa(a) = {a} fa(λa.g) = fa(g) \ {a} fa(gg′) = fa(g) ∪fa(g′) fa(c) = {}.

This is standard.

Lemma 43

a ∉ fa(g) if and only if ⊢a#g.

Also, if a ∉g (Definition 7) then ⊢a#g.

Proof

By routine inductions on the structure of g. ■

Definition 44

Define the size of a ground term inductively by:

|a| = 1 |λa.g| = |g| + 1 |g′g| = |g′| + |g| + 1 |c| = 1.

We define a capture-avoiding substitution action g[h/a] inductively on the size of g by:

a[h/a] ≡h b[h/a] ≡b (λa.g)[h/a] ≡λa.g(λb.g)[h/a] ≡λb.(g[h/a]) (b ∉fa(h)) (λb.g)[h/a] ≡λc.(g[c/b][h/a]) (b ∈fa(h), c fresh)(g′g)[h/a] ≡(g′[h/a])(g[h/a]) c[h/a] = c.

In the clause for (λb.g)[h/a] we make some fixed and arbitrary choice of fresh c (the ‘c fresh’), for each b, g, h, a.

A basic property is useful in the proofs of the results which follow:

Lemma 45

Capture-avoiding substitution of atoms for atoms preserves size. More formally, |g[a/a]| = |g| and |g[b/a]| = |g|.

Proof

By an easy induction on |g|. ■

Lemma 46

fa(g[h/a]) ⊆ (fa(g)\{a}) ∪ fa(h).

Also, if ⊢a#h then ⊢a#g[h/a].

Proof

The first part is by a routine induction on size. For the second part we prove the contrapositive. By Lemma 43 it suffices to show that a ∈ fa(g[h/a]) implies a ∈ fa(h). This also follows by a routine induction on the size of g. ■

We introduce the usual notion of α-equivalence.

Definition 47

We write =α for the α-equivalence relation, which is obtained by extending syntactic equivalence with the following rule to rename bound variables:

λa.g =α λb.h when g[c/a] =α h[c/b] for some fresh atom c.

The following lemma shows how permutations interact with =α:

Lemma 48

1. If a, b ∉ fa(g) then (a b) · g =α g.

2. If b ∉ fa(g) then g[b/a] =α (b a) · g.

Proof

For the first part, we observe that all a and b in g must occur in the scope of λa and λb. We traverse the structure of g bottom-up and rename these to fresh atoms (for example λa′ and λb′ which do not occur anywhere in g). Call the resulting term g′. Now (a b) · g′ ≡g′ because a, b ∉g′. Equality is symmetric, so we reverse the process to return to g.

The second part follows by an induction on |g|. ■

Theorem 49

Derivable equality in CORE coincides with =α on ground terms.

Proof

See [15, Theorem 3.9] or [23, Theorem 4.3.13]. ■

Remark 50

We do not quotient terms by α-conversion and we do not use a syntax based on a nominal-style datatype of syntax-with-binding [17]. This is because the proof of Theorem 57 involves keeping careful track of what atoms do and do not appear in terms, and if we quotient by α-equivalence now we lose information — names of abstracted atoms — which is useful for expressing that proof.

Definition 51

Let β-reduction g →β h be inductively defined by:

g[a↦ →h] →β g[h/a]g →β g′λa.g →β λa.g′g →β g′h →β h′gh →β g′h′

We call g a β-normal form when there is no g′ such that g →β g′.

We write g →αβ h when there exist g′ and h′ such that

g =α g′, g′ →β h′, and h′ =α h.

We write =αβ for the transitive reflexive symmetric closure of →αβ.

Theorem 52

→αβ is confluent.

Proof

See elsewhere [6]. ■

4 Soundness, completeness, conservativity

4.1 Soundness

Definition 53

We call a substitution ς ground for a set of unknowns X when ς(X) is ground for every X ∈X. We call ς ground for ∆, t, u when ς is ground for the set of unknowns appearing anywhere in ∆, t, or u.

Lemma 54

fa(π · g) = {π(a) | a ∈ fa(g)}.

Proof

By Lemmas 43 and 19. The result also follows directly by a routine induction on the syntax of g. ■

It is now easy to state and prove a notion of soundness for ULAM:

Theorem 55 (Soundness).

Suppose that ς is a ground substitution for ∆, t, and u. Suppose further that a ∉ fa(ς(X)) for every a#X ∈∆. Then:

• ∆⊢a#t implies a ∉ fa(tς).

• ∆⊢ULAM t = u implies tς =αβ uς.

Proof

We proceed by induction on ULAM derivations.

We consider the rules in Figure 3 in turn:

• By assumption. We must show that if a#X ∈ ∆then a ∉ fa(ς(X)), which follows by our assumptions on ς.

• The case (#ab). It is a fact of Definition 42 that a ∉ fa(b).

• The case (#λa). It is a fact that a ∉ fa(λa.(tς)).

• The cases of (#λb), (#app), and (#c) are no harder.

• The case (#X). By Lemma 54, a ∈ fa(π · g) if and only if π-1(a) ∈ fa(g).

We consider the rules in Figure 4 in turn:

• The cases (refl), (symm), (tran), (congλ) and (congapp) follow by induction using the fact that =αβ is an equivalence relation and a congruence.

• The case (perm). Suppose that a, b ∉ fa(g). Then (a b) · g =αβ g follows by Lemma 48, since =α implies =αβ.

• The case (ax). It remains to check the validity of the axioms of ULAM. It suffices to verify that:

– (var↦→). We must show

π(a)[π(a)↦ →(π · σ(X))ς] =αβ (π · σ(X))ς

for any permutation π and substitution σ. This follows from the property that

b[b↦ →h] =αβ h

always (i.e. for any atom b and ground term h), which is a fact about αβ-equivalence.

– (#↦→). Suppose that (π · σ(Z))[π(a) ↦→π · σ(X)] = π · σ(Z) is derived from π(a)#π · σ(Z) using the assumptions from ∆. By inductive hypothesis, we know π(a) ∉ fa((π · σ(Z))ς). We must show ((π · σ(Z))ς)[π(a) ↦→ (π · σ(X))ς] =αβ (π · σ(Z))ς. This follows from the basic fact about αβ-equivalence that

b ∉fa(g) implies g[b↦ →h] =αβ g

always. Other cases are similar:

– (app↦→). (g′g)[b↦ →h] =αβ (g′[b↦ →h])(g[b↦ →h]).

– (abs↦→). If c ∉ fa(h) then (λc.g)[b↦ →h] =αβ λc.(g[b↦ →h]).

– (id↦→). g[b↦ →b] =αβ g.

• The case (fr). If necessary, we rename the fresh atom in (fr) to a ‘fresher’ atom. By ZFA equivariance ([16, Appendix A]), the inductive hypothesis also holds for the ‘freshened’ derivation, and the result easily follows.

■

4.2 Completeness

We start with a weak form of completeness:

Lemma 56

For ground terms g and h, if g =αβ h then ⊢ULAM g = h.

It is not hard to prove this by concrete calculations, but it also follows as a corollary of the following more powerful result:

Theorem 57 (Completeness).

Suppose that tς =αβ uς for every substitution ς such that

• ς is ground for ∆, t, u and

• a ∉ fa(ς(X)) for every a#X ∈∆.

Then ∆⊢ULAM t = u is derivable.

The proof occupies the rest of this section. Fix some freshness context ∆and two terms t and u.

Definition 58

Let A be the atoms mentioned anywhere in ∆, t, or u. Let X be the unknowns mentioned anywhere in ∆, t, or u. For each X ∈X fix the following data:

• An order aX1, . . . , aXkX on the atoms in A such that a#X ∉∆.

• Some entirely fresh atom cX.

We write C for the set {cX | X ∈X}.

Definition 59

Specify ς a ground substitution for X by:

• ς(X) ≡cXaX1. . . aXkX if X ∈X.

• ς(Y ) ≡Y for Y ∉X.

Lemma 60

If a#X ∈∆ then a ∉ fa(ς(X)).

Proof

By construction of ς(X). ■

By assumption tς =αβ uς. The untyped λ-calculus is confluent (Theorem 52) so tς and uς rewrite to a common term, call it p:

Definition 61

Fix two chains

tς ≡g1 =α g2 →β g3 =α g4 →β . . . →β gm−1 =α gm ≡p uς ≡h1 =α h2 →β h3 =α h4 →β . . . →β hn−1 =α hn ≡p

Without loss of generality we assume these α-conversions and β-reductions do not introduce abstractions by atoms from C.

Definition 62

Let A+ be the set of all atoms mentioned anywhere in the chains of Definition 61, extended with a set of fresh atoms

B = {bXi | X, i such that aXi ∈A}.

in bijection with A. (So B is disjoint from C and from all atoms mentioned in ∆, t, u, g1, . . . , gm, h1, . . . , hn.) Let ∆+ be ∆enriched with freshness assumptions a#X for every a ∈A+ \ A and every X ∈X.

Definition 63

We call a ground term g accurate when:

• g mentions only atoms in A+ \ B.

• cX ∈C never occurs abstracted. That is, no term contains ‘λcX’.

• cX ∈C appears, if it appears at all, in head position applied to a list of terms in a subterm of the form ‘cXg1. . . gkX ’.

Note that g1, . . . , gm and h1, . . . , hn are accurate by construction of tς and uς and by the nature of α-conversions and β-reductions.

Definition 64

Define an inverse translation from accurate terms to (possibly non-ground) terms inductively by:

a-1 ≡a (a ∉C) (λa.g)-1 ≡λa.(g-1) (gh)-1 ≡(g-1)(h-1) c-1 ≡c(cX)-1 ≡λbX1. · · · λbXkX.(bX1 aX1) · · · (bXkX aXkX) · X (cX ∈C)

The inverse translation _-1 is an inverse of ς in the following sense:

Lemma 65

∆+ ⊢ULAM (tς)-1 = t, and ∆+ ⊢ULAM (uς)-1 = u.

Proof

We prove by induction that if v is a subterm of t or u then ∆+ ⊢ULAM (vς)-1 = v.

The only interesting case is when v ≡π · X. We must show

∆+ ⊢ULAM (π1 · X)[bXkX↦ →π(aXkX)] · · · [bX1↦ →π(aX1)] = π · X

where π1 = (bX1 aX1) · · · (bXkX aXkX).

Take π2 = (bX1 π(aX1)) · · · (bXkX π(aXkX)). By transitivity it suffices to show:

1. ∆+ ⊢ULAM (π1 · X)[bXkX↦ →π(aXkX)] · · · [bX1↦ →π(aX1)] = (π2 ◦π1) · X.
2. ∆+ ⊢ULAM (π2 ◦π1) · X = π · X.

The first part follows using Lemma 30 when, for 1 ≤i ≤kX,

∆+ ⊢π(aXi)#(π1 · X)[bXkX↦ →π(aXkX)] · · · [bXi + 1↦ →π(aXi + 1)].

By the rules for freshness, this follows from ∆+ ⊢π(aXi)#π1 · X since the π(aX1), . . . , π(aXkX) are all disjoint. We conclude using a case distinction on π(aXi):

• π(aXi) ≠ aXj for all j: then π(aXi)#X ∈∆+ since π(aXi)#X ∈∆.

• π(aXi) = aXj for some j: then bXj#X ∈∆+ by definition.

We still have to show that ∆+ ⊢ULAM (π2 ◦π1) · X = π · X. It is convenient to show the stronger property ∆+ ⊢CORE (π2 ◦π1) · X = π · X. By Theorem 35 we need only show that ∆+ ⊢ ds(π2 ◦π1, π)#X. That is, we must show that ∆+ ⊢a#X for every a such that (π2 ◦π1)(a) ≠ π(a). We consider every possible a (every a ∈π2 ◦π1 and a ∈π):

• a = bXi: then bXi#X ∈∆+ by definition, and the result follows.

• a = aXi: then (π2 ◦π1)(aXi) = π(aXi) and there is nothing to prove.

• a = π(aXi): then we distinguish two cases:

– if π(aXi) = aXj for some j, the result follows by the case of aXi;

– if π(aXi) ≠ aXj for all j, then π(aXi)#X ∈∆+ by definition.

• a ∈π, but a ≠ aXj for all j, then a#X ∈∆+ by definition.

■

Remark 66

The reader might wonder why the inverse mapping of the cX renames aXi to the fresh bXi. Consider for example (aX1 aX2) · X in the empty freshness context ∅, so we do not know aX1#X or aX2#X. Then

((aX1 aX2) · X)ς-1 ≡((bX1 aX1)(bX2 aX2) · X)[bX2↦ →aX1][bX1↦ →aX2].

By calculations we can verify Lemma 65:

∅+ ⊢ULAM ((aX1 aX2) · X)ς-1 = (aX1 aX2) · X

where ∅+ = {bX1#X, bX2#X, cX#X}. Had we left out the renaming to fresh atoms then ((aX1 aX2) · X)ς-1 would be X[aX2↦ →aX1][aX1↦ →aX2], which is not equal to (aX1 aX2) · X, since for example

((aX1 aX2) · X)[aX2/X] = aX1 but X[aX2↦ →aX1][aX1↦ →aX2][aX2/X] = aX2.

A technical lemma about freshness will be useful.

Lemma 67

Suppose that g is accurate. For any a ∈A+, if a ∉ fa(g) then ∆+ ⊢a#g-1.

Proof

By induction on g. The only non-trivial case is when g ≡cX. Suppose a ∉ fa(cX). Then a ≠ cX and we must show

∆+ ⊢a#λbX1. · · · λbXkX.(π · X),

where π = (bX1 aX1) · · · (bXkX aXkX). We distinguish two cases:

• a = bXkj for some j: then bXkj#λbXkj. · · · λbXkX(π · X) by (#λa), and the result follows by the rules of freshness using the inductive hypothesis.

• a ≠ bXkj for all j: then π-1(a) ≠ aXkj for all j, so π-1(a)#X ∈∆+ by definition. The result follows using the rules for freshness and the inductive hypothesis.

■

We need a technical lemma:

Lemma 68

Suppose that g is accurate. Suppose that π is a permutation such that π(a) = a for all a ∉A+ \ (B ∪C). Then ∆+ ⊢CORE (π·g)-1 = π·(g-1).

Proof

By a routine induction on g. In the case of g ≡cX we use the fact that π(a) = a for all a ∈B ∪C. ■

Lemma 69

Suppose that g and h are accurate. Then if g =α h then ∆+ ⊢CORE g-1 = h-1.

Proof

By Theorem 49 g =α h coincides with ⊢CORE g = h. We therefore work by induction on the structure of g using the syntactic criteria of Theorem 35.

The only non-trivial case is when

g ≡λa.g′, h ≡λb.h′, ⊢b#g′, and ⊢CORE (b a) · g′ = h′.

By assumption a, b ∈A+ \ (B ∪C). By Lemma 67 we have ∆+ ⊢b#g′-1. By inductive hypothesis ∆+ ⊢CORE ((b a) · g′)-1 = h′-1. By Lemma 68 we have ∆+ ⊢CORE ((b a) · g′)-1 = (b a) · (g′-1). From the rules for freshness and equality ∆+ ⊢CORE λa.(g′-1) = λb.(h′-1) follows. ■

Lemma 70

Suppose that a ∈A+ \ C. Suppose that g, h, and g[h/a] are accurate. Then ∆+ ⊢ULAM g-1[a↦ →h-1] = (g[h/a])-1.

Proof

We work by induction on the size of g:

• a[h/a]. ∆+ ⊢ULAM a[a↦ →h-1] = h-1 by (var↦→).

• b[h/a]. ∆+ ⊢ULAM b[a↦ →h-1] = b by (#↦→) since ∆+ ⊢a#b. The cases of (λa.g)[h/a] and c[h/a] are similar.

• (λb.g)[h/a] where b ∉ fa(h). We must show

∆+ ⊢ULAM (λb.(g-1))[a↦ →h-1] = λb.((g[h/a])-1).

By the inductive hypothesis and the rules for equality, it suffices to show

∆+ ⊢ULAM (λb.(g-1))[a↦ →h-1] = λb.(g-1[a↦ →h-1]).

By Lemma 67 we know ∆+ ⊢b#h-1. The result follows from (abs↦→).

• (λb.g)[h/a] where b ∈ fa(h). By assumption λb.g is accurate, therefore b ∉B ∪C.

Recall from Definition 44 that (λb.g)[h/a] ≡λc.(g[c/b][h/a]) for some choice of fresh c (so c ∉ fa(g) and c ∉ fa(h)). Now by assumption λc.(g[c/b][h/a]) is accurate, so c ∉B ∪C and g[c/b][h/a] is accurate.

We must show

∆+ ⊢ULAM (λb.(g-1))[a↦ →h-1] = λc.((g[c/b][h/a])-1).

Note that by Lemma 67, ∆+ ⊢c#g-1 and ∆+ ⊢c#h-1, and therefore ∆+ ⊢c#λb.(g-1) by (#λb). Also ∆+ ⊢b#λb.(g-1) is immediate by (#λa). We present the rest of the proof in a calculational style:

λc.((g[c/b][h/a])-1)= { g[c/b] =α (c b) · g by Lemma 48 since c ∉fa(g) } λc.(((c b) · g)[h/a])-1= { inductive hypothesis, since (c b) · g is accurate } λc.(((c b) · g)-1[a↦ →h-1])= { Lemma 68 } λc.(((c b) · (g-1))[a↦ →h-1])= { (abs↦→), since ∆+ ⊢c#h-1 } (λc.((c b) · (g-1)))[a↦ →h-1]= { (perm) since ∆+ ⊢b#λb.(g-1) and ∆+ ⊢c#λb.(g-1) } (λb.(g-1))[a↦ →h-1]

The result follows by transitivity.

• (gg′)[h/a]. By the inductive hypothesis and the rules for equality, ∆+ ⊢ULAM ((g-1)(g′-1))[a↦ →h-1] = ((gg′)[h/a])-1 follows from

∆+ ⊢ULAM ((g-1)(g′-1))[a↦ →h-1] = (g-1[a↦ →h-1])(g′-1[a↦ →h-1]).

We conclude using axiom (app↦→).

• cX[h/a] where cX ∈C. By assumption a ≠ cX, so we must show

∆+ ⊢ULAM (λbX1. · · · λbXkX.(π · X))[a↦ →h-1] = λbX1. · · · λbXkX.(π · X), where π = (bX1 aX1) · · · (bXkX aXkX).

By assumption bXi ∉h for all 1 ≤i ≤kX, therefore also bXi ∉ fa(h). By Lemma 67 also ∆+ ⊢bXi#h-1. Then we can show by a number of applications of axiom (abs↦→) that (λbX1. · · · λbXkX.(π · X))[a↦ →h-1] is equal to λbX1. · · · λbXkX.(π · X)[a↦ →h-1]. By the rules for equality, it suffices to show

∆+ ⊢ULAM (π · X)[a↦ →h-1] = π · X.

By axiom (#↦→) this follows if π-1(a)#X ∈∆+. There are two possibilities:

– a = aXj for some j: then π-1(a) = bXj, and bXj#X ∈∆+ by definition.

– a ≠ aXj for all j: then π-1(a) = a, and a#X ∈∆+ by definition.

The result follows. ■

Corollary 71

Suppose that g and h are accurate. If g →β h then ∆+ ⊢ULAM g-1 = h-1.

Proof

By induction on the derivation rules for →β from Definition 51. It suffices to show the following (here g, g′, h, h′, and g[h/a] are accurate and a ∈A+ \ C):

1. ∆+ ⊢ULAM g-1[a↦ →h-1] = (g[h/a])-1.

2. If ∆+ ⊢ULAM g-1 = g′-1 then ∆+ ⊢ULAM λa.(g-1) = λa.(g′-1).

3. If ∆+ ⊢ULAM g-1 = g′-1 and ∆+ ⊢ULAM h-1 = h′-1

then ∆+ ⊢ULAM (g-1)(h-1) = (g′-1)(h′-1).

The first part is Lemma 70. The second and third parts follow by (congλ) and (congapp). ■

We are now ready to prove Theorem 57:

Proof

Recall from Definition 61 the chains

tς ≡g1 =α g2 →β g3 =α g4 →β . . . →β gm−1 =α gm ≡p uς ≡h1 =α h2 →β h3 =α h4 →β . . . →β hn−1 =α hn ≡p.

By Lemma 69 and Corollary 71

∆+ ⊢ULAM(tς)-1 ≡g-1 1 = g-1 2 = . . . = g-1 m ≡p-1∆+ ⊢ULAM(uς)-1 ≡h-1 1 = h-1 2 = . . . = h-1 n ≡p-1.

By transitivity

∆+ ⊢ULAM (tς)-1 = p-1and ∆+ ⊢ULAM (uς)-1 = p-1

so by symmetry and transitivity ∆+ ⊢ULAM (tς)-1 = (uς)-1. By Lemma 65 then also ∆+ ⊢ULAM t = u. Since ∆+ extends ∆with atoms that are not mentioned in t and u by Lemma 38 we conclude ∆ ⊢ULAM t = u as required.

■

4.3 Conservativity over CORE

We can exploit the ς from Subsection 4.2 to prove conservativity of ULAM over CORE.

Lemma 72

Fix ∆. Suppose that t and u contain no subterm of the form v[a↦ →w]. Then for ς the ground substitution constructed in Subsection 4.2, tς and uς are β-normal forms.

Proof

ς(X) ≡cXaX1. . . aXkX for every X appearing in ∆, t, or u. Applying this substitution to t and u cannot introduce subterms of the form v[a↦ →w].

■

Theorem 73 (Conservativity).

Suppose that t and u contain no subterm of the form v[a↦ →w]. Then

∆⊢ULAM t = u if and only if ∆⊢CORE t = u.
Proof

A derivation in CORE is also a derivation in ULAM so the right-to-left implication is immediate.

Now suppose that ∆ ⊢ULAM t = u. We construct ς as in Subsection 4.2. By Theorem 55, tς =αβ uς. By Lemma 72 we know that tς and uς are β-normal forms. By confluence of the λ-calculus (Theorem 52), tς =α uς.

We now prove ∆ ⊢CORE t = u by induction on t. The calculations are detailed but entirely routine. We consider just one case, the hardest one:

Suppose t ≡π · X. Then tς ≡cXπ(aX1) . . . π(aXkX). By Theorem 35, if tς =α uς it must be that uς ≡cXπ(aX1) . . . π(aXkX).

By the construction of uς and the way we chose aX1, . . . , aXkX to be the atoms mentioned in ∆, t, or u which are not provably fresh for X in ∆, it follows that u must have been equal to π′ · X, for some π′, such that ∆⊢ ds(π, π′)#X. It follows that ∆ ⊢CORE t = u as required. ■

5 Conclusions

5.1 Related work not using nominal techniques

αβ-equivalence on λ-calculus syntax is a good idea; we find it realised in different ways in different systems. If the λ-calculus syntax in question serves as the language of a logic, then αβ-equivalence may have the status of axioms. For example Andrews’s logic Q0 [1, §51] contains five axioms (41), (42), (43), (44), and (45) ([1, page 164]). In fact they are axiom schemes, containing meta-variables A and B in the informal meta-level ranging over terms (and also meta-variables x, y ranging permutatively over variable-symbols). The relationship which Figure 1 bears to them is clear but here, axioms feature in the formal framework of Nominal Algebra — a formal logic, not an informal meta-level. We claim that Nominal Algebra captures part of the ‘informal meta-level’ in which researchers routinely work — and that within that, ULAM captures the (untyped) λ-calculus.

Salibra’s Lambda Abstraction Algebras [28] axiomatise the λ-calculus using universal algebra. The method is cylindric in the sense of cylindric algebras [18]; abstraction is represented by infinitely many term-formers (there is a term-former ‘λa’ for every a) and freshness is encoded in the structure of the terms in the following sense: consider Salibra’s rule (β4) from [28, page 6]:

(β4) (λx.(λx.ξ))µ = λx.ξ.

We can rewrite this in our notation as (λa.Z)[a↦ →X] = λa.Z and this is a version of (#↦→), where the freshness condition a#Z has been built into the structure of the term by replacing Z with λa.Z. Similarly Salibra’s rule (α)

(α) λx.(λy.ξ)z = λy.(λx.(λy.ξ)z)y

can be rewritten in our notation as λa.(Z[b↦ →c]) = λb.(Z[b↦ →c][a↦ →b]) and this plays an analogous rôle to our Lemma 28. The notion of dimension set [28, Definition 4] corresponds to freshness. The proof of a main result, Theorem 13 of [28] (first carried out by Salibra, improved by Selinger), uses definitions reminiscent of, though not identical to, Definitions 58 and 59. The ‘nominal’ techniques give a clear separation of the parts having to do with names and abstraction, and the parts having to do with λ and application, which is not possible with Lambda Abstraction Algebras. However, Salibra’s results [28, 22] show what can be achieved using algebraic methods.

Curry discovered combinatory algebra [10]. The signature contains a binary term-former application and two constants S and K. Axioms are Kxy = x and Sxyz = (xz)(yz). This syntax is parsimonious and the axioms are compact, but it is not natural or ergonomic to program in; that most ergonomic feature of the λ-calculus which makes it so very useful in practice, the λ, is missing. There is also a mathematical issue: the natural encoding of closed λ-terms into combinatory algebra syntax ([6, Section 7] or [29, Subsection 1.4]) does not map αβ-equivalent λ-terms (λz.(λx.x)z and λz.z) to provably equal terms in combinatory algebra. This is resolved if we strengthen combinatory algebra to lambda algebra by adding five axioms, due to Curry [29, Proposition 5]. However the translation is still not sound, in the sense that there exist λ-terms M and N such that the translation of M is derivably equal to the translation of N, but the translation of λx.M is not derivably equal to the translation of λx.N. To ensure soundness, we must add the Meyer-Scott axiom [29, Proposition 20] (Selinger calls it ‘the notorious rule’).

In short, combinators do not capture the model of functions expressed by the λ-calculus. Selinger [29] identifies the problem with the interpretation of variables and argues for denotations with fresh ‘indeterminates’; this reminds us of nominal techniques with its set of atoms in the denotation and well-developed theories of freshness.

λ-calculi of explicit substitution decompose the substitution used in β-reduction into many explicit reduction steps [21]. This is similar to the way ULAM breaks down the calculation of an equality into many explicit algebraic equalities. A calculus of explicit substitutions is a calculus, not a logic; all reasoning using calculi occurs informally in natural language. ULAM on the other hand is intended to support algebraic reasoning on the λ-calculus within a formal framework, while remaining very close to informal practice.

5.2 Related work using nominal techniques

The first application of nominal techniques was to datatypes of syntax with binding [17]. The syntax of the untyped λ-calculus is often used as a paradigmatic example of such a datatype. This paper is not another such study. ‘The λ-calculus’ studied in some other publications — using nominal sets [17], nominal logic [27], and also using higher-order abstract syntax [26], de Bruijn terms [11], and so on — is a collection of (syntax) trees. This paper studies functions.

This paper is part of a broader research programme developing nominal techniques in general and nominal algebra in particular. A rewrite system for the λ-calculus appeared already in [13] but without any statement or proof of completeness (indeed, the system considered there was not complete). The authors have axiomatised first-order logic as a theory FOL [16] and also substitution as a theory SUB [15]. Since β-reduction is based on substitution, this paper shares technical results with the study of SUB [15]. The completeness result we give for ULAM is for a model based on untyped λ-terms quotiented by αβ-equality. The completeness result for SUB is for a model based on trees with an explicit substitution. Derivable equality in ULAM includes the full power of the λ-calculus and is undecidable; equality in SUB is equality of syntax with a substitution action and is decidable. For example

⊢ULAM (ba)[b↦ →λa.a] = a

is derivable in ULAM, but (in notation from [15]) only

⊢SUB app(b, a)[b↦ →lam([a]a)] = app(lam([a]a), a)

is derivable in SUB. The proofs in this paper have been improved and simplified. Technical issues have been avoided and we do not rely on a strong normalisation property which the proofs of [15] required (probably unnecessarily). Note that the treatment of SUB is parametric over a range of signatures and would be the appropriate theory where substitution is precisely what we require — for example as part of an axiomatisation of quantifiers in first-order logic.

A version of ULAM for a typed λ-calculus should be possible. It would sit ‘in between’ ULAM and SUB, as one might expect, but to make this formal a typing system for nominal terms is required (such that atoms are assigned types by a typing context). This has been investigated to some extent [12]. Investigations in nominal algebra are for future work.

Nominal algebra has a cousin, nominal equational logic (NEL) [9], which was derived from nominal algebra but making different design decisions. NEL satisfies a completeness result for a generic class of models in nominal sets [9], as does nominal algebra [14, 23]. The completeness result of this paper is much stronger than the generic results, because it is completeness for a single elementary model; similarly for the authors’ treatments of substitution [15] and first-order logic [16]. We know of no like treatments of substitution, logic, and the λ-calculus in NEL. If and when this is done it will be interesting to compare the results.

5.3 Future work

The nominal algebraic framework proved itself capable of translating, with remarkable accuracy and uniformity, informal mathematical specification into formal nominal algebra axioms, almost symbol for symbol. This paper is both a study of the algebraisation of functions using nominal algebra, and a case study in nominal techniques applied to the λ-calculus. We hope that future study of nominal techniques may benefit from the ‘off-the-shelf’ axiomatisation provided in this paper. We have proved a soundness result (Theorem 55) and a strong completeness result (Theorem 57). We hope that as the theory of nominal algebra itself is improved, this will be of direct benefit to λ-calculus theory.

It would be interesting to consider direct ‘nominal’ versions of models of the λ-calculus, such as graph models or domain models of the λ-calculus [6, 30]. It would also be interesting to consider work using the language of categories (for example [29, 4]) using categories based on nominal sets.

It remains to develop the theory of nominal algebra itself, such as to prove the HSP theorem [8]; we would then be able to apply it to ULAM to study the λ-calculus, and likewise for other nominal algebraic theories.

It is also possible to investigate how well nominal algebra, or a system like it, can serve as the basis of a theorem-prover. Theorem-provers based on the λ-calculus [3] are the state of the art, and the Isabelle theorem-prover demonstrates how a weak meta-logic (such as Isabelle/Pure) can encode powerful object-logics (such as Isabelle/HOL) [24]. Is it possible that an elaboration of Nominal Algebra could serve as the foundation of a generic theorem-prover in the spirit of Isabelle, offering a new set of reasoning-principles ‘ϵ away from informal practice’? The construction of ULAM in nominal algebra is a useful preliminary step.

5.4 Conclusions

The λ-calculus is a fundamental model of functions in logic and computation. We have given axioms ULAM for the untyped λ-calculus in nominal algebra, a recently-developed logical framework based on nominal techniques. This gives a logical theory pleasingly close to informal practice, while remaining mathematically completely rigorous. ULAM completes a trio of papers on nominal algebra and first-order logic [16], substitution [15], and with this paper, the λ-calculus. Researchers using nominal techniques might find ULAM and its completeness result a useful off-the-shelf component in later and larger works.

ULAM formally connects ‘nominal atoms’ and ‘λ-calculus variables’. Discussions about this connection — usually based on not-entirely-explicit criteria of practical usefulness — have continued since nominal techniques were introduced [17] and they may continue into the forseeable future. ULAM makes a nice mathematical contribution to this discussion; the axioms of ULAM are an algebraic measure of the distance we must travel from nominal-style atoms and atoms-abstraction, to λ-calculus style variables and λ-binding. This is gives new sense of how nominal techniques fit into a long tradition of functions in logic and computation.

BIBLIOGRAPHY

[1] Peter B. Andrews. An introduction to mathematical logic and type theory: to truth through proof. Academic Press, 1986.

[2] Peter B. Andrews. Classical type theory. In Handbook of Automated Reasoning, volume 2, chapter 15, pages 965–1007. Elsevier Science, 2001.

[3] Peter B. Andrews, Matthew Bishop, Sunil Issar, Dan Nesmith, Frank Pfenning, and Hongwei Xi. TPS: A Theorem Proving System for Classical Type Theory. Journal of Automated Reasoning, 16(3):321–353, 1996.

[4] Giulio Manzonetto Antonio Bucciarelli, Thomas Ehrhard. Not Enough Points Is Enough. In Computer Science Logic, pages 298–312, 2007.

[5] Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.

[6] H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, 1984.

[7] J. Barwise. An Introduction to First-Order Logic. In J. Barwise, editor, Handbook of Mathematical Logic, pages 5–46. North Holland, 1977.

[8] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Graduate texts in mathematics. Springer, 1981.

[9] Ranald A. Clouston and Andrew M. Pitts. Nominal Equational Logic. Electronic Notes in Theoretical Computer Science, 172:223–257, 2007.

[10] Haskell B. Curry and R. Feys. Combinatory Logic, volume 1. North Holland, 1958.

[11] N. G. de Bruijn. Lambda Calculus Notation With Nameless Dummies, A Tool For Automatic Formula Manipulation, With Application To The Church-Rosser Theorem. Indagationes Mathematicae, 5(34):381–392, 1972.

[12] Maribel Fernández and Murdoch J. Gabbay. Curry-style types for nominal terms. In Types for Proofs and Programs (proceedings of TYPES’06), volume 4502 of Lecture Notes in Computer Science, pages 125–139. Springer, 2007.

[13] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, 2007.

[14] Murdoch J. Gabbay and Aad Mathijssen. A formal calculus for informal equality with binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162–176, 2007.

[15] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, August 2008.

[16] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic. Journal of Logic and Computation, 18(4):521–562, August 2008.

[17] Murdoch J. Gabbay and A. M. Pitts. A New Approach to Abstract Syntax with Variable Binding (journal version). Formal Aspects of Computing, 13(3–5):341–363, 2001.

[18] L. Henkin, J. D. Monk, and A. Tarski. Cylindric Algebras. North Holland, 1971 and 1985. Parts I and II.

[19] Wilfrid Hodges. Elementary predicate logic. In D.M. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer, 2001.

[20] Daniel Leivant. Higher order logic. In D. Gabbay, C.J. Hogger, and J.A. Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming, volume 2, pages 229–322. Oxford University Press, 1994.

[21] Pierre Lescanne. From Lambda-sigma to Lambda-upsilon: a Journey Through Calculi of Explicit Substitutions. In POPL, pages 60–69. ACM, 1994.

[22] G. Manzonetto and A. Salibra. Boolean Algebras for Lambda Calculus. In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), pages 317–326. IEEE Computer Society, 2006.

[23] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.

[24] Lawrence C. Paulson. The Foundation of a Generic Theorem Prover. Journal of Automated Reasoning, 5(3):363–397, 1989.

[25] Lawrence C. Paulson. ML for the working programmer (2nd ed.). Cambridge University Press, 1996.

[26] F. Pfenning and C. Elliot. Higher-Order Abstract Syntax. In PLDI (Programming Language design and Implementation), pages 199–208. ACM Press, 1988.

[27] A. M. Pitts. Nominal Logic, A First Order Theory of Names and Binding. Information and Computation, 186(2):165–193, 2003.

[28] Antonino Salibra. On the algebraic models of lambda calculus. Theoretical Computer Science, 249(1):197–240, 2000.

[29] Peter Selinger. The lambda calculus is algebraic. Journal of Functional Programming, 12(6):549–566, 2002.

[30] Joseph E. Stoy. Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. MIT Press, Cambridge, MA, USA, 1977.

[31] Simon Thompson. Haskell: The Craft of Functional Programming. Addison Wesley, 1996.

[32] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, 2004.

Notes

1Homepage: http://www.gabbay.org.uk ↩

2Email: a.h.j.mathijssen@tue.nl ↩

3We are grateful to a dilligent anonymous referee of a previous paper for making a suggestion which put us on the path to write this paper, and to Pablo Nogueira and Chad Brown for useful advice on improving the exposition. Supported by grant RYC- 2006-002131 at the Polytechnic University of Madrid. ↩

1In [17], names had no functional content at all; they were used just to build datatypes of abstract syntax trees with binding. Higher-order abstract syntax [26] is a way to do the same thing using the ‘names as arguments to functions’ philosophy. ↩