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

Under consideration for publication in Formal Aspects of Computing

Capture-Avoiding Substitution as a Nominal Algebra

Murdoch J. Gabbay and Aad Mathijssen 1

Abstract. Substitution is fundamental to the theory of logic and computation. Is substitution something that we define on syntax on a case-by-case basis, or can we turn the idea of substitution into a mathematical object?

We give axioms for substitution and prove them sound and complete with respect to a canonical model. As corollaries we obtain a useful conservativity result, and prove that equality-up-to-substitution is a decidable relation on terms. These results involve subtle use of techniques both from rewriting and algebra.

A special feature of our method is the use of nominal techniques. These give us access to a stronger assertion language, which includes so-called ‘freshness’ or ‘capture-avoidance’ conditions. This means that the sense in which we axiomatise substitution (and prove soundness and completeness) is particularly strong, while remaining quite general.

Keywords: Substitution, nominal techniques, nominal algebra, binding, capture-avoidance, nominal rewriting, omega-completeness.

1. Introduction

Substitution is intuitively the operation v[a↦ →t] meaning:

Replace the variable a by t in v.

Is there an algebra which describes exactly the properties of v[a↦ →t] independently of what v and t are (λ-terms, formulae of a logic, terms of some process calculus, or any mixture or variation thereof)?

Consider by way of analogy the notion of ‘a field’. This has an algebraic characterisation which tells us what properties ‘a field’ must have, independently of which field it is, or how it may be implemented (if we are programming). This is useful; for example the definition of ‘vector space’ is parametric over fields, and this step requires a characterisation of what fields are [BS81].

When we begin to axiomatise substitution, unusual difficulties present themselves. Consider the following informally expressed candidate property of substitution:

v[a↦ →t][b↦ →u] = v[b↦ →u][a↦ →t[b↦ →u]] provided a ∉fv(u)
(var↦→) ⊢ a[a↦ →T] = T(#↦→) a#X ⊢ X[a↦ →T] = X(f↦→) ⊢f(X1, . . . , Xn)[a↦ →T] = f(X1[a↦ →T], . . . , Xn[a↦ →T])(abs↦→) b#T ⊢ ([b]U)[a↦ →T] = [b](U[a↦ →T])(ren↦→) b#X ⊢ X[a↦ →b] = (b a) · X(η↦→) a#X ⊢ [a]sub(X, a) = X
Figure 1. Axioms of SUB

This is not algebraic, because of the side-condition a ∉ fv(u). Here fv(u) is ‘the free variables of u’, which is a property of the syntax of u.

So is it the case that substitution cannot be axiomatised, and only exists as an incidental property of syntax used to talk about ‘real’ mathematical objects? But in that case, what is the status of the intuition which makes us agree that the property above should be satisfied by any self-respecting substitution action?

We shall argue that the properties of Figure 1 axiomatise substitution, all of substitution, and nothing but substitution. We express them in Nominal Algebra as a theory called SUB (given formal meaning in the rest of this paper). Informally, the axioms express the following:

(var↦→): A variable a with a replaced by T, is T.

(#↦→): If a is fresh for X then X with a replaced by T is X.

(f↦→): Substitution distributes through term-formers; f ranges over them.

(abs↦→): Substitution of a distributes under an abstraction [b]U, provided a capture-avoidance condition is satisfied (b is fresh for T).

(ren↦→): If b is fresh for X then X with a replaced by b is identical to X with a replaced by b and simultaneously b replaced by a.

(η↦→): t[a↦ →u] is sugar for sub([a]t, u). In (η↦→), X is a term not of the form [a]t so we cannot use that sugar. The reader can think of (η↦→) as related to η-equality from the world of the λ-calculus, though X is not a function. The reader can also think of (η↦→) as related to a known property of the atoms-concretion operation of Gabbay-Pitts abstraction [GP02], though sub is not atoms-concretion. More on this in Subsection 1.2.

Formally, Figure 1 uses nominal terms [UPG04] as a syntax, and nominal algebra [GM07, GM06b] as an algebraic framework. We describe these below.

A number of questions now arise:

1. Is this substitution and if so, in what sense; for what model are the axioms sound?

2. Are the axioms complete for that model?

3. Do other (perhaps unexpected) models exist of the same axioms?

4. Can theories be built on top of this one by adding axioms for predicate logic, functional programming, unification and logic programming, simultaneous equations, and so on?

1.1. Answers to questions and map of the paper

Section 2 defines nominal terms and nominal algebra, which fix the syntax and judgement forms we use for our axiomatisation. Section 3 creates a concrete model out of syntax and defines a completely standard capture-avoiding substitution action on the model — this is what we want to capture in axioms. Section 4 defines a relatively weak subset of SUB which we call SIMP (for ‘simple’) which is sound for a concrete model, but not complete. This answers question 1 above. Section 5 proves useful properties of this simple axiomatisation; here we make heavy use of techniques from (nominal) rewriting.

Section 6 explores the stronger axioms of Figure 1 formally as a nominal algebra theory. Decidability of these axioms is proved in Subsection 6.2, and completeness with respect to the concrete model from section 3 is proved in Subsection 6.3. This answers question 2 above and completes the proof that Figure 1 does represent substitution.

In other as-yet unpublished work the first author shows how Fraenkel-Mostowski set theory (the underlying model of nominal techniques) [GP02] supports a substitution action. In the case of a set representing a term in the concrete model of this paper, the substitution action coincides with capture-avoiding substitution. However it extends smoothly, in our opinion quite remarkably, to the entire set theoretic universe. This is an answer for question 3 above and, in our opinion, provides independent evidence that substitution has independent mathematical stature.

In other work [GM07, GM06c] we have investigated how the axiomatisation of substitution can be used to develop algebraic theories, for example of first-order logic. This is the start of an answer to question 4.

The Conclusions discuss related and future work.

1.2. Relation with the conference version

A conference version of this paper has appeared [GM06a]. In this paper the technical machinery has been revised and considerably simplified by making more use of models.

As part of these changes we identify an intermediate axiomatisation SIMP. This captures SUB on closed terms but is weaker than SUB on open terms, in a sense made precise in Theorem 5.24. SIMP can be identified with the usual definition of capture-avoiding substitution.

We give a procedure for converting equalities in SUB into equivalent (in a suitable sense) equalities in SIMP over an extended signature (see Subsection 6.2). This is part of the proof of decidability of SUB, and it yields a clearer and more efficient algorithm than the one in the conference version.

This paper includes a new axiom (η↦→), correcting a technical error of the conference paper: (η↦→) is necessary for ω-completeness (Subsection 6.3). In fact (η↦→) is only necessary if we admit unknowns X of abstraction sort [A]T (using terminology from the rest of this paper, or from [GM06a]). Although it is not strictly necessary to admit unknowns of abstraction sort, it allows us to talk about substitution at a more general level, resulting in a more smooth presentation (see Subsection 6.4).

2. Nominal algebra

2.1. The syntax of nominal terms

First, we define a syntax of nominal terms. The syntax we use here is tailored to our application of axiomatising substitution; see elsewhere for general treatments [UPG04, FG07].

Definition 2.1

Fix a base sort T and call it the sort of terms. Define sorts τ by the following grammar:

τ ::= T | [A]T | [A][A]T.

This simple sort system is sufficient to make sure that terms are well-formed; the reader should not necessarily view it as a ‘typing system’.

Extensions with pair sorts τ ×τ, or base sorts other than T (e.g. to model terms and formulae in first-order logic [GM06c]) cause no essential difficulties, aside from inflating the mathematics with extra cases.

Definition 2.2

Fix some countably infinite set of atoms a, b, c, . . . ∈A. These model object-level variable symbols (the ones we substitute for).

Fix a countably infinite collection of unknowns X, Y, Z, T, U, . . .. These represent unknown terms of sort T or [A]T. We assume unknowns are inherently sorted and infinitely many populate each sort. X is shorthand for Xτ, τ ∈{T, [A]T}. If we write XT and X[A]T then we have two different unknowns with confusingly similar names. Typically we take T and U to have sort T.

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 other words, for ‘most’ atoms π is the identity.

A term-former f is a formal symbol to which is associated an arity (τ1, . . . , τn)τ. We may write f : (τ1, . . . , τn)τ for f which has arity (τ1, . . . , τn)τ. We call a collection of term-formers a signature.

Atoms, unknowns, signatures and other distinct syntactic classes, are assumed disjoint.

Convention 2.3. We shall use a permutative convention that a, b, c, . . . range permutatively over atoms, so that for example a and b are always distinct.

In the rare circumstances where we do not want this behaviour, we use primes and subscripts, such as a′, aX and aXi (where X is an unknown and i is an index).

Definition 2.4

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

t ::= a | π · X | [a]t | f(t1, . . . , tn).

Here a ranges over atoms, X over unknowns, π over permutations, and f over term-formers.

We call π · X a moderated unknown, representing an unknown term on which a permutation of atoms is performed when it is instantiated. An abstraction [a]t represents a term t in which an atom a is abstracted.

Call a term closed when it does not mention any unknowns.

Write syntactic identity of terms t and u as t ≡u to distinguish it from provable equality. Note that if π = π′ then π · X ≡π′ · X, since permutations are represented by themselves. Important: we do not quotient terms in any way.

Definition 2.5

Let (valid) sorting assertions t : τ, read ‘t has sort τ’ be inductively defined by:

a : T π · Xτ : τt : τ [a]t : [A]τt1 : τ1· · · tn : τn(f : (τ1, . . . , τn)τ)f(t1, . . . , tn) : τ.

Note that atom a represents a variable symbol of sort T. Also note that in the rules for π · Xτ and [a]t, τ is restricted to T and [A]T.

We consider only terms that adhere to the sorting assertions from now on.

Example 2.6 (Lambda calculus).

A signature for the lambda calculus consists of the following term-formers:

app : (T, T)T lam : ([A]T)T.

The sorting system is such that a well-sorted term of the form lam(t) must be of the form lam(π · X) (so t ≡π · X) or lam([a]t′) (so t ≡ [a]t′). If lam(t) is closed then it must be of the form lam([a]t′).

It may help to show how nominal terms in this signature relate to ‘ordinary’ syntax. For convenience identify atoms with variable symbols, then the syntax of the untyped λ-calculus is inductively defined by:

e ::= a | ee | λa.e.

We define a map (-)′ to nominal terms by:

(a)′ = a (e1e2)′ = app((e1)′, (e2)′) (λa.e)′ = lam([a](e)′).

We shall see that lam([a]X) behaves much like the λ-context λa.- where - is a ‘hole’.

Substitution is just a term-former, and this is reflected by the notion of a substitution signature.

Definition 2.7

We call a signature T a substitution signature when:

• T contains two term-formers sub, one with arity ([A]T, T)T, and one with arity ([A][A]T, T)[A]T;

• for any other term-former f in T , sorting arities are of the form (τ1, . . . , τn)T, where τi ∈{T, [A]T}, for 1 ≤i ≤n.

A term sub(t, u) represents an explicit substitution. We write u[a↦ →t] as shorthand for sub([a]u, t). We already used this shorthand in Figure 1.

Note that a well-sorted term of the form sub(t, u) must be of the form sub(π · X, u), or sub(sub(t′, u′), u), or t′[a↦ →u] (without sugar: sub([a]t′, u)). If sub(t, u) is closed then it has the form t′[a↦ →u′][a↦ →u], or t′[a′↦ →u′][a↦ →u], or t′[a↦ →u].

We will only consider substitution signatures in the rest of this paper.

Term-formers f other than sub are intuitively ‘the language over which substitution for atoms occurs’. Note that sorting assertions allow arguments of abstraction sort [A]T; this is useful for modelling languages with abstractors, such as λ, ∀, fix, ϵ, and so on. Examples follow:

Example 2.8 (Lambda calculus with explicit substitution).

A substitution signature for the lambda calculus is:

app : (T, T)T lam : ([A]T)T sub : ([A]T, T)T sub : ([A][A]T, T)[A]T.

So intuitively, the two term-formers sub take care of substitution, and app and lam take care of there being a term-language to substitute over (in the presence of some axioms, which are our object of study in this paper).

Example 2.9 (Natural numbers with fixpoints and explicit substitutions).

We can express natural numbers with fixpoints using the following substitution signature:

zero : ()T succ : (T)T plus : (T, T)T fix : ([A]T)T sub : ([A]T, T)T sub : ([A][A]T, T)[A]T.
Remark 2.10

Unknowns of sort [A]T, and the second sub above of arity ([A][A]T, T)[A]T, are convenient but not necessary; see SUB′ in Subsection 6.4.

Remark 2.11

The signature is arbitrary and may be empty (aside from sub), except that Theorem 6.29 (a strong completeness result with respect to a single term model) requires a term-former taking at least two arguments (for example app or plus) to avoid a degenerate case. All other results, including Theorem 6.20 (a notion of completeness with respect to term models in extended signatures which are never degenerate) are valid even in a signature with just sub.

2.2. Permutation, substitution and freshness

Before we can introduce an equational logic on nominal terms, we need to be able to

• permute atoms in terms,

• substitute unknowns with terms, and

• decide whether an atom is fresh for a term.

In this subsection we elaborate on these elements.

Definition 2.12

In Definition 2.2 we defined permutations as finitely supported bijection on atoms. As usual 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, i.e. 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. Also, we usually abbreviate a moderated unknown id · X to X.

Write a ∈π when π(a) ≠ a. Write a ∈t (or X ∈t) for ‘a (or X) occurs in (the syntax of) t’. Occurrence is literal, e.g. a ∈ [a]a and a ∈π · X when a ∈π, i.e. π(a) ≠ a. Similarly write a ∉π, a ∉t and X ∉t for ‘does not occur in the syntax’.

Definition 2.13

A permutation action π · t is defined inductively on t by:

π · a ≡π(a) π · (π′ · X) ≡(π ◦π′) · X π · [a]t ≡[π(a)](π · t) π · f(t1, . . . , tn) ≡f(π · t1, . . . , π · tn).

Intuitively, π propagates through the structure of t until it reaches an atom or a moderated unknown.

Lemma 2.14

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

Proof

By an easy induction on the structure of t.End of proof

Definition 2.15

Call a substitution σ a finitely supported function from unknowns to terms of the same sort. Here, finite support means that σ(X) ≡ id · X for all but finitely many unknowns X.

Write [t1/X1, . . . , tn/Xn] for the substitution σ, defined by σ(Xi) ≡ti and σ(Y ) ≡ id · Y , for all Y ≢Xi, for 1 ≤i ≤n.

Definition 2.16

The substitution action tσ is inductively defined by:

aσ ≡a (π · X)σ ≡π · σ(X) ([a]t)σ ≡[a](tσ) f(t1, . . . , tn)σ ≡f(t1σ, . . . , tnσ).

We may call tσ an instance of t.

Intuitively, σ propagates through the structure of t until it reaches an atom or a moderated unknown. σ ‘evaporates’ on an atom, and acts on the unknown of a moderated unknown. The moderating permutation then passes into the term substituted in that position. We suggest a reading of π · X as ‘permute π in whatever X eventually becomes’.

(#ab)a#bπ-1(a)#X (#X) (π ≠ id)a#π · X(#[]a)a#[a]ta#t (#[]b) a#[b]ta#t1 · · · a#tn (#f) a#f(t1, . . . , tn)
Figure 2. Freshness derivation rules for nominal terms

Note that meta-level substitution does not avoid capture; ([a]X)[a/X] ≡ [a]a. In this sense X is ‘meta’ and really does represent an unknown term. There is an exact and deliberate analogy here with context substitution, which is the substitution used when we write ‘let - be a in λa.-’, to obtain λa.a.

The following commutation is easy to prove [UPG04, FG07]:

Lemma 2.17

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

Proof

By straightforward induction on the structure of t.End of proof

Definition 2.18

A freshness (assertion) is a pair a#t of an atom and a term. Call a freshness of the form a#X (so t ≡X) primitive. Write ∆and ∇ for (possibly infinite) 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. Furthermore, write a ∈ ∆when a occurs anywhere in ∆, and X ∈ ∆when X occurs anywhere in ∆.

Definition 2.19

Define derivability on freshnesses in natural deduction style [Hod01] by the rules in Figure 2. Here:

• a and b permutatively range over atoms, i.e. a and b represent any two distinct atoms;

• π ranges over permutations

• X ranges over unknowns;

• t and t1, . . . , tn range over nominal terms;

• f ranges over term-formers; there is one copy of the rule for each term-former.

We use similar conventions in the rest of this paper.

The side-condition π ≠ id of the (#X) rule restricts π to non-empty permutations. There is no mathematical reason for this, but there is a nice computational one: the algorithm obtained by reading rules bottom-up, must terminate.

Definition 2.20

Write ∆ ⊢a#t when a derivation of a#t exists using the elements of ∆as assumptions. Say that ∆ entails a#t or a#t is derivable from ∆; call this a freshness judgement.

We usually write ∅⊢a#t as ⊢a#t. We will also write ∆ ⊢S for a set of freshnesses S when ∆ ⊢a#t for each a#t ∈S.

For example, in the substitution signature for the lambda calculus (Example 2.8), we have ⊢a#lam([b]b) and a#X ⊢a#app(X, lam([a]Y)):

(#ab)a#b (#[]b) a#[b]b(#f)a#lam([b]b)a#X(#[]a)a#[a]Y(#f) a#lam([a]Y ) (#f) a#app(X, lam([a]Y ))

The derivation rules are completely syntax-directed, so they also hold in the opposite direction:

Lemma 2.21

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

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

3. If ∆⊢a#[b]t then ∆ ⊢a#t.

4. If ∆⊢a#f(t1, . . . , tn) then ∆ ⊢a#ti, for 1 ≤i ≤n.

Proof

By an easy induction on the structure of the derivation rules in Figure 2.End of proof

(refl)t = tt = u (symm) u = tt = u u = v (tran) t = vt = u(cong[])[a]t = [a]ut = u(congf)f(t1, . . . , t, . . . , tn) = f(t1, . . . , u, . . . , tn)
a#t b#t[a#X] ∆···

(perm)

(a b) · t = tt = u (fr) (a ∉t, u)t = u
Figure 3. Derivation rules for nominal equality

Sometimes the freshness context ∆may be strengthened:

Lemma 2.22

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 we assumed c ∉a#X, we know c ≠ a. Then a#X ∈ ∆, and we conclude ∆ ⊢a#X by assumption.

• (#X): If 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).

• (#ab) and (#[]a) carry over directly.

• (#[]b) and (#f) are straightforward using the inductive hypothesis and the following facts: if c ∉ [b]t then c ∉t, and if c ∉ f(t1, . . . , tn) then c ∉ti for 1 ≤i ≤n.

End of proof
Lemma 2.23

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

Proof

By an easy induction on freshness derivations (Figure 2).End of proof

Definition 2.24

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

Note that ∆σ is not usually a freshness context unless σ(X) is an unknown for each a#X ∈∆.

Theorem 2.25

For any ∆′, ∆, σ, 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 2.23.End of proof

The above condition ∆′ ⊢∆σ ensures that ∆σ is consistent, in the sense that a#σ(X) is derivable from ∆′ for each a#X ∈∆.

2.3. Equality

Definition 2.26

An equality (assertion) is a pair t = u where t and u are terms of the same sort. Define derivability on equalities in natural deduction style by the rules in Figure 3.

We may call this the core theory and refer to it as CORE. We may write ∆ ⊢CORE t = u for ‘t = u is derivable from assumptions ∆in the core theory’; call this an equality judgement. We also write ∅⊢CORE t = u as ⊢CORE t = u.

In (fr) square brackets denote discharge in the sense of natural deduction (as in implication introduction); ∆denotes the other assumptions of the derivation of t = u. This is useful because unknowns in a derivation intuitively represent unknown terms, but any finite collection of such terms can mention only finitely many atoms; (fr) expresses that we can always find a fresh one. In sequent style (fr) would be

a#X, ∆⊢t = u ∆⊢t = u(a ∉t, u).

In (perm) read (a b) · t as ‘swap a and b in t’. This single rule expresses α-equivalence. To provide some intuition, here are some examples on closed terms.

Example 2.27

⊢CORE [a]a = [b]b is derivable in any signature, and ⊢CORE [a][b]app(a, b) = [b][a]app(b, a) is derivable in the substitution signature of the lambda calculus (Example 2.8):

(#ab)a#b (#[]b) a#[b]b(#[]a) b#[b]b (perm)[a]a = [b]b(#[]a)a#[a]app(b, a) (#[]b) a#[b][a]app(b, a)(#[]a) b#[b][a]app(b, a) (perm) [a][b]app(a, b) = [b][a]app(b, a)

Note that we use [a]a ≡ (a b) · [b]b and [a][b]app(a, b) ≡ (a b) · [b][a]app(b, a) in the conclusions of the derivations.

Example 2.28

• ⊢CORE [a]a = [b]b is derivable:

(#ab)a#b (#[]b) a#[b]b(#[]a) b#[b]b (perm)[a]a = [b]b

(Note here that [a]a ≡ (a b) · [b]b.)

• In the substitution signature of the lambda calculus (Example 2.8), ⊢CORE [a][b]app(a, b) = [b][a]app(b, a) is derivable. Since [a][b]app(a, b) ≡ (a b) · [b][a]app(b, a) it suffices to show ⊢CORE (a b) · [b][a]app(b, a) = [b][a]app(b, a). By (perm) this follows from ∆ ⊢a, b#[b][a]app(b, a), which follow using (#[]a) and (#[]b).

The following is an example of α-equivalence on open terms, which shows that we can rename the atom which is substituted for.

Lemma 2.29

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

Proof

De-sugaring, we derive sub([a]X, T) = sub([b](b a) · X, T) from b#X using the rules in Figures 3 and 2:

(#[]a)a#[a]Xb#X(#[]b) b#[a]X (perm) [b](b a) · X = [a]X (symm) [a]X = [b](b a) · X(congf)sub([a]X, T) = sub([b](b a) · X, T)End of proof

2.4. Inequality of nominal terms up to CORE

It is important to be able to decide when two nominal terms are not equal in CORE because:

• We need this to show that CORE is consistent (does not equate all terms; Corollary 2.33).

• We need to prove that CORE captures α-equivalence (and no more than α-equivalence; see Theorem 3.9).

• We promised to show that equality up to axioms for substitution is decidable. If we are unable to determine equality and inequality of terms without any axioms then our project would be doomed from the start.

(Ax)a ≈∆a∆⊢ds(π′, π)#X (Ds) π · X ≈∆π′ · Xt1 ≈∆u1· · · tn ≈∆un(F)f(t1, . . . , tn) ≈∆f(u1, . . . , un)t ≈∆u(Absaa)[a]t ≈∆[a]u(b a) · t ≈∆u ∆⊢b#t (Absab) [a]t ≈∆[b]u
Figure 4. Syntax-directed rules for CORE

The rules in Figure 3 are unsuited to determining inequality. The problem is that (tran) is not syntax-directed, in the sense that u appears in the premises and not in the conclusion. This makes derivation-search, and any proof that derivation-search must fail, hard. In this subsection we give a syntax-directed version of CORE which is more convenient for proving that derivations cannot exist. It bears an astounding resemblance to the equality on nominal terms introduced in nominal unification [UPG04] (we still need nominal algebra so we can extend CORE with axioms).

The following definition was introduced in [UPG04, Figure 2]; the proofs are modelled on a method presented in [FG07, p.13]:

Definition 2.30

Let t ≈∆u be an ordered tuple of a term t, a freshness context ∆, and a term u. Let the derivable equalities of t ≈∆u be inductively defined by the rules in Figure 4. Here we write ds(π, π′) for the set {a | π(a) ≠ π′(a)}, the difference set of π and π′. We write ∆ ⊢ ds(π, π′)#t for a set of proof-obligations ∆⊢a#t, one for each a ∈ ds(π, π′).

Theorem 2.31

∆⊢CORE t = u if and only if t ≈∆u is derivable in the sequent system for CORE.

Proof

The left-to-right direction is by induction on the structure of derivations of ∆ ⊢CORE t = u. By the inductive hypothesis it suffices to show:

• Syntax-directed equality ≈∆ is an equivalence relation and a congruence. This is [FG07, Theorem 24].

• If ∆⊢a#t and ∆ ⊢b#t then (a b) · t ≈∆t. This follows by an induction on the structure of t.

• If t ≈∆,a#X u where a ∉t, u then t ≈∆u. By a straightforward induction on the structure of derivations of t ≈∆,a#X u. The case of (Absab) uses Lemma 2.22 to strengthen the assumption ∆, a#X ⊢c#t to ∆⊢c#t.

For the right-to-left direction we work by induction on derivations of t ≈∆u. By the inductive hypothesis it suffices to show:

• ∆⊢CORE a = a. This is an instance of (refl).

• If ∆⊢ ds(π, π′)#X then ∆ ⊢CORE π · X = π′ · X. By induction on the number of elements in ds(π, π′). If this set is empty then π = π′ and the result follows easily by (refl). Now suppose a ∈ ds(π, π′). We construct a partial derivation of the proof obligation:

π · X = ((π(a) π′(a)) ◦π′) · Xπ(a)#π′ · X π′(a)#π′ · X(perm) ((π(a) π′(a)) ◦π′) · X = π′ · X (tran) π · X = π′ · X

The remaining equality π · X = ((π(a) π′(a)) ◦π′) · X follows from the assumptions ds(π, π′)#X using the inductive hypothesis and the fact that ds(π, (π(a) π′(a)) ◦π′) = ds(π, π′) \ {a}; the remaining freshnesses π(a)#π′ · X and π′(a)#π′ · X follow from the assumptions ds(π, π′)#X using Lemma 2.23.

• If ∆⊢CORE ti = ui for 1 ≤i ≤n, then ∆ ⊢CORE f(t1, . . . , tn) = f(u1, . . . , un). Using a number of instances of (tran) and (congf).

• If ∆⊢CORE t = u then ∆ ⊢CORE [a]t = [a]u. This is (cong[]).

• If ∆⊢CORE (b a) · t = u and ∆ ⊢b#t then ∆ ⊢CORE [a]t = [b]u. Suppose that Π and Π′ are derivations of

∆⊢CORE (b a) · t = u and ∆ ⊢b#t respectively. Then the following is a derivation of ∆ ⊢CORE [a]t = [b]u:

Π′b#t(#[]b)b#[a]t(#[]a)a#[a]t (perm)[b](b a) · t = [a]t (symm) [a]t = [b](b a) · tΠ(b a) · t = u(cong[])[b](b a) · t = [b]u (tran)[a]t = [b]uEnd of proof

As corollaries of Theorem 2.31 we obtain syntactic criteria for determining equality in CORE, and consistency of CORE.

∇σ(ax∇⊢t=u)π · tσ = π · uσ
Figure 5. The axiom rule
Corollary 2.32 (Syntactic criteria for CORE).

∆⊢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 ≡ f(t1, . . . , tn) and u ≡ f(u1, . . . , un) and ∆ ⊢CORE ti = ui for 1 ≤i ≤n.

Proof

By Theorem 2.31 it suffices to inspect the rules for t ≈∆u, which are just a rendering of the above criteria in terms of derivation rules.End of proof

Corollary 2.33 (Consistency of CORE).

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

Proof

By Corollary 2.32, ∆⊢CORE a = b is never derivable.End of proof

2.5. Axioms and theories

We now come to the raison d’être of nominal algebra: axioms.

Definition 2.34

Call a triple ∇⊢t = u where ∇ is a finite freshness context, an axiom. We may write ⊢t = u when ∇ is empty (the empty set). Call an instance of an axiom a step in a derivation where the conclusion is obtained from an axiom by instantiating unknowns by terms and permutatively renaming atoms such that the hypotheses are corresponding instances of freshness conditions of the axiom.

This is formally expressed by the rule (ax∇⊢t=u) in Figure 5. Here π ranges over permutations and σ ranges over substitutions. Recall that we write ∇σ for {a#σ(X) | a#X ∈∇}.

The reader might have expected that the premise of the axiom rule should be π · ∇σ instead of ∇σ. It turns out that both versions are correct, because of Lemma 2.23: ∆⊢∇σ iff∆⊢π · ∇σ for any ∆.

Definition 2.35

Call a set of axioms T a theory. Write ∆ ⊢T t = u when t = u can be derived from ∆ using only axioms from T.

A number of properties on freshnesses also hold for equations of any theory T.

Lemma 2.36

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

Proof

By induction on the structure of the rules of Figures 3 and 5.End of proof

Theorem 2.37

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

Proof

Analogous to the proof of Theorem 2.25.End of proof

3. Substitution on ground terms

Definition 3.1

Call terms g, h and k ground terms when they do not mention unknowns or explicit substitutions. Ground terms are inductively characterised by

g ::= a | [a]g | f(g1, . . . , gn).

where f ranges over all term-formers except for sub.

We now consider the meaning of explicit substitution on ground terms, in a suitable formal sense. This will make a connection between [a↦ →t] and actual capture-avoiding substitution on syntax, and we will find that connection useful later.

Definition 3.2

Define a ‘free atoms of’ function fa(g) on ground terms inductively as follows:

fa(a) = {a} fa([a]g) = fa(g) \ {a} fa(f(g1, . . . , gn)) =⋃1≤i≤nfa(gi).
Lemma 3.3

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

Proof

By induction on the structure of g.End of proof

Definition 3.4

Let the size of a ground term be inductively defined by:

|a| = 1 |[a]g| = |g| + 1 |f(g1, . . . , gn)| = |g1| + . . . + |gn| + 1.
Definition 3.5

For each finite set of atoms fix some choice of ‘fresh’ atom not in that finite set. Then define a ground substitution action g[h/a] on ground terms of sort T and [A]T 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) f(g1, . . . , gn)[h/a] ≡f(g1[h/a], . . . , gn[h/a]),

where f ranges over all term-formers excluding sub. By ‘c fresh’ we mean that c is chosen such that c ∉{a, b} ∪ fa(g) ∪ fa(h) according to our arbitrary choice. We will not mention c ∉{a, b} anymore, since this is enforced by our permutative convention (see Convention 2.3).

Note that the ground substitution action is well-defined, since |g[c/b]| = |g| in the penultimate case of Definition 3.5, as can be shown by an induction on the size of g. We will often use this fact that capture-avoiding substitution of atoms for atoms preserves size.

Lemma 3.6 states familiar properties of ground terms. It makes the vital connection between ‘substitution as we know it’ and the nominal technology we bring to bear on it.

Lemma 3.6

For ground terms g, h, k:

1. Identity. ⊢CORE g[a/a] = g.

2. Swapping. If ⊢b#g then ⊢CORE g[b/a] = (b a) · g.

3. Garbage collection. If ⊢a#g then ⊢CORE g[h/a] = g.

4. Non-capturing distributivity. If ⊢a#k then ⊢CORE g[h/a][k/b] = g[k/b][h[k/b]/a].

Proof

Part 1 follows from the stronger property that g[a/a] ≡g, which we can show by an easy induction on the structure of g. The other parts all follow by an induction on the size of g.End of proof

We will now show how equality on ground terms in theory CORE coincides with a straightforward definition of α-equivalence on ground terms: syntactic equality extended with a rule to rename bound variables.

Definition 3.7

Define an α-equivalence relation g =α h inductively by the rules in Figure 6. Here ‘c fresh’ means any c such that c ∉{a, b} ∪ fa(g) ∪ fa(h).

Lemma 3.8

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

g =α gg =α h h =α gg1 =α g2g2 =α g3g1 =α g3g =α h [a]g =α [a]hg1 =α h1 · · · gn =α hnf(g1, . . . , gn) =α f(h1, . . . , hn) g[c/a] =α h[c/b] [a]g =α [b]h(c fresh)
Figure 6. α-equivalence =α on ground terms
(var↦→) ⊢ a[a↦ →T] = T(b↦→) ⊢ b[a↦ →T] = b(f↦→) ⊢f(X1, . . . , Xn)[a↦ →T] = f(X1[a↦ →T], . . . , Xn[a↦ →T]) (f ≠ sub)(abs↦→) c#T ⊢ ([c]U)[a↦ →T] = [c](U[a↦ →T])
Figure 7. Axioms of SIMP
Proof

All instances of a and b in g must occur in the scope of abstractors [a] and [b]. Traverse the structure of g bottom-up using the rules of Figure 6 to rename abstractions by [a] and [b] to fresh atoms. Call the new term g′. Now (a b) · g′ ≡g′ because a, b ∉g′. Equality is symmetric, so we reverse the process to return to g.End of proof

Lemma 3.8 enables us to prove the main result of this section: in the presence of the equalities of CORE, ground terms g and h are provably equal if and only they are α-equivalent.

Theorem 3.9

⊢CORE g = h if and only if g =α h.

Proof

We prove the left-to-right implication by induction on the structure of g, using the syntactic criteria of Corollary 2.32. The cases of g ≡a and g ≡ f(g1, . . . , gn) are easy. Now suppose g ≡ [a]g′, then there are two possibilities:

1. h ≡ [a]h′ and ⊢CORE g′ = h′. Then g′ =α h′ by the inductive hypothesis, and we conclude [a]g′ =α [a]h′ by congruence.

2. h ≡ [b]h′, ⊢b#g′ and ⊢CORE (b a) · g′ = h′. Then a, b ∉ fa([a]g′) by Lemma 3.3 and some easy calculations, so [a]g′ =α [b](b a) · g′ by Lemma 3.8 and symmetry. Also [b](b a) · g′ =α [b]h′ by congruence and the inductive hypothesis. We conclude [a]g′ =α [b]h′ by transitivity.

Conversely suppose that g =α h. It suffices to show that equality in CORE can simulate every derivation rule of =α. We treat the only non-trivial case: [a]g =α [b]h is deduced using the last rule from Figure 6. Then for c chosen fresh for fa(g) ∪ fa(h), we know g[c/a] =α h[c/b]. By the inductive hypothesis ⊢CORE g[c/a] = h[c/b]. Since ⊢c#g and ⊢c#h we obtain ⊢CORE g[c/a] = (c a) · g and ⊢CORE h[c/b] = (c b) · h by part 2 of Lemma 3.6. Using (symm), (tran) and (cong[]) we obtain ⊢CORE [c](c a) · g = [c](c b) · h. By (perm) ⊢CORE [c](c a) · g = [a]g and ⊢CORE [c](c b) · h = [b]h, since ⊢c#g and ⊢c#h. Using (symm) and (tran) we conclude that ⊢CORE [a]g = [b]hEnd of proof

4. The theory SIMP; simply substitution

We introduce nominal algebra theory SIMP which is sound but not complete with respect to the ground term model from Section 3. This is an important technical step towards SUB because we shall prove properties of SUB by reducing them to properties of SIMP.

Definition 4.1

Let SIMP be the nominal algebra theory with axioms as in Figure 7.

Here, f ranges over all term-formers except for sub. Recall that T and U are unknowns of T, and that the Xi are unknowns of sort T or [A]T (which one applies depends on the instance of f).

Lemma 4.2

For ground terms g and h, if ⊢a#g then ⊢SIMP g[a↦ →h] = g.

Proof

By induction on the size of g.End of proof

Theorem 4.3

If g and h are ground terms then ⊢SIMP g[a↦ →h] = g[h/a] is always derivable.

Proof

By induction on the size of g. We only consider the interesting cases:

• g ≡ [a]g′. Then ⊢SIMP ([a]g′)[a↦ →t] = [a]g′ by Lemma 4.2 since ⊢a#[a]g′. We are done since ([a]g′)[h/a] ≡ [a]g′.

• g ≡ [b]g′, b ∈ fa(h). Then ([b]g′)[h/a] ≡ [c](g[c/b][h/a]) where c is a fresh atom according to our arbitrary choice, i.e. c ∉ fa(g′) ∪ fa(h). Then by Lemma 3.3 also ⊢c#g′ and ⊢c#h. Now ⊢CORE [c](c b) · g′ = [b]g′ by (perm) since ⊢b#[b]g′ and ⊢c#[b]g′. By (symm), (cong[]) and (congf) we obtain

⊢CORE ([b]g′)[a↦ →h] = ([c](c b) · g′)[a↦ →h].

By axiom (abs ↦→) also

⊢SIMP ([c](c b) · g′)[a↦ →h] = [c](((c b) · g′)[a↦ →h])

since ⊢c#h. By the inductive hypothesis and (cong[])

⊢SIMP [c](((c b) · g′)[a↦ →h]) = [c](((c b) · g′)[h/a]).

Since ⊢CORE g′[c/b] = (c b) · g′ by part 2 of Lemma 3.6, we deduce

⊢SIMP [c](((c b) · g′)[h/a]) = [c](g′[c/b][h/a])

using the rules of equality. Using (tran) we conclude ⊢SIMP ([b]g′)[a↦ →h] = [c](g′[c/b][h/a]).

End of proof
Definition 4.4

Define the translation _↧→ of closed terms to ground terms inductively on closed terms by:

a↧→≡a ([a]t)↧→≡[a](t↧→) f(t1, . . . , tn)↧→≡f(t↧→1, . . . , t↧→n) (f ≠ sub) sub(t, u)↧→≡g[u↧→/a] ([a]g ≡t↧→).

Note that (t[a↦ →u])↧→≡t↧→[u↧→/a] follows from the sub case, since [a](t↧→) ≡ ([a]t)↧→by the abstraction case.

Lemma 4.5

For any closed term t, if ⊢a#t then ⊢a#t↧→.

Proof

By induction on the structure of t.End of proof

Note that the converse of Lemma 4.5 does not hold. Take for example t ≡b[c↦ →a]. Then ⊢a#(b[c↦ →a])↧→ since (b[c↦ →a])↧→≡b. But ⊬a#b[c↦ →a], since ⊬a#a.

Theorem 4.6

For any closed term t, ⊢SIMP t = t↧→.

Proof

By induction on the structure of t. We consider the only non-trivial case t ≡ sub(u, v). By definition sub(u, v)↧→≡g[v↧→/a] where [a]g ≡u↧→, and by the inductive hypothesis, ⊢SIMP u = u↧→ and ⊢SIMP v = v↧→. By (congf) and (tran), we obtain

⊢SIMP sub(u, v) = sub(u↧→, v↧→).

By Theorem 4.3 we know ⊢SIMP g[a↦ →v↧→] = g[v↧→/a]. Since [a]g ≡u↧→and g[v↧→/a] ≡ sub(u, v)↧→, this is syntactically equivalent to

⊢SIMP sub(u↧→, v↧→) = sub(u, v)↧→.

By an application of (tran) we conclude ⊢SIMP sub(u, v) = sub(u, v)↧→as required.End of proof

As a corollary of Theorem 4.6 all standard properties of capture-avoiding substitution on ground terms carry over to closed terms.

Corollary 4.7

For closed terms t, u, v:

1. ⊢SIMP t[a↦ →a] = t.

2. If ⊢b#t then ⊢SIMP t[a↦ →b] = (b a) · t.

3. If ⊢a#t then ⊢SIMP t[a↦ →u] = t.

4. If ⊢a#v then ⊢SIMP t[a↦ →u][b↦ →v] = t[b↦ →v][a↦ →u[b↦ →v]].

∆⊢CORE t = π · lσ ∆⊢CORE u = π · rσ ∆⊢∇σ (→rew)∆⊢R t →u(∇⊢l →r ∈R)∆⊢R t →u(→[])∆⊢R [a]t →[a]u∆⊢R t →u(→f)∆⊢R f(t1, . . . , t, . . . , tn) →f(t1, . . . , u, . . . , tn)
Figure 8. Derivation rules for nominal rewriting
Proof

Using Theorem 4.6 and Lemma 3.6.End of proof

In this section we have established that in the presence of the equalities of SIMP, t and t↧→ are provably equal, for closed terms t. Yet many questions related to open terms remain:

1. Is SIMP conservative over CORE? That is, if two terms that do not mention sub are equated in SIMP, are they necessarily equated in CORE? (Answer: Yes.)

2. Is equality in SIMP decidable? (Answer: Yes.)

3. Is SIMP sound for the ground term model? That is, if two terms are equated in SIMP, are all their closed instances α-equivalent, if we interpret every occurrence of sub by capture-avoiding substitution? (Answer: Yes.)

4. Is SIMP complete? That is, if all closed instances of two terms are α-equivalent where we interpret sub by capture-avoiding substitution, are the terms themselves provably equal in SIMP? (Answer: No, but a more powerful theory SUB exists which is complete, and which retains properties 1 to 3 of this list.)

The next two sections provide answers to these questions together with detailed proofs.

5. Substitution on open terms using SIMP

In this section we recall a notion of rewriting called nominal rewriting [FG07], which is tailored to nominal terms. We will use nominal rewriting to prove properties on open terms of theory SIMP.

5.1. Nominal rewriting

Definition 5.1

A nominal rewrite rule ∇⊢l →r is a tuple of a freshness context ∇ and terms l and r of the same sort such that ∇ and r mention only unknowns appearing in l.

A nominal rewrite system R is a set of nominal rewrite rules. It determines a set of nominal rewrites ∆⊢R t →u inductively by the rules in Figure 8.

Write ∆ ⊬R t →u when the rewrite ∆ ⊢R t →u is not derivable.

In the (→f) rule of Figure 8, f ranges over all term-formers of the signature of R (whatever that signature is). The (→rew) rule is closely related to the (ax∇⊢t=u) rule from Figure 5. We discuss the aspects of this rule in more detail:

• The permutation π allows us to permutatively rename atoms. Consider for instance the substitution signature of the lambda calculus (Example 2.8) extended with a term-former const : ()T, and write const() as const. Then the rewrite rule app(a, b) → const generates, for example, rewrites app(b, a) → const and app(a, c) → const but not app(a, a) → const because no π can identify a with b.

• The substitution σ gives unknowns X in rules the character of ‘unknown terms’, and is subject to the freshness conditions formulated by ∆ ⊢∇σ. Note that we could also have used ∆ ⊢π · ∇σ, which is equivalent to ∆ ⊢∇σ by Lemma 2.23.

• The use of equality in CORE gives abstractions [a]- the character of real abstractions. For example the rule lam([a]lam([b]b)) → const generates rewrites

lam([a]lam([a]a)) →const lam([b]lam([b]b)) →const lam([b]lam([c]c)) →const.
∆⊢R t →u (→∗→) ∆⊢R t →∗u∆⊢CORE t = u (→∗refl) ∆⊢R t →∗u∆⊢R t →∗u ∆⊢R u →∗v (→∗tran) ∆⊢R t →∗v
Figure 9. Derivation rules for the transitive reflexive closure of R

The following result is easy to prove from the definition of rewriting:

Lemma 5.2

If ∆⊢R t →u and ∆′ ⊢∆σ, then ∆′ ⊢R tσ →uσ.

Proof

By induction on the derivation of ∆ ⊢R t →u we construct a derivation of ∆′ ⊢R tσ →uσ.End of proof

Definition 5.3

Write ∆ ⊢R t →∗u for the transitive reflexive closure of R defined inductively by the rules in Figure 9.

Write ∆ ⊬R t →∗u when ∆ ⊢R t →∗u is not derivable.

If a term does not have any rewrites, the transitive reflexive closure of R is precisely CORE-equality:

Lemma 5.4

If there is no t′ such that ∆ ⊢R t →t′ then

∆⊢R t →∗u iff ∆⊢CORE t = u.

Proof

Suppose there is no t′ such that ∆ ⊢R t →t′. If ∆⊢CORE t = u then by (→∗refl) also ∆ ⊢R t →∗u. Conversely if ∆ ⊢R t →∗u then this rewrite must be derived using (→∗refl) by an inductive argument.End of proof

Definition 5.5

Call a nominal rewrite system R confluent when if ∆ ⊢R t →∗u and ∆ ⊢R t →∗v then there is some w such that ∆ ⊢R u →∗w and ∆ ⊢R v →∗w.

Definition 5.6

Call a nominal rewrite system R strongly normalising when there is no infinite sequence t1, t2, t3, . . . such that ∆ ⊢R ti →ti+1 for all 1 ≤i.

Lemma 5.7

If a derivation exists of ∆ ⊢R t →u then that derivation mentions (→rew) exactly once.

Proof

By the structure of the derivation rules from Figure 8.End of proof

Definition 5.8

If a rewrite ∆ ⊢R t →u occurs, it must occur at some subterm t′ of t (the subterm t′ where we actually use (→rew) and prove ∆ ⊢∇σ and ∆ ⊢CORE t′ = lσ). We say that the rewrite occurs at t′ inside t. If the derivation tree has just an instance of (→rew), then we may say the rewrite occurs at top level.

Call a pair of nominal rewrites ∆ ⊢R t →u and ∆ ⊢R t →v a critical pair when at least one of the rewrites occurs at top level. If any of the two rewrites occurs at a moderated unknown inside t, call the critical pair trivial. Otherwise call it nontrivial.

Definition 5.9

Call a rewrite rule ∇⊢l →r uniform when ∆ ⊢a#l and ∆ ⊢∇ imply ∆ ⊢a#r for all ∆ and a. A rewrite rule ∇⊢l →r is left-linear when l does not mention the same unknown more than once. A uniform nominal rewrite system with only left-linear rules and no non-trivial critical pairs is orthogonal.

Theorem 5.10

An orthogonal uniform nominal rewrite system is confluent.

Proof

See [FG07, Theorem 65].End of proof

Remark 5.11

Nominal rewriting is the default notion of rewriting for nominal terms, like higher-order rewriting (such as CRS’s [KvOvR93] and HRS’s [MN98]) is for higher-order terms. The major differences between the two frameworks can be summarised as follows:

• The default notion of instantiation of meta-variables is capturing for nominal rewriting whereas it is capture-avoiding for higher-order rewriting.

• Nominal rewriting uses unification up to α whereas higher-order rewriting uses unification up αβ(η).

Detailed comparisons are elsewhere [FG07].

(Rvar) ⊢ a[a↦ →T] → T(Rb) ⊢ b[a↦ →T] → b(Rf) ⊢ f(X1, . . . , Xn)[a↦ →T] → f(X1[a↦ →T], . . . , Xn[a↦ →T]) (f ≠ sub)(Rabs) c#T ⊢ ([c]U)[a↦ →T] → [c](U[a↦ →T])
Figure 10. Substitution as a rewrite system SIMPr

5.2. SIMPr: explicit substitution rewritten

Definition 5.12

Let SIMPr be the nominal rewrite system defined in Figure 10.

A basic correctness result is this:

Lemma 5.13

If ∆⊢SIMPr t →∗u then ∆ ⊢SIMP t = u is derivable.

Proof

By induction on the structure of derivations of ∆ ⊢SIMPr t →∗u. The case of (→∗→) uses the precise correspondence between the rewrites in Figure 10 and the axioms in Figure 7. (→∗refl) uses (refl), and (→∗tran) uses (tran).End of proof

Remark 5.14

The (Rb) rule cannot be represented by a rule in a higher-order rewrite system, since in such a system object-variables only exist when they are bound by a meta-level abstraction. That is, the rule sub(λx.y, T) →y does not represent (Rb) since y represents a meta-variable instead of an object-variable. It represents the more general rule a#X ⊢X[a↦ →T] →X.

Lemma 5.15

All rewrite rules of SIMPr are uniform.

Proof

For each rule, use appropriate instances of Lemma 2.21. For example, for the (Rabs) rule, we need to show that ∆ ⊢a′#([c]U)[a↦ →T] and ∆ ⊢c#T imply ∆ ⊢a′#[c](U[a↦ →T]) for any a′ and ∆. From the first assumption we know, by Lemma 2.21:

• if a′ = a or a′ = c then a′#T ∈∆;

• if a′ ≠ a and a′ ≠ c then a′#T ∈ ∆and a′#U ∈∆.

Using these assumptions it is easy to show ∆ ⊢a′#[c](U[a↦ →T]) by case distinction on a′.End of proof

Theorem 5.16 (Confluence of SIMPr).

SIMPr is confluent.

Proof

By Lemma 5.15 all rewrite rules of SIMPr are uniform. Also, SIMPr has no non-trivial critical pairs and every rule is left-linear (each unknown is mentioned on the left at most once). Then SIMPr is orthogonal and uniform by Definition 5.9. We conclude that it is confluent by Theorem 5.10.End of proof

Confluence of SIMPr has a number of nice corollaries, which comprise the remainder of this subsection.

Definition 5.17

Call a term t a SIMPr-normal form with respect to ∆when there is no u such that ∆⊢SIMPr t →u.

Theorem 5.18

Suppose that t and u are SIMPr-normal forms with respect to ∆. Then

∆⊢SIMP t = u if and only if ∆⊢CORE t = u.

Proof

The (empty) set of axioms of CORE is a subset of the axioms of SIMP so a derivation in CORE is also a derivation in SIMP and it follows that if ∆ ⊢CORE t = u then ∆ ⊢SIMP t = u.

Conversely suppose ∆ ⊢SIMP t = u. By Theorem 5.16 there is some term v such that ∆ ⊢SIMPr t →∗v and ∆⊢SIMPr u →∗v. By assumption there can be no t′ and u′ such that ∆ ⊢SIMPr t →t′ and ∆ ⊢SIMPr u →u′. Then ∆⊢CORE t = v and ∆ ⊢CORE u = v by Lemma 5.4, and we conclude ∆ ⊢CORE t = u by (symm) and (tran).End of proof

Corollary 5.19 (Conservativity of SIMP over CORE).

Suppose that t and u do not mention the term-former sub. Then

∆⊢SIMP t = u if and only if ∆⊢CORE t = u.

Proof

This is an instance of Theorem 5.18, since if t and u do not mention sub, then t and u are SIMPr-normal forms with respect to any ∆.End of proof

Recall the notation t↧→for closed terms t from Definition 4.4.

Corollary 5.20

For closed terms t and u,

⊢SIMP t = u if and only if ⊢CORE t↧→= u↧→.
Proof

⊢SIMP t = u is equivalent to ⊢SIMP t↧→= u↧→by Theorem 4.6, (symm) and (tran). By Corollary 5.19 this is equivalent to ⊢CORE t↧→= u↧→.End of proof

Corollary 5.21 (Consistency of SIMP).

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

Proof

A corollary of Corollaries 5.19 and 2.33.End of proof

For the final theorem of this subsection we need a few definitions.

Definition 5.22

Call a substitution σ closing for an unknown X when σ(X) is a closed term. Call σ closing for a term t or closing for a freshness context ∆when σ(X) is closed for every X ∈t or X ∈∆.

Say a closing substitution σ for ∆is ∆-consistent when ⊢∆σ, i.e. when ⊢a#σ(X) for all a#X ∈∆.

Theorem 5.23 (Soundness of SIMP).

SIMP is sound for the ground term model. That is: If ∆⊢SIMP t = u then tσ↧→=α uσ↧→for all ∆-consistent closing substitutions σ (for ∆, t and u).

Proof

⊢SIMP tσ = uσ by Theorem 2.37 and our assumption that ⊢∆σ. We obtain ⊢CORE tσ↧→= uσ↧→ by Corollary 5.20, since tσ and uσ are closed. We conclude tσ↧→=α uσ↧→by Theorem 3.9, since tσ↧→and uσ↧→are ground.

End of proof

5.3. Failure of completeness for SIMP

SIMP is not a complete theory of substitution on ground terms. Unknowns in nominal algebra represent unknown terms, and here are some examples of statements that are true for every closing σ (for the unknowns in the statements) but which are not derivable in SIMP:

Theorem 5.24 (Incompleteness of SIMP).

1. ⊬SIMP X[a↦ →a] = X.

2. b#X ⊬SIMP X[a↦ →b] = (b a) · X.

3. a#X ⊬SIMP X[a↦ →T] = X.

4. a#U ⊬SIMP X[a↦ →T][b↦ →U] = X[b↦ →U][a↦ →T[b↦ →U]].

Proof

For part 1, we can easily check using the syntactic criteria of Corollary 2.32 that ⊢CORE X[a↦ →a] = X is not derivable. Now since X[a↦ →a] and X have no SIMPr rewrites, we conclude ⊬SIMP X[a↦ →a] = X by Theorem 5.18. The proofs of the other parts are similar.End of proof

The fact that above assertions are derivable for closing substitutions follows by Corollary 4.7.

Nominal algebra has a model theory and satisfies soundness and completeness [GM06b, GM07]. So SIMP has ‘nonstandard’ models which contain ‘pathological elements’ for which the above equalities do not hold. SIMP defines substitution, but it does not express all of the properties which emerge from that definition. To do that we must strengthen the theory. Before that however, it is useful to consider the computational content of SIMP.

5.4. Strong normalisation and decidability

We expect the part of a λ-calculus that handles substitution to be terminating [BR95, Les94] — so is SIMP terminating? After all our syntax contains sub as an explicit term-former, and it contains unknowns so that sub cannot always be completely eliminated. Also, we consider single substitutions and not simultaneous substitutions, so that the order of substitutions matters. Perhaps that all makes enough of a difference that reductions could cycle or diverge in some way?

In fact reductions in SIMPr are extremely well-behaved. We show strong normalisation by a standard method: define a well-founded measure |t|m on terms and show that rewrites reduce it.

Definition 5.25

For a term t let |t|m be inductively defined by:

|a|m = 1 |π · X|m = 1 |[a]t|m = |t|m + 1 |f(t1, . . . , tn)|m = |t1|m + . . . + |tn|m + n + 1 (f ≠ sub)|sub(t, u)|m = |t|m ∗(|u|m + 1)

For terms u[a↦ →t] we have

|u[a↦ →t]|m ≡|sub([a]u, t)|m = |[a]u|m ∗(|t|m + 1) = (|u|m + 1) ∗(|t|m + 1).
Lemma 5.26

For all terms t and permutations π:

1. |t|m > 0.

2. |t|m = |π · t|m. As a corollary, if ∆ ⊢CORE t = u then |t|m = |u|m.

Proof

Both parts can be proven by a simple induction on the structure of t. The corollary follows by Corollary 2.32 which states that t and u are renamed versions of each other by means of permutations.End of proof

Lemma 5.27

For terms t, u, t1, . . . , tn and term-formers f ≠ sub:

1. |a[a↦ →t]|m > |t|m.

2. |b[a↦ →t]|m > |b|m.

3. |f(t1, . . . , tn)[a↦ →t]|m > |f(t1[a↦ →t], . . . , tn[a↦ →t])|m (f ≠ sub).

4. |([c]u)[a↦ →t]|m > |[c](u[a↦ →t])|m.

Proof

By straightforward calculations using the measure on terms. The last part uses the fact |t|m > 0 (Lemma 5.26 above).End of proof

Lemma 5.28

For terms t, u, t1, . . . , tn and term-formers f:

1. If |t|m > |u|m then |[a]t|m > |[a]u|m.

2. If |t|m > |u|m then |f(t1, . . . , t, . . . , tn)|m > |f(t1, . . . , u, . . . , tn)|m.

Proof

Again by straightforward calculations. The last part uses the fact that |t|m > 0 when f = sub.End of proof

Theorem 5.29 (Strong normalisation of SIMPr).

SIMPr is strongly normalising.

Proof

It suffices to show that if ∆ ⊢SIMPr t →u then |t|m > |u|m. We proceed by induction on the rules from Figure 8, using the rewrite rules from Figure 10.

Suppose ∆ ⊢SIMPr t →u is derived using (→ []) or (→ f); then the result follows by Lemma 5.28 and the inductive hypothesis.

Suppose ∆ ⊢SIMPr t →u is derived using (→ rew); then for each SIMPr rewrite rule of the form ∇⊢l →r from Figure 10 we have, for some π and σ,

∆⊢CORE t = π · lσ and ∆⊢CORE u = π · rσ and ∆⊢π · ∇σ.

By part 2 of Lemma 5.26, |t|m = |π · lσ|m = |lσ|m and |u|m = |π · rσ|m = |rσ|m. So in order to show that |t|m > |u|m, it suffices to show |lσ|m > |rσ|m. For each SIMPr rule this is an instance of Lemma 5.27.End of proof

We have already given an algorithm to compute normal forms on closed terms in Definition 4.4:

Lemma 5.30

If t is closed then t↧→is a SIMPr-normal form of t with respect to any ∆.

Proof

By an induction on the structure of t.End of proof

Theorem 5.31 (Unique normal forms for SIMPr).

SIMPr-normal forms are unique up to equality in CORE.

Proof

Let ∆be a freshness context and t be a term. By Theorem 5.29 t has a normal form, say u, with respect to ∆. Now suppose v is also a normal form of t with respect to ∆. Then ∆ ⊢SIMPr t →∗u and ∆ ⊢SIMPr t →∗v. By confluence (Theorem 5.16) there exists a term w such that ∆ ⊢SIMPr u →∗w and ∆ ⊢SIMPr v →∗w. Since u and v do not have any rewrites ∆ ⊢CORE u = w and ∆ ⊢CORE v = w by Lemma 5.4. Using (symm) and (tran) we conclude ∆ ⊢CORE u = v.End of proof

As a corollary we obtain decidability of theory SIMP:

Theorem 5.32 (Decidability of SIMP).

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

Proof

Given ∆, t and u the following procedure decides whether ∆ ⊢SIMP t = u is derivable:

1. Rewrite t and u to SIMPr-normal forms t′ and u′ with respect to ∆; by Theorem 5.29 these exist and by Theorem 5.31 they are unique up to equality in CORE.

2. Check whether ∆ ⊢CORE t′ = u′ using the syntactic criteria of Corollary 2.32.

3. If ∆⊢CORE t′ = u′ then return ‘true’, otherwise return ‘false’.

End of proof

6. Substitution on open terms using SUB

In this section we focus on theory SUB from Figure 1. We show that it is decidable and complete with respect to the ground term model by relating it to theory SIMP.

Definition 6.1

The theory of substitution SUB is the equality relation obtained by the rules of nominal algebra with the axioms in Figure 1. Here f ranges over all term-formers, including sub.

As an example, we show that our standard properties of capture-avoiding substitution are all derivable in SUB.

Lemma 6.2

The following judgements are derivable in SUB:

1. ⊢SUB X[a↦ →a] = X.

2. b#X ⊢SUB X[a↦ →b] = (b a) · X.

3. a#X ⊢SUB X[a↦ →T] = X.

4. a#U ⊢SUB X[a↦ →T][b↦ →U] = X[b↦ →U][a↦ →T[b↦ →U]].

Proof

Parts 2 and 3 are direct from (ren↦→) and (#↦→). For the other two parts we give nominal algebra derivations in the theory SUB.

Derivation for part 1:

(#[]a)a#[a]X[b#X]1(#[]b)b#[a]X (perm)[b](b a) · X = [a]X (symm) [a]X = [b](b a) · X(congf)X[a↦ →a] = ((b a) · X)[b↦ →a][b#X]1(#X)a#(b a) · X(axren↦→)((b a) · X)[b↦ →a] = X (tran)X[a↦ →a] = X (fr)1X[a↦ →a] = X

In the above derivation of X[a↦ →a] = X, the superscript number one 1 is an annotation associating the instance of the rule (fr) with the assumption it discharges in the derivation. This is standard natural deduction notation.

For the derivation of part 4, we write s for [b↦ →U] and we use the unsugared syntax for the other substitutions.

(axf↦→)sub([a]X, T)s = sub(([a]X)s, Ts)a#U(axabs↦→)([a]X)s = [a](Xs)(congf) sub(([a]X)s, Ts) = sub([a](Xs), Ts) (tran)sub([a]X, T)s = sub([a](Xs), Ts)End of proof

We conjecture that it is not possible to derive ⊢SUB X[a↦ →a] = X without (fr).

6.1. Soundness and the relation to SIMP

SUB can do everything that SIMP can:

Lemma 6.3

If ∆⊢SIMP t = u then ∆ ⊢SUB t = u.

Proof

All the axioms of SIMP are also axioms of SUB, except for (b↦→). However an instance of (b↦→) is also an instance of (#↦→). Therefore any SIMP derivation is also a SUB derivation. The result follows.End of proof

We now show that SIMP can do everything that SUB can — provided that the terms are closed. We need a technical lemma:

Lemma 6.4

If t, u and v are closed, then:

1. ⊢SIMP sub(t, u)[a↦ →v] = sub(t[a↦ →v], u[a↦ →v]).

2. If ⊢a#t then ⊢SIMP [a]sub(t, a) = t.

Proof

We consider the parts in turn:

1. Since ⊢SIMP t = t↧→by Theorem 4.6, the proof obligation is equivalent to

⊢SIMP sub(t↧→, u)[a↦ →v] = sub(t↧→[a↦ →v], u[a↦ →v]).

Now t↧→ is of the form [a]g or [b]g, where g is a ground term. We only consider the case of b, the case of a is completely analogous. Take c fresh such that ⊢c#g and ⊢c#v. Then ⊢CORE [b]g = [c](c b) · g using (perm), since ⊢b#[b]g and ⊢c#[b]g. Then using the rules for equality, the proof obligation is equivalent to

⊢SIMP sub([c](c b) · g, u)[a↦ →v] = sub(([c](c b) · g)[a↦ →v], u[a↦ →v]).

Since ⊢c#v, ⊢SIMP ([c](c b) · g)[a↦ →v] = [c](((c b) · g)[a↦ →v]) by axiom (abs↦→), so the proof obligation is equivalent to ⊢SIMP sub([c](c b) · g, u)[a↦ →v] = sub([c](((c b) · g)[a↦ →v]), u[a↦ →v]). Or, using sugar:

⊢SIMP ((c b) · g)[c↦ →u][a↦ →v] = ((c b) · g)[a↦ →v][c↦ →u[a↦ →v]].

And this is just an instance of part 4 of Corollary 4.7, since ⊢c#v.

2. We must show ⊢SIMP [a]sub(t, a) = t. By Theorem 4.6 this is equivalent to ⊢SIMP [a]sub(t↧→, a) = t↧→. We proceed by case distinction on the structure of t↧→:

• t↧→≡ [a]g: Then ⊢SIMP [a](g[a↦ →a]) = [a]g follows by (cong[]) and part 1 of Corollary 4.7.

• t↧→≡ [b]g: Then ⊢SIMP [a](g[b↦ →a]) = [b]g follows from

⊢SIMP [a](g[b↦ →a]) = [a](a b) · g and ⊢SIMP [a](a b) · g = [b]g.

by (tran). By (cong[]), ⊢SIMP [a](g[b↦ →a]) = [a](b a) · g follows from ⊢SIMP g[b↦ →a] = (a b) · g. By Corollary 4.7, this is when ⊢a#g. By (perm) and the rules for freshness also ⊢SIMP [a](b a) · g = [b]g when ⊢a#g. By Lemma 2.21, this is when ⊢a#[b]g. Since [b]g ≡t↧→, this follows from the assumption ⊢a#t by Lemma 4.5.

End of proof

On closed terms, SUB is equivalent to SIMP:

Lemma 6.5

For closed terms t, u:

⊢SUB t = u if and only if ⊢SIMP t = u.
Proof

The right-to-left part follows by Lemma 6.3.

For the left-to-right part, we must show that SIMP can simulate the axioms of SUB on closed terms. Axioms (var↦→), (abs↦→) and (f↦→), for f ≠ sub, are also present in SIMP. Each instance of axiom (f↦→), where f = sub, is an instance of part 1 of Lemma 6.4. Instances of axioms (ren↦→) and (#↦→) are instances of parts 2 and 3 of Corollary 4.7. Finally, each instance of (η↦→) is an instance of part 2 of Lemma 6.4.End of proof

To recap, SIMP is sound for a ground term model by Theorem 4.3, equality in SIMP is decidable by Theorem 5.32, but not complete by the Theorem 5.24.

We now build the tools to prove that SUB is sound, decidable — and also complete for the ground term model. For soundness we have already done all the hard work:

Theorem 6.6 (Soundness of SUB).

SUB is sound for the ground term model. That is: If ∆⊢SUB t = u then tσ↧→=α uσ↧→for all ∆-consistent closing substitutions σ (for ∆, t and u).

Proof

Since ∆ ⊢SUB t = u and σ is ∆-consistent, we obtain ⊢SUB tσ = uσ by Theorem 2.37. tσ and uσ are closed so by Lemma 6.5 ⊢SIMP tσ = uσ. By Corollary 5.20 we obtain ⊢CORE tσ↧→= uσ↧→. We conclude tσ↧→=α uσ↧→ by Theorem 3.9, since tσ↧→and uσ↧→are ground.End of proof

6.2. Decidability

In this subsection we will establish that equality in SUB is decidable. We do this by transforming the problem of deciding whether a derivation of ∆ ⊢SUB t = u exists, into the problem of deciding whether a derivation of ⊢SIMP t′ = u′ exists, for some carefully-chosen closed terms t′ and u′ in an extended signature (to be precise: in a correspondingly extended theory with extra (f↦→) axioms for the extra term-formers). We can then exploit decidability of SIMP (Theorem 5.32), and conclude that SUB is decidable. The rest of this subsection makes this formal.

Definition 6.7

Fix some substitution signature T , and fix ∆, t, and u where t and u are terms in T . 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 pick the following data:

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

• Choose some fresh term-former dX : (T, . . . , T)T (so dX does not occur in T) with kX arguments.

• Choose some entirely fresh atom cX when X : [A]T.

Write C = {cX | X ∈X, X : [A]T}, write D = {dX | X ∈X}, and let T′ be the signature T ∪D.

Definition 6.8

Define a substitution ς by:

ς(X) = dX(aX1, . . . , aXkX) (X ∈X, X : T)ς(X) = [cX]dX(aX1, . . . , aXkX) (X ∈X, X : [A]T)ς(Y ) = Y (Y ∉X)

A few words on Definition 6.8 may be useful. Substitution ς maps possibly open terms in T mentioning unknowns in X, to closed terms in T′. We design ς(X) to be a closed term which mentions unabstracted those atoms that ∆cannot prove are fresh for X. The term-formers from D help us to create a syntax in which to write these terms. The atoms from C help us, where necessary, to place them in the right sort — since according to our sorting system, and consistent with [UPG04], only abstraction can create terms of abstraction sort. We think of d ∈D and cX ∈C as tags.

Definition 6.9

Call a closed term in T′ CD-tagged when for each X : [A]T all occurrences of cX and dX are restricted to subterms [cX]dX(t1, . . . , tkX) where the ti are also CD-tagged.

ς is ∆-consistent:

Lemma 6.10

⊢∆ς is derivable.

Proof

For each a#X ∈ ∆, we need to show ⊢a#ς(X).

Suppose a#X ∈ ∆and X : T. We must prove ⊢a#dX(aX1, . . . , aXkX). By construction aXi#X ∉ ∆for 1 ≤i ≤kX, so a ∉{aX1, . . . , aXkX}, and the result follows.

The case of X : [A]T is similar.End of proof

Now it is not hard to show that ς preserves derivability:

Theorem 6.11

If ∆⊢SUB t = u then ⊢SIMP tς = uς.

Proof

Suppose ∆ ⊢SUB t = u in the syntax of T . Then also ∆ ⊢SUB t = u in the syntax of T′, since T ⊆T′. We obtain ⊢SUB tς = uς by Theorem 2.37, using Lemma 6.10. We conclude ⊢SIMP tς = uς by Lemma 6.5.End of proof

Recall that we fixed ∆, t, and u. Since t and u mention only unknowns from X, tς and uς are closed terms. Then by Lemma 5.30, tς↧→and uς↧→are the SIMPr-normal forms of tς and uς.

Definition 6.12

Let A+ be the set of all atoms mentioned anywhere in the chain of SIMPr-reductions

tς ≡t′ 1 →t′ 2 →. . . →t′ m ≡tς↧→and uς ≡u′ 1 →u′ 2 →. . . →u′ n ≡uς↧→,

extended with a set of fresh atoms B = {bXi | X, i such that aXi ∈A} in bijection with A. Let ∆+ be ∆ enriched with freshness assumptions a′#X for every a′ ∈A+ \ A and every X ∈X.

Without loss of generality we may assume that all terms occurring in the above chains of rewrites are CD-tagged, since the atoms from C that occur in tς and uς are chosen completely fresh (by Definition 6.7), so when rewriting tς and uς to normal form it is not necessary to perform α-renamings on these atoms.

Definition 6.13

We let t′ and u′ range over closed CD-tagged terms in T′ mentioning only atoms in A+ \ B. The importance of these terms is that they include all of the t′ i and u′ i in the two chains of SIMPr-reductions mentioned above.

Define an inverse translation from closed CD-tagged terms in T′ to terms in T , inductively as follows, where we omit ◦ between compositions of swappings for brevity:

a′-1 ≡a′([a′]t′)-1 ≡[a′](t′-1) f(t′ 1, . . . , t′ n)-1 ≡f(t′ 1-1, . . . , t′ n-1) (f ∉D)dX(t′ 1, . . . , t′ kX)-1 ≡((bXkX aXkX) · · · (bX1 aX1) · X)[bX1↦ →t′ 1-1] · · · [bXkX↦ →t′ kX-1] (X : T)dX(t′ 1, . . . , t′ kX)-1 ≡sub(((bXkX aXkX) · · · (bX1 aX1) · X)[bX1↦ →t′ 1-1] · · · [bXkX↦ →t′ kX-1], cX) (X : [A]T)

As a first result, we show that _-1 really is the inverse of ς:

Lemma 6.14

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

Proof

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

The only interesting case is when v ≡π · X. When X : T, we must show

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

Take π′ = (bXkX π(aXkX)) · · · (bX1 π(aX1))(bX1 aX1) · · · (bXkX aXkX). Then the proof obligation follows from

∆+ ⊢SUB π · X = π′ · X

by (ren↦→), since

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

for all i. We can see this as follows: it suffices to show

∆+ ⊢π(aXi)#(bX1 aX1) · · · (bXkX aXkX) · X,

since the π(aXi) are pairwise disjoint and by using the rules for freshnesses. Then there are two possibilities:

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

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

The remaining proof obligation is

∆+ ⊢SUB π · X = π′ · X.

It is convenient to show the stronger property ∆+ ⊢CORE π · X = π′ · X. By the syntactic criteria of Corollary 2.32 it suffices to show that ∆+ ⊢ ds(π, π′)#X. That is, we must show that ∆+ ⊢ ds(π, π′)#X for every a such that π(a) ≠ π′(a). We consider every possible a (every a ∈π and a ∈π′):

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

• a = aXi: then π(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.

The case of X : [A]T is similar except that we additionally need to prove that

∆+ ⊢SUB [cX]sub(π · X, cX) = π · X.

This follows by axiom (η↦→), since ∆+ ⊢cX#π · X.End of proof

Remark 6.15

The reader might wonder why the inverse mapping of the dX renames the atoms aXi to the fresh bXi. Consider for example (aT 1 aT 2) · T in the empty freshness context ∅, so we do not know aT 1#T or aT 2#T. Then

(((aT 1 aT 2) · T)ς)-1 ≡dT(aT 2 aT 1)-1 ≡((bT 2 aT 2)(bT 1 aT 1) · T)[bT 1↦ →aT 2][bT 2↦ →aT 1].

By calculations we can verify Lemma 6.14:

∅+ ⊢SUB ((bT 2 aT 2)(bT 1 aT 1) · T)[bT 1↦ →aT 2][bT 2↦ →aT 1] = (aT 1 aT 2) · T,

where ∅+ = {bT 1#T, bT 2#T, cT #T}. Had we left out the renaming to fresh atoms then (((aT 1 aT 2) · T)ς)-1 would be T[aT 1↦ →aT 2][aT 2↦ →aT 1], which is not equal to (aT 1 aT 2) · T, since for example

⊢SUB ((aT 1 aT 2) · T)[aT 1/T] = aT 2but ⊢SUB (T[aT 1↦ →aT 2][aT 2↦ →aT 1])[aT 1/T] = aT 1.

We now build up towards Theorem 6.20, which is our main result. Recall from Definition 6.13 that t′ and u′ are closed CD-tagged terms in the signature of T′ mentioning only atoms in A+ \ B.

Lemma 6.16

For any a′ ∈A+, if ⊢a′#t′ then ∆+ ⊢a′#t′-1.

Proof

By induction on the structure of t′. We treat the hardest case, namely that of t′ ≡ [cX]dX(t′ 1, . . . , t′ kX). We must show

∆+ ⊢a′#[cX]sub((π · X)[bX1↦ →t′ 1-1] · · · [bXkX↦ →t′ kX-1], cX),

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

• a′ = cX: then the result trivially follows by (#ab).

• a′ = bXj for some j: then bXj#[bXj]((π · X)[bX1↦ →t′ 1-1] · · · [bXj−1↦ →t′ j−1-1]) by (#[]a), and the result follows by the rules of freshness using the inductive hypothesis.

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

End of proof
Lemma 6.17

∆+ ⊢CORE (π · t′)-1 = π · t′-1 when π mentions only atoms from A+ \ (B ∪C).

Proof

By induction on the structure of t′. In the case of t ≡ [cX]dX(t′ 1, . . . , t′ kX) we use the fact that π(b) = b for all b ∈B and π(c) = c for all c ∈C.End of proof

Lemma 6.18

If ⊢CORE t′ = u′ then ∆+ ⊢CORE t′-1 = u′-1.

Proof

By induction on the structure of t′, using the syntactic criteria of Corollary 2.32. The only non-trivial case is when

t′ ≡[a′]v′, u′ ≡[b′]w′, ⊢b′#v′, and ⊢CORE (b′ a′) · v′ = w′.

By Lemma 6.16 we obtain ∆+ ⊢b′#v′-1, and by the inductive hypothesis ∆+ ⊢CORE ((b′ a′) · v′)-1 = w′-1.

We now prove that:

• a′ ∉C and b′ ∉C: Suppose a′ = cX for some cX ∈C. Now t′ is CD-tagged so t′ ≡ [cX]dX(t′ 1, . . . , t′ kX). We have assumed that ⊢CORE t′ = u′ so by the syntactic criteria of Corollary 2.32 it must be that u′ ≡ [cX]dX(u′ 1, . . . , u′ kX) (and ⊢CORE ti = ui for 1 ≤i ≤kX). This is impossible because a′ ≠ b′. We deduce that b′ ∉C in a similar manner.

• a′ ∉B and b′ ∉B: By our assumption in Definition 6.13.

By Lemma 6.17 we obtain ∆+ ⊢CORE ((b′ a′) · v′)-1 = (b′ a′) · v′-1.

By standard reasoning using the rules for freshness and equality we conclude ∆+ ⊢CORE [a′]v′-1 = [b′]w′-1 as required.End of proof

Lemma 6.19

If ⊢SIMPr t′ →u′ then ∆+ ⊢SUB t′-1 = u′-1.

Proof

We work by induction on the derivation of ⊢SIMPr t′ →u′ to show that ∆+ ⊢SUB t′-1 = u′-1 is derivable.

If the derivation concludes in (→[]) or (→f) we may use the inductive hypothesis and extend the derivation with (cong[]) or (congf) respectively.

Suppose the derivation concludes in (→rew). Then there are various cases depending on which rewrite rule is used:

• (Rvar). ∆+ ⊢SUB a′[a′↦ →v′-1] = v′-1 is derivable using axiom (var↦→).

• (Rb). ∆+ ⊢SUB b′[a′↦ →v′-1] = b′ is derivable using axiom (#↦→), since ∆+ ⊢a′#b′.

• (Rf), f ∉D. ∆+ ⊢SUB f(v′ 1-1, . . . , v′ n-1)[a′↦ →v′-1] = f(v′ 1-1[a′↦ →v′-1], . . . , v′ n-1[a′↦ →v′-1]) is derivable using axiom (f↦→).

• (Rf), f ∈D. In case X : T, we must show

∆+ ⊢SUB (π · X)[bX1↦ →v′ 1-1] · · · [bXkX↦ →v′ kX-1][a′↦ →v′-1] =(π · X)[bX1↦ →v′ 1-1[a′↦ →v′-1]] · · · [bXkX↦ →v′ kX-1[a′↦ →v′-1]],

where π = (bXkX aXkX) · · · (bX1 aX1). Since bXi ∉v′ for all i, we know ⊢bXi#v′. Then also ∆+ ⊢bXi#v′-1 by Lemma 6.16. Now we apply part 4 of Lemma 6.2, such that the left-hand-side of the proof obligation is SUB-equal to

(π · X)[a′↦ →v′-1][bX1↦ →v′ 1-1[a′↦ →v′-1]] · · · [bXkX↦ →v′ kX-1[a′↦ →v′-1]].

By the rules for equality, this is equal to the right-hand-side of the proof obligation when

∆+ ⊢SUB (π · X)[a′↦ →v′-1] = π · X.

By axiom (#↦→) this is when ∆+ ⊢a′#π · X, i.e. when π-1(a′)#X ∈∆+. There are two possibilities:

– a′ = aXi for some i: then π-1(a′) = bXi, and bXi#X ∈∆+ by definition.

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

The result follows.

The case of X : [A]T is similar.

• (Rabs). Suppose ⊢c#v′. Then ∆+ ⊢c#v′-1 by Lemma 6.16. By (axabs↦→), we obtain

∆+ ⊢SUB ([c]w′-1)[a′↦ →v′-1] = [c](w′-1[a′↦ →v′-1])

as required.

The result follows.End of proof

Theorem 6.20

∆⊢SUB t = u if and only if ⊢SIMP tς = uς.

Proof

The left-to-right part is Theorem 6.11.

For the right-to-left part, suppose that ⊢SIMP tς = uς. We have observed that there are SIMPr rewrites

tς ≡t1 →t2 →. . . →tm ≡tς↧→ and uς ≡u1 →u2 →. . . →un ≡uς↧→.

Then by Lemma 6.19, we know

∆+ ⊢SUB (tς)-1 ≡t-1 1 = t-1 2 = . . . = t-1 m ≡ (tς↧→)-1 and ∆+ ⊢SUB (uς)-1 ≡u-1 1 = u-1 2 = . . . = u-1 n ≡ (uς↧→)-1,

so ∆+ ⊢SUB (tς)-1 = (tς↧→)-1 and ∆+ ⊢SUB (uς)-1 = (uς↧→)-1 by transitivity.

We supposed that ⊢SIMP tς = uς so by Corollary 5.20 it must be that ⊢CORE tς↧→= uς↧→. By Lemma 6.18 also ∆+ ⊢CORE (tς↧→)-1 = (uς↧→)-1.

Then ∆+ ⊢SUB (tς)-1 = (uς)-1 using symmetry and transitivity. By Lemma 6.14 then also ∆+ ⊢SUB t = u. Since ∆+ extends ∆with atoms not in t, u, we conclude ∆ ⊢SUB t = u using (fr).End of proof

As a simple corollary of Theorem 6.20, we obtain decidability of SUB.

Corollary 6.21 (Decidability of SUB).

It is decidable whether ∆ ⊢SUB t = u.

Proof

By Theorem 6.20, ∆⊢SUB t = u is equivalent to ⊢SIMP tς = uς. By Theorem 5.32, this is decidable.End of proof

Combining Theorem 6.20 and Corollary 5.20, we extract the following algorithm that decides whether ∆⊢SUB t = u:

1. Map possibly open terms t and u to closed terms tς and uς.

2. Evaluate tς↧→and uς↧→.

3. Check whether ⊢CORE tς↧→= uς↧→using the syntactic criteria of Corollary 2.32.

We can extract a witnessing derivation in SUB of ∆⊢SUB t = u from the algorithm above: the meat of work is done in the proofs of Lemma 6.19 and Lemma 6.14.

By a similar method to the one we used to prove Theorem 6.20 we can prove conservativity of SUB over CORE. We use the notation and machinery of this subsection in the following proof:

Theorem 6.22 (Conservativity of SUB).

Suppose that t and u do not mention term-former sub. Then

∆⊢SUB t = u if and only if ∆⊢CORE t = u.

Proof

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

Now suppose that ∆ ⊢SUB t = u. We take a suitably chosen enriched signature and suitably chosen ς, as in the proofs above. By Theorem 6.11, ⊢SIMP tς = uς. By construction tς and uς do not mention sub, therefore by Corollary 5.19 also ⊢CORE tς = uς.

Given the derivability of ⊢CORE tς = uς we can prove the derivability of ∆ ⊢CORE t = u by exploiting the syntactic criteria of Corollary 2.32. The proof is by induction on t using detailed but entirely routine calculations. We consider just one case, the hardest one:

Suppose t ≡π · X and X : [A]T. Then

tς ≡[cX]dX(π(aX1), . . . , π(aXkX)).

By the syntactic criteria of Corollary 2.32 if ⊢CORE tς = uς it must be that

uς ≡[b]dX(π(aX1), . . . , π(aXkX)).

Here b is not equal to π(aXi) for 1 ≤i ≤kX. 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.End of proof

6.3. ω-completeness

We consider completeness with respect to the ground term model (see Definition 6.23 below for a formal definition). This is also called ω-completeness. Before we go into the proof of ω-completeness, it is useful to mention why this is an appropriate notion to consider.

Nominal algebra enjoys a general completeness result [GM07] with respect to a standard class of semantics in nominal sets [GP02]. SUB is a nominal algebra theory, so it is automatically sound and complete with respect to the standard class of nominal sets semantics.

A completeness result is weaker, the larger the class of semantics that it uses. Can we strengthen this general result to some more specific class than the nominal sets models?

Theorem 6.20 can be read as a completeness result with respect to a class of models built out of syntax enriched with finitely but unboundedly many extra term-formers dX. We could stop there, however, we would have an even more powerful completeness result if we could strengthen this to completeness with respect to terms of substitution signature T itself.

In fact, so long as T contains a term-former which takes more than one argument (like app or plus), then we can nail SUB down to the theory of capture-avoiding substitution on ground terms of T . We now have all the machinery we need to do this quite easily:

Definition 6.23

Call σ a ground substitution for ∆, t and u when for every unknown X in ∆, t, and u, σ(X) is a ground term (it mentions no unknowns and does not mention sub).

Call SUB ω-complete when for all ∆, t and u, if tσ↧→=α uσ↧→for all ∆-consistent ground substitutions σ (for ∆, t and u), then ∆ ⊢SUB t = u.

We shall prove the contrapositive. Supposing ∆ ⊬SUB t = u, we will exhibit some ∆-consistent ground substitution σ such that tσ↧→≠α uσ↧→.

We cannot use ς from Definition 6.8 because ς maps to an extended signature T′ with extra term-formers dX. But we can use ς to construct another substitution with the right properties, as we now see.

Recall from the previous subsection the chain of rewrites

tς ≡t′ 1 →t′ 2 →. . . →t′ m ≡tς↧→and uς ≡u′ 1 →u′ 2 →. . . →u′ n ≡uς↧→.

Note that tς↧→and uς↧→are ground.

Definition 6.24

Let A′ be the set of all atoms mentioned in the above chains, let t′ and u′ range over closed terms in T′ mentioning only atoms from A′, and choose atoms {aX | X ∈X} completely fresh from A′.

Assuming that T contains a binary term-former, say pair : (T, T)T), define a translation -∗ from closed terms in T′ to closed terms in T by:

a′∗≡a′([a′]t′)∗≡[a′]t′∗f(t′ 1, . . . , t′ n)∗≡f(t′∗ 1 , . . . , t′∗ n ) (f ∉D)dX()∗≡pair(aX, aX) dX(t′ 1)∗≡pair(aX, t′∗ 1 )dX(t′ 1, . . . , t′ kX)∗≡pair(aX, pair(t′∗ 1 , pair(t′∗ 2 , . . . , pair(t′∗ kX−1, t′∗ kX)))) (kX > 1)

It is not hard to verify the following properties:

Lemma 6.25

1. ⊢ (t′∗)↧→≡ (t′↧→)∗.

2. ⊢CORE t′ = u′ if and only if ⊢CORE t′∗= u′∗.

3. ⊢SIMP t′ = u′ if and only if ⊢SIMP t′∗= u′∗.

Proof

Part 1 is by induction on the syntax of t′. For the case of t′ ≡ sub(u′, v′), we use the property that g′[h′/a′]∗≡g′∗[h′∗/a′] (where g′, h′, a′ and g′[h′/a′] mention only atoms from A′), which is easy to verify.

Part 2 is by induction on the syntax of t′, using the syntactic criteria from Corollary 2.32.

For part 3, by Corollary 5.20 it suffices to prove the equivalent

⊢CORE t′↧→= u′↧→if and only if ⊢CORE (t′∗)↧→= (u′∗)↧→,

which follows by parts 1 and 2.End of proof

Definition 6.26

Define the substitution ς∗ by:

ς∗(X) = ς(X)∗(X ∈X),ς∗(Y ) = Y (Y ∉X).

It is a fact of the construction that ς∗ maps every X appearing in ∆, t, or u, to a ground term in T . This is morally ‘the same’ as ς(X), but we map each extra term-former dX to a collection of instances of pair.

Lemma 6.27

If v is a subterm of t or v is a subterm of u, v(ς∗) ≡ (vς)∗.

Proof

By an easy induction on the structure of v.End of proof

Corollary 6.28

⊢SIMP tς = uς if and only if ⊢SIMP t(ς∗) = u(ς∗).

Proof

By Lemma 6.27 and part 3 of Lemma 6.25.End of proof

Theorem 6.29

SUB is ω-complete.

Proof

We show that if ∆ ⊬SUB t = u then there exists a ∆-consistent ground substitution σ (for ∆, t and u) such that tσ↧→≠α uσ↧→.

Suppose ∆ ⊬SUB t = u. Then also⊬SIMP tς = uς by Theorem 6.20. Now ⊬SIMP t(ς∗) = u(ς∗) by Corollary 6.28. Then we obtain (tς∗)↧→≠α (uς∗)↧→ by Theorem 3.9 and Corollary 5.20.

Now take σ = ς∗. Since ς∗ maps to ground terms in T , the result follows.End of proof

6.4. Restricting the sort system

We now turn to our discussion in Subsection 2.1 on unknowns of abstraction sort [A]T and term-formers sub : ([A][A]T, T)[A]T (Remark 2.10). We mentioned that they are convenient, but not strictly necessary.

To see what precisely we mean by this, we consider a typical signature for languages with binding, namely that of the lambda calculus (see Examples 2.6 and 2.8).

Definition 6.30

Consider the following signature:

app : (T, T)T lam : ([A]T)T sub : ([A]T, T)T.

Let theory SUB′ over this signature have axioms

(var↦→′) ⊢ a[a↦ →T] = T(#↦→′) a#U ⊢ U[a↦ →T] = U(app↦→′) ⊢app(U, V )[a↦ →T] = app(U[a↦ →T], V [a↦ →T])(lam↦→′) b#T ⊢lam([b]U)[a↦ →T] = lam([b](U[a↦ →T]))(sub↦→′) b#T ⊢V [b↦ →U][a↦ →T] = V [a↦ →T][b↦ →U[a↦ →T]](ren↦→′) b#T ⊢ T[a↦ →b] = (b a) · T.
Theorem 6.31

Suppose SUB is the theory of substitution over the signature of the lambda calculus from Example 2.8. Then for any ∆, t and u (in this signature) not mentioning unknowns of sort [A]T or terms of sort [A][A]T:

∆⊢SUB t = u if and only if ∆⊢SUB′ t = u.

Proof

For the right-to-left part it suffices to show that each axiom of SUB′ can be derived in SUB. Both axiom (lam↦→′) and (sub↦→′) follow by an instance of (f↦→) and (#↦→), the other axioms of SUB′ follow direclty from their corresponding axioms in SUB.

For the left-to-right part, suppose ∆ ⊢SUB t = u. Then also ⊢SIMP tς = uς by Theorem 6.11. We observe that there are SIMPr rewrites

tς ≡t1 →t2 →. . . →tm ≡tς↧→and uς ≡u1 →u2 →. . . →un ≡uς↧→,

such that whenever a term of sort [A][A]T is introduced by a rewrite, it is removed in the next step. More precisely, only an application of rewrite rule (Rf), where f = lam, can introduce such a term, but we can always apply the (Rabs) rule to get rid of it.

We can use properties similar to Lemma 6.19 on these chains of rewrites to obtain derivations of

∆+ ⊢SUB′ (tς)-1 = (tς↧→)-1 and ∆+ ⊢SUB′ (uς)-1 = (uς↧→)-1.

That is, we need one such property for direct rewrites and another one for two-step rewrites. The inverse translation never introduces unknowns of sort [A]T or terms of sort [A][A]T.

We also have ∆+ ⊢CORE (tς↧→)-1 = (uς↧→)-1 by Corollary 5.20, Lemma 6.18 and our assumption ⊢SIMP tς = uς. Then ∆+ ⊢SUB (tς)-1 = (uς)-1 using (symm) and (tran). Using a property similar to Lemma 6.14 we obtain ∆+ ⊢SUB′ t = u. We conclude ∆ ⊢SUB′ t = u using (fr).End of proof

The presentation of theory SUB′ is somewhat more specific and longer than SUB, since we cannot use a meta-variable f to range over term-formers. For this reason we preferred SUB in this paper.

7. Related work and conclusions

Substitution underlies the quantifiers in predicate logics and the λ-binder of the λ-calculus . . . and lots more besides. Quantification and binding are central features of these systems. This paper discusses their common denominator, substitution.

Future work using nominal techniques seems likely to require an axiomatisation of substitution within the nominal style. This paper provides that, and proves a precise sense in which that axiomatisation can be considered the right one, namely soundness and completeness with respect to a canonical term model (Theorem 6.29). It also provides a precise sense in which that axiomatisation can be considered tractable, namely decidability of equality up to the axioms for substitution.

Crabbé [Cra04b, Cra04a] axiomatises substitution much like us and shares (in our terminology) atoms and freshness conditions. However, his axiomatisation is not capture-avoiding from the simple fact that he does not treat binding: ‘. . . we are not concerned with the notion of bound variable’ [Cra04a, page 2].

Feldman [Fel82] gives an algebraic axiomatisation inspired by a concrete model of functions/evaluations. His axioms are closer in spirit to Cylindric Algebras [BS81] and Lambda Abstraction Algebras [LS04, Sal00]. The three approaches share an infinity of term-formers which are ‘morally’ precisely λ[a], -[a↦ → -], and ∃[a]. We see the advantage of our treatment as systematising and formalising precisely what rôle the atoms really have. In any case the approaches above cannot directly express (ren↦→), (#↦→), and (abs↦→), even though instantiations are derivable for closed terms by calculations parametric over their specific structure.

Combinatory Algebra (CA) [Bar84] and related systems implement substitution by ‘pipes’ (e.g. the translation of λ-terms into CA [Bar84]). There is no native notion of binder, nor of capture-avoidance. General truths such as (#↦→) are not provable as equalities between combinators, though they remain true and can be proved informally by calculations parametric over specific structure.

Lescanne’s classic survey [Les94] and the thesis of Bloo [Blo97] chart a vast literature on λ-calculi with explicit substitutions. These decompose β-reduction as a rule to introduce explicit substitution ( (λa.u)t → u[a↦ →t] ), and explicit rules for that substitution’s subsequent behaviour (which is to substitute, of course). These calculi are designed to measure the cost of a β-reduction (in an implementation, which may be based on de Bruijn indexes [dB72] or on named variable symbols). They do not axiomatise substitution, they implement it. For example, ‘confluence’ is a typical correctness criterion for a calculus, and ‘ω-completeness’ is not.

Sun has investigated Binding Algebras [Sun99]. As far as we understand, binding algebras implement binding in the style of higher-order or first-order logic — using variables and binders — but without committing to a functional semantics or to higher orders. Put another way, binding algebra enriches the language of algebra with binding, substitution, and α-conversion — but leaves out λ-abstraction and β-conversion. (This has much in common with Binding Logic [DHK02], which does something very similar to first-order logic; neither thread of research cites the other so they appear to have developed independently.)

Nominal algebra is in this spirit. In fact it does not commit to substitution, but by design SUB does and SUB is the topic of this paper. We note that in Sun’s work that every variable must be explicitly accounted for in some binder or some evaluation, some where. That is, variables have no independent denotational existence analogous to that of the atoms in nominal sets. Our best guess is that binding algebras correspond, in our world, to elements with empty support of models of SUB. We do not intend to investigate a connection with binding algebra but we do plan to consider binding logic.

There is a close connection between nominal sets [GP02] and categories of presheaves used in another thread of work [FT01, FPT99, TP05]. This uses ideas from categorical algebra [LS86] and applies presheaves to give just enough extra structure to model names and name-binding. Nominal sets, the canonical semantics for nominal terms, are the Schanuel topos; they can be viewed as a category of pullback-preserving presheaves. Being pullback-preserving (to be more precise, preserving pullbacks of pairs of monos) does not correspond to having finite support — it corresponds, in the terminology of nominal techniques, to assuming a unique least supporting set. This is not a vital assumption, but without a unique least supporting set, the freshness judgement a#X of nominal terms is meaningless in its current form. It is not clear how [FT01, FPT99, TP05] would give a direct semantics to nominal terms. Thus an easy and direct connection cannot be made at the moment.

A direct connection could be made by relating the general class of models of substitution determined by SUB (which we do not consider in this paper) with the classes of models in presheaves — or alternatively, if the work based on presheaves could include a completeness result for some canonical model (which to our knowledge has not yet been done); this could then be conveniently compared to the ground term model of SUB. Since our models would be in nominal sets and would have unique least supporting sets, and the presheaf models do not, our best guess is that a canonical model for the presheaf work, if it exists, would be a ‘ground term model enriched with non-unique least supporting sets’. It remains to make that formal, and non-syntactic models of SUB remain to be investigated.

There is much possible and interesting future work:

Decidability of unification up to SUB, the axioms for substitution, remains an open problem. Nominal unification [UPG04] (in our terminology, unification of nominal terms up to CORE) is decidable. Nominal unification is to be compared with higher-order patterns [Mil91]. We suggest that unification up to SUB is to be compared with higher-order unification [Hue02], and the technique of Huet’s algorithm could perhaps be imported.

There is no obstacle to taking SUB over itself — that is, to taking what we write in this paper as, say, (X[a↦ →Y])[t/X] and expressing it in a stronger axiom system as (X[a↦ →Y])[X↦ →T] where T is a ‘stronger’ meta-variable. This relates directly to the Lambda-Context Calculus [GL07] and Hierarchical Nominal Rewriting [Gab07] both of which feature hierarchies of ‘increasingly meta-’variables plus operational notions of semantics for substituting those variables.

Finally, SUB is just an axiom system and it has interesting non-syntactic models. Exploring them is current research, and we hope it will be possible to exploit those models to design interesting new classes of logics and lambda-calculi.

References

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

[Blo97]Roel Bloo. Preservation of Termination for Explicit Substitution. PhD thesis, Eindhoven University of Technology, Eindhoven, 1997.

[BR95]Roel Bloo and Kristoffer Høgsbro Rose. Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection. In CSN-95: Computing Science in the Netherlands, pages 62–72, Amsterdam, 1995. Stichting Mathematisch Centrum.

[BS81]S. Burris and H. Sankappanavar. A Course in Universal Algebra. Springer, Berlin, 1981.

[Cra04a]Marcel Crabbé. On the notion of substitution. Logic Journal of the IGPL, 12(2):111–124, 2004.

[Cra04b]Marcel Crabbé. Une axiomatisation de la substitution. Comptes rendus de l’Académie des Sciences de Paris, Série I, 338:433–436, 2004.

[dB72]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.

[DHK02]Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Binding logic: proofs and models. In LPAR’02: 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, volume 2514 of LNCS, pages 130–144, Berlin, 2002. Springer.

[Fel82]Norman Feldman. Axiomatization of polynomial substitution algebras. Journal of Symbolic Logic, 47(3):481–492, 1982.

[FG07]Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205:917–965, 2007.

[FPT99]Marcelo Fiore, Gordon Plotkin, and Daniele Turi. Abstract syntax and variable binding. In 14th Annual Symposium on Logic in Computer Science, pages 193–202, Brussels, 1999. IEEE Computer Society Press.

[FT01]Marcelo Fiore and Daniele Turi. Semantics of name and value passing. In 16th Annual Symposium on Logic in Computer Science, pages 93–104, Los Alamitos, 2001. IEEE Computer Society Press.

[Gab07]Murdoch J. Gabbay. Hierarchical nominal terms and their theory of rewriting. ENTCS, 174(5):37–52, 2007.

[GL07]Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. In LFMTP’07: International Workshop on Logical Frameworks and Meta-Languages, to be published in ENTCS, 2007.

[GM06a]Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding substitution as a nominal algebra. In Theoretical Aspects of Computing: ICTAC 2006, volume 4281 of LNCS, pages 198–212, Berlin, 2006. Springer.

[GM06b]Murdoch J. Gabbay and Aad Mathijssen. Nominal algebra. Technical Report HW-MACS-TR-0045, Heriot-Watt, 2006.

[GM06c]Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order logic. In PPDP’06: Proc. of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, pages 189–200, New York, 2006. ACM Press.

[GM07]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 LNCS, pages 162–176, Berlin, 2007. Springer.

[GP02]Murdoch J. Gabbay and Andrew M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2002.

[Hod01]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 Academic, Dordrecht, 2001.

[Hue02]Gérard Huet. Higher order unification 30 years later. In TPHOLs 2002: Theorem Proving in Higher Order Logics, number 2410 in LNCS, pages 241–258, Berlin, 2002. Springer.

[KvOvR93] Jan Willem Klop, Vincent van Oostrom, and Femke van Raamsdonk. Combinatory reduction systems, introduction and survey. Theoretical Computer Science, 121:279–308, 1993.

[Les94]Pierre Lescanne. From λσ to λυ a journey through calculi of explicit substitutions. In POPL’94: Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 60–69, New York, 1994. ACM Press.

[LS86]J. Lambek and P.J. Scott. Introduction to Higher Order Categorical Logic. Cambridge University Press, Cambridge, 1986.

[LS04]Stefania Lusin and Antonino Salibra. The lattice of lambda theories. Journal of Logic and Computation, 14(3):373–394, 2004.

[Mil91]Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Extensions of Logic Programming, 475:253–281, 1991.

[MN98]Richard Mayr and Tobias Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.

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

[Sun99]Yong Sun. An algebraic generalization of Frege structures - binding algebras. Theoretical Computer Science, 211:189–232, 1999.

[TP05]Miki Tanaka and John Power. A unified category-theoretic formulation of typed binding signatures. In MERLIN’05: Proc. of the ACM SIGPLAN workshop on mechanized reasoning about languages with variable binding, pages 13–24, New York, 2005. ACM Press.

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

Notes

1 Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands ↩

Correspondence and offprint requests to: Murdoch J. Gabbay, www.gabbay.org.uk