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

Capture-Avoiding Substitution as a Nominal Algebra

Murdoch J. Gabbay1 and Aad Mathijssen2

1 School of Mathematical and Computer Sciences, Heriot-Watt University, Edinburgh EH14 4AS, Scotland, Great Britain

murdoch.gabbay@gmail.com

2 Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

A.H.J.Mathijssen@tue.nl

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 turn out to be hard and 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.

Table of Contents

Capture-Avoiding Substitution as a Nominal Algebra 1

Murdoch J. Gabbay and Aad Mathijssen

1 Introduction. 3

1.1 Answers to questions and map of the paper 4

1.2 Relation with the conference version 5

2 Nominal algebra 5

2.1 The syntax of nominal terms. 5

2.2 Permutation, substitution and freshness 8

2.3 Equality 12

2.4 Axioms and theories 13

3 Equality and inequality of raw nominal terms. 15

4 Substitution on ground terms. 18

5 The theory SIMP; simply substitution 24

6 Substitution on open terms using SIMP 28

6.1 Nominal rewriting 28

6.2 SIMPr: explicit substitution rewritten 31

6.3 Confluence, conservativity and consistency 32

6.4 Failure of completeness for SIMP with respect to unknowns. 34

6.5 Strong normalisation and decidability 34

7 Substitution on open terms using SUB 36

7.1 Soundness and the relation with SIMP 37

7.2 Decidability 39

7.3 ω-completeness . 45

7.4 Restricting the sort system 47

8 Related work and conclusions. 48

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

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)

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 (given formal meaning in the rest of this paper). Informally, the axioms express the following:

(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
Fig. 1. Axioms of SUB

(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 holds (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 [2], though sub is not atoms-concretion. More on this in Subsection 1.2.

Formally, Figure 1 uses nominal terms [3] as a syntax, and nominal algebra [4, 5] 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 considers α-equality and α-inequality of nominal terms. Section 4 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 5 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 6 proves useful properties of the simple axiomatisation; here we make heavy use of techniques from (nominal) rewriting.

Section 7 explores the stronger axioms (Figure 1) formally as a nominal algebra theory. Decidability of the stronger axioms is proved in Subsection 7.2, and completeness is proved in Subsection 7.3 relative to the concrete model from section 4. This answers question (2) above and completes the proof that Figure 1 does represent substitution. Finally, Subsection 7.4 shows how the general axiomatisation of SUB relates to a more concrete axiomatisation.

In other work in preparation, the first author shows how Fraenkel-Mostowski set theory (the underlying model of nominal techniques) [2] 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 [4, 6] 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 [7]. 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 6.25. SIMP can be identified with the usual definition of capture-avoiding substitution.

We give a procedure for converting equalities SUB into equivalent (in a suitable sense) equalities in SIMP over an extended signature (see Subsection 7.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 7.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 [7]). 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 Remark 2.9 and Subsection 7.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 [3, 8].

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 [6]) 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, . . ..3 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 an arity (τ1, . . . , τn)τ is associated. We may write f : (τ1, . . . , τn)τ for f which has arity (τ1, . . . , τn)τ. We call a collection of term-formers a signature.

Definition 2.3

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. Important: we do not quotient terms in any way.

Definition 2.4

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.5 (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(e′ 1, e′ 2) (λ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.6

We call a signature T a substitution signature when:

– it 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 ∈T , sorting arities are of the form (τ1, . . . , τn)T, where τi ∈{T, [A]T}, 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.7 (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.8 (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.9

Unknowns of sort [A]T, and term-former sub : ([A][A]T, T)[A]T, are convenient but not necessary; see SUB′ in Subsection 7.4.

Remark 2.10

The signature is arbitrary and may be empty (aside from sub), except that Theorem 7.27 (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 7.18 (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.11

A permutation is a 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.12

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.13

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

Proof

By an easy induction on the structure of t. ⊓⊔

Definition 2.14

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, with 1 ≤i ≤n.

Definition 2.15

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’.

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 [3, 8]:

Lemma 2.16

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

Proof

By straightforward induction on the structure of t. ⊓⊔

Definition 2.17

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 ∆ for a (possibly infinite) set of primitive freshnesses and call it a freshness context.

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.18

Define derivability on freshnesses in natural deduction style [9] 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 non-empty permutations, i.e. π ≠ Id.4

– 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.

Definition 2.19

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.

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

For example, in the substitution signature for the lambda calculus (Example 2.7), 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) a#[a]Y (#f ) a#X a#lam([a]Y ) (#f ) a#app(X, lam([a]Y ))

The derivation rules are completely syntax-directed. This implies that the rules also hold in the opposite direction:

Lemma 2.20

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 all i, 1 ≤i ≤n.

Proof

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

⊓⊔

In freshness judgements, the freshnesses context ∆ may be weakened:

Lemma 2.21

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

Proof

By an easy induction on the structure of the derivation rules. ⊓⊔

Sometimes the freshness contexts ∆ may also be strengthened. We need some terminology in order to state this.

Definition 2.22

Let ∆′ and ∆ be freshness contexts, and S be a set of terms. Say that ∆′ freshly extends ∆ with atoms not in S when ∆⊆∆′ and a ∉∆, S for each a#X ∈∆′ \ ∆. If S is empty we just say that ∆′ freshly extends ∆.

For example:

– b#X, a#X freshly extends a#X.

– b#X, a#X freshly extends a#X with atoms not in a.

– b#X, a#X does not freshly extend a#X with atoms not in b.

– a#Y, a#X does not freshly extend a#X.

Lemma 2.23

If ∆′ ⊢a#t and ∆′ freshly extends ∆ with atoms not in a, t, then ∆⊢a#t.

Proof

We inductively transform a derivation of ∆′ ⊢a#t to a derivation of ∆⊢a#t:

– If ∆′ ⊢a#X by assumption, then a#X ∈∆′. We proceed by case distinction:

• If a#X ∈∆, then ∆⊢a#X by assumption.

• If a#X ∈∆′ \ ∆, then a ∈∆, a, X, so a#X does not freshly extend ∆ with respect to a, X and there is nothing to prove.

– (#X): Suppose ∆′ ⊢a#π · X, π ≠ Id, is derived using (#X) and ∆′ freshly extends ∆ with atoms not in a, π · X. Then ∆′ ⊢π-1(a)#X by assumption and ∆′ freshly extends ∆ with atoms not in π-1(a), X. By the inductive hypothesis ∆⊢π-1(a)#X, and by (#X) we conclude ∆⊢a#π · X.

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

– (#[]b) and (#f) are straightforward using the inductive hypothesis and the facts that a ∉ [b]t implies a ∉t and that a ∉ f(t1, . . . , tn) implies a ∉ti for all i.

⊓⊔

We can generalise the permutation of terms to freshnesses as follows:

Lemma 2.24

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

Proof

By an easy induction on freshness derivations (Figure 2). The only non-trivial case is (#X). Suppose a#π′ · X is derived from π′-1(a)#X using (#X), where π′ ≠ Id. Then we need to show π(a)#π · (π′ · X). By Lemma 2.13, this is equivalent to π(a)#(π ◦π′) · X.

We continue by case distinction. Suppose π ◦π′ = Id. Then the proof obligation is equivalent to the assumption π′-1(a)#X, since π = π′-1 by basic properties of permutations.5 The result follows.

If π ◦π′ ≠ Id by (#X) the proof obligation follows from (π ◦π′)-1(π(a))#X. Since (π ◦π′)-1(π(a)) = π′-1(a), this is equivalent to the assumption π′-1(a)#X, and again the result follows. ⊓⊔

Definition 2.25

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

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

We can generalise substitution of terms to freshnesses as follows:

Theorem 2.26

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.24. ⊓⊔

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.27

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.

(refl) t = t t = u (symm) u = t t = u u = v (tran) t = v t = u (cong[]) [a]t = [a]u t = u (congf ) f(t1, . . . , t, . . . , tn) = f(t1, . . . , u, . . . , tn) a#t b#t (perm) (a b) · t = t [a#X1, . . . , a#Xn] ∆ · · · t = u (fr) (a ∉ t, u, ∆) t = u
Fig. 3. Derivation rules for nominal equality

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.6 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 (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.28

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

(#ab) a#b (#[]b) (#[]a) a#[b]b 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.7),

⊢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:

b#X (#[]a) (#[]b) a#[a]X 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 )

⊓⊔

In Section 3 we will prove that derivability in CORE is α-equivalence in a formal sense, also on open terms.

2.4 Axioms and theories

Nominal Algebra is the theory of freshness and equality outlined above, along with the ability to impose axioms on terms:

Definition 2.30

Call a triple ∇⊢t = u where ∇ is a finite freshness context, an axiom. We may write ⊢t = u when 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 4. Here π ranges over permutations and σ ranges over substitutions. Recall that we write ∇σ for {a#σ(X) | a#X ∈∇}.

∇σ (ax∇ ⊢ t=u) π · tσ = π · uσ
Fig. 4. The axiom rule

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.24: ∆⊢∇σ iff ∆⊢π · ∇σ for any ∆.

Definition 2.31

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. For instance we can weaken the freshnesses context ∆ in equational judgments:

Lemma 2.32

If ∆⊢T t = u and ∆⊆∆′ then ∆′ ⊢T t = u.

Proof

By an easy induction on the structure of the derivation rules. ⊓⊔

We may strengthen the freshness context ∆, since the rule (fr) precisely introduces a ‘∆′ freshly extending ∆ with atoms not in t, u’ in equational derivations:

Lemma 2.33

If ∆′ ⊢T t = u and ∆′ freshly extends ∆ with atoms not in t, u, then ∆⊢T t = u.

Proof

We extend the derivation with (fr). ⊓⊔

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

Lemma 2.34

For any π, if ∆⊢T t = u then ∆⊢T π · t = π · u.

Proof

By induction on the structure of the rules of Figures 3 and 4. ⊓⊔

Theorem 2.35

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

Proof

Analogous to the proof of Theorem 2.26. ⊓⊔

3 Equality and inequality of raw nominal terms

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 3.5).

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

– 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.

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 [3] (we still need nominal algebra so we can extend CORE and study theories with more axioms, like SUB).

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

Definition 3.1

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 5. 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(π, π′).

(Ax) a ≈∆ a ∆ ⊢ ds(π′, π)#X (Ds) π · X ≈∆ π′ · X t1 ≈∆ 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
Fig. 5. Syntax-directed rules for CORE

Syntax-directed equality _≈∆_ is transitive:

Lemma 3.2

If t ≈∆u and u ≈∆v then t ≈∆v.

Proof

By induction on the size of t (we do not count permutations in the size). For each t we exploit the syntax-directed nature of the rules of Figure 5 to determine the possibilities for u and v.

For the abstraction case t ≡ [a]t′ we need the following properties:

– If t ≈∆u then π · t ≈∆π · u. This follows by induction on the structure of derivations of t ≈∆u.

– If ∆⊢ ds(π, π′)#t then π · t ≈∆π′ · t. By induction on the structure of t.

– If t ≈∆u then ∆⊢a#t if and only if ∆⊢a#u. By induction on the structure of t.

Full details can be found in the proof of [8, Lemma 23(2)]. ⊓⊔

We use Lemma 3.2 to show that CORE is equivalent to the syntax-directed equality of Figure 5.

Theorem 3.3

∆⊢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 routine induction on the structure of Nominal algebra derivations of ∆⊢CORE t = u. By the inductive hypothesis it suffices to show:

– t ≈∆t (is derivable). This follows by an easy induction on the structure of t.

– If t ≈∆u then u ≈∆t. By induction on derivations of t ≈∆u. Except for (Absab), all cases are trivial using the inductive hypothesis, since they are symmetric. For the remaining case, we need to show [b]u ≈∆ [a]t. By Lemma 3.2, this follows from

[b]u ≈∆[b](b a) · t and [b](b a) · t ≈∆[a]t.

By (Absaa) [b]u ≈∆ [b](b a) · t follows from u ≈∆ (b a) · t; by the inductive hypothesis this follows from the assumption (b a) · t ≈∆u. By (Absab) [b](b a) · t ≈∆ [a]t follows from t ≈∆t and ∆⊢a#(b a) · t. We have already shown t ≈∆t. Finally ∆⊢a#(b a) · t follows from the assumption ∆⊢b#t by Lemma 2.24.

– If t ≈∆u and u ≈∆v then t ≈∆v. This is Lemma 3.2.

– If t ≈∆u then [a]t ≈∆ [a]u. This is (Absaa).

– If t ≈∆u then f(t1, . . . , t, . . . , tn) ≈∆ f(t1, . . . , u, . . . , tn). This is an instance of (F), using the fact that ti ≈∆ti for all i.

– if ∆⊢a, b#t then (a b) · t ≈∆t. By an easy induction on the structure of t.

– if t ≈∆,a#X1,...,a#Xn u where a ∉t, u, ∆ then t ≈∆u. By an easy induction the structure of derivations of t ≈∆,a#X1,...,a#Xn u. The case of (Absab) uses Lemma 2.23 to strengthen the assumption ∆, a#X1, . . . , a#Xn ⊢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:

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

The following proof obligations remain:

1. π · X = (π(a) π′(a)) · π′ · X follows from ds(π, (π(a) π′(a)) ◦π′)#X, by Lemma 2.13 and the inductive hypothesis, provided

|ds(π, (π(a) π′(a)) ◦π′)| < |ds(π, π′)|.

This condition is satisfied since ds(π, (π(a) π′(a)) ◦π′) = ds(π, π′) \ {a}. Finally, the remaining proof obligation ds(π, (π(a) π′(a)) ◦π′)#X follows from assumption ds(π, π′)#X.

2. π(a)#π′ · X follows from π′-1(π(a))#X by Lemma 2.24. This follows from assumptions ds(π, π′)#X, if π′-1(π(a)) ∈ ds(π, π′). That is, when π(π′-1((π(a))) ≠ π(a). This is the case, since we assumed π(a) ≠ π′(a) and because ̸ ≠ is invariant under permutation.

3. π′(a)#π′ · X follows from a#X, by Lemma 2.24. This follows directly from assumption ds(π, π′)#X, since a ∈ ds(π, π′).

– If ∆⊢CORE ti = ui for i, 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 a derivation of ∆⊢CORE [a]t = [b]u is:

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

⊓⊔

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

Corollary 3.4 (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 (that is, ∆⊢a#X for every a such that π(a) ≠ π′(a)).

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 i, 1 ≤i ≤n.

Proof

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

Corollary 3.5 (Consistency of CORE).

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

Proof

By Corollary 3.4, ∆⊢CORE a = b is never derivable. ⊓⊔

A technical corollary will also be useful later and has a simple proof using Corollary 3.4:

Corollary 3.6

If ∆⊢CORE t = u then ∆⊢a#t if and only if ∆⊢a#u.

Proof

By an easy induction on t using concrete calculations and the syntactic criteria of Corollary 3.4. ⊓⊔

4 Substitution on ground terms

Definition 4.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(g, . . . , g),

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 4.2

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

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

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

Proof

By induction on g. ⊓⊔

Definition 4.4

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 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.

Note that we will not mention c ∉{a, b} anymore, since this is enforced by our permutative convention (see Definition 2.18.)

Definition 4.5

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

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

We will often use the fact that on ground terms capture-avoiding substitution of atoms for atoms preserves size, i.e. |g[b/a]| = |g| for ground terms g. This can easily be shown by an induction on the size of g.

We will use the following simple properties relating freshness and capture-avoiding substitution on ground terms:

Lemma 4.6

For ground terms g, h, fa(g[h/a]) ⊆ (fa(g)\{a}) ∪ fa(h).

Proof

By induction on the size of g. In the calculations we indicate uses of the inductive hypothesis with a superscript IH . We consider the three more interesting cases in turn:

– g ≡ [a]g′: Then ([a]g′)[h/a] ≡ [a]g′. We must show

fa(g′) \ {a} ⊆(fa(g′) \ {a}) ∪fa(h),

which is trivial.

– g ≡ [b]g′, b ∉ fa(h): Then ([b]g′)[h/a] ≡ [b](g′[h/a]). We calculate as follows:

fa(g′[h/a])\{b} \overset{IH }{⊆} ((fa(g′)\{a})∪fa(h))\{b} = ((fa(g′)\{b})\{a})∪fa(h).

– g ≡ [b]g′, b ∉ fa(h): Then ([b]g′)[h/a] ≡ [c](g′[c/b][h/a]), where our choice of fresh atom is c ∉ fa(g′) ∪ fa(h). We must show

(fa(g′[c/b][h/a]) \ {c}) ⊆((fa(g′) \ {b}) \ {a}) ∪fa(h),

which we calculate as follows:

fa(g′[c/b][h/a]) \ {c} \overset{IH }{⊆} ((fa(g′[c/b]) \ {a}) ∪ fa(h)) \ {c} = ((fa(g′[c/b]) \ {c}) \ {a}) ∪ fa(h) \overset{IH }{⊆} ((((fa(g′) \ {b}) ∪ fa(c)) \ {c}) \ {a}) ∪ fa(h) = ((fa(g′) \ {b}) \ {a}) ∪ fa(h).

In the first application of the inductive hypothesis above, we use the fact that |g′[c/b]| < |[b]g′|.

⊓⊔

Lemma 4.7

For ground terms g, h:

1. If ⊢a#h then ⊢a#g[h/a].

2. If ⊢a#g and ⊢a#h then ⊢a#g[h/b].

Proof

We prove the contrapositive. By Lemma 4.3 it suffices to show that:

1. If a ∈ fa(g[h/a]) then a ∈ fa(h).

2. If a ∈ fa(g[h/b]) then a ∈ fa(g) or a ∈ fa(h), or both.

This is easy using Lemma 4.6. ⊓⊔

Lemma 4.8 states familiar properties of ground terms — but are they true? Lemma 4.8 makes the vital connection between ‘substitution as we know it’ and the nominal technology we bring to bear on it. We give proofs in some detail. They run smoothly, and this fact is encouraging evidence that our definitions are appropriate:

Lemma 4.8

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. Distributivity. If ⊢a#k then ⊢CORE g[h/a][k/b] = g[k/b][h[k/b]/a].

Proof (of parts 1, 2 and 3.).

Part 1 follows from the stronger property that g[a/a] ≡g. We prove that by an easy induction on g which we omit.

We show part 2 by induction on the size of g. Most cases are easy; the interesting ones are:

– g ≡ [a]g′. Then ([a]g′)[b/a] ≡ [a]g′, so we must show ⊢CORE [a]g′ = (b a) · [a]g′. By (#[]a) we know a#[a]g′. By assumption b#[a]g′. By (symm) and (perm) we conclude that ⊢CORE [a]g′ = (b a) · [a]g′ as required.

– g ≡ [b]g′. Then ([b]g′)[b/a] ≡ [c](g′[c/b][b/a]) where c ∉ fa(g′) is our choice of fresh atom. We must now show that

⊢CORE [c](g′[c/b][b/a]) = [a](b a) · g′.

By (symm) and the syntactic criteria of Corollary 3.4, this happens when

⊢c#(b a) · g′ and ⊢CORE g′[c/b][b/a] = (c a) · (b a) · g′.

We consider each part in turn. Since c ∉ fa(g), we know ⊢c#(b a) · g′ by Lemmas 2.24 and 4.3. To prove ⊢CORE g′[c/b][b/a] = (c a) · (b a) · g′ it suffices to show that

⊢CORE g′[c/b][b/a] = (b a) · g′[c/b] and ⊢CORE (b a) · g′[c/b] = (b a) · (c b) · g′,

by (tran). Now |g′[c/b]| < |[b]g′| so we use the inductive hypothesis to deduce

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

from ⊢b#g′[c/b], which follows by Lemma 4.7. We deduce ⊢CORE (b a) · g′[c/b] = (b a) · (c b) · g′ from ⊢CORE g′[c/b] = (c b) · g′ using Lemma 2.34. We assumed c ∉ fa(g′) so by Lemma 4.3 also ⊢c#g′. We use the inductive hypothesis.

– g ≡ [c]g′. Then ([c]g′)[b/a] ≡ [c](g′[b/a]), so we need to show

⊢CORE [c](g′[b/a]) = [c](b a) · g′.

This follows directly from the inductive hypothesis using (cong[]).

We show part 3 by induction on the size of g using the syntactic criteria of Corollary 3.4. The only interesting case is when g ≡ [b]g′ and b ∈ fa(h). Then ([b]g′)[h/a] ≡ [c](g′[c/b][h/a]) where c ∉ fa(g′) ∪ fa(h), so we must show ⊢CORE [c](g′[c/b][h/a]) = [b]g′. By (tran) this follows from

⊢CORE [c](g′[c/b][h/a]) = [c](c b) · g′ and ⊢CORE [c](c b) · g′ = [b]g′.

By (perm), ⊢CORE [c](c b) · g′ = [b]g′ follows from ⊢b#[b]g′ and ⊢c#[b]g′, which follow from assumption c ∉ fa(g′) by the rules for freshness and Lemma 4.3. By (cong[]) and (tran), ⊢CORE [c](g′[c/b][h/a]) = [c](c b) · g′ follows from

⊢CORE g′[c/b][h/a] = g′[c/b] and ⊢CORE g′[c/b] = (c b) · g′.

By the inductive hypothesis, ⊢CORE g′[c/b][h/a] = g′[c/b] follows from ⊢a#g′[c/b], which follows from assumption ⊢a#[b]g′ by Lemmas 4.7 and 2.20. Finally, ⊢CORE g′[c/b] = (c b) · g′ is an instance of part 2 of this lemma, since ⊢c#g′. ⊓⊔

We can prove part 4 by induction on the size of g, using parts 2 and 3 and congruence of capture-avoiding substitution on ground terms. We will only provide the congruence properties here.

Lemma 4.9

For ground terms g, h, k:

1. If ⊢CORE g = h then ⊢CORE g[k/a] = h[k/a].

2. If ⊢CORE h = k then ⊢CORE g[h/a] = g[k/a].

Proof

The proof of the first part is by induction on the size of g, using the syntactic criteria of Corollary 3.4. We consider the two most interesting cases:

– g ≡ [a]g′. Then there are two possibilities:

• h ≡ [a]h′ and ⊢CORE g′ = h′. Then we must show ⊢CORE [a]g′ = [a]h′ since ([a]g′)[k/a] ≡ [a]g′ and ([a]h′)[k/a] ≡ [a]h′. The result follows from the assumption ⊢CORE g′ = h′ by (cong[]).

• h ≡ [b]h′, ⊢b#g′ and ⊢CORE (b a) · g′ = h′. Then since ⊢b#g′, we also have ⊢a#(b a) · g′ by Lemma 2.24. Using Corollary 3.6 and assumption ⊢CORE (b a) · g′ = h′ also ⊢a#h′. Then ⊢a#[b]h′ by (#[]b), so by part 3 of Lemma 4.8 we obtain ⊢CORE ([b]h′)[k/a] = [b]h′. Now by (cong[]), (symm) and assumption ⊢CORE (b a) · g′ = h′, we have ⊢CORE [b]h′ = (b a) · [a]g′. Also ⊢CORE (b a) · [a]g′ = [a]g′ by (perm) and assumption ⊢b#g′. Since [a]g′ ≡ ([a]g′)[k/a], we may use (tran) and (symm) to conclude ⊢CORE ([a]g′)[k/a] = ([b]h′)[k/a], as required.

– g ≡ [b]g′. Then again there are two possibilities:

• h ≡ [a]h′, ⊢a#g′ and ⊢CORE (a b) · g′ = h′. Completely analogous to the previous part we can show that ⊢CORE ([b]g′)[k/a] = ([a]h′)[k/a].

• g ≡ [b]h′ and ⊢CORE g′ = h′. If b ∉ fa(k) we must show ⊢CORE [b](g′[k/a]) = [b](h′[k/a]), which follows from the assumption ⊢CORE g′ = h′ by (cong[]) and the inductive hypothesis. If b ∈ fa(k) we must show ⊢CORE [c](g′[c/b][k/a]) = [c](h′[c/b][k/a]) where c ∉ fa(g′) ∪ fa(h′) ∪ fa(k).7 By an application of (cong[]) this follows from ⊢CORE g′[c/b][k/a] = h′[c/b][k/a]. By inductive hypothesis, this follows from ⊢CORE g′[c/b] = h′[c/b]. Since ⊢c#g′ and ⊢c#h′, this is equivalent to ⊢CORE (c b) · g′ = (c b) · h′ by part 2 of Lemma 4.8. By Lemma 2.24 this follows from ⊢CORE g′ = h′, which we assumed.

The proof of the second part is similar, but simpler. ⊓⊔

We will now show how equality on ground terms in theory CORE coincides with a ‘standard’ definition of α-equivalence.

Definition 4.10

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).

Before we can relate CORE equality and =α, we need to establish a few technical properties of =α. Define a ‘bound atoms of’ function ba(g) on ground terms inductively as follows:

ba(a) = ∅ ba(f(g1, . . . , gn)) =⋃1≤i≤nba(gi) ba([a]g) = ba(g) ∪{a}.
Lemma 4.11

If a ∉ ba(g) and b ∉g, then [b](g[b/a]) =α [a]g.

Proof

Let c ∉g. By a congruence rule from Figure 6, [b](g[b/a]) =α [a]g follows from g[b/a][c/b] =α g[c/a]. This follows by reflexivity since we can show g[b/a][c/b] ≡g[c/a] by an easy induction on the structure of g: the cases of a and d are trivial, the cases of f(g1, . . . , gn) and [d]g′ follow directly from the inductive hypothesis, and the remaining cases b, c, [a]g′, [b]g′ and [c]g′ are vacuously true. ⊓⊔

g =α g g =α h h =α g g1 =α g2 g2 =α g3 g1 =α g3 g =α h [a]g =α [a]h g[c/a] =α h[c/b] (c fresh) [a]g =α [b]h g1 =α h1 · · · gn =α hn f(g1, . . . , gn) =α f(h1, . . . , hn)
Fig. 6. α-equivalence =α on ground terms

Lemma 4.11 enables us to prove the =α-equivalent of the (perm) rule.

Lemma 4.12

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

Proof

It is not hard to see that all instances of a and b in g occur in the scope of abstractors [a] and [b]. Traverse the structure of g bottom-up, and use Lemma 4.11 to rename those abstractors so they are not a or b any more, but some completely fresh set of atoms — a different one for each instance of [a] and [b]. Call the new term g′, then it is easy to show (a b) · g′ ≡g′, since a, b ∉g′. Now equality is symmetric, so we reverse the process to get g back again. ⊓⊔

Lemma 4.12 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 g and h are α-equivalent.

Theorem 4.13

For ground terms g, h, ⊢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 3.4. The cases 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′. By Lemma 4.3 and some easy calculations we know a, b ∉ fa([a]g′), so [a]g′ =α [b](b a) · g′ by Lemma 4.12 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.

Suppose we have deduced [a]g =α [b]h using the last abstraction rule for =α. 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 4.8. 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]h ⊓⊔

5 The theory SIMP; simply substitution

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

Definition 5.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).

(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 ])
Fig. 7. Axioms of SIMP
Lemma 5.2

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

Proof

We work by induction on the size of g. We consider the cases in turn:

– g ≡a. Then ⊬a#a and there is nothing to prove.

– g ≡b. Then ⊢a#b. ⊢SIMP b[a↦ →h] = b by axiom (b↦→).

– g ≡ [a]g′. Take c fresh for g′ and h. Then ⊢CORE [c](c a) · g′ = [a]g′ by (perm) since ⊢c#g′ and ⊢a#g′. Using (symm), (cong[]) and (congf) we obtain

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

By (abs↦→) also

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

since ⊢c#h. Since ⊢a#(c a) · g′, we know ⊢SIMP ((c a) · g′)[a↦ →h] = (c a) · g′ by the inductive hypothesis ((c a) · g′ has the same size as g′, and so is smaller than [a]g′). Using (cong[]) and ⊢CORE [c](c a) · g′ = [a]g′ we obtain

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

We use (tran) to obtain ⊢SIMP ([a]g′)[a↦ →h] = [a]g′, as required.

– g ≡ [b]g′. Analogous to the previous part.

– g ≡ f(g1, . . . , gn)[a↦ →h], f ≠ sub. By assumption ⊢a#f(g1, . . . , gn). Then ⊢a#gi by Theorem 2.20 and ⊢SIMP gi[a↦ →h] = gi by the inductive hypothesis, for all i, 1 ≤i ≤n. Using (congf) and (tran) we obtain

⊢SIMP f(g1[a↦ →h], . . . , gn[a↦ →h]) = f(g1, . . . , gn).

By axiom (f↦→)

⊢SIMP f(g1, . . . , gn)[a↦ →h] = f(g1[a↦ →h], . . . , gn[a↦ →h]).

We obtain ⊢SIMP f(g1, . . . , gn)[a↦ →h] = f(g1, . . . , gn) by (tran), as required.

⊓⊔

Theorem 5.3

For ground terms g, h, ⊢SIMP g[a↦ →h] = g[h/a].

Proof

By induction on the size of g:

– g ≡a. Then ⊢SIMP a[a↦ →h] = h by axiom (var↦→), and a[h/a] ≡h.

– g ≡b. Then ⊢SIMP b[a↦ →h] = b by axiom (b↦→), and b[h/a] ≡b.

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

– g ≡ [b]g′, b ∉ fa(h). Then ⊢SIMP ([b]g′)[a↦ →h] = [b](g′[a↦ →h]) is an instance of axiom (abs↦→), since ⊢b#h by Lemma 4.3. By the inductive hypothesis ⊢SIMP g′[a↦ →h] = g′[h/a], so we conclude ([b]g′)[a↦ →h] = [b](g′[h/a]) using (cong[]) and (tran). We are then done, since ([b]g′)[h/a] ≡ [b](g′[h/a]).

– 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). By Lemma 4.3 then 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 4.8, we deduce

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

using the rules of equality and Lemma 4.9. Using (tran) we put the pieces together to conclude

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

– g ≡ f(g1, . . . , gn), f ≠ sub. Then

⊢SIMP f(g1, . . . , gn)[a↦ →h] = f(g1[a↦ →h], . . . , gn[a↦ →h])

by (f↦→). By the inductive hypothesis ⊢SIMP gi[a↦ →h] = gi[h/a] for all i, 1 ≤i ≤n. Then by applications of (congf) and (tran) we obtain

⊢SIMP f(g1, . . . , gn)[a↦ →h] = f(g1[h/a], . . . , gn[h/a]).

Since f(g1, . . . , gn)[h/a] ≡ f(g1[h/a], . . . , gn[h/a]), we are done.

⊓⊔

On closed terms we can interpret all occurrences of term-former sub by capture-avoiding substitution.

Definition 5.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(t1↧→, . . . , tn↧→) (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 5.5

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

Proof

By induction on the structure of t. The interesting case is t ≡ sub(u, v). By assumption we know ⊢a#sub(u, v). By Lemma 2.20 also ⊢a#u and ⊢a#v. By the inductive hypothesis, ⊢a#u↧→and ⊢a#v↧→.

There are now two cases:

– u↧→≡ [b]g and sub(u, v)↧→≡g[v↧→/b]. Then we must show ⊢a#g[v↧→/b]. By Lemma 4.7 this follows from assumption ⊢a#v↧→and ⊢a#g. This in turn follows from assumption ⊢a#u↧→(recall that u↧→≡ [b]g) by Lemma 2.20.

– u↧→≡ [a]g and sub(u, v)↧→≡g[v↧→/a]. Then ⊢a#g[v↧→/a] follows from assumption ⊢a#v↧→by Lemma 4.7.

⊓⊔

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

Theorem 5.6

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

Proof

By induction on the structure of t:

– t ≡a. Then a↧→≡a, and we conclude ⊢SIMP a = a by (refl).

– t ≡ [a]u. Then ([a]u)↧→≡ [a](u↧→), and ⊢SIMP [a]u = [a](u↧→) follows from inductive hypothesis ⊢SIMP u = u↧→by (cong[]).

– t ≡ f(t1, . . . , tn), f ≠ sub. Then f(t1, . . . , tn)↧→≡ f(t1↧→,...,tn↧→), and

⊢SIMP f(t1, . . . , tn) = f(t1↧→, . . . , tn↧→) follows from inductive hypotheses ⊢SIMP ti = ti↧→, 1 ≤ i ≤ n, by (congf ) and

(tran).

– t ≡ sub(u, v). Then sub(u, v)↧→≡g[v↧→/a] where [a]g ≡u↧→. 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 5.3 we know ⊢SIMP g[a↦ →v↧→] = g[v↧→/a]. Now 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.

⊓⊔

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

Corollary 5.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]].

Proof

Using Theorem 5.6 and Lemma 4.8. ⊓⊔

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, is it not the case that there are two terms all of whose closed instances are equated by SIMP, but which are not themselves probably 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.

6 Substitution on open terms using SIMP

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

6.1 Nominal rewriting

Definition 6.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 is a set of nominal rewrite rules. We tend to let R range over nominal rewrite systems.

Definition 6.2

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

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

In Figure 8, f ranges over all term-formers of the signature of R (whatever that signature is). We dicuss each of the aspects of the (→rew) in more detail:

– The permutation π gives atoms in rules the character of ‘unknown atoms up to permutation’. Thus in the substitution signature of the lambda calculus (Example 2.7) extended with a term-former const : ()T 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’. This is standard.

– The premise ∆⊢∇σ ensures that the instantiation is consistent. Note that we could also have used ∆⊢π · ∇σ, which is equivalent to ∆⊢∇σ by Lemma 2.24.

– Finally, 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.
∆ ⊢CORE t = π · lσ ∆ ⊢CORE u = π · rσ ∆ ⊢ ∇σ (→rew) (∇ ⊢ l → r ∈ R) ∆ ⊢R t → u ∆ ⊢R t → u (→[]) ∆ ⊢R [a]t → [a]u ∆ ⊢R t → u (→f ) ∆ ⊢R f(t1, . . . , t, . . . , tn) → f(t1, . . . , u, . . . , tn)
Fig. 8. Derivation rules for nominal rewriting
Lemma 6.3

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

Proof

By an easy induction on derivations. ⊓⊔

So 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σ).

Definition 6.4

We say that the rewrite occurs at that position or occurs at t′ inside t. If the derivation tree has just one derivation rule in it then it must be an instance of (→rew) for some rewrite rule R ∈ R and we may say the rewrite occurs at root position and that R matches at top level.

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

Lemma 6.5

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σ. ⊓⊔

Definition 6.6

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 alpha-equivalence:

∆ ⊢R t → u (→∗→) ∆ ⊢R t →∗ u ∆ ⊢CORE t = u (→∗refl) ∆ ⊢R t →∗ u ∆ ⊢R t →∗ u ∆ ⊢R u →∗ v (→∗tran) ∆ ⊢R t →∗ v
Fig. 9. Derivation rules for the transitive reflexive closure of R
Lemma 6.7

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′. For the right-to-left direction, assume ∆⊢CORE t = u. By (→∗refl) we obtain ∆⊢R t →∗u.

For the left-to-right direction, the proof obligation is equivalent to (swapping antecedents): If ∆⊢R t →∗u then if there is no t′ such that ∆⊢R t →t′ then ∆⊢CORE t = u. We proceed by induction on derivations of ∆⊢R t →∗u. Suppose the derivation concludes in:

– (→∗→): then ∆⊢R t →u and there is nothing to prove, since there is a t′ such that ∆⊢R t →t′.

– (→∗refl): then ∆⊢CORE t = u and we are done.

– (→∗tran): then ∆⊢R t →∗v is derived from ∆⊢R t →∗u and ∆⊢R u →∗v for some u. By the inductive hypothesis

• if there is no t′ such that ∆⊢R t →t′ then ∆⊢CORE t = u, and

• if there is no u′ such that ∆⊢R u →u′ then ∆⊢CORE u = v.

By assumption there is no t′ such that ∆⊢R t →t′, so ∆⊢CORE t = u. Using ∆⊢CORE t = u, it is easy to verify that there is no u′ such that ∆⊢R u →u′. So we also have ∆⊢CORE u = v. We conclude ∆⊢CORE t = v by (tran).

The result follows. ⊓⊔

The transitive reflexive closure of R is a congruence:

Lemma 6.8

The following rules are admissible:

∆ ⊢R t →∗ u (→∗[]) ∆ ⊢R [a]t →∗ [a]u ∆ ⊢R t →∗ u (→∗f ) ∆ ⊢R f(t1, . . . , t, . . . , tn) →∗ f(t1, . . . , u, . . . , tn)
Proof

We only give a proof for the case of (→∗[]), the case of (→∗f) is analogous. We work by induction on the derivation of ∆⊢R t →∗u:

– If the derivation concludes in (→∗→) then it must be that ∆⊢R t →∗u is derived from ∆⊢R t →u. We extend the derivation of ∆⊢R→u with (→ []) and (→∗→) to obtain one of ∆⊢R [a]t →∗ [a]u.

– If the derivation concludes in (→∗refl) then we extend the derivation of ∆⊢CORE t = u with (cong[]) and (→∗refl) to obtain ∆⊢R [a]t →∗ [a]u.

– If the derivation concludes in (→∗tran) then it must be that ∆⊢R t →∗u is derived from ∆⊢R t →∗u′ and ∆⊢R u′ →∗u. So ∆⊢R [a]t →∗ [a]u′ and ∆⊢R [a]u′ →∗ [a]u by the inductive hypothesis. We extend with (→∗tran) to obtain ∆⊢R [a]t →∗ [a]u as required.

⊓⊔

Definition 6.9

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 6.10

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.

Definition 6.11

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 root position. If any of the two rewrites occurs at a moderated unknown inside t, call the critical pair trivial.

Call a nominal 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 each variable occurring in l occurs only once. A uniform nominal rewrite system with only left-linear rules and no non-trivial critical pairs is orthogonal.

Theorem 6.12

An orthogonal uniform nominal rewrite system is confluent.

Proof

See [8, Theorem 65]. ⊓⊔

6.2 SIMPr: explicit substitution rewritten

Definition 6.13

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

(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 ])
Fig. 10. Substitution as a rewrite system SIMPr

A basic correctness result is this:

Theorem 6.14

For possibly open t, u, if ∆⊢SIMPr t →u then ∆⊢SIMP t = u.

Proof

We work by induction on the derivation of ∆⊢SIMPr t →u to show that ∆⊢SIMP t = u 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). ∆⊢SIMP a[a↦ →u] = u is derivable using axiom (var↦→).

– (Rb). ∆⊢SIMP b[a↦ →t] = b using axiom (b↦→).

– (Rf). ∆⊢SIMP f(u1, . . . , un)[a↦ →t] = f(u1[a↦ →u], . . . , un[a↦ →u]) using axiom (f↦→).

– (Rabs). ∆⊢SIMP ([b]u)[a↦ →t] = [b](u[a↦ →t]) using (abs↦→); the freshness side-condition is guaranteed by the identical side-condition on (abs→).

The result follows. ⊓⊔

Corollary 6.15

For possibly open t, u, if ∆⊢SIMPr t →∗u then ∆⊢SIMP t = u.

Proof

By induction on the structure of derivations of ∆⊢SIMPr t →∗u. The case of (→∗→) uses Theorem 6.14, (→∗refl) uses (refl), and (→∗tran) uses (tran).

⊓⊔

6.3 Confluence, conservativity and consistency

Lemma 6.16

All rewrite rules of SIMPr are uniform.

Proof

For each rule, use appropriate instances of Lemma 2.20. 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.20:

– 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′. ⊓⊔

Note that SIMPr satisfies the even stronger property of being a closed nominal rewrite system [10, Section 4.2, Theorem 5.2]. However, Lemma 6.16 is enough to obtain Theorem 6.17 below.

Theorem 6.17 (Confluence of SIMPr).

SIMPr is confluent.

Proof

By Lemma 6.16 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 by Definition 6.11, SIMPr is orthogonal and uniform. Then by Theorem 6.12, SIMPr is confluent. ⊓⊔

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

Definition 6.18

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

Theorem 6.19

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 6.17 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 6.7, and we conclude ∆⊢CORE t = u by (tran). ⊓⊔

Corollary 6.20 (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 6.19, since if t and u do not mention sub, then t and u are SIMPr-normal forms with respect to any ∆. ⊓⊔

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

Corollary 6.21

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 5.6 and (tran). By Corollary 6.20 this is equivalent to ⊢CORE t↧→= u↧→. ⊓⊔

Corollary 6.22 (Consistency of SIMP).

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

Proof

A corollary of Corollaries 6.20 and 3.5. ⊓⊔

For the next result need some terminology.

Definition 6.23

Call a substitution σ closing for an unknown X when σ(X) is a closed term. Call σ closing for a term t or a freshness context ∆ when it is closing for the unknowns in t or ∆, i.e. σ(X) is closed for every X ∈t or X ∈∆.

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

Theorem 6.24 (Soundness of SIMP).

Theorey 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.35 and our assumption that ⊢∆σ. We obtain ⊢CORE tσ↧→= uσ↧→by Corollary 6.21, since tσ and uσ are closed. We conclude tσ↧→=α uσ↧→by Theorem 4.13, since tσ↧→and uσ↧→are ground. ⊓⊔

6.4 Failure of completeness for SIMP with respect to unknowns.

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 6.25 (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 4, we can easily check using the syntactic criteria of Corollary 3.4 that

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

Since X[a↦ →T][b↦ →U] and X[b↦ →U][a↦ →T[b↦ →U]] have no SIMPr rewrites with respect to a#U, we conclude

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

by Theorem 6.19.

The proofs of the other parts are similar. ⊓⊔

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

Nominal algebra has a model theory and satisfies soundness and completeness [5, 4]. 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.

6.5 Strong normalisation and decidability

We expect the part of a λ-calculus that handles substitution to be terminating [11, 12] — 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.8

Definition 6.26

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 6.27

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 3.4 which states that t and u are renamed versions of each other by means of permutations. ⊓⊔

Lemma 6.28

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 6.27 above). ⊓⊔

Lemma 6.29

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. ⊓⊔

Theorem 6.30 (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 6.29 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 6.27, |t|m = |π · lσ|m = |lσ|m and |u|m = |π · rσ|m = |rσ|m. Then showing |t|m > |u|m is equivalent to showing |lσ|m > |rσ|m. For each SIMPr rule this is an instance of Lemma 6.28. ⊓⊔

We have already given an algorithm to compute normal forms:

Lemma 6.31

If t is closed then t↧→ is a SIMPr normal form of t.

Proof

By an easy induction on t. ⊓⊔

Theorem 6.32

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

Proof

Let ∆ be a freshness context and t be a term. By Theorem 6.30 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 6.17) 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 6.7. Using (symm) and (tran) we conclude ∆⊢CORE u = v. ⊓⊔

As a corollary we obtain decidability of theory SIMP:

Theorem 6.33 (Decidability of SIMP).

It is decidable whether ∆⊢SIMP t = u.

Proof

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

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

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

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

⊓⊔

7 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 7.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 7.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.

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

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

Derivation for part 1:

[b#X]1 (#[]a) (#[]b) a#[a]X 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)1 X[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. ⊓⊔

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

7.1 Soundness and the relation with SIMP

SUB can do everything that SIMP can:

Lemma 7.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. ⊓⊔

We now need a technical lemma:

Lemma 7.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 5.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]).

Also ⊢SIMP ([c](c b) · g)[a↦ →v] = [c](((c b) · g)[a↦ →v]) by axiom (abs↦→) and ⊢c#v, 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]].

But since ⊢c#v, this is just an instance of part 4 of Corollary 5.7, and we are done.

2. We must show ⊢SIMP [a]sub(t, a) = t. By Theorem 5.6 this is equivalent to ⊢SIMP [a]sub(t↧→, a) = t↧→. We proceed by case distinction on the structure of t↧→; here we only consider the two most interesting cases:

– t↧→≡ [a]g: Then ⊢SIMP [a](g[a↦ →a]) = [a]g follows by (cong[]) and part 1 of Corollary 5.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 5.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.20, this is when ⊢a#[b]g. Since [b]g ≡t↧→, this follows from the assumption ⊢a#t by Lemma 5.5.

⊓⊔

SIMP can do everything that SUB can — provided that the terms are closed:

Lemma 7.5

If t and u are closed and ⊢SUB t = u then ⊢SIMP t = u.

Proof

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 7.4. Instances of axioms (ren↦→) and (#↦→) are instances of parts 2 and 3 of Corollary 5.7. Finally, each instance of (η↦→) is an instance of part 2 of Lemma 7.4. ⊓⊔

To recap, SIMP is sound for a ground term model by Theorem 5.3, equality in SIMP is decidable by Theorem 6.33, but not complete by the Theorem 6.25.

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 7.6 (Soundness of SUB).

Theory 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.35. tσ and uσ are closed so by Lemma 7.5 ⊢SIMP tσ = uσ. By Corollary 6.21 we obtain ⊢CORE tσ↧→= uσ↧→. We conclude tσ↧→=α uσ↧→ by Theorem 4.13, since tσ↧→ and uσ↧→are ground. ⊓⊔

7.2 Decidability

In this subsection we will establish that equality in SUB is decidable; we will show an algorithm exists which given t, u and a freshness context ∆, decides whether ∆⊢SUB t = u is derivable.

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 6.33), and conclude that SUB is decidable. The rest of this section makes this formal.

Definition 7.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 entirely fresh atom a′ X.

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

Write D = {dX | X ∈X}, and let T′ be the signature T ∪D.

Definition 7.8

Define a substitution ς by:

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

Note that ς maps possibly open terms in T mentioning unknowns in X, to closed terms in T′. Then ς is ∆-consistent:

Lemma 7.9

⊢∆ς 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 ∉∆, so a ∉{aX1, . . . , aXkX}, and the result follows.

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

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

Theorem 7.10

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.35, using Lemma 7.9. We conclude ⊢SIMP tς = uς by Lemma 7.5. ⊓⊔

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 6.31, tς↧→ and uς↧→ are the SIMPr-normal forms of tς and uς.

Definition 7.11

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 new atom a′X for each X ∈X, and

– a set of new atoms B in bijection with A, write it {bXi | X, i such that aXi ∈ A}. (Note that we choose atoms in B distinct from all the a′X chosen above.)

Let ∆+ be ∆ enriched with freshness assumptions a′#X for every a′ ∈A+ \ A and every X ∈X.

Definition 7.12

We let t′ and u′ range over closed terms in T′ mentioning only atoms in A+ \ B. Define an inverse translation from these closed terms in T′ to terms in T , inductively by:

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], a′ X) (X:[A]T)

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.

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

Lemma 7.13

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

Proof

We prove that if v is a subterm of t or u then ∆+ ⊢SUB (vς)-1 = v, by induction on 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 3.4 we need only 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 [a′X]sub(π · X, a′X) = π · X.

This follows by axiom (η↦→), since ∆+ ⊢a′X#π · X. ⊓⊔

Remark 7.14

The reader might wonder why the inverse mapping of the dX needs to rename the atoms aXi to the fresh bXi. We illustrate the reasons with an informal argument which can easily be made formal. Consider (aT1 aT2) · T, where we don’t know aT1#T or aT2#T. Then

(((aT1 aT2) · T)ς)-1 ≡((bT2 aT2)(bT1 aT1) · T)[bT1↦ →aT2][bT2↦ →aT1].

By calculations we can verify Lemma 7.13:

((bT2 aT2)(bT1 aT1) · T)[bT1↦ →aT2][bT2↦ →aT1] = (aT1 aT2) · T

is derivable in an appropriate freshness context. Had we left out the renaming to fresh atoms the result of (((aT1 aT2) · T)ς)-1 would be T[aT1↦ →aT2][aT2↦ →aT1], which is not equal to (aT1 aT2) · T, since for example

((aT1 aT2) · T)[aT1/T] = aT2but T[aT1↦ →aT2][aT2↦ →aT1] = aT1.

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

Lemma 7.15

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

Proof

By induction on the structure of t′. The only non-trivial case is when t′ ≡ dX(t′ 1, . . . , t′ kX). We treat the case of X : T, the case of X : [A]T is similar. Suppose ⊢a′#dX(t′ 1, . . . , t′ kX). Then ⊢a′#t′ i for all i, by Lemma 2.20. By the inductive hypothesis, ∆+ ⊢a′#t′-1 i . We must show

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

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

– a′ = bXki for some i: then

bXki#[bXki]((π · X)[bX1↦ →t′ 1-1] · · · [bXki−1↦ →t′ i−1-1])

by (#[]a). Now sub is just a term-former so

bXki#(π · X)[bX1↦ →t′ 1-1] · · · [bXki−1↦ →t′ i−1-1][bXki↦ →t′ i-1]

by (#f) and the inductive hypothesis for t′ i, and the result easily follows by the rules of freshness using the inductive hypothesis.

– a′ ≠ bXki for all i: then π-1(a′) ≠ aXki for all i, and π-1(a′)#X ∈∆+ by definition. The result follows using the rules for freshness and the inductive hypothesis.

⊓⊔

Lemma 7.16

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

Proof

By induction on the structure of t′, using the syntactic criteria of Corollary 3.4. The only non-trivial case is when t′ ≡ [a′]v′, u′ ≡ [b′]w′, ⊢b′#v′ and ⊢CORE (b′ a′) · v′ = w′. By Lemma 7.15 we obtain ∆+ ⊢b′#v′-1, and by the inductive hypothesis ∆+ ⊢CORE (b′ a′) · v′-1 = w′-1. By standard reasoning using the

rules for freshness and equality we conclude ∆+ ⊢CORE [a′]v′-1 = [b′]w′-1. ⊓⊔

Lemma 7.17

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′Xk-1][a′ ↦→ v′-1] = (π · X)[bX1 ↦→ v′1[a′ ↦→ v′-1]] · · · [bXkX ↦→ v′Xk-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 7.15. Now we apply part 4 of Lemma 7.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′Xk-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 follows from ∆+ ⊢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 7.15. By (axabs↦→), we obtain

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

as required.

The result follows. ⊓⊔

Theorem 7.18

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

Proof

The left-to-right part is Theorem 7.10.

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 7.17, we know

∆+ ⊢SUB (tς)-1 ≡ t1-1 = t2-1 = . . . = tm-1 ≡ (tς ↧→)-1

and

∆+ ⊢SUB (uς)-1 ≡ u1-1 = u2-1 = . . . = un-1 ≡ (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 6.21 it must be the case that ⊢CORE tς↧→= uς↧→. By Lemma 7.16 also ∆+ ⊢CORE (tς↧→)-1 = (uς↧→)-1.

Then ∆+ ⊢SUB (tς)-1 = (uς)-1 by symmetry and transitivity. By Lemma 7.13 then also ∆+ ⊢SUB t = u. Since ∆+ freshly extends ∆ with atoms not in t, u, we conclude ∆⊢SUB t = u by strengthening (Lemma 2.33). ⊓⊔

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

Corollary 7.19 (Decidability of SUB).

It is decidable whether ∆⊢SUB t = u.

Proof

By Theorem 7.18, ∆⊢SUB t = u is equivalent to ⊢SIMP tς = uς. By Theorem 6.33, this is decidable. ⊓⊔

Combining Theorem 7.18 and Corollary 6.21, 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 3.4.

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 7.17 and Lemma 7.13.

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

Theorem 7.20 (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 7.10, ⊢SIMP tς = uς. By construction tς and uς do not mention sub, therefore by Corollary 6.20 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 3.4. 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ς ≡[a′ X]dX(π(aX1), . . . , π(aXkX)).

By the syntactic criteria of Corollary 3.4 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. ⊓⊔

7.3 ω-completeness

We consider completeness with respect to the ground term model (see Definition 7.21 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 [4] with respect to a standard class of semantics in nominal sets [2]. 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 7.18 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 7.21

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 the previous subsection 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 7.22

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 {cX | 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(cX, cX) dX(t′1)∗ ≡ pair(cX, t′1∗) dX(t′1, . . . , t′kX )∗ ≡ pair(cX, pair(t′1∗, pair(t′2∗, . . . , pair(t′kX−1∗ , t′kX∗ )))) (kX > 1)

It is not hard to verify the following properties:

Lemma 7.23

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 3.4.

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

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

which follows by parts 1 and 2. ⊓⊔

Definition 7.24

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 7.25

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. ⊓⊔

Corollary 7.26

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

Proof

By Lemma 7.25 and part 3 of Lemma 7.23. ⊓⊔

Theorem 7.27

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 7.18. Now by Corollary 7.26 we obtain ⊬SIMP t(ς∗) = u(ς∗). Then (tς∗)↧→≠α (uς∗)↧→ by Theorem 4.13 and Corollary 6.21.

Now take σ = ς∗. Since ς∗ maps to ground terms in T , the result follows. ⊓⊔

7.4 Restricting the sort system

In Remark 2.9 we claimed that unknowns of sort [A]T and the term-former sub : ([A][A]T, T)[A]T are ‘convenient but not necessary’.

To see what precisely we mean by this, consider by way of example the lambda calculus signature from Example 2.7. Remove from it sub : ([A][A]T, T)[A]T and disallow unknowns of abstraction sort. The signature now has term-formers

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.

Let SUB be the theory of substitution over the signature of the lambda calculus from Example 2.7.

Theorem 7.28

Suppose that ∆, t and u are terms in the signature of SUB′ and do mention unknowns of sort [A]T. Then

∆⊢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. Instances of (lam↦→′) and (sub↦→′) may be replaced by instances of (f↦→) and (#↦→). Instances of the other axioms of SUB′ are directly instances of axioms with similar names in SUB.

For the left-to-right part, suppose ∆⊢SUB t = u. Then also ⊢SIMP tς = uς by Theorem 7.10. 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.

Using a result similar to Lemma 7.17 we obtain derivations of

∆+ ⊢SUB′ (tς)-1 = (tς↧→)-1and ∆+ ⊢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 6.21, Lemma 7.16 and our assumption ⊢SIMP tς = uς. Then ∆+ ⊢SUB (tς)-1 = (uς)-1 using (symm) and (tran). Using a result similar to Lemma 7.13 we obtain ∆+ ⊢SUB′ t = u. We conclude ∆⊢SUB′ t = u using (fr). ⊓⊔

We used every axiom of SUB′ in the proof above and it is not hard to show that if we remove any then the weaker theory is not complete. SUB′ is somewhat longer than SUB, and proofs involving SUB′ tend to be somewhat longer than proofs involving SUB. For this reason we preferred SUB in this paper.

8 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 7.27). 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é [13, 14] 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’ [14, page 2].

Feldman [15] gives an algebraic axiomatisation inspired by a concrete model of functions/evaluations. His axioms are closer in spirit to Cylindric Algebras [1] and Lambda Abstraction Algebras [16, 17]. 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) [18] and related systems implement substitution by ‘pipes’ (e.g. the translation of λ-terms into CA [18]). 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 [12] and the thesis of Bloo [19] 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 [20] 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’ definitely is not.

Sun has investigated Binding Algebras [21]. 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 [22], 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 [2] and categories of presheaves used in another thread of work [23, 24, 25]. This uses ideas from categorical algebra [26] 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 [23, 24, 25] 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 [3] (in our terminology, unification of nominal terms up to CORE) is decidable. Nominal unification is to be compared with higher-order patterns [27]. We suggest that unification up to SUB is to be compared with higher-order unification [28], 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 [29] and Hierarchical Nominal Rewriting [30] 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

[1] Burris, S., Sankappanavar, H.: A Course in Universal Algebra. Springer (1981)

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

[3] Urban, C., Pitts, A.M., Gabbay, M.J.: Nominal unification. Theoretical Computer Science 323(1–3) (2004) 473–497

[4] Gabbay, M.J., Mathijssen, A.: A formal calculus for informal equality with binding. In: WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation. Volume 4576 of LNCS. (2007) 162–176

[5] Gabbay, M.J., Mathijssen, A.: Nominal algebra. Technical Report HW-MACS-TR-0045, Heriot-Watt (2006)

[6] Gabbay, M.J., Mathijssen, A.: One-and-a-halfth-order logic. In: PPDP ’06: Proc. of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, ACM Press (2006) 189–200

[7] Gabbay, M.J., Mathijssen, A.: Capture-avoiding substitution as a nominal algebra. In: ICTAC’2006: 3rd Int’l Colloquium on Theoretical Aspects of Computing. Volume 4281 of LNCS. (2006) 198–212

[8] Fernández, M., Gabbay, M.J.: Nominal rewriting. Information and Computation 205 (2007) 917–965

[9] Hodges, W.: Elementary predicate logic. In Gabbay, D., Guenthner, F., eds.: Handbook of Philosophical Logic, 2nd Edition. Volume 1. Kluwer (2001) 1–131

[10] Fernández, M., Gabbay, M.J., Mackie, I.: Nominal rewriting systems. In: Proc. 6th Int. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming (PPDP’2004), ACM (2004) 108–119

[11] Bloo, R., Rose, K.H.: Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection. In: CSN-95: Computer Science in the Netherlands. (1995)

[12] Lescanne, P.: From lambda-sigma to lambda-upsilon a journey through calculi of explicit substitutions. In: POPL ’94: Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press (1994) 60–69

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

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

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

[16] Lusin, S., Salibra, A.: The lattice of lambda theories. Journal of Logic and Computation 14 n.3 (2004) 373–394

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

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

[19] Bloo, R.: Preservation of Termination for Explicit Substitution. PhD thesis, Eindhoven University of Technology, Eindhoven (1997)

[20] de Bruijn, N.G.: Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the church-rosser theorem. Indagationes Mathematicae 5(34) (1972) 381–392

[21] Sun, Y.: An algebraic generalization of frege structures - binding algebras. Theoretical Computer Science 211 (1999) 189–232

[22] Dowek, G., Hardin, T., Kirchner, C.: Binding logic: Proofs and models. In: LPAR ’02: Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, London, UK, Springer-Verlag (2002) 130– 144

[23] Fiore, M., Turi, D.: Semantics of name and value passing. In: Proc. 16th LICS Conf., IEEE, Computer Society Press (2001) 93–104

[24] Fiore, M.P., Plotkin, G.D., Turi, D.: Abstract syntax and variable binding. In: 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press (1999) 193–202

[25] Tanaka, M., Power, J.: A unified category-theoretic formulation of typed binding signatures. In: MERLIN, ACM (2005) 13–24

[26] Lambek, J., Scott, P.: Introduction to Higher Order Categorical Logic. CUP (1986)

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

[28] Huet, G.: Higher order unification 30 years later. In: TPHOL 2002. Number 2410 in LNCS (2002) 3–12

[29] Gabbay, M.J., Lengrand, S.: The lambda-context calculus. In: LFMTP’07: International Workshop on Logical Frameworks and Meta-Languages. To appear in ENTCS (2007)

[30] Gabbay, M.J.: Hierarchical nominal rewriting. In: LFMTP’06: Logical Frameworks and Meta-Languages: Theory and Practice. (2006) 32–47

Notes

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

4 There is no mathematical reason for this, but there is a nice computational one: the algorithm obtained by reading rules bottom-up, must terminate. ↩

5 Composing both sides of π ◦π′ = Id with π-1, we obtain π′ = π-1. Inverting both sides, we obtain π′-1 = π. ↩

6 In sequent style (fr) would be ∆, a#X1, . . . , a#Xn ⊢ t = u ∆ ⊢ t = u (a ∉ t, u, ∆). ↩

7 Both ([b]g′)[k/a] and ([b]h′)[k/a] introduce the same fresh atom c because fa(g′) = fa(h′). We can see this as follows: fa(g′) = fa(h′) is equivalent to a′ ∉ fa(g′) iff a′ ∉ fa(h′) for all atoms a′. By Lemma 4.3 this is equivalent to ⊢a′#g′ iff ⊢a′#h′, and by Corollary 3.6, this follows from the assumption ⊢CORE g′ = h′. ↩

8 As is also standard, it took the authors months of laborious fiddling to get this definition just right. ↩