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

Permissive nominal terms and their unification

Gilles Doweka, Murdoch J. Gabbayb, Dominic P. Mulliganc

ahttp://www.lix.polytechnique.fr/~dowek

bhttp://www.gabbay.org.uk
chttp://www.macs.hw.ac.uk/~dpm8

Abstract

We introduce permissive nominal terms, and their unification.

Nominal terms are one way to extend first-order terms with binding. However, they lack some useful 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; and it is not always possible to ‘α-convert a bound variable symbol’.

Permissive nominal terms closely resemble nominal terms, but they recover these useful ‘always fresh’ and ‘always alpha-rename’ properties, familiar from first- and higher-order syntax. In the permissive world, freshness contexts are elided, and the notion of unifier is based on substitution alone, rather than on nominal terms’ notion of substitution plus freshness conditions.

We prove that expressivity is not lost moving to the permissive case. We provide a translation from nominal terms into permissive nominal terms and we prove that a nominal unification problem is solvable if and only if its translation into permissive nominal terms is.

Finally, we investigate the precise relation between nominal unification and Miller’s higher-order pattern unification. We translate nominal terms into the λ-calculus and show that the translation may also be applied to unification problems; the result is pattern unification. This cements an existing intuition that higher-order patterns are what is needed to unify encodings of nominal terms. This builds on a translation by Levy and Villaret, and refines it; both translations are parameterised by sets of atoms, but we identify a smaller parameter set and prove that it is as small as possible. We also translate solutions of nominal unification problems to solutions of higher-order pattern unification problems. We exhibit a general class of higher-order pattern solutions and show that every pattern solution in that class is the translation of a nominal unification solution up to a permutative renaming.

Key words: Nominal unification, higher-order pattern unification, nominal techniques

February 25, 2009

1. Introduction

Many formal languages feature variable 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 [8], extensions of rewriting on terms with binders [18, 20, 9], and programming languages and proof systems allowing datatypes with binders [25, 21, 26, 17, 24] and more generally, definitions of a notion of term where variables may be bound: nominal terms [27].

Introducing binding opens new possibilities: when a variable occurs in the scope of a binder, for instance in the term f([a]X) we may decide that the substitution of some term for X may capture the bound variable a or not. In the original formulation of nominal terms, we could decide to exclude this capture by imposing a condition a#X, forbidding a to appear in X. This example explains some of the features of nominal terms: two levels of variable (atoms, such as a, and unknowns, such as X), freshness conditions, such as a#X, and atom permutations.

Nominal terms preserved much of the flavour of first-order terms, while extending them, so that we could represent informal statements like “If y ∉ fv(t) then λx.t is α-equivalent with λy.[y/x]t” and “How can we choose t and u to make λx.λy.(y t) equal to λx.λx.(x u)?”. For instance, the first statement above may be rendered as a nominal term as the equality judgement b#X ⊢ [a]X = [b](b a) · X where a and b denote atoms, which represent the ‘x’ and ‘y’; X denotes an unknown, it represents the ‘t’; b#X is a freshness side-condition, it represents the ‘y ∉ fv(t)’; (b a) is a permutation meaning ‘map a to b and b to a’, it represents the ‘[y/x]’ (we assumed y ∉ fv(t), so this is possible). Yet original nominal terms possess some less attractive properties too:

• Freshness contexts are not fixed so we must often prove properties of terms-in-freshness context. This is harder than reasoning just about terms.

• We expect that we can always pick a fresh variable symbol and α-rename a bound variable. Not so in nominal terms; for X in the empty freshness context, there is

— by definition of the empty freshness context — no a such that we know a#X; further, we cannot α-rename abstracted a to a ‘fresh b’ to obtain [b](b a)·X, because there is no fresh b (this is useful e.g. for moving syntax under a binder). ‘Freshness contexts’ sound like ‘typing contexts’ for the λ-calculus, but freshness contexts’ effects are more complex and harder to control. Extending a typing context may make more terms typable, but will not typically make more terms equal; α-equivalence is independent of typing, but it depends on freshness. This then complicates, for example, normal forms and theories of reduction (lack of α-convertibility may block a reduction; adding a fresh atom may change the normal form of a term) as is explicit in [13], and implicit e.g. in [12, 11].

In this paper, we propose an alternative way to handle these conditions by associating a freshness context once and for all to each unknown. This leads to a new definition of nominal terms: permissive nominal terms. An unknown takes the form XS where S is a single fixed permission sort (Definition 3); thus, we can reason about terms, rather than about terms-in-freshness-context. In a further departure from the usual nominal style, permission sorts are sets of atoms that are both infinite and co-infinite (see Definition 2). Thus, we can always choose a fresh atom for a term, always α-convert, and α-equivalence is inherent rather than depending on a freshness context (Definition 11, Theorem 13, and Corollary 14).

Permissive nominal terms allow to simplify several results and algorithms of the theory of nominal terms, in particular their unification. The solutions of a problem, such as (a b) · XS = XS, is the set of all substitutions mapping the variable X to a term containing no occurrences of a and b. The unifier of such a problem is simply the substitution XS := Y T where T = S \ {a, b}.

Thus, after laying down definitions and basic properties of permissive nominal terms (Sections 2 and 3) and studying their relation to original nominal terms (Section 4), we focus on the unification of permissive nominal terms (Sections 5 and 6).

The rest of the paper considers translations of permissive nominal terms. It is known that languages containing binders can be encoded as datatypes in some programming languages and proof systems using λ-binding and higher-order abstract syntax [25]. We investigate this idea in the general form of a translation of permissive nominal terms to λ-calculus (Section 8). Finally, building up on a recent result of Levy and Villaret, we show (Section 9) that this translation can be applied to unification problems and yields pattern unification problems, as identified by Miller [22, 21], crystallizing the intuition that pattern unification is exactly what is needed to unify encodings of nominal terms.

Levy and Villaret’s main result is that a nominal unification problem is solvable if and only if its translation into higher-order patterns, is solvable [19, Corollary 1 and Theorem 2]. We take this further as follows:

• We investigate how the solutions of a problem, and the solutions of its translation, correspond. We translate terms and substitutions from the ‘nominal’ to the ‘higher-order pattern’ world (Definitions 117 and 129) and show that the translation of a solution is a solution of the translation (Theorem 141).

• We exhibit a general class of higher-order pattern solutions (Definition 149), a notion of permutative renaming of pattern substitutions (Lemma 147), and show that every pattern substitution in that class is the translation of a nominal unification solution, up to permutative renaming (Theorem 155).

• We refine Levy and Villaret’s translation of terms. Their translation is parameterised by a vector of atoms; Levy and Villaret consider a vector containing all the atoms of the problem [19, Definition 2], whereas we identify a smaller vector containing only the capturable atoms (Definition 121). We prove that this is minimal, in the sense that if we use any smaller vector, then injectivity is lost (Theorem 128).

This technical report is formed from two conference papers [6, 5], and a journal paper [7]; the technical report includes all material, with full proofs.

2. Permissive nominal terms

Definition 1

Fix a countably infinite set A of atoms. a, b, c, . . . will range over distinct atoms (we call this the permutative convention). Fix a set of term-formers. f, g, h will range over distinct term-formers.

Definition 2

Call S ⊆A co-infinite when A \ S is infinite. Fix an infinite, co-infinite set comb ⊆A.1 A permissions set has the form (comb∪A1)\A2 for finite sets A1⊆A and A2⊆A.

S, S′, T will range over permissions sets, whereas Permit is the set of all permissions sets.

S, T ∈ Permit implies S ∪T, S ∩T ∈ Permit, and S and A \ S are infinite.

Definition 3

For each permission sort 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 4

Define the domain of a function from atoms to atoms by:

dom(f) = {a | f(a) ≠ a}
Definition 5

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

Write id for the identity permutation such that id(a) = a always. Write (a b) · r for the swapping permutation that swaps a and b in the term r.

Definition 6

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.

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 lam: − app(a, b) can represent ‘xy’ (x applied to y). − app(lam([a]a), b) can represent ‘(λx.x)y’ (identity applied to y). − lam([a]Xcomb) can represent ‘λx.t’ if a ∈ comb, and ‘λx.t, where x ∉ fv(t)’ if a ∉ comb.

See Section 4 for comparison with ‘ordinary’ nominal terms [27].

Definition 7

Define a permutation action by:

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

If S ⊆A, define the pointwise action by: π · S = {π(a) | a ∈S}

Definition 9

Define free atoms fa(r) by:

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

Define fV (r) by:

fV (a) = ∅ fV (f(r1, . . . , rn)) =⋃1≤i≤nfV (ri) fV ([a]r) = fV (r) fV (π·XS) = {XS}
Definition 11

Define α-equivalence =α inductively by:

(=α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

Here, π|S denotes the partial function ‘π restricted to S’; similarly for π′.

Remark 12

r =α s is either true or false. Compare with the corresponding notion for nominal terms, which is subject to a freshness context (Definition 37).

Theorem 13 and Corollary 14 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.

Theorem 13

For any r, there exist infinitely many b such that b ∉ fa(r).

Proof

By induction on r.

• The case a. There are infinitely many atoms not equal to a, as required.

• The case f(r1, . . . , rn). Suppose S, S′, S′′, . . . are the distinct permissions sorts of fV (ri) for 1 ≤i ≤n. By Definition 2, each permission sort differs finitely from, comb. Therefore, we have for every π and S, that π · S differs finitely from combs, too. There exists infinitely many b ∉π ·S ∪π′ ·S′, for every π, S and S′. The result follows from the inductive hypotheses.

• The case [a]r. By inductive hypothesis, infinitely many b ∉ fa(r) exist. There exists infinitely many b ∉ fa(r) \ {a}. The result follows.

• The case π · XS. By Definition 9, fa(π · XS) = π · S. Infinitely many b ∉S exist, by the co-infinite nature of S, therefore infinitely many b ∉π · S exist. The result follows.End of proof

Corollary 14

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 Theorem 13 and (=α[b]).End of proof

Our changes do not affect basic results about nominal terms [27]:

Lemma 15

1. id · r ≡r

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

Proof

By induction on r.

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

• The case [a]r. We have:

id · [a]r ≡ [a](id · r) Definition 7≡ [a]r Inductive hypothesis
π · (π′ · [a]r) ≡ [a](π · (π′ · r)) Definition 7≡ [a]((π◦π′) · r) Indictive hypothesis≡ (π◦π′) · [a]r Definition 7

• The case π′′ · XS. As id ◦π′′ = π′′, we have id · π′′ · XS ≡π′′ · XS. Further:

π · (π′ · (π′′ · XS)) ≡ π · ((π′◦π′′) · XS) Definition 7≡ (π◦(π′◦π′′)) · XSDefinition 7≡ ((π◦π′)◦π′′) · XSFact≡ (π◦π′) · (π′′ · XS) Definition 7End of proof
Lemma 16

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

Proof

By induction on r.

• The case a and f(r1, . . . , rn). These are easy.

• The case [a]r. We have:

π · fa([a]r) = π · (fa(r) \ {a}) Definition 9= π · fa(r) \ {π(a)} Fact= fa(π · r) \ {π(a)} Inductive hypothesis= fa([π(a)](π · r)) Definition 9= fa(π · [a]r) Definition 7

• The case π′ · XS. We have:

π · fa(π′ · XS) = π · (π′ · S) Definition 9= (π◦π′) · S Fact= fa((π◦π′) · XS) Definition 9= fa(π · (π′ · XS)) Definition 7End of proof
Lemma 17

fV (π · r) = fV (r)

Proof

By induction on r.

• The case a. Since fV (a) = ∅= fV (π(a)), the result follows.

• The case f(r1, . . . , rn). We have:

fV (f(r1, . . . , rn)) =⋃1≤i≤n fV (ri) Definition 10=⋃1≤i≤n fV (π · ri) Inductive hypotheses= fV (f(π · r1, . . . , π · rn)) Definition 10= fV (π · f(r1, . . . , rn)) Definition 7

The result follows.

• The case [a]r. We have:

fV ([a]r) = fV (r) Definition 10= fV (π · r) Inductive hypothesis= fV ([π(a)](π · r)) Definition 10= fV (π · [a]r) Definition 7

The result follows.

• The case π′ · XS. By Definition 7, π · (π′ · XS) ≡ (π◦π′) · XS. Then fV (π′ · XS) = {XS} = fV ((π◦π′) · XS), and the result follows.End of proof

Lemma 18

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

Proof

By induction on r =α s.

• The case (=αa). Using (=αa), π(a) =α π(a) always.

• The case (=αf). By hypothesis, π ·ri =α π ·si for 1 ≤i ≤n. Extending with (=αf), we have f(π · r1, . . . , π · rn) =α f(π · s1, . . . , π · sn). This implies π · f(r1, . . . , rn) =α π · f(s1, . . . , sn). The result follows.

• The case (=α[a]). By hypothesis, π · r =α π · s. We use (=α[a]) to conclude [π(a)](π · r) =α [π(a)](π · s). The result follows.

• The case (=α[b]). Suppose (b a) · r =α s with b ∉ fa(r). By Lemma 15 and inductive hypothesis, (π◦(b a)) · r =α s. By Lemma 16, π(b) ∉ fa(π · r). Further, (π◦(b a)) = (π(b) π(a))◦π. Using (=αb), [π(b)](π · r) =α [π(a)](π · s). The result follows.

• The case (=αX). Suppose π′|S = π′′|S so that π′·XS =α π′′·XS. Then (π◦π′)|S = (π◦π′′)|S. By (=αX), (π◦π′) · XS =α (π◦π′′) · XS. The result follows.End of proof

Lemma 19

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

Proof

By induction on r =α s.

• The cases (=αa), (=αf) and (=α[a]). Easy.

• The case (=α[b]). Suppose [a]r =α [b]s by (=α[b]), so b ∉ fa(r). We aim to show fa([a]r) = fa([b]s), or fa(r) \ {a} = fa(s) \ {b}. As b ∉ fa(r), fa(r) \ {a} = (b a)·fa(r)\{b}. By Lemma 16, (b a)·fa(r)\{b} = fa((b a)·r)\{b}. By hypothesis, fa((b a) · r) = fa(s). The result follows.

• The case (=αX). We have fa(π·XS) = π·S and fa(π′·XS) = π′·S. By assumption, π|S = π′|S, therefore π · S = π′ · S. The result follows.End of proof

Lemma 20

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

Proof

By induction on r.

• The case a. As fa(a) = {a}, the result follows by (=αaa).

• The case f(r1, . . . , rn). Suppose π|fa(f(r1,...,rn)) = π′|fa(f(r1,...,rn)). By Definition 9, π|fa(ri) = π′|fa(ri) for 1 ≤i ≤n. By hypothesis, π · ri =α π′ · ri for 1 ≤i ≤n. Using (=αf), the result follows.

• The case [a]r. Suppose π|fa(r) = π′|fa(r) so that π · r =α π′ · r. Then π|fa(r)\{a} = π′|fa(r)\{a}. By Definition 9, π|fa([a]r) = π′|fa([a]r). The result follows.

• The case π′′ · XS. The result follows from (=αX).End of proof

To prove Theorem 24, we introduce the following notion:

Definition 21

Define the size of a term r by:

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

size(r) = size(π · r)

Proof

By induction on r.

• The case a. Since size(π(a)) = 0 = size(a).

• The case f(r1, . . . , rn). We have:

size(f(r1, . . . , rn)) =∑1≤i≤n size(ri) Definition 21=∑1≤i≤n size(π · ri) Inductive hypotheses= size(f(π · r1, . . . , π · rn)) Definition 21= size(π · f(r1, . . . , rn)) Definition 7

• The case [a]r. We have:

size([a]r) = 1 + size(r) Definition 21= 1 + size(π · r) Inductive hypothesis= size([π(a)](π · r)) Definition 21= size(π · [a]r) Definition 7

• The case π′·XS. By Definition 7, π·(π′·XS) ≡ (π◦π′)·XS. Then, size(π′·XS) = 1 = size((π◦π′) · XS). The result follows.End of proof

Lemma 23

For every term r, the set {size(s) | s is a subterm of r} is well-ordered.

Proof

As {size(s) | s is a subterm of r} is a subset of the natural numbers.End of proof

Theorem 24

=α is transitive, reflexive, and symmetric.

Proof

We handle the three claims separately:

• The reflexivity case. We prove r =α r by induction on r.

• The case a. Straightforward, using (=αa).

• The cases f(r1, . . . , rn) and [a]r. These are easy consequences of the inductive hypotheses.

• The case π · XS. Note, π|S = π|S. Using (=αX), π · XS =α π · XS.

• The symmetry case. We prove s =α r by induction on r =α s.

• The cases (=αa) and (=αf). Easy.

• The case (=α[a]). Suppose r =α s so s =α r by hypothesis. Using (=α[a]), [a]s =α [a]r. The result follows.

• The case (=α[b]). Suppose (b a) · r =α s with b ∉ fa(r). By Lemma 16, a ∉ fa((a b) · r). By Lemma 15, and as π = π-1, r =α (a b) · s. By Lemma 19, a ∉ fa(s), and by hypothesis, (a b) · s =α r. Using (=α[b]), [b]s =α [a]r. The result follows.

• The case (=αX). Since equality on partial functions is symmetric.

• The transitivity case. By Lemma 23, we may perform induction on the size of a term. We prove, given r =α s and s =α t, that r =α t by induction on size(r).

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

• The case [a]r. We examine only the most complex case, where all abstracted variables are distinct. Suppose (b a) · r =α s and (c b) · s =α t with b ∉ fa(r) and c ∉ fa(s). By Lemma 18, (c b) · ((b a) · r) =α (c b) · s. By Lemma 22, (c b) · ((b a) ·r) =α t, equivalent to (c a) ·r =α t. By Lemma 19, c ∉ fa((b a) ·r).

By Lemma 16, c ∉(b a) · fa(r). By Lemma 15, c ∉fa(r). Using (=α[b]),

[a]r =α [c]t. The result follows.

• The case π · XS. Since equality on partial functions is transitive.End of proof

3. Substitutions

Definition 25

A substitution θ is a function from unknowns to terms such that fa(θ(XS)) ⊆S always. θ, θ′, θ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 T for all other Y T.2

Definition 26

Define a substitution action on terms by:

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

fa(rθ) ⊆ fa(r).

Proof

By induction on r.

• The case a. Since aθ ≡a.

• The case f(r1, . . . , rn). We have:

fa(f(r1, . . . , rn)θ) ≡ fa(f(r1θ, . . . , rnθ)) Definition 26= fa(r1θ) ∪. . . ∪fa(rnθ) Definition 9⊆ fa(r1) ∪. . . ∪fa(rn) Inductive hypotheses= fa(r1, . . . , rn) Definition 9

The result follows.

• The case [a]r. We have:

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

The result follows.

• The case π·XS. By Definition 9, fa(π·XS) = π·S. By Definition 25, fa(θ(XS)) ⊆ S. Using Lemma 16, fa(π · θ(XS)) ⊆π · S. The result follows.End of proof

Lemma 28

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

Proof

By induction on r.

• The case a. We have:

π · (aθ) ≡ π · a Definition 26≡ π(a) Definition 7≡ π(a)θ Definition 26≡ (π · a)θ Definition 7

The result follows.

• The case f(r1, . . . , rn) and [a]r. These are straightforward. • The case π · XS.

π · ((π′ · XS)θ) ≡ π · (π′ · θ(XS)) Definition 26≡ (π◦π′) · θ(XS) Lemma 15≡ ((π◦π′) · XS)θ Definition 26≡ (π · (π′ · XS))θ Lemma 15

The result follows.End of proof

Lemma 29

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

Proof

By induction on r.

• The case a. Since a[XS:=s] ≡a.

• The case f(r1, . . . , rn). We have:

fV (f(r1, . . . , rn)[XS:=s]) = fV (f(r1[XS:=s], . . . , rn[XS:=s])) Definition 25=⋃1≤i≤n fV (ri[XS:=s]) Definition 10⊆⋃1≤i≤n fV (ri) ∪fV (s) Inductive hypothesis= fV (f(r1, . . . , rn)) ∪fV (s) Definition 10

The result follows.

• The case [a]r. We have:

fV (([a]r)[XS:=s]) = fV ([a](r[XS:=s])) Definition 25= fV (r[XS:=s]) Definition 10⊆ fV (r) ∪fV (s) Inductive hypothesis= fV ([a]r) ∪fV (s) Definition 10

The result follows.

• The case π · Y T. By Definition 26, (π · Y T)[XS:=s] ≡π · Y T. The result follows.

• The case π · XS. By Definition 26, (π · XS)[XS:=s] ≡π · s. By Lemma 17, fV (s) = fV (π · s). The result follows.End of proof

Theorem 30

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

Proof

By induction on r.

• The case a. As fV (a) = ∅.

• The case f(r1, . . . , rn). Suppose for every XS ∈ fV (ri) for 1 ≤i ≤n we have XSθ1 =α XSθ2 and riθ1 =α riθ2 by hypothesis. Using (=αf), f(r1θ1, . . . , rnθ1) =α f(r1θ2, . . . , rnθ2). By Definition 26, f(r1, . . . , rn)θ1 =α f(r1, . . . , rn)θ2. The result follows.

• The case [a]r. Suppose, for every XS ∈ fa(r), we have XSθ1 =α XSθ2. By hypothesis, rθ1 =α rθ2. Using (=α[a]), [a](rθ1) =α [a](rθ2). The result follows.

• The case π · XS. By assumption, XSθ1 =α XSθ2. By Lemma 18, π · (XSθ1) =α π · (XSθ2). By Lemma 28, (π · XS)θ1 =α (π · XS)θ2. The result follows.End of proof

Lemma 31

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

Proof

By induction on the derivation of r =α s.

• The case (=αaa). As aθ ≡a.

• The cases (=αf) and (=α[a]). These are immediate consequences of the inductive hypotheses.

• The case (=α[b]). Suppose (b a) · r =α s with b ∉ fa(r). Then ((b a) · r)θ =α sθ by assumption. By Lemma 28, (b a) · rθ =α sθ. By Theorem 27, b ∉ fa(rθ). Using (=α[b]), [a](rθ) =α [b](sθ). By Definition 25, [a](rθ) ≡ ([a]r)θ. The result follows.

• The case (=αX). Suppose π · XS =α π′ · XS using (=αX). Then π|S = π′|S and as fa(θ(XS)) ⊆S by assumption. The result follows.End of proof

Definition 32

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

Theorem 33

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

Proof

By induction on r.

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

• The case [a]r. We have:

(([a]r)θ)θ′≡ [a]((rθ)θ′) Definition 26≡ [a](r(θ◦θ′)) Inductive hypothesis≡ ([a]r)(θ◦θ′) Definition 26

The result follows.

• The case π · XS

(π · XS)(θ◦θ′) ≡ π · (θ◦θ′)(XS) Definition 26≡ π · (θ(XS)θ′) Definition 32≡ (π · θ(XS))θ′Lemma 28≡ ((π · XS)θ)θ′Lemma 28

The result follows.End of proof

4. Relation to nominal terms

Nominal terms are described fully elsewhere [27]. We inject ‘nominal’ into ‘permissive’. Main results are Theorems 41, 42, and 49.

Fix a countably infinite set of nominal atoms, ˙A. ˙a, ˙b, ˙c, . . . will range over distinct nominal atoms. Fix a bijection ι between ˙A and comb (Definition 2). 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 dom( ˙π) 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 34

Define nominal terms with the following grammar:

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

Define a permutation action on nominal terms with the following rules:

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

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

(#ḃ)∆⊢˙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 1: 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 2: Derivable equality on nominal terms
Definition 36

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

Definition 37

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

Definition 38

Define a mapping ⟦ ˙π⟧ from nominal permutations to permissive nominal permutations by ⟦ ˙π⟧ι(˙a) = ι(π(˙a)) and ⟦ ˙π⟧(c) = c for all other c. Define an interpretation ⟦ ˙r⟧∆ by:

⟦˙a⟧∆≡ι(˙a) ⟦f( ˙r1, . . . , ˙rn)⟧∆≡f(⟦ ˙r1⟧∆, . . . , ⟦ ˙rn⟧∆) ⟦[˙a] ˙r⟧∆≡[ι(˙a)]⟦ ˙r⟧∆⟦ ˙π · ˙X⟧∆≡⟦ ˙π⟧ · XSwhere S = comb \ {ι(˙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 39

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

Proof

By induction on ˙r.

• The case ˙a. Suppose ˙π· ˙a = ˙b and ⟦ ˙π⟧(ι(˙a)) = ι(˙b). Then ι( ˙π· ˙a) = ι(˙b) = ⟦ ˙π⟧(ι(˙a)) and ⟦ ˙π⟧(ι(˙a)) = ⟦ ˙π⟧ · ⟦˙a⟧∆. The result follows.

• The case ˙π′ · ˙X.

⟦ ˙π · ˙π′ · ˙X⟧∆≡ ⟦( ˙π◦˙π′) · ˙X⟧∆Definition 35≡ ⟦ ˙π◦˙π′⟧ · XSDefinition 38, S = comb \ {ι(˙a) | ˙a# ˙X ∈∆}≡ ⟦ ˙π⟧ · (⟦ ˙π′⟧ · XS) Definition 35≡ ⟦ ˙π⟧ · (⟦ ˙π′ · ˙X⟧∆) Lemma 15, Definition 38

• The case [˙a] ˙r. We have:

⟦ ˙π · [˙a] ˙r⟧∆≡ ⟦[ ˙π(˙a)] ˙π · ˙r⟧∆Definition 35≡ [ι( ˙π · ˙a)]⟦ ˙π · ˙r⟧∆Definition 38≡ [ι( ˙π · ˙a)](⟦ ˙π⟧ · ⟦ ˙r⟧∆) Inductive hypothesis≡ [⟦ ˙π⟧ · ι(˙a)](⟦ ˙π⟧ · ⟦ ˙r⟧∆) Definition 38≡ ⟦ ˙π⟧ · ⟦[˙a] ˙r⟧∆Definition 7

The result follows.

• The case f( ˙r1, . . . , ˙rn). This is routine.End of proof

Lemma 40

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

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

• The case [˙a] ˙r. There are two cases to consider:

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

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

• The case ˙π · ˙X. Suppose ι(˙a) ∉ fa(⟦ ˙π · ˙X⟧∆). Then ι(˙a) ∉⟦ ˙π⟧ · S, where S = comb \ {ι(˙a) | ˙a# ˙X ∈∆}. But ⟦ ˙π⟧ · comb \ {ι(˙a) | ˙a# ˙X ∈∆} equivalent to ⟦ ˙π⟧ · comb \ ⟦ ˙π⟧ · {ι(˙a) | ˙a# ˙X ∈∆}. Then ⟦ ˙π⟧ · {ι(˙a) | ˙a# ˙X ∈∆} = {⟦ ˙π⟧ · ι(˙a) | ˙a# ˙X ∈∆}. By Definition 38, and the fact permutations are bijective, {⟦ ˙π⟧ · ι(˙a) | a#X ∈∆} = {ι( ˙π-1 · ˙a) | ˙π-1 · ˙a#X ∈∆}. Using (#Ẋ ), ∆⊢˙a# ˙X. The result follows.

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

• The cases (# ḃ) and (#f). Routine.

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

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

• The case (# Ẋ). Suppose ˙π-1(˙a)# ˙X ∈ ∆, and ∆ ⊢˙a# ˙π · ˙X using (#Ẋ ).

Then ⟦ ˙π · ˙X⟧∆= ⟦ ˙π⟧ · XS where S = comb \ {ι(˙a) | ˙a# ˙X ∈∆}. Further,

fa(⟦ ˙π⟧ · XS) = ⟦ ˙π⟧ · S. The result follows by Definition 38.End of proof

Theorem 41

⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ implies ∆⊢˙r = ˙s.

Proof

By induction on the derivation of ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆.

• The case ˙a. We have ⟦˙a⟧∆= ι(˙a). Using (=αaa), s ≡˙a and ⟦˙a⟧∆=α ⟦˙a⟧∆. Using (=ȧ), ∆⊢˙a = ˙a. The result follows.

• The case f( ˙r1, . . . , ˙rn). Suppose ⟦f( ˙r1, . . . , ˙rn)⟧∆=α ⟦f( ˙s1, . . . , ˙sn)⟧∆. Then ⟦ ˙ri⟧∆=α ⟦ ˙si⟧∆ for 1 ≤i ≤n. By hypothesis, ∆ ⊢˙ri = ˙si for 1 ≤i ≤n. Using (=αf), f(⟦ ˙r1⟧∆, . . . , ⟦ ˙rn⟧∆) =α f(⟦ ˙s1⟧∆, . . . , ⟦ ˙sn⟧∆). Then f(⟦ ˙r1⟧∆, . . . , ⟦ ˙rn⟧∆) = ⟦f( ˙r1, . . . , ˙rn)⟧∆. The result follows.

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

• The case (=α[b]). Suppose (ι(˙b) ι(˙a)) · ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆ and ι(˙b) ∉ fa(⟦ ˙r⟧∆). By Lemmas 39 and 40, ⟦(˙b ˙a) · ˙r⟧∆=α ⟦ ˙s⟧∆ and ∆ ⊢˙b# ˙r. By hypothesis, ∆ ⊢ (˙b ˙a) · ˙r = ˙s. Using (=[ḃ ]), [˙a] ˙r = [˙b] ˙s. The result follows.

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

Theorem 42

If ∆⊢˙r = ˙s then ⟦ ˙r⟧∆=α ⟦ ˙s⟧∆.

Proof

By induction on the derivation of ∆ ⊢˙r = ˙s.

• The case (=ȧ). Straightforward.

• The case (=f). Routine, by the inductive hypotheses.

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

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

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

Definition 43

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.

Definition 44

Define a substitution action on nominal terms by the following rules:

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

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 [27, Definition 3.1]. We extend our interpretation to solutions by:

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

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

Proof

By induction on ˙r.

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

• The case [˙a] ˙r. We have:

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

The result follows.

• The case ˙π · ˙X. We have:

⟦( ˙π · ˙X) ˙θ⟧∆≡ ⟦ ˙π · ˙θ( ˙X)⟧∆Definition 44≡ ⟦ ˙π⟧ · ⟦ ˙θ( ˙X)⟧∆Definition 38≡ ⟦ ˙π⟧ · ⟦ ˙θ⟧(⟦ ˙X⟧∆)

The result follows.End of proof

Definition 47

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

Lemma 48

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

Proof

We handle the two implications separately.

• The case a ∉ fa(r) implies (b a) · r =α r. We proceed by induction on r.

• The case c. Straightforward.

• The case f(r1, . . . , rn). Easy, by the inductive hypotheses.

• The cases [a]r and [b]r. We handle only the [a]r case, as the other is similar. We show (b a) · [a]r =α [a]r where b ∉ fa([a]r), hence b ∉ fa(r) and a ∉ fa(r). By Definition 7, (b a) · [a]r =α [b](b a) · r. By the rules in Definition 11, we must show (a b) · ((b a) · r) =α r where a ∉ fa((b a) · r). By Lemma 16, this is equivalent to b ∉ fa(r), which we have by assumption. By Lemma 15, (a b) · ((b a) · r) =α ((a b)◦(b a)) · r, and as π = π-1, we have r =α r. The result follows from Theorem 24.

• 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 7, (b a) · [c]r ≡ [c](b a) · r. Using (=α[a]) and the inductive hypothesis, (b a) · r =α r.

• The case π · XS. Suppose b ∉ fa(π · XS), a ∉ fa(π · XS) and a, b ∉π · S. By Definition 7, (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, and the result follows.

• The case (b a) · r =α r implies a ∉ fa(r). We proceed by induction on r.

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

• The case f(r1, . . . , rn). By hypotheses, (b a)·r1 =α r1. . . (b a)·rn =α rn implies a ∉ fa(r1) . . . a ∉ fa(rn). As fa(f(r1, . . . , rn)) = fa(r1) ∪. . . ∪ fa(rn), the result follows.

• The cases [a]r and [b]r. We handle only the [a]r case, as the other is similar. Suppose (b a) · [a]r =α [a]r. By Definition 7, (b a) · [a]r ≡ [b](b a) · r. By the rules in Definition 11, [b](b a) · r =α [a]r whenever (a b) · ((b a) · r) =α r with a ∉ fa((b a) · r). By Definition 7, and as π = π-1, (a b) · ((b a) · r) ≡r. By assumption, b ∉ fa(r). By Lemma 16, a ∉ fa((b a) · r). The result follows.

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

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

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

Theorem 49

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

Proof

We handle the two implications separately:

• The case (∆, ˙θ) solves ˙Pr implies ⟦(∆, ˙θ)⟧ solves ⟦ ˙Pr⟧∆. Suppose ∆ ⊢˙r ˙θ = ˙sθ ˙.

By Lemma 46 and Theorem 42, ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α ⟦ ˙s⟧∆⟦(∆, ˙θ)⟧. Suppose ∆⊢a# ˙r ˙θ. By Lemma 40, ι(˙a) ∉fa(⟦ ˙r ˙θ⟧∆). By Lemma 46, ι(˙a) ∉ fa(⟦ ˙r⟧∆⟦(∆, ˙θ)⟧). By Lemma 48, (b ι(˙a)) · ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧, where b is

fresh (see Definition 47). By Lemma 28, ((b ι(˙a)) · ⟦ ˙r⟧∆)⟦(∆, ˙θ)⟧ =α ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧. The result follows.

• The case ⟦(∆, ˙θ)⟧ solves ⟦Pr ˙⟧∆ implies (∆, ˙θ) solves ˙Pr. Suppose ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α ⟦ ˙s⟧∆⟦(∆, ˙θ)⟧. By Theorem 41, ∆⊢rθ = sθ.

Suppose ((b ι(˙a))·⟦ ˙r⟧∆)⟦(∆, ˙θ)⟧ =α ⟦ ˙r⟧∆⟦(∆, ˙θ)⟧. By Lemma 28, (b ι(˙a))·⟦ ˙r⟧∆⟦(∆, ˙θ)⟧ =α⟦ ˙r⟧∆⟦(∆, ˙θ)⟧. By Lemma 48, ι(˙a) ∉fa(⟦ ˙r⟧∆⟦(∆, ˙θ)⟧). By Lemma 46, ι(˙a) ∉

fa(⟦ ˙r ˙θ⟧∆). By Lemma 40, ∆⊢a# ˙r ˙θ. The result follows.End of proof

5. Support inclusion problems

Nominal unification has ‘freshness problems’; the algorithm of [27] solves these concurrently with equality problems. We prefer to factor the algorithm differently, so that problems to do with free atoms are solved separately from problems to do with equalities. The linkage is isolated in rule (I3) (Definition 75). Permissions sets differ finitely from comb or ∅, so although we are manipulating infinite sets, we may represent them as finite data structures in any implementation.

5.1. Simplification reduction and normal forms

Definition 50

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

Definition 51

Define a simplification rewrite relation by:

(⊑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)
Theorem 52

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. As fa(aθ) = fa(a) = {a}.

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

⋃1≤i≤n fa(ri), 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}. 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 16, π · fa(t) ⊆T. By Lemmas 15 and 16, (π-1◦π) · fa(t) ⊆π-1 · T. As π-1◦π = id, we have fa(XS[XS:=t]) ⊆π-1 · T. The result follows.

Alternatively, suppose fa(t) ⊈S. Then fa((π · XS)[XS:=t]) = fa(π · XS). By Lemma 16, π · fa(XS) ⊆T. By Lemmas 15 and 16, fa(XS[XS:=t]) ⊆π-1 · T. The

result follows. The reverse direction is similar.

Claim 5: If S ⊆π-1·T then fa(π·XSθ) ⊆T always. Note, S ⊆π-1·T if and only if π·S ⊆ T and fa(π·XS) = π·S. By Lemmas 28 and 16, fa(π·XSθ) = π·fa(θ(XS)) ⊆π·S. Then, fa(π · XSθ) ⊆T. The result follows.

We proceed by case analysis on Inc =⇒ Inc′ (Definition 51):

• The case (⊑a). Suppose a ∈T. If θ ∈ Sol(a ⊑T, Inc′) then θ ∈ Sol(Inc′) and the result follows. Otherwise, suppose θ ∈ Sol(Inc′). Using Claim 1, fa(aθ) ⊆T. 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 direction 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 direction is similar.

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

Definition 53

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. Order tuples lexicographically.

Theorem 54

Support inclusion problem simplication is strongly normalizing.

Proof

By case analysis on r ⊑T, Inc′, showing that each rule reduces the measure (Definition 53).

• The case a ⊑T, Inc′. Suppose a ∈T, size(a ⊑T, Inc′) = (T, A, P, S), and a ⊑ T, Inc′ =⇒ Inc′ using (⊑a). Then size(Inc′) = (T, A, P, S − 1).

• 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′ using (⊑[]). 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′ using (⊑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).End of proof

Theorem 55

Support inclusion problem simplification is strongly confluent.

As an immediate corollary, support inclusion simplification is confluent.

Proof

We prove the result by induction on the cardinality of Inc.

• The case Inc = ∅. As no rewrites are applicable.

• The case Inc = r ⊑T, Inc′. Note for each r ⊑T only one simplification rule may be applied. The result then follows from the inductive hypothesis.

The corollary follows, as all strongly confluent rewrite relations are confluent (see [1] for details).End of proof

We conclude with a few useful observations:

Definition 56

Write nf (Inc) for the unique =⇒-normal form of Inc, guaranteed to exist by Theorems 54 and 55.

Definition 57

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

Lemma 58

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

Proof

By inspection.End of proof

5.2. Building solutions

Our main results are Theorems 62 and 70.

Definition 59

Define fV (Inc) by fV (Inc) = ⋃{fV (r) | ∃T.r ⊑T ∈ Inc}. (fV (Inc) is ‘the unknowns appearing in terms appearing in Inc’.)

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

Definition 60

Suppose Inc is consistent. For every XS ∈V make a fixed but arbitrary choice of X′S′ such that X′S′∉V and S′ = ⋂{T | XS ⊑T ∈ nf (Inc)}.

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

It is easy to verify that fa(ρV Inc(XS)) ⊆S always.

Lemma 61

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 52 Sol(Inc) = Sol(nf (Inc)), and we use the previous paragraph.End of proof

Theorem 62

Inc is consistent (Definition 57) if and only if Inc is solvable (Definition 50).

Proof

By Theorem 52 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 61.End of proof

Definition 63

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 63 is well-defined:

Lemma 64

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 63, (θ−ρ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 60, ρ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 65

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

Proof

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

Lemma 66

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 60, 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 67

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

Proof

By case analysis on the rules defining =⇒ (Definition 51).

• The case (⊑a). Suppose a ∈T and a ⊑T, Inc′ =⇒ Inc′ using (⊑a). By Definition 59, fV (a ⊑T, Inc′) = fV (Inc′). The result follows.

• The case (⊑f). Suppose f(r1, . . . , rn) ⊑T, Inc′ =⇒r1 ⊑T, . . . , rn ⊑T, Inc′ using (⊑f). By Definition 59, fV (f(r1, . . . , rn) ⊑T, Inc′) = fV (r1 ⊑T, . . . , rn ⊑T, Inc′). The result follows.

• The case (⊑[]). Suppose [a]r ⊑T, Inc′ =⇒r ⊑T ∪{a}, Inc′ using (⊑[]). By Definition 59, fV ([a]r) = fV (r). By Definition 10, fV ([a]r ⊑T, Inc′) = fV (r ⊑ T ∪{a}, Inc′). The result follows.

• The case (⊑X). Suppose S ⊈π-1 · T, π ≠ id and π · XS ⊑T, Inc′ =⇒XS ⊑ π-1 · T, Inc′ using (⊑X). By Definition 10, fV (π · XS) = XS = fV (XS). By Definition 59, fV (π · XS ⊑T, Inc′) = fV (XS ⊑π-1 · T, Inc′). The result follows.

• The case (⊑X′). Suppose S ⊆π-1 · T and π · XS, Inc′ =⇒ Inc′ using (⊑X′). By Definition 59, fV (Inc′) ⊆ fV (π · XS, Inc′). The result follows.End of proof

Corollary 68

fV (nf (Inc)) ⊆ fV (Inc)

Proof

By Lemma 67.End of proof

Lemma 69

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

Proof

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

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

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

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

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

Theorem 70

If θ ∈ 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 15.End of proof

6. Permissive nominal unification problems

6.1. Problems, solutions, the unification algorithm

Definition 71

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}
Definition 72

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

A solution to Pr ‘makes the equalities valid’, as for first- and higher-order unification. This simplifies the nominal unification notion of solution (Definition 45 or [27, Definition 3.1]) based on ‘a substitution + a freshness context’. We can do this, because in permissive nominal terms, freshness information is fixed. Lemma 73 will be useful:

Lemma 73

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

(?=?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 3: Simplification rules for problems
Proof

Suppose θ◦θ′ ∈ Sol(Pr) and r ?=? s ∈Pr. We have:

(rθ)θ′≡ r(θ◦θ′) Theorem 33=αs(θ◦θ′) Assumption≡ (sθ)θ′Theorem 33

By Definition 72, θ′ ∈ Sol(Prθ).

For the reverse implication, suppose θ′ ∈ Sol(Prθ) and rθ ?=? sθ ∈ Sol(Prθ). Then:

r(θ◦θ′) ≡ (rθ)θ′Theorem 33=α(sθ)θ′Assumption≡ s(θ◦θ′) Theorem 33

By Definition 72, θ◦θ′ ∈ Sol(Pr). The result follows.End of proof

Definition 74

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

Definition 75

Define a simplification rewrite relation V; Pr =⇒V′; Pr′ on unification problems by the rules in Figure 3.3 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 60.

Lemma 76

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

Proof

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

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

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

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

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

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

• Suppose ([a]r)θ =α ([b]s)θ. By Definition 26, [a](rθ) =α [b](sθ). By the rules in Definition 11, (b a)·(rθ) =α sθ. By Lemma 28 and Theorem 24, ((b a)·r)θ =α sθ. The result follows.

• Suppose ((b a) · r)θ =α sθ. By Lemma 28 and Theorem 24, (b a) · (rθ) =α sθ. By Theorem 27, b ∉ fa(rθ). Using (=α[b]), [a](rθ) =α [b](sθ). By Definition 26 [a](rθ) =α [b](sθ). The result follows.End of proof

Definition 77

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

Definition 78

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

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

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

1. Rewrite fV (Pr); Pr using the rules of Definition 75 as much as possible.

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.

Lemma 80

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

Proof

By Definition 72 it suffices to show rθ =α sθ if and only if rθ′ =α sθ′, for every r ?=? s ∈Pr. This is easy using Theorem 30 and the fact by construction (Definition 77) that fV (r) ⊆ fV (Pr) and fV (s) ⊆ fV (Pr).End of proof

Definition 81

Write θ−XS for the substitution such that:

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

Theorem 82

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

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

We reason as follows:

XS([XS:=s]◦(θ−XS)) ≡ s(θ−XS) Definition 26≡ sθ XS ∉fV (s), Theorem 30=αXSθ Assumption
Y T ([XS:=s]◦(θ−XS)) ≡ Y T (θ−XS) Definition 32≡ Y T θ Definition 81End of proof

6.2. Simplification rewrites calculate principal solutions

Definition 83

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

Definition 84

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 88 — the unification algorithm from Definition 79 calculates a solution — and 93 — the solution it calculates, is principal.

Lemma 85

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

Proof

As the empty set cannot be simplified, it must be that Pr = r ?=? s, Pr′. Therefore, we perform case analysis on the simplification of r ?=? s.

• The cases (?=?a), (?=?f) and (=αX). 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′ using (?=?[a]). By Definitions 10 and 77, fV (r ?=? s, Pr′) ⊆V. 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′ using (?=?[a]).

By Definitions 10 and 77 and Lemma 17, fV ((b a) · r) ⊆V. The result follows.End of proof

Lemma 86

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

Proof

There are two cases to consider:

• The cases (I1) and (I2). We handle the first case, the second is similar. Suppose

fV (π · XS ?=? s, Pr′) ⊆V and V; π · XS ?=? s, Pr′ [XS:=π-1·s]=⇒ V′; Pr′[XS:=π-1 · s] using (I1). By Definition 77 and Lemma 29, fV (Pr′[XS:=π-1 · s]) ⊆ fV (Pr′) ∪ fV (π-1 · s). The result follows.

• The case (I3). By Lemma 67.End of proof

Lemma 87

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

Proof

There are multiple cases to consider:

• The case XS with XS ∈V. We have:

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

• The case Y T with Y T ∈V. We have:

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

• 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 78:

Theorem 88

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′; ∅. By Lemma 85, fV (Pr′′) ⊆V. By inductive hypothesis, θ ∈ Sol(Pr′′). By Lemma 76, θ ∈ Sol(Pr). The result follows.

• The case of (I1) or (I2). Suppose V; Prχ=⇒V; Prχθ′=⇒∗V′; ∅. By Lemma 86, fV (Prχ) ⊆V. By inductive hypothesis, θ′|V ∈ Sol(Prχ). By Lemma 87, (χ◦θ′)|V = χ◦(θ′|V). By Lemma 73, (χ◦θ′)|V ∈ Sol(Pr). The result follows.

• The case of (I3). Suppose V; Prρ=⇒V′; Prρθ′=⇒∗V′′; ∅. By Lemma 86, fV (Prρ) ⊆V′. By inductive hypothesis, θ′|V′ ∈ Sol(Prρ). By Lemma 73, ρ◦(θ′|V′) ∈ Sol(Pr). By Lemma 87, ρ◦(θ′|V′) = (ρ◦θ′)|V′. By Lemma 80, (ρ◦θ′)|V ∈ Sol(Pr). The result follows.End of proof

We need some lemmas for Theorem 93:

Lemma 89

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

Proof

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

XS(θ◦θ1) ≡ (XSθ)θ1Theorem 33=α(XSθ)(θ2◦θ′) Theorem 30≡ XS((θ◦θ2)◦θ′) Theorem 33

The result follows.End of proof

Lemma 90

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

Proof

By a routine calculation using Definition 83 and using Theorem 24.End of proof

Lemma 91

If θ ∈ Sol(Pr) (Definition 72) then θ ∈ Sol(Pr⊑) (Definition 50).

Proof

By a routine calculation, using Definitions 72 and 74, and Lemma 19.End of proof

Lemma 92

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

Proof

There are multiple cases to consider:

• 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 93

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

Proof

By Theorem 88, θ|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 83, id|V ≤θ′|V.

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

• 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 76, θ|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 Theorem 88, θ′′|V ∈Sol(Pr′′χ). By Lemma 86, fV (Pr′′χ) ⊆V. By Theorem 82 and Lemma 80, χ◦(θ′|V −XS) ∈Sol(Pr). By Lemma 92, (θ|V − XS) = (θ −XS)|V. By Lemma 73, (θ −XS)|V ∈Sol(Pr′′χ).

By inductive hypothesis, θ′′|V ≤ (θ′−XS)|V. By Lemma 89, χ◦(θ′′|V) ≤ χ◦(θ′−XS)|V. By Lemma 87, χ◦(θ′′|V) = (χ◦θ′′)|V. By Lemma 92, (θ′−XS)|V = θ′|V−XS. By Theorem 82 and Lemma 90, (χ◦θ′′)|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 88, θ′′|V′′ ∈ Sol(Prρ). It is a fact that V′′ = V ∪V′V Pr⊑, so fV (Prρ) ⊆V′′. By Lemma 91, θ′|V ∈ Sol(Pr⊑). By Theorem 70 and Lemma 80, ρ◦(θ′|V−ρ) ∈ Sol(Pr). By Lemma 73, θ′|V−ρ ∈ Sol(Prρ). By inductive hypothesis, θ′′|V ≤θ′|V−ρ. By Lemma 89, ρ◦θ′′|V ≤ρ◦(θ′|V−ρ). It is a fact that ρ◦(θ′′|V) = (ρ◦θ′′)|V. By Theorem 70 and Lemma 90, (ρ◦θ′′)|V ≤θ′|V as required.End of proof

Theorem 94

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

Proof

If the algorithm succeeds we use Theorem 93. 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). It is clear that no solution to Pr exists.End of proof

7. The λ-calculus

Definition 95

Let X, Y, Z, . . . range over distinct unknowns.

Define λ-terms by:

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

Here f ranges over term-formers, and a ranges over atoms (see Definition 1). g, h, k will range over λ-terms.

Definition 96

Define a permutation action by:

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

Write π◦π′ for the composition of permutations π and π′, and id for the identity permutation on λ-terms.

Definition 97

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 98

Let α-equivalence =α be the least relation on λ-terms such that:

(λ=α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′

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

Lemma 99 to Theorem 107 mirror similar results for permissive nominal terms.

Lemma 99

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

Proof

By induction on g.

• The cases a, f and X. Routine.

• The case λa.g. We wish to show λπ(a).π · g =α λπ′(a).π′ · g. There are two cases to consider:

• The case π(a) = π′(a). By inductive hypothesis.

• The case π(a) ≠ π′(a). We wish to show λπ(a).g =α λπ′(a).h. Using (λ=αλa), this is equivalent to showing (π′(a) π(a)) · g =α h with π′(a) ∉ fa(g). If π′(a) ∉ fa(g) then π(a) ∉ fa(g), which holds by assumption. Therefore there is nothing to prove.

• The case g′g. Routine.End of proof

Lemma 100

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

Proof

By induction on g.

• The case a. We have:

π · (π′ · a) ≡ π · π′(a) Definition 96≡ π(π′(a)) Definition 96≡ (π◦π′) · a Definition 96

• The cases X, f and g′g. These are routine.

• The case λa.g. We have:

π · (π′ · λa.g) ≡ π · λπ′(a).(π′ · g) Definition 96≡ λπ(π′(a)).(π · (π′ · g)) Definition 96≡ λπ(π′(a)).((π◦π′) · g) Inductive hypothesis≡ (π◦π′) · λa.g Definition 96

The result follows.End of proof

Lemma 101

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

Proof

By induction on g.

• The case a. We have:

π · fa(a) = π · {a} Definition 97= {π(a)} Definition 8= fa(π(a)) Definition 97= fa(π · a) Definition 96

• The case X and f. These are straightforward.

• The case g′g. We have:

π · fa(g′g) = π · (fa(g′) ∪fa(g)) Definition 97= π · fa(g′) ∪π · fa(g) Fact= fa(π · g′) ∪fa(π · g) Inductive hypothesis= fa((π · g′)(π · g)) Definition 97= fa(π · g′g) Definition 96

The result follows.

• The case λa.g. We have:

π · fa(λa.g) = π · (fa(g) \ {a}) Definition 97= π · fa(g) \ π · {a} Fact= fa(π · g) \ {π(a)} Inductive hypothesis, Definition 8= fa(λπ(a).(π · g)) Definition 97= fa(π · λa.g) Definition 97

The result follows.End of proof

Lemma 102

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

Proof

By induction on the derivation of g =α h.

• The case (λ=αa). Using (λ=αa), π(a) =α π(a).

• The case (λ=αX) and (λ=αf). Routine.

• The case (λ=αp). By inductive hypothesis, π · g =α π · g′ and π · h =α π · h′. Using (λ=αp), (π · g)(π · h) =α (π · g′)(π · h′). By Definition 96, (π · g)(π · h) ≡π · gh. The result follows.

• The case (λ=αλaa). By inductive hypothesis, π · g =α π · h. Using (λ=αλaa), λπ(a).(π · g) =α λπ(a).(π · h). By Definition 96, λπ(a).π · g ≡π · λa.g. The result follows.

• The case (λ=αλab). By inductive hypothesis, π·((b a)·g) =α π·h. By Lemma 100, π·((b a)·g) ≡ (π◦(b a))·g. It is a fact that π◦(b a) = (π(b) π(a))◦π. By Lemma 100, (π(b) π(a)) · (π · g) =α π · h. By Lemma 101, π(b) ∉ fa(π · g). Using (λ=αλab), λπ(a).(π · g) =α λπ(b).(π · h). The result follows by Definition 96.End of proof

Lemma 103

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

Proof

By induction on the derivation of g =α h.

• The cases (λ=αa), (λ=αX) and (λ=αf). Straightforward.

• The case (λ=αp). By inductive hypothesis, fa(g′) = fa(g) and fa(h′) = fa(h). As fa(g′g) = fa(g′) ∪ fa(g), the result follows.

• The case (λ=αλaa). By inductive hypothesis, fa(g) = fa(h), hence fa(g) \ {a} = fa(h) \ {a}. The result follows.

• The case (λ=αλab). Suppose λa.g =α λb.h using (λ=αλab), with b ∉ fa(g). We aim to show fa(λa.g) = fa(λb.h), that is, fa(g) \ {a} = fa(h) \ {b}. As b ∉ fa(g), fa(g) \{a} = (b a) · fa(g) \{b}. By Lemma 101, (b a) · fa(g) \{b} = fa((b a) ·g) \{b}. By inductive hypothesis, fa((b a) · g) = fa(s). The result follows.End of proof

Definition 104

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 105

For every lambda-term g, the set {size(h) | h is a subterm of g} is well-ordered.

Proof

Since the set {size(h) | h is a subterm of g} forms a subset of the natural numbers.End of proof

Lemma 106

size(g) = size(π · g)

Proof

By induction on g.

• The cases a, X and f. Straightforward.

• The case g′g. We have:

size(g′g) = size(g′) + size(g) Definition 104= size(π · g′) + size(π · g) Inductive hypothesis= size((π · g′)(π · g)) Definition 104= size(π · g′g) Definition 96

The result follows.

• The case λa.g. We have:

size(λa.g) = 1 + size(g) Definition 104= 1 + size(π · g) Inductive hypothesis= size(λπ(a).(π · g)) Definition 104= size(π · λa.g) Definition 96

The result follows.End of proof

Theorem 107

=α is transitive, reflexive, and symmetric.

Proof

We handle the three cases separately.

• The reflexivity case, g =α g. We proceed by induction on g.

• The case a, X and f. Routine.

• The case g′g. By hypothesis, g′ =α g′ and g =α g. Using (λ=αp), g′g =α g′g. The result follows.

• The case λa.g. By hypothesis, g =α g. Using (λ=αλaa), λa.g =α λa.g. The result follows.

• The symmetry case, g =α h implies h =α g. We proceed by induction on the derivation of g =α h.

• The cases (λ=αa), (λ=αX) and (λ=αf). Routine.

• The case (λ=αp). By inductive hypotheses, g′ =α g and h′ =α h. Using (λ=αp), g′h′ =α gh. The result follows.

• The case (λ=αλaa). By inductive hypothesis, h =α g. Using (λ=αλaa), λa.h =α λa.g. The result follows.

• The case (λ=αλab). Suppose (b a) · g =α h with b ∉ fa(g). By inductive hypothesis, h =α (b a)·h. By Lemma 103, b ∉ fa(h). By Lemma 102, (b a)·h =α (b a)·((b a)·g). By Lemma 100, (b a)·h =α ((b a)◦(b a))·g, therefore (b a)·h =α g.

By Lemma 101, a ∉fa((b a) · h). Using (λ=αλ[b]), λb.h =α λa.g. The result

follows.

• The transitivity case, g =α h and h =α i imply g =α i. Following Lemma 105, we proceed by induction on size(g).

• The cases a, X and f. Straightforward.

• The case g′g. By the inductive hypotheses.

• The case λa.g. There are multiple cases to consider. We consider the most difficult, the case where all abstractions are named apart. Suppose λa.g =α λb.h and λb.h =α λc.k. We aim to show λa.g =α λc.k.

Suppose (b a) · g =α h and (c b) · h =α k with b ∉fa(g) and c ∉fa(h). By Lemma 100, (c b) · ((b a) · g) =α (c b) · h. By Lemma 106, (c b) · ((b a) · g) =α k, equivalent to (c a) · g =α k. By Lemma 103, c ∉fa((b a) · g). By Lemma 102,

c ∉ fa(g). Using (λ=αλab), the result follows.End of proof

Definition 108

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

Definition 109

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

Definition 110

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(gσ))(λa.g)σ ≡λb.((b a) · gσ) (a ∈fa(gσ), b fresh)

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

Lemma 111

π · (gσ) =α (π · g)σ

Proof

By induction on size(g).

• The cases a, f and X. Straightforward.

• The case g′g. We have:

(π · g′g)σ ≡ ((π · g′)(π · g))σ Definition 96≡ ((π · g′)σ)((π · g)σ) Definition 110≡ (π · g′σ)(π · (gσ)) Inductive hypothesis≡ π · (g′σ)(gσ) Definition 96≡ π · ((g′g)σ) Definition 110

The result follows.

• The case λa.g with a, π(a) ∉ fa(rng(σ)). We have:

(π · λa.g)σ ≡ (λπ(a).(π · g))σ Definition 96≡ λπ(a).((π · g)σ) Definition 110≡ λπ(a).(π · (gσ)) Inductive hypothesis≡ π · λa.(gσ) Definition 96≡ π · ((λa.g)σ) Definition 110

The result follows.

• The case λa.g with a ∈ fa(rng(σ)) or π(a) ∈ fa(rng(σ)). We have:

(π · λa.g)σ =α(π · λb.((b a) · g))σ b fresh≡ (λπ(b).(π · ((b a) · g)))σ Definition 96≡ (λπ(b).((π◦(b a)) · g))σ Lemma 100≡ λπ(b).((π◦(b a)) · g)σ) Definition 110=αλπ(b).((π◦(b a)) · gσ) Lemma 106, Inductive hypothesis≡ λπ(b).(π · ((b a) · (gσ))) Lemma 100≡ π · λb.((b a) · (gσ)) Definition 96≡ π · λb.(((b a) · g)σ) Lemma 106, Inductive hypothesis≡ π · ((λb.(b a) · g)σ) Definition 110=απ · (λa.g)σ b fresh

The result follows.End of proof

Definition 112 is an analogue of the substitution action on permissive nominal terms from Definition 32:

Definition 112

Define composition σ◦σ′ by: (σ◦σ′)(X) ≡ (σ(X))σ′.

Lemma 113

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

Proof

By induction on size(g).

• The case a. Since aσ ≡a.

• The case X. By Definition 112.

• The case f. Since π · f ≡ f and fσ ≡ f.

• The case g′g. We have:

(g′g)σσ′≡ (g′σσ′)(gσσ′) Definition 110≡ (g′(σ◦σ′))(g(σ◦σ′)) Inductive hypothesis≡ (g′g)(σ◦σ′) Definition 110

The result follows.

• The case λa.g with a ∉ fa(rng(σ)) ∪ fa(rng(σ′)). We have:

(λa.g)σσ′=α(λb.(b a) · g)σσ′b fresh≡ λb.((b a) · g)σσ′Definition 110=αλb.((b a) · g)(σ◦σ′) Lemma 106, Inductive hypothesis≡ (λb.((b a) · g)(σ◦σ′) Definition 110=α(λa.g)(σ◦σ′) b fresh

The result follows.End of proof

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 [22, 21]. Recall that, unlike [19], we work in an untyped λ-calculus.

Definition 114

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 every X in g occurs as Xa1. . . aφ(X), for some φ(X).

8. Translating nominal terms into the λ-calculus

8.1. The translation ⟦-⟧D, and its soundness

Definition 115

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 116

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 117

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 118

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

Proof

By induction on r.

• The case a. We have:

⟦π · a⟧D≡ ⟦π(a)⟧DDefinition 7≡ π · a Definition 117≡ π · ⟦a⟧DDefinition 96

The result follows.

• The case f(r1, . . . , rn). We have:

⟦π · f(r1, . . . , rn)⟧D≡ ⟦f(π · r1, . . . , π · rn)⟧DDefinition 7≡ f⟦π · r1⟧D . . . ⟦π · rn⟧DDefinition 117≡ fπ · ⟦r1⟧D . . . π · ⟦rn⟧DInductive hypothesis≡ π · f⟦r1⟧D . . . ⟦rn⟧DDefinition 96≡ π · ⟦f(r1, . . . , rn)⟧DDefinition 117

The result follows.

• The case [a]r. We have:

π · ⟦[a]r⟧D≡ π · λa.⟦r⟧DDefinition 117≡ λπ(a).(π · ⟦r⟧D) Definition 96≡ ⟦[π(a)](π · r)⟧DDefinition 117≡ ⟦π · [a]r⟧DDefinition 7

The result follows.

• The case π′ · XS.

⟦π · (π′ · XS)⟧D≡ ⟦(π◦π′) · XS⟧DDefinition 7≡ XS(π◦π′)(c1) . . . (π◦π′)(cn) Definition 117≡ π · (XSπ′(c1) . . . π′(cn)) Fact≡ π · ⟦π′ · XS⟧DDefinition 117

The result follows.End of proof

Lemma 119 is useful for the proof of Theorem 120:

Lemma 119

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

Proof

By induction on r.

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

• The case f(r1, . . . , rn). We have:

fa(⟦f(r1, . . . , rn)⟧D) = fa(f⟦r1⟧D . . . ⟦rn⟧D) Definition 117= fa(⟦r1⟧D) ∪. . . ∪fa(⟦rn⟧D) Definition 97⊆ fa(r1) ∪. . . ∪fa(rn) Inductive hypothesis= fa(f(r1, . . . , rn)) Definition 9

The result follows.

• The case [a]r. We have:

fa(⟦[a]r⟧D) = fa(λa.⟦r⟧D) Definition 117= fa(⟦r⟧D) \ {a} Definition 97⊆ fa(r) \ {a} Inductive hypothesis= fa([a]r) Definition 9

The result follows.

• The case π · XS. We have:

fa(⟦π · XS⟧D) = fa(XSπ(d1) . . . π(dn)) Definition 117= fa(π(d1)) ∪. . . ∪fa(π(dn)) Definition 97= π · (fa(d1) ∪. . . ∪fa(dn)) Fact⊆ π · fa(XS) Definition 9= fa(π · XS) Lemma 16

The result follows.End of proof

Theorem 120 (Soundness).

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

Proof

By induction on the size of r. We reason by cases on the last rule in the derivation of r =α s:

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

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

• The case D ∩S = []. Then ⟦π · XS⟧D = ⟦π′ · XS⟧D = XS. Using (λ=α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).

Using (λ=αp), (λ=αX), and (λ=αa), the result follows.

• The case (=α[]ab). By assumption, (b a) · r =α s and b ∉ fa(r). Choose fresh c, so c ∉ fa(r)∪fa(s). By Lemma 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 a)·s⟧D. By Lemma 118, λc.((c a) · ⟦r⟧D) =α λc.((c b) · ⟦s⟧D). By Lemma 119, c ∉ fa(⟦r⟧D) ∪ fa(⟦s⟧D).

Using (λ=αλab), λc.((c a) · ⟦r⟧D) =α λa.⟦r⟧D and λc.((c b) · ⟦s⟧D) =α λb.⟦s⟧D. By

Theorem 107, λa.⟦r⟧D =α λb.⟦s⟧D. By Definition 117, ⟦[a]r⟧D =α ⟦[b]s⟧D. The result follows.End of proof

8.2. Capturable atoms; injectivity and minimality

The main results of this subsection are Theorems 126 and 128, and also Definition 121.

⟦r⟧D (Definition 117) is parameterised by a vector D. Levy and Villaret introduced a similar translation [19, Definition 2]; they used all the atoms in r. We now show that the smaller set of capturable atoms in r (Definition 121) is consistent with injectivity of the translation (Theorem 126), and that it is minimal (Theorem 128).

Definition 121

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

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

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

For instance, if S = (comb ∪{a}) \ {b}, then capt([a][b]XS) = {a} and capt((b a) · XS) = {a}. We now prove that capt respects α-equivalence:

Lemma 122

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

Proof

By induction on r.

• The case b. Routine.

• The case f(r1, . . . , rn). If a ∉ fa(f(r1, . . . , rn)), then by Definition 9, a ∉ fa(ri) for 1 ≤i ≤n. We have:

captA(f(r1, . . . , rn)) =⋃1≤i≤n captA(ri) Definition 121=⋃1≤i≤n captA∪{a}(ri) Inductive hypothesis= captA∪{a}(f(r1, . . . , rn)) Definition 121

The result follows.

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

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

The result follows.

• The case π·XS. If a ∉ fa(π·XS), then a ∉π·S. By Definition 121, captA(π·XS) = (dom(π) ∪A) ∩S. Then, captA∪{a}(π · XS) = (dom(π) ∪A ∪{a}) ∩S. If π(a) = a, then a ∉S. If π(a) ≠ a, then a ∈ dom(π). The result follows.End of proof

Lemma 123

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

Proof

By induction on r.

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

• The case a. Since captA(π(a)) = ∅= captA(a).

• The case f(r1, . . . , rn). We have:

captA(π · f(r1, . . . , rn)) = captA(f(π · r1, . . . , π · rn)) Definition 7= captA(π · r1) ∪. . . ∪captA(π · rn) Definition 121= captA(r1) ∪. . . ∪captA(rn) Inductive hypotheses= captA(f(r1, . . . , rn)) Definition 121

The result follows.

• The case [a]r. We have:

captA(π · [a]r) = captA([π(a)](π · r)) Definition 7= captA∪{π(a)}(π · r) Definition 121

There are two cases to consider:

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

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

The result follows.

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

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

The result follows.

• The case π′ · XS. We have:

capt(π · (π′ · XS)) = captA((π◦π′) · XS) Lemma 15= (dom(π◦π′) ∪A) ∩S Definition 121= (dom(π) ∪dom(π′) ∪A) ∩S Fact= (dom(π′) ∪A) ∩S Assumption= captA(π′ · XS) Definition 121

The result follows.End of proof

Corollary 124

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

Proof

We have:

captA([b]r) = captA∪{b}(r) Definition 121= captA∪{a,b}(r) Lemma 122, a ∉fa(r)= captA∪{a,b}((b a) · r) Lemma 123= captA∪{a}((b a) · r) Lemmas 122 and 16= captA([a](b a) · r) Definition 121

The result follows.End of proof

Lemma 125

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

Proof

By induction on the derivation of r =α s.

• The case (=αaa). Straightforward.

• The case (=αf). Suppose r1 =α s1. . . rn =α sn. By hypothesis, captA(r1) = captAs1. . . captA(rn) = captAsn. Using (=αf), f(r1, . . . rn) =α f(s1, . . . , sn). Then, captA(f(r1, . . . , rn)) = captA(r1) ∪. . . ∪ captA(rn). The result follows.

• The case of (=α[a]). Suppose r =α s. By Definition 121, captA([a]r) = captA∪{a}(r), similarly for s. By inductive hypothesis, captA∪{a}(r) = captA∪{a}(s). The result follows.

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

• The case of (=αX). Suppose π|S = π′|S. Then, dom(π) ∩S = dom(π′) ∩S. The result follows.End of proof

Theorem 126 (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, reasoning by cases on the last rule in the derivation of ⟦r⟧D =α ⟦s⟧D:

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

• The case (λ=αλab). Suppose (b a) · ⟦r⟧D =α ⟦s⟧D, b ∉ fa(⟦r⟧D) and captA([a]r) ∪ captB([b]s) ⊆D.

Choose fresh c, so c ∉fa(r) ∪fa(s) and c ∉fa(⟦r⟧D) ∪fa(⟦s⟧D). By Lemma 99, (c a) · ⟦r⟧D =α (c b) · ⟦s⟧D. By Lemma 118, ⟦(c a) · r⟧D =α ⟦(c b) · s⟧D. By Corollary 124 and Definition 121, captA∪{c}((c a) · r) ∪captB∪{c}((c b) · s) ⊆D. By

hypothesis, (c a) · r =α (c b) · s. Using (=α[]ab), and by Theorem 107, [a]r =α [b]s. The result follows.

• The case (λ=αapp). By Definition 117, there are two cases:

• The case fr1. . . rn and fs1. . . sn and ⟦ri⟧D =α ⟦si⟧D for 1 ≤i ≤n. By hypothesis, ri =α si for 1 ≤i ≤n. Using (=αf), the result follows.

• The case XSπ(d1) . . . π(dn) and XSπ′(d1) . . . π′(dn) with [d1, . . . , dn] = D ∩S and π(di) =α π′(di) for 1 ≤i ≤n. Then π|D∩S = π′|D∩S follows immediately. By assumption, capt(π · XS) ⊆D. By definition, π|S = π′|S. Using (=αX), the result follows.

• The case (λ=αX). From the form of the translation, r ≡π · XS and s ≡π′ · XS and dom(π) ∩S = ∅= dom(π′) ∩S. Using (=αX), the result follows.

The corollary follows from the first part and Lemma 125.End of proof

Lemma 127

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

Proof

By induction on r.

• The cases a and b. Since captA(a) = ∅.

• The case f(r1, . . . , rn). Suppose a ∈ captA(f(r1, . . . , rn)), with a ∈ captA(ri) for some i with 1 ≤i ≤n. By hypothesis, XS ∈ fV (ri) with a ∈S. Then fV (f(r1, . . . , rn)) = fV (r1) ∪. . . ∪ fV (rn). The result follows.

• The cases [a]r and [b]s. We handle the first case, the second is similar. Suppose a ∈ captA([a]r). Then a ∈ captA∪{a}(r). By hypothesis, XS ∈ fV (r) exists with a ∈S. As fV ([a]r) = fV (r), the result follows.

• The π · XS. By Definition 121.End of proof

Theorem 128 (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 127, XS ∈ fV (r) exists with a ∈S. Choose fresh c, so c ∉ fa(r) ∪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

The main result of this subsection is Theorem 131.

We extend the translation to substitutions, to then prove that if a substitution solves a nominal unification problem, then its translation solves the translation of the problem. This raises a difficulty: θ 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 another vector E, 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 129

Define ⟦θ⟧E D by:

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

Lemma 130 is useful in the proof of Theorem 131:

Lemma 130

dom(π) ⊆{d1, . . . , dn} implies (λd1. . . . λdn.g)π(d1) . . . π(dn) =αβ π · g.

Proof

By induction on g.

• The case a. Suppose π(a) = a so a ∉{d1, . . . , dn}, therefore a[π(di)/di] ≡a for 1 ≤i ≤n, as required. Otherwise, suppose π(a) ≠ a, so a ∈{d1, . . . , dn}. Then a[π(di)/di] ≡π(di) for some 1 ≤i ≤n. The result follows.

• The case X, f and g′g. Routine.

• The case λa.g. Suppose π(a) = a, so a ∉{d1, . . . , dn} therefore a ∉{π(d1), . . . , π(dn)}. Write h for (λd1. . . . λdn.λa.g)π(d1) . . . π(dn). Then:

h =αβ(λa.g)[π(d1)/d1] . . . [π(dn)/dn] Definition 108=αβλa.(g[π(d1)/d1] . . . [π(dn)/dn]) a ∉{d1, . . . , dn}=αβλa.(π · g) Inductive hypothesis≡ λπ(a).(π · g) π(a) = a≡ π · λa.g Definition 96

The result follows. Otherwise, suppose π(a) ≠ a so a ∈{d1, . . . , dn} and therefore π(a) ∈{π(d1), . . . , π(dn)}. Assume a = di for some di and write h as shorthand for (λd1. . . . λdn.λa.g)π(d1) . . . π(dn). Then:

h =αβ(λa.g)[π(d1)/d1] . . . [π(dn)/dn] Definition 108=αβλb.((b a) · g[π(d1)/d1] . . . [π(dn)/dn]) b ∉fa(g), b ∉{d1, . . . , dn}=αβλb.((b a) · (π · g)) Inductive hypothesis=αλπ(b).((b a) · (π · g)) π(b) = b≡ π · λa.g Definitions 98 and 96

The result follows.End of proof

Theorem 131

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

Proof

By induction on r.

• The cases a. Routine.

• The case f(r1, . . . , rn). We have:

⟦f(r1, . . . , rn)θ⟧E≡ ⟦f(r1θ, . . . , rnθ)⟧EDefinition 43≡ f⟦r1θ⟧E . . . ⟦rnθ⟧EDefinition 117=αβf(⟦r1⟧D⟦θ⟧E D) . . . (⟦rn⟧D⟦θ⟧E D) Inductive hypothesis≡ (f⟦r1⟧D . . . ⟦rn⟧D)⟦θ⟧E DProperties of λ-calculus≡ ⟦f(r1, . . . , rn)⟧D⟦θ⟧E DDefinition 117

The result follows.

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

⟦(π · XS)θ⟧E≡ ⟦π · θ(XS)⟧EDefinition 43≡ π · ⟦θ(XS)⟧ELemma 118=αβ(λd1. . . . λdn.⟦θ(XS)⟧E)π(d1) . . . π(dn) Lemma 130≡ (XSπ(d1) . . . π(dn))⟦θ⟧E DDefinition 129≡ ⟦π · XS⟧D⟦θ⟧E DDefinition 117

The use of Lemma 130 above is valid, as capt(π ·XS) ⊆D, therefore dom(π)∩S ⊆ D ∩S by Definition 121. 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 11, Theorem 120, Lemma 31≡ λb.(⟦((b a) · r)θ)⟧EDefinitions 43 and 117=αβλb.(⟦(b a) · r⟧D)⟦θ⟧E DInductive hypothesis≡ (λb.⟦(b a) · r⟧D)⟦θ⟧E Db fresh≡ ⟦[b]((b a) · r)⟧D⟦θ⟧E DDefinition 117=α⟦[a]r⟧D⟦θ⟧E DDefinition 11, Theorem 120, Lemma 31

The result follows.End of proof

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

Definition 132

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

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

Corollary 133

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

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

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

⟦XS⟧D⟦θ1⟧E D=αβ⟦XSθ1⟧ETheorem 131=α⟦XS(θ2 ◦θ′)⟧ETheorem 120≡ ⟦(XSθ2)θ′)⟧ETheorem 33=αβ⟦XSθ2⟧E⟦θ′⟧E ETheorem 131, capt(θ2(XS)) ⊆E=αβ(⟦XS⟧D⟦θ2⟧E D)⟦θ′⟧E ETheorem 131≡ ⟦XS⟧D(⟦θ2⟧E D ◦⟦θ′⟧E E) Lemma 113

The result follows.End of proof

In Corollary 133, 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. Reducing permissive nominal unification to pattern unification; soundness, weak

completeness The main result of this subsection is Theorem 141. It says that if D and E are ‘large enough’, then θ solves Pr if and only if ⟦θ⟧E D solves ⟦Pr⟧D.

Definition 134

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 135

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} So if Pr = {XS ?=? f(Y S, a, ZS)} where S = comb ∪{a, b}, then the translation ⟦Pr⟧[a] = {λa.(XSa) ?=? λa.(f (Y Sa) a (ZSa))}.
Lemma 136

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

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

Proof

By induction on r.

• The case a. As captA(a) = ∅.

• The case f(r1, . . . , rn). We have:

captA(f(r1, . . . , rn)) = captA(r1) ∪. . . ∪captA(rn) Definition 121⊆ captB(r1) ∪. . . ∪captB(rn) Inductive hypotheses= captB(f(r1, . . . , rn)) Definition 121

The result follows.

• The case [a]r. We have:

captA([a]r) = captA∪{a}(r) Definition 121⊆ captB∪{a}(r) Inductive hypothesis= captB([a]r) Definition 121

The result follows.

• The case π · XS. We have:

captA(π · XS) = (dom(π) ∪A) ∩S Definition 121⊆ (dom(π) ∪B) ∩S Assumption= captB(π · XS) Definition 121

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

We need Lemma 137 to prove Lemma 138:

Lemma 137

captA(π · r) ⊆ ((dom(π) ∪A) ∩ fa(r)) ∪ capt(r).

Proof

By induction on r.

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

• The case [a]r. Suppose π(a) = a. Then:

captA(π · [a]r) = captA([a](π · r)) Definition 7, π(a) = a= captA∪{a}(π · r) Definition 121⊆ (dom(π) ∩fa(r)) ∪capt(r) Inductive hypothesis⊆ (dom(π) ∩fa(r)) ∪capt([a]r) Lemma 136= (dom(π) ∩fa([a]r)) ∪capt([a]r) a ∉dom(π)

Conversely, suppose π(a) ≠ a. Choose fresh b, so b ∉ dom(π) ∪ fa(r). Then, set π′ = (b a)◦π◦(b a). By Lemma 20, π · [a]r =α π′ · [a]r. By similar reasoning as above,

captA(π′ · [a]r) ⊆(dom(π′) ∪A) ∩fa([a]r)) ∪capt([a]r)

By Definition 9, a ∉ fa([a]r), and the result follows by sets calculations.

• The case π′ · XS. Then:

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

The result follows.End of proof

Lemma 138

fa(t) ⊆S implies captA(r[XS:=t]) ⊆ captA(r) ∪ capt(t). (We really do mean ‘capt(t)’, and not ‘captA(t)’.)

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

The first part is by induction on r.

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

• The case [a]r. Then:

captA([a](r[XS:=t])) = captA∪{a}(r[XS:=t]) Definition 121⊆ captA∪{a}(r) ∪capt(t) Inductive hypothesis= captA([a]r) ∪capt(t) Definition 121

The result follows.

• The case π · XS. As (π · XS)[XS:=t] ≡π · t, we reason as follows:

captA(π · t) ⊆ ((dom(π) ∪A) ∩fa(t)) ∪capt(t) Lemma 137⊆ ((dom(π) ∪A) ∩S) ∪capt(t) fa(t) ⊆S= captA(π · XS) ∪capt(t) Definition 121

The result follows. The second part follows from the first.End of proof

Remark 139

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 140

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

Proof

Suppose r ?=? s ∈Pr. By Definition 72, rθ =α sθ. By Theorems 120 and 126, ⟦rθ⟧E =α ⟦sθ⟧E. By Theorem 131, ⟦r⟧D⟦θ⟧E D =αβ ⟦s⟧D⟦θ⟧E D. It is a fact of the λ-calculus that this is equivalent to λd1. . . . λdn.⟦r⟧D⟦θ⟧E D =αβ λd1. . . . λdn.⟦s⟧D⟦θ⟧E D. As no atom of D is free in ⟦θ⟧E D, (λd1. . . . λdn.⟦r⟧D)⟦θ⟧E D =αβ (λd1. . . . λdn.⟦s⟧D)⟦θ⟧E D, as required.

The reverse implication uses the same results, in reverse order.End of proof

Theorem 141 (Soundness and weak completeness).

Suppose capt(Pr) ⊆D, and ⋃XS∈fV (P r) capt(θ(XS)) ⊆E, with D ⊆E. Then θ solves Pr if and only if ⟦θ⟧E D solves ⟦Pr⟧D.

Proof

An immediate consequence of Lemmas 140 and 138.End of proof

Pr = {XS?=? f(Y S, a, ZS)} where S = comb ∪{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 = comb ∪{a, b} translates to the solution ⟦θ⟧[[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 155. This strengthens the completeness result of Theorem 141, in a certain sense, by expressing that a class of σ solving ⟦Pr⟧D all originate from θ solving Pr, in a suitable formal sense.

Definition 142

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

Lemma 143

fa(g) = fa(gρ)

Proof

By induction on g.

• The case a. Since aρ ≡a.

• The case X. Since fa(X) = ∅ and ρ is a bijection on unknowns.

• The case f. Since fρ ≡ f.

• The case g′g. By hypothesis, fa(g′ρ) = fa(g′) and fa(gρ) = fa(g). As fa(g′g) = fa(g′) ∪ fa(g) = fa(g′ρ) ∪ fa(gρ) = fa((g′ρ)gρ), and (g′ρ)gρ ≡ (g′g)ρ, the result follows.

• The case λa.g. As fa((λa.g)ρ) = fa(λa.(gρ)) we have fa(λa.(gρ)) = fa(gρ) \ {a}. By hypothesis, fa(gρ) = fa(g). The result follows.End of proof

Lemma 144

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

• The cases (λ=αaa), (λ=αX) and (λ=αf). Routine.

• The cases (λ=αp) and (λ=αλaa). By the inductive hypotheses.

• The case (λ=αλab). For the left to right implication, by hypothesis, ((b a)·g)ρ =α hρ with b ∉ fa(g). By Theorem 107 and Lemma 111, (b a) · gρ =α hρ. By Lemma 143, b ∉ fa(gρ). Using (λ=αλab), λa.(gρ) =α λb.(hρ). The result follows. For the right to left implication, suppose ((b a) · g)ρ =α hρ with b ∉ fa(gρ). By Theorem 107 and Lemma 111, (b a) · gρ =α hρ. By Lemma 143, b ∉ fa(g). Using (λ=αλab), λa.g =α λb.h. The result follows.End of proof

Definition 145

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

Note that π · σ is a substitution. g(π · σ) is not a shorthand for π · (gσ), and the two are not equal in general.

Lemma 146

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

Proof

By induction on size(g).

• The case a. By assumption, π · a ≡a and aσ ≡a.

• The case X. Since X(π · σ) ≡π · σ(X) by Definition 145.

• The case f. Since π · f ≡ f and fσ ≡ f.

• The case g′g. If dom(π) ∩ fa(g′g) = ∅, then dom(π) ∩ fa(g′) = ∅ and dom(π) ∩ fa(g) = ∅. Then:

(g′g)(π · σ) ≡ g′(π · σ)(g(π · σ)) Definition 110=α(π · (g′σ))(π · (gσ)) Inductive hypotheses≡ π · ((g′g)σ) Definition 96≡ π · ((g′g)σ) Definition 110

• The case λa.g. There are multiple cases to consider:

• The case a ∉ fa(gσ), a ∉ fa(π · σ) and π(a) = a. Then:

(λa.g)(π · σ) ≡ λa.(g(π · σ)) Definition 110=αλa.(π · (gσ)) Inductive hypothesis≡ λπ(a).(π · (gσ)) Assumption≡ π · λa.(gσ) Definition 96≡ π · (λa.g)σ Definition 110

The result follows.

• The case a ∉ fa(gσ), a ∉ fa(π · σ) and π(a) ≠ a. Pick fresh b, so b ∉ fa(g), b ∉ fa(gσ), b ∉ fa(π · σ) and π(b) ≠ b. Every permutation has finite support, so b is guaranteed to exist. Then:

(λa.g)(π · σ) =α(λb.((b a) · g))(π · σ) Definition 98≡ λb.((b a) · g)(π · σ)) Definition 110=αλb.(π · (((b a) · g)σ)) Inductive hypothesis≡ λb.((π(b) π(a)) · ((π · g)σ)) Fact≡ λπ(b).((π(b) π(a)) · ((π · g)σ)) Assumption≡ λπ(a).(π · (gσ)) Definition 96≡ ((π(b) π(a))◦π) · (λa.(gσ)) Definition 96, Lemma 15≡ π · ((b a) · (λa.g)σ) Definition 110≡ π · ((λb.((b a) · g))σ) Definition 96=απ · (λa.g)σ Definition 98

The result follows. All other cases are similar to the case for a ∉ fa(gσ), a ∉ fa(π · σ) and π(a) ≠ a. The result follows.End of proof

Lemma 147

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

Suppose dom(π) ∩ (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 144, gσρ =α hσρ. By Lemma 113, g(σ◦ρ) =α h(σ◦ρ). The result follows.

• The case σ◦ρ solves ⟦Pr⟧D implies σ solves ⟦Pr⟧D. Suppose g ?=? h ∈⟦Pr⟧D and σ◦ρ solves ⟦Pr⟧D. Then g(σ◦ρ) =α h(σ◦ρ). By Lemma 113, gσρ =α hσρ. By Lemma 144, gσ =α hσ. The result follows.

For the second part, suppose dom(π) ∩ (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 118, dom(π)∩(fa(⟦r⟧D)∪fa(⟦s⟧D)) = ∅. By Lemma 146, Theorem 107 and Lemma 102, the result follows.End of proof

Remark 148

Lemma 147 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 155. ρ is the price we pay for using the same unknowns in Definitions 95 and 6: This design decision makes Definition 117 compact, but it causes technical problems in Lemma 154, because σ(X) can introduce new unknowns over whose permission sorts (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 λ-calculus. 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 117, 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 149

Let V be a finite set of unknowns. Call σ D-consistent on V when for every X ∈V, σ(X) =α λa1. . . . λak.q where k 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 150

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

Take Pr = {XS ?=? f([a]Y S, Y S)} with S = comb. 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]. (σ◦ρ)(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 = comb and T = comb \ {a}. Then ⟦Pr⟧D = {λa.(XS a) ?=? λa.(f (λa.Y T) Y T)} has the solution σ = [XS:=λc.(f (λc.a) a), Y T:=a]. (σ◦ρ)(Y T) =α ⟦θ⟧E D(Y T) is impossible, since a ∈ fa(a) whereas a ∉ fa(⟦θ(Y T)⟧E) by Lemma 119.

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 147 allows us to eliminate with a permutation π.

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

Definition 151

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 152

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 π is a fixed but arbitrary choice of permutation of the atoms in E, mapping the ith element of E ∩S (Definition 116) to bi for 1 ≤i ≤ φ(X).

Lemma 153

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

Proof

By induction on q.

• The cases a and fq1. . . qn. Routine.

• The case λa.g. Suppose args(λa.q) ⊆E so that args(q) ⊆E. By hypothesis, ⟦q-E⟧E ≡q. The result now follows.

• The case Xb1. . . bn. Then q-E = π · X and ⟦q-E⟧E ≡Xπ(x1) . . . π(xn), where [x1, . . . , xn] = E ∩δ(X) and π(xi) = bi. The result follows.End of proof

Lemma 154

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 129≡ λa1. . . . λan.(qρ) Lemma 153≡ (λa1. . . . λan.q)ρ Fact of λ-calculus=α(σ◦ρ)(X) By constructionEnd of proof
Theorem 155

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 154, 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 141, θ 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 147.End of proof

10. Conclusions

Nominal contrasted with permissive nominal terms. Permissive nominal terms come closer to first- and higher-order terms than nominal terms do, but they are a special case of neither. The idea of associating permissions sets to unknowns is mentioned already in [27, Remark 2.6]. What really makes that idea come alive, in this paper, is the use of fixed permissions sets of co-infinite sets of atoms. This has beneficial technical repercussions which go well beyond ‘just tweaking nominal terms’. We recover Theorem 13 and Corollary 14, α-equivalence is a property of terms (of course; there are no longer freshness contexts) — and the notions of unification problem and solution are based on equality (rather than equality-and-freshness-context) with no loss of expressivity.

Permissive nominal terms do not obsolete nominal terms; if we want to talk about ‘an arbitrary term’, then a nominal terms unknown ˙X is more directly useful than a permissive nominal terms unknown Xcomb (which means ‘an arbitrary term, mentioning atoms in comb’).

In Section 4 we connected the ‘permissive’ and the ‘nominal’ worlds in some technical detail. In nominal terms, if we need a fresh name then we can enrich the freshness context (consider [12, Figure 2, axiom (fr) ] and [13, e.g. Lemma 25 and Theorem 33]). One nice way to view the interpretation of Section 4 is that comb plays the rôle of ‘the atoms we had so far’ and A \ comb that of ‘the atoms we will generate fresh in the future’.

Related work on unification. Patterns emerged by studying Skolemisation of unification problems [22]; they proved useful in the unification of higher-order abstract syntax terms [21]. Cheney proposed a two-stage translation of higher-order to nominal unification [3], 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’s translation [19], of nominal unification to higher-order patterns, crystallised an intuition that pattern unification is exactly what is needed to unify encodings of nominal terms. Their encoding is not minimal and addresses unifiability rather than individual solutions. In Section 8 we refined their encoding, using capt(r) (Definition 121) to obtain one that is minimal, and in Section 9 we established a precise sense in which solutions correspond across the translations.

Hamana’s β0 unification of λ-terms with holes adds a capturing substitution [16]. 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 permissions sorts also describe which level 1 variable symbols (we call them atoms in this paper) may appear in them, though with our permissions sorts 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 [23] 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).

Future work. We noted, in Definition 2, that comb is incompatible with the finite-support property of nominal sets [15, Definition 3.1]. This matters because permissive nominal terms can be directly quotiented by α-equivalence, so it could be useful to apply the Gabbay-Pitts model of abstract syntax up to α-equivalence [14]. We hypothesise that this can be overcome by using generalisations of nominal sets by the second author [10] or by Cheney ([2, Section 3], or [4]). We also hypothesise a theory of rewriting could be developed similarly to [9].

Via the interpretation in Section 4 this extends to solutions of ‘ordinary’ nominal unficiation problems. We have begun to apply permissive nominal terms to construct novel logics and λ-calculi, taking advantage of their properties to simplify the theory — we find it 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.

Nominal terms come with a denotation in nominal sets [14]. These are based on the idea of giving names a denotational reality as urelemente [28] (the atoms in this paper can be considered urelemente of a sets universe; this is a reason that nominal terms retain a first-order flavour). Famously, nominal sets exclude sets like permission sorts S, because they do not have finite support. This is fully consistent with our use of permission sorts here; in this paper we are working at the meta-level where we can talk about any sets of atoms that we like. However, generalisations of nominal sets exist [10, 2] and we believe that permissive nominal terms can use them for denotation. Checking this is future work.

References

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

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

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

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

[5] Gilles Dowek and Murdoch J. Gabbay. Relating the solutions of nominal unification and pattern unification. 2009. Available online at http://www.gabbay.org.uk/papers/relsnp.pdf.

[6] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive nominal terms and their unification. 2009. Available online at http://www.gabbay.org.uk/papers/perntu.pdf.

[7] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive nominal terms and their unification. 2009. Available online at http://www.gabbay.org.uk/papers/perntu-jv.pdf.

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

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

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

[11] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. Electronic Notes in Theoretical Computer Science, 196:19–35, 2008.

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

[13] Murdoch J. Gabbay and Dominic P. Mulligan. Two-and-a-halfth Order Lambda-calculus. Electronic Notes in Theoretical Computer Science, 2009. To appear.

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

[15] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax Involving Binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, 1999.

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

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

[18] J.-W. Klop, V. van Oostrom, and F. van Raamsdonk. Combinatory reduction systems. Theoretical Computer Science, 121:279–308, 1993.

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

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

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

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

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

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

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

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

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

[28] Ernst Zermelo. Untersuchungen über die Grundlagen der Mengenlehre. Mathematische Annalen, 65:261–281, 1908.

Notes

1The second author helped develop nominal sets [14], which famously disallow sets like comb (comb lacks finite support) [14]. Here, we are working at the meta-level, where we can talk about any subset or function that we wish. ↩

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

3Note to referees: an error in a previous version of this paper, which made the algorithm incomplete, has been corrected. ↩

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