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

Permissive nominal terms and their unification: an infinite, co-infinite approach to nominal techniques

Gilles Dowek, Murdoch J. Gabbay, Dominic P. Mulligan

Source watermark: DRAFT

Abstract

Nominal terms extend first-order terms with binding. They lack some properties of first- and higher-order terms: Terms must be reasoned about in a context of ‘freshness assumptions’; it is not always possible to ‘choose a fresh variable symbol’ for a nominal term; it is not always possible to ‘α-convert a bound variable symbol’ or to ‘quotient by α-equivalence’; the notion of unifier is not based just on substitution.

Permissive nominal terms closely resemble nominal terms but they recover these properties, and in particular the ‘always fresh’ and ‘always rename’ properties. In the permissive world, freshness contexts are elided, equality is fixed, and the notion of unifier is based on substitution alone rather than on nominal terms’ notion of unification based on substitution plus extra freshness conditions.

We prove that expressivity is not lost moving to the permissive case and provide an injection of nominal terms unification problems and their solutions into permissive nominal terms problems and their solutions.

We investigate the relation between permissive nominal unification and higher-order pattern unification. We show how to translate permissive nominal unification problems and solutions in a sound, complete, and optimal manner, in suitable senses which we make formal.

Keywords: Nominal unification, higher-order pattern unification, permissive nominal techniques

$Thanks to the anonymous referees.

1. Introduction

1.1. About nominal terms and permissive nominal terms

Many formal languages feature names and binding: examples include quantification, λ-abstraction, sets comprehension {x | φ(x)}, and process-calculi name-hiding. Binding is ubiquitous, because variables are there to be bound or substituted.

In contrast, variables cannot be bound in first-order terms: In first-order logic, variables are bound in propositions by quantifiers and not at all in terms; first-order rewriting does not allow binding as it is based on first-order terms; and, many programming languages and proof systems allow datatypes of terms, but only of first-order terms.

This motivates logics where variables can be bound by any function or predicate symbol [9], extensions of rewriting on terms with binders [28, 30, 10], and programming languages and proof systems allowing datatypes with binders [36, 31, 39, 27, 35] and more generally, definitions of a notion of term where variables may be bound.

In particular, this motivates nominal terms [40]. They are designed to directly represent informal schematic specifications. For example:

Informal equality: If y ∉ fv(t) then λx.t is α-equivalent to λy.[y/x]t. Nominal terms: b#X ⊢λ[a]X = λ[b](b a) · X Permissive: λ[a]XS = λ[b](b a) · XS, where b ∉S

Informal unification: Which t and u make λx.λy.(y t) equal to λx.λx.(x u)? Nominal unification: ∅⊢λ[a]λ[b](b X) ?= λ[a]λ[a](a Y) Permissive: λ[a]λ[b](b XS) ?= λ[a]λ[a](a Y S) (here, a ∈S, b ∈S) The first example is part of the usual specification of α-equivalence. The second example is from [40]. Definitions of nominal and permissive nominal terms will follow.

Nominal terms have been explored in logic-programming [7], rewriting [10], logic [19, 21], and elsewhere.

An intuition of the translation from informal specification to (permissive) nominal terms is as follows:

• Object-level variable symbols x and y correspond to atoms a and b (Definition 2.1).

• Meta-level variables t and u correspond to unknowns X. Substitution of unknowns is capturing, which models the effect of writing “set t to be x in λx.t; we get λx.x”. Similarly, (λ[a]X)[X:=a] ≡ [a]a. Atoms and unknowns are two distinct levels of variable, just as object- and meta-level are two levels.

• Conditions like x ∉ fv(t) correspond to freshness conditions b#X in nominal terms. b#X is a restriction, which is enforced on the notion of substitution, on what X may be instantiated to. b#X is a promise to instantiate X only to terms for which b is fresh (see the conditions ‘∇′ ⊢θ(∇)’ in Lemma 2.14, and ‘∇⊢a#θ(t)’ in Definition 3.1 of [40]).

• Object-level renaming [y/x] is modelled by swapping (b a) (which maps b to a, a to b, and all other atoms c to themselves; Definition 2.5). Swappings are bijective on atoms and invertible, unlike renamings, and for this reason they are naturally capture-avoiding.1 This gives them attractive mathematical properties which can be exploited in the mathematical theory. Using them to manage renaming in α-equivalence is a conspicuous feature of nominal techniques and follows [25, 40]. The reader can safely think of [y/x] as corresponding to (b a) so long as b (y) is sufficiently fresh. It is notable that freshness side-conditions in informal practice seem to appear exactly in those places in which they would be necessary for this to work.

• λ and application are term-formers (function-symbols). In the examples above we write application infix, as is standard.

Permissive nominal terms differ in two ways from nominal terms:

• Difference 1. Freshness information is fixed once and for all, and associated to unknowns in the manner of a sorting or typing annotation. For example: b#X ⊢X is a nominal term-in-freshness context X whose freshness context insists that b not occur free in X. A corresponding permissive nominal term is XS where S is a set of atoms we call the permission set of X, and b ∉S.

• Difference 2. Permission sets are sets of atoms that are both infinite and co-infinite (see Remark 2.23; S ⊆A is co-infinite when A \ S is infinite).

These combine with consequences which we now discuss.

1.2. Difference 1: about fixing freshness contexts

Difference 1 on its own is mostly a matter of presentation. It is mentioned already in [40, Remark 2.6] (there, we would obtain ‘permission sets’ A such that A is infinite and A \ A is finite). It is still worth reflecting briefly on what that difference in presentation means, for some example results. Part 2 of Lemma 2.14 from [40] reads as follows:

If ∇′ ⊢σ(∇) and ∇⊢a#t, then ∇⊢a#σ(t).

The corresponding result in this paper (Lemma 3.3) reads as follows:

fa(rθ) ⊆fa(r).

Parts 1 to 3 of Lemma 2.7 from [40] read as follows:

1. If ∇⊢a#π · t then ∇⊢π-1 · a#t.

2. If ∇⊢π · a#t then ∇⊢a#π-1 · t.

3. If ∇⊢a#t then ∇⊢π · a#π · t.

These three statements correspond to one result in this paper (Lemma 2.17) which reads as follows:

fa(π · r) = π · fa(r).

To us, the ‘permissive’ versions seem shorter and clearer.

In fact there is a little more to Difference 1 than presentation. If freshness contexts are fixed then some ‘consistency’ properties of the same term across different freshness contexts become irrelevant. For instance consider the weakening and strengthening results for freshness contexts like those in Subsection 3.2 of [24] or Subsection 3.3.2 of [21]; if we had used permissive nominal terms, then these results would have been irrelevant and could have been omitted.

1.3. Difference 2: about choosing fresh atoms

The reader used to nominal terms can think of Difference 2 as allowing and requiring infinite freshness contexts.2 Together with Difference 1, this gives us two key properties which are absent in [40]:

• An infinite supply of fresh atoms is guaranteed for every term. There is no need to change a freshness context to obtain fresh atoms, because they are already there.

• Terms may be directly quotiented by α-equivalence. They also become susceptible to the nominal inductive reasoning principles of [25].

This matters. The nominal terms as presented in [40] cannot be quotiented by α-equivalence, and cannot be subjected to the nominal inductive principles of nominal abstract syntax [25]. In this respect, they are less tractable than first-order or higher-order terms, which can be.

True enough, it is always possible to ‘add a fresh atom to the freshness context’ in nominal terms and rename, but this causes similar difficulties to those encountered in α-renaming on name-carrying syntax.

This is potentially a problem for the viability of any reasoning on, programming on, or extensions of nominal terms. We have experienced this ourselves in [24, 23].

It becomes possible to argue against nominal terms because they appear to be harder to manipulate than the language they describe, and in particular, because they reintroduce the problem of α-equivalence which nominal abstract syntax was originally designed to solve.

The existence of permissive nominal terms demonstrates that in fact, the apparent problem is just an artefact of the way matters were set up in [40]. We can quotient permissive nominal terms by α-equivalence. In fact we can also use nominal inductive reasoning principles to reason on permissive nominal terms [22, 15].

Turning to the issue of fresh atoms; in the world of finite freshness contexts based on [40], we may always extend freshness contexts if we want more fresh atoms. This is made formal for example by (fr) in [21, Figure 2] and (Tfr) in [24, Figure 1].

We can observe the effects of this solution to the problem of generating fresh atoms, by considering the mathematics in [24]. (Tfr) is not a syntax-directed rule and this complicates case-analysis on derivations. Subsection 5.1 of [24] is devoted to controlling this issue. Further, since freshness contexts may change during a proof, it is necessary to account for these changes in statements and proofs of results; the results in Subsection 5.3 of [24] therefore contain an existential quantification over ‘sufficiently freshened’ freshness contexts.

In fact we should recognise what happens in [24] because it is typical of something we have seen before. A ‘state’ of ‘generated atoms’ is being carried by the freshness context and threaded through all the proofs. This is a situation familiar from implementing languages with binding; we may need to keep track of the ‘generated fresh atoms’ so that when we generate a new one we can easily pick an ‘even fresher atom’. We thread through the program a ‘state’ of ‘generated atoms’ (see for instance the ‘fresh monad’ in Cheney’s FreshLib [5]). This is undesirable if it can be avoided, because it interferes with the state-free style of functional programming, forces us to program more sequentially, and it complicates code.3 This is what motivated FreshML [38, 39].

The paper [24] is not an isolated case. Similar issues have arisen in proofs on the two-level lambda-calculus [23] and in other work [19, 18, 20]. Furthermore, the ‘fresh atom’ issue is not restricted to proofs:

A prototype implementation of permissive nominal terms and their unification by the third author [33] has a direct mechanism for generating a fresh name for any permissive term. Even in a pure functional language like Haskell, no monadic programming is needed just to generate fresh names.

Calvès recently wrote the Haskell Nominal Toolkit (HNT) [2], which provides efficient implementations of several algorithms on nominal terms. The HNT provides an elegant programming interface for manipulating nominal terms, and any efficient implementation of permissive nominal terms would also likely expose a similar API to the programmer.

However, Calvès’ underlying model is the nominal term and this is reflected in the types of programs written with the HNT. Whereas core functions in the implementation of permissive nominal terms (e.g. unification and alpha-equivalence checks) are pure, the types of their HNT counterparts are heavily monadic, and explicit freshness contexts must also be passed around.

As an example, we compare the types (1) of the alpha-equivalence check function from the HNT and (2) of the implementation of permissive nominal terms:4

(1) alpha′check :: (Show t, Eq t, Ord a, Ordv) ⇒ FrsCtxt v a →

Term a t v →Term a t v →

CS r (ExtB l e (ErrorT [Char])) m ()

(2) aeq :: (Eq a, Permissive b) ⇒ Term a b → Term a b → Bool

To us, the ‘permissive’ type seems shorter and clearer. An implementation of the HNT, based on permissive nominal terms, would likely present less daunting types to the programmer, and removing the burden of handling freshness contexts would likely make code shorter and neater.

1.4. Permissive nominal terms in this paper

Permissive nominal terms are designed to deal with these issues. Their theory of α-equivalence and ‘fresh atom of’ restore the good features of nominal abstract syntax without losing any expressivity or computational properties.

In fact, permissive nominal terms are ‘best possible’ in a certain sense: in [22, 15] we demonstrate how the atoms-abstraction construction from [25] can be applied directly to permissive nominal terms syntax. That is, in [22, 15] we show that it is possible to take [a]r to be literally the Gabbay-Pitts atoms-abstraction of a in the set that is the abstract syntax tree r, so that α-equivalence is literal identity, and the definition of permissive nominal terms syntax (Definition 2.6) becomes a nominal abstract syntax style inductive datatype of syntax-with-binding.

In this paper we introduce permissive nominal terms. We study their theory of unification. Given any new syntax, it is important to connect it to existing denotations. Therefore, we relate permissive nominal terms and their unification to nominal unification, and to unification of higher-order patterns. Denotations in nominal sets will be the topic of a separate manuscript [15] (some elements are also in [22]).

The contributions are as follows:

• We introduce permissive nominal terms Definitions 2.6, along with theories of α-equivalence and freshness with the ‘always fresh’ and ‘always rename’ properties discussed above (Corollaries 2.14 and 2.15).

• It may look like permissive nominal terms are infinite, because the S in XS in Definition 2.6 is an infinite set. In Remark 2.7 we mention that they are just as ‘finite’, and computable-upon, as nominal terms.

• We develop a notion of unification (Definition 6.6). We use a simplified notion of unifier (Definition 3.9) which is more like the notion of unifier from first- and higher-order unification in that it is based just on a substitution, as compared to the notion of unifier used in [40], which is not.

• We make precise the connection between nominal terms and permissive nominal terms by translating nominal terms, nominal unification problems, and their solutions, to the permissive context (Definition 4.6). We verify that no expressivity is lost (Theorem 4.16).

• We connect permissive nominal terms and higher order patterns [32, 31] (Definition 8.3) by translating permissive nominal terms, unification problems, and their solutions, to a very general notion of untyped pattern unification problems and their solutions (Definition 9.1). We also prove that this translation is ‘best possible’ and ‘complete’ in senses which we make formal (Theorems 8.14 and Theorems 9.16 and 9.30).

1.5. Map of the paper

The paper is organised as follows: We introduce permissive nominal terms in Section 2. Notable results are the ‘always fresh’ and ‘always rename’ properties for terms (Corollaries 2.14 and 2.15 respectively).

In Section 3 we introduce technical definitions and results which will prove useful in the development of the unification algorithm, including permissive nominal terms substitution (Definition 3.1), unification problems and their solutions (Definition 3.9).

We clarify the relationship between nominal and permissive nominal terms in Section 4, by injecting nominal terms into permissive nominal terms (Definition 4.6 onwards). We also elucidate the relationship between solutions of nominal unification problems, based on subsititution+freshness, and solutions of permissive nominal unification problems, based on substitution alone (Definition 4.12).

In Sections 5 and 6 we present an algorithm to compute most general solutions to permissive nominal unification problems (Definition 6.6). We prove it correct in Theorem 6.25.

We define λ-terms syntax (Definition 7.1) in Section 7, and higher-order patterns (Definition 7.19). Section 8 translates from permissive nominal term syntax to λ-term syntax (Definition 8.3 onwards). We prove that this translation is ‘best possible’, in a suitable sense which we make formal (Theorem 8.14).

Section 9 relates the solutions of higher-order pattern unification with solutions of permissive nominal unification (Definition 9.1). We show that the instantiation ordering, hence the property of solutions being ‘more general’, is preserved by the translation (Corollary 9.5). We prove a soundness and weak completeness result (Theorem 9.16). Finally, we refine this to a more complex but more powerful completeness result (Theorem 9.30).

In Section 10, we conclude and suggest ideas for future work.

2. Permissive nominal terms

We set up the syntax of permissive nominal terms (Definition 2.6) and their notion of α-equivalence =α, which does not require a freshness context (Definition 2.13). We prove that permissive nominal terms have the ‘always fresh’ and ‘always rename’ properties (Corollaries 2.14 and 2.15). Finally, we verify that =α is an equivalence relation; this mirrors the result for nominal terms [40, Theorem 2.11], though the proof-method is based on [10, Subsection 3.2]. Where we omit proofs they are routine (or see a technical report [8], or [10]).

Note the two notions of ‘free variables of’; fa(r) is the free atoms in r, and fV (r) is the free unknowns in r (Definitions 2.11 and 2.12). This reflects the two-level structure of nominal terms familiar from previous work [40].

Definition 2.1

Fix two disjoint countably infinite sets A< and A> of atoms and write

A = A< ⊎A>.

(Here ⊎ denotes disjoint set union) a, b, c, . . . will range over distinct elements of A (we call this the permutative convention).

Definition 2.2

Define P by

P = {(A< \ A) ∪B | A ⊆A<, B ⊆A>, A, B finite}.

Call elements of P permission sets. S, S′, T will range over permission sets.

Call S ⊆A co-infinite when A \ S is infinite. P is a set of infinite, co-infinite sets of atoms.5

Definition 2.3

For each permission set S fix a disjoint countably infinite set of unknowns of sort S. XS, Y S, ZS, will range over distinct unknowns of sort S. If S ≠ S′ then there is no particular connection between XS and XS′. V will range over finite sets of unknowns (we use this from Section 5 onwards).

Definition 2.4

Suppose f is a function from atoms to atoms. Define nontriv(f) by:

nontriv(f) = {a | f(a) ≠ a}

This has also been called the support of π [25].

Definition 2.5

A (finite) permutation is a bijection on atoms such that nontriv(π) is finite. π and π′ will range over finite permutations.

Write π◦π′ for the composition of π and π′ (so (π◦π′)(a) = π(π′(a))). Write id for the identity permutation (so id(a) = a always). Write (a b) for the swapping permutation that swaps a and b.

Definition 2.6

Fix a set of term-formers. f, g, h will range over distinct term-formers.

Define (permissive nominal) terms by:

r, s, t, . . . ::= a | f(r, . . . , r) | [a]r | π · XS

We write ≡ for syntactic identity; r ≡s when r and s denote identical terms. Note that XS (the unknown) is not a term, however π · XS is a term and in particular id · XS is a term, which we may write as XS.

Remark 2.7

Permissive-nominal terms are finite. They are finitely branching finitely deep trees.

Equality of permissive-nominal terms may be calculated in finite time. Permission sets trivially admit a finite representation as the pair of finite sets A and B in Definition 2.2.

In an implementation of the algorithms in this paper by Mulligan [33], atoms are implemented concretely as numbers. A< is identified with the even numbers. Permission sets are represented finitely as their finite deviation from A<.

Another, quite elegant, presentation is possible using exclusive or; see Remark 2.23.

Remark 2.8

See Section 4 for a comparison between permissive nominal terms of Definition 2.6 and ‘ordinary’ nominal terms [40]. Atoms represent variable symbols; term-formers functions; unknowns meta-variables; abstraction [a]r binding; and π · XS a meta-variable with a suspended substitution, like ‘t[y/x]’. For example, suppose term-formers app and λ: − app(a, b) can represent ‘xy’ (x applied to y). − app(lam([a]a), b) can represent ‘(λx.x)y’ (identity applied to y). −λ([a]XS) can represent ‘λx.t’ if a ∈S, and ‘λx.t, where x ∉ fv(t)’ if a ∉S.

Definition 2.9

Define a permutation action by:

π · a ≡π(a) π · (f(r1, . . . , rn)) ≡f(π · r1, . . . , π · rn)π · [a]r ≡[π(a)](π · r) π · (π′ · XS) ≡(π◦π′) · XS
Definition 2.10

If S ⊆A, define the pointwise action by:

π · S = {π(a) | a ∈S}
Definition 2.11

Define free atoms fa(r) by:

fa(a) = {a} fa(f(r1, . . . , rn)) = ⋃1≤i≤n fa(ri)fa([a]r) = fa(r)\{a} fa(π·XS) = π·S

Note that fa(π · XS) = π · S. Thus, an intuition for fa(r) is ‘the free atoms we can have after instantiation’.

Definition 2.12

Define free unknowns fV (r) by:

fV (a) = ∅ fV (f(r1, . . . , rn)) = fV (r1) ∪· · · ∪fV (rn)fV ([a]r) = fV (r) fV (π·XS) = {XS}
Definition 2.13

If A ⊆A, define π|A, π restricted to A, to be:

π|A(a) = π(a) when a ∈Aπ|A(a) undefined when a ∈A \ A

Define α-equivalence =α inductively by the rules in Figure 1.

Corollaries 2.14 and 2.15 are properties that ‘ordinary syntax’ has, that nominal terms do not have, and that permissive nominal terms recover; we can always choose a fresh variable, and we can always α-rename with it.

Corollary 2.14

For any r1, ..., rn there exist infinitely many b such that b ∉⋃{fa(ri) | 1 ≤ i ≤n}.

(=αaa)a =α ar1 =α s1· · · rn =α sn(=αf)f(r1, . . . , rn) =α f(s1, . . . , sn)r =α s(=α[a])[a]r =α [a]s(b a) · r =α s (b ∉fa(r)) (=α[b]) [a]r =α [b]s(π|S = π′|S)(=αX)π · XS =α π′ · XS
Figure 1: Derivable α-equivalence on permissive nominal terms.
Proof

Define atoms(r) inductively by:

atoms(a) = {a} atoms(f(r1, . . . , rn)) = atoms(r1) ∪. . . ∪atoms(rn)atoms([a]r) = atoms(r) ∪{a} atoms(π · XS) = nontriv(π)

It is not hard to prove by induction on term syntax that fa(ri) ⊆ atoms(ri) ∪⋃{S | XS ∈ fV (ri)} for 1 ≤i ≤n. The syntax of ri is finite so atoms(ri) is finite, and also fV (ri) is finite. It follows that ⋃{S | XS ∈ fV (ri) for some i} is co-infinite. The result follows.End of proof

Later on, we will often need to say ‘choose an atom fresh’ (see for example Definition 4.14). When we do this, we are using Corollary 2.14.

Corollary 2.15 expresses that we can always α-rename:

Corollary 2.15

For any r and a there exists infinitely many fresh b (so b ∉ fa(r)) such that for some s, [a]r =α [b]s.

Proof

Immediate, by Corollary 2.14 and (=α[b]).End of proof

Our changes do not affect basic results about nominal terms [40]; the proofs of the following lemmas are by routine inductions (see [8] for details):

Lemma 2.16

1. id · r ≡r

2. π′ · (π · r) ≡ (π′◦π) · r

Lemma 2.17

π · fa(r) = fa(π · r).

Lemma 2.18

If r =α s then π · r =α π · s.

Lemma 2.19

If r =α s then fa(r) = fa(s).

Lemma 2.20

If π|fa(r) = π′|fa(r) then π · r =α π′ · r.

Proposition 2.21

=α is transitive, reflexive, and symmetric.

Proof

See Appendix Appendix A. We use Lemmas 2.16, 2.17, 2.18, 2.19 and 2.20.End of proof

2.1. Foundations of permission sets

Remark 2.22

The Fraenkel-Mostowski sets model used in the work which introduced nominal techniques [25] famously does not admit sets like S and T, because they do not have finite support. It is not an issue in this paper because we are not concerned with representing permissive nominal syntax-up-to-binding. Permissive nominal syntax-up-to-binding can be constructed though; see [22, 15]. See also generalisations of nominal sets by the second author [11, 13] or by Cheney ([3, Section 3], or [6]).

Remark 2.23

Define S ∆T (the exclusive or) by

S ∆T = (S \ T) ∪(T \ S).

It is a fact that for every S ∈P, the set S ∆A< is a finite set of atoms, and it is the unique finite set such that A< ∆(S ∆A<) = S. This gives a nice finite representation of permission sets, alternative to the two mentioned in Remark 2.7.

3. Substitutions, problems, and solutions

3.1. Substitutions

The purpose of an unknown XS is to represent an ‘unknown term/unknown element’. We therefore define a substitution action for unknowns. Consistent with nominal terms, substitution for unknowns is capturing for abstraction by atoms.

Definition 3.1

A substitution θ is a function from unknowns to terms such that fa(θ(XS)) ⊆ S always (so S in XS describes the ‘permission’ we have to instantiate XS, namely to terms with free atoms in S). θ, θ′, θ1, θ2, will range over substitutions.

Write id for the identity substitution mapping XS to id · XS always. It will always be clear whether id means the identity substitution or permutation. Suppose fa(t) ⊆S. Write [XS:=t] for the substitution such that

[XS:=t](XS) ≡t and [XS:=t](Y T ) ≡id · Y Tfor all other Y T .

‘fa(θ(XS)) ⊆S’ looks absent in nominal terms theory ([40, Definition 2.13], [10, Definition 4]), yet it is there: see the conditions ‘∇′ ⊢θ(∇)’ in Lemma 2.14, and ‘∇⊢ a#θ(t)’ in Definition 3.1 of [40]. More on this in Section 4.

Definition 3.2

Define a substitution action on terms by:

aθ ≡a f(r1, . . . , rn)θ ≡f(r1θ, . . . , rnθ)([a]r)θ ≡[a](rθ) (π·XS)θ ≡π·θ(XS)

Note that XSθ means ‘θ acting on id · XS’; θ(XS) means ‘the value of function θ at XS’.

Lemma 3.3

fa(rθ) ⊆ fa(r).

Proof

See Appendix Appendix A. We use Lemma 2.17.End of proof

Lemma 3.4

π · (rθ) ≡ (π · r)θ.

Proof

By induction on r.End of proof

Lemma 3.5

If θ1(XS) =α θ2(XS) for all XS ∈ fV (r), then rθ1 =α rθ2.

Proof

By induction on r.

• The cases a and f(r1, . . . , rn) are straightforward.

• The case [a]r. Suppose θ1(XS) =α θ2(XS) for every XS ∈ fV ([a]r). fV ([a]r) = fV (r) so by inductive hypothesis rθ1 =α rθ2. By (=α[a]) also [a](rθ1) =α [a](rθ2). The result follows by Definition 3.2.

• The case π · XS. By assumption, θ1(XS) =α θ2(XS). Using Lemma 2.18, π · (θ1(XS)) =α π · (θ2(XS)). By Definition 3.2 (π · XS)θ1 =α (π · XS)θ2, as required.End of proof

Lemma 3.6

If r =α s then rθ =α sθ.

Proof

By induction on the derivation of r =α s. We consider one case:

• The case (=α[b]). Suppose (b a) · r =α s and b ∉ fa(r). Then ((b a) · r)θ =α sθ by assumption. By Lemma 3.4, (b a) · (rθ) =α sθ. By Lemma 3.3, b ∉ fa(rθ), therefore [a](rθ) =α [b](sθ) by (=α[b]). By Definition 3.1, [a](rθ) ≡ ([a]r)θ, and the result follows.End of proof

Definition 3.7

Define composition θ1◦θ2 by (θ1◦θ2)(XS) ≡ (θ1(XS))θ2.

Lemma 3.8

(rθ)θ′ ≡r(θ◦θ′).

Proof

By induction on r. We consider one case:

• The case π · XS

(π · XS)(θ◦θ′) ≡π · (θ◦θ′)(XS) Definition 3.2≡π · (θ(XS)θ′) Definition 3.7≡(π · θ(XS))θ′Lemma 3.4≡((π · XS)θ)θ′Lemma 3.4End of proof

3.2. Unification problems, and solutions

This is a brief subsection, but it is useful: A solution to Pr ‘makes the equalities valid’, as for first- and higher-order unification. This simplifies the nominal unification notion of solution (Definition 4.11 or [40, Definition 3.1]) based on ‘a substitution + a freshness context’. We prove results about these definitions in Sections 4 (connection with nominal unification) and 6 (unification algorithm).

Definition 3.9

An equality is a pair r?= s. A problem Pr is a finite multiset of equalities. Define Prθ by:

Prθ = {rθ?= sθ | r?= s ∈Pr}

Say that θ solves Pr when r?= s ∈Pr implies rθ =α sθ. Write Sol(Pr) for the set of solutions to Pr. Call Pr solvable when Sol(Pr) is non-empty.

4. Relation to nominal terms

In Subsection 3.2 we stated what a permissive nominal unification problem is, and what a solution to it is. We now make precise a mathematical sense in which nominal terms and their unification can be considered a subsystem of permissive nominal terms and their unification.

We recall the notions of nominal term and nominal unification problem (Definitions 4.2 and 4.11). We translate from the ‘nominal world’ to the ‘permissive nominal world’ (Definition 4.6). Theorem 4.9 expresses how this translation is sound and complete for respective notions of α-equivalence. Theorem 4.16 then shows that furthermore, solutions to unification problems are preserved 1-1 across the translation.

Recall from the Introduction that in nominal terms we often to enrich the freshness context. An interesting feature of Definition 4.6 is how it maps nominal terms to permissive nominal terms with free atoms in A<, which is an infinite, co-infinite set of atoms. One way to view the interpretation of Definition 4.6 is therefore this: A< is ‘the atoms we had available so far’ (any other permission set would do as well) and A> is ‘the atoms with which we will extend the freshness context, in the future’. Both these sets are infinite, and syntax is finite, so it is not absolutely necessary to explicitly separate them: permissive nominal terms do this, for each fixed permission set S; nominal terms do not.

4.1. Alpha-equivalence between nominal and permissive nominal terms

Definition 4.1

Fix a countably infinite set of nominal atoms, ˙A. ˙a, ˙b, ˙c, . . . will range over distinct nominal atoms.

Fix a bijection ι between ˙A and any permission set. For concreteness we will suppose it is A< from Definition 2.2 but any permission set will do as well.

Fix a countably infinite set of nominal unknowns. ˙X, ˙Y , ˙Z, . . . will range over distinct nominal unknowns. A nominal permutation is a bijection ˙π on ˙A such that nontriv( ˙π) is finite. ˙π, ˙π′, ˙π′′, . . . will range over permutations.

Write ˙π-1 for the inverse of ˙π, ˙id for the identity permutation, and ˙π◦˙π′ for function composition, as is standard. For example, ( ˙π◦˙π′)(˙a) = ˙π( ˙π′(˙a))

Definition 4.2

Define nominal terms by:

˙r, ˙s, ˙t ::= ˙a | ˙π · ˙X | [˙a] ˙r | f( ˙r, . . . , ˙r)
Definition 4.3

Define a permutation action on nominal terms by:

˙π · ˙a ≡˙π(˙a) ˙π · f( ˙r1, . . . , rn) ≡f( ˙π · ˙r1, . . . , ˙π · rn)˙π · [˙a] ˙r ≡[ ˙π(˙a)]( ˙π · ˙r) ˙π · ( ˙π′ · ˙X) ≡( ˙π◦˙π′) · ˙X

Write ≡ for syntactic identity. f ranges over term-formers (Definition 2.1).

Definition 4.4

A freshness is a pair ˙a# ˙r. A freshness context is a finite set of freshnesses of the form ˙a# ˙X. Define derivable freshness on nominal terms by the rules in Figure 2.

(#ḃ)∆⊢˙a#˙b∆⊢˙a# ˙ri(1 ≤i ≤n) (#f) ∆⊢˙a#f( ˙r1, . . . , ˙rn)(#[ȧ])∆⊢˙a#[˙a] ˙r∆⊢˙a# ˙r(#[ḃ])∆⊢˙a#[˙b] ˙r( ˙π-1(˙a)# ˙X ∈∆) (#Ẋ) ∆⊢˙a# ˙π · ˙X
Figure 2: Derivable freshness on nominal terms
(=ȧ)∆⊢˙a = ˙a∆⊢˙ri = ˙si(1 ≤i ≤n)(=f)∆⊢f( ˙r1, . . . , ˙rn) = f( ˙s1, . . . , ˙sn)∆⊢˙r = ˙s(=[ȧ])∆⊢[˙a] ˙r = [˙a] ˙s∆⊢(˙b ˙a) · ˙r = ˙s ∆⊢˙b# ˙r (=[ḃ]) ∆⊢[˙a] ˙r = [˙b] ˙s(˙a# ˙X ∈∆for every ˙π(˙a) ≠ ˙π′(˙a)) (=Ẋ) ∆⊢˙π · ˙X = ˙π′ · ˙X
Figure 3: Derivable equality on nominal terms

Definition 4.5 repeats [40, Figure 2], up to differences in presentation:

Definition 4.5

An equality is a pair ˙r = ˙s. Define derivable equality on nominal terms by the rules in Figure 3.

Definition 4.6

Define a mapping ⟦ ˙π⟧ from nominal permutations to permissive nominal permutations by:

⟦ ˙π⟧(ι(˙a)) = ι( ˙π(˙a)) ⟦ ˙π⟧(c) = c all c ∈A>

Define an interpretation ⟦ ˙r⟧∆ by:

⟦˙a⟧∆≡ι(˙a) ⟦f( ˙r1, . . . , ˙rn)⟧∆≡f(⟦ ˙r1⟧∆, . . . , ⟦ ˙rn⟧∆) ⟦[˙a] ˙r⟧∆≡[ι(˙a)]⟦ ˙r⟧∆⟦ ˙π · ˙X⟧∆≡⟦ ˙π⟧ · XSwhere S = A< \ {ι(˙a) | ˙a# ˙X ∈∆}

Here, we make a fixed but arbitrary choice of XS for each ˙X, injectively so that ⟦X ˙⟧∆ and ⟦Y ˙⟧∆ are always distinct.

⟦ ˙r⟧∆ commutes with permutation and it preserves and reflects freshness:

Lemma 4.7

⟦ ˙π⟧ · ⟦ ˙r⟧∆≡⟦ ˙π · ˙r⟧∆

Proof

By induction on ˙r.End of proof

Lemma 4.8

ι(˙a) ∉ fa(⟦ ˙r⟧∆) if and only if ∆⊢˙a# ˙r.

Proof

See Appendix Appendix A.End of proof

Theorem 4.9 states that α-equivalent nominal-terms-in-context map precisely to α-equivalent permissive nominal terms:

Theorem 4.9

⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ if and only if ∆⊢˙r = ˙s.

Proof

See Appendix Appendix A. We use Lemmas 4.7 and 4.8.End of proof

4.2. Substitutions and solutions between nominal and permissive nominal unification problems

Definition 4.10

A substitution ˙θ is a function from nominal unknowns to nominal ˙

terms such that { ˙X | ˙θ( ˙X) ≢ id · ˙X} is finite. ˙θ, ˙θ′, ˙θ′′, . . . will range over nominal substitutions.

Write ˙id for the identity, mapping ˙X to ˙id · ˙X. Define a substitution action on nominal terms by:

˙a ˙θ ≡˙a f( ˙r1, . . . , ˙rn) ˙θ ≡f( ˙r1 ˙θ, . . . , ˙rn ˙θ) ([˙a] ˙r) ˙θ ≡[˙a]( ˙r ˙θ) ( ˙π· ˙X) ˙θ ≡˙π· ˙θ( ˙X)
Definition 4.11

A unification problem ˙Pr is a finite multiset of freshnesses and equalities. A solution to ˙Pr is a pair (∆, ˙θ) such that ∆⊢˙a# ˙r ˙θ for every ˙a# ˙r ∈˙Pr, and ∆⊢˙rθ = ˙sθ for every ˙r = ˙s ∈˙Pr. This follows [40, Definition 3.1].

Definition 4.12

We extend the interpretation of Definition 4.6 to solutions of nominal unification problems by:

⟦(∆, ˙θ)⟧(XS) ≡⟦ ˙θ(X)⟧∆if id·XS≡⟦X⟧∆⟦(∆, ˙θ)⟧(Y T ) ≡id·Y T otherwise
Lemma 4.13

⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ ≡⟦ ˙r ˙θ⟧∆.

Proof

See Appendix Appendix A.End of proof

Definition 4.14

Define ⟦Pr ˙⟧∆ by mapping ˙r = ˙s to ⟦ ˙r⟧∆?= ⟦ ˙s⟧∆ and mapping ˙a# ˙r to (b ι(˙a)) · ⟦ ˙r⟧∆?= ⟦ ˙r⟧∆, for some choice of fresh b (so b ∉ fa(⟦ ˙r⟧∆); in fact, it suffices to choose some b ∉A<).

Lemma 4.15

Suppose b ∉ fa(r). Then a ∉ fa(r) if and only if (b a) · r =α r.

Proof

See Appendix Appendix A. We use Lemmas 2.16 and 2.17, and Proposition 2.21.End of proof

No solutions go missing, moving from the nominal to the permissive nominal world:

Theorem 4.16

(∆, ˙θ) solves ˙Pr if and only if ⟦(∆, ˙θ)⟧ solves ⟦Pr ˙⟧∆.

Proof

If (∆, ˙θ) solves ˙Pr then ⟦(∆, ˙θ)⟧ solves ⟦ ˙Pr⟧∆. Suppose ∆⊢˙r ˙θ = ˙sθ ˙. Using Lemma 4.13 and Theorem 4.9, ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α ⟦ ˙s⟧∆⟦(∆, ˙θ)⟧.

Suppose ∆⊢a# ˙r ˙θ. Using Lemma 4.8, ι(˙a) ∉ fa(⟦ ˙r ˙θ⟧∆). By Lemma 4.13, ι(˙a) ∉ fa(⟦ ˙r⟧∆⟦(∆, ˙θ)⟧). By Lemma 4.15, (b ι(˙a)) · ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧, where b is fresh (see Definition 4.14). By Lemma 3.4, ((b ι(˙a)) · ⟦ ˙r⟧∆)⟦(∆, ˙θ)⟧ =α ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧. The result follows.

If ⟦(∆, ˙θ)⟧ solves ⟦Pr ˙⟧∆ then (∆, ˙θ) solves ˙Pr. Suppose that ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α ⟦ ˙s⟧∆⟦(∆, ˙θ)⟧. By Theorem 4.9, ∆⊢rθ = sθ.

Suppose ((b ι(˙a))·⟦ ˙r⟧∆)⟦(∆, ˙θ)⟧ =α ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧. By Lemma 3.4, (b ι(˙a))·⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧. By Lemma 4.15, ι(˙a) ∉ fa(⟦ ˙r⟧∆⟦(∆, ˙θ)⟧). Using Lemma 4.13, ι(˙a) ∉ fa(⟦ ˙r ˙θ⟧∆). By Lemma 4.8, ∆⊢a# ˙r ˙θ, and the result follows.End of proof

5. Support inclusion problems

The freshness symbol a#r used in [25] and [40] is ambiguous. Do we mean − ‘a is not free in the syntax of r’ or − ‘a is not in the support of the denotation of r’? The first option can be called intensional or syntactic freshness; the second option can be called extensional or semantic freshness.

In nominal terms this question is slightly obscured because a ‘free atoms of’ function on terms is hard to define. In permissive nominal terms we can easily define a ‘free atoms of’ function; see Definition 2.11, fa(r).

We have seen in Section 4 how nominal terms’ notion of freshness ‘a#r’ translates to a syntactic freshness ‘a ∉ fa(r)’.

Nominal terms unification solves equality and freshness problems within a single rewrite system. When we designed the permissive nominal terms unification algorithm, we solve these separately — one algorithm is described in this section, the other (for equalities) is described in Section 6. This is simply a design choice, but it is informed by the translation of # to a syntactic judgement, described above. For, in future it may be useful to consider unification modulo equational theories (and note that semantic freshness can be easily captured using equations; see [17, Theorem 5.5] or [21, Theorem 4.52]). In the presence of equational theories, because we have factored out fragment of the computation that checks ‘a ∉ fa(r)’, that fragment will remain modular and unaffected by the imposition of equality axioms.

Recall from Definition 3.1 that fa(θ(XS)) ⊆ fa(XS) = S, and from Lemma 3.3 that instantiation must reduce the set of free atoms. We will exhibit an algorithm which, intuitively, solves the problem “please make fa(rθ) ⊆T true” (Definition 5.9 and Lemma 5.7). In fact the algorithm calculates solutions that are most general, in a sense made formal in Theorem 5.20.

Next, in Section 6, we construct an algorithm to solve equality problems.

5.1. Simplification reduction and normal forms

Definition 5.1

A support inclusion is a pair r ⊑T of a term and a permissions set. A support inclusion problem is a finite multiset of support inclusions; Inc will range over support inclusion problems. Call θ a solution to Inc when fa(rθ) ⊆T for every r ⊑T ∈

Inc. Write Sol(Inc) for the solutions of Inc. Call Inc solvable when Sol(Inc) ≠ ∅, and non-trivial when nf (Inc) ≠ ∅.

(⊑a) a ⊑T, Inc =⇒Inc (a ∈T)(⊑f) f(r1, . . . , rn) ⊑T, Inc =⇒r1 ⊑T, . . . , rn ⊑T, Inc (⊑[]) [a]r ⊑T, Inc =⇒r ⊑T ∪{a}, Inc(⊑X) π · XS ⊑T, Inc =⇒XS ⊑π-1 · T, Inc (S ⊈π-1 · T, π ≠ id)(⊑X′) π · XS ⊑T, Inc =⇒Inc (S ⊆π-1 · T)
Figure 4: Simplification of support inclusion problems
Definition 5.2

Define a simplification rewrite relation by the rules in Figure 4.

Definition 5.2 can easily be expressed as a type I conditional term rewrite system, according to the classification scheme of [1, Definition 7.1.1]. This becomes evident if we bear in mind that we can represent atoms as numbers, A< as the even numbers, S as the finite set S ∆A< (Remark 2.23), and T as the finite set T ∆A<.

Theorem 5.3

If Inc =⇒ Inc′ then Sol(Inc) = Sol(Inc′).

Proof

First, we make the following claims:

Claim 1: If a ∈T then fa(aθ) ⊆T always. Since fa(aθ) = fa(a) = {a}.

Claim 2: fa(f(r1, . . . , rn)θ) ⊆T if and only if fa(riθ) ⊆T for 1 ≤i ≤n. Since fa(f(r1, . . . , rn)) =

fa(r1) ∪. . . ∪fa(rn), and f(r1, . . . , rn)θ ≡f(r1θ, . . . , rnθ).

Claim 3: fa(([a]s)θ) ⊆T if and only if fa(sθ) ⊆T ∪{a}. Suppose fa(([a]s)θ) ⊆T, therefore

fa([a]sθ) ⊆T. Then fa(sθ) \ {a} ⊆T, therefore fa(sθ) ⊆T ∪{a} and the result follows. The reverse direction is similar.

Claim 4: fa((π · XS)θ) ⊆T if and only if fa(XSθ) ⊆π-1 · T. We consider only one case.

Suppose θ = [XS:=t] and fa(t) ⊆S, therefore fa((π · XS)[XS:=t]) = fa(π · t) hence

fa(π · t) ⊆T by assumption. By Lemma 2.17, π · fa(t) ⊆T, and by Lemma 2.16 and Lemma 2.17, (π-1◦π) · fa(t) ⊆π-1 · T. As π-1◦π = id, we have fa(XS[XS:=t]) ⊆ π-1 · T, and the result follows. Alternatively, suppose fa(t) ⊈S. Then fa((π · XS)[XS:=t]) = fa(π · XS) and π · fa(XS) ⊆T by Lemma 2.17. By Lemmas 2.16 and 2.17, fa(XS[XS:=t]) ⊆π-1 · T, and the result follows. The reverse implication is no harder.

Claim 5: By Definition 3.2 we have fa((π · XS)θ) = fa(π · (XSθ)). If S ⊆π-1 · T then

fa(π·(XSθ)) ⊆T always. Note, S ⊆π-1·T if and only if π·S ⊆T and fa(π·XS) =

π · S. Using Definition 3.2 and Lemma 2.17, fa(π · (XSθ)) = π · fa(θ(XS)) ⊆π · S. Therefore, fa((π · XS)θ) ⊆T, and the result follows. We now proceed by case analysis on Inc =⇒ Inc′ (Definition 5.2):

• The case (⊑a). Suppose a ∈T. If θ ∈ Sol(a ⊑T, Inc′) then θ ∈ Sol(Inc′) and the result follows immediately. Conversely, suppose θ ∈ Sol(Inc′). Using Claim 1, fa(aθ) ⊆T, and the result follows.

• The case (⊑f). From Claim 2.

• The case (⊑[]). If θ ∈ Sol(r ⊑T ∪{a}, Inc′) then fa(rθ) ⊆T ∪{a}. By Claim 3, fa([a](rθ)) ⊆T. As fa([a](rθ)) = fa(([a]r)θ) and θ ∈ Sol(Inc′), the result follows. The reverse implication is similar.

• The case (⊑X). Suppose S ⊈π-1 · T, π ≠ id and θ ∈ Sol(π · XS ⊑T, Inc), so fa((π · XS)θ) ⊆T. By Claim 4, fa(XSθ) ⊆π-1 · T, and as θ ∈ Sol(Inc′), the result follows. The reverse implication is similar.

• The case (⊑X′). Suppose S ⊆π-1·T. If θ ∈ Sol(π·XS, Inc′) then θ ∈ Sol(Inc′) and the result follows. Conversely, suppose θ ∈ Sol(Inc′). By Claim 5, fa((π·XS)θ) ⊆T. The result follows.End of proof

Proposition 5.4

Support inclusion problem simplification is strongly normalising.

Proof

See Appendix Appendix A.End of proof

We conclude with a few useful observations:

Definition 5.5

For every Inc make a fixed but arbitrary choice of normal form nf (Inc), guaranteed to exist by Proposition 5.4.6

Definition 5.6

Call Inc consistent when a ⊑T ∉ nf (Inc) for all atoms a and permission sets T.

Lemma 5.7

If Inc is consistent then all inc ∈ nf (Inc) have the form XS ⊑T where S ⊈T.

5.2. Building solutions for support inclusion problems

Our main results are Theorems 5.13 and 5.20.

Definition 5.8

Define fV (Inc) by fV (Inc) = ⋃{fV (r) | ∃T.r ⊑T ∈ Inc}.

In words, fV (Inc) is “the unknowns appearing in terms appearing in Inc”.

Recall from Definition 2.3 that V ranges over finite sets of unknowns.

Definition 5.9

Let V range over finite sets of unknowns.

Suppose Inc is consistent. For every XS ∈V make a fixed but arbitrary choice of X′S′ such that X′S′∉V and

S′ = S ∩⋂{T | XS ⊑T ∈nf (Inc)}. (1)

We make our choice injectively; for distinct XS ∈ fV (Inc) and Y T ∈ fV (Inc), we choose X′S′ and Y ′T ′ distinct. It will be convenient to write V′V Inc for the set of our choices {X′S′| XS ∈V}.

Define a substitution ρV Inc by:

ρV Inc(XS) ≡id · X′S′if XS ∈VρV Inc(Y T ) ≡id · Y Totherwise
Remark 5.10

For example, take a, b, c ∈A<, S = A< \ {c}, T = A< \ {a}, U = A< \ {b}, and V = {XS}.

It is easy to see that the support reduction problem {XS ⊑T, XS ⊑U} is in normal form. Let X′S′ where S′ = A<\{a, b, c} be the fixed but arbitrary choice of fresh variable made in Definition 5.9. Then:

ρV Inc(XS) = id · X′S′andρV Inc(Y T ) = id · Y Tfor all other Y T
Remark 5.11

ρV Inc is a substitution that “makes Inc true on V”. Nominal unification does not have this notion because nominal terms unknowns are not permanently labelled with freshness information — instead, nominal terms unification emits ‘fresh’ freshness conditions.

It is easy to verify that

fa(ρV Inc(XS)) ⊆S for all XS ∈V.

In fact, ρV Inc is the most general solution with property; intuitively, all other solutions must factor through ρV Inc on V. This is made formal in Theorem 5.20.

Lemma 5.12

If Inc is consistent then ρV Inc ∈ Sol(Inc). (‘ρV Inc solves Inc.’)

Proof

Suppose Inc is a =⇒-normal form. If XS ⊑T ∈ Inc then ρV Inc(X) = id · X′S′ for an S′ which satisfies S′ ⊆T. The result follows.

More generally, if Inc is not a =⇒-normal form, by Theorem 5.3 Sol(Inc) = Sol(nf (Inc)), and we use the previous paragraph.End of proof

Theorem 5.13

Inc is consistent (Definition 5.6) if and only if Inc is solvable (Definition 5.1).

Proof

By Theorem 5.3 Sol(Inc) = Sol(nf (Inc)), so it suffices to show the result for the case when Inc is a =⇒-normal form.

Suppose Inc is inconsistent, so nf (Inc) contains a support inclusions of the form a ⊑T where a ∉T. Then aθ ≡a always, so there is no substitution θ such that aθ ⊆T. Conversely, if Inc is consistent, the result follows by Lemma 5.12.End of proof

Definition 5.14

Suppose that Inc is consistent, fV (Inc) ⊆V, and θ ∈ Sol(Inc). Define a substitution θ−ρV Inc by:

• (θ−ρV Inc)(X′S′) ≡θ(XS) if XS ∈V and ρV Inc(XS) ≡id · X′S′.• (θ−ρV Inc)(XS) ≡θ(XS) if XS ∉V.

We check that Definition 5.14 is well-defined:

Lemma 5.15

If θ−ρV Inc exists then it is well-defined.

Proof

Suppose θ−ρV Inc exists. Then:

• Suppose XS ≠ Y T, XS ∉V and Y T ∉V. By Definition 5.14, (θ−ρV Inc)(XS) ≡ θ(XS) and (θ−ρV Inc)(Y T) ≡θ(Y T). The result follows, as substitutions are well-defined.

• Suppose X′S′ ≠ Y ′T ′, ρV Inc(XS) ≡ id · X′S′, ρV Inc(Y T) ≡ id · Y ′T ′ and XS, Y T ∉V. Then (θ−ρV Inc)(X′S′) ≡θ(XS) and (θ−ρV Inc)(Y ′T ′) ≡θ(Y T). Since XS ≠ Y T, the result follows as substitutions are well-defined.

• Suppose X′S′ ≠ Y T, ρV Inc(XS) ≡ id·X′S′, XS ∉V and Y T ∈V. Then (θ−ρV Inc)(Y T) ≡ θ(Y T) and (θ−ρV Inc)(X′S′) ≡θ(XS). By Definition 5.9, ρV Inc(XS) ≢ id ·Y T as Y T ∈V. The result follows as substitutions are well-defined.

The case Y ′T ′ ≠ XS, ρV Inc(Y T) ≡ id · Y ′T ′, Y T ∉V and XS ∈V is similar to the case for X′S′ ≠ Y T, ρV Inc(XS) ≡ id · X′S′, XS ∉V and Y T ∈V.End of proof

Lemma 5.16

If θ ∈ Sol(Inc) then ρV Inc exists.

Proof

By assumption, Inc is solvable. By Theorem 5.13, Inc is consistent. Using Definition 5.9, ρV Inc exists.End of proof

Lemma 5.17

If ρV Inc exists, then it is well-defined.

Proof

Suppose ρV Inc exists and XS ≠ Y T. Then:

• XS ∈V and Y T ∈V. Then ρV Inc(XS) = id · X′S′ and ρV Inc(Y T) = id · Y ′T ′. By Definition 5.9, X′S′ and Y ′T ′ are chosen so X′S′≠ Y ′T ′. The result follows.

• XS ∉V and Y T ∉V. Then ρV Inc(XS) = id · XS and ρV Inc(Y T) = id · Y T. The result follows.

• XS ∈V and Y T ∉V. Then ρV Inc(Y T) = id · Y T and ρV Inc(XS) = id · X′S′ with X′S′∉V. The result follows.

• The case XS ∉V and Y T ∈V is similar to the case for XS ∈V and Y T ∉V.End of proof

Lemma 5.18

If Inc =⇒ Inc′ then fV (Inc′) ⊆ fV (Inc).

Proof

By case analysis on the rules defining =⇒ (Definition 5.2).End of proof

Lemma 5.19

If θ ∈ Sol(Inc) and fV (Inc) ⊆V then θ−ρV Inc is a substitution.

Proof

By Lemma 5.16, ρV Inc exists. We show fa((θ−ρV Inc)(X′S′)) ⊆S by cases:

• The case id · X′S′≡ρV Inc(XS) for XS ∈V. Using Lemma 5.18, fV (nf (Inc)) ⊆ fV (Inc). Then fV (nf (Inc)) ⊆V, as fV (Inc) ⊆V by assumption. There are two sub-cases:

• The case XS ∉ fV (nf (Inc)). Then S = S′ and (θ−ρV Inc)(X′S) = θ(XS) by Definition 5.14. By assumption fa(θ(XS)) ⊆S. The result follows.

• The case XS ∈ fV (nf (Inc)). By assumption, θ ∈ Sol(Inc) so θ ∈ Sol(nf (Inc)) using Theorem 5.3. Then fa(θ(XS)) ⊆T for every T such that XS ⊑T ∈ nf (Inc), using Definition 5.1. By Definition 5.14, S′ = ⋂{T | XS ⊑T ∈ nf (Inc)}. The result follows.

• Otherwise, (θ−ρV Inc)(XS) ≡θ(XS) and fa(θ(XS)) ⊆S by assumption.End of proof

Theorem 5.20

Suppose θ ∈ Sol(Inc) and fV (Inc) ⊆V.

Then θ(XS) ≡ (ρV Inc ◦(θ−ρV Inc))(XS) for every XS ∈V.

Proof

For some fresh X′S ∉V, ρ(XS) ≡ id ·X′S, and (θ−ρV Inc)(X′S) ≡θ(XS). The result follows by Lemma 2.16.End of proof

5.3. Support reduction example

Suppose a, c ∈A< and b, d ∉A<. Take S = A< = T, U = A<∪{b} and V = A<∪{d}. We first run the support reduction algorithm on Inc = {a ⊑S, f([a]a, id ·Y T) ⊑T, (c a)· ZU ⊑S, (b a) · W V ⊑T}:

a ⊑S , f([a]a, id · Y T ) ⊑T, (c a) · ZU ⊑S, (b a) · W V ⊑T =⇒ (⊑a)f([a]a, id · Y T ) ⊑T , (c a) · ZU ⊑S, (b a) · W V ⊑T =⇒ (⊑f)[a]a ⊑T , id · Y T ⊑T, (c a) · ZU ⊑S, (b a) · W V ⊑T =⇒ (⊑[])id · Y T ⊑T , (c a) · ZU ⊑S, (b a) · W V ⊑T =⇒ (⊑X′)(c a) · ZU ⊑S , (b a) · W V ⊑T =⇒ (⊑X)ZU ⊑(c a) · S, (b a) · W V ⊑T =⇒ (⊑X)ZU ⊑(c a) · S, W V ⊑(b a) · T

We take nf (Inc) = {ZU ⊑ (c a) · S, W V ⊑ (b a) · T}. By Definition 5.6 we have nf (Inc) is consistent, therefore by Theorem 5.13 a solution for Inc exists.

We now construct ρV Inc. Take W ′ and Z′ as our injective choices of fresh unknowns. Take U ′ = U ∩ ((c a) ·S ∩ (b a) ·T) and V ′ = V ∩ ((c a) ·S ∩ (b a) ·T). An easy calculation shows that U ′ = A< \ {a} = V ′. We define ρV Inc piecewise by:

ρV Inc(ZU) = id · Z′U ′ and ρV Inc(W V ) = id · W ′V ′ and ρV Inc(XS) = id · XS for all other XS

It is easy to verify that this is in fact a substitution (i.e. fa(ρV Inc(XS)) ⊆S always).

6. Permissive nominal unification problems

We can now give an algorithm to compute solutions to permissive nominal unification problems (Definition 3.9) and we prove that our algorithm computes most general solutions. Note, as we have observed before, that the notion of problem and solution is based just on equalities and substitutions.

6.1. The unification algorithm

Lemma 6.1

θ◦θ′ ∈ Sol(Pr) if and only if θ′ ∈ Sol(Prθ).

Proof

By unpacking Definition 3.9 and using Lemma 3.8.End of proof

Definition 6.2

If Pr is a problem, define a support inclusion problem Pr⊑ by:

Pr⊑= {r ⊑fa(s), s ⊑fa(r) | r?= s ∈Pr}

Call a support inclusion problem Inc non-trivial when nf (Inc) ≠ ∅.

(?=a) V; a?= a, Pr =⇒ V; Pr(?=f) V; f(r1, . . .)?= f(s1, . . .), Pr =⇒ V; r1?= s1, . . . , Pr(?=[a]) V; [a]r?= [a]s, Pr =⇒ V; r?= s, Pr(?=[b]) V; [a]r?= [b]s, Pr =⇒ V; (b a) · r?= s, Pr (b ∉fa(r))(?=X) V; π · XS?= π · XS, Pr =⇒ V; Pr(I1) V; π · XS?= s, Pr[XS:=π-1·s]=⇒ V; Pr[XS:=π-1 · s] (XS ∉fV (s), fa(s) ⊆π · S)(I2) V; r?= π · XS, Pr[XS:=π-1·r]=⇒ V; Pr[XS:=π-1 · r] (XS ∉fV (r), fa(r) ⊆π · S)(I3) V; PrρV Pr⊑=⇒ V ∪V′V Pr⊑; Pr ρV Pr⊑(Pr⊑consistent and non-trivial)
Figure 5: Simplification rules for problems
Definition 6.3

Define a simplification rewrite relation V; Pr =⇒V′; Pr′ on unification problems by the rules in Figure 5.

Call (?=a), (?=f), (?=[a]), (?=[b]), and (?=X) non-instantiating rules. Call (I1), (I2), and (I3) instantiating rules. Write =⇒∗ for the transitive and reflexive closure of =⇒.

In (I3) we insist that Pr⊑ is non-trivial to avoid indefinite rewrites. We insist Pr⊑ is consistent so that ρV Pr⊑ exists. ρV Pr⊑ and (V′V Pr⊑ are defined in Definition 5.9.)

Definition 6.4

Define fV (Pr) = ⋃{fV (r) ∪ fV (s) | r?= s ∈Pr}.

Definition 6.5

Suppose V is a set of unknowns. Define θ|V by:

θ|V(X) ≡θ(X) if X ∈Vθ|V(X) ≡id · X otherwise

(We overload |, for technical convenience: π|S is partial and θ|V is total.)

Definition 6.6

If Pr is a problem, define a unification algorithm by:

1. Rewrite fV (Pr); Pr using the rules of Definition 6.3 as much as possible, with top-down precedence (so we apply (?=a) before (?=f), and so on down to (I3)).

2. If we reduce to V′; ∅, we succeed and return θ|V where θ is the functional composition of all the substitutions labelling rewrites (we take θ = id if there are none). Otherwise, we fail.

Proposition 6.7

The algorithm of Definition 6.6 always terminates.

Proof

See Appendix Appendix A.End of proof

6.2. Examples of the algorithm

Example one.

Suppose a, c ∈A< and d ∉A<. Take S = A<. Take V = {XS}. Suppose a term-former g. We apply the algorithm to {g([a](id · XS), [a]a) ?= g([d]c, [d]d)}:

V; g([a](id · XS), [a]a)?= g([d]c, [d]d) =⇒ (?=f)V; [a](id · XS)?= [d]c , [a]a?= [d]d =⇒ (?=[b])V; (d a) · XS?= c , [a]a?= [d]d[XS:=c]=⇒ (I1)V; [a]a?= [d]d =⇒ (?=[b])V; (d a) · a?= d =⇒ (?=a)

V; ∅ (Success!) The algorithm succeeds and returns the substitution [XS:=c].

Example two.

Suppose a, c ∈A< and b, d ∉A<. Take S = A< ∪{b, d} and T = A< ∪{f} and U = A<. Take V = {XS, Y T}. Suppose a term-former f.

We apply the algorithm to {f([a]b, id · ZU, id · XS) ?= f([d]b, [a]a, id · Y T)}:

V; f([a]b, id · ZU, id · XS)?= f([d]b, [a]a, id · Y T ) =⇒ (?=f)V; [a]b?= [d]b , id · ZU?= [a]a, id · XS?= id · Y T=⇒ (?=[b])V; (d a) · b?= b , id · ZU?= [a]a, id · XS?= id · Y T=⇒ (?=a)V; id · ZU?= [a]a , id · XS?= id · Y T[ZU:=[a]a]=⇒ (?=I1)V; id · XS?= id · Y T[XS:=X′S′][Y T :=Y ′T ′]=⇒ (I3)V ∪{X′S′, Y ′T ′}; id · X′S′?= id · Y ′T ′[X′S′:=Y ′T ′]=⇒ (I1)V ∪{X′S′, Y ′T ′}; id · Y ′T ′?= id · Y ′T ′=⇒ (?=X)V ∪{X′S′, Y ′T ′}; ∅ (Success!)

Here X′ and Y ′ are the choice of unknown made in Definition 5.9, and S′ = A< = T ′.

The algorithm succeeds and returns the substitution

[X′S′:=Y ′T ′]◦[XS:=X′S′]◦[Y T :=Y ′T ′]◦[ZU:=[a]a].

Example three.

An example that fails to unify. Take S = A<. Take V = {XS}. We run the algorithm on {[a]([b](id · XS)) ?= [a](id · XS)}:

V; [a]([b](id · XS))?= [a](id · XS) =⇒ (?=[a])V; [b](id · XS)?= id · XS(Failure!)

The algorithm fails as the precondition of rule (I2), XS ∉ fV ([b](id·XS)), the ‘occurs check’, fails to hold. By Theorem 6.25 there is no solution to the unification problem.

6.3. Preservation of solutions

Lemma 6.8

If V; Pr =⇒V; Pr′ by a non-instantiating rule (Definition 6.3) then Sol(Pr) = Sol(Pr′).

Proof

See Appendix Appendix A. We use Lemmas 3.3 and 3.4, and Proposition 2.21.End of proof

Lemma 6.9

Suppose θ(XS) =α θ′(XS) for all XS ∈ fV (Pr). Then θ ∈ Sol(Pr) if and only if θ′ ∈ Sol(Pr).

Proof

Unpacking Definition 3.9 it suffices to show that rθ =α sθ if and only if rθ′ =α sθ′, for every r?= s ∈Pr. This is easy using Lemma 3.5 and the fact by construction (Definition 6.4) that fV (r) ⊆ fV (Pr) and fV (s) ⊆ fV (Pr).End of proof

Definition 6.10

Write θ−XS for the substitution such that

(θ−XS)(XS) ≡id · XSand(θ−XS)(Y T ) ≡θ(Y T ) for all other Y T .

In the right circumstances, a substitution θ can be factored as ‘a part of θ that does not touch XS’ and ‘a single substitution for XS’:

Theorem 6.11

Suppose XSθ =α sθ and XS ∉ fV (s). Then

XSθ =α XS([XS:=s]◦(θ−XS)) andY T θ =α Y T ([XS:=s]◦(θ−XS)).
Proof

We reason as follows:

XS([XS:=s]◦(θ−XS)) ≡s(θ−XS) Definition 3.2≡sθ XS ∉fV (s), Lemma 3.5=α XSθ Assumption
Y T ([XS:=s]◦(θ−XS)) ≡Y T (θ−XS) Definition 3.7≡Y T θ Definition 6.10End of proof

6.4. Simplification rewrites calculate principal solutions

Definition 6.12

Write θ1 ≤θ2 when there exists some θ′ such that XSθ2 =α XS(θ1 ◦θ′) always. Call ≤ the instantiation ordering.

Definition 6.13

A principal (or most general) solution to a problem Pr is a solution θ ∈ Sol(Pr) such that θ ≤θ′ for all other θ′ ∈ Sol(Pr).

Our main results are Theorems 6.18 — the unification algorithm from Definition 6.6 calculates a solution — and 6.23 — the solution it calculates, is principal.

Lemma 6.14

If fV (Pr) ⊆V and V; Pr =⇒V′; Pr′ using a non-instantiating rule, then fV (Pr′) ⊆V.

Proof

See Appendix Appendix A.End of proof

Lemma 6.15

fV (r[XS:=s]) ⊆ fV (r) ∪ fV (s).

Proof

By induction on r.End of proof

Lemma 6.16

If fV (Pr) ⊆V and V; Prθ=⇒V′; Pr′θ using an instantiating rule, then fV (Pr′θ) ⊆V′.

Proof

There are two cases:

• The case (I1). Suppose fV (π · XS?= s, Pr′) ⊆V and V; π · XS?= s, Pr′ [XS:=π-1·s]=⇒ V′; Pr′[XS:=π-1 · s] using (I1). Using Definition 6.4 and Lemma 6.15, we have fV (Pr′[XS:=π-1 · s]) ⊆ fV (Pr′) ∪ fV (π-1 · s). The result follows.

• The case (I3). A corollary of Lemma 5.18.End of proof

Lemma 6.17

If XS ∈V then ([XS:=s]◦θ)|V = [XS:=s]◦(θ|V)

Proof

We consider cases:

• The case XS with XS ∈V. We reason as follows:

([XS:=s]◦θ)|V(XS) ≡([XS:=s]◦θ)(XS) Definition 6.5, XS ∈V≡sθ Definition 3.7≡sθ|VDefinition 6.5

• The case Y T with Y T ∈V. We reason as follows:

([XS:=s]◦θ)|V(Y T ) ≡([XS:=s]◦θ)(Y T ) Definition 6.5, Y T ∈V≡θ(Y T ) Definition 3.7≡θ|V(Y T ) Definition 6.5

• The case Y T with Y T ∉V. Since ([XS:=s]◦θ)|V(Y T) ≡ id · Y T and θ|V ≡ id · Y T.End of proof

Recall that θ|V is defined in Definition 6.5:

Theorem 6.18

If fV (Pr) ⊆V then V; Prθ=⇒∗V′; ∅ implies θ|V ∈ Sol(Pr).

Proof

By induction on the length of the path in θ=⇒∗.

• Length 0. Then Pr = ∅ and θ ≡ id. The result follows.

• Length k + 1. There are three cases:

• The non-instantiating case. Suppose V; Pr =⇒V; Pr′′θ=⇒∗V′; ∅. Using Lemma 6.14, fV (Pr′′) ⊆V and θ ∈ Sol(Pr′′) by inductive hypothesis. Using Lemma 6.8, θ ∈ Sol(Pr), and the result follows.

• The case of (I1) or (I2). Suppose V; Prχ=⇒V; Prχθ′=⇒∗V′; ∅. Using Lemma 6.16, fV (Prχ) ⊆V. By inductive hypothesis θ′|V ∈ Sol(Prχ). By Lemma 6.17, (χ◦θ′)|V = χ◦(θ′|V). By Lemma 6.1, (χ◦θ′)|V ∈ Sol(Pr).

• The case of (I3). Suppose V; Prρ=⇒V′; Prρθ′=⇒∗V′′; ∅. Using Lemma 6.16, fV (Prρ) ⊆V′. By inductive hypothesis θ′|V′ ∈ Sol(Prρ). By Lemma 6.1, ρ◦(θ′|V′) ∈ Sol(Pr). By Lemma 6.17, ρ◦(θ′|V′) = (ρ◦θ′)|V′. By Lemma 6.9,

(ρ◦θ′)|V ∈Sol(Pr).End of proof
Lemma 6.19

If θ1 ≤θ2 then θ◦θ1 ≤θ◦θ2.

Proof

By Definition 6.12, θ′ exists such that XSθ2 =α XS(θ1◦θ′) always. Then:

XS(θ◦θ2) ≡(XSθ)θ2Lemma 3.8=α (XSθ)(θ1◦θ′) Lemma 3.5≡XS((θ◦θ1)◦θ′) Lemma 3.8End of proof
Lemma 6.20

Suppose XSθ2 =α XSθ′ 2 always. Then θ1 ≤θ2 implies θ1 ≤θ′ 2.

Proof

By a routine calculation using Definition 6.12 and using Proposition 2.21.End of proof

Lemma 6.21

If θ ∈ Sol(Pr) (Definition 3.9) then θ ∈ Sol(Pr⊑) (Definition 5.1).

Proof

By a routine calculation, using Definitions 3.9 and 6.2, and Lemma 2.19.End of proof

Lemma 6.22

If XS ∈V then (θ|V −XS) = (θ−XS)|V.

Proof

We consider cases:

• The case XS. Then (θ|V −XS)(XS) = id · XS and (θ−XS)|V(XS) = id · XS. The result follows.

• The case Y T with Y T ∉V. Then (θ|V −XS)(Y T) = id · Y T and (θ−XS)|V(Y T) = id · Y T. The result follows.

• The case Y T with Y T ∈V. Then (θ|V −XS)(Y T) = θ|V(Y T) and (θ−XS)|V(Y T) = θ(Y T). As θ|V(Y T) = θ(Y T) when Y T ∈V, the result follows.End of proof

Theorem 6.23

Suppose fV (Pr) ⊆V.

If V; Prθ=⇒∗V′; ∅ then θ|V is a principal solution to Pr (Definition 6.13).

Proof

By Theorem 6.18, θ|V ∈ Sol(Pr). We prove θ|V is principal by induction on the path length of V; Prθ=⇒∗V′; ∅.

• Length 0. So Pr = ∅ and θ = id|V. By Definition 6.12, id|V ≤θ′|V.

• Length k + 1. We consider the rules in Definition 6.3.

• The non-instantiating case. Suppose

V; Pr =⇒V; Pr′θ=⇒∗V′; ∅

where V; Pr =⇒V; Pr′ is a non-instantiating simplification rewrite. By inductive hypothesis θ|V is a principal solution of Pr′. By Lemma 6.8 θ|V is a principal solution of Pr. The result follows.

• The case (I1). Suppose fa(s) ⊆π ·S and XS ∉ fV (s). Write χ = [XS:=π-1 ·s]. Suppose Pr = π·XS?= s, Pr′′ so that

V; π · XS?= s, Pr′′χ=⇒V; Pr′′χθ′′=⇒∗V′; ∅.

Further, suppose that θ′|V ∈ Sol(Pr). By assumption (π · X)θ′ =α sθ′, so by Lemma 3.4 π · θ′(X) =α sθ′. By Lemmas 2.18 and 2.16 θ′(X) =α π-1 · (sθ′), and by Lemma 3.4 θ′(X) =α (π-1 · s)θ′. It follows by Theorem 6.11 and Lemma 6.9 that χ◦(θ′|V −XS) ∈ Sol(Pr). Using Lemma 6.22, (θ′|V −XS) = (θ′ −XS)|V. By Lemma 6.1, (θ′ −XS)|V ∈ Sol(Pr′′χ). By Theorem 6.18, θ′′|V ∈ Sol(Pr′′χ). By Lemma 6.16, fV (Pr′′χ) ⊆V. By inductive hypothesis θ′′|V ≤ (θ′−XS)|V. By Lemma 6.19, χ◦(θ′′|V) ≤ χ◦(θ′−XS)|V. Now by assumption fV (s) ⊆V and XS ∈V. Using Lemma 6.17 it follows that χ◦(θ′′|V) = (χ◦θ′′)|V. By Lemma 6.22, (θ′−XS)|V = θ′|V−XS. By Theorem 6.11 and Lemma 6.20, (χ◦θ′′)|V ≤θ′|V as required.

• The case (I2) is similar to the case of (I1).

• The case (I3). Suppose Pr⊑ is consistent and non-trivial. Write ρ = ρV Pr⊑, so that

V; Prρ=⇒V′′; Prρθ′′=⇒∗V′; ∅,

and suppose that θ′|V ∈ Sol(Pr). By Theorem 6.18, θ′′|V′′ ∈ Sol(Prρ). It is a fact that V′′ = V ∪V′V Pr⊑, so fV (Prρ) ⊆V′′. By Lemma 6.21, θ′|V ∈ Sol(Pr⊑). By Theorem 5.20 and Lemma 6.9, ρ◦(θ′|V−ρ) ∈ Sol(Pr). By Lemma 6.1, θ′|V−ρ ∈ Sol(Prρ). By inductive hypothesis θ′′|V ≤θ′|V−ρ. By Lemma 6.19, ρ◦θ′′|V ≤ρ◦(θ′|V−ρ). It is a fact that ρ◦(θ′′|V) = (ρ◦θ′′)|V. By Theorem 5.20 and Lemma 6.20, (ρ◦θ′′)|V ≤ θ′|V as required.End of proof

Lemma 6.24

1. Suppose fa(s)⊆π · S and XS ∉ fV (s). Write χ=[XS:=π-1 · s].

If V; Prχ=⇒V; Pr′ with (I1) or (I2) then θ ∈Sol(Pr) implies θ−XS ∈Sol(Pr′).

2. If V; Prρ=⇒V′; Pr′ with (I3) then θ ∈ Sol(Pr) implies θ−ρ ∈ Sol(Pr′).

Proof

1. We consider the case of (I1); the case of (I2) is similar. Suppose Pr = π · XS?= s, Pr′′ so that V; π · XS?= s, Pr′′χ=⇒V; Pr′′χ. Now suppose θ ∈ Sol(Pr). By Lemma 6.9 and Theorem 6.11, χ◦(θ−XS)) ∈ Sol(Pr). By Lemma 6.1, θ−XS ∈ Sol(Prχ). It follows that θ−XS ∈ Sol(Pr′′χ) as required.

2. Suppose Pr⊑ is consistent and non-trivial. Write ρ = ρV Pr⊑, so that V; Prρ=⇒ V′′; Prρ. Now suppose θ ∈ Sol(Pr). By Lemma 6.9 and Theorem 5.20, ρ◦(θ−ρ) ∈ Sol(Pr). By Lemma 6.1, θ−ρ ∈ Sol(Prρ) as required.End of proof

Theorem 6.25

Given a problem Pr, if the algorithm of Definition 6.6 succeeds then it returns a principal solution; if it fails then there is no solution.

Proof

If the algorithm succeeds we use Theorem 6.23. Otherwise, the algorithm generates an element of the form f(r1, . . . , rn) ?= f(r′ 1, . . . , r′ n′) where n ≠ n′, f(. . .) ?= g(. . .), f(. . .) ?= [a]s, f(. . .) ?= a, [a]r =α a, [a]r =α b, a?= b, a Pr such that Pr⊑ is inconsistent, or π · XS?= r or r?= π · XS where XS ∈ fV (r). By arguments on syntax and size of syntax, no solution to the reduced problem exists. It follows by Lemma 6.24 that no solution to Pr exists.End of proof

7. Lambda-term syntax

We want to relate permissive nominal unification with higher-order pattern unification as promised in the Introduction. In this section we recall the syntax and operational semantics of the λ-calculus. It is convenient to match the variables of permissive nominal terms with those of the λ-calculus. Therefore, when we define λ-terms’ syntax in Definition 7.1, we use the same atoms and unknowns as we used in Definition 2.6; both behave like ordinary variables (with capture-avoiding substitution). As in permissive nominal terms we unify on the unknowns, but we do not care about the permission sets so we will let X, Y, Z, . . . range over distinct unknowns (without superscripts).

Definition 7.1

Define λ-terms by:

g, h, . . . ::= a | X | f | λa.g | g′g

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

g, h, k will range over λ-terms.

Definition 7.2

Define a permutation action by:

π·a ≡π(a) π·X ≡X π·f ≡f π·(λa.g) ≡λπ(a).(π·g) π·(g′g) ≡(π·g′)(π·g)
Definition 7.3

Define free atoms by:

fa(a)={a} fa(X)=∅ fa(f)=∅ fa(λa.g)=fa(g)\{a} fa(g′g)=fa(g′)∪fa(g)
Definition 7.4

Define α-equivalence =α inductively by the rules in Figure 6.

(λ=αa)a =α ag =α h(λ=αλaa)λa.g =α λa.h(b a) · g =α h b ∉fa(g) (λ=αλab) λa.g =α λb.h(λ=αf)f =α f(λ=αX)X =α Xg =α g′h =α h′(λ=αp)gh =α g′h′
Figure 6: α-equivalence on λ-terms.

It is not hard to prove that Definition 7.4 does indeed specify the usual α-equivalence relation on λ-terms. Our definition is designed to match the definition of α-equivalence on nominal terms (Definition 2.13). This makes later results easier to prove (for example Theorem 8.12).

Lemma 7.5 to Proposition 7.12 mirror similar results for permissive nominal terms. The proofs of Lemmas 7.5 to 7.7 are by induction on g.

Lemma 7.5

If π|fa(g) = π′|fa(g) then π · g =α π′ · g.

Lemma 7.6

π · (π′ · g) ≡ (π◦π′) · g

Lemma 7.7

fa(π · g) = π · fa(g).

Lemma 7.8

g =α h implies π · g =α π · h.

Proof

By induction on the derivation of g =α h. We consider one case:

• The case (λ=αλab). By inductive hypothesis π · ((b a) · g) =α π · h. By Lemma 7.6, π · ((b a) · g) ≡ (π◦(b a)) · g. It is a fact that π◦(b a) = (π(b) π(a))◦π, therefore (π(b) π(a)) · (π · g) =α π · h, by Lemma 7.6. By Lemma 7.7, π(b) ∉ fa(π · g). Using (λ=αλab), we obtain λπ(a).π·g =α λπ(b).π·h. The result follows from Definition 7.2.End of proof

Lemma 7.9

If g =α h then fa(g) = fa(h).

Proof

By induction on the derivation of g =α h. We consider one case;

• The case (λ=αλab). Suppose λa.g =α λb.h using (λ=αλab), where b ∉ fa(g). We aim to show fa(λa.g) = fa(λb.h), or, fa(g) \ {a} = fa(h) \ {b}. As b ∉ fa(g) we have fa(g)\{a} = (b a)·fa(g)\{b}. Using Lemma 7.7, (b a)·fa(g)\{b} = fa((b a)·g)\{b}. By inductive hypothesis fa((b a) · g) = fa(s), as required.End of proof

Definition 7.10

Define a notion of size on λ-terms by:

size(a) = 0 size(X) = 0 size(f) = 0 size(g′g) = size(g′)+size(g) size(λa.g) = 1+size(g)
Lemma 7.11

size(g) = size(π · g)

Proof

By induction on g.End of proof

Proposition 7.12

=α is transitive, reflexive, and symmetric.

Proof

See Appendix Appendix A. We use Lemmas 7.5, 7.6, 7.7, 7.8, 7.9 and 7.11.End of proof

Definition 7.13

Call a function σ from unknowns to λ-terms a (λ-calculus) substitution. σ will range over substitutions (and later so will ρ; Definition 9.17).

We will write [h/X] for the substitution which maps X to h and maps all other Y to Y .

Definition 7.14

Define the capture-avoiding substitution action gσ on λ-terms by:

aσ ≡a Xσ ≡σ(X) fσ ≡f (g′g)σ ≡(g′σ)(gσ)(λa.g)σ ≡λa.(gσ) (a ∉⋃{fa(σ(X)) | X ∈fV (g)}) (λa.g)σ ≡λb.(((b a)·g)σ) (a ∈⋃{fa(σ(X)) | X ∈fV (g)})

In the final clause, ‘b fresh’ denotes a fixed but arbitrary choice of fresh b (so b ∉ fa(g) and b ∉⋃{fa(σ(X))|X∈fV (g)}).

Definition 7.15

Define composition σ◦σ′ by: (σ◦σ′)(X) ≡ (σ(X))σ′. This mirrors the definition for substitutions on permissive terms, given in Definition 3.7.

Lemma 7.16

gσσ′ =α g(σ◦σ′)

Proof

By induction on size(g).End of proof

We also need a substitution action on atoms so that we can talk about αβ-convertibility — the distinction between unknowns and atoms is rather artificial here, but in the context of relating to permissive nominal terms it is useful to maintain it:

Definition 7.17

Define a capture-avoiding substitution g[h/a] by:

a[h/a] ≡h b[h/a] ≡b X[h/a] ≡X f[h/a] ≡f(g′g)[h/a] ≡(g′[h/a])(g[h/a]) (λa.g)[h/a] ≡λa.g (λa.g)[h/a] ≡λb.(((b a) · g)[h/a]) (b fresh)

In the final clause, ‘b fresh’ denotes a fixed but arbitrary choice of b such that b ∉ fa(h)∪ fa(g).

Definition 7.18

Let αβ-equivalence =αβ be the least transitive, reflexive, symmetric relation such that (λa.g)h =αβ g[h/a] and closed under the rules of Definition 7.4.

We define unification problems as usual and write ‘g?= h’ for an equality considered as part of a unification problem. σ solves a problem when gσ =αβ hσ for every g?= h in the problem, as usual.

We conclude with definions of pattern and pattern substitution [32, 31]. Recall that we work in an untyped λ-term syntax.

Definition 7.19

Let φ map each unknown X to a natural number which we call its arity. Define φ-patterns, a subset of λ-terms, by:

q, r, . . . ::= a | Xa1 . . . aφ(X) | fq1 . . . qn | λa.q

Call q a pattern when it is a φ-pattern for some φ. q, r, . . . will range over patterns.

Call σ a φ-pattern substitution when every σ(X) is a φ-pattern. Call σ a pattern substitution when σ is a φ-pattern substitution for some φ.

So g is a pattern when there exists some φ such that every X in g occurs as Xa1. . . aφ(X). This is not quite a typing constraint, but it achieves part of what a typing system would achieve; that within g, for each X, X is consistently applied to a list of atoms of the same length. Note that the translation of Definition 8.3 below, produces terms of this form.

8. Translating nominal terms to lambda-term syntax

8.1. The translation, and its soundness

We define the translation from permissive nominal terms to λ-terms, and show that it is sound in the sense that α-convertible permissive nominal terms map to α-convertible λ-terms (Theorem 8.6). The translation involves a vector of atoms D; we discuss where this comes from in Subsection 8.2.

Definition 8.1

Call a finite list of distinct atoms a vector. C, D range over vectors. Write [a1, . . . , an] for the vector containing a1, ..., an in that order.

Definition 8.2

Suppose A ⊆A. Write C ∩A for the vector of atoms in C that occur in A, in order; thus [a1, a2, a3] ∩{a1, a3, a5} = [a1, a3]. Write C ⊆A when every atom in C is in A. Write A ⊆C when every atom in A is in C.

Definition 8.3

Translate a nominal term r to a λ-term ⟦r⟧D by:

⟦a⟧D ≡a ⟦π · XS⟧D ≡XSπ(d1) . . . π(dn) ([d1, . . . , dn] = D ∩S)⟦[a]r⟧D ≡λa.⟦r⟧D⟦f(r1, . . . , rn)⟧D ≡f⟦r1⟧D . . . ⟦rn⟧D
Lemma 8.4

⟦π · r⟧D ≡π · ⟦r⟧D

Proof

By induction on r.End of proof

Lemma 8.5 is useful for the proof of Theorem 8.6:

Lemma 8.5

fa(⟦r⟧D) ⊆ fa(r).

Proof

By induction on r. We consider only one case:

• The case π · XS. We reason as follows:

fa(⟦π · XS⟧D) = fa(XSπ(d1) . . . π(dn)) Definition 8.3= fa(π(d1)) ∪. . . ∪fa(π(dn)) Definition 7.3= π · (fa(d1) ∪. . . ∪fa(dn)) Fact⊆π · fa(XS) Definition 2.11= fa(π · XS) Lemma 2.17

The result follows.End of proof

Theorem 8.6 (Soundness).

If r =α s then ⟦r⟧D =α ⟦s⟧D.

Proof

By induction on the size of r (Definition Appendix A.1). We reason by cases on the last rule in the derivation of r =α s:

• The cases (=αa), (=αf) and (=α[]aa) are straightforward.

• The case (=αX). There are two cases:

• The case D ∩S = []. Then ⟦π ·XS⟧D = ⟦π′ ·XS⟧D = XS. We use (λ=αX). The result follows.

• The case D ∩S = [d1, . . . , dn] and n ≥ 1. By assumption π|δ(X) = π′|δ(X).

Then π(di) = π′(di) for 1 ≤i ≤n and ⟦π·XS⟧D ≡⟦π′·XS⟧D ≡XSπ(d1) . . . π(dn).

We use (λ=αp), (λ=αX), and (λ=αa). The result follows.

• The case (=α[]ab). By assumption (b a) · r =α s and b ∉ fa(r). We choose fresh c so c ∉ fa(r) ∪ fa(s). By Lemma 2.18, (c a) · r =α (c b) · s. By inductive hypothesis ⟦(c a) · r⟧D =α ⟦(c b) · s⟧D. Using (λ=αλaa), λc.⟦(c a) · r⟧D =α λc.⟦(c b) · s⟧D. By Lemma 8.4, λc.((c a) · ⟦r⟧D) =α λc.((c b) · ⟦s⟧D). By Lemma 8.5, c ∉ fa(⟦r⟧D) ∪ fa(⟦s⟧D). By (λ=αλab), λc.((c a) · ⟦r⟧D) =α λa.⟦r⟧D and λc.((c b) · ⟦s⟧D) =α λb.⟦s⟧D. Using Proposition 7.12, λa.⟦r⟧D =α λb.⟦s⟧D. By Definition 8.3, ⟦[a]r⟧D =α ⟦[b]s⟧D, as required.End of proof

8.2. Capturable atoms; injectivity and minimality

We investigate the converse to Theorem 8.6; if the translations of two terms are α-convertible, then so are the two terms. This is injectivity (Theorem 8.12). The translation ⟦r⟧D (Definition 8.3) is parameterised by a vector D. Levy and Villaret introduced a translation [29, Definition 2] (for nominal, not permissive nominal terms); they used all the atoms in r. This is a safe choice, but we will also show that the smaller set of capturable atoms in r (Definition 8.7) is consistent with injectivity — and that the capturable atoms are the minimal such set (Theorem 8.14).

Definition 8.7

Define the capturable atoms of a term (with respect to a set of atoms) captA(r) inductively by:

captA(a) = ∅ captA(π · XS) = (nontriv(π) ∪A) ∩ScaptA([a]r) = captA∪{a}(r) captA(f(r1, . . . , rn)) = ⋃1≤i≤n captA(ri)

Write capt∅(r) as capt(r).

For instance, if S = (A< ∪{a})\{b}, then capt([a][b]XS) = {a} and capt((b a)·XS) = {a}.

Lemma 8.8

If a ∉ fa(r) then captA(r) = captA∪{a}(r).

Proof

By induction on r.

• The cases b, f(r1, . . . , rn) and [a]r are straightforward.

• The case [b]r. If a ∉ fa([b]r) then a ∉ fa(r) by Definition 2.11. We then have:

captA([b]r) = captA∪{b}(r) Definition 8.7= captA∪{b}∪{a}(r) Inductive hypothesis= captA∪{a}([b]r) Definition 8.7

The result follows.

• The case π · XS. If a ∉ fa(π · XS) then a ∉π · S. By Definition 8.7, captA(π · XS) = (nontriv(π) ∪A) ∩S. Further, captA∪{a}(π · XS) = (nontriv(π) ∪A ∪{a}) ∩S. If π(a) = a then a ∉S. If π(a) ≠ a then a ∈ nontriv(π), as required.End of proof

Lemma 8.9

If nontriv(π) ⊆A then captA(π · r) = captA(r).

Proof

See Appendix Appendix A. We use Lemma 2.16.End of proof

Corollary 8.10

If b ∉ fa(r) then captA([a]r) = captA([b](b a) · r).

Proof

See Appendix Appendix A. We use Lemmas 8.8, 8.9, and 2.17.End of proof

Capturable atoms is a canonical notion, in the sense that it is preserved by α-equivalence:

Lemma 8.11

If r =α s then captA(r) = captA(s).

Proof

By induction on the derivation of r =α s. We consider one case:

• The case of (=α[b]). Suppose b ∉ fa(r), (b a) · r =α s and s ≡ [b](b a) · r. The result follows by Corollary 8.10.End of proof

Provided that D is ‘large enough’, α-equivalence of translated terms implies α-equivalence of the original terms:

Theorem 8.12 (Injectivity).

Let D be a vector. Let r and s be nominal terms and let A, B ⊆A be finite. Suppose captA(r) ∪ captB(s) ⊆D. Then

⟦r⟧D =α ⟦s⟧Dimplies r =α s.

As a corollary, if capt(r) ∪ capt(s) ⊆D and ⟦r⟧D =α ⟦s⟧D then r =α s and captA(r) = captA(s) for all A.

Proof

For the first part, we work by induction on the size of r (Definition Appendix A.1), reasoning by cases on the last rule in the derivation of ⟦r⟧D =α ⟦s⟧D:

• The cases (λ=αa) and (λ=αλaa). Easy.

• The case (λ=αλab). Suppose (b a) · ⟦r⟧D =α ⟦s⟧D, b ∉ fa(⟦r⟧D) and captA([a]r) ∪ captB([b]s) ⊆D. We choose fresh c (so c ∉ fa(r) ∪ fa(s) and c ∉ fa(⟦r⟧D) ∪ fa(⟦s⟧D)). By Lemma 7.5, (c a) · ⟦r⟧D =α (c b) · ⟦s⟧D. By Lemma 8.4:

⟦(c a) · r⟧D =α ⟦(c b) · s⟧D.

By Corollary 8.10 and Definition 8.7:

captA∪{c}((c a) · r) ∪captB∪{c}((c b) · s) ⊆D.

By inductive hypothesis (c a)·r =α (c b)·s, and using (=α[]ab), and Proposition 7.12, [a]r =α [b]s as required.

• The case (λ=αapp). From Definition 8.3, there are two possibilities:

• The case f(r1, . . . , rn) and f(s1, . . . , sn) and f⟦r1⟧D . . . ⟦rn⟧D =α f⟦s1⟧D . . . ⟦sn⟧D. Then ⟦ri⟧D =α ⟦si⟧D for 1 ≤i ≤n. By inductive hypothesis ri =α si for 1 ≤i ≤n. The result follows from (=αf).

• The case π·XS and π′·XS and XSπ(d1) . . . π(dn) =α XSπ′(d1) . . . π′(dn) where [d1, . . . , dn] = D ∩S. Then π(di) =α π′(di) for 1 ≤i ≤n, and so π|D∩S = π′|D∩S. By assumption, capt(π · XS) ⊆D, and by definition, π|S = π′|S. We conclude with (=αX).

• The case (λ=αX). From the form of the translation it must be that r = π · XS and s = π′ · XS and nontriv(π) ∩S = ∅= nontriv(π′) ∩S. The result follows from (=αX).

The corollary follows from the first part, and by Lemma 8.11.End of proof

Lemma 8.13

a ∈ captA(r) implies XS ∈ fV (r) exists such that a ∈S.

Proof

See Appendix Appendix A.End of proof

In Theorem 8.12 we used a notion of a ‘large enough’ vector D, based on capturable atoms. Theorem 8.14 shows how this bound is precise:

Theorem 8.14 (Minimality).

If capt(r) ⊈D then there exists some s such that r ≠α s and ⟦r⟧D =α ⟦s⟧D.

Proof

Suppose a ∈ capt(r) and a ∉D. By Lemma 8.13 XS ∈ fV (r) exists such that a ∈S. We choose c ∈S\D and take s ≡r[XS:=(c a)·XS]. It is a fact that XS ≠α (c a)·XS whilst ⟦XS⟧D =α ⟦(c a) · XS⟧D. An easy calculation shows r ≠α r[XS:=(c a) · XS] and ⟦r⟧D =α ⟦r[XS:=(c a) · XS]⟧D.End of proof

9. Translating substitutions; relating solutions of nominal and pattern unification problems

9.1. Translating substitutions

We extend the translation to substitutions. Our main result is Theorem 9.3: we can read this as a compositionality result for permissive nominal substitutions acting on terms with respect to the translation. Given the compositionality result it is easy to prove that the translation also preserves the natural instantiation ordering of solutions to unification problems (Corollary 9.5).

Translating substitutions introduces a problem: θ may solve Pr but in substituting it may introduce new capturable atoms (consider θ = [XS:=[c]ZS] solving {XS?= XS}, where c ∈S). This motivates introducing a second vector, to account for the capturable atoms ‘after’ the substitution. Accordingly, we will introduce another vector E that contains at least the capturable atoms of θ.

Definition 9.1

Define ⟦θ⟧E D by:

⟦θ⟧E D(XS) = λd1. . . . λdn.⟦θ(XS)⟧E where [d1, . . . , dn] = D ∩S.

Lemma 9.2 is useful in the proof of Theorem 9.3:

Lemma 9.2

If nontriv(π) ∩ fa(g) ⊆{d1, . . . , dn} then

(λd1. . . . λdn.g)π(d1) . . . π(dn) =αβ π · g.
Proof

By induction on g. We consider one case:

• The case λa.g. Choose a′ fresh (so a′ does not appear in {d1, . . . , dn}, nontriv(π), or g).

h =αβ (λa.g)[π(d1)/d1] . . . [π(dn)/dn] Definition 7.18=α (λa′.(a′ a) · g)[π(d1)/d1] . . . [π(dn)/dn] Definition 7.4≡λa′.((a′ a) · g)[π(d1)/d1] . . . [π(dn)/dn]) Definition 7.17, a′ fresh=αβ λa′.(π · ((a′ a) · g)) Inductive hypothesis≡π · λa′.((a′ a) · g) Definition 7.2=α π · λa.g Definition 7.4End of proof

Theorem 9.3 is a compositionality result for permissive nominal substitutions acting on terms with respect to the translation:

Theorem 9.3

If capt(r) ⊆D then ⟦rθ⟧E =αβ ⟦r⟧D⟦θ⟧E D.

Proof

By induction on r.

• The cases a and f(r1, . . . , rn) are routine.

• The case π ·XS. Let d1, . . . , dn be D ∩S and ⟦θ⟧E D(XS) = λd1. . . . λdn.⟦θ(XS)⟧E by Definition 9.1. Then:

⟦(π · XS)θ⟧E ≡⟦π · θ(XS)⟧EDefinition 3.2≡π · ⟦θ(XS)⟧ELemma 8.4=αβ (λd1. . . . λdn.⟦θ(XS)⟧E)π(d1) . . . π(dn) Lemma 9.2≡(XSπ(d1) . . . π(dn))⟦θ⟧E DDefinition 9.1≡⟦π · XS⟧D⟦θ⟧E DDefinition 8.3

The use of Lemma 9.2 above is valid, because: By assumption capt(π·XS) ⊆D. By Definition 8.7 capt(π·XS) = nontriv(π)∩S, so nontriv(π)∩S ⊆D. By assumption in Definition 3.1, fa(θ(XS)) ⊆S. It follows from Definition 8.3 that fa(⟦θ(XS)⟧E) ⊆S, and so that nontriv(π) ∩ fa(⟦θ(XS)⟧E) ⊆D. The result follows.

• The case [a]r. Choose b fresh, so b ∉ fa(⟦θ(XS)⟧E D) for every XS ∈ fV (r) and b ∉ fa(r). Then:

⟦([a]r)θ⟧E =α ⟦([b]((b a) · r))θ⟧EDefinition 2.13, Theorem 8.6, Lemma 3.6≡λb.(⟦((b a) · r)θ)⟧EDefinitions 3.2 and 8.3=αβ λb.((⟦(b a) · r⟧D)⟦θ⟧E D) Inductive hypothesis≡(λb.⟦(b a) · r⟧D)⟦θ⟧E DDefinition 7.17, b fresh≡⟦[b]((b a) · r)⟧D⟦θ⟧E DDefinition 8.3=α ⟦[a]r⟧D⟦θ⟧E DDefinition 2.13, Theorem 8.6, Lemma 3.6

The result follows.End of proof

Recall the instantiation ordering θ1 ≤θ2 from Definition 6.12. Similarly:

Definition 9.4

Write σ1 ≤σ2 when there exists some σ′ such that Xσ2 =αβ X(σ1 ◦σ′), for any X. Call ≤ the instantiation ordering.

We can leverage Theorem 9.3 to prove a corollary, describing a sense in which the instantiation ordering θ1 ≤θ2 of Definition 6.12 translates to the instantiation ordering of Definition 9.4:

Corollary 9.5

Suppose ⋃XS capt(θ2(XS)) ⊆E.

If θ1 ≤θ2 then ⟦θ1⟧E D ≤⟦θ2⟧E D.
Proof

Suppose θ1 ≤θ2. By definition (Definition 6.12) there exists some θ′ such that XSθ1 =α XS(θ2 ◦θ′) always. We reason as follows, for any unknown XS:

⟦XS⟧D⟦θ2⟧E D =αβ ⟦XSθ2⟧ETheorem 9.3=α ⟦XS(θ1 ◦θ′)⟧ETheorem 8.6≡⟦(XSθ1)θ′)⟧ELemma 3.8=αβ ⟦XSθ1⟧E⟦θ′⟧E ETheorem 9.3, capt(θ1(XS)) ⊆E=αβ (⟦XS⟧D⟦θ1⟧E D)⟦θ′⟧E ETheorem 9.3≡⟦XS⟧D(⟦θ1⟧E D ◦⟦θ′⟧E E) Lemma 7.16

The result follows.End of proof

In Corollary 9.5, the precondition ⋃XS capt(θ2(XS)) ⊆E is necessary to prevent θ2 from introducing infinitely many capturable atoms. The ‘complexity’ of θ1 is unconstrained. In practice it is likely that we will care about a particular finite set of unknowns V (for example, fV (Pr) for some Pr), and the precondition can be correspondingly refined to consider just XS ∈V.

9.2. Translating permissive nominal unification to pattern unification; soundness, weak completeness

The main result of this subsection is Theorem 9.16.

It says that if D and E are ‘large enough’, then θ solves Pr if and only if ⟦θ⟧E D solves ⟦Pr⟧D. We call this ‘soundness and weak completeness’, to distinguish from a stronger completeness result we prove in Subsection 9.3.

Definition 9.6

An equation is a pair r?= s. A unification problem Pr is a finite set of equations. A solution to Pr is a θ such that rθ=αsθ for all r?=s ∈Pr.

Definition 9.7

If D = [d1, . . . , dn] and Pr = {r1?= s1, . . .} then define ⟦Pr⟧D by:

⟦Pr⟧D ={λd1. . . . λdn.⟦r⟧D?= λd1. . . . λdn.⟦s⟧D | r?= s ∈Pr}

For example, if Pr = {XS?= f(Y S, a, ZS)} where S = A< ∪{a, b}, then ⟦Pr⟧[a] = {λa.(XSa) ?= λa.(f (Y Sa) a (ZSa))}.

Definition 9.8 is a technical definition, and the results following it are technical lemmas required for Lemma 9.11, which is a key result for Lemma 9.13, which is itself needed for Theorem 9.16.

Definition 9.8

Define uncapt(r) by:

uncapt(a) = ∅ uncapt(π · XS) = S \ nontriv(π) uncapt([a]r) = uncapt(r) \ {a} uncapt(f(r1, . . . , rn)) = uncapt(r1) ∪· · · ∪uncapt(rn)

uncapt(r) is quite interesting; technically, it came about as the ‘right definition’ to make Lemmas 9.10, 9.11, and 9.12 work.7 Intuitively, it may be useful to think of uncapt(r) as collecting those atoms that are not necessarily in capt(r), but which could feature in capt([a]r) for some a.

For example, if a ∈S then a ∈ uncapt(XS) but

a ∉uncapt(a), a ∉uncapt([b][a]XS), and a ∉uncapt((b a) · XS).
Lemma 9.9

If A ⊆B then captA(r) ⊆ captB(r).

As a corollary, captA(r) ⊆ captA([a]r).

Proof

By induction on r. As captA([a]r) = captA∪{a}(r), the corollary follows.End of proof

Lemma 9.10

Suppose a ∈A. Then if a ∈ uncapt(r) then a ∈ captA(r).

As a corollary, a ∈ uncapt(r) implies a ∈ capt([a]r).

Proof

By induction on r.

• The cases a and f(r1, . . . , rn) are straightforward.

• The case [a]r. a ∈ uncapt([a]r) is impossible.

• The case [b]r. Suppose a ∈ uncapt([b]r). By Definition 9.8 a ∈ uncapt(r). By inductive hypothesis a ∈ captA(r). By Lemma 9.9 a ∈ captA([b]r) as required.

• The case π·XS. Suppose a ∈ uncapt(π·XS), so a ∈S \nontriv(π). By assumption a ∈A so a ∈ (nontriv(π) ∪A) ∩S = captA(π · XS).End of proof

Lemma 9.11

captA(π · r) ⊆ ((nontriv(π) ∪A) ∩ uncapt(r)) ∪ capt(r).

Proof

See Appendix Appendix A. We use Lemmas 9.9 and 9.10.End of proof

Lemma 9.12

uncapt(r) ⊆ fa(r).

Proof

By a routine induction on r using Definitions 2.11 and 9.8.End of proof

Lemma 9.13

captA(rθ) ⊆ captA(r) ∪⋃XS∈fV (r) capt(θ(XS)).

Proof

By induction on r:

• The cases a and f(r1, . . . , rn). Straightforward.

• The case [a]r. We reason as follows:

captA([a](rθ)) = captA∪{a}(rθ) Definition 8.7⊆captA∪{a}(r) ∪⋃XS∈fV (r) capt(θ(XS)) Ind. hyp.= captA([a]r) ∪⋃XS∈fV (r) capt(θ(XS)) Definition 8.7

The result follows.

• The case π · XS. As (π · XS)θ ≡π · θ(XS), we reason as follows:

captA(π · θ(XS)) ⊆((nontriv(π) ∪A) ∩uncapt(θ(XS))) ∪capt(θ(XS)) Lemma 9.11⊆((nontriv(π) ∪A) ∩S) ∪capt(θ(XS)) Lemma 9.12= captA(π · XS) ∪capt(θ(XS)) Definition 8.7

The result follows.End of proof

Remark 9.14

capt(rθ) ⊆⋃fV (r) capt(θ(XS)) is not true in general. For example if a ∈S and b ∈S then capt([a]XS) = {a} and capt([XS:=[b]XS]) = {b}, and capt(([a]XS))θ = {a, b} ⊈{b}.

Lemma 9.15

Suppose capt(Pr) ⊆D and capt(Prθ) ⊆E. Then θ solves Pr if and only if ⟦θ⟧E D solves ⟦Pr⟧D.

Proof

We reason as follows, where D = [d1, . . . , dn]:

rθ =α sθ ⇔⟦rθ⟧E =α ⟦sθ⟧ETheorems 8.6 and 8.12⇔⟦r⟧D⟦θ⟧E D =αβ ⟦s⟧D⟦θ⟧E DTheorem 9.3⇔λd1. . . . λdn.⟦r⟧D⟦θ⟧E D =αβ λd1. . . . λdn.⟦s⟧D⟦θ⟧E Dfact of λ-terms⇔(λd1. . . . λdn.⟦r⟧D)⟦θ⟧E D =αβ (λd1. . . . λdn.⟦s⟧D)⟦θ⟧E Dno atom of D free in ⟦θ⟧E DEnd of proof

If D and E are ‘large enough’, then θ solves Pr if and only if the translation ⟦θ⟧E D solves the translation ⟦Pr⟧D:

Theorem 9.16 (Soundness and weak completeness).

Suppose

capt(Pr) ⊆D capt(θ(XS)) ⊆E for all XS ∈fV (Pr), and D ⊆E.

Then θ solves Pr if and only if ⟦θ⟧E D solves ⟦Pr⟧D.

Proof

Suppose capt(Pr) ⊆D, capt(θ(XS)) ⊆E for all XS ∈ fV (Pr), and D ⊆E. Then:

capt(Prθ) ⊆capt(Pr) ∪⋃XS∈fV (P r) capt(θ(XS)) Lemma 9.13⊆D ∪⋃XS∈fV (P r) capt(θ(XS)) capt(Pr) ⊆D⊆D ∪E capt(θ(XS)) ⊆E⊆E D ⊆E

By Lemma 9.15, θ solves Pr if and only if ⟦θ⟧E D solves ⟦Pr⟧D.End of proof

For example, Pr = {XS?= f(Y S, a, ZS)} where S = A< ∪{a, b} translates to ⟦Pr⟧[a] = {λa.(XS a) = λa.(f (Y S a) a (ZS a))}.

The solution [XS:=f(W S, a, b), Y S:=W S, ZS:=b] with S = A< ∪{a, b} translates to ⟦θ⟧[[a,b]a]= [XS:=λa.(f (W S a b) a b), Y S:=λa.(W S a b), ZS:=λa.b].

9.3. Strong Completeness

The main result of this subsection is Theorem 9.30. This strengthens the completeness result of Theorem 9.16, in a certain sense, by expressing that a class of σ solving ⟦Pr⟧D all originate from θ solving Pr, in a suitable formal sense.

Definition 9.17

Call a bijection on unknowns a renaming. ρ will range over renamings. Each X is also a λ-term (Definition 7.1), so each ρ is also a substitution (Definition 7.13).

Lemma 9.18

fa(g) = fa(gρ)

Proof

By induction on g.End of proof

Lemma 9.19

g =α h if and only if gρ =α hρ.

Proof

The left to right implication is by induction on the derivation of g =α h; right to left is by induction on the derivation of gρ =α hρ. We consider one case:

• The case (λ=αλab). For the left to right implication, suppose (b a) · g =α h and b ∉ fa(g). By inductive hypothesis ((b a) · g)ρ =α hρ. By Lemma 9.18, b ∉ fa(gρ). It is a fact that ((b a) · g)ρ ≡ (b a) · (gρ). It follows that (b a) · (gρ) =α hρ. Using (λ=αλab), λa.(gρ) =α λb.(hρ). The result follows. For the right to left implication, suppose (b a) · (gρ) =α hρ and b ∉ fa(gρ). It is a fact that (b a) · (gρ) ≡ ((b a) · g)ρ. It follows by inductive hypothesis that (b a) · g =α h. By Lemma 9.18, b ∉ fa(g). Using (λ=αλab), λa.g =α λb.h as required.End of proof

Definition 9.20

Define the substitution π · σ by: (π · σ)(X) ≡π · σ(X).

Note that π·σ is a substitution. g(π·σ) is not a shorthand for π·(gσ). g(π·σ) =α π·(gσ) does not hold in general; for example: a ≡a((b a) · id) ≢ (b a) · (a id). However:

Lemma 9.21

If nontriv(π) ∩ fa(g) = ∅ then g(π · σ) =α π · (gσ).

Proof

By a routine induction on g.End of proof

Lemma 9.22

σ solves ⟦Pr⟧D if and only if σ◦ρ does.

Suppose nontriv(π) ∩ (fa(r) ∪ fa(s)) = ∅ for every r?= s ∈Pr. Then σ solves ⟦Pr⟧D if and only if π · σ does.

Proof

For the first part, we have two cases:

• The case σ solves ⟦Pr⟧D implies σ◦ρ solves ⟦Pr⟧D. Suppose g?= h ∈⟦Pr⟧D and σ solves ⟦Pr⟧D. Then gσ =α hσ. By Lemma 9.19, gσρ =α hσρ. By Lemma 7.16, g(σ◦ρ) =α h(σ◦ρ), as required.

• The case σ◦ρ solves ⟦Pr⟧D implies σ solves ⟦Pr⟧D. Suppose g?= h ∈⟦Pr⟧D and σ◦ρ solves ⟦Pr⟧D. Then g(σ◦ρ) =α h(σ◦ρ). By Lemma 7.16, gσρ =α hσρ. By Lemma 9.19, gσ =α hσ, as required.

For the second part, suppose nontriv(π) ∩ (fa(r) ∪ fa(s)) = ∅ for every r?= s ∈Pr and D = [d1, . . . , dn]. Then ⟦Pr⟧D = {λd1. . . . λdn.⟦r⟧D?= λd1. . . . λdn.⟦s⟧D | r?= s ∈Pr}. By Lemma 8.4, nontriv(π)∩(fa(⟦r⟧D)∪fa(⟦s⟧D)) = ∅. The result follows from Lemma 9.21, and using Proposition 7.12 and Lemma 7.8.End of proof

Remark 9.23

Lemma 9.22 expresses an intuition that ‘names of atoms and unknowns on the right in a solution, do not matter’, which also underlies the π and ρ in Theorem 9.30. ρ is the price we pay for using the same unknowns in Definitions 7.1 and 2.6: This design decision makes Definition 8.3 compact, but it causes technical problems in Lemma 9.29, because σ(X) can introduce new unknowns over whose permission sets (back in the nominal world) we have no control. ρ lets us rename those new unknowns as convenient. As for π, we discuss it below.

Another design decision is to work with an untyped λ-terms. This simplifies our presentation and makes our results slightly more powerful (because they apply to more substitutions), but we cannot be too liberal: Suppose σ solves ⟦Pr⟧D. Examining Definition 8.3, if X occurs in ⟦Pr⟧D then it is applied to a number of atoms equal to the length of D ∩S. So, we will only be interested in σ that respect this fragment of typability (V will be fV (Pr)):

Definition 9.24

Let V be a finite set of unknowns. Call σ D-consistent on V when for every X ∈V, σ(X) =α λa1. . . . λan.q where n is the length of D ∩S. (So σ(X) starts with ‘at least’ length-D ∩S-many λ-abstractions.)

Call σ strictly D-consistent when also, for every X ∈V, fa(σ(X)) ∩D = [].

Remark 9.25

Strictness is motivated by the following examples: Take D = [a].

Take Pr = {XS?= f([a]Y S, Y S)} with S = A<. Then the problem

⟦Pr⟧D = {λa.(XS a)?= λa.(f (λa.(Y Sa)) (Y Sa))} has the solution σ = [XS:=λc.(f (λc.a) a), Y S:=λc.a].

Now (σ◦ρ)(Y S) =α ⟦θ⟧E D(Y S) is impossible for any ρ, since λc.a =α λa.⟦θ(Y S)⟧E is impossible.

Take Pr = {XS?= f([a]Y T, Y T)} with S = A< and T = A< \ {a}. Then the problem

⟦Pr⟧D = {λa.(XS a)?= λa.(f (λa.Y T ) Y T )} has the solution σ = [XS:=λc.(f (λc.a) a), Y T :=a].

Now (σ◦ρ)(Y T) =α ⟦θ⟧E D(Y T) is impossible, since a ∈ fa(a) whereas

a ∉ fa(⟦θ(Y T)⟧E) by Lemma 8.5. The a in σ(Y T) for the two σ considered above, has nothing to do with the a in D. We can regard this as an unfortunate ‘name-clash’ which Lemma 9.22 allows us to eliminate with a permutation π.

More on this in Theorem 9.30. We continue with the proofs:

Definition 9.26

Define the arguments of unknowns in a pattern q by:

args(a) = ∅ args(X) = ∅ args(Xa1 . . . an) = {a1, . . . , an}args(fq1 . . . qn) =⋃1≤i≤nargs(qi) args(λa.q) = args(q)

q =α r does not imply args(q) = args(r). This is by design.

Definition 9.27

Suppose q is a φ-pattern and args(q) ⊆E.

Define a nominal term q-E by:

a-E ≡a (Xb1 . . . bφ(X))-E ≡π·XS(λa.q)-E ≡[a]q-E(fq1 . . . qn)-E ≡f(q1-E, . . . , qn-E)

Here, for each E and X, π is a fixed but arbitrary choice of permutation of the atoms in E, mapping the ith element of E ∩S (Definition 8.2) to bi for 1 ≤i ≤ φ(X).

Lemma 9.28

args(q) ⊆E implies ⟦q-E⟧E ≡q.

Proof

By induction on q.End of proof

Lemma 9.29

Suppose V is a finite set of unknowns and σ is a φ-pattern substitution, strictly D-consistent on V.

Then there exist ρ, θ, and E, such that D ⊆E, ⋃X∈V capt(θ(X)) ⊆E, and (σ◦ρ)(X) =α ⟦θ⟧E D(X) for every X ∈V.

Proof

Take any E = [e1, ..., ep] which includes all atoms in D and in {σ(X) | X ∈V}. Define V′ = ⋃X∈V fV (σ(X)) (‘the unknowns in σ(X) for X ∈V’). For each Y ∈V′ choose a fresh Y ′ such that the length of E ∩ fa(Y ′) is equal to φ(Y ). We do this injectively, so that for distinct Y, Z ∈V′, Y ′ and Z′ are also distinct. Let ρ be any renaming such that ρ(Y ) ≡Y ′ for all Y ∈V′.

By assumption σ(X) =α λa1. . . . λan.q for a φ-pattern q, where [a1, . . . , an] = D ∩S. Take θ(X) ≡ (qρ)-E.

We can verify that ⋃X∈V capt(θ(X)) ⊆E. We then reason as follows:

⟦θ⟧E D(X) ≡λa1. . . . λan.⟦(qρ)-E⟧EDefinition 9.1≡λa1. . . . λan.(qρ) Lemma 9.28≡(λa1. . . . λan.q)ρ Fact of λ-terms=α (σ◦ρ)(X) By constructionEnd of proof
Theorem 9.30 (Strong completeness).

Suppose capt(Pr) ⊆D.

For σ strictly D-consistent on fV (Pr) solving ⟦Pr⟧D there are ρ, θ, and E, such that

(σ◦ρ)(X) =α ⟦θ⟧E D(X) for all X ∈fV (Pr) and θ solves Pr.

For σ D-consistent on fV (Pr) solving ⟦Pr⟧D there are π, ρ, θ, and E, such that

π·(σ◦ρ)(X) =α ⟦θ⟧E D(X) for all X ∈fV (Pr) and θ solves Pr.
Proof

By Lemma 9.29, there are ρ, θ, and E, such that (σ◦ρ)(X) =α ⟦θ⟧E D(X) for all X ∈ fV (Pr), D⊆E and ⋃X∈fV (P r) capt(θ(X)) ⊆E. capt(Pr) ⊆D and D ⊆E, so capt(Pr) ⊆E. By Theorem 9.16, θ solves Pr.

For the second part, write D = [d1, . . . , dn], choose D′ = [d′ 1, . . . , d′ n] fresh (so d′ i is not in D, Pr, or σ(X) for any X ∈ fV (Pr)), and take π = (d′ 1 d1) . . . (d′ n dn). π · σ is strictly D-consistent and the result follows from the first part and Lemma 9.22.End of proof

10. Conclusions

In this paper, we have presented a syntax which slightly generalises nominal terms and obtains significantly enhanced properties. We gain ‘always fresh’ and ‘always rename’ properties (Corollaries 2.14 and 2.15) which are present in first- and higher-order syntax, absent in nominal terms, and regained in permissive nominal terms.

We do not claim a telling difference in expressivity in practice between nominal and permissive nominal terms. It may indeed be that permissive nominal terms can express some things that nominal terms cannot8 but expressivity is not our main motivation in this paper. The issues which motivate us are with the properties of these syntaxes. As we have seen in this paper, a significant new body of mathematics follows from these changes, which at first seem so innocuous. It does not stop there; the interested reader can find more in [15].

Permissive nominal terms do not obsolete nominal terms. To discuss ‘an arbitrary term’, a nominal terms unknown ˙X may be more directly useful than a permissive nominal terms unknown X𝔸< (which means ‘an arbitrary term, mentioning atoms in A<’).

We have leveraged the difference between nominal terms and permissive nominal terms to obtain a new unification algorithm which is more efficient in the sense that it is based just on substitutions, and in that sense is also more like the notion of solution familiar from first- and higher-order syntax. Freshness problems are solved ‘all in one go’ by a distinct algorithm. We have interpreted nominal unification as a subsystem of permissive nominal unification (Section 4).

One nice way to view this interpretation is that A< plays the role of ‘the atoms we had so far’ and A> that of ‘the atoms we will generate fresh in the future’. Finally, we have exhibited permissive nominal unification as equivalent to higher-order pattern unification.

10.1. Related work

Infinite sets of atoms

Permissive nominal terms are based on the idea of infinite and co-infinite sets of atoms S. This is new, but it emerges from a literature rich in precedents. As we noted in Remark 2.22, infinite and co-infinite sets break with the standard nominal sets semantics from [25], which does not admit them because they do not have finite support. This is however not a serious mathematical problem: the idea of relaxing the ‘finite support’ property of nominal sets to infinite generalisations is natural.

As far as we know this was first discussed in [11], where the second author proposed to identify ‘small’ sets of atoms not with cardinality but with well-orderability of the atoms in the set — so a set of atoms is small when it can be assigned a cardinal size, and large when it cannot be assigned a cardinal size (internally, within the model) — but we do not commit ourselves to how large those cardinals can get, and in particular they could be infinite. See [13] for a more extended treatment of the same ideas.

Pitts referred to the possibility of using nominal sets with infinite support in [37], in order to obtain a complete semantics for nominal logic. This idea was taken up by Cheney in [6]. Thus, in [6] ‘small’ sets of atoms are identified as elements of a support ideal (Definition 4.1 of [6]), which are similar in spirit to the set of permission sets from Definition 2.2. In Definition 2.2 we give a concrete set of permission sets, but in a footnote to that definition we also identify some reasonable abstract conditions for the set of permission sets to satisfy such that the proofs in this paper still work. These conditions are extremely mild; the structure actually required of permission sets is much weaker than that provided by Definition 2.2.

Namespaces

Since this paper was written, the second author has prepared a manuscript treating permissive nominal algebra [15] (a precursor is [22]). There, the set of all atoms is taken to be uncountable and permission sets are taken to be all countably infinite sets of atoms. This setting is sufficiently general to accommodate many different notions of permission sets as subsystems. In particular the permission sets of this paper feature as a ‘namespace’ identified by A<; thus, the ideas in this paper slot quite nicely into a more abstract setting.

‘Free atoms of’ as distinct from ‘support of the denotation of’

It may be useful to note some work to which this paper is not related. One nice aspect of permissive nominal terms is that they give us a notion of ‘free atoms of a term’ fa(r). The judgement ∇⊢a#r of nominal terms corresponds to the judgement a ∉ fa(r) of permissive nominal terms (see Lemma 4.8) and both correspond to the informal judgement ‘a is not free in r’.

Nominal sets have a native notion of semantic freshness; a#semr means ‘a is not in the support of the denotation of r’. Semantic freshness is a distinct concept. The reader should not confuse semantic freshness with the intensional judgement ‘free atoms of’ used in this paper.

Semantic freshness may be expressed using ‘free atoms of’ and equality [17, 21, 15].

Patterns

Patterns emerged by studying Skolemisation of unification problems [32]; they proved useful in the unification of higher-order abstract syntax terms [31].

Cheney proposed a two-stage translation of higher-order pattern unification to nominal unification [4], first by exhibiting a translation of higher-order pattern unification to nominal pattern unification (where nominal patterns are a variant of nominal terms, with a concretion operator, where unknowns have empty support), followed by a translation between nominal pattern unification and nominal unification.

Levy and Villaret related nominal unifiability with higher-order pattern unifiability in [29]. Our treatment translates solutions as well, handles a more general class of higher-order patterns than considered in [29], and we prove our translation complete (Theorem 9.30) and optimal (Subsection 8.2).

Note that translating solutions really matters: it might have been, for example, that higher-order pattern unification and permissive nominal unification have the same notion of unifiability — but very different notions of solution and sets of solutions. For comparison, the λ-calculus and combinators express similar notions of computability, but have very different notions of reduction and computation.

The version of higher-order pattern unification which we examine is more general than usual, since we do not type our λ-terms. We show how to retain enough of the properties of typing to avoid ‘silly’ problems. For example, we do not consider untyped higher-order pattern unification problems like X =αβ λa.(Xa), because this cannot be expressed as a unification of two φ-patterns for any φ (Definition 7.19) — we impose a structural condition on our patterns that X should be applied to a consistent, fixed number of arguments.

We hypothesise that the results in this paper would work in a typed setting; the conditions which our proofs depend on to work are just structural ones, which would also be guaranteed by types. We have not investigated the effects of η-conversion; this is future work.

The broader literature

Hamana’s β0 unification of λ-terms with holes adds a capturing substitution [26]. Level 2 variables (which are instantiated) are annotated with level 1 variable symbols that may appear in them; permissive nominal terms move in this direction in the sense that permission sets also describe which level 1 variable symbols (we call them atoms in this paper) may appear in them, though with our permission sets there are infinitely many that may, and infinitely many that may not. Another significant difference is that the treatment of α-equivalence in Hamana’s system is not nominal (not based on permutations) and unlike our systems, Hamana’s does not have most general unifiers.

Similarly, Qu-Prolog [34] adds level 2 variables, but does not manage α-conversion in nominal style, and, for better or for worse, the system is more ambitious in what it expresses, and thus loses mathematical properties (unification is semi-decidable, most general unifiers need not exist).

10.2. Future work

We propose permissive nominal terms as a syntax for designing logics and λ-calculi in the spirit of nominal terms.

A first implementation of permissive nominal unification has been made [33] by the third author.

We have begun to apply permissive nominal terms to construct novel logics and λ-calculi, taking advantage of their properties to simplify the theory. It is simply very useful to reason on terms (without a freshness context), to have an inexhaustible supply of fresh names, and to be able to quotient by α-equivalence. We note in particular the papers [24, 23, 19, 18, 20], in which we have struggled with the theory of α-equivalence given to us by nominal terms; these might benefit from the use of permissive nominal terms.

Permissive nominal terms syntax has two levels of variable, atoms a and unknowns X. There is no reason to stop there; we have already considered syntaxes with more than two levels of variable, for example [14, 16]. Again, we had difficulty with α-conversion and fresh atoms. It would be very interesting to revisit this material armed with the permissive ideas of this paper.

Finally, it may be possible to extend the techniques of this paper to biject full higher-order unification with an enrichment of (permissive) nominal unification.

References

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

[2] Christophe Calvès. A Haskell Nominal Toolkit. In 2nd International Workshop on Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009), 2009. source code available online at: http://www.dcs.kcl.ac.uk/pg/calves/hnt/.

[3] James Cheney. Nominal Logic Programming. PhD thesis, Cornell University, August 2004.

[4] James Cheney. Relating nominal and higher-order pattern unification. In Proceedings of the 19th International Workshop on Unification (UNIF 2005), pages 104–119, 2005.

[5] James Cheney. Scrap your nameplate: (functional pearl). SIGPLAN Notices, 40(9):180– 191, 2005.

[6] James Cheney. Completeness and Herbrand theorems for nominal logic. Journal of Symbolic Logic, 71:299–320, 2006.

[7] James Cheney and Christian Urban. Alpha-prolog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proceedings of the 20th International Conference on Logic Programming (ICLP 2004), number 3132 in Lecture Notes in Computer Science, pages 269–283. Springer, 2004.

[8] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. Technical Report HW-MACS-TR-0062, Heriot-Watt University, 2009. Available online at gabbay.org.uk/papers/perntu-tr.pdf.

[9] Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Binding logic: Proofs and models. In LPAR ’02: Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, pages 130–144, London, UK, 2002. Springer.

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

[11] Murdoch J. Gabbay. FM-HOL, a higher-order theory of names. In F. Kamareddine, editor, 35 Years of Automath, 2002.

[12] Murdoch J. Gabbay. A NEW calculus of contexts. In PPDP ’05: Proc. of the 7th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, pages 94–105. ACM, 2005.

[13] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982–1011, July 2007.

[14] Murdoch J. Gabbay. Hierarchical Nominal Terms and Their Theory of Rewriting. Electronic Notes in Theoretical Computer Science, 174(5):37–52, 2007.

[15] Murdoch J. Gabbay. Permissive nominal algebra and semantic nominal unknowns: a new universal algebra for nominal techniques. Manuscript, 2010.

[16] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus (extended version). Information and computation, 207(12):1369–1400, 2009.

[17] Murdoch J. Gabbay and Aad Mathijssen. A Formal Calculus for Informal Equality with Binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162–176. Springer, 2007.

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

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

[20] Murdoch J. Gabbay and Aad Mathijssen. A nominal axiomatisation of the lambda-calculus. Journal of Logic and Computation, September 2009. Online access.

[21] Murdoch J. Gabbay and Aad Mathijssen. Nominal (universal) algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, 2009.

[22] Murdoch J. Gabbay and Dominic P. Mulligan. Semantic nominal terms. In 2nd International Workshop on Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009), 2009.

[23] Murdoch J. Gabbay and Dominic P. Mulligan. Two level lambda-calculus. Electronic Notes in Theoretical Computer Science, 246:107–129, 2009.

[24] Murdoch J. Gabbay and Dominic P. Mulligan. Curry-Howard for incomplete first-order logic derivations using one-and-a-half level terms. Information and Computation, 208:230– 258, 2010.

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

[26] Makoto Hamana. A logic programming language based on binding algebras. In TACS’01, volume 2215 of Lecture Notes in Computer Science, pages 243–262. Springer, 2001.

[27] Robert Harper, Furio Honsell, and Gordon Plotkin. A framework for defining logics. In Proc. 2nd Annual IEEE Symposium on Logic in Computer Science, LICS’87, pages 194–204. IEEE Computer Society Press, 1987.

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

[29] Jordi Levy and Mateu Villaret. Nominal unification from a higher-order perspective. In Proceedings of RTA’08, volume 5117 of Lecture Notes in Computer Science. Springer, 2008.

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

[31] Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation, 1(4):497 – 536, 1991.

[32] Dale Miller. Unification under a mixed prefix. Journal of Symbolic Computation, 14(4):321–358, 1992.

[33] Dominic P. Mulligan. Implementation of permissive nominal terms. source code available online at: http://www.macs.hw.ac.uk/˜dpm8/permissive/, 2009.

[34] Peter Nickolas and Peter J. Robinson. The Qu-Prolog unification algorithm: formalisation and correctness. Theoretical Computer Science, 169(1):81–112, 1996.

[35] Lawrence C. Paulson. Isabelle: the next 700 theorem provers. In P. Odifreddi, editor, Logic and Computer Science, pages 361–386. Academic Press, 1990.

[36] Frank Pfenning and Conal Elliot. Higher-order abstract syntax. In PLDI (Programming Language design and Implementation), pages 199–208. ACM Press, 1988.

[37] Andrew M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186(2):165–193, 2003.

[38] Andrew M. Pitts and Murdoch J. Gabbay. A Metalanguage for Programming with Bound Names Modulo Renaming. In MPC2000, volume 1837 of Lecture Notes in Computer Science, pages 230–255. Springer, 2000.

[39] Mark R. Shinwell, Andrew M. Pitts, and Murdoch J. Gabbay. FreshML: Programming with Binders Made Simple. In ICFP’03, volume 38, pages 263–274. ACM Press, 2003.

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

Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.

Appendix A. Supplementary proofs

Definition Appendix A.1 is useful for Proposition 2.21.

Definition Appendix A.1.

Define the size of a term r by:

size(a) = 0 size(f(r1, . . . , rn)) = ∑1≤i≤n size(ri)size([a]r) = 1+size(r) size(π·XS) = 0

Proof of Proposition 2.21:

Proof

Reflexivity is shown by induction on terms. Symmetry is shown by induction on derivations. Transitivity is shown by induction on the size of a term. We consider one case from the proof of symmetry and one from the proof of transitivity:

• [a]r =α [b]s implies [b]s =α [a]r. Suppose (b a)·r =α s and b ∉ fa(r). By Lemma 2.17 a ∉ fa((a b) · r). From Lemmas 2.16 and 2.18, r =α (a b) · s. By Lemma 2.19, a ∉ fa(s). It is a fact that the size of terms is unaffected by permutation, so by inductive hypothesis (a b) · s =α r. Extending with (=α[b]) we obtain [b]s =α [a]r as required.

• [a]r =α [b]s and [b]s =α [c]t imply [a]r =α [c]t. Suppose (b a) · r =α s, (c b) · s =α t, b ∉ fa(r) and c ∉ fa(s). By Lemma 2.18 (c b) · ((b a) · r) =α (c b) · s. It is a fact that the size of terms is unaffected by permutation, so by inductive hypothesis also (c b) · ((b a) · r) =α t, and by Lemmas 2.20 and 2.16 (c a) · r =α t. By Lemma 2.19 c ∉ fa((b a) · r), so by Lemma 2.17 c ∉ (b a) · fa(r). Therefore, c ∉ fa(r). We use (=α[b]) to derive [a]r =α [c]t as required.End of proof

Proof of Lemma 3.3:

Proof

By induction on r.

• The cases a and f(r1, . . . , rn) are routine.

• The case [a]r. We reason as follows:

fa(([a]r)θ) ≡fa([a]rθ) Definition 3.2= fa(rθ) \ {a} Definition 2.11⊆fa(r) \ {a} Inductive hypothesis= fa([a]r) Definition 2.11

The result follows.

• The case π·XS. By Definition 2.11, fa(π·XS) = π·S. By Definition 3.1, fa(θ(XS)) ⊆ S. Using Lemma 2.17, it follows fa(π · θ(XS)) ⊆π · S.End of proof

Proof of Lemma 4.8:

Proof

We handle the two implications separately.

• The case ι(˙a) ∉ fa(⟦ ˙r⟧∆) implies ∆⊢˙a# ˙r. We proceed by induction on ˙r.

• The cases ˙b and f( ˙r1, . . . , ˙rn) are straightforward.

• The case [˙a] ˙r. Since ∆⊢˙a#[˙a] ˙r always, using (#[ȧ]).

• The case [˙b] ˙r. Suppose ι(˙a) ∉ fa(⟦[ι(˙b)] ˙r⟧∆) and ι(˙a) ∉ fa(⟦ ˙r⟧∆) \ {ι(˙b)}. Then ι(˙a) ∉ fa(⟦ ˙r⟧∆), therefore ∆⊢˙a# ˙r by inductive hypothesis. Using (#[ ḃ]), we have ∆⊢˙a#[˙b] ˙r, and the result follows.

• The case ˙π · ˙X. Suppose ι(˙a) ∉ fa(⟦ ˙π · ˙X⟧∆). Then ι(˙a) ∉⟦ ˙π⟧ · S, where S = A< \ {ι(˙a) | ˙a# ˙X ∈∆}. But ⟦ ˙π⟧ · A< \ {ι(˙a) | ˙a# ˙X ∈∆} is the same as ⟦ ˙π⟧ · A< \ ⟦ ˙π⟧ · {ι(˙a) | ˙a# ˙X ∈∆}. Then ⟦ ˙π⟧ · {ι(˙a) | ˙a# ˙X ∈∆} = {⟦ ˙π⟧ · ι(˙a) | ˙a# ˙X ∈∆}. Using Definition 4.6, and the fact permutations are bijective, we have {⟦ ˙π⟧ · ι(˙a) | a#X ∈∆} = {ι( ˙π-1 · ˙a) | ˙π-1 · ˙a#X ∈∆}. We use (# Ẋ) to obtain ∆⊢˙a# ˙X, and we have the result.

• The case ∆⊢˙a# ˙r implies ι(˙a) ∉ fa(⟦ ˙r⟧∆). We proceed by induction on the derivation of ∆⊢˙a# ˙r.

• The cases (# ḃ) and (#f) are routine.

• The case (#[ȧ]). Suppose ∆⊢˙a#[˙a] ˙r using (#[ȧ]). Then ⟦[˙a] ˙r⟧∆≡ [ι(˙a)]⟦ ˙r⟧∆. Further, ι(˙a) ∉ fa(⟦ ˙r⟧∆) \ {ι(˙a)}, and the result follows.

• The case (#[ ḃ]). Suppose ∆⊢˙a# ˙r and ι(˙a) ∉ fa( ˙r) by assumption. Then ∆⊢˙a#[˙b] ˙r by (#[ ḃ]). Further, fa(⟦[˙b] ˙r⟧∆) = fa(⟦ ˙r⟧∆) \ {ι(˙b)}, and the result follows.

• The case (# Ẋ). Suppose ˙π-1(˙a)# ˙X ∈∆, and ∆⊢˙a# ˙π · ˙X by (# Ẋ). Then ⟦ ˙π · ˙X⟧∆= ⟦ ˙π⟧ · XS where S = A< \ {ι(˙a) | ˙a# ˙X ∈∆}. Further, fa(⟦ ˙π⟧ · XS) = ⟦ ˙π⟧ · S. The result follows from Definition 4.6.End of proof

Proof of Theorem 4.9:

Proof

We prove that ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ implies ∆⊢˙r = ˙s by induction on the derivation of ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆:

• The cases ˙a and f( ˙r1, . . . , ˙rn) are routine.

• The case (=α[a]). Suppose ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ and ∆⊢˙r = ˙s. Then using (=α[a]), [ι(˙a)]⟦ ˙r⟧∆=α [ι(˙a)]⟦ ˙s⟧∆ and ∆⊢[˙a] ˙r = [˙a] ˙s also, using (=[ȧ]). The result follows, as [ι(˙a)]⟦ ˙r⟧∆= ⟦[˙a] ˙r⟧∆.

• The case (=α[b]). Suppose (ι(˙b) ι(˙a)) · ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ and ι(˙b) ∉ fa(⟦ ˙r⟧∆). By Lemmas 4.7 and 4.8 ⟦(˙b ˙a) · ˙r⟧∆=α ⟦ ˙s⟧∆ and ∆⊢˙b# ˙r. By inductive hypothesis ∆⊢ (˙b ˙a) · ˙r = ˙s. We use (=[ḃ ]).

• The case (=αX). Suppose ⟦ ˙π⟧|S = ⟦ ˙π′⟧|S where S = A<\{ι(˙a) | ˙a# ˙X∈∆}. ι is injective, so a# ˙X ∈∆ for all ˙a such that ˙π(˙a) ≠ ˙π′(˙a). The result follows by (=Ẋ ).

We prove that ∆⊢˙r = ˙s implies ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ by induction on the derivation of ∆⊢ ˙r = ˙s:

• The cases (=ȧ), (=f) and (=[ȧ]) are straightforward.

• The case (=[ḃ ]). Suppose ∆⊢ (˙b ˙a) · ˙r = ˙s and ∆⊢˙b# ˙r. By inductive hypothesis and Lemma 4.7, (˙b ˙a) · ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆. By Lemma 4.8, ι(˙b) ∉ fa(⟦ ˙r⟧∆). The result follows by (=α[b]).

• The case (=Ẋ ). Recall that ⟦ ˙π · ˙X⟧∆= ⟦ ˙π⟧ · XS and ⟦ ˙π′ · ˙X⟧∆= ⟦ ˙π′⟧ · XS where S = A< \ {ι(˙a) | ˙a# ˙X ∈∆}. Suppose ˙π(˙a) ≠ ˙π′(˙a) implies ∆⊢˙a# ˙X. Using Lemma 4.8, ⟦ ˙π⟧(ι(˙a)) ≠ ⟦ ˙π′⟧(ι(˙a)) implies ι(˙a) ∉S. The result follows by (=αX).End of proof

Proof of Lemma 4.13:

Proof

By induction on ˙r. We show two cases:

• The case [˙a] ˙r. We reason as follows:

⟦([˙a] ˙r) ˙θ⟧∆≡⟦[˙a] ˙r ˙θ⟧∆Definition 4.10≡[ι(˙a)]⟦ ˙r ˙θ⟧∆Definition 4.6≡[ι(˙a)]⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ Inductive hypothesis≡([ι(˙a)]⟦ ˙r⟧∆)⟦(∆, ˙θ)⟧ Fact≡⟦[˙a] ˙r⟧∆⟦(∆, ˙θ)⟧ Definition 4.6

The result follows.

• The case ˙π · ˙X. We reason as follows:

⟦( ˙π · ˙X) ˙θ⟧∆≡⟦ ˙π · ˙θ( ˙X)⟧∆Definition 4.10≡⟦ ˙π⟧ · ⟦ ˙θ( ˙X)⟧∆Definition 4.6≡⟦ ˙π⟧ · ⟦ ˙θ⟧(⟦ ˙X⟧∆) Definition 3.1

The result follows.End of proof

Proof of Lemma 4.15:

Proof

We prove by induction on r that a ∉ fa(r) implies (b a) · r =α r:

• The cases c and f(r1, . . . , rn). Straightforward.

• The cases [a]r. We show (b a) · [a]r =α [a]r where b ∉ fa([a]r), hence b ∉ fa(r) and a ∉ fa(r). By Definition 2.9, (b a) · [a]r =α [b](b a) · r. By Definition 2.13, we must show (a b) · ((b a) · r) =α r where a ∉ fa((b a) · r). By Lemma 2.17, b ∉ fa(r) implies a ∉ fa((b a) · r). By Lemma 2.16, (a b) · ((b a) · r) =α ((a b)◦(b a)) · r. As π = π-1, we have r =α r. The result follows from Proposition 2.21.

• The case [b]r is similar.

• The case [c]r. Suppose b ∉ fa([c]r), a ∉ fa([c]r) and a, b ∉ fa(r). We show (b a) · [c]r =α [c]r. By Definition 2.9, (b a) · [c]r ≡ [c](b a) · r. We use (=α[a]) and the inductive hypothesis to obtain (b a) · r =α r.

• The case π · XS. Suppose b ∉ fa(π · XS), a ∉ fa(π · XS) and a, b ∉π · S. By Definition 2.9, (b a)·(π·XS) ≡ ((b a)◦π)·XS. Using (=αX), ((b a)◦π)·XS =α π·XS whenever ((b a)◦π)|S = π|S. As a, b ∉π · S, ((b a)◦π)|S = π|S. The result follows.

We prove by induction on r that (b a) · r =α r implies a ∉ fa(r):

• The case a, b, c and f(r1, . . . , rn) are routine.

• The case [a]r. Suppose (b a) · [a]r =α [a]r. By Definition 2.9, (b a) · [a]r ≡ [b](b a) · r. By Definition 2.13, [b](b a)·r =α [a]r whenever (a b)·((b a)·r) =α r with a ∉ fa((b a)· r). By Lemma 2.16, and the fact that swappings are self-inverse, (a b)·((b a)·r) ≡r. By assumption, b ∉ fa(r). By Lemma 2.17, a ∉ fa((b a) · r). The result follows.

• The case [b]r is similar.

• The case [c]r. By inductive hypothesis (b a) · r =α r implies a ∉ fa(r). The result follows from [c](b a) · r ≡ (b a) · [c]r.

• The case π · XS. Suppose (b a) · π · XS =α π · XS. By Definition 2.9, (b a) · π · XS ≡ ((b a)◦π) · XS. Using (=αX), ((b a)◦π) · XS =α π · XS whenever (b a)◦π|S = π|S. It is a fact that (b a)◦π|S = π|S only when b, a ∉π · S. The result follows.End of proof

The following definition is used in the proof of Proposition 5.4:

Definition Appendix A.2.

Define the size of a support inclusion problem size(Inc) to be a tuple (T, A, P, S), where: −T is the number of term-formers appearing within terms in Inc, −A is the number of abstractions appearing within terms in Inc, −P is the number of permutations, distinct from the identity permutation, appearing within terms in Inc, and −S is the number of support inclusions within Inc. We order tuples lexicographically.

Proof of Proposition 5.4:

Proof

By case analysis, checking all simplification rules reduce the measure defined in Definition Appendix A.2.

• The case a ⊑T, Inc′. Suppose a ∈T, size(a ⊑T, Inc′) = (T, A, P, S), and a ⊑ T, Inc′ =⇒ Inc′ by (⊑a). Then size(Inc′) = (T, A, P, S − 1). Otherwise, suppose a ∉T so (⊑a) is not applicable. No other rule is applicable by assumption, and the result follows.

• The case f(r1, . . . , rn) ⊑T, Inc′. Suppose size(f(r1, . . . , rn) ⊑T, Inc′) = (T, A, P, S) and f(r1, . . . , rn) ⊑T, Inc′ =⇒ r1 ⊑T, . . . , rn ⊑T, Inc′ by (⊑f). Then size(r1 ⊑ T, . . . , rn ⊑T, Inc′) = (T − 1, A, P, S + n − 1). The result follows from the ordering.

• The case [a]r ⊑T, Inc′. Suppose size([a]r ⊑T, Inc′) = (T, A, P, S) and [a]r ⊑ T, Inc′ =⇒r ⊑T ∪{a}, Inc′ by (⊑[]). Then size(r ⊑T ∪{a}, Inc′) = (T, A− 1, P, S) and the result follows.

• The case π · XS ⊑T, Inc′. Suppose size(π · XS ⊑T, Inc′) = (T, A, P, S). Then, if S ⊆π-1·T, we have π·XS ⊑T, Inc′ =⇒ Inc′ by (⊑X′), with measure (T, A, P, S−1). Otherwise, if we have S ⊈π-1 · T and π ≠ id, we have π · XS ⊑T, Inc′ =⇒

XS ⊑π-1 · T, Inc′ with measure (T, A, P − 1, S). By assumption, no other rules are applicable.End of proof

The following definition is used in the proof of Proposition 6.7:

Definition Appendix A.3.

Define the size of a unification problem size(Pr) to be a tuple (E, T, A), where: −E is the number of equalities appearing in the unification problem, −T is the number of term-formers appearing within terms in the equalities of the unification problem, −A is the number of abstractions appearing within terms in the equalities of the unification problem. We order tuples lexicographically.

Proof of Proposition 6.7:

Proof

By case analysis, checking all simplification rules reduce the measure defined in Definition Appendix A.3. We consider three cases:

− The case (?=[b]). Suppose b ∉ fa(r) and V; [a]r?= [b]s, Pr =⇒V; (b a) · r?= s, Pr by (?=[b]). Suppose further that size([a]r?= [b]s, Pr) = (E, T, A). Then size((b a) · r?= s, Pr) = (E, T, A − 1), and the result follows.

[XS:=π-1·s]

− The case (I1). Suppose XS ∉ fV (s) and fa(S) ⊆π·S, and V; π·XS?= s, Pr=⇒ V; Pr[XS:=π-1 · s] by (I1). Suppose further that size(π · XS?= s, Pr) = (E, T, A). Then size(Pr[XS:=π-1 · s]) = (E − 1, T, A), and the result follows. − The case (I3). It is a fact that rewriting with (I3) terminates, because of the condition that Pr⊑ is non-trivial.End of proof

Proof of Lemma 6.8:

Proof

The empty set cannot be simplified, so suppose Pr = r?= s, Pr′ where the simplification rule acts on r?= s. We reason by cases:

• The cases (?=a), (?=f) and (?=X) are straightforward.

• The case (?=[a]). Suppose Pr = [a]r?= [a]s, Pr′ and [a]r?= [a]s, Pr′ =⇒r?= s, Pr′ by (?=[a]). Then:

• Suppose ([a]r)θ =α ([a]s)θ. By Definition 3.2, [a](rθ) =α [a](sθ). By the rules in Definition 2.13, rθ =α sθ. The result follows.

• Suppose rθ =α sθ. By the rules in Definition 3.2, [a](rθ) =α [a](sθ). By Definition 3.2, ([a]r)θ =α ([a]s)θ, as required.

• The case (?=[b]). Suppose Pr = [a]r?= [b]s, Pr′, b ∉ fa(r) and Pr =⇒ (b a) · r?=

s, Pr′ with (?=[b]). Then:

• Suppose ([a]r)θ =α ([b]s)θ. By Definition 3.2, [a](rθ) =α [b](sθ). By the rules in Definition 2.13, (b a) · (rθ) =α sθ. By Lemma 3.4 and Proposition 2.21, ((b a) · r)θ =α sθ. The result follows.

• Suppose ((b a)·r)θ =α sθ. By Lemma 3.4 and Proposition 2.21, (b a)·(rθ) =α sθ. By Lemma 3.3, b ∉ fa(rθ). Using (=α[b]), [a](rθ) =α [b](sθ). By Definition 3.2 [a](rθ) =α [b](sθ), as required.End of proof

Proof of Lemma 6.14:

Proof

As the empty set cannot be simplified, it must be that Pr = r?= s, Pr′. It therefore suffices to perform case analysis on the simplification of r?= s. At each stage, without loss of generality, assume Pr′ has been simplified by non-instantiating rules as much as possible.

• The cases (?=a), (?=f) and (=αX) are routine.

• The case (?=[a]). Suppose V; [a]r?= [a]s, Pr′ and fV ([a]r?= [a]s, Pr′) ⊆V, then V; [a]r?= [a]s, Pr′ =⇒V; r?= s, Pr′ by (?=[a]). By Definitions 2.12 and 6.4, fV (r?= s, Pr′) ⊆V, and the result follows.

• The case (?=[b]). Suppose V; [a]r?= [b]s, Pr′, b ∉ fa(r) with fV ([a]r?= [b]s, Pr′) ⊆ V, then V; [a]r?= [b]s, Pr′ =⇒V; (b a) · r?= s, Pr′ by (?=[a]). By Definitions 2.12 and 6.4 it follows that fV ((b a) · r) ⊆V, and the result follows.End of proof

Proof of Proposition 7.12:

Proof

We prove reflexivity by induction on terms; symmetry by induction on derivations; transitivity by induction on the size of a term. We include one case from the proof of symmetry, and one from the proof of transitivity:

• λa.g =α λb.h implies λb.h =α λa.g. Suppose (b a) · g =α h and b ∉ fa(g). By Lemma 7.7, a ∉ fa((b a) · h). By Lemmas 7.8 and 7.6, g =α (b a) · h. By Lemma 7.9, a ∉ fa(h). By inductive hypothesis (b a) · h =α g. Extending with (λ=αλ[b]) we obtain λb.h =α λa.g, as required.

• λa.g =α λb.h and λb.h =α λc.k implies λa.g =α λc.k. Suppose (b a) · g =α h, (c b) · h =α k, b ∉ fa(g) and c ∉ fa(h). By Lemma 7.6, (c b) · ((b a) · g) =α (c b) · h. By Lemmas 7.11, 7.6 and 7.5 we have (c a) · g =α k. By Lemma 7.9, c ∉ fa((b a) · g). By Lemma 7.8, c ∉ fa(g). We use (λ=αλab) to obtain λa.g =α λc.k, and the result follows.End of proof

Proof of Lemma 8.9:

Proof

By induction on r.

• The cases a and f(r1, . . . , rn) are routine.

• The case [a]r. We reason as follows:

captA(π · [a]r) = captA([π(a)](π · r)) Definition 2.9= captA∪{π(a)}(π · r) Definition 8.7

There are now two cases:

• The case π(a) = a. Then:

captA∪{π(a)}(π · r) = captA∪{a}(π · r) Assumption= captA∪{a}(r) Inductive hypothesis= captA([a]r) Definition 8.7

The result follows.

• The case π(a) ≠ a. Then:

captA∪{π(a)}(π · r) = captA(π · r) Assumption, π(a) ≠ a= captA(r) Inductive hypothesis= captA([a]r) Definition 8.7

The result follows.

• The case π′ · XS. We reason as follows:

capt(π · (π′ · XS)) = captA((π◦π′) · XS) Lemma 2.16= (nontriv(π◦π′) ∪A) ∩S Definition 8.7= (nontriv(π) ∪nontriv(π′) ∪A) ∩S Fact= (nontriv(π′) ∪A) ∩S Assumption= captA(π′ · XS) Definition 8.7

The result follows.End of proof

Proof of Corollary 8.10:

Proof

We reason as follows:

captA([b]r) = captA∪{b}(r) Definition 8.7= captA∪{a,b}(r) Lemma 8.8, a ∉fa(r)= captA∪{a,b}((b a) · r) Lemma 8.9= captA∪{a}((b a) · r) Lemmas 8.8 and 2.17= captA([a](b a) · r) Definition 8.7

The result follows.End of proof

Proof of Lemma 8.13:

Proof

By induction on r.

• The cases a and f(r1, . . . , rn) are straightforward.

• The case [a]r. Suppose a ∈ captA([a]r). Then a ∈ captA∪{a}(r), and by inductive hypothesis XS ∈ fV (r) exists such that a ∈S. As fV ([a]r) = fV (r), the result follows.

• The case [b]r. Suppose a ∈ captA([b]r). Then a ∈ captA∪{b}(r), and by inductive hypothesis XS ∈ fV (r) exists such that a ∈S. As fV ([b]r) = fV (r), the result follows.

• The π · XS. The result follows immediately by Definition 8.7.End of proof

Proof of Lemma 9.11:

Proof

By induction on r.

• The cases a and f(r1, . . . , rn). Routine.

• The case [a]r. By Definitions 2.9 and 8.7

captA(π · [a]r) = captA∪{π(a)}(π · r).

By inductive hypothesis

captA∪{π(a)}(π · r) ⊆((nontriv(π) ∪A ∪{π(a)}) ∩uncapt(r)) ∪capt(r).

By Definition 9.8 uncapt([a]r) = uncapt(r) \ {a}, so it suffices to show that

((nontriv(π) ∪A ∪{π(a)}) ∩uncapt(r))∪capt(r)⊆((nontriv(π) ∪A) ∩(uncapt(r) \ {a}))∪capt([a]r).

By Lemma 9.9 capt(r) ⊆ capt([a]r). Therefore, we only need concern ourselves with the ‘extra π(a)’ on the left, and the ‘missing a’ on the right. We consider cases for the ‘extra π(a)’:

• Suppose π(a) ≠ a. Then π(a) ∈ nontriv(π).

• Suppose π(a) = a and a ∉ uncapt(r). Then {π(a)} ∩ uncapt(r) = ∅.

• Suppose π(a) = a and a ∈ uncapt(r). Then by Lemma 9.10 a ∈ capt([a]r).

We consider cases for the ‘missing a’:

• Suppose a ∉ uncapt(r). Then uncapt(r) \ {a} = uncapt(r).

• Suppose a ∈ uncapt(r). Then by Lemma 9.10 a ∈ capt([a]r).

In all cases, the result follows.

• The case π′ · XS. Then:

captA((π◦π′) · XS) = (nontriv(π◦π′) ∪A) ∩S ⊆(nontriv(π) ∪nontriv(π′) ∪A) ∩S = (((nontriv(π) ∪A) \ nontriv(π′)) ∩S) ∪(nontriv(π′) ∩S) = (((nontriv(π) ∪A) \ nontriv(π′)) ∩S) ∪capt(π′ · XS) = ((nontriv(π) ∪A) ∩(S \ nontriv(π′))) ∪capt(π′ · XS) = ((nontriv(π) ∪A) ∩uncapt(π′ · XS)) ∪capt(π′ · XS)

The result follows.End of proof

Notes

1For example, (b a) · [a](b a) ≡ [b]a (Definition 4.3) whereas (λx.(y x))[x/y] is equal to λx′.(x x′) where x′ is chosen fresh; with the permutation, the capture-avoidance is automatic, with the renaming we have to deliberately rename. This nice turn of phrase is due to Cheney, as far as we know. ↩

2An similar idea is behind the notion of freshness contexts with sufficient freshnesses in [12, Subsection 3.1]. ↩

3Another layer of complexity arises. Some natural definitions rely on a sufficiently large supply of fresh atoms being available. Even if we can always extend the freshness context, for a fixed freshness context there may be inputs for which the function cannot be defined, and so is partial. This happens for example to the canonical form function in Subsection 5.3 of [24]. ↩

4See the documentation for module Nominal.Matching at http://www.dcs.kcl.ac.uk/pg/calves/hnt/doc/Nominal-Matching.html and module Terms.Terms in the permissive nominal terms implementation source code, available at http://www.macs.hw.ac.uk/˜dpm8/permissive/ ↩

5Other versions of P are possible. We believe that a sufficient property for P is that it be: co-infinitely down-closed (so if S ∈P and S′ ⊆S is co-infinite, then S′ ∈P); and such that for any finite {S1, . . . , Sn} ⊆P, the union S1 ∪. . . ∪Sn is co-infinite (it does not have to be in P). The first property is sufficient to build the permission set in (1). The second property is sufficient to guarantee Corollary 2.14. This is similar in spirit to the notion of support ideal from [6, Definition 4.1]. ↩

6In fact, support inclusion simplification is confluent so nf (Inc) is also unique. A proof of confluence is in a technical report [8]. For our purposes in this paper, it suffices to know that a normal form exists. ↩

7Thanks to an anonymous referee for spotting the error in a previous proof. ↩

8Permission sets may be larger than 𝔸< as well as smaller, whereas intuitively in nominal terms freshness contexts can only make permission sets smaller. ↩