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

MURDOCH J. GABBAY

NOMINAL TERMS AND NOMINAL LOGICS: FROM FOUNDATIONS TO META-MATHEMATICS

ABSTRACT: Nominal techniques concern the study of names using mathematical semantics. Whereas in much previous work names in abstract syntax were studied, here we will study them in meta-mathematics. More specifically, we survey the application of nominal techniques to languages for unification, rewriting, algebra, and first-order logic. What characterises the languages of this chapter is that they are first-order in character, and yet they can specify and reason on names. In the languages we develop, it will be fairly straightforward to give first-order ‘nominal’ axiomatisations of name-related things like alpha-equivalence, capture-avoiding substitution, beta- and eta-equivalence, first-order logic with its quantifiers—and as we shall see, also arithmetic. The formal axiomatisations we arrive at will closely resemble ‘natural behaviour’; the specifications we see typically written out in normal mathematical usage. This is possible because of a novel name-carrying semantics in nominal sets, through which our languages will have name-permutations and term-formers that can bind as primitive built-in features. This chapter draws together material from several papers to deliver a coherent account of a journey from the foundations of a mathematics with names, via logical systems based on those foundations, to concrete applications in axiomatising systems with binding. Definitions and proofs have been improved, generalised, and shortened, and placed into an overall narrative. On the way we touch on a variety of definitions and results. These include: the nominal unification algorithm; nominal rewriting and its confluence proofs; nominal algebra, its soundness, completeness, and an HSP theorem; permissive-nominal logic and its soundness and completeness; various axiomatisations with pointers to proofs of their correctness; and we conclude with a case study stating and proving correct a finite first-order axiomatisation of arithmetic in permissive-nominal logic.

D. Gabbay and F. Guenthner (eds.), Handbook of Philosophical Logic, Volume 17, 1–??. ⃝c 2012, Kluwer Academic Publishers. Printed in the Netherlands.

CONTENTS

MURDOCH J. GABBAY Nominal Terms and Nominal Logics: From Foundations to Meta-mathematics 11 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 NOMINAL SETS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.1 Atoms, permutations, permission sets . . . . . . . . . . . . . . . . . 82.2 Permissive-nominal sets . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Equivariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Examples of permissive-nominal sets . . . . . . . . . . . . . . . . . 142.5 Strong support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 THE SYNTAX OF NOMINAL TERMS . . . . . . . . . . . . . . . . . 183.1 Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Free unknowns of a term . . . . . . . . . . . . . . . . . . . . . . . . 223.4 Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.5 Composition and invertibility of substitutions . . . . . . . . . . . . . 253.6 shift-permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.7 Occurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 UNIFICATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.1 The unification algorithm . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Examples of the algorithm . . . . . . . . . . . . . . . . . . . . . . . 334.3 Preservation of solutions . . . . . . . . . . . . . . . . . . . . . . . . 344.4 Simplification rewrites calculate principal solutions . . . . . . . . . . 365 REWRITING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.1 Rewrite rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2 Rewrite steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.3 Peaks, critical pairs, joinability . . . . . . . . . . . . . . . . . . . . . 415.4 Uniform rewriting . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.5 Orthogonal rewrite systems . . . . . . . . . . . . . . . . . . . . . . . 445.6 Nominal rewriting with freshness contexts versus permissive-nominal rewriting . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 CLOSED TERMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.1 The definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.2 Closed rewrite rules . . . . . . . . . . . . . . . . . . . . . . . . . . 497 EQUALITY: (PERMISSIVE-)NOMINAL ALGEBRA . . . . . . . . . 507.1 Judgement form, axioms, theories . . . . . . . . . . . . . . . . . . . 507.2 Derivable equality . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.3 Interpretation of signatures and terms . . . . . . . . . . . . . . . . . 537.4 Models and soundness . . . . . . . . . . . . . . . . . . . . . . . . . 547.5 Free term models and completeness . . . . . . . . . . . . . . . . . . 55
7.6 Freshness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577.7 Design of nominal algebra . . . . . . . . . . . . . . . . . . . . . . . 588 THE NOMINAL HSP THEOREM . . . . . . . . . . . . . . . . . . . . 598.1 Algebra homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 608.2 Subalgebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618.3 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618.4 Ground term models and extending a signature . . . . . . . . . . . . 628.5 Surjective maps onto algebras . . . . . . . . . . . . . . . . . . . . . 638.6 Injections out of free algebras . . . . . . . . . . . . . . . . . . . . . 638.7 Proof of the HSP theorem . . . . . . . . . . . . . . . . . . . . . . . 649 PERMISSIVE-NOMINAL LOGIC . . . . . . . . . . . . . . . . . . . . 659.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659.2 Derivability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669.3 Interpretation and soundness . . . . . . . . . . . . . . . . . . . . . . 689.4 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6910 CASE STUDY: ARITHMETIC IN PERMISSIVE-NOMINAL LOGIC . 7310.1 The signature .L and the axioms . . . . . . . . . . . . . . . . . . . . 7310.2 The axioms: equality, substitution, first-order logic, and arithmetic . . 7410.3 Comments on the axioms . . . . . . . . . . . . . . . . . . . . . . . . 7510.4 First-order logic L . . . . . . . . . . . . . . . . . . . . . . . . . . . 7610.5 Interpretation of first-order logic . . . . . . . . . . . . . . . . . . . . 7710.6 A theory of arithmetic in L . . . . . . . . . . . . . . . . . . . . . . . 7810.7 Building an interpretation for .L from one for L . . . . . . . . . . . . 7911 FURTHER PROPERTIES OF PNL . . . . . . . . . . . . . . . . . . . 8111.1 More PNL theories . . . . . . . . . . . . . . . . . . . . . . . . . . . 8111.2 Admissibility of Cut . . . . . . . . . . . . . . . . . . . . . . . . . . 8311.3 Exhausting the available atoms . . . . . . . . . . . . . . . . . . . . . 8512 CONCLUSIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85A AN ATLAS OF NOMINAL LANGUAGES . . . . . . . . . . . . . . . 91INDEX 97

1 INTRODUCTION

Nominal sets for meta-mathematics Suppose we want to axiomatise the λ-calculus or first-order logic. Then we need to express properties like this:

• If y ∉ fv(t) then ∀x.t =α ∀y.(t[y/x]).

• If x ∉ fv(u) then (λx.t)[u/y] = λx.(t[u/y]).

• If x ∉ fv(t) then λx.(tx) =η t.

x, y, t, and u here are what we would call names. A linguist might call them referents, a mathematician might call them variables. But the words ‘referent’ and ‘variable’ carry connotations (a referent should refer to something, a variable should vary), so we prefer the more neutral term ‘name’. So for us, a name is just an atomic symbol, to which we may then associate further properties, at our discretion, using additional axioms.

The axioms above are typical of a certain kind of specification. Mathematical specification is nothing new. First-order logic can specify, to choose a classic trio of examples, groups, rings, and fields. But the λ-calculus, first-order logic itself, the π-calculus, and a very great many other examples, are different. They have names.

By adding names to first-order logic in the correct way, we can axiomatise the specifications above, cleanly and in a manner very close to the informal specification. How should we do this? Using a recent application of mathematical foundations originating in computer science: nominal sets [GP01; Gab11b], to which we will use nominal terms [UPG03; UPG04] as a corresponding formal syntax. To survey and update the state of the art of logics based on nominal terms and taking semantics in nominal sets, is our goal here.

In nominal terms, term-formers can bind names and freshening renamings like the [y/x] or [u/y] above are taken as primitive.

Here are the informal statements above, rewritten in permissive-nominal algebra— an algebraic logic based on nominal terms with a sound and complete semantics in nominal sets:

• If b ∉ supp(X) then ∀([a]X) = ∀([b](b a)·X).

• If a ∉ supp(Y) then λ([a]X)[b↦→Y ] = λ([a](X[b↦→Y])).

• If a ∉ supp(X) then λ([a](Xa)) = X.

In this chapter we will briefly consider nominal sets, then survey nominal terms, unification, rewriting, algebra, and permissive-nominal logic. We cover the nominal unification algorithm, confluence proofs for nominal rewriting, soundness and completeness results for nominal algebra and permissive-nominal logic, an HSP theorem, and a finite axiomatisation of first-order logic.

By doing this we aim to give an overview of the applications of nominal sets to meta-mathematical syntax. We cannot be exhaustive, but we can try to be representative of what can be achieved.

As we shall see, nominal syntax is more expressive than first-order syntax (for instance we can give a finite first-order axiomatisation of arithmetic), because term-formers that can explicitly manipulate names. Yet, it remains first-order in flavour, preserving theoretical and computational properties like completeness and most general unifiers.

A few words on atoms What nominal sets add to ‘ordinary’ structures is an assumption of a distinguished class of symmetric atomic elements called atoms: these are also called urelemente or names. We will use these terms more-or-less synonymously.

Indeed, nominal sets are a special case Zermelo-Fraenkel sets with atoms, and are instances of the structures considered by Fraenkel and Mostowski in their celebrated independence proof of the the Axiom of Choice from the other axioms of set theory with atoms. For detailed references see [Gab11b, Remark 2.22]. So this chapter really does describe a journey from mathematical foundations to meta-mathematics, and that is representative of how the maths we describe here was arrived at.

We can view the underlying philosophy of nominal techniques is as the following informal inequality, where ‘smaller’ means ‘greater generality’:

atoms = urelemente = names ≤referents ≤variables

Discovering to what extent these intuitions can be made precise, concrete, and useful, is the topic of much ongoing research, some of which is reported on here.

Names induce automorphisms generated by permuting them. We shall see that if we model variables as a special case of atoms, then α-renaming becomes a special case of a much more general fact that nominal sets are symmetric under permuting atoms. This generalisation turns out to have powerful consequences, including the atoms-abstraction and N-quantifier introduced by the author with Pitts in [GP01]. So the point of view described above has led to and continues to lead to new reasoning principles.

If we identify a thing with the properties of that thing, then the ‘nominal’ model suggests that names are equal to the following set of three properties:

names = {atomic, symmetric, generative}

The reader familiar with nominal techniques can identify these three properties with the use of: atomic symbols a (an atom, name, or urelement, with a distinct existence in the denotation), permutations π (symmetries under permutation of names), and the N-quantifier (‘choose a fresh name’). These three properties will appear directly in this chapter as atoms, permutations, and permission sets.1 Full definitions appear below.

This material in the literature This paper surveys existing literature on logics based on nominal terms, and adds a few new results. Very broadly, Section 2 is based on [GP99; GP01] (nominal sets; they were called equivariant FM sets there); Sections 3 and 4 are based on [UPG03; UPG04; DGM09; DGM10; Gab12a] (nominal terms and unification); Sections 5 and 6 are based on [FGM04; FG07; Gab12a] (rewriting and closed terms); Section 7 is based on [Gab05; GM06a; GM07; GM09a] (nominal algebra); Sections 9 to 11 are based on [DG10; DG12a] (permissive-nominal logic).

Definitions and proofs may have changed from the original presentations. In particular:

• The semantics is permissive-nominal, meaning that it is based on possibly infinitely supported nominal sets with co-infinite support. In [GP01] a nominal semantics based on finite and co-infinite support was used.

• Unlike [UPG04] and [DGM10] we use nominal abstract syntax to build our nominal terms. That is, in this paper nominal terms atoms-abstraction is directly equal to Gabbay-Pitts atoms-abstraction. Thus, nominal terms here are an instance of nominal abstract syntax and come quotiented by α-equivalence by construction.

• Permutation may be stronger than usual, and we parameterise over the group of permutations. We consider (as usual) finite permutations (generated by swappings, also called transpositions) as standard, but in particular we also find shift-permutations δ useful, which shift infinitely many atoms. The shift-permutation δ corresponds

to a de Bruijn shift function ↑ and presheaf reindexing map up, though δ is not equal to them since it is a permutation and so invertible.

• Syntax includes non-equivariant constant symbols. In [UPG04] all term-formers/function-symbols (including 0-ary ones, i.e. constants) were equivariant. This does not matter for finite support but it does make a difference with infinite support.

• Nominal unknowns are modelled as arbitrary elements of a strongly-supported nominal set. This means that the X and Y in this paper correspond to moderated unknowns from [UPG04]: see Example 3.1.7.

• Because unknowns have support, there are no freshness contexts and substitutions are characterised as equivariant functions (the freshness conditions normally attached to substitutions follow from equivariance: see Proposition 3.4.3). The theories of nominal unification, rewriting, and algebra are reformulated to reflect this.

• The simplification rules for unification problems (Figure 2) are new and the treatments of closed terms and closed nominal rewriting (Section 6) are entirely revised with respect to [FG07].

Nominal sets and nominal terms

2 NOMINAL SETS

We open with a brief presentation of nominal sets, which are the semantic basis for this work: this is the universe that the logics we define will describe, and be sound (and complete) for.

Nominal sets were developed with Pitts and introduced in the author’s thesis [Gab01], a conference paper [GP99], and journal paper [GP01]. The nominal sets here are more general than in [GP01]: following [DGM10] we are permissive, meaning that we split the set of atoms into two infinite halves and consider infinite support. This specific idea was developed jointly with Dowek,2 but shades of it appear also in Cheney’s paper [Che06] and in the author’s study of infinite atoms-abstraction [Gab07b].

In addition we parameterise over a group of permutations which need not just be finitely-supported permutations. This is new.

2.1 Atoms, permutations, permission sets

In Definition 2.1.2 we need several sets of atoms. This is to model the several sorts of names that will appear in our syntax later on.

Following [DGM10] our development will be permissive-nominal. A permission set S splits a set of atoms into two halves A< and A> . One intuition for A< is ‘the atoms that have been generated so far’, and for A> is ‘the atoms that might be generated later’.

Definition 2.1.1

Write N = {0, 1, 2, 3, . . .} for the natural numbers and Z = {0, -1, 1, -2, 2, . . .} for the integers.

Definition 2.1.2

For each i ∈N fix a pair of disjoint countably infinite sets of atoms A<i and A>i.

Write

Ai = A< ⊎A>A< =⋃A<iA> =⋃A>iA =⋃Ai

a, b, c, . . . will range over distinct atoms: we call this the permutative convention.

Remark 2.1.3 (Comments on splitting the set of atoms).

The different sets of atoms Ai are different ‘types’ of atoms. Thus, later on in Definitions 3.1.1 and 3.2.1 we can give each name sort its own distinct population of atoms.

The reasons for splitting the set of atoms into A< and A> will become clear as the maths develops. It might help to think of A< as ‘atoms that can be captured’ and of A> as ‘atoms that cannot be captured’, or as ‘atoms that might have been generated in the past’ and ‘atoms that may be generated in the future’—but with reservations. In Definition 2.1.10 we see that this is only true up to permuting atoms.

The real purpose of Definition 2.1.2 is to ensure that we have plenty—countably infinitely many—of ‘capturable’ and ‘non-capturable’ atoms. Permutations (below) can and will move atoms between these worlds, but no permutation can move them all at once. So the interest of A< is not just for the set itself but for its orbit under permutations; this is a property of the set as a whole, and not of its individual elements.

Remark 2.1.4 (Comments on the permutative convention).

While visiting Tel-Aviv University in 2006 I gave talks on nominal techniques and Arnon Avron asked: “Do a and b refer to specific atoms (e.g. in the axioms in the Introduction), or to any two atoms?”. In other words, are a and b constants or variables?

In response I started using a permutative convention that a and b are variables, but they range over distinct atoms so that variables with distinct names refer to distinct objects (the first uses were in [GM06c; GM06a]; the convention was explicitly named in [GM08c]).

For a while this was resisted by some anonymous referees. Yet, we typically apply the permutative convention informally; e.g. we silently assume that λx.λy.xy is never the same term as λx.λx.xx. I would claim that the permutative convention expresses something about the foundational origins of the nominal view of names as urelemente—constants that are distinguishable yet symmetric—in an underlying set theory.

Perhaps this is why the referees did not like it: the permutative convention may seem unnatural if we are committed to standard (nameless) Zermelo-Fraenkel foundations, since names are then just some set, and like any set should be varied over non-permutatively by variables. Thus the fact that we accept that λx.λy.xy and λx.λx.xx always signify distinct λ-terms to us, can be taken as a sign that we inhabit a nameful foundation, so that the permutative convention is a signpost on the way to something more extensive.

A formal reflection of the permutative convention appears explicitly in the formal logics of this paper: it lives in the π of the π·X in Definition 5.2.1.

Definition 2.1.5

Given a, b ∈Ai for some i ∈N write (a b) for the swapping bijection on atoms mapping a to b, b to a, and any other c ∈A \ {a, b} to c.

Another standard name for a swapping is a transposition. By convention (a a) will denote the identity function on atoms id. If π is a bijection on atoms define

nontriv(π) = {a | π(a) ≠ a}.
Definition 2.1.6

A nominal permutation group is any set of bijections P of A such that:

1. If a ∈Ai and b ∈Ai then (a b) ∈P.

2. If π ∈P then a ∈Ai if and only if π(a) ∈Ai.

3. There exists some infinite S ⊆A such that nontriv(π) ∩S is finite for every π ∈P.

Call a bijection on atoms π a finite permutation when it is in the subgroup generated by swappings. (π is finite when π(a) ∈Ai if and only if a ∈Ai and nontriv(π) is finite.)

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

The purpose of conditions 1 to 3 of Definition 2.1.6 are as follows:

1. Swappings make sure we can always rename a to b (and b to a).

2. Condition 2 is a standard typing condition, that we do not try to turn an atom of one sort, into an atom of another sort.

3. This condition guarantees that we can still always choose a fresh atom for any finite set of permutations (see for instance Lemma 3.2.9).

Example 2.1.7

1. The set of all finite permutations is a nominal permutation group.

2. For each i fix a bijection fi between Ai and the integers Z, such that {f(i) | i ≤ 0} = A<i and (consequently) {f(i) | i > 0} = A>i . We can do this because we assumed atoms are countable.

Write δi for the permutation mapping

• fi(j) to fi(j−1) for j ≤ 0,

• fi(2j) to fi(2(j−1)) and fi(2j−1) to fi(2j−1) for j ≥ 1, and

• any other c ∈A \ Ai to c.

This is an example of a shift-permutation, considered in more generality in Definition 3.6.1 and throughout Subsection 3.6. We illustrate fragments of the actions of a swapping (f(0) f(1)) and a δi:

f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6)f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6)

The atoms corresponding to positive odd integers are taken to be fixed points of δi in order to satisfy condition 3 of Definition 2.1.6, so that these atoms can be taken fresh for δi if we need to.

The set of permutations generated by swappings and δi, is a nominal permutation group.

Remark 2.1.8

The nominal permutation group P determines the symmetries of our nominal syntax and semantics. We consider permutations designed to guarantee (in Definition 2.2.3) symmetry up to equality/inequality of atoms. We will get sets with atoms that are atomic, symmetric (up to equality and inequality of names), and generative—the main further design choice we care about is whether or not to include a shift (Example 2.1.7), which goes strictly beyond what can be achieved with finite permutations as considered e.g. in [GP01].

Other notions of permutation may lead to other symmetries, so an interesting topic of future research is to weaken the conditions in Definition 2.1.6.

For instance, if we only allow permutations generated by f(i) ↦→f(i + 1) and f(i) ↦→f(-i) then we preserve a notion of ‘distance’ between atoms.3 In a similar vein, we can identify atoms with points in a plane and consider Euclidian transformations. It is not known how much of ‘nominal techniques’ would hold of such examples.

More generally of course, presheaves are a forum within which sets with symmetry structure can be expressed. Indeed, nominal sets can be viewed as a category of presheaves [GP99] and a similar presheaf category was considered at the same time

[FPT99] (see also the later related nominal renaming sets [GH08], which are in some sense half-way in between those two systems).

There is no shortage of research into this kind of structure [MM92]. It remains, however, to understand what are the abstract properties that make a set with a group action, or a presheaf, into something ‘nominal’.

Definition 2.1.9

If A ⊆A define the pointwise action by

π·A = {π(a) | a ∈A}.
Definition 2.1.10

A permission set S is a set of the form π·A<. S, T will range over permission sets.

Remark 2.1.11

Some preliminary comments on permission sets:

• The notion of permission set used in some previous work, for instance in [DGM10, Definition 2.2], was slightly different: a permission set was taken to be a set of the form (S \ A) ∪B for finite A ⊆A< and B ⊆A> . In the presence of shift-permutations we can do this using a permutation, and any (S \ A) ∪B can be written as π·S for suitable π (cf. Remark 3.6.2 and δX-a·X in (IF) of Figure 2). Given that the designs are equivalent for the cases we will care about, we chose Definition 2.1.10 because it is somewhat simpler to do mathematics with.

• In the semantics, permission sets are used in the definition of support Definition 2.2.3; if permutations specify symmetry, permission sets specify captura-bility and generativity (Remark 2.2.4).

• In the syntax, permission sets are used to control capture (see Remark 3.4.9); atoms in S are intuitively ‘capturable’ and atoms not in S are intuitively ‘not capturable’. This is reminiscent of some treatments of syntax where a formal distinction is made between ‘names that exist to be bound’ and ‘names that exist to be free’. See for instance the freie and gebundene Gegenstansvariable of Gentzen [Gen35, Section 1], and the individual variables and parameters of Prawitz [Pra65, Section 1], or Smullyan [Smu68, Chapter IV, Section 1]. However, note that here, for any a ∈S and b ∉S, also a ∉ (b a)·S and b ∈ (b a)·S. That is, for any given atom there is no fixed sense in which it is

capturable or not capturable. Each individual permission sets defines its own world of capturable/non-capturable atoms, which differs by a permutation π from what is really a fixed but entirely arbitrary representative A<.

2.2 Permissive-nominal sets

Definition 2.2.1

A set with a (P-)permutation action X is a pair (|X|, ·) of

• a carrier set |X| and

• a group action (P × |X|) →|X|, written infix as π·x. So, id·x = x and π·(π′·x) = (π ◦π′)·x for every π, π′, and x ∈|X|.

Definition 2.2.2

Given a set with a P-permutation action X say that A ⊆A supports x ∈|X| when for all permutations π ∈P, if π(a) = a for all a ∈A then π·x = x.

Also, call A ⊆A small when A ⊆S for some permission set S.

Definition 2.2.3

A permissive-nominal set is a set with a permutation action such that every element has a unique least small supporting set supp(x). We call this the support of x. X, Y will range over permissive-nominal sets.

Note in Definition 2.2.3 that supp(x) must be small, that is, included in some permission set. For instance, a ∈A—with A having the natural permutation action given by π·x = π(x) for x ∈A—is supported by {a} and A \ {a}, but the former is small while the latter is not.

Remark 2.2.4

The difference between a set with a permutation action and a ‘nominal’ set is that nominal sets guarantee for any element, infinitely many atoms fresh for that element.

A mild generalisation of Definition 2.2.3 is possible, where we insist there is a supporting set but do not insist on the existence of a unique least such set. It is possible to do a surprising amount just with that; see for instance Fiore, Plotkin and Turi’s paper [FPT99] based on presheaves, and the ‘nominal’ study of infinite permutations and infinite atoms-abstraction in [Gab07b].4

Example 2.2.5

• First-order syntax with variable symbols (modelled as atoms) is a permissive-nominal set, where the permutation action permutes variable symbols directly in syntax so that e.g. π·λa.t = λπ(a).π·t. A term t is supported by the variable symbols it contains. In this and the following examples the precise nature of the permutation group is not important.

• First-order syntax up to α-equivalence is a permissive-nominal set. The α-equivalence class of t is supported by the free variable symbols of t. A full proof is in [Gab11b, Theorem 5.18].

• Traces of π-calculus processes with channel names (atoms) taken from some permission set S, form a permissive-nominal set. A trace is supported by the set of channel names it mentions (which may be infinite in number).

• Given a permissive-nominal nominal set X the set of subsets U ⊆|X| with the pointwise action π·U = {π·u | u ∈U} is a set with a permutation action (this generalises Definition 2.1.9). The subset of this consisting of those subsets U ⊆|X| that have a supporting permission set under this action, forms a permissive-nominal set pow(X).5

Lemma 2.2.6

Suppose X is a permissive-nominal set and x ∈|X|. Then supp(π·x) = π·supp(x).

Proof

By a routine calculation using the group action. ■

We conclude with a useful condition for checking whether a ∈ supp(x):

Corollary 2.2.7

Suppose X is a permissive-nominal set and x ∈|X|. Suppose b ∉ supp(x). Then (b a)·x = x if and only if a ∉ supp(x).

Proof

Suppose b ∉ supp(x). The right-to-left implication is by the definition of support. For the left-to-right implication, we prove the contrapositive. Suppose a ∈ supp(x). By Lemma 2.2.6 supp((b a)·x) = (b a)·supp(x). By our suppositions, (b a)·supp(x) ≠ supp(x). It follows that (b a)·x ≠ x. ■

2.3 Equivariance

Definition 2.3.1

Suppose X and Y are permissive-nominal sets.

Call x ∈|X| equivariant when supp(x) = ∅. (So x is equivariant when π·x = x for all π.)

Call F ∈|X| →|Y| equivariant when

∀π ∈P.∀x ∈|X|.π·(F(x)) = F(π·x).

F will range over equivariant functions between pairs of permissive-nominal sets.

Remark 2.3.2

The second notion of equivariance in Definition 2.3.1 is a special case of the first. For details, see e.g. Definition 9.3 and Lemma 9.4 of [Gab11b].

Lemma 2.3.3

If F from |X| to |Y| is equivariant then supp(F(x)) ⊆ supp(x) for all x ∈|X|.

Proof

Suppose π ∈ fix(supp(x)). By assumption π·F(x) = F(π·x), and π·x = x.

■

Definition 2.3.4

Write PmsPrm for the category with objects permissive-nominal sets and arrows equivariant functions between them.

So X, Y range over objects in PmsPrm (Definition 2.2.3).

2.4 Examples of permissive-nominal sets

Throughout the rest of this document we will need the following examples of permissive-nominal sets: atoms, booleans, lists, product, equivariant elements, permutation orbits, and atoms-abstraction. We consider each in turn now.

Atoms, Booleans, infinite lists

Definition 2.4.1 (Atoms).

A the set of all atoms can be considered a permissive-nominal set with a natural permutation action π·a = π(a). So can each Aν.

Definition 2.4.2

If X is a permissive-nominal set say the permutation action is trivial when π·x = x for all x ∈|X| and all π ∈P.

So X is trivial if and only if all its elements are equivariant.

Definition 2.4.3

Any ‘ordinary’ set can be made into a permissive-nominal set by giving it the trivial permutation action such that π·x = x always.

In particular, the set B = {0, 1} can be considered a permissive-nominal set with the trivial permutation action; so can N and Z from Definition 2.1.1.

In the cases of A and {0, 1} only, we will be lax about the distinction between the set, and the permissive-nominal set with its natural permutation action.

Definition 2.4.4 (Infinite lists).

Define a permissive-nominal set L by:

• |L| is the set of infinite sequences of distinct atoms L = [a1, a2, a3, . . .] such that atms(L) = {a1, a2, a3, . . .} is a permission set.

• π·L = [π(a1), π(a2), π(a3), . . . ].

Product

Definition 2.4.5

Suppose I is an indexing set.6 If Xi are permissive-nominal sets for i ∈I then define ΠiXi by:

• |ΠiXi| is the set of I-tuples (xi)i such that ∀i.xi ∈|Xi| and there exists a permission set S such that ∀i.supp(xi) ⊆S.

• π·(xi)i = (π·xi)i (the elementwise or pointwise action). Permutation orbits

Permutation orbits will serve us later in Definition 3.3.2 (free unknowns of a term).

If X is a nominal set then orb(X) is ‘X quotiented by the permutation action’.

Definition 2.4.6

If X is a permissive-nominal set define orb(X) by:

• If x ∈X then define its permutation orbit by orb(x) = {π·x | π ∈P}.

• |orb(X)| = {orb(x) | x ∈ X}.

• π·orb(x) = orb(x).

Lemma 2.4.7

• supp(orb(x)) = ∅. That is, orb(x) is equivariant (Definition 2.3.1).

• orb(x) = orb(y) if and only if y = π·x for some π.

Atoms-abstraction

Definition 2.4.8

Suppose X is a permissive-nominal set and Ai is a set of atoms. Define atoms-abstraction [Ai]X by:

[a]x = {(a, x)} ∪{(b, (b a)·x | b ∈Ai\supp(x)} |[Ai]X| = |[Ai]X| = {[a]x | a ∈Ai, x ∈|X|} π·[a]x = [π(a)]π·x
Lemma 2.4.9

1. [Ai]X is a permissive-nominal set.

2. [a]x=[a]x′ if and only if x=x′, for a∈Ai and x∈|X|.

3. [a]x=[a′]x′ if and only if a′∉supp(x) and (a′ a)·x=x′, for a, a′∈Ai and x, x′∈|X|.

Lemma 2.4.10

Suppose a function F from |A×X| to |Y| is equivariant and suppose ∀a, x.a ∉ supp(F(a, x)). Then there is a unique equivariant function ˆF from |[A]X| to |Y| such that ∀a, x.F ˆ([a]x) = F(a, x).

Proof

It suffices to show that if b ∉ supp(x) ∪ supp(F(a, x)) then F(b, (b a)·x) = F(a, x). By assumption a ∉ supp(F(a, x)), so (b a)·F(a, x) = F(a, x). The result follows by equivariance. ■

Here are some basic properties of support:

Lemma 2.4.11

• supp(a) = {a}.

• supp([a]x) = supp(x) \ {a}.

• supp((x1, . . . , xn)) = ⋃{supp(xi) | 1 ≤i ≤n}.

Proof

Proofs are as in [GP01] or [Gab11b]. ■

The fine design of PmsPrm

Studying PmsPrm (Definition 2.3.4) is not the point of this paper, but for the benefit of the interested reader we will discuss a few aspects of its behaviour.

• If P consists of finite permutations then PmsPrm is a Boolean topos, directly generalising the category of nominal sets (equivariant FM sets) from [GP01; Gab11b]. The proof proceeds much as in [Gab11b, Corollary 9.11].

• If P contains infinite permutations then PmsPrm is cartesian (has products) but is not necessarily cartesian closed (may not have exponentials). This is the fuzzy support observed in [Gab07b]; see [Gab07b, Lemma 21] for the concrete construction. This is reasonable, and it happens because it is possible to construct a function f on ω+ω which satisfies f(0) = 0 and f(i+1) = f(i) yet which is not a constant function (it returns 0 on finite cardinals and 1 on infinite ones).

• If P contains infinite permutations but we follow [DGM10] and take the notions of support in Definition 2.2.2 and equivariance to consider only finite permutations, then the category we obtain is a Boolean topos but we only have supp(x) ∩ nontriv(π) = ∅ implies π·x = x for finite π. In other words, an element can be fixed by all finite permutations and have empty support, but be shifted by some infinite permutation. Again, this is reasonable; it is no surprise that infinite permutations can ‘observe’ more than finite ones.

• If P contains infinite permutations and we work with presheaves (in essence, we lose the ‘unique least supporting set’ assumption in Definition 2.2.3), then we get a topos, though it is not Boolean.

In this paper we do not attempt to reason inside PmsPrm so we do not care whether it is a topos; and we do want the possibility of infinite permutations because these let us write nice algorithms and they give our logics some useful extra expressive power (see e.g. rule (IF) of Figure 2, Subsection 3.6, and Remark 9.2.4).

So we admit the possibility of infinite permutations in Definition 2.1.6, we let Definition 2.2.2 consider all π ∈P (even infinite ones), and we insist in Definition 2.2.3 that every x have a unique least small supporting set.

In another paper, another set of design decisions might be appropriate.

The reader who does not care about these considerations need not worry; they are all swept under the carpet henceforth.

2.5 Strong support

Strong support exists in nominal terms, though this is implicit. Consider in [UPG04] the ≈-suspension rule in Figure 2, and Lemma 2.8. We call this strong support, following [Tze07, Definition 1].

A possibly useful intuition is that an element x ∈ X has strong support when the atoms in its support occur in order (a dedicated theoretical study of this is in

[Gab07b]). Formally, the notion of strong support enters into the mathematics in this paper via Proposition 2.5.5, Lemma 3.4.6, and Lemma 7.4.4.

Definition 2.5.1

Suppose X is a permissive-nominal set. Say A ⊆A strongly supports x ∈|X| when π·x = x if and only if ∀a∈A.π(a) = a.

If x has some strongly supporting set, call x strongly supported. If every x ∈|X| is strongly supported then call X strongly supported.

Lemma 2.5.2

x ∈ X is strongly supported if and only if

∀π, π′.(π·x = π′·x ⇔(∀a ∈supp(x).π(a) = π′(a))).
Proof

From Definition 2.5.1 by considering π-1 ◦π′. ■

Example 2.5.3

• The pair (a, b) ∈A × A is strongly supported by {a, b}.

• The unordered pair {a, b} ⊆A with the pointwise permutation action (Definition 2.1.9) is not strongly supported, because (a b)·{a, b} = {a, b}.

• The infinite sequences [a1, a2, a3, . . .] in L from Definition 2.4.4 are strongly supported.

Definition 2.5.4

Suppose X and Y are permissive-nominal sets and X is strongly-supported. Suppose we are given the following data:

• For each x ∈|orb(X)| a fixed but arbitrary choice of representative Xx ∈x.

• For each x ∈|orb(X)| a choice of yx ∈|Y| such that supp(yx) ⊆ supp(Xx).

Define the equivariant extension F of this data, which is a function from |X| to |Y|, by:

F(π·Xx) = π·yx
Proposition 2.5.5

1. The equivariant extension is well-defined and is an equivariant function from |X| to |Y|.

2. Every equivariant f is an equivariant extension.

Proof

For the first part, by properties of orbits every x ∈|X| has the form π·Xx for some π and for precisely one Xx. This is equivariant by construction, if it is well-defined. So suppose π·Xx = π′·Xx. By assumption Xx is strongly supported so π(a) = π′(a) for every a ∈ supp(Xx). By assumption supp(yx) ⊆ supp(Xx). The result follows by the definition of support.

The second part is easy, noting that supp(F(x)) ⊆ supp(x) by Lemma 2.3.3. ■

3 THE SYNTAX OF NOMINAL TERMS

Nominal terms were introduced in [UPG04]. The development here is permissive, following [DGM10], but with some additional ingredients: We allow non-equivariant constant symbols and we parameterise over a set of unknowns which is a strongly-supported [Tze07].

Some example permissive-nominal terms are given in Example 3.2.4. See also how nominal terms are used in rewrite theories (Example 5.1.3), algebra (Example 7.1.3), and first-order logic (Subsection 10.1).

3.1 Signatures

Definition 3.1.1

A sort-signature is a tuple (A, B) of name and base sorts A ⊆N and B.

ν will range over name sorts; τ will range over base sorts.

A sort language is defined by

α ::= ν | τ | (α, . . . , α) | [ν]α.
Example 3.1.2

Example base sorts are: ‘λ-terms’, ‘formulae’, ‘π-calculus processes’, and ‘program environments’, ‘functions’, ‘truth-values’, ‘behaviours’, and ‘valuations’.

Base sorts τ are arbitrary; later on when we build denotations they will be populated by elements of arbitrary permissive-nominal sets, see Definition 7.3.1.

Examples of name sorts are ‘variable symbols’, ‘channel names’, ‘thread identi-fiers’, or ‘memory locations’. Name sorts ν are populated by the atoms we fixed in Definition 2.1.2 and which we used to build permutations and permissive-nominal sets.

Remark 3.1.3

(α, . . . , α) is a product sort and behaves as expected.

[ν]α is an atoms-abstraction sort; this is different. The behaviour of a term of sort [ν]α corresponds to ‘α-abstract a name of sort ν in a term of sort α’. This is binding without functions: we will use atoms-abstractions (Definition 2.4.8) to populate atoms-abstraction sorts.

Remark 3.1.4

In Definition 3.1.1 we insist that a name sort ν is a natural number; this is not necessary but it makes it easier for us to identify name sorts with sets of atoms from Definition 2.1.2, which are also indexed by numbers.

Definition 3.1.5

A (nominal) term-signature over a sort-signature (A, B) is a tuple (C, X, F, ar) where:

• C is a permissive-nominal set of constants.

• X is a strongly supported (Definition 2.5.1) permissive-nominal set of unknowns.

• F is a set of equivariant term-formers.

• ar assigns

– to each constant C ∈C a base sort τ which may we write sort(C),

– to each unknown X ∈X a sort α which we may write sort(X), and

– to each f ∈F a term-former arity (α)τ, where α and τ are in the sort-language determined by (A, B).

A (nominal terms) signature Σ is then a tuple (A, B, C, X, F, ar).

The support supp(X) of an unknown X ∈X is intuitively the atoms that may occur free in a term we substitute for that unknown, and A \ supp(X) is the atoms which may not occur free. See Proposition 3.4.3.

Notation 3.1.6

We may write ((α1, . . . , αn))τ just as (α1, . . . , αn)τ.

We write f : (α)τ for ar(f) = (α)τ and similarly we write P : α for ar(P) = α.

Example 3.1.7

Here are some examples of suitable X.

1. For each sort α and permission set S choose a disjoint countably infinite set of unknown symbols XS α, YS α, ...Define π·XS α = {(π′, XS α) | ∀a∈S.π(a) = π′(a)}. Let X = {π·XS α | all XS α, π} with permutation action π·(π′·XS α) = (π ◦π′)·XS α. Define ar(π·XS α) = α. Essentially this X was used in [DGM10].

2. For each sort α choose a disjoint countably infinite set of unknown symbols Xα, Yα, ...Define π·Xα = {(π′, Xα) | ∀a∈A<.π(a) = π′(a)}. Let X = {π·Xα | all Xα, π} with permutation action π·(π′·Xα) = (π ◦π′)·Xα. Define ar(π·Xα) = α.

3. Take X = (α, (a0, a1, a2, . . .)) where {ai | i ∈N} is a permission set and let X be the set of all possible X. Give this the pointwise permutation action π·X = (α, (π(a0), π(a1), . . .)) and define ar(X) = α. This X is mathematically simple, eliminating the need to take quotients over π.

4. Take X = {0, 1, 2, . . . } with the trivial action π·x = x, so every x ∈X has supp(x) = ∅. This example illustrates that our framework is general enough to include the possibility of unknowns ranging over closed elements (a possibility also mooted in [FG07, Subsection 9.2]). By adding further structure to X, further possibilities can be explored. See also [Gab11c] and [Gab12a].

In all cases it can be verified that X is strongly supported.

Remark 3.1.8

In the case that X the set of unknowns is as described in parts 1 or 2 of Example 3.1.7, orb(X) (Definition 2.4.6) may be identified with XS α or Xα respectively.

The X of part 1 above may be equivalent to that of X of part 2, if there exists π ∈P bijecting S with S \ {a} for a ∈S. This is a shift-permutation; see Definition 3.6.1 and subsequent discussion.

For the benefit of the reader familiar with ‘vanilla’ nominal terms as used e.g. in [UPG04; FG07; GM09a], Figure 1 gives a cheat sheet suggesting how concepts in those papers map to the ‘permissive’ context.

Figure 1: Cheat sheet relating ‘vanilla’ nominal terms concepts with ‘permissive’ onesVanilla PermissiveX Unknown with permission set A<a#X a ∉supp(X)a#r a ∉fa(r)∇⊢r →s or ∆⊢r = s r →s or r = sExtend freshness context shift-permutation (approx)Finite support Small support Figure 1: Cheat sheet relating ‘vanilla’ nominal terms concepts with ‘permissive’ ones
Example 3.1.9

A nominal terms signature for the λ-calculus would have one name sort ν, one base sort τ, and term-formers lam : ([ν]τ)τ, app : (τ, τ)τ, and var : (ν)τ. The set of constants is empty, and for unknowns we can consider Example 3.1.7.

Usually we assume ‘plenty’ of variable symbols. Definition 3.1.10 makes that formal:

Definition 3.1.10

Say that a signature Σ = (A, B, C, X, F, ar) has enough unknowns when for every sort α in (A, B) and every permission set S, the set {orb(X) | X ∈X, sort(X) = α, supp(X) = S} is infinite.

All the examples in Example 3.1.7 have enough unknowns.

3.2 Terms

Definition 3.2.1

For each signature Σ = (A, B, C, X, F, ar) (Definition 3.1.5) define (permissive-nominal) terms over Σ by:

(a∈Aν, ν∈A) a : ν(sort(C) = τ) C : τ(sort(X) = α) X : αr : α (ar(f) = (α)τ) f(r) : τr1 : α1 . . . rn : αn(r1, . . . , rn) : (α1, . . . , αn)r : α (a∈Aν, ν∈A) [a]r : [ν]α
Notation 3.2.2

We may write f((r1, . . . , rn)) as f(r1, . . . , rn).

Remark 3.2.3

Definition 3.2.1 is nominal abstract syntax: terms come pre-quotiented by α-equivalence by construction by virtue of our use of atoms-abstraction [a]r. That is, if a ∈Aν and r : α then [a]r is not a pair (a, r), it is a set {(a, r)} ∪ {(b, (b a)·r) | b ∈Aν \ supp(r)} (Definition 2.4.8).

Example 3.2.4

Recall the signature for the λ-calculus from Example 3.1.9. In that signature we can form terms as illustrated in the following table, where a : ν and X : τ:

a : ν This is not a λ-term.var(a) : τ If we want an atom to behave like a λ-term vari- able, we use var to ‘inject’ it into τ. This corre- sponds to ‘x’.[a]a : [ν]ν An atoms-abstraction. This is not a λ-term.[a]var(a) : [ν]τ An atoms-abstraction of a λ-term. This is not a λ-term.lam([a]var(a)) : τ This corresponds to ‘λx.x’.lam([a]app(X, var(a))) : τ An open nominal term. This corresponds to ‘λx.tx, for some t’. Depending on whether a ∉supp(X), we may add a side-condition ‘where x is not free in t’.
Lemma 3.2.5

Support and the permutation action are characterised on terms r as follows:

supp(a) = {a} supp(f(r)) = supp(r)supp(C) = supp(C) supp((r1, . . . , rn)) = ⋃1≤i≤n supp(ri)supp(X) = supp(X) supp([a]r) = supp(r)\{a}π·a = π(a) π·f(r) = f(π·r)π·C = π·C π·(r1, . . . , rn) = (π·r1, . . . , π·rn)π·X = π·X π·[a]r = [π(a)]π·r
Proof

By facts of the permutation action and Lemma 2.4.11. ■

Remark 3.2.6

Lemma 3.2.5 is important because it verifies that ‘support of r’ coincides with the usual definition of ‘free variables (atoms) of r’. This is false of nominal terms; for instance the support of the structure [a]X as constructed in

[UPG04] is {a}, and that of (a b)·X is {a, b}.

What makes Lemma 3.2.5 work is the very specific way in which we constructed our permissive-nominal terms syntax, so that it coincides with the nominal abstract syntax of [GP01]. In this sense, what Lemma 3.2.5 expresses is a unification (no pun intended) of the mathematics of [GP01] and [UPG04].

In Lemma 3.2.5 the clauses for C and X are uninformative, of course. This is because support and the permutation action are determined by the choice of C and X. If we assume further internal structure of C ∈C or X ∈X then we can be more specific: for instance in the case of part 1 of Example 3.1.7, fa(π·XS) = {π(a) | a ∈ S}.

Because of Lemma 3.2.5, we are entitled to use the following notation:

Notation 3.2.7

In the case of syntax r, we may write fa(r) for supp(r) and call this the free atoms of r.

Lemma 3.2.8

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

Proof

By a routine induction on r. ■

Lemma 3.2.9

If π(a) = π′(a) for all a ∈ fa(r) then π·r = π′·r. The reverse implication also holds, provided that all constant symbols in r are strongly supported.

Proof

The first part is immediate from Notation 3.2.7 and the definition of support in Definition 2.2.2.

The reverse implication is by a nominal abstract syntax induction on r. For the case of r = [a]r′ we α-convert a to be fresh so that a ∉ nontriv(π) ∪ nontriv(π′); by assumption 3 in Definition 2.1.6 we can do this. We then use part 2 of Lemma 2.4.9. The case of r = X ∈X uses the assumption of strong support in Definition 3.1.5.7

■

3.3 Free unknowns of a term

Remark 3.3.1

Defining a notion of ‘the free unknowns of r’ is not entirely evident.

Consider for example [a]X where a ∈ supp(X). If ‘X appears in [a]X’ is true then so is ‘(b a)·X appears in [a]X’ for any b ∉ supp(X), since [a]X = [b](b a)·X. We deal with this in Definition 3.3.2 using permutation orbits from Definition 2.4.6; we simply quotient out all permutations. We take a more refined look at this later in Remark 3.7.1.

Definition 3.3.2

Define (free) unknowns fU (r) by:

fU (a) = ∅ fU (f(r)) = fU (r)fU (C) = ∅ fU ((r1, . . . , rn)) = ⋃i fU (ri)fU (X) = {orb(X)} fU ([a]r) = fU (r)

By abuse of notation we write X ∈ fU (r) for orb(X) ∈ fU (r) and X ∉ fU (r) for orb(X) ∉ fU (r), and so forth.

Lemma 3.3.3

fU (r) is well-defined.

Proof

Using Lemmas 2.4.7 and 2.4.10. ■

Notation 3.3.4

Call a term r ground when fU (r) = ∅. Otherwise, call r open.

3.4 Substitutions

Remark 3.4.1

Substitutions are of course how unknowns ‘stand for’ terms. Somewhat later we will develop a denotational theory for nominal terms, and so valuations for unknowns will appear, in Definition 7.3.3. Between now and then, substitutions are king.

The permissive-nominal framework we work with allows us an elegant definition:

Definition 3.4.2

Suppose Σ is a signature. A substitution θ in Σ is an equivariant function from X to terms in Σ such that sort(θ(X)) = sort(X) always. θ will range over substitutions. Write id for the identity substitution mapping X to X always. It will always be clear whether id means the identity substitution or permutation.

The reader familiar with nominal terms will expect a ‘freshness’ condition on substitutions corresponding to ‘∇′ ⊢∇θ’, as in for example Equation (11) or Lemma 2.14 of [UPG04], or ‘fa(θ(X)) ⊆ supp(X)’ as in Definition 3.1 of [DGM10]. This follows immediately from equivariance:

Proposition 3.4.3

If θ is a substitution then ∀X∈X.fa(θ(X)) ⊆ supp(X).

Proof

Direct from Lemma 2.3.3. ■

Putting Propositions 3.4.3 and 2.5.5 together with a concrete X recovers the notion of substitution used in [DGM10]:

Lemma 3.4.4

If X is equal to example 1 of Example 3.1.7 then the construction in Definition 2.5.4 describes a 1-1 correspondence between substitutions and maps from unknowns XS α to terms t : α such that fa(t) ⊆S.

Definition 3.4.5

Suppose fa(t) ⊆ supp(X) and sort(t) = sort(X). Write [X:=t] for the atomic substitution equivariantly extending the assignment X↦ →t, so that

[X:=t](π·X) = π·t and[X:=t](Y ) = Y for all other Y.

By Proposition 2.5.5 we have:

Lemma 3.4.6

Definition 3.4.5 is well-defined. That is, if π·X = π′·X then π·t = π′·t.

Remark 3.4.7

The ‘moderated unknown’ π·X in Definition 3.4.5 is an artefact of our writing [X:=t] instead of a mathematically equal [π·X:=π·t] for some other π.

Since θ is equivariant its behaviour on π·X is already determined by its behaviour on X and so we could unambiguously specify [X:=t] succinctly as [X:=t](X) = t and [X:=t](Y ) = Y .

Definition 3.4.8

Define a substitution action on terms by:

aθ = a f(r)θ = f(rθ)Cθ = C (r1, . . . , rn)θ = (r1θ, . . . , rnθ)Xθ = θ(X) ([a]r)θ = [a](rθ)

Note that Xθ refers to θ acting on X as a term whereas θ(X) refers the value of the function θ at X. The substitution action is well-defined by Lemmas 2.4.10 and 2.4.11.

Remark 3.4.9

Famously, the nominal terms substitution is capturing [UPG04, Definition 2.13]. We spell out how this works in our permissive-nominal context: Suppose supp(X) is equal to a permission set S and a ∈S and b ∉S (where we assume appropriate sorts). Then:

• ([a]X)[X:=a] = [a]a. The a in the substitution [X:=a] has been captured by the [a]X.

• ([b]X)[X:=a] = [b]a.

• It is impossible to even ask what ([b]X)[X:=b] is equal to because [X:=b] is not even a substitution, since b ∉S. So b ∉S cannot be captured by a substitution [X:=b], because that substitution does not exist. This is no ad hoc restriction: by Proposition 3.4.3 it cannot exist.

• Also, [b](b a)·X = [a]X. By construction in Definition 3.4.5

([b](b a)·X)[X:=a] = [b](b a)·a = [b]b = [a]a. Also [X:=a] = [(b a)·X:=b] and ([b](b a)·X)[(b a)·X:=b] = [b]b.

That is, the choice of representative of [a]X and [X:=a] does not matter for capture to occur.

It is interesting to note that in our setting, [X:=a] is equivariant and that a ∉ supp([a]X). If a is fresh for both [X:=a] and [a]X, how can it be captured?

What allows a to get captured is the strong support property of X. Because X is strongly supported, we can think of it as ‘containing’ a list of its supporting atoms in some order, so that the a in [X:=a] is bound by supp(X) but in being bound it points to a ‘position’ in X.

Viewed from this interesting perspective, the nominal substitution action is not capturing at all: it is simply a compact way to present an ‘infinite raising’ (terminology from higher-order logic), or a de Bruijn index.

Lemma 3.4.10

π·(rθ) = (π·r)θ.

Proof

By a routine induction on r using equivariance. ■

Lemma 3.4.11

fa(rθ) ⊆ fa(r).

Proof

From Lemmas 2.3.3 and 3.4.10. ■

Lemma 3.4.12

rθ = rθ′ if and only if ∀X∈fU (r).θ(X) = θ′(X).

Proof

By a routine induction on r. We consider two cases:

• The case [a]r. Suppose θ(X) = θ′(X) for every X ∈ fU ([a]r). fU ([a]r) = fU (r) so by inductive hypothesis rθ = rθ′. The result follows from the definitions. The reverse implication is similar.

• The case X. Suppose θ(π·X) = θ′(π·X) for all π. Then taking π = id we have Xθ = θ(X) = θ′(X) = Xθ′. Conversely if Xθ = Xθ′ then using equivariance (Definition 3.4.2) θ(π·X) = θ′(π·X) for all π.

■

Remark 3.4.13

Recall from Definition 3.3.2 that we write X ∈ fU (r) for orb(X) ∈ fU (r). It might seem that the condition ∀X∈fU (r).θ(X) = θ′(X) in Lemma 3.4.12 would require checking θ(X) = θ′(X) for infinitely many X provided that fU (r) ≠ ∅. In fact, this is not the case: by equivariance of θ, we only need to check equality for one representative X of each permutation orbit: X ∈ orb(X) ∈ fU (r).

3.5 Composition and invertibility of substitutions

Definition 3.5.1

Define composition of substitutions θ1◦θ2 by

(θ1◦θ2)(X) = (θ1(X))θ2.
Lemma 3.5.2

(rθ)θ′ = r(θ◦θ′).

Proof

By induction on r. ■

Definition 3.5.3

Call θ invertible when there exists θ-1 such that θ◦θ-1 = θ-1◦θ = id.

Lemma 3.5.4

θ is invertible if and only if θ is a bijection on X the set of all unknowns. Furthermore, if θ is invertible then supp(θ(X)) = supp(X) always.

Proof

Substitution cannot make syntax smaller, or (by Lemma 3.4.11) make free atoms larger. ■

So an invertible θ must biject unknowns of a particular sort and permission set with other unknowns of that same sort and permission set. So, like atoms, we can rename unknowns to ‘be fresh’ (provided we have given ourselves enough of them). Invertible substitutions will be useful later, and they are also one manifestation of a more general framework of two-level nominal sets [Gab11c].

3.6 shift-permutations

The reader may be familiar with nominal freshness conditions a#X from [UPG04]. In that paper, a#X indicated that X should be substituted only for terms for which a is fresh.

In [UPG04; FG07], we might have to extend a freshness context in order to give ourselves more fresh atoms. This is what rules like (Fr) from [GM08c, Figure 2] or (fr) from [GM09a, Figure 2] do; see also [FG10] where the issue of extending nominal freshness contexts is made very explicit.

In principle, permission sets guarantee an infinite supply of fresh atoms, so the problem of extending a freshness context should not arise. But this may rely on oracular knowledge of what the permission set should be, which we might prefer not to assume. The choice of nominal permutation group P gives us the power to implicitly parameterise over this decision.

Suppose we have some X such that a ∈ supp(X) and we perhaps we are solving a unification problem and the information that a should be fresh for X has just been revealed by an algorithm; so we want to remove a from the permission set of X. This arises in the unification algorithm of Section 4.

Suppose alternatively we would like to make the permission set larger, e.g. if we know ∀X.φ and want to deduce φ[X:=t] where fa(t) ⊈ supp(X), or we have a rewrite rule X →X and want to deduce t →t where again fa(t) ⊈ supp(X). This arises in the nominal rewriting, algebra and permissive-nominal logic which we construct later.

This is where shift-permutations can help.

Definition 3.6.1

Call a permutation δ ∈P a shift-permutation when there exists a permission set S and atom a ∈S such that S \ {a} = δ·S. Say that a nominal permutation group P has shift-permutations when for every permission set S and atom a ∈A there exists a permutation π ∈P such that π·S = S\{a}.

Remark 3.6.2

Another way to read Definition 3.6.1 is that P has shift-permutations when, if S is a permission set and A is finite, then S \ A and S ∪A are permission sets. Stronger versions allowing infinite A are certainly imaginable.

Example 3.6.3

The nominal permutation group in part 2 of Example 2.1.7 has shift-permutations.

δi bijects A<i with A<i \ {f(0)}. Using swappings we can now generate a π to biject any permission set S with S\{a} for a ∈S. We give the concrete constructions below, culminating with Lemma 3.6.10.

For the rest of this subsection we work concretely with the nominal permutation group from part 2 of Example 2.1.7; the reader only interested in the high-level picture can skip this. Recall the bijections fi from integers to atoms from part 2 of Example 2.1.7. For simplicity drop the subscript i and consider just one set of atoms.

Notation 3.6.4

By abuse of notation write 0 for the atom f(0).

Definition 3.6.5

1. If a ∈A< then define δ-a by:

δ-a = (a 0) ◦δ ◦(a 0)

2. If b ∈A> then for some fixed but arbitrary choice of c ∈A> such that δ(c) = c (and so also c ∉A<), define δ+b by:

δ+b = (b 0) ◦(c b) ◦δ-1 ◦(c b) ◦(b 0)
Example 3.6.6

We illustrate δ-a and δ+b where a = f(-2) and b = f(3) and where we take c = b:

f(-6) f(-5) f(-4) f(-3) f(-2)f(-1) f(0) f(1) f(2) f(5) f(4) f(5) f(6)f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6)

We also consider the slightly more complex example of δ+d where d = f(4), and again we take c = f(3). We do this in three steps, where we illustrate δ-1, then (c d) ◦δ-1 ◦ (c d), and finally δ+d:

f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6)f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6)f(-6) f(-5) f(-4) f(-3) f(-2) f(-1) f(0) f(1) f(2) f(3) f(4) f(5) f(6)
Lemma 3.6.7

1. If a ∈A< then δ-a bijects A< with A< \ {a}.

2. If b ∈A> then δ+b bijects A< with A< ∪{b}.

Proof

For the first part, suppose a ∈A< . Then A< = (a 0)·A< . We reason as follows:

δ-a·((a 0)·A< ) = ((a 0) ◦δ ◦(a 0) ◦(a 0))·A<= ((a 0) ◦δ)·A< = (a 0)·(A< \{0}) = A< \{a}

Now suppose b ∈A> . It is easier to work with (δ+b)-1, to keep the parallel with the previous case. So A< ∪{b} = ((b 0)·A<) ∪{0}. We reason as follows:

(δ+b)-1·(((b 0)·A< )∪{0}) = ((b 0) ◦(c b) ◦δ ◦(c b) ◦(b 0))·(((b 0)·A< ) ∪{0}) Def. 3.6.5=(((b 0) ◦(c b) ◦δ ◦(c b) ◦(b 0))·((b 0)·A< ))∪{0} δ(c)=c=(((b 0) ◦(c b) ◦δ ◦(c b))·A< )∪{0}Fact=(((b 0) ◦(c b) ◦δ)·A< )∪{0}b, c ∉A<=(((b 0) ◦(c b))·(A< \{0}))∪{0} δ·A< =A< \{0}= (A< \{0}) ∪{0}b, c ∉A< \{0}= A<

■

Recall from Definition 2.1.10 that each permission set S has the form π·A< for some permutation π.

Definition 3.6.8

For each S make some choice of permutation πS such that S = π-1 S ·A<.8

Definition 3.6.9

Suppose S is a permission set and a ∈S and b ∉S. Then we define:

δS-a = π-1 S ◦δ-πS(a) ◦πSδS+b = π-1 S ◦δ+πS(b) ◦πS

The concrete details of the construction are only interesting insofar as they give us Lemma 3.6.10. Other permutations are possible, but we only need that one exists.

Lemma 3.6.10

1. δS-a bijects S with S\{a}.

2. δS+b bijects S with S∪{b}.

Proof

From Lemma 3.6.7. ■

Definition 3.6.11

Suppose S is a permission set and supp(X) = S. Suppose D is a finite list of atoms d1, . . . , dn and E is a finite list of atoms e1, . . . , en. Suppose {d1, . . . , dn} ⊆S and {e1, . . . , en}∩S = ∅. Then define δS-D and δS+E, and X-D and X+E by:

δS-[] = id δS-[d] = δS-dδS-d,D = δ(S\{d})-D ◦δS-dX-D = δsupp(X)-D·XδS+[] = id δS+[e] = δS+eδS+e,E = δ(S∪{e})+E ◦δS+eX+E = δsupp(X)+E·X
Lemma 3.6.12

Suppose S is a permission set. Suppose D and E are finite lists of atoms d1, . . . , dn and e1, . . . , en. Suppose {d1, . . . , dn} ⊆S and {e1, . . . , en}∩S = ∅.

Then δS-D bijects S with S\{d1, . . . , dn} and δS+E bijects S with S∪{e1, . . . , en}.

Proof

Using Lemma 3.6.10. ■

Corollary 3.6.13

S is a permission set if and only if S = (A< \A)∪B for some finite A ⊆A< and B ⊆A>.

Proof

If S is a permission set then by Definition 2.1.10 S = π·A< for some π and the result follows by a routine induction on the generators of π (swapping and δ; see part 2 of Example 2.1.7).

Conversely consider S = (A< \A)∪B. Let D be the atoms in A in some order, and E be the atoms in B in some order. Then we apply δS-D and then δ(S\A)+E and use Lemma 3.6.12. ■

Remark 3.6.14

The reader may be familiar with the de Bruijn shift function ↑ [ACCL91, Subsection 2.2]. This maps N to N\{0} by mapping j ∈N to j + 1 ∈N, and in doing so it ‘creates a fresh number’ 0. The reader familiar with presheaf techniques may know of a functor δ and arrow up, which work the same way, as exemplified in [FPT99, Section 1].

δi from part 2 of Example 2.1.7 is in the same spirit. It shifts ‘down’ instead of ‘up’, but δ-1 i shifts ‘up’.

Note that δ is invertible (↑ and up are not). This is consistent with the general preference of nominal techniques for using permutations where possible.

3.7 Occurrences

Remark 3.7.1

As discussed in Remark 3.3.1 we have to be careful if we wish to say ‘X appears in r’; this might not quite mean what we think it does.

For example if ‘X appears in [a]X’ where a ∈ supp(X) then also ‘(b a)·X appears in [a]X’ for any b ∉ supp(X). We dealt with this in Definition 3.3.2 by quotienting out all permutations.

But this is a little drastic. For instance, ‘(b a)·X appears in [a]X’ is not true for b ∈ supp(X); it is not the case that if ‘X appears in r’ then ‘π·X appears in r’ for any π.

We did not need to quotient out all permutations—only some of them—and so returning orb(X) in Definition 3.3.2 throws out more information than necessary.

Definitions 3.7.2 and 3.7.3 develop a more refined notion of occurrence, based on an intuition of ‘X appears in r under a list of abstractions D’. This will be useful later.

Definition 3.7.2

D will range over finite lists of distinct atoms. A (level 2) occurrence is a term of the form [D]X where []X is X and [a, D]X is [a][D]X.

Definition 3.7.3

Define the occurrences in r inductively by:

occ(a) = ∅ occ(f(r)) = occ(r)occ(C) = ∅ occ((r1, . . . , rn)) = ⋃ occ(ri)occ(X) = X occ([a]r) = {[a]x | x∈occ(r)}
Example 3.7.4

• X occurs in X.

• [a]X occurs in [a]X and also in [a](X, Y); so does [a]Y . X does not occur in [a]X or [a](X, Y).

• [a][b]X and [a][a]X occur in [a]([b]X, [a]X).

We write occurrences as [D]X for D a finite list of distinct atoms. Note that [a][a]X is an occurrence since it is equal to [a][b](b a)·X where b ∉ supp(X). This is an equality, not an equivalence imposed on terms after they are constructed, because of our use of atoms-abstraction (Definition 2.4.8) in syntax (Definition 3.2.1).

Rewrites, equations, and algebras

4 UNIFICATION

We want to write rewrite rules and equality axioms using nominal terms. In order to do this, we have to unify nominal terms (answer the question: “given r and s what substitutions θ make them equal?”). Unification makes unknowns ‘come alive’ and represent unknown terms.

Therefore, we now create a nominal unification algorithm. One notable property of nominal unification is that it has most general (principal) unifiers Theorem 4.4.6. Contrast this with higher-order unification, which does not [Dow01, Section 4]. This is one reason we say that the nominal approach to names and binding has a ‘first-order’ flavour.

The algorithm we use follows the spirit of [UPG04] but the design is different. In [UPG04] a solution to [a]X ?= [b]Y would be (b#X, [Y:=(b a)·X]); that is, the unification algorithm returns a pair of some freshness side-conditions and some equalities.9

Here, solutions are equalities only, without freshness conditions. The extra power resides in the notion of an shift-permutation (Definition 3.6.1).

A solution to [a]X = [b]Y where b ∈ supp(X) = supp(Y) would be

[X:=δ′·X, Y :=((b a) ◦δ′)·X]

where δ′ bijects supp(X) with supp(X) \ {b} (and by this bijection ‘internally freshens’ X with respect to b).

In another design [DGM10, Section 5] we use permission sets and fresh unknowns; a solution to [a]X = [b]Y where b ∈ supp(X) = supp(Y) is [X:=Z, Y :=(b a)·Z] where supp(Z) = supp(X)\{b}. Generating Z fresh requires us to solve problems in a context of ‘known unknowns’ V. This introduces a notion of state and sequentiality into the algorithm of [DGM10] which we avoid here.

Nothing forces us to feed the unification algorithm syntax with shift-permutations, even if the solutions it returns might mention them; similarly in [UPG04] we may obtain a solution with freshness side-conditions to a unification problem with only equalities. So use of shift-permutation in Definition 4.0.5 should not be read as a commitment to using them everywhere (though we do note empirically that shift seems to be useful elsewhere too).

The main definition of this section is Definition 4.1.7. The main result is Theorem 4.4.6.

Definition 4.0.5

Throughout this Section we fix some signature Σ and we work with syntax over Σ. We assume a nominal permutation group P with shift-permutations and a set of unknowns X such that every unknown is supported by a permission set (see e.g. part 2 of Example 3.1.7).

4.1 The unification algorithm

Definition 4.1.1

A (unification) equality is a unordered pair r?= s (so r?= s is identical to s?= r) such that:

1. sort(r) = sort(s).

2. If [D]X and [D′]π·X are both in occ(r) ∪ occ(s) then π is finite. So we exclude an equality like X?= δ·X, where δ is a shift permutation and nontriv(δ) ∩ supp(X) is not finite.

A (unification) freshness is an ordered pair a#?r.

Let ef range over equalities or freshnesses and define ef θ by:

• (r?= s)θ = (rθ?= sθ).

• (a#?r)θ = (a#?(rθ)).

A nominal unification problem Pr is a finite list ef1, . . . , efn.

We (ab)use standard sets notation and write ef ∈Pr as shorthand for ‘ef appears in the list Pr’.

Remark 4.1.2

Condition 2 in Definition 4.1.1 protects (?=X) in Figure 2 from an ‘infinite freshness explosion’, if nontriv(π) ∩ supp(X) is not finite. This condition exists implicitly in [UPG04], in the sense that all permutations there are finite. However, condition 2 is not only computationally motivated. Given constants C and D with supp(C) = ∅= supp(D), X?= δ·X may have solutions C and D but have no principal solution. We discuss the implications of this condition to nominal rewriting, at the end of Section 6.

Definition 4.1.3

If Pr = ef1, . . . , efn is a problem then define Prθ by:

Prθ = ef1θ, . . . , efnθ

Say θ solves Pr and call θ a solution to Pr when

rθ = sθ for every r?= s ∈Pr, anda ∉fa(rθ) for every a#?r ∈Pr.

Write Sol(Pr) for the set of solutions to Pr and call Pr solvable when Sol(Pr) is non-empty.

Recall the definition of θ◦θ′ from Definition 3.5.1.

Lemma 4.1.4

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

Proof

By unpacking Definition 4.1.3 and using Lemma 3.5.2. ■

Definition 4.1.5

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

We call rules (IF) and (IE) instantiating rules. We call all the other rules non-instantiating rules.

(?=a) a?= a, Pr =⇒ Pr(?=C) C?= C, Pr =⇒ Pr(?=f) f(r)?= f(s), Pr =⇒ r?= s, Pr(?=()) (r1, . . . , rn)?= (s1, . . . , sn), Pr =⇒ r1?= s1, . . . , rn?= sn, Pr(?=[]) [a]r?= [a]s, Pr =⇒ r?= s, Pr(?=X) X?= π·X, Pr =⇒ a1#?X, . . . , an#?X, Pr ({a1, . . . , an} = nontriv(π) ∩supp(X))(F) r?= X, Pr =⇒ a#?r, r?=X, Pr (a ∈fa(r)\supp(X))(F#) a#?r, Pr =⇒ Pr (a ∉fa(r))(Ff) a#?f(r), Pr =⇒ a#?r, Pr(F()) a#?(r1, . . . , rn), Pr =⇒ a#?r1, . . . , a#?rn, Pr(F[]) a#?[b]r, Pr =⇒ a#?r, Pr(IE) r?= X, Pr[X:=r]=⇒ Pr[X:=r] (X∉fU (r), fa(r)⊆supp(X))(IF) a#?X, Pr[X:=δX-a·X]=⇒ Pr[X:=δX-a·X]
Figure 2: Simplification rules for problems

In (IF) δX-a is some permutation bijecting supp(X) with supp(X) \ {a}. We can do this because we assumed shift-permutations in Definition 4.0.5.10

Write =⇒∗ for the transitive and reflexive closure of =⇒.

Remark 4.1.6

Compare Figure 2 with Figure 3 of [UPG04]. Note of (?=[]) that we do not consider the case [a]r?= [b]s. This is because α-equivalence is handled automatically by nominal abstract syntax, specifically by Definition 2.4.8. So α-renaming is pushed into the background (just as is usually the case for first-order syntax) and these rules are somewhat higher-level than those of [UPG04].

We also do not require a rule a#?[a]r, Pr =⇒Pr because the abstracted atom in [a]r is α-convertible; more formally, [a]r = [b](b a)·r for some/any fresh b (so b ∉ fa(r)).

Finally, in (?=X) we do not need to write π·X?= π′·X (though we could) because unknowns are just a strongly-supported nominal set. We know that nontriv(π) ∩ supp(X) is finite by a routine argument based on condition 2 of Definition 4.1.1. It is not hard to check that the instantiating rules (IF) and (IE) do indeed preserve these conditions—(IF) involves a shift permutation, but in a manner that is applied uniformly to the whole problem.

Definition 4.1.7

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

1. Rewrite Pr using the rules of Definition 4.1.5 where possible, with top-down precedence (so apply (?=a) before (?=f), and so on).

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

Remark 4.1.8

Note in Definition 4.1.7 that we apply each rule to the head of the list Pr. This is to prevent ‘unfair’ looping, e.g. repeatedly applying (F) to some equality r?= X wherever it appears in Pr.

Note also that the rule (F#) is equivalent—in the presence of the other rules—to three rules as follows:

(Fa) a#?b, Pr =⇒Pr(FC) a#?C, Pr =⇒Pr (a ∉supp(C))(FX) a#?X, Pr =⇒Pr (a ∉supp(X))
Proposition 4.1.9

The algorithm of Definition 4.1.7 always terminates.

Proof

It is not hard to generate an inductive quantity which is reduced by the reductions in Figure 2. ■

4.2 Examples of the algorithm

We assume the permutation group from part 2 of Example 2.1.7 and we recall the definition of X-D from Definition 3.6.9.

Example one (succeeds).

Suppose a, c ∈A< and d ∉A< . Take supp(X) = A< and suppose a term-former g. We apply the algorithm to {g([a]X, [a]a) ?= g([d]c, [d]d)}:

g([a]X, [a]a)?= g([d]c, [d]d) =⇒ (?=g), (?=())[a]X?= [d]c , [a]a?= [d]d =⇒ (?=[]), [a]X = [d](d a)·X(d a)·X?= c , [a]a?= [d]d[X:=c]=⇒ (IE)[a]a?= [d]d =⇒ (?=[]), [a]a = [d]dd?= d=⇒ (?=a)∅ Success, with [X:=c]

Example two (succeeds).

Suppose a, c ∈A< and b, d ∉A< . Take supp(X) = A< ∪{b, d}, supp(Y ) = A< ∪{f}, and supp(Z) = A<. Suppose a term-former f.

We apply the algorithm to {f([a]b, Z, X) ?= f([d]b, [a]a, Y)}:

f([a]b, Z, X)?= f([d]b, [a]a, Y ) =⇒ (?=f), (?=())[a]b?= [d]b , Z?= [a]a, X?= Y =⇒ (?=[]), [a]b = [d]bb?= b , Z?= [a]a, X?= Y =⇒ (?=a)Z?= [a]a , X?= Y[Z:=[a]a]=⇒ (IE)X?= Y=⇒ (F)b#?X , X?= Y[X:=X-b]=⇒ (IF)X-b?= Y=⇒ (F)d#?X-b , X-b?= Y[X-b:=X-b,d]=⇒ (IF)X-b, d?= Y =⇒ (F)f#?Y , X-b, d?= Y[Y :=Y -f]=⇒ (IF)X-b, d?= Y -f[Y -f:=X-b,d]=⇒ (IE)∅ Success, with [X:=X-b, d, Y :=X-b, d, Z:=[a]a]

Example three (fails). Take supp(X) = A<. We run the algorithm on {[a][b]X?= [a]X}:

[a][b]X?= [a]X =⇒ (?=[])[b]X?= X Failure

The algorithm fails because the precondition of rule (IE), X ∉ fU ([b]X) is not satisfied.

Example four (succeeds). Take supp(X) = A< and take a, b ∈A< . We run the algorithm on {X?= (a b)·X}:

X?= (a b)·X =⇒ (?=X)a#?X , b#?X[X:=X-a]=⇒ (IF)b#?X-a[X-a:=(X-a)-b]=⇒∅ Success, with [X:=(X-a)-b]

Later we will prove Theorem 4.4.6, which tells us that failure here implies that no solution to the unification problem exists.

4.3 Preservation of solutions

...under non-instantiating rules

Lemma 4.3.1

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

Proof

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

• The case (?=[]). Suppose Pr = [a]r?= [a]s, Pr′ and [a]r?= [a]s, Pr′ =⇒ r?= s, Pr′ by (?=[]). By Definition 3.4.8 and properties of equality, [a](rθ) = [a](sθ) if and only if rθ = sθ.

• The case (F()). Suppose Pr = a#?(r1, . . . , rn), Pr′ and suppose that a#?(r1, . . . , rn), Pr′ =⇒a#?r1, . . . , a#?rn, Pr′ by (F()). By Definition 3.4.8 and Lemma 3.2.5, a ∉ fa((r1, . . . , rn)θ) if and only if a ∉ fa(r1θ), ..., a ∉ fa(rnθ).

■

Lemma 4.3.2

Suppose θ(X) = θ′(X) for all X ∈ fU (Pr). Then θ ∈ Sol(Pr) if and only if θ′ ∈ Sol(Pr).

Proof

From Definition 4.1.3 it suffices to show that rθ = sθ if and only if rθ′ = sθ′, for every (r?= s) ∈Pr, and a ∉ fa(rθ) if and only if a ∉ fa(rθ′), for every (a#?r) ∈Pr. This is immediate using Lemma 3.4.12. ■

...under (IE)

Recall from Remark 3.4.7 the discussion of why we write π·X when we have chosen a representative element X of an equivalence class of unknowns under permutations.

Definition 4.3.3

Write θ−X for the substitution such that

(θ−X)(π·X) = π·X (θ−X)(Y ) = θ(Y ) for all other Y .

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

Theorem 4.3.4

If Xθ = sθ and X ∉ fU (s) then

θ = [X:=s]◦(θ−X).

That is:

θ(X) = X([X:=s]◦(θ−X)) andθ(Y ) = Y ([X:=s]◦(θ−X)).
Proof

We reason as follows:

(π·X)([X:=s]◦(θ−X)) = (π·s)(θ−X) Definition 3.4.8, Lemma 3.5.2= (π·s)θ X ∉fU (s), Lemma 3.4.12= (π·X)θ Assumption
Y ([X:=s]◦(θ−X)) = Y (θ−X) Definition 3.4.8, Lemma 3.5.2= Y θ Definition 4.3.3■

...under (IF)

Definition 4.3.5

Suppose θ is a substitution. Suppose a ∈ supp(X) and a ∉ fa(θ(X)). Let δX-a be a shift permutation bijecting supp(X) with supp(X) \ {a}.

Define a substitution θ[X-a:=X](X) by:

• (θ[X-a:=X])(π·X) = (π ◦δ-1 X-a)·θ(X). • (θ[X-a:=X])(Y ) = θ(Y ) for all other Y .

It is routine to verify that Definition 4.3.5 is well-defined and a substitution.

Theorem 4.3.6

Suppose a ∈ supp(X) and a ∉ fa(θ(X)). Then

θ = [X:=X-a]◦(θ[X-a:=X]).

That is:

θ(π·X) = ([X:=X-a]◦θ[X-a:=X])(π·X) andθ(Y ) = ([X:=X-a]◦θ[X-a:=X])(Y ).
Proof

We unpack definitions:

([X:=X-a]◦(θ[X-a:=X]))(π·X) = (π·(X-a))θ[X-a:=X]Definition 3.5.1= ((π◦δX-a)·X)θ[X-a:=X]Def. X-a= (π ◦δX-a ◦δ-1 X-a)·X Definition 4.3.5= π·X Group action

The result follows. ■

4.4 Simplification rewrites calculate principal solutions

Definition 4.4.1

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

Definition 4.4.2

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

Our main result is Theorem 4.4.5: the unification algorithm from Definition 4.1.7 calculates a principal solution.

Lemma 4.4.3

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

Proof

By Definition 4.4.1, θ′ exists such that Xθ2 = X(θ1◦θ′) always. Then:

X(θ◦θ2) = (Xθ)θ2Lemma 3.5.2= (Xθ)(θ1◦θ′) Lemma 3.4.12= X((θ◦θ1)◦θ′) Lemma 3.5.2■
Lemma 4.4.4

1. Suppose fa(s)⊆supp(X) and X ∉ fU (s). Write χ=[X:=s]. If Prχ=⇒Pr′ with (IE) then θ ∈ Sol(Pr) implies θ−X ∈ Sol(Pr′).

2. Suppose a ∈ supp(X). Write ρ=[X:=X-a]. If Prρ=⇒Pr′ with (IF) then θ ∈ Sol(Pr) implies θ[X-a:=X] ∈ Sol(Pr′).

Proof

1. Suppose Pr = X?= s, Pr′′ so that X?= s, Pr′′χ=⇒Pr′′χ. Now suppose θ ∈ Sol(Pr). By Theorem 4.3.4 χ◦(θ−X) ∈ Sol(Pr). By Lemma 4.1.4, θ−X ∈ Sol(Prχ). It follows that θ−X ∈ Sol(Pr′′χ) as required.

2. Suppose Pr = a#?X, Pr′′ and a ∈ supp(X) so that Prρ=⇒Prρ. Now suppose θ ∈ Sol(Pr). By Theorem 4.3.6 ρ◦θ[X-a:=X] ∈ Sol(Pr). By Lemma 4.1.4, θ[X-a:=X] ∈ Sol(Prρ) as required.

■

Theorem 4.4.5

If Prθ=⇒∗∅ then θ is a principal solution to Pr (Definition 4.4.2).

Proof

By induction on the path of Prθ=⇒∗∅.

• The empty path. So Pr = ∅ and θ = id. By Definition 4.4.1, id ≤θ′.

• The non-instantiating case. Suppose

Pr =⇒Pr′θ=⇒∗∅

where Pr =⇒Pr′ by a non-instantiating rule. By inductive hypothesis θ is a principal solution of Pr′. It follows from Lemma 4.3.1 that θ is also a principal solution of Pr.

• The case (IE). Suppose fa(r) ⊆ supp(X) and X ∉ fU (r). Write χ = [X:=r]. Suppose Pr = r?=X, Pr′′ so that

r?=X, Pr′′χ=⇒Pr′′χθ′′=⇒∗∅.

Further, consider any other θ′ ∈ Sol(Pr). By Lemma 4.4.4 (θ′−X) ∈ Sol(Pr′′χ) and by inductive hypothesis θ′′ ∈ Sol(Pr′′χ) and θ′′ ≤θ′−X. By Lemma 4.4.3, χ◦θ′′ ≤χ◦(θ′−X). By Theorem 4.3.4 χ◦(θ′−X) = θ′.

• The case (IF). Suppose a ∈ supp(X). Write ρ = [X:=X-a], so that

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

Further, consider any other θ′ ∈ Sol(Pr). By Lemma 4.4.4, θ′ [X-a:=X] ∈ Sol(Prρ) and by inductive hypothesis θ′′ ∈ Sol(Prρ) and θ′′ ≤θ′ [X-a:=X]. By Lemma 4.4.3, ρ◦θ′′ ≤ρ◦θ′ [X-a:=X]. By Theorem 4.3.6 ρ◦θ′ [X-a:=X] = θ′.

■

Theorem 4.4.6 (Correctness of algorithm).

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

Proof

If the algorithm succeeds we use Theorem 4.4.5. Otherwise, the algorithm generates an element of the form f(r) ?= g(s), a?= b, a#?a, a#?C where a ∈ supp(C), or X?= s where X ∈ fU (s) and s is not of the form π·X. By arguments on syntax and size of syntax, no solution to the reduced problem exists. It follows by Lemma 4.4.4 that no solution to Pr exists. ■

Definition 4.4.7

Fix terms r and s.

• Call nominal unification the problem of finding a θ to make rθ = sθ.

• Call nominal matching the problem of finding a θ to make rθ = s.

Corollary 4.4.8

Providing that equality of C (constants), X (unknowns), and P (permutations) are decidable, nominal unification and nominal matching over signatures using them are also decidable.

Proof

An algorithm for unification is sketched in Definition 4.1.7; furthermore by Theorem 4.4.6 it calculates a most general θ which represents all other solutions.

For matching, we substitute unknowns in s with fresh (non-equivariant) constants of the same sorts and permission sets—we extend the signature if we need to—and run the unification algorithm. We then replace the constants by the original unknowns.11 It is not hard to see that this calculates a most general matching solution. ■

Remark 4.4.9

The matching and unification algorithms might generate solutions with shift-permutations. If we prefer to eliminate them then—provided that X has enough unknowns (Definition 3.1.10)—we may do so by appending an invertible substitution (Definition 3.5.3) mapping each shifted δ·X in the solution to a fresh unknown Y such that supp(Y ) = δ·supp(X).

5 REWRITING

Nominal rewriting was the first logical system designed to study theories (sets of axioms, i.e. rewrite rules) over nominal terms. It was introduced by Fernández and the author in [FGM04; FG07]. Nominal terms allow us to express rewrite rules involving binding, like substitution and the λ-calculus (see Example 5.1.3).

The presentation of nominal rewriting here differs from that in [FG07], and is more concise. Partly this is optimisation, but this is also due to the permissive-nominal approach. We compare and contrast nominal rewriting from [FG07] with nominal rewriting here, in Subsection 5.6.

5.1 Rewrite rules

Definition 5.1.1

A rewrite rule in a signature Σ = (A, B, C, F, ar) is a pair of terms l →m in Σ such that sort(l) = sort(m) ∈B and fU (m) ⊆ fU (l). R will range over rewrite rules. A rewrite theory R = (Σ, Rew) is a pair of a signature Σ (Definition 3.1.5) and a (possibly infinite) set of rewrite rules Rew in Σ.

Notation 5.1.2

Write (l →m) ∈ R to mean ‘l and m are terms in Σ and (l →m) ∈ Rew’.

The notion of rewrite rule and rewrite theory in Definition 5.1.1 is much like the first-order case, but because of the ‘nominal’ aspects of our syntax we can handle names and binding.

Example 5.1.3

Here are some example rewrite theories:

• nrSUB expresses the usual capture-avoiding substitution action on λ-calculus terms.

Let Σ have a base sort τ and the following term-formers:

sub : ([ν]τ, τ)τ lam : ([ν]τ)τ app : (τ, τ)τ var : (ν)τ

Rewrite rules are as follows:

(var→) var(a)[a↦→X] →X(var→′) var(b)[a↦→X] →var(b)(lam→) lam([a]X)[b↦→Y ] →lam([a](X[b↦→Y ])) (a∉supp(Y ))(app→) app(X, X′)[b↦→Y ] →app(X[b↦→Y ], X′[b↦→Y ])

Here and in the next example we sugar sub([a]r, t) to r[a↦→t]. Every permission set contains b and every permission set contains a except for supp(Y), as indicated above.

• nrLAM extends the previous theory with two more rewrites:

(β→) (λ[a]Z)X →Z[a↦→X](η→) λ[a](Y a) →Y (a∉supp(Y ))

Sugar lam(r) to λr, app(r, s) to rs, and var(a) to a. We anticipate Subsection 5.2 and sketch how one might rewrite (λ[b](λ[a]ab))a to λ[a′]a′a:

(λ[b](λ[a]ab))a →(λ[a]ab)[b↦→a] = (λ[a′]a′b)[b↦→a] →λ[a′]((a′b)[b↦→a]) →∗λ[a′]a′a

5.2 Rewrite steps

Definition 5.2.1

Define the terms s in which X occurs only once by:

s ::= π·X | [a]s | f(r1, . . . , ri−1, s, ri+1, . . . , rn) (X ∉fU (r1), . . . , fU (ri−1), fU (ri+1), . . . , fU (rn))

A position P is a pair (s, X) of a nominal term and an unknown X which occurs only once in s.

Our notion of position is also sometimes called a context; the idea goes back to at least [FH92].

In Definition 5.2.1, π·X denotes an unknown in the same permutation orbit as X.

Notation 5.2.2

If P = (s, X) is a position write supp(P) for supp(X) and sort(P) for sort(X).

If sort(r) = sort(P) and fa(r) ⊆ supp(P) (so that [X:=r] is a substitution) write P[r] for s[X:=r].

Definition 5.2.3

The one-step rewrite relation rR−→s is the least relation such that for every (l →m) ∈ R, position P, and substitution θ, if sort(r) = sort(P) and fa(lθ) ∪ fa(mθ) ⊆ supp(P) (so that P[lθ] and P[mθ] are well-defined) then

P[lθ]R−→P[mθ].

The multi-step rewrite relation rR−→∗s is the reflexive transitive closure of the one-step rewrite relation.

We consider decidability and complexity of the rewrite relation in Section 6.

Example 5.2.4

Let T have one name sort ν, one base sort τ, one term-former triv and one axiom triv(a) → triv(b).

Then triv(a) → triv(b) but also (using positions (π·X, X) for any π) triv(b) → triv(a) and triv(a′) → triv(b′) for any pair of distinct atoms a′ and b′.

Thus atoms in rewrite rules range over ‘any atom’ analogously to how unknowns in rewrite rules range over ‘any term’.

Example 5.2.5

Recall the rule (η→) = (λ[a](Y a) →Y) where a ∉ supp(Y) from Example 5.1.3. Suppose also b ∉ supp(Y).

1. To deduce λ[a](ba) →b we take P = ((b c)·Y, Y) for some c ∈ supp(Y) and we take θ = [Y :=c].

2. To deduce λ[a′](ba′) →b for any other a′ we also take P = ((b c)·Y, Y) and θ = [Y :=c]. This is because λ[a′](ba′) and λ[a](ba) are the same term (Lemma 2.4.9).

3. To deduce λ[a](Y a) →Y we take P = (Y, Y) and θ = id.

4. Suppose supp(Y ′) = supp(Y) ∪{a}. Suppose we have shift-permutations so there exists a permutation, write it δY ′-a, bijecting supp(Y ′) with supp(Y). To deduce λ[a](Y ′a) →Y ′ we take P = ((δY ′-a)-1·Y, Y) and θ = [Y :=δY ′-a·Y ′]. Without shift we cannot deduce λ[a](Y ′a) →Y ′; we can still deduce λ[a](Y a) → Y .

5. We cannot deduce λ[a](aa) →a, because [Y :=a] is not a substitution: no function mapping Y to a can be equivariant, since (b a)·Y = Y but (b a)·a = b ≠ a (also a ∉ supp(Y): see Proposition 3.4.3).

6. A rewrite X →X only entails rewrites for t with fa(t) ⊆π·supp(X) for some π. With shift, the effect of this may be that we can deduce t →t from X →X for any t. We make no claim to there being a ‘right’ or ‘wrong’ answer here: the issue is purely a design question of how much expressivity we want permutations to have. Our results are parameterised over this choice.

Definition 5.2.6

• Call R locally confluent when rR−→s1 and rR−→s2 implies there exists some s′ such that s1R−→∗s′ and s2R−→∗s′.

• Call R confluent when rR−→∗s1 and rR−→∗s2 implies there exists some s′ such that s1R−→∗s′ and s2R−→∗s′.

5.3 Peaks, critical pairs, joinability

We now begin to investigate criteria for deducing confluence of nominal rewrite systems. Our first observation is that things are not quite as simple as in first-order rewriting [BN98, Section 6.2]: by Lemma 5.3.5, trivial critical pairs are not always joinable.

Definition 5.3.1

Write r →s1, s2 when r →s1 and r →s2 and call this a peak. Call this peak joinable when there exists a t such that s1 →∗t and s2 →∗t.

So R is locally confluent when every peak is joinable.

Definition 5.3.2

Consider two rewrite rules R1 = (l1 →m1) and R2 = (l2 → m2). Call R1 a copy of R2 when there exists an invertible substitution θ such that (l2θ →m2θ) = R1.

Clearly, if R1 is a copy of R2 then R2 is also a copy of R1. Furthermore:

Lemma 5.3.3

If R1 and R2 are copies of the same rule then lR1−→m if and only if lR2−→m.

Proof

Unpacking Definition 5.2.3 and exploiting the existence of an inverse θ-1. ■

Definition 5.3.4

Suppose that Ri = (li →mi) for i = 1, 2 and fU (R1) ∩ fU (R2) = ∅. Suppose l1 = P[l′ 1] for some l′ 1, and suppose l′ 1?= l2 has a principal solution θ. Call the pair (m1θ, P[m2]θ) a critical pair.

Call (m1θ, P[m2]θ) trivial when at least one of the following hold:

1. P = (π·X, X) and R1 and R2 are copies of the same rule.

2. l′ 1 = X for some unknown X.

Lemma 5.3.5

Peaks that are instances of trivial critical pairs, are not always joinable.

Proof

It suffices to provide a counterexample. Fix term-formers 0 and f and take R1 = (0 →a) and R2 = (X → f(a)) where a ∉ supp(X).

There is a critical pair (a, f(a)) between R1 and R2.

Also, 0 R1−→a and 0 R2−→ f(a) and it is a fact that this peak cannot be joined—we ‘want’ to close this peak by rewriting a to f(a) using R2, but the fact that a ∉ supp(X) blocks this. ■

5.4 Uniform rewriting

The proof of Lemma 5.3.5 suggests a simple cure:

Definition 5.4.1

Call a rule R = (l →m) uniform when

fa(m) ⊆fa(l).

Call a rewrite theory R uniform when every R ∈ R is uniform.

Definition 5.4.1 mirrors the condition in Definition 5.1.1 that fU (m) ⊆ fU (l), but for atoms instead of unknowns. This condition is sufficient to obtain Theorem 5.4.7, which is a nominal rewriting version of the well-known critical pair lemma from first-order rewriting [BN98, Theorem 6.2.4].

Example 5.4.2

Let R have one name sort ν, one base sort τ, two term-formers triv : (ν)τ and abs : ([ν]τ)τ, and rewrite rules

triv(a) →triv(a) triv(a) →triv(b) abs([a]X) →X.

fa(triv(a)) ⊆ fa(triv(a)) and fa(triv(b)) ⊈ fa(triv(a)). Also fa(X) ⊈ fa(abs([a]X)) if and only if a ∉ supp(X).

So the first rule is uniform, the second is not, and the third is uniform if and only if a ∉ supp(X).

The rewrite rules of nrSUB and nrLAM in Example 5.1.3 are uniform.12

Lemma 5.4.3

If fa(m) ⊆ fa(l) then fa(P[m]) ⊆ fa(P[l]).

Proof

Routine induction using Lemmas 3.2.8 and 3.2.5. ■

Corollary 5.4.4

R = (l →m) is uniform if and only if ∀r,s.(rR−→s ⇒ fa(s) ⊆ fa(r)).

Proof

From Lemmas 3.2.8 and 3.4.11. ■

Lemma 5.4.5

Suppose R = (l →m) is uniform and X ∉ fU (R). Suppose θ(X) = lθ. Specify θ′ by θ′(π·X) = π·(mθ) and θ′(Y ) = θ(Y). Then rθ →∗rθ′ for any r.

Proof

θ′ is a substitution by Lemmas 3.4.11 and 3.2.8. The result follows by a routine induction on r. ■

Because of Lemma 5.3.3, we can be relaxed about the particular (orbits of) unknowns that are used in a rewrite rule, if we only care about the rewrites that they generate. We do this in Theorems 5.4.6 and 5.4.7. This can always be made formal by inserting invertible ‘freshening’ substitutions as appropriate.

Theorem 5.4.6

If a rewrite theory R (Definition 5.1.1) is uniform then peaks that are instances of trivial critical pairs, are joinable.

Proof

Consider two rules Ri = (li →mi) ∈ R for i = 1, 2. Taking copies if necessary, suppose fU (R1) ∩ fU (R2). Suppose they have a critical pair (m1θ, P[m2]θ). That is, there exists l′ 1 such that l1 = P[l′ 1] and θ is a principal solution to l′ 1?= l2.

There are two cases:

• The case P = (π·X, X) and R1 and R2 are copies of the same rule l →m. The peak we want to join is l1θ = π·l2θ →m1θ, π·m2θ, where the rules l1 →m1 and l2 →m2 are identical aside from their free unknowns which are renamed disjoint. We use Lemma 3.4.12 and the assumption in Definition 5.1.1 that fU (m) ⊆ fU (l).

• The case of (m1θ, P[m2]θ) where l1 = P[X] and θ(X) = l2. Specify θ′ by θ′(π·X) = π·m2 and θ′(Y ) = θ(Y) for all other Y ; note that θ′ is a substitution since fa(m2) ⊆ fa(l2) by uniformity and fa(l2) ⊆ supp(X) by our assumption that θ is a substitution. By Lemma 5.4.5 m1θ →∗m1θ′. By definition P[m2]θ = l1θ′R1−→m1θ′, so we have joined the peak.

■

Theorem 5.4.7

Suppose all non-trivial critical pairs of R are joinable and suppose R is uniform. Then R is locally confluent.

Proof

Suppose rR1−→s1 and rR2−→s2. Write P1 and P2 for the positions at which the two rewrites occur. Taking copies if necessary, suppose fU (R1) ∩ fU (R2) = ∅.

If P1 and P2 identify distinct subterms of r then local confluence holds by a standard diagrammatic argument (see for instance [BN98]).

Otherwise it must be that P2 = (P1[P], X) for some position P; that is, P2 identifies a point in r beneath the point identified by P1 (or the symmetric case that P1 = (P2[P], X), which is similar and we elide). There are now three possibilities:

1. X in P2 replaces an unknown in r. This is an instance of a trivial critical pair; we use Theorem 5.4.6.

2. P = (π·X, X) and R1 and R2 are copies of the same rule. Then again this is an instance of a trivial critical pair and we use Theorem 5.4.6.

3. Otherwise, this is an instance of a non-trivial critical pair at it may be joined using our assumption that non-trivial critical pairs are joinable.

■

Definition 5.4.8

Call a rewrite system R terminating when all rewrite sequences are finite. Call a term r a normal form (with respect to a rewrite system R) when ∀s.¬(rR−→s), that is, when r does not R-rewrite to anything.

Example 5.4.9

It can be proved that nrSUB in Example 5.1.3 is terminating. nrLAM (famously) is not terminating, because of (β↦→).

Corollary 5.4.10

Suppose R is terminating, uniform, and suppose non-trivial critical pairs in R are joinable. Then:

1. R is confluent.

2. If r →∗s and r →∗s′ and s and s′ are normal forms, then s = s′.

5.5 Orthogonal rewrite systems

We now treat another standard criterion in rewriting: orthogonality [DJ89; BN98]. By Theorem 5.5.7 orthogonality implies not only local confluence, but the stronger property of confluence (Definition 5.2.6). The proof is not direct: it turns out that it is easier to consider an auxilliary parallel reduction relation ⇒ (Definition 5.5.4). The reflexive transitive closure of ⇒ is equal to that of → (Lemma 5.5.5), but ⇒ allows (intuitively) multiple reductions provided that they do not occur ‘one after the other, in the same position’. This is the kind of multiple reduction generated in the second case of the proof of Theorem 5.4.6, when we rewrite m1θ to m1θ′.

Definition 5.5.1

Call R = (l →m) left-linear when each unknown occurring in l occurs only once (Definition 5.2.1).

For example f(X) → g(X, X) is left-linear but g(X, X) → f(X) and g(π·X, x) → f(X) are not. Note that (a, a) →a is left-linear.

Definition 5.5.2

Call R orthogonal when every R ∈ R is uniform and left-linear, and all critical pairs are trivial.

(Note that we insist that R is uniform, as well as the standard condition that it be left-linear.)

Definition 5.5.3

Suppose R = (l →m). Write rR→ϵ s when rR−→s and the rewrite occurs at a position P = (π·X, X). We say that the rewrite with R occurs at root position.

Expanding Definition 5.5.3, rR→ϵ s when there exists θ and π such that r = π·(lθ) and s = π·(mθ). For example: if R = (a →a) then aR→ϵ a but not [a]aR→ϵ [a]a.

Definition 5.5.4

We define a parallel reduction relation ⇒ by the rules in

Figure 3.

Lemma 5.5.5

r →∗s if and only if r ⇒∗s.

Proof

By routine inductions. ■

Lemma 5.5.6

If R is orthogonal then ⇒ is confluent.

Proof

We prove by induction on the derivation of r ⇒s that a stronger property holds, often called the diamond property: for all s′ if r ⇒s′ then there exists some

s′′ such that s ⇒s′′ and s′ ⇒s′′. From this, confluence easily follows by a standard diagrammatic argument.

We consider a selection of cases:

• The derivations of r ⇒s and r ⇒s′ both end in (⇒f). We use the inductive hypotheses and (⇒f).

• The derivation of r ⇒s ends in (⇒f) and that of r ⇒s′ ends in (⇒f′). So ri ⇒si and ri ⇒s′ i for 1 ≤i ≤n, and f(s′ 1, . . . , s′ n) = π·(lθ) R→ϵ π·(mθ) for some π and R = (l →m) ∈ R. By inductive hypothesis there exist s′′ i such that si ⇒s′′ i and s′ i ⇒s′′ i. We now proceed as illustrated and explained below:

f(r1, . . . , rn) f(s′ 1, . . . , s′ n)=π·(lθ)Rϵπ·(mθ)f(s1, . . . , sn)f(s′′ 1, . . . , s′′ n)= π·(lθ′)Rϵπ·(mθ′)

Either l is an unknown X or the rewrite f(s′ 1, . . . , s′ n) ⇒ f(s′′ 1, . . . , s′′ n) takes place in the substitution θ. If l is an unknown then by uniformity we may rewrite f(s′′ 1, . . . , s′′ n) using R and close the diagram by rewriting corresponding instances of θ(X) in π·(mθ). Otherwise, by uniformity there is a substitution θ′ such that θ(X) ⇒θ′(X) for every X and f(s′′ 1, . . . , s′′ n) = π·(lθ′). Rules are also left-linear so R still applies to π·(lθ): f(s′′ 1, . . . , s′′ n) R→ϵ π·(mθ′) and therefore f(s1, . . . , sn) ⇒ sθ′ by (⇒f′) for R.

The other cases are no harder. ■

r1 ⇒s1 · · · rn ⇒sn(⇒f)f(r1, . . . , rn) ⇒f(s1, . . . , sn) r1 ⇒s1 · · · rn ⇒snf(s1, . . . , sn)R→ϵ s′(⇒f′)f(r1, . . . , rn) ⇒s′s ⇒t(⇒abs)[a]s ⇒[a]tr ⇒s [a]sR→ϵ s′(⇒abs′)[a]r ⇒s′(refl)r ⇒raR→ϵ s′(⇒a′)a ⇒s′XR→ϵ s′(⇒X′)X ⇒s′
Figure 3: Parallel reduction relation
Theorem 5.5.7

If a theory R is orthogonal (Definition 5.5.2) then R is confluent (Definition 5.2.6).

Proof

If the uniform rewrite system has only left-linear rules and only trivial critical pairs, then ⇒ is confluent by Lemma 5.5.6. It follows that ⇒∗ is confluent. By Lemma 5.5.5 the result follows. ■

5.6 Nominal rewriting with freshness contexts versus permissive-nominal rewriting

As mentioned in the introduction to this Section, the presentation of this paper differs from that of [FG07] in being permissive-nominal.

For clarity, let us call the nominal rewrite framework from [FG07] ‘System ∇’ and the nominal rewrite framework here ‘System S’.

In system ∇ a rewrite rule takes the form ∇⊢t →u where ∇ is a set of assumptions a#X called a freshness context. X is an unknown. This is not typed by a permission set; freshness information is given by ∇.

Here are (λ→) from Example 5.1.3, and how it would look in System ∇:

System S lam([a]X)[b↦→Y ]→lam([a](X[b↦→Y ])) (a∉supp(Y ))System ∇ a#Y ⊢lam([a]X)[b↦→Y] →lam([a](X[b↦→Y]))

a ∉ supp(Y) is a fact (we must choose Y so that this is true). It does not matter which permission set we give Y because using δ and swappings we can build a π to map supp(Y) to every other permission set π·supp(Y)—which will contain π(a).

Conversely a#Y is a freshness condition. It directly controls the terms to which we may instantiate Y; they must not contain a free. Here we attain this effect using Proposition 3.4.3.

Freshness conditions are elementary: they mean what they say and what they mean be quickly understood. Permission sets are still finitely representable, but somewhat harder to understand. So from the point of view of keeping a gentle learning curve, System ∇ may be preferable to System S.

However, System S rewards us with some advantages: we can use nominal abstract syntax and the freshness conditions which must be explicitly stated (repeatedly) in [FG07] are handled in the background by equivariance of substitutions (as Proposition 3.4.3 makes formal).

This also has some effects on mathematical properties. In System ∇ from [FG07] it was not in general the case that if ∇⊢r ≈α r′ and ∇⊢rR−→s then ∇⊢r′R−→s (see the end of Subsection 5.2 in [FG07]). It was also not in general the case that nominal rewriting coincides with nominal algebra (Section 7), essentially because any fixed freshness contexts might not be ‘big enough’. Fernández and the author wrote a paper on how to adjust for this [FG10]. In a permissive-nominal context, these issues do not arise in the first place.

This author’s feeling is that nominal-terms-with-freshness-contexts and permissive-nominal terms can be considered as essentially the same thing. However, if our goal is to prove theorems then we get closer to what is ‘really going on’ via the permissive-nominal presentation.

6 CLOSED TERMS

Equivariant unification—the problem of finding θ and π such that π·(rθ) = sθ—is NP complete [Che04; Che10]. The same applies to corresponding matching problems. This matters to us because the rewrite relation in Definition 5.2.3 is equivariant; to determine whether r rewrites with a rule (l →r), we must solve an equivariant matching problem.

Fernández and the author introduced a notion of closed term such that for closed terms, equivariant matching/unification coincides with ‘ordinary’ matching/unification

[FG07]. That is, for closed terms we can throw away the π.

We now develop corresponding definitions and results. The definitions and proofs in this paper are significantly different from those in [FG07].13

6.1 The definition

Definition 6.1.1

Define explicit atoms ea(r) inductively by:

ea(a) = {a} ea(C) = supp(C) ea(X) = ∅ea(f(r)) = ea(r) ea((r1, . . . , rn)) = ⋃ ea(ri) ea([a]r) = ea(r)\{a}
Remark 6.1.2

Intuitions for ea(r) versus fa(r) are as follows:

• The explicit atoms of r are the atoms that actually appear in r (unbound). That is, we can read ‘a ∈ ea(r)’ as ‘a appears in r’.

• The free atoms of r are the atoms that can appear in rθ for some θ.

For instance, ea(X) = ∅≠ supp(X) = fa(X).

This is an intuition, not a fact. fa(r) = ⋃θ ea(rθ) is not true in general (but see Lemma 6.1.5). For instance in a signature with one base sort τ and no term formers, terms containing atoms simply do not populate the sort τ.

Recall the notion of occurrences occ(r) from Definition 3.7.3.

Notation 6.1.3

Write π·occ(r) = {π·x | x ∈ occ(r)}. Also if D = [d1, . . . , dn] and S is a permission set define S \ D = S \ {d1, . . . , dn}.

Lemma 6.1.4

ea(π·r) = π·ea(r) and occ(π·r) = π·occ(r). In addition, ea(r) ⊆ ea(rθ).

Proof

By routine inductions on r. ■

Lemma 6.1.5

fa(r) = ea(r) ∪⋃{supp(x) | x ∈ occ(r)}.

As an easy corollary using Lemma 3.2.5, fa(r) = ea(r) ∪⋃{supp(X) \ D | [D]X ∈ occ(r)}.

Proof

By a routine induction on r. We consider one case:

• The case [a]r. Suppose fa(r) = ea(r) ∪⋃{supp(x) | x ∈ occ(r)}. By definition fa([a]r) = fa(r)\{a}, and ea([a]r) = ea(r)\{a} and occ([a]r) = {[a]x | x ∈ occ(r)}. The result follows by an easy sets calculation.

■

Definition 6.1.6

Call r fa-functional when if [D1]X ∈ occ(r) and [D2]X ∈ occ(r) then fa([D1]X) = fa([D2]X) (equivalently, when D1 and D2 contain the same atoms but not necessarily in the same order).

Definition 6.1.7

Call r closed when r is fa-functional and ea(r) = ∅.

Example 6.1.8

• a is not closed (ea is non-empty).

• X is closed, so note that ‘closed’ does not mean ‘fU (r) = ∅’. Our terminology is consistent with [FG07] and the subsequent literature.

• ([a]X, X) is not closed (occ is not fa-functional).

• [a](X, a) is closed.

Lemma 6.1.9

Suppose ea(r) = ∅. Then π·(rθ) = rθ′ if and only if π·(([D]X)θ) = ([D]X)θ′ for every [D]X ∈ occ(r).

Proof

By a routine induction on r. ■

Theorem 6.1.10

r is closed if and only if

∃S.fa(r) ⊆S ∧∀π, θ.π·fa(rθ) ⊆S ⇒∃θ′.π·(rθ) = rθ′.
Proof

Suppose there is a permission set S ⊇ fa(r) such that if π·fa(rθ) ⊆S then there exists θ′ such that π·(rθ) = rθ′. There are two things to prove:

• ea(r) is empty. Suppose there exists a ∈ ea(r). Pick b ∈S \ ea(r). By assumption taking θ = id there exists θ′ such that (b a)·(rθ) = rθ′. By Lemma 6.1.4 ea((b a)·r) = (b a)·ea(r) ∌a and a ∈ ea(r) ⊆ ea(rθ′), a contradiction.

• occ(r) is fa-functional. Consider [D1]X and [D2]X in occ(r); choose Di such that Di ∩ fa(r) = ∅ for i = 1, 2. Suppose there exists a ∈ fa([D2]X) \ fa([D1]X), and choose any b ∈ fa([D1]X) (since supp(X) is infinite and D1 is finite, such a b exists). By Lemma 6.1.5 a, b ∈ fa(r) so by assumption taking θ = id there exists θ′ such that (b a)·r = rθ′. We proved above that ea(r) = ∅, so by Lemma 6.1.9 (b a)·[D1]X = ([D1]X)θ. By Lemma 3.2.8 a is free in the left-hand side, and by Lemma 3.4.11 a is not free in the right-hand side; a contradiction.

Suppose occ(r) is fa-functional and ea(r) = ∅ and choose some permutation π and substitution θ.

If occ(r) = ∅ then by Lemma 6.1.5 fa(r) = ∅ so by Lemmas 3.2.9 and 3.4.12 π·(rθ) = r and rθ′ = r, so there is nothing to prove.

Otherwise take S = fa(r). For every element of in occ(r) make a fixed but arbitrary choice of representation as [D]X where the atoms in D are disjoint from the atoms in nontriv(π). We take θ′ to equivariantly extend this choice (Definition 2.5.4), so we map π′·X to (π′◦π)·θ(X) for the choice of representing X above, and otherwise to map Y to Y . Using Proposition 2.5.5 this is a substitution and π·(([D]X)θ) = ([D]X)θ′ for every [D]X ∈ occ(r). We use Lemma 6.1.9. ■

6.2 Closed rewrite rules

Definition 6.2.1

Call a rewrite rule l →m closed when (l, m) is closed.

Example 6.2.2

Let R have one name sort ν, one base sort τ, two term-formers triv : (ν)τ and abs : ([ν]τ)τ, and rewrite rules

triv(a) →triv(a) triv(a) →triv(b) abs([a]X) →X.

The terms triv(a) and triv(b) are not closed; the terms abs([a]X) and X are closed. The terms (triv(a), triv(a)) and (triv(a), triv(b)) are not closed. The term (abs([a]X), X) is closed if and only if a ∉ supp(X). So the first two rules are not closed and the third is closed if and only if a ∉ supp(X).

The rewrite rules of nrSUB and nrLAM in Example 5.1.3 are closed.

Recall that uniform rules have good properties like Theorems 5.4.7 and 5.5.7. Closed rules inherit these good properties, because:

Theorem 6.2.3

If R = (l →m) is closed then it is uniform.

Proof

By assumption fU (m) ⊆ fU (l). Also (l, m) is fa-functional; it follows that occ(m) ⊆ occ(l). The result follows from Lemma 6.1.5. ■

Lemma 6.2.4

Suppose r and l are terms and l is closed. Then

1. ∃π, θ.r = π·(lθ) implies

2. ∀π.fa(r) ⊆π·fa(l) ⇒∃θ.r = π·(lθ)

Proof

Suppose fa(r) ⊆π·fa(l) and fa(r) ⊆π′·fa(l) and r = π·(lθ).

We need a θ′ such that r = π′·(lθ′). It follows from the above that (π′-1 ◦ π)·fa(lθ) ⊆ fa(l). We use Theorem 6.1.10. ■

Theorem 6.2.5

If R is closed then R−→ can be checked as follows, where for simplicity we suppose R = {(l →m)}:

1. We try to match r against π·l for some π such that fa(r) ⊆π·fa(l), if such a π exists.

2. If we fail then by Lemma 6.2.4 we must fail for instantiating for any π·l. We descend into subterms of r and repeat the previous step.

Whether step 1 of the algorithm above is decidable depends on the decidability of P, X, and C; obviously, if equality of the syntax is undecidable then matching will also be undecidable. So assuming that we have not been silly, closed rules are useful because we only need to compute one π and consider matching, rather than consider an equivariant matching problem.

To use the matching algorithm of Section 4, we need terms to satisfy condition 2 of Definition 4.1.1. So, we could forbid shift permutations altogether. The algorithm might reintroduce them but as noted in Remark 4.4.9, shift can be eliminated once a solution is found. Thus, if we care about decidability and not so much about infinite permutations—which was the case e.g. in [FGM04; FG07]—then shift can be viewed as an internal mechanism of our unification/matching algorithm. However we have designed the mathematics to allow the possibility of exploring other, more liberal (and perhaps still decidable) choices, if we wish. More on this in [Gab12a].

7 EQUALITY: (PERMISSIVE-)NOMINAL ALGEBRA

Permissive-nominal algebra has one judgement form: an equality r = s. This is just an unoriented nominal rewriting rule, so what makes algebra different from rewriting is not so much the judgement form as the properties we care about: instead of confluence and decidability, we primarily care about soundness and completeness. These are Theorems 7.4.6 and Corollary 7.5.12.

This different emphasis affects the axioms we write. The rewrites in Example 5.1.3 are designed to work on λ-terms without unknowns (since we expect to ‘evaluate’ closed terms using rewrites). The analogous axioms in Example 7.1.3 are designed to work also on open terms (since we expect to reason about arbitrary denotations).

Permissive-nominal algebra simplifies and streamlines the nominal algebra logic of [GM09a] (which was based on nominal terms). Essentially, these two logics do the same thing, but there are significant differences which we discuss in Subsection 7.7. Nominal Algebra (NA) was presented in [Gab05; GM06b]; see also [GM07; GM09a]. It was first used to axiomatise substitution, first-order logic, and the λ-calculus [GM06a; GM08a; GM06c; GM08c; GM08b; GM10]. The interest of these papers was not merely to write down the axioms—which all take advantage of atoms-abstraction to axiomatise various binding operators—but also to prove these axioms sound and complete. These proofs are not included here; see the presentations in [GM08a; GM08c; GM10]. Or, to see a much more sophisticated instance of the same general idea, the reader can examine the permissive-nominal logic axiomatisation of arithmetic which is proved correct in the case study of Section 10.

7.1 Judgement form, axioms, theories

Definition 7.1.1

A (nominal algebra) equality judgement is a pair r = s.

Definition 7.1.2

A theory T = (Σ, Ax) is a pair of a signature Σ and a possibly infinite set of equality judgements Ax in that signature; we call them the axioms.

Example 7.1.3

Here are some example nominal algebra theories:

• naSUB axiomatises capture-avoiding substitution (on the λ-calculus). Let Σ have a base sort τ and the following term-formers:

sub : ([ν]τ, τ)τ lam : ([ν]τ)τ app : (τ, τ)τ var : (ν)τ

Axioms are as follows:

(var↦→) var(a)[a↦→X] = X(#↦→) Y [a↦→X] = Y (a∉supp(Y ))(f↦→) f(Y )[a↦→X] = f(Y [a↦→X]) (f∈{lam, app, var, sub})(tup↦→) (X1, . . . , Xn)[a↦→X]= (X1[a↦→X], . . . , Xn[a↦→X])(abs↦→) ([b]Y )[a↦→X] = [b](Y [a↦→X]) (a∉supp(Y ))(id↦→) Y [b↦→var(b)] = Y(η↦→) [a]sub(Y, var(a)) = Y (a∉supp(Y ))

Here and in the next example we sugar sub([a]r, t) to r[a↦→t]. Every permission set contains b and every permission set contains a except for supp(Y), as indicated above. Sorts are filled in as appropriate. naSUB is based on the nominal algebra axioms of [GM06a; GM08a] (which were parameterised over the signature Σ). There, we proved the axioms sound and complete for a specific syntactic model in which Z[a:=X] really is interpreted as capture-avoiding substitution. The completeness result from Corollary 7.5.12 remains valid but is weaker because it holds not for the specific syntactic model, but the class of all nominal algebra models of the axioms.

• naLAM extends the previous theory with two more axioms:

(β) (λ[a]Y )X = Y [a↦→X](η) λ[a](Xa) = X (a∉supp(X))

This theory is studied in [GM08b; GM10]. Analogously to naSUB, we prove the axioms sound and complete for a syntactic model where substitution is substitution and β- and η-conversion are β- and η-conversion.

Remark 7.1.4

Compare and contrast Example 7.1.3 with Example 5.1.3. Clearly, one is an equality theory and another a rewrite theory, but we obtain a nominal algebra theory from Example 5.1.3 by replacing → by =, and conversely we can replace = with → in Example 7.1.3.

So why are they different? They demonstrate different design priorities.

The rewrites in Example 5.1.3 are designed to operate on ground terms (fU (r) = ∅), following an intuition that rewriting is about ‘executing programs’. The equalities in Example 7.1.3 are designed to operate on possibly open terms, following an intuition that algebra is about models, not all of whose elements need be referenced by ground terms.

What we gain in deductive power we lose in computational properties. For instance, nrSUB is terminating whereas (an oriented version of) naSUB is not terminating, because explicit substitutions can ‘churn’ by distributing repeatedly over one another

(this is essentially the idea behind Melliès’s counterexample in [Mel95]). On the other hand while the effect of (#↦→) from naSUB can be obtained on ground terms using the rules in nrSUB, by pushing the substitution down to the atoms, the rules of nrSUB are not deductively powerful enough to do this for open terms (or arbitrary models). More on this in [GM08a; GM10].

Figure 4: Derivable entailment in Permissive-Nominal Algebra (PNA)(Refl)r = rr = s s = t(Trans)r = tr = s(Symm)s = rr1 = r′ 1 . . . rn = r′ n(Cong1)(r1, . . . , rn) = (r′ 1, . . . , r′ n)r = r′(Cong2)f(r) = f(r′)r = r′(Cong3)[a]r = [a]r′((r=s)∈T)(Axr=s)π·(rθ) = π·(sθ) Figure 4: Derivable entailment in Permissive-Nominal Algebra (PNA)

7.2 Derivable equality

Definition 7.2.1

Suppose T is a theory. Derivable equality T ⊢r = s is the least transitive reflexive symmetric relation such that for every (r = s) ∈ T, position P, and substitution θ, if sort(r) = sort(P) and fa(rθ) ∪ fa(sθ) ⊆ supp(P) (so that P[lθ] and P[sθ] are well-defined) then

T ⊢P[rθ] = P[sθ].
Remark 7.2.2

Definition 7.2.1 is rather compact; it might be useful to expand it a little. This is Figure 4, given in natural deduction style.

The reader familiar with nominal terms (see for instance Figure 2 of [UPG04]) should note of (Cong3) that we do not need to consider the case [a]r = [b]s, because α-equivalence is handled automatically for us by nominal abstract syntax. It is built in by Definition 2.4.8. In other words, thanks to how we set up our permissive-nominal terms syntax, we can always rename abstracted atoms so that they are equal. We noted an analogous point earlier on, in Remark 4.1.6.

Lemma 7.2.3

Suppose T = (Σ, Ax) is a theory. Then:

• T ⊢a = b is impossible.

• T ⊢ [a]r = [b]s if and only if b ∉ fa(r) and (b a)·r = s.

• T ⊢ (r1, . . . , rn) = (s1, . . . , sn) if and only if T ⊢ri = si for 1 ≤i ≤n.

Proof

In axiom (r = s) ∈ Ax, r and s must have base sort τ; thus it is not possible to assert equalitities between atoms, abstractions, or tuples (unless wrapped in a term-former and so injected into a base sort). The second part additionally uses Lemma 2.4.9. ■

Lemma 7.2.4

Suppose T ⊢r = s. Then:

1. T ⊢π·r = π·s.

2. T ⊢rθ = sθ.

Proof

Both parts are by a routine argument on derivations. We consider one case:

• The case (r′ = s′) ∈ T and r = P[r′θ′] and s = P[s′θ′] and P = (t, X). For the first part we use a position (π·t, X).
For the second part we consider a position P ′ = (t(θ−X), X) and consider P ′[r′θ′θ] and S′[r′θ′θ] (θ−X defined in Definition 4.3.3). It is not hard to check that P ′[r′θ′θ] = P[r′θ′]θ and P ′[s′θ′θ] = P[s′θ′]θ, and the result follows.

■

7.3 Interpretation of signatures and terms

Definition 7.3.1

Suppose (A, B) is a sort-signature (Definition 3.1.1).

An interpretation I for (A, B) consists of an assignment of a nonempty permissive-nominal set ⟦α⟧I to each sort α in (A, B), along with equivariant maps

• for each ν ∈A an equivariant and injective map Aν →⟦ν⟧I which we write aI,

• for each ν ∈A and α an equivariant and injective map [Aν]⟦α⟧I →⟦[ν]α⟧I which we write [a]Ix, and

• for each αi for 1 ≤i ≤n an equivariant and injective map Πi⟦αi⟧I → ⟦(α1, . . . , αn)⟧I which we write (x1, . . . , xn)I.

Definition 7.3.2

Suppose Σ = (A, B, C, F, ar) is a signature (Definition 3.1.5).

An interpretation I for Σ, or Σ-algebra, consists of the following data:

• An interpretation for the sort-signature (A, B) (Definition 7.3.1).

• For every f ∈F with ar(f) = (α)τ an equivariant function fI from ⟦α⟧I to ⟦τ⟧I.

• An equivariant assignment from C ∈C to CI ∈⟦sort(C)⟧I. (That is, (π·C)I = π·(CI).)

Definition 7.3.3

Suppose I is a Σ-algebra. A valuation ς to I is an equivariant function on unknowns X such that for each unknown X, ς(X) ∈⟦sort(X)⟧I.

ς will range over valuations.

Definition 7.3.4

Suppose I is a Σ-algebra. Suppose ς is a valuation to I.

Extend I to an interpretation on terms ⟦r⟧I ς (where of course r is a term in the signature Σ) by:

⟦a⟧I ς = aI⟦f(r)⟧I ς = fI(⟦r⟧I ς)⟦C⟧I ς = CI⟦(r1, . . . , rn)⟧I ς = (⟦r1⟧I ς, . . . , ⟦rn⟧I ς)I⟦X⟧I ς = ς(X) ⟦[a]r⟧I ς = [a]I⟦r⟧I ς

Lemma 7.3.5 is a basic sanity check and an important soundness result:

Lemma 7.3.5

If r : α then ⟦r⟧I ς ∈⟦α⟧I.

Proof

By a routine induction on r. ■

Lemma 7.3.6

π·⟦r⟧I ς = ⟦π·r⟧I ς.

Proof

By a routine induction on r. We consider one case:

• The case X. By Definition 7.3.4 ⟦X⟧I ς = ς(X). Therefore π·⟦X⟧I ς = π·ς(X). By assumption π·ς(X) = ς(π·X) = ⟦π·X⟧I ς.

■

Lemma 7.3.7

supp(⟦r⟧I ς) ⊆ fa(r).

Proof

From Lemmas 2.3.3 and 7.3.6. ■

7.4 Models and soundness

Definition 7.4.1

For a theory T = (Σ, Ax) and interpretation I of T call (r = s) valid in I when ⟦r⟧I ς = ⟦s⟧I ς for every valuation ς to I. Call I a model of T when every axiom (r = s) ∈ Ax is valid in I. Write T |= r = s when (r = s) is valid in every model of T.

Lemma 7.4.2

If ς(X) = ς′(X) for all X ∈ fU (r) then ⟦r⟧I ς = ⟦r⟧I ς′.

Proof

By a routine induction on r. ■

Definition 7.4.3

Suppose ς is a valuation to I. Suppose X is an unknown and x ∈⟦sort(X)⟧I is such that supp(x) ⊆ supp(X). Define a function ς[X:=x] by

(ς[X:=x])(π·X) = π·x and (ς[X:=x])(Y ) = ς(Y ) all other Y
Lemma 7.4.4

ς[X:=x] in Definition 7.4.3 is well-defined and a valuation to I.

Proof

As that of Proposition 2.5.5. ■

Lemma 7.4.5

⟦r⟧I ς[X:=⟦t⟧I ς] = ⟦r[X:=t]⟧I ς. As corollaries we have:

1. If ⟦r⟧I ς = ⟦s⟧I ς then ⟦P[r]⟧I ς = ⟦P[s]⟧I ς.

2. If ⟦r⟧I ς = ⟦s⟧I ς then ⟦rθ⟧I ς = ⟦sθ⟧I ς.

Proof

By a routine induction on the definition of ⟦r⟧I ς. We consider one case:

• The case of ⟦π·X⟧I ς[X:=t]. We reason as follows:

⟦π·X⟧I ς[X:=⟦t⟧I ς] = π·⟦t⟧I ςDefinition 7.3.4= ⟦π·t⟧I ςLemma 7.3.6= ⟦(π·X)[X:=t]⟧I ςDefinition 3.4.8.

For the two corollaries we reason as follows:

1. By definition where P = (t, X), P[r] = t[X:=r] and P[s] = t[X:=s]. Using the assumptions,

⟦t[X:=r]⟧I ς = ⟦t⟧I ς[X:=⟦r⟧I ς] = ⟦t⟧I ς[X:=⟦s⟧I ς] = ⟦t[X:=s]⟧I ς.

2. It is a fact of syntax that fU (r) and fU (s) are finite. Using Lemma 3.4.12 we may represent the effect of θ on r and s as a sequence of atomic substitutions (Definition 3.4.5). The result follows.

■

Theorem 7.4.6 (Soundness).

For any T = (Σ, Ax) if T ⊢r = s then T |= r = s.

Proof

Let I be a model of T and ς be a valuation to I.

Identity in the denotation is reflexive, transitive, and symmetric so it suffices to check the theorem for axioms. That is, suppose (r = s) ∈ Ax and assume a position P and substitution θ such that sort(r) = sort(P) and fa(rθ) ∪ fa(sθ) ⊆ supp(P). We must show that ⟦P[rθ]⟧I ς = ⟦P[sθ]⟧I ς.

I is a model so ⟦r⟧I ς = ⟦s⟧I ς. We use parts 1 and 2 of Lemma 7.4.5. ■

7.5 Free term models and completeness

In this subsection fix a signature Σ and a theory T = (Σ, Ax).

The proof of completeness follows a standard method: we construct a model out of syntax in which by construction two terms denote equal elements if and only if they are derivably equal.

The subtlety occurs in Lemma 7.5.9. We want to eliminate ς in ⟦r⟧F(T) ς by converting it into a substitution θ. This ‘should’ be easy, since for each X, ς(X) is a provably equivalent class of terms. We need only choose some representative term in ς(X) for each X and set θ(X) to be that representative.

If we are naive in our construction then this could be impossible, as outlined in Example 7.5.10: there might be ‘too many atoms’ in the available representatives. We enrich our syntax with ‘enough’ extra constant symbols, to guarantee ‘enough’ representatives of every element of the model. Nominal algebra without the constant symbols is complete for the same semantics, but the proof would be more complex.

Definition 7.5.1

For each sort α in Σ define [r]T and F(T)α by

[r]T = {r′ : α | T ⊢r = r′} (r : α)F(T)α = {[r]T | r : α}.

Make each F(T)α into a permissive-nominal set by giving it a permutation action

π·[r]T = [π·r]T.

F(T) stands for ‘Free terms in the signature of T, up to derivable equality in T’. Lemmas 7.5.2 and 7.5.3 relate permutation and support to the natural notions from nominal sets:

Lemma 7.5.2

The permutation action on [r]T is pointwise on [r]T as a set: that is, π·[r]T = {π·r′ | r′ ∈ [r]T}.

Proof

From Definition 7.5.1 and Lemma 7.2.4. ■

Lemma 7.5.3

supp([r]T) ⊆ fa(r).

Proof

From Definition 7.5.1 and Lemma 2.3.3. ■

Definition 7.5.4

We construct the free term interpretation F(T) of T as follows:

• Take F(T)α as in Definition 7.5.1.

• aF(T) = [a]T, [a]F(T)[r]T = [[a]r]T, and ([r1]T, . . . , [rn]T)F(T) = [(r1, . . . , rn)]T.

• fF(T)([r]T) = [f(r)]T for each term-former f : (α)τ in Σ and each r : α.

• CF(T) = [C]T for each constant in Σ.

Lemma 7.5.5

Definition 7.5.4 is well-defined and is an interpretation. That is:

• The choice of representative of [r]T does not matter in any of the clauses.

• The choice of abstracted atom in the clause for [a]F(T)[r]T does not matter.

• The maps aF(T), [a]F(T)[r]T, and ([r1]T, . . . , [rn]T)F(T) are injective.

Proof

The first part follows by congruence properties of derivable equality. The second part additionally uses Lemmas 2.4.10 and 2.4.11. The third part uses Lemma 7.2.3.

■

Definition 7.5.6

Define a theory T+ = (Σ+, Ax +) to be equal to T except that we adjoin ⋃τ F(T)τ to the set of constants in Σ, and we add axioms equating r with [r]T in Ax.

That is, for every r : τ there is a constant Cr = [r]T ∈ Σ+, and an axiom (Cr = r) ∈F(T)+.

Lemma 7.5.7

F(T) extends to an interpretation F(T)+ of T+, where for each r : τ we take CF(T)+r= [r]T. Furthermore, F(T)+ is a model of T+.

Definition 7.5.8

Write ςid for the valuation to F(T) mapping each X to CX = [X]T.

Lemma 7.5.9

For every valuation ς to F(T) there exists a substitution θ in T+

such that ⟦r⟧F(T) ς= ⟦rθ⟧F(T)+ςid.

Proof

For each orbit x ∈|orb(X)| choose a representative X ∈x. Define θ by θ(π·X) = π·CX. Recall that CX = [X]T and by Lemma 7.5.3 supp([X]T) ⊆ supp(X). By Proposition 2.5.5 θ is well-defined and is a substitution

It is not hard to check by induction on r that ⟦r⟧F(T) ς= ⟦rθ⟧F(T)+ςid. ■

Example 7.5.10

To see why Lemma 7.5.9 is non-trivial and how T+ helps, suppose T has one name sort ν, two base sorts τ and τ ′, one term-former abs : (ν, τ)τ ′, and one axiom abs(b, (b a)·X) = abs(a, X) where a ∈ supp(X) and b ∉ supp(X).

Then it is a fact that there is no r ∈ [abs(a, X)]T such that fa(r) ⊆ supp([abs(a, X)]T) and it follows that there is no θ such that ⟦X′⟧F(T) [X′:=[abs(a, X)]T] = ⟦X′θ⟧F(T)+ςid (recall that substitutions must be equivariant).

Theorem 7.5.11

F(T) is a model of T.

Proof

We must show that F(T) validates the axioms.

Suppose (r = s) ∈ Ax. Suppose ς is a valuation to F(T). We must show that ⟦r⟧F(T) ς= ⟦s⟧F(T) ς.

By Lemma 7.5.9 there exists θ to T+ such that ⟦r⟧F(T) ς= ⟦rθ⟧F(T)+ςid and ⟦s⟧F(T) ς= ⟦sθ⟧F(T)+ςid.

By assumption T+ ⊢rθ = sθ. By Lemma 7.5.7, ⟦rθ⟧F(T)+ςid= ⟦sθ⟧F(T)+ςid. The result follows. ■

Corollary 7.5.12 (Completeness).

If T |= r = s then T ⊢r = s.

Proof

Suppose T |= r = s. By Theorem 7.5.11 ⟦r⟧F(T) ςid= ⟦s⟧F(T) ςid (ςid is defined in Definition 7.5.8).

It is not hard to prove by induction that ⟦r⟧F(T) ςid= [r]T and ⟦s⟧F(T) ςid= [s]T. It follows that T ⊢r = s as required. ■

7.6 Freshness

Nominal terms freshness conditions a#X and a#r from [UPG04] correspond in this paper to ‘free atoms of’ a ∉ supp(X) and a ∉ fa(r). See Notation 3.2.7 and Lemma 3.2.5. Call this syntactic freshness.

Nominal sets freshness a ∉ supp(⟦r⟧) is a distinct notion which can be expressed using equality; call this semantic freshness. The two are not identical, but they are connected in various ways which we briefly explore.

Proposition 7.6.1 corresponds to Theorem 5.5 from [GM07] and Lemma 4.51 from [GM09a]:

Proposition 7.6.1

Suppose b ∉ fa(r).

Then T ⊢ (b a)·r = r if and only if for every model I of T and valuation ς to I, a ∉ supp(⟦r⟧I ς).

Proof

By Theorem 7.4.6 and Corollary 7.5.12 T ⊢ (b a)·r = r if and only if T |= (b a)·r = r, which unpacking definitions means that for every I and ς, ⟦(b a)·r⟧I ς = ⟦r⟧I ς. By Lemma 7.3.6 ⟦(b a)·r⟧I ς = (b a)·⟦r⟧I ς, and by Lemma 7.3.7 b ∉ supp(⟦r⟧I ς). The result follows by Corollary 2.2.7. ■

Lemmas 7.5.3 (and also Lemma 7.3.7) express that syntactic freshness implies semantic freshness. A partial converse is Proposition 7.6.3, which is based on a technical property of nominal sets:

Lemma 7.6.2

Suppose X is a nominal set and U ⊆|X| is finitely-supported (so U ∈|pow(X)| from Example 2.2.5) and nonempty.

Then if a#U then there exists some x ∈U with a#x.

Proof

U is nonempty so choose any x′ ∈U. Choose fresh b (so b ∉ supp(U) ∪ supp(x′)) and set x = (b a)·x′. By the definition of support (b a)·U = U. By the pointwise action (Example 2.2.5) x ∈U. By Lemma 2.2.6 a ∉ supp(x). ■

Proposition 7.6.3

a#[r]T implies there exists some r′ such that T ⊢r = r′ and a ∉ fa(r′).

Proof

By Lemmas 7.5.2 and Lemma 7.6.2. ■

7.7 Design of nominal algebra

We designed nominal algebra originally to axiomatise substitution, first-order logic, and the λ-calculus [GM06a; GM06c; GM08a; GM08c; GM09a].

We encountered two design decisions: whether to include freshness axioms, and whether to include atoms-abstraction as primitive.

We disallowed freshness axioms because they are a definitional extension of the system without them, and we chose to include atoms-abstraction as primitive because— even though they too are a definitional extension (see next paragraph)—they make for more compact derivations and proofs and we knew that the reader would expect to see them in a ‘nominal’ paper. These decisions do not matter for expressivity because of the following two equalities from [GP01], here written in the language of FM sets:

(Freshness) a#x ⇔Nb.(b a)·x = x(Abstraction)Nb.([b](b a)·x = [a]x)

In Subsection 11.1 we express the equalities above in PNL. In [Gab12b], we do the same in nominal algebra, showing how to compile nominal algebra with semantic freshness judgements and atoms-abstraction down to the core logic without it.

N above is the new-quantifier meaning ‘for some/any fresh atom’ [GP01; Gab11b].14 N does not care which fresh atom we choose (the some/any property [Gab11b, Theorem 6.5]). So, we do not have to be exact about supp(x) when we choose fresh b; any will do, and for instance Proposition 7.6.1 is an ‘if and only if’ even though we chose b ∉ fa(r) (syntactic freshness) instead of b ∉ supp(⟦r⟧) (semantic freshness), and it may be that supp(⟦r⟧) ⫋ fa(r). More on this Subsection 11.1.

Note that including atoms-abstraction is orthogonal to the rest of the logic in the sense that it is isolated by the sort system: if we provide no term-formers injecting atoms-abstraction into base sorts, then it cannot interact with the rest of the logic.

The permissive-nominal algebra of this paper differs from the nominal algebra of

[GM09a] in the following respects:

• The system here is sorted, the system in [GM09a] is not.

• We use permissive-nominal terms and semantics here, and ‘vanilla’ nominal terms and nominal sets in [GM09a]. That is, the logic here is permissive-nominal algebra. Freshness conditions a#X and a#r translate to a ∉ supp(X) and a ∉ fa(r) here.

• Axioms are exactly equalities, with no freshness contexts: permission sets play this role instead.

• The syntax here admits non-equivariant constant symbols, that of [GM09a] does not. That does not matter if we are using finitely-supported models (as is the case in [GM09a]) because finite non-equivariance can be emulated using term-formers applied to finitely many atoms. Here, elements can have infinite support, which cannot be emulated using (finite) equivariant term-formers.

• The syntax here admits the possibility of unknowns with empty support ranging over closed elements (so it includes the •t freshness constraint of [FG07, Subsection 9.2]), unknowns with finite support ranging over finitely-supported elements, unknowns with support equal to a permission set, and whatever else we can imagine in-between.

• The development is parameterised over the set of unknowns X and also the group of permutations P. In particular we admit (but do not insist on) the possibility of infinite permutations, including the shift-permutations considered in Subsection 3.6.

• Substitutions and valuations are—rather elegantly—treated as equivariant functions on X the set of unknowns.

In spite of these many differences, the spirit of the proofs remains the same. The details become simpler, and in particular the non-equivariant constants make construction of the free term model easier.15

8 THE NOMINAL HSP THEOREM

The HSP theorem states that a class of Σ-algebras is equational if and only if it is closed under Homomorphism, Subobject, and Product. Definitions follow below, and the main result is Theorem 8.7.3.

The result was first proved for the case of ‘ordinary’ algebra (using first-order terms and not over nominal sets) by Birkhoff [Bir35]. It is also called Birkhoff’s theorem [BS81, Theorem 11.12]. We prefer ‘HSP’ since this is more descriptive and Birkhoff’s name is attached to several other results.

The result was first proved for nominal algebra by the author [Gab09], and an alternative proof was provided by Kurz and Petrişan [KP10]. The new proof presented here is also rather short.

HSP was interesting for two reasons: first, it is not obvious that nominal algebra is a true logic of equality, because of the freshness side-conditions which give the nominal algebra as presented e.g. in [GM09a] or in Mathijssen’s thesis [Mat07] a prima facie flavour of conditional equalities. The HSP result holding for nominal algebra was a way of making formal that this is a logic of equality.

The use of permission sets to phrase the logic entirely in terms of equality (freshness migrates to the types, as permission sets) is a step forward from this point of view: the nominal algebra of this paper is more visibly an equational logic. Still, HSP along with soundness and completeness (Theorem 7.4.6 and Corollary 7.5.12) form a triumvirate of results of interest for an algebraic reasoning framework.

The proofs here are much shorter and clearer than those of [Gab09]—and the final result is strictly stronger than [Gab09; KP10], which actually proved an HSPA theorem that a class of Σ-algebras is equational if and only if it is closed under Homomorphism, Subobject, Product, and Atoms-abstraction.

That is, we have dropped the ‘atoms-abstraction’ from the closure conditions. How can this be? The use of permission sets gives us finer control over the support of valuations; we needed atoms-abstraction in the proof of [Gab09, Theorem 9.8] to eliminate ‘extra’ atoms introduced by a valuation ς—‘extra’ relative to the freshness information in a freshness context ∆. Here, because freshness contexts/permission sets are fixed, this cannot happen.

8.1 Algebra homomorphisms

Definition 8.1.1

Suppose Σ = (A, B, C, X, F, ar) is a signature and suppose X and Y are interpretations of Σ. A Σ-homomorphism Θ from X to Y is a family of equivariant functions Θα from ⟦α⟧X to ⟦α⟧Y for each sort α in the sort-signature (A, B) such that:

• Θν(aX) = aY.

• Θ(α1,...,αn)(x1, . . . , xn)X = (Θα1(x1), . . . , Θαn(xn))Y.

• Θ[ν]α([a]Xx) = [a]YΘα(x).

• Θτ (fX(x)) = fY(Θα(x)) where f : (α)τ is in F.

Definition 8.1.2

Call Y a homomorphic image of X when there is a Σ-homomorphism Θ from X to Y such that Θα is surjective for every sort α in (A, B).

Call Θ injective when Θα is injective for every sort α in (A, B).

Lemma 8.1.3

Suppose Σ is a signature and X and Y are Σ-algebras. Suppose Θ is a Σ-algebra homomorphism from X to Y.

Suppose that ς is a valuation to X. Define Θ(ς) a valuation to Y by Θ(ς)(X) = Θsort(X)(ς(X)) for every X ∈X.

Then for every r : α, Θα(⟦r⟧X ς ) = ⟦r⟧Y Θ(ς).

Proof

By an easy induction on r. ■

Lemma 8.1.4

Suppose Σ is a signature and T = (Σ, Ax) is a theory. Suppose X and Y are Σ-algebras and Y is a homomorphic image of X under Θ.

Then if X is a model of T, then so is Y.

Proof

Choose (r = s) ∈ Ax and a valuation ς to Y. It suffices to show that ⟦r⟧Y ς = ⟦s⟧Y ς .

We construct a valuation ς′ to X as an equivariant extension (Definition 2.5.4) of the following data. For each unknown X : α let XX = {x ∈|Xα| | Θ(x) = ς(X)}. We construct a valuation ς′ to X by for each orbit and representative X ∈ orb(X) ∈X setting ς′(X) = x for some choice of x ∈XX.

By construction Θς′ = ς. By assumption ⟦r⟧X ς′ = ⟦s⟧X ς′. We apply Θ to both sides and use Lemma 8.1.3. ■

8.2 Subalgebras

Definition 8.2.1

For Σ-algebras X and Y, call X a subalgebra of Y when:

• |τ X| ⊆|τ Y| for every τ ∈B.

• The subset inclusion maps form a Σ-algebra homomorphism (Definition 8.1.1).16

Lemma 8.2.2

For Σ-algebras X, Y and a theory T = (Σ, Ax), if Y is a model of T and X is a subalgebra of Y then X is a model of T.

8.3 Products

Definition 8.3.1

Let I be a (possibly countably infinite) indexing set and (Xi)i∈I be an I-indexed collection of Σ-algebras. The product algebra Πi∈IXi is the Σ-algebra such that:

• For each α in Σ, αΠi∈IXi = Πi∈IαXi as defined in Definition 2.4.5.

• The ith projection map to Xi is a Σ-algebra homomorphism for every i ∈I.

Lemma 8.3.2

For any I-indexed collection of Σ-algebras (Xi)i∈I, if Xi is a model of T = (Σ, Ax) for every i ∈I then so is Πi∈IXi.

Proof

Suppose (r = s) ∈ Ax. Suppose ς is a valuation to Πi∈IXi. For each i ∈I we obtain a valuation ςi to Xi by projecting to the ith component. It follows that ⟦r⟧Xςi i= ⟦s⟧Xςi i, and thus ⟦r⟧Πi∈IXiς= ⟦s⟧Πi∈IYiς. ■

8.4 Ground term models and extending a signature

Definition 8.4.1

Call r ground when fU (r) = ∅.

Definition 8.4.2 exactly follows Definition 7.5.1 (cf. Remark 8.4.6):

Definition 8.4.2

Suppose T = (Σ, Ax) is a theory. For each sort α in Σ define [r]gndT and G(T)α by

[r]gnd T= {r′ : α | T ⊢r = r′} (r : α, r ground)G(T)α = {[r]gnd T| r : α, r ground}.

Make each G(T)α into a permissive-nominal set by giving it a permutation action

π·[r]gnd T= [π·r]gnd T .
Lemma 8.4.3

supp([r]gndT ) ⊆ fa(r).

Proof

From Definition 7.5.1 and Lemma 2.3.3. ■

Definition 8.4.4

We construct the ground free term interpretation G(T) of T as follows:

We take G(T)α as in Definition 8.4.2. We define:

aG(T) = [a]gnd T[a]G(T)[r]gnd T= [[a]r]gnd T([r1]gnd T , . . . , [rn]gnd T )G(T) = [(r1, . . . , rn)]gnd TfG(T)([r]gnd T ) = [f(r)]gnd TCG(T) = [C]gnd T

Above, f ranges over each term-former f : (α)τ in Σ and C ranges over each constant in Σ.

Lemma 8.4.5

Definition 8.4.4 is well-defined and is an interpretation.

Proof

As the proof of Lemma 7.5.5. ■

Remark 8.4.6

Definition 7.5.1 is a special case of Definition 7.5.1. We obtain F(T) as G(T′) where T′ is obtained from T by extending its signature with a copy of X as constants (the construction is made formal in Definition 8.5.2 below).

Doing this in Definition 7.5.1 would have complicated the presentation for no immediate gain, so it seemed kinder on the reader to build the special case first by hand.

Note that we need to use ground terms now, for the proof of Theorem 8.5.3 to work. The reason is that F(T) has elements in each sort given by the elements [X]T, whereas G(T) lacks these elements.

8.5 Surjective maps onto algebras

Fix a signature Σ and any collection of Σ-algebras V.

Definition 8.5.1

Suppose T = (Σ, Ax) and suppose X and Yi for i ∈I are models of T. Suppose θi ∈X →Yi is a family of homomorphisms.

Write Πiθi for the natural map from X to ΠiYi, mapping x ∈|Xα| to (θi(x))i ∈ |ΠiYi|.

It is easy to verify that Πiθi is a Σ-algebra homomorphism.

Definition 8.5.2

Suppose Σ and Σ′ are signatures. Say Σ′ extends Σ with fresh constants when Σ = (A, B, C, X, F, ar′) and Σ′ = (A, B, C ∪D, X, F, ar′) where D ∩C = ∅ and ar′(C) = ar(C) for every C ∈C.

Theorem 8.5.3

Suppose T = (Σ, Ax) is a theory and V is a model of T. Then there exists a theory T′ = (Σ′, Ax) where Σ′ extends Σ with some fresh constants D such that V is a homomorphic image of G(T′).

Proof

We take D = ⋃α |Vα| and construct a homomorphism based on mapping x ∈Vα (as a constant in D) to itself (as an element of |Vα|). ■

8.6 Injections out of free algebras

Definition 8.6.1

Suppose Σ is a signature and V is a set of Σ-algebras. Let T = (Σ, Ax) where Ax is the collection of judgements valid in all V ∈V for all valuations. Call T the (Σ-)theory generated by V.

Remark 8.6.2

So (r = s) ∈ Ax in Definition 8.6.1 when for every V ∈V and every valuation ς to V, it is the case that ⟦r⟧V ς = ⟦s⟧V ς .

Definition 8.6.3

Define the constants of a term consts(r) just as Definition 3.3.2 except that we take consts(C) = {orb(C)} and consts(X) = ∅.

Lemma 8.6.4

Suppose Σ is a signature and Σ′ extends Σ with some fresh constants D. Suppose Σ has enough unknowns (Definition 3.1.10).

If g is a ground term in Σ′ then there exists a term g-1 in Σ and substitution θ such that g-1θ = g.

Proof

For each orbit in consts(r) choose a representative C ∈ orb(C) ∈ consts(r), and some distinct unknown XC with sort(XC) = sort(C) and supp(C) ⊆ supp(XC)— we can do this because we have assumed enough unknowns and it is a fact that consts(r) is finite. Define θ to be the equivariant extension of this choice, so θ(π·XC) = π·C and (for all the other unknowns) θ(Y ) = Y . This is well-defined by Proposition 2.5.5.

It is now easy to generate g-1 by replacing each C in g with XC (modulo some permutations). ■

Theorem 8.6.5

Suppose V is a collection of Σ-algebras and Σ has enough unknowns. Let T = (Σ, Ax) be the Σ-theory generated by V. Suppose Σ′ extends Σ with some fresh constants D and write T′ = (Σ′, Ax).

Then there exists some indexing set I, set of algebras {Vi ∈V | i ∈I}, and an injective Σ-algebra homomorphism Θ from G(Σ′) to Πi∈IVi.

Proof

Take I to be the set of all pairs (g, h) of ground terms in Σ′ such that T′ ⊬g = h.

Consider some i = (g, h) ∈I. By Lemma 8.6.4 there exist g-1, h-1, and θi such that g-1θi = g and h-1θi = h. We assumed that T′ ⊬g = h and it follows using Lemma 7.2.4 that T ⊬g-1 = h-1. Since T is the theory generated by V there exists a model Vi ∈V and a valuation ς such that ⟦g-1⟧Viς≠ ⟦h-1⟧Vς i. We define a Σ-homomorphism Θi from G(T′) to Vi as an equivariant extension of mapping C ∈D to ς(XC), where C and XC are as chosen in the proof of Lemma 8.6.4.

It follows by the choice of Vi that Πi∈Iθi from G(T′) to Πi∈IVi is injective as a map on underlying sets. ■

8.7 Proof of the HSP theorem

We can now prove Theorem 8.7.3; a similar result for nominal algebra is proved in [Gab09].

Definition 8.7.1

Suppose Σ is a signature. Suppose V is a collection of Σ-algebras. Then:

• Call V a (Σ-)variety when it is closed under Homomorphic image (Definition 8.1.1), Subalgebra (Definition 8.2.1), and countable Product (Definition 8.3.1).

• Call V (Σ-)equational when it is the collection of Σ-algebras that are models of T = (Σ, Ax) for some set of axioms Ax.

Lemma 8.7.2

Suppose Σ is a signature with enough unknowns. Suppose V is a Σ-variety and let T = (Σ, Ax) be the Σ-theory generated by V. Suppose Σ′ extends Σ with some fresh constants D and write T′ = (Σ′, Ax). Then G(T′) ∈V.

Proof

By Theorem 8.6.5 there is some indexing set I, set of Σ-algebras {Vi ∈V | i ∈I}, and injective Σ-algebra homomorphism Θ from G(T′) to Πi∈IVi. V is closed under products so Πi∈IVi ∈V. The image of |G(T′)| is a subalgebra of Πi∈IVi, and is a homomorphic image of that subalgebra (by inverting Θ). V is closed under subalgebras and homomorphic images, so the result follows. ■

Theorem 8.7.3

Suppose Σ is a signature with enough unknowns. A collection of Σ-algebras V is equational if and only if it is a variety

Proof

Suppose V is equational. By Lemma 8.3.2 V is closed under products. By Lemma 8.1.4 V is closed under homomorphic images. By Lemma 8.2.2 V is closed under subalgebras. Therefore V is a variety.

Conversely, suppose V is a variety. Let T be the theory on Σ generated by V as described in Definition 8.6.1. Let V be any model of T. By Theorem 8.5.3 there exists a signature Σ′ extending Σ with some fresh constants D such that V is a homomorphic image of G(T′). By Lemma 8.7.2 G(T′) ∈V. Since V is closed under homomorphisms, V ∈V as required. Therefore V is equational. ■

Permissive-nominal logic: ∀X

9 PERMISSIVE-NOMINAL LOGIC

We now add quantification over unknowns—that is, ∀X—to permissive-nominal terms. Permissive nominal techniques makes the theory of α-equivalence easy here: if we used ‘vanilla’ nominal terms, then the development below might not be impossible, but we believe that it would be harder. We obtain a first-order logic which we call permissive-nominal logic.

Permissive-nominal logic (PNL) is just first-order logic, enriched with nominal-style names. Thus, the derivation rules in Figure 5 are (virtually) identical to those of first-order logic. Only the term language is really changed.

In this section we set up PNL as a sequent derivation system (Figure 5), interpret it in permissive-nominal sets (Definition 9.3.2), and prove soundness and completeness (Theorems 9.3.6 and 9.4.16).

In Section 10 we undertake as an extended case study a sound and complete finite axiomatisation of arithmetic inside PNL.

9.1 Syntax

The notions of sort-signature (A, B) and sort language are as in Definition 3.1.1. An interpretation I for (A, B) consists of an assignment of a permissive-nominal set τI to each τ ∈B, and we extend I to sorts as in Definition 7.3.1.

Definition 9.1.1

For this section it is convenient to take X to be specifically example 2 of Example 3.1.7.

Remark 9.1.2

So an unknown X takes the form

π·Xα = {(π′, Xα) | ∀a∈A< .π(a) = π′(a)}.

In this case, in the light of Remark 3.1.8, we may take fU (r) to be equal to the set of Xα occurring in r.

It is now easy to define binding of unknowns (level 2 variables) in terms. A more abstract account of level 2 binding is also available [Gab11c].

Definition 9.1.3

A PNL signature over a sort-signature (A, B) is a tuple (C, F, P, ar) where:

• C is a permissive-nominal set of constants.

• F is a set of equivariant term-formers.

• P is a set of equivariant predicate-formers.

• ar assigns

– to each constant C ∈C an arity τ,

– to each f ∈F a term-former arity (α)τ, and

– to each P ∈P a proposition-former arity α, where α and τ are in the sort-language determined by (A, B).

A (PNL) signature S is then a tuple (A, B, C, F, P, ar).

Definition 9.1.4

Suppose S = (A, B, C, F, P, ar) is a PNL signature.

Terms are defined as in Definition 3.2.1 for the signature (A, B, C, X, F, ar).17

Propositions are defined as follows:

⊥propositionφ proposition ψ proposition φ ⇒ψ propositionr : α (ar(P) = α) P(r) propositionφ proposition ∀Xα.φ proposition

Here ∀Xα binds Xα in φ. We can use nominal abstract syntax to do this.

Notation 9.1.5

Write ∀X.φ as shorthand for ∀Xα.φ where X = {(π′, Xα) | ∀a∈A<.π′(a) = π(a)} for some π.

Lemma 9.1.6

Support and the permutation action as characterised for terms on Lemma 3.2.5 extend to propositions as follows:

supp(⊥) = ∅ supp(P(r)) = supp(r)supp(φ ⇒ψ) = supp(φ) ∪supp(ψ) supp(∀X.φ) = supp(φ)π·⊥= ⊥ π·P(r) = P(π·r)π·(φ ⇒ψ) = (π·φ) ⇒π·ψ π·∀X.φ = ∀X.π·φ
Notation 9.1.7

We may write fa(φ) for supp(φ).

9.2 Derivability

Definition 9.2.1

Φ and Ψ will range over sets of propositions. We may write φ, Φ and Φ, φ as shorthand for {φ} ∪ Φ. We may write Φ, Ψ as shorthand for Φ ∪ Ψ.

Write fU (Φ) = ⋃{fU (φ) | φ ∈ Φ}. A sequent is a pair Φ ⊢ Ψ.

Definition 9.2.2 (Derivable sequents).

The derivable sequents are defined in

Figure 5.

Remark 9.2.3

As standard, the intuition of Φ ⊢ Ψ being derivable is “the con-junction (logical and) of the propositions in Φ entails the disjunction (logical or) of

the propositions in Ψ”. So for instance, intuitively the axiom rule (Ax) expresses that φ if and only if π·φ.

The permutation π in (Ax) is deliberate and represents equivariance (preservation of truth under permuting atoms) within permissive-nominal logic. Because of this permutation π, free atoms can behave like variables ranging over distinct atoms.

Thus in PNL we can express a theory of atoms-inequality as follows: Suppose a name sort Atm and a proposition-former neq : (Atm, Atm), along with a single proposition neq(a, b) for two distinct atoms in Atm—and, if we wish, another proposition neq(a, a) ⇒⊥. The permutation π in (Ax) ensures that a and b represent any two distinct atoms.

Figure 5: Sequent derivation rules of Permissive-Nominal Logic(Ax)Φ, φ ⊢π·φ, Ψ(⊥L)Φ, ⊥⊢ΨΦ ⊢φ, Ψ Φ, ψ ⊢Ψ(⇒L)Φ, φ ⇒ψ ⊢ΨΦ, φ ⊢ψ, Ψ(⇒R)Φ ⊢φ ⇒ψ, ΨΦ, φ[X:=r] ⊢Ψ (fa(r)⊆supp(X), r:sort(X)) (∀L) Φ, ∀X.φ ⊢ΨΦ ⊢φ, Ψ (X ∉fU (Φ, Ψ))(∀R)Φ ⊢∀X.φ, ΨΦ ⊢φ, Ψ Φ, φ ⊢Ψ(Cut)Φ ⊢Ψ Figure 5: Sequent derivation rules of Permissive-Nominal Logic
Remark 9.2.4

The condition fa(r) ⊆ supp(X) in (∀L) might suggest that ∀X.φ means “φ[X:=r] for every r such that fa(r) ⊆ supp(X)”. This is so, but the π in (Ax) means that what supp(X) in ∀X.φ really restricts is capture, as we now discuss.

• Suppose a name sort Atm and suppose X : Atm and P : Atm. Suppose b ∈ pmss(X). By considering the swapping (b a) and (Ax), and (∀L), ∀X.P(X) ⊢ P(b) for all a, even if a ∉ supp(X), as follows:

(Ax) π = (b a)P(b) ⊢P(a)(∀L) [X:=b]∀X.P(X) ⊢P(a)

So we can derive P(a) from ∀X.P(X), even if a is not permitted in X.

• This may not work if we have to ‘shift’ infinitely many atoms; e.g. there is no finite π such that fa(π·(X, a)) ⊆ supp(X) where a ∉ supp(X). If P has shift-permutations (Definition 3.6.1), then we can use them. Consider any sort α and suppose X : α and supp(X) = S. Suppose Q : α. Consider any other Y : α with supp(Y ) = S ∪{a} where a ∉S. We will show that given shift-permutations, ∀X.Q(X) ⊢ Q(Y) is derivable.

Suppose S ∪{a} = π·S. We derive as follows:

(Ax)Q(π·Y ) ⊢Q(Y )(∀L) [X:=π·Y ]∀X.Q(X) ⊢Q(Y )

• Nevertheless, ∀X.φ does not mean “φ[X:=r] for every r”. This is because permutations are bijective. For example, suppose X : Atm, a ∉ supp(X), and P : ([Atm]Atm). Then ∀X.P([a]X) ⊢P([a]r) for all r such that a ∉ fa(r), and also ∀X.P([b]X) ⊢P([b]r) for all r and all b such that b ∉ fa(r). However,

∀X.P([a]X) ⊬P([a]a), and for all b, ∀X.P([a]X) ⊬P([b]b).

The fact that a ∉ supp(X) forbids capture by an instantiation, in a suitable sense.

9.3 Interpretation and soundness

Definition 9.3.1

Suppose S = (A, B, C, F, P, ar) is a signature.

A (PNL) interpretation I for S consists of the following data:

• An interpretation for the sort-signature (A, B) (Definition 7.3.1).

• For every f ∈F with ar(f) = (α′)α an equivariant function fI from ⟦α′⟧I to ⟦α⟧I (Definition 2.3.1).

• For every P ∈P with ar(P) = α an equivariant function PI from ⟦α⟧I to {0, 1} (Definition 2.4.1).

Definition 9.3.2

Suppose that I is an interpretation. Define an interpretation of propositions by:

⟦P(r)⟧I ς = PI(⟦r⟧I ς)⟦⊥⟧I ς = 0 ⟦φ ⇒ψ⟧I ς = max{1−⟦φ⟧I ς, ⟦ψ⟧I ς}⟦∀X.φ⟧I ς = min{⟦φ⟧I ς[X:=x] | x∈⟦sort(X)⟧I, supp(x)⊆supp(X)}
Lemma 9.3.3

⟦φ⟧I ς = ⟦π·φ⟧I ς always.

Proof

By induction on φ. We consider two cases:

• The case ∀X.φ. Suppose ⟦∀X.φ⟧I ς = 1. This means that ⟦φ⟧I ς[X:=x] = 1 for all x ∈⟦α⟧I such that supp(x) ⊆ supp(X). By inductive hypothesis ⟦π·φ⟧I ς[X:=x] = 1 for all x ∈⟦α⟧I such that supp(x) ⊆ supp(X). Therefore ⟦∀X.π·φ⟧I ς = 1. The result follows, since π·(∀X.φ) = ∀X.π·φ.

• The case P(r). We have ⟦P(r)⟧I ς = PI(⟦r⟧I ς). As PI is equivariant, we get ⟦P(r)⟧I ς = PI(π·⟦r⟧I ς). By Lemma 7.3.6 π·⟦r⟧I ς = ⟦π·r⟧I ς. Thus ⟦P(r)⟧I ς = PI(⟦π·r⟧I ς) = ⟦π·P(r)⟧I ς.

■

Lemma 9.3.4

⟦φ⟧I ς[X:=⟦t⟧I ς] = ⟦φ[X:=t]⟧I ς.

Proof

By a routine induction on the definition of ⟦φ⟧I ς in Definition 9.3.2. We consider one case:

• The case of ⟦P(r)⟧I ς[X:=t]. We reason as follows:

⟦P(r)⟧I ς[X:=⟦t⟧I ς] = PI(⟦r⟧I ς[X:=⟦t⟧I ς]) Definition 9.3.2= PI(⟦r[X:=t]⟧I ς) Lemma 7.4.5= ⟦P(r)[X:=t]⟧I ςDefinition 9.3.2.■

Validity and soundness

Definition 9.3.5 (Validity).

Call the proposition φ valid in I when ⟦φ⟧I ς = 1 for all ς.

Call the sequent φ1, . . . , φn ⊢ψ1, . . . , ψp valid in I when (φ1 ∧· · · ∧φn) ⇒ (ψ1 ∨· · · ∨ψp) is valid.

Theorem 9.3.6 (Soundness).

If Φ ⊢ Ψ is derivable, then it is valid in all interpretations.

Proof

By induction on derivations (Figure 5). The case of (Ax) uses Lemma 9.3.3. The case of (∀L) uses Lemma 9.3.4. The case of (∀R) uses Lemma 7.4.2. Other rules are routine by unpacking definitions. ■

9.4 Completeness

In this subsection we prove Theorem 9.4.16: a converse to Theorem 9.3.6, that if φ is valid in all interpretations, then φ it is derivable.

For this subsection fix the following data:

• A signature S = (A, B, C, F, P, ar).

• A formula φ such that ⊬φ.

We will construct an interpretation I and a valuation ς (Definition 7.3.1) such that ⟦φ⟧I ς = 0. This suffices to prove the result.

Maximally consistent set of propositions

Definition 9.4.1

Make a fixed but arbitrary order on propositions ξ1, ξ2, ξ3, ...

Define Φ1 = {¬φ} (where φ was fixed above). For each i ≥ 1 we define Φi+1 as follows:

• If Φi ⊢ξi then write ξ = ξi.

• If Φi ⊢¬ξi then write ξ = ¬ξi.

• If Φi ⊬ξi and Φi ⊬¬ξi then write ξ = ξi. There are now two cases:

• If ξ has the form ¬∀X.ξ′ then we define Φi+1 = Φi∪{ξ, ¬ξ′[X:=Z]} where Z is some fixed but arbitrary choice of unknown that is not free in any proposition in Φi and is such that supp(Z) = supp(X) and sort(Z) = sort(X).

• Otherwise, we define Φi+1 = Φi ∪{ξ}.

Finally, we define Φω by Φω = ⋃i Φi.

Lemma 9.4.2

For every i, Φi ⊬⊥.

Proof

By induction on i:

• By definition Φ1 = {¬φ}. As ⊬φ, we have ¬φ ⊬⊥

• Suppose Φi ⊬⊥. Either Φi+1 = Φi ∪{¬ξ} or Φi+1 = Φi ∪{¬ξ, ¬ξ′[X:=Z]}—we consider the first, simpler case; the second case is similar. Suppose Φi, ξ ⊢⊥. It follows that Φi ⊢¬ξ. So we are not in the third case of Definition 9.4.1 and we are either in the first or the second. So Φi ⊢ξ and thus Φi ⊢⊥; a contradiction.

■

Lemma 9.4.3

Φω ⊬⊥.

Proof

Assume Φω ⊢⊥. So there exists a finite subset Γ of Φω such that Γ ⊢⊥. As Γ is finite it is included in some Φi, and Φi ⊢⊥, contradicting Proposition 9.4.2. ■

Remark 9.4.4

It is well-known that in nominal sets, least upper bounds can sometimes not exist if there are ‘too many’ atoms; so sometimes we have to be careful to not make too many arbitrary choices.18

The reader familiar with nominal techniques will be alert to the possibility that Φω might fail to have a supporting permission set, and that this could cause problems. In fact, in this particular case this is a non-issue: (Ax) from Figure 5 ensures that Φω is not only supported, but in fact equivariant.

Lemma 9.4.5

For every ξ, at least one of ξ ∈ Φω and ¬ξ ∈ Φω holds.

Proof

We check of Definition 9.4.1 that for every i, either ξi ∈ Φi+1 or ¬ξi ∈ Φi+1. The result follows. ■

Lemma 9.4.6

For every ξ, if ¬∀X.ξ ∈ Φω then there exists a Z such that ¬ξ[X:=Z] ∈ Φω.

Proof

There exists an i such that ξi = ¬∀X.ξ. Since Φω ⊢ξi and Φω ⊬⊥, we have that Φω ⊬¬ξi, and so Φi ⊬¬ξi. Thus Φi+1 = Φi ∪{¬∀X.ξ, ¬ξ[X:=Z]}. The result follows. ■

Lemma 9.4.7

If Φω ⊢φ then φ ∈ Φω.

Proof

As, by Lemma 9.4.3, Φω ⊬⊥, if Φω ⊢φ then ¬φ ∉ Φω. Thus by Lemma 9.4.5, φ ∈ Φω. ■

Corollary 9.4.8

1. (φ ⇒ψ) ∈ Φω if and only if (φ ∉ Φω or ψ ∈ Φω).

2. ∀X.φ ∈ Φω if and only if (for every r such that r : sort(X) and fa(r) ⊆ supp(X), φ[X:=r] ∈ Φω).

Proof

1. Suppose (φ ⇒ψ) ∈ Φω and φ ∈ Φω. Then Φω ⊢ψ and so by Lemma 9.4.7 ψ ∈ Φω. Suppose φ ∉ Φω. By Lemma 9.4.5 ¬φ ∈ Φω. So Φω ⊢¬φ and therefore Φω ⊢φ ⇒ψ. By Lemma 9.4.7 (φ ⇒ψ) ∈ Φω. Suppose ψ ∈ Φω. Then Φω ⊢ψ and so Φω ⊢φ ⇒ψ. By Lemma 9.4.7 (φ ⇒ψ) ∈ Φω.

2. Suppose ∀X.φ ∈ Φω. By Lemma 9.4.7, if r : sort(X) and fa(r) ⊆ supp(X) then φ[X:=r] ∈ Φω. Conversely, suppose φ[X:=r] ∈ Φω for every r such that r : sort(X) and fa(r) ⊆ supp(X). We proceed by contradiction: suppose ∀X.φ ∉ Φω. By Lemma 9.4.5 ¬∀X.φ ∈ Φω and by Lemma 9.4.6, there exists a Z such that ¬φ[X:=Z] ∈ Φω. So Φω ⊢¬φ[X:=Z], and so Φω ⊢φ[X:=Z], and so Φω ⊢⊥, contradicting Lemma 9.4.3.

■

The term interpretation

Definition 9.4.9

Define the term interpretation I by:

• ⟦α⟧I = {r | r : α}.

• fI maps r to f(r).

• PI maps r1, . . . , rn to 1 if P(r1, . . . , rn) ∈ Φω and to 0 otherwise.

Define ς by ς(X) = X for all X ∈X and endow ⟦α⟧I with a permutation action given by the action on terms.

Remark 9.4.10

In Definition 7.5.4 we built an interpretation to prove completeness of nominal algebra (Corollary 7.5.12). There, we built our interpretation out of terms quotiented by derivable equality; here we just use terms. Why the difference?

In nominal algebra the judgement-form of the logic is equality—so it makes sense to build an interpretation such that equality maps to denotational identity.

Lemma 9.4.11

1. If ar(f) = (α)τ then fI is well-defined, equivariant, and maps ⟦α⟧I to ⟦τ⟧I.

2. If ar(P) = α then PI is well-defined, equivariant, and maps ⟦α⟧I to {0, 1}.

Proposition 9.4.12

I is an interpretation of the signature S = (A, B, F, P, ar) which we fixed at the beginning of this subsection. In addition, ς is a valuation to I.

Proof

By Lemma 9.4.11 for each f : (α′)α ∈F, fI is an equivariant map from ⟦α′⟧I to ⟦α⟧I and for each P : α ∈P, PI is an equivariant function from ⟦α⟧I to {0, 1}.

By construction ς(X) ∈⟦sort(X)⟧I always. Equivariance is easy. ■

Lemma 9.4.13

⟦r⟧I ς = r.

Lemma 9.4.14

⟦ξ⟧I ς = 1 if and only if ξ ∈ Φω.

Proof

By induction on the definition of ⟦ξ⟧I ς (Definition 9.3.2):

• The case of ⟦P(r)⟧I ς. We reason as follows:

⟦P(r)⟧I ς = 1 ⇔PI(⟦r⟧I ς) = 1 Definition 9.3.2⇔PI(r) = 1 Lemma 9.4.13⇔P(r) ∈ΦωDefinition 9.4.9

• The case of ⟦⊥⟧I ς. By definition ⟦⊥⟧I ς = 0. By part 1 of Corollary 9.4.8, ⊥∉ Φω.

• The case of ⟦φ ⇒ψ⟧I ς. We reason as follows:

⟦φ ⇒ψ⟧I ς = 1 ⇔⟦φ⟧I ς = 0 or ⟦ψ⟧I ς = 1 Definition 9.3.2⇔φ ∉Φω or ψ ∈Φωind. hyp.⇔φ ⇒ψ ∈ΦωCor. 9.4.8, part 2

• The case of ⟦∀X.φ⟧I ς, where α = sort(X) and S = supp(X).

⟦∀X.φ⟧I ς=1 ⇔∀t∈⟦α⟧I.supp(t)⊆S ⇒⟦φ⟧I ς[X:=t]=1 Definition 9.3.2⇔∀t∈⟦α⟧I.supp(t)⊆S ⇒⟦φ[X:=t]⟧I ς = 1 Lems. 7.4.2, 9.4.13⇔⟦φ[X:=t]⟧I ς = 1 every t:α s.t. fa(t)⊆S supp(t) = fa(t)⇔φ[X:=t]∈Φω every t:α s.t. fa(t)⊆S ind. hyp.⇔∀X.φ∈ΦωCor. 9.4.8, part 4■
Lemma 9.4.15

If ⊬φ, then there exists an interpretation I and a valuation ς such that ⟦φ⟧I ς = 0.

Proof

As ¬φ∈Φ0⊆Φω and Φω⊬⊥, we have φ∉Φω. By Lemma 9.4.14, we get ⟦φ⟧I ς = 0. ■

As a corollary we get Theorem 9.4.16:

Theorem 9.4.16 (Completeness).

If φ is valid in all interpretations, then φ is derivable.

10 CASE STUDY: ARITHMETIC IN PERMISSIVE-NOMINAL LOGIC

Because term-formers in PNL can bind, we can axiomatise first-order logic. Thus assume a sort o whose terms reflect formulas of first-order logic. Then PNL quantification ∀Z where Z : o has the quality of an axiom schema, and we can use those terms to axiomatise arithmetic (a theory which in first-order logic famously involves an axiom schema).

So, we should be able to use PNL to give a finite, first-order axiomatisation of arithmetic. Writing down some plausible-looking axioms is one thing—proving they do what we expect them to do, is another. In this section, as a case study of an application of PNL, we do just that.

We proceed as as follows, starting with the following PNL definitions:

• Figure 6 gives .L a signature for a shallow embedding of terms and formulas of first-order logic as PNL terms of sort ι and o respectively.

• Figure 7 gives equality axioms, as a transitive reflexive symmetric congruence for the term-formers in .L.

• Figure 8 axiomatises substitution. We can have some confidence in this axiomatisation because it was already considered for nominal algebra in [GM08a] and proven correct.

• Figure 9 gives axioms for first-order logic.

• Finally, Figure 10 gives axioms for arithmetic. As discussed above, the induction axiom schema is captured using a universal quantification (the ∀Z in (PInd)).

Subsection 10.4 briefly recalls the syntax and derivability relation of ‘real’ first-order logic. Then Subsection 10.5 maps this into the PNL theory we just constructed. Subsection 10.6 briefly recalls Peano arithmetic in the ‘real’ first-order logic.

Finally, in Subsection 10.7 by arguments on models we show our main result of this section: Theorem 10.7.7. A formula is derivable in ‘real’ Peano arithmetic if and only if its translation in PNL is derivable in the PNL theory for arithmetic.

The permissive-nominal terms, PNL, permission-sets, and permissive-nominal sets semantics, all work together, and at the end of it all we really can embed a non-trivial theory with binding in PNL, and know it is correct.

10.1 The signature .L and the axioms

Definition 10.1.1

A signature .L suitable for writing out a PNL theory of first-order logic is given in Figure 6.

Notation 10.1.2

We introduce the following syntactic sugar:

• We may write subo([a]r, t) as r[a↦→t].

• We may write subι([a]r, t) as r[a↦→t].

• We may write both ≈ι and ≈o just as ≈.

Examples of this in use, follow immediately below.

Figure 6: Signature .L suitable for a PNL specification of arithmeticWe assume one atomic sort ν and two base sorts ι and o. We assume term-formers and proposition-formers as follows: .0 : ι.succ : (ι)ι.+: (ι, ι)ι.∗: (ι, ι)ι. ⊥: o.⇒: (o, o)o. ∀: ([ν]o)o.≈: (ι, ι)ovar : (ν)ι subι : ([ν]ι, ι)ι subo : ([ν]o, ι)o≈ι: (ι, ι) ≈o: (o, o) ϵ : (o) Figure 6: Signature .L suitable for a PNL specification of arithmetic
Figure 7: EQU: axioms for equality as a PNL theory(≈2) ∀X′, X, Y ′, Y.(X′≈X∧Y ′≈Y ) ⇒(X′ .+ Y ′ ≈X .+ Y ∧ X′ .∗Y ′ ≈X .∗Y ∧ X′ .⇒Y ′ ≈X .⇒Y ∧ X′ .≈Y ′ ≈X .≈Y)(≈1) ∀X′, X. X′≈X ⇒.succ(X′) ≈.succ(X)(≈0) ∀X. X ≈X(≈. ∀) ∀Z′, Z. Z′≈Z ⇒. ∀([a]Z′) ≈. ∀([a]Z)(≈sub) ∀X′, X, Y ′, Y.(X′≈X∧Y ′≈Y ) ⇒(subι([a]X′, Y ′) ≈subι([a]X, Y ) ∧ subo([a]X′, Y ′) ≈subo([a]X, Y ))(≈o) ∀Z′, Z. Z′≈Z ⇒(ϵ(Z′) ⇔ϵ(Z))(≈ι) ∀X′, X. X′≈X ⇒ϵ(X′ .≈X) We fill in sorts as appropriate. Thus,. ⊥≈o. ⊥whereas 0 ≈ι 0, and so on. The permission sets of all unknowns are equal to A< , and a ∈A< . Figure 7: EQU: axioms for equality as a PNL theory

10.2 The axioms: equality, substitution, first-order logic, and arithmetic

Equality

Axioms for equality ≈: (ι, ι) and equality ≈: (o, o) are given in Figure 7.

Substitution

Axioms for substitution subι and subo are given in Figure 8.

We arguably abuse notation in Figure 8 when we use unknowns of sort ι and o as appropriate not necessarily giving them distinct names (e.g. in (sub∗) X has sort ι, whereas in (sub⇒ . ) we use another unknown also written X with sort o).

First-order logic

Axioms for (a shallow reflection of) first-order formulas as terms in PNL (the . ⊥, .⇒, and . ∀) are given in Figure 9.

Figure 8: SUB: axioms for substitution as a PNL theory(subvar) ∀X. var(a)[a↦→X] ≈X(sub#) ∀X, Z. Z[a↦→X] ≈Z(sub .succ) ∀X′, X..succ(X′)[a↦→X] ≈.succ(X′[a↦→X])(sub .+) ∀X′′, X′, X. (X′′ .+ X′)[a↦→X] ≈(X′′[a↦→X] .+ X′[a↦→X])(sub.∗) ∀X′′, X′, X. (X′′ .∗X′)[a↦→X] ≈(X′′[a↦→X] .∗X′[a↦→X])(sub .⇒) ∀X′′, X′, X. (X′′ .⇒X′)[a↦→X] ≈(X′′[a↦→X] .⇒X′[a↦→X])(sub .≈) ∀X′′, X′, X. (X′′ .≈X′)[a↦→X] ≈(X′′[a↦→X] .≈X′[a↦→X])(sub. ∀) ∀X, Z. (. ∀([b]Z))[a↦→X] ≈. ∀([b](Z[a↦→X]))(subid) ∀X. X[a↦→var(a)] ≈X a ∈A< and b ∉A< . The permission set of X′′, X′, and X is equal to A< . The permission set of Z is equal to (b a)·A< . Figure 8: SUB: axioms for substitution as a PNL theory
Figure 9: FOL: axioms for first-order formulas as a PNL theory( .⇒) ∀Z′, Z. ϵ(Z′ .⇒Z) ⇔(ϵ(Z′) ⇒ϵ(Z))(. ∀) ∀Z.(ϵ(. ∀([a]Z)) ⇔∀X.ϵ(Z[a↦→X]))(. ⊥) ϵ(. ⊥) ⇒⊥ Here Z′ and Z have sort o, permission set A< , and a ∈A< . Figure 9: FOL: axioms for first-order formulas as a PNL theory
Figure 10: ARITH: axioms for arithmetic as a PNL theory(PS0) ∀X..succ(X) ≈.0 ⇒⊥(PSS) ∀X′, X..succ(X′) ≈.succ(X) ⇒X′ ≈X(P+0) ∀X. X .+.0 ≈X(P+succ) ∀X′, X. X′ .+ .succ(X) ≈.succ(X′) .+X(P∗0) ∀X. X .∗.0 ≈.0(P∗succ) ∀X′, X. X′ .∗.succ(X) ≈(X′ .∗X) .+X(PInd) ∀Z.ϵ(Z[a↦→.0]) ⇒(∀X.(ϵ(Z[a↦→X]) ⇒ϵ(Z[a↦→.succ(X)])))⇒∀X.ϵ(Z[a↦→X]) The permission set of X, X′, and Z is A< , and a ∈A< . Figure 10: ARITH: axioms for arithmetic as a PNL theory

Arithmetic

Given EQU, SUB, and FOL, it is not hard to write axioms for arithmetic in PNL. This is in Figure 10. Later on in Theorem 10.7.7 we prove that this is an axiomatisation of arithmetic in PNL.

10.3 Comments on the axioms

Remark 10.3.1

SUB is a PNL rendering of the nominal algebra theory naSUB from Example 7.1.3; the universal quantifiers which are implicit in the nominal algebraic judgement-form are made explicit here. This is essentially the same axiomatisation as studied in [GM06a; GM08a]. Soundness and completeness are proved, so providing some formal sense in which the axioms of SUB are ‘right’.

In [GM08c] first-order logic is equationally axiomatised using nominal algebra (so the axioms involve only equality). Because PNL is already a first-order logic, we can use ⊥, ⇒, and ∀ directly to capture the behaviour of . ⊥, .⇒, and . ∀. So note that FOL here is not the axiomatisation of [GM08c]; there we had to work a little harder because the ambient logic, nominal algebra, was purely equational.

Remark 10.3.2

Instead of the axioms for equality EQU, we could directly extend PNL by adding derivation rules Figure 5 as follows:

Φ, r ≈s, φ[X:=r], φ[X:=s] ⊢Ψ (fa(r)∪fa(s) ⊆supp(X))(≈S)Φ, r ≈s, φ[X:=r] ⊢Ψ
Φ, r ≈r ⊢Ψ(≈R)Φ ⊢Ψ
Remark 10.3.3

Every unknown has a sort, and a permission set.

Different choices of permission set may yield logically equivalent results. For example, in (sublam) it is not vital that supp(Z) is exactly (b a)·A< . The important point is that a ∉ supp(Z).

Similarly, in (subapp) it is not vital that supp(X′′) = supp(X′); when we use the axiom we can instantiate X′′ and X′ to r′′ and r′ such that fa(r′′) ≠ fa(r′), and conversely if we take supp(X′′) ≠ supp(X′) then we can still instantiate X′′ and X′ to r′′ and r′ such that fa(r′′) = fa(r′) ⊆ supp(X′′) ∩ supp(X′).

10.4 First-order logic L

We will use the atoms Aν from .L in Section 10 as variables of our first-order logic (this is not necessary, but it is convenient). So for this section, a, b, c, . . . will range over distinct atoms in Aν.

Definition 10.4.1

Define terms and formulas of L by:

t ::= a | 0 | succ(t) | t + t | t ∗t ξ ::= t ≈t | ⊥| ξ ⇒ξ | ∀a.ξ

Substitution t′[a:=t] and ξ[a:=t] is as usual for first-order logic. We write sequents Ξ ⊢χ where Ξ and χ are sets of formulas. Derivability is as usual for first-order logic.

.

Definition 10.4.2

Define a mapping (-) from terms and formulas of L to terms of .L (Subsection 10.1) by:

(a). = a (0). = .0(succ(t)). =.succ((t).) (t′ + t). = (t′). .+ (t).(t′ ∗t). = (t′). .∗(t). (t′ ≈t). = (t′). .≈(t).(⊥). =. ⊥(ξ′ ⇒ξ). = (ξ′). .⇒(ξ).(∀a.ξ). =. ∀[a](ξ).

.

Definition 10.4.3

Extend (-) to first-order logic sequents Ξ ⊢χ as follows:

(Ξ ⊢χ). = ϵ(. ∀[a1] . . .. ∀[an]((ξ1 ∧. . . ∧ξk) ⇒(χ1 ∨. . . ∨χl)).)

Here, Ξ = {ξ1, . . . , ξk}, χ = {χ1, . . . , χl}, and the free variables of Ξ and χ are {a1, . . . , an} (in some order).

Notation 10.4.4

Write S for EQU ∪ SUB ∪ FOL.

...
Lemma 10.4.5

S ⊢ (t′[a:=t]) ≈ (t′) [a↦→(t) ] and

S ⊢(ξ[a:=t]). ≈(ξ).[a↦→(t).].
Proof

By routine inductions on t and ξ. ■

Theorem 10.4.6 (Correctness).

If Ξ ⊢χ is derivable in first-order logic then S ⊢ (Ξ ⊢χ). is derivable in PNL.

Proof

By a long but routine inspection we can check that EQU, SUB, and FOL allow us to model the behaviour of ‘real’ first-order logic. We use Lemma 10.4.5. ■

10.5 Interpretation of first-order logic

We recall the usual definition of interpretations in first-order logic:

Definition 10.5.1

A nominal (first-order logic) interpretation M is a carrier set M, and elements:

0M ∈M, succM ∈M →M,+M ∈(M × M) →M, and ∗M ∈(M × M) →M.

It is convenient to fix some M from here until Theorem 10.7.7.

Definition 10.5.2

Define Valu𝔸ν (M) by:

Valu𝔸ν (M) = {ε ∈Aν →M | ∃A ⊆Aν.A finite ∧∀a, b ∉A.ε(a) = ε(b)}

Call elements of Valu𝔸ν (M) Aν-valuations (to M). ε will range over Aν-valuations.

If x ∈M write ε[a:=x] for the valuation mapping b to ε(b) and mapping a to x:

ε[a:=x](a) = x ε[a:=x](b) = ε(b)

Give ε ∈ Valu𝔸ν (M) and X ⊆ Valu𝔸ν (M) a pointwise permutation action:

(π·ε)(a) = ε(π-1(a)). π·X = {π·ε | ε ∈X}.

U, V will range over finitely-supported subsets of Valu𝔸ν (M)—so there exists some finite A ⊆Aν such that for all π, if π(a) = a for all a ∈A then π·U = U.

Figure 11: arithmetic: axioms for arithmetic in first-order logic(ps0) ∀a. succ(a) ≈0 ⇒⊥(pss) ∀a′, a. succ(a) ≈succ(a′) ⇒a ≈a′(p+0) ∀a. a+0 ≈a(p+succ) ∀a′, a. a′+succ(a) ≈succ(a′)+a(p∗0) ∀a. a∗0 ≈0(p∗succ) ∀a′, a. a′∗succ(a) ≈(a′∗a)+a(pind) ξ[a:=0] ⇒(∀a.(ξ ⇒ξ[a:=succ(a)]))⇒∀a.ξ(every ξ, every a) Figure 11: arithmetic: axioms for arithmetic in first-order logic
Remark 10.5.3

Valu𝔸ν (M) would normally just be called ‘the set of valuations’. We are more specific since we separately also have valuations on unknowns X (Definition 7.3.3).

PNL atoms are serving as variable symbols of L. To conveniently apply nominal techniques, it is useful to restrict to valuations that are finite in the sense given in Definition 10.5.2. In any case, any term or formula will only contain finitely many atoms.

Definition 10.5.4

We extend the interpretation to first-order logic syntax as follows:

⟦a⟧M ε = ε(a) ⟦0⟧M ε = 0M⟦succ(t)⟧M ε = succM(⟦t⟧M ε )⟦t′ + t⟧M ε = +M(⟦t′⟧M ε , ⟦t⟧M ε )⟦t′ ∗t⟧M ε = ∗M(⟦t′⟧M ε , ⟦t⟧M ε )⟦⊥⟧M ε = 0 ⟦ξ′ ⇒ξ⟧M ε = max{1−⟦ξ′⟧M ε , ⟦ξ⟧M ε }⟦∀a.ξ⟧M ε = min{⟦ξ⟧M ε[a:=x] | x ∈M}⟦t′ ≈t⟧M ε = 1 if ⟦t′⟧M ε = ⟦t⟧M ε and 0 otherwise
Definition 10.5.5

Call the formula ξ valid in M when ⟦ξ⟧M ε = 1 for all ε.

Call ξ1, . . . , ξk ⊢χ1, . . . , χl valid in M when (ξ1 ∧. . . ∧ξk) ⇒ (χ1 ∨. . . ∨χl) is valid.

10.6 A theory of arithmetic in L

Definition 10.6.1

Define a first-order theory of arithmetic by the axioms in

Figure 11. An interpretation M is a model of arithmetic when ⟦ξ⟧M = 1 for ξ each of (ps0), (pss), (p+0), (p+succ), (p∗0), (p∗succ), and every instance of (pind).

Remark 10.6.2

(pind) the induction axiom-scheme is of course of particular interest. We therefore unpack what its validity

⟦ξ[a:=0] ⇒∀a.(ξ ⇒ξ[a:=succ(a)]) ⇒∀a.ξ⟧M = 1 (every ξ, every a)

means, in a little more detail. For every a and ξ:

• If ⟦ξ[a:=0]⟧M ε = 1, and

• if for every x ∈M, ⟦ξ⟧M ε[a:=x] = 1 implies that ⟦ξ[a:=succ(a)]⟧M ε[a:=x] = 1,

• then for every x ∈M, ⟦ξ⟧M ε[a:=x] = 1.

In (pind) we take ‘every a’, and in (PInd) we do not. This is because in (PInd), a is α-convertible,

10.7 Building an interpretation for .L from one for L

Recall the PNL signature .L from Subsection 10.1. Suppose M is a model of arithmetic. We use it to build an interpretation N of .L.

Definition 10.7.1

Extend L to L+M where we add all elements of M as constants, and extend the interpretation to interpret these constants as themselves in M. (So if x ∈M then x is a constant symbol in L+M and ⟦x⟧M ε = x.)

Define an Aν-valuation ε0 ∈ Valu𝔸ν (M) by

ε0(a) = 0Malways.

If t is a term, we write ⟦t⟧M for the function λε.⟦t⟧M ε . If ξ is a formula, we write ⟦ξ⟧M for the function λε.⟦ξ⟧M ε .

We now define an interpretation N for .L. We give a denotation to the base sorts ι and o of .L, as follows:

ιN = {⟦t⟧M | t a term of L+M} oN = {⟦ξ⟧M | ξ a formula of L+M}

We give a denotation to the term-formers and proposition-formers of .L, as follows:

varN a ε = ε(a).0N ε = 0M.succN u ε = succM(uε).+N (u, v) ε = +M(uε, vε) .∗N (u, v) ε = ∗M(uε, vε)subN ι ([a]u, v) ε = u(ε[a:=vε]). ⊥N ε = 0subN o ([a]u, v) ε = u(ε[a:=vε]) .⇒N (U, V ) ε = max{1−U(ε), V (ε)}. ∀N [a]U ε = min{U(ε[a:=x]) | x ∈M} .≈N (u, v) ε = ≈M(uε, vε) ≈N ι (u, v) = 1 if u=v and 0 otherwise ≈N o (U, V ) = 1 if U=V and 0 otherwise ϵN U = U(ε0)

Here, u and v range over ιN and U and V range over oN.

Lemma 10.7.2

1. ⟦t′[a:=t]⟧M ε = ⟦t′⟧M ε[a:=⟦t⟧M ε ].

2. ⟦ξ[a:=t]⟧M ε = 1 if and only if ⟦ξ⟧M ε[a:=⟦t⟧M ε ] = 1.

Lemma 10.7.3

The following equalities all hold:

varN(a) = ⟦a⟧M.0N = ⟦0⟧M.succN(⟦t⟧M) = ⟦succ(t)⟧M.+N(⟦t′⟧M, ⟦t⟧M) = ⟦t′ + t⟧M.∗N(⟦t′⟧M, ⟦t⟧M) = ⟦t′ ∗t⟧MsubN ι ([a]⟦t′⟧M, ⟦t⟧M) = ⟦t′[a:=t]⟧MsubN o([a]⟦ξ⟧M, ⟦s⟧M) = ⟦ξ[a:=s]⟧M. ⊥N = ⟦⊥⟧M.⇒N(⟦ξ′⟧M, ⟦ξ⟧M) = ⟦ξ′ ⇒ξ⟧M. ∀N([a]⟦ξ⟧M) = ⟦∀a.ξ⟧M.≈N(⟦r⟧M, ⟦s⟧M) = ⟦r ≈s⟧M
Proof

We compare Definitions 10.7.1 and 10.5.4. Most cases are immediate; we consider only the slightly less trivial ones:

varN(a) = (λa.λε.ε(a))a Definition 10.7.1= (λa.⟦a⟧M)a Definition 10.5.4= ⟦a⟧MfactsubN ι ([a]⟦t′⟧M, ⟦t⟧M) = λε.⟦t′⟧M(ε[a:=⟦t⟧Mε]) Definition 10.7.1= λε.⟦t′[a:=t]⟧MLemma 10.7.2

Other cases are no harder. ■

Lemma 10.7.4

N (Definition 10.7.1) is a PNL interpretation.

Proof

We must check that:

• ιN and oN are permissive-nominal sets. By routine calculations. (In fact, ιN and oN are nominal sets; that is, their elements all have finite support.)

• The functions defined in Definition 10.7.1 map elements of ιN, oN, [A]ιN, and [A]oN correctly to the appropriate sets. By Lemma 10.7.3.

• ϵN is equivariant from oN to {0, 1}. By routine calculations using the fact that (a b)·ε0 = ε0.

■

Lemma 10.7.5

If (Ξ ⊢χ). is valid in N, then Ξ ⊢χ is valid in M.

Proof

We calculate that if (Ξ ⊢χ). is valid in N, then

⟦(ξ1 ∧. . . ∧ξk) ⇒(χ1 ∨. . . ∨χl)⟧M ε0 = 1

But the proposition written out above is closed, so for all valuations ε, ⟦(ξ1 ∧. . . ∧ ξk) ⇒ (χ1 ∨. . . ∨χl)⟧M ε = 1. ■

Recall from Notation 10.4.4 that we write S for EQU ∪ SUB ∪ FOL.

Proposition 10.7.6

The axioms of S ∪ ARITH are valid in N.

Proof

By a routine verification. We consider the axiom (. ∀) from Figure 9. We unpack definitions and see that we must prove that for every ξ in L+M,

.

• ∀x∈M.ε0[a:=x] ∈ (ξ) if and only if . .

• ε0[a:=(t) ] ∈ (ξ) for every t a term of L+M.

This follows, because L+M has a constant symbol for every x ∈M. Validity of the other axioms is no harder. ■

Theorem 10.7.7

arithmetic, Ξ ⊢χ in first-order logic if and only if

S ∪ ARITH ⊢ (Ξ ⊢χ). in PNL.

Proof

We prove two implications. The top-to-bottom implication follows using Theorem 10.4.6.

For the bottom-to-top implication, we reason as follows: Suppose S ∪ ARITH ⊢ (Ξ ⊢χ). in PNL. Choose an arbitrary interpretation M of first-order logic that is a model of arithmetic, with carrier set M. By Soundness (Theorem 9.3.6) and Proposition 10.7.6, (Ξ ⊢χ). is valid in N. By Lemma 10.7.5 Ξ ⊢χ is valid in M. M was arbitrary, so by completeness of first-order logic [Sho67, §4.2] it follows that Ξ ⊢χ is derivable. ■

11 FURTHER PROPERTIES OF PNL

11.1 More PNL theories

We briefly mention on how to express some familiar ‘nominal’ constructs in PNL.

Inductive types

Permissive-nominal logic can express the principles of nominal abstract syntax developed in [GP01].

Suppose a base sort ι, a name sort ν, and term-formers

var : (ν)ι, app : (ι, ι)ι, and lam : ([ν]ι)ι.

Fix an unknown U : ι and for brevity write φ[U:=r] as φ(r) for every φ. Suppose an axiom-scheme, for every φ:

φ(var(a)) ⇒ ∀X.(φ(X) ⇒φ(lam([a]X))) ⇒ ∀X, Y.(φ(X) ⇒φ(Y ) ⇒app(X, Y )) ⇒ ∀X.(φ(X))

Here X and Y have sort ι and we make a fixed but arbitrary choice of atom a ∈ supp(X).

We can also express this finitely, if we axiomatise a sort for predicates (as we did for arithmetic). Here is the axiom-scheme above made finite by using the theories EQU, SUB, and FOL from Section 10:

∀Z.ϵ(Z[a↦→var(a)]) ⇒ ∀X.(ϵ(Z[a↦→X]) ⇒ϵ(Z[a↦→lam([a]X))) ⇒ ∀X, Y.(ϵ(Z[a↦→X]) ⇒ϵ(Z[a↦→Y ]) ⇒ϵ(Z[a↦→app(X, Y )])) ⇒ ∀X.ϵ(Z[a↦→X])

The N quantifier

Nominal sets support the N-quantifier [GP01]. PNL also includes the N-quantifier; the way in which it does this is quite interesting, as we shall see in a moment.

N has some distinctive properties which are reflected in nominal logic (NL) and the logic of FM sets (FM):

∀x.(P(x) ⇒Na.Q(a, x)) ================== ∀x.Na.(P(x) ⇒Q(a, x))∀x.Na.Nb.(b a)·x≈x =============================Na.Nb.∀x.(a#x ⇒b#x ⇒(b a)·x≈x)

Here and below we write a double horizontal line for ‘is provably equivalent to’. N appears absent from Permissive-Nominal Logic (PNL). It is ‘hiding’ in the permission sets. Corresponding propositions are, where a, b ∉ supp(X)

∀X.(P(X) ⇒Q(a, X)) ================= ∀X.(P(X) ⇒Q(a, X))∀X.(b a)·X ≈X ============= ∀X.(b a)·X ≈X

We see from these examples that two things are happening: first, freshness conditions are hard-coded into the syntax by permission sets—and second, so is the N-quantifier.

It is interesting to consider another example. In NL/FM:

Na.P(a) ∧Na.Q(b) ================Na.Nb.(P(a) ∧Q(b))Na.P(a) ∧Na.Q(b) ==============Na.(P(a) ∧Q(a))

Correspondingly in PNL we have:

P(a) ∧Q(b) ========= P(a) ∧Q(b)P(a) ∧Q(b) ========= P(a) ∧Q(a)

It is easy to use the rule (Ax) from Figure 5 to construct a derivation proving that P(a) ∧ Q(b) and P(a) ∧ Q(a) are indeed logically equivalent in Permissive-Nominal Logic.

The π in (Ax) expresses that truth is preserved by permutative renaming, or in symbols: ⊢φ ⇔π·φ always.

A permission set S can be viewed in two ways: as giving permission to instantiate using free atoms in S—but also as a form of N for the atoms not in S.

Semantic freshness

To express in permissive-nominal algebra that a is fresh for the denotation of s it suffices to assert (b a)·s = s where b ∉ supp(s). Thus the theory of a semantic freshness predicate Fresh has one axiom Fresh(a, X) ⇔ (b a)·X = X where a ∈ supp(X) and b ∉ supp(X) (and we fill in sorts as appropriate). In PNL with equality, the axiom is ∀X.Fresh(a, X) ⇔ (b a)·X = X.

Atoms-abstraction

Atoms-abstraction can also be expressed as a theory in permissive-nominal algebra. For a base sort sort τ and name sort ν assume a base sort [ν]τ and a term-former abs : (ν, τ)([ν]τ), along with a single axiom abs(a, X) = abs(b, (b a)·X) where a ∈ supp(X) and b ∉ supp(X). In PNL with equality, the axiom is ∀X.abs(a, X) = abs(b, (b a)·X).

11.2 Admissibility of Cut

We indicate how (Cut) is admissible in the presence of the other rules in Figure 5.

Definition 11.2.1

Suppose fa(r) ⊆ supp(X) and r : sort(X). Define Φ[X:=r] by

Φ[X:=r] = {φ[X:=r] | φ ∈Φ}.

Lemma 11.2.2 is proved by routine arguments like those in [DGM10; UPG04]:

Lemma 11.2.2

Suppose Y ∉ fV (t). Then

r[Y :=u][X:=t] = r[X:=t][Y :=u[X:=t]].
Lemma 11.2.3

Suppose fa(r) ⊆ supp(X) and r : sort(X). Then

Φ ⊢Ψ implies Φ[X:=r] ⊢Ψ[X:=r].
Proof

By a routine induction on derivations. The case of (Ax) uses Lemmas 3.4.10 and 11.2.2. The case of (∀L) uses Lemma 11.2.2. ■

Lemma 11.2.4

1. If there exists a derivation ∆ of Φ ⊢ψ, Ψ then there exists a derivation of Φ ⊢π·ψ, Ψ.

2. If there exists a derivation ∆ of Φ, φ ⊢ Ψ then there exists a derivation of Φ, π·φ ⊢ Ψ.

Proof

By a simultaneous induction on ∆. The case of (∀L) uses Lemma 3.4.10. (We need the simultaneous induction for (⇒L) and (⇒R), since parts of the proposition move between left and right.) ■

Notation 11.2.5

An instance of (Cut) rests on two sub-derivations. It is convenient to call them the left branch and right branch as illustrated:

··· Left branch Φ, φ ⊢Ψ··· Right branch Φ ⊢φ, Ψ(Cut)Φ ⊢Ψ
Theorem 11.2.6 (Cut-elimination).

If Φ ⊢ Ψ is derivable with a derivation that uses (Cut), then it is derivable with a derivation that does not use (Cut).

Proof

The proof is as for first-order logic. The only differences are a π in (Ax) and a side-condition fa(r) ⊆ supp(X) in (∀L). These affect terms and have no effect on the structure of derivations; for the purposes of this proof they are irrelevant.

We commute instances of (Cut) upwards, as usual, following the method of [Dum77, pages 139-145] or [Gab11a]. At each step, the following measure based on the depth of subderivations and the size of the cut formula, decreases:

• The size of the cut formula, and

• the longest path up the derivation the cut, that the formula persists,

lexicographically ordered.

• The commutation cases between rules for ⇒ and ∀ are as standard for first-order logic.

• The essential case for ⇒ is as standard.

• For the essential case for ∀, suppose the subderivation has the following form:

Φ, φ[X:=r] ⊢Ψ(∀L)Φ, ∀X.φ ⊢Ψ··· ∆ Φ ⊢φ, Ψ(∀R)Φ ⊢∀X.φ, Ψ(Cut)Φ ⊢Ψ

By Lemma 11.2.3 there is a derivation ∆[X:=r] of Φ ⊢φ[X:=r], Ψ. We eliminate the essential case as follows:

Φ, φ[X:=r] ⊢Ψ··· ∆[X:=r] Φ ⊢φ[X:=r], Ψ(Cut)Φ ⊢Ψ

• Suppose the subderivation has the following form:

(Ax)Φ, φ ⊢π·φ, Ψ··· ∆ Φ, π·φ ⊢Ψ(Cut)Φ, φ ⊢Ψ

We use Lemma 11.2.4 to obtain a derivation ∆′ of Φ, φ ⊢ Ψ (the transformations involved in the proof of Lemma 11.2.4 do not increase the inductive measure).

■

11.3 Exhausting the available atoms

We conclude with a brief discussion on a subtle point in the PNL design. Suppose a name sort ν, a base sort τ, and a proposition former # : (ν, τ). Suppose an atom a and an unknown X : τ with supp(X) = A< . Suppose an unknown Y : ν with supp(Y ) = A<. Consider an interpretation in which #(a, X) is interpreted as a ∉ supp(ς(X)) and τ is interpreted as L (Definition 2.4.4).

That is, # is interpreted as freshness and τ is interpreted as well-orderings of permission-sets.

In the PNL of this paper, the interpretation of the proposition φ = ∀X.∃Y.#(Y, X) is false: we take ς(X) to well-order A< and there is no a ∈ supp(Y) such that a ∉ supp(ς(X)).

Suppose we decide that we want a version of PNL in which φ is true. In this case, we can consider denotations such that every element has support of the form π·A≪ where A≪ is infinite and A≪⊆A< and A< \ A≪ is also infinite. In this way, an unknown X cannot ‘exhaust’ A<.

The lesson we draw from this small example is that nominal semantics offer a host of interesting and inspiring design options. In this paper, we have cut one path through this design space which is expressive enough to get the results we want. Other paths are possible.

12 CONCLUSIONS

This paper reflects a research arc by the author in collaboration with others, roughly from 2005 to 2012. Thanks to improvements in presentation and the use of permissive-nominal techniques, definitions and proofs are simpler than in previous literature, and new properties emerge.

We have constructed permissive-nominal sets. We gave a nominal syntax for them and explored their computational properties in nominal unification and rewriting. We considered nominal algebra and proved soundness, completeness, and HSP over permissive-nominal sets. We gave nominal terms a ∀-quantifier over unknowns and used this to build a first-order logic permissive-nominal logic. Finally, in an extended case study we gave finite axiomatisations of first-order logic and arithmetic and proved correctness.

Mathematical foundations influence language, and (famously) language influences thought. Nominal sets are a foundation with a model of names which is different from what has been considered before, so the question is: what new languages, and new thoughts, can emerge? This chapter attempts to address that question by illustrating the broad sweeps of what a ‘nominal’ meta-mathematics might look like.

We are not and cannot be encyclopaedic or exhaustive. For other work we should mention αProlog, which allows Horn clauses [CU08] (this preceded PNL, and could be viewed as a subset of it). The author in collaboration has proved correctness for several non-trivial theories in nominal syntaxes, including equational treatments of substitution [GM06a; GM08a], λ-calculus [GM08b; GM10], and first-order logic [GM06c; GM08c], as well as the finite first-order nominal axiomatisation of arithmetic [DG10; DG12a] which we considered in Section 10. There are translations from nominal terms to λ-terms by Levy and Villaret and by Dowek, the author, and Mulligan [LV08; DGM10], including a translation of algebraic reasoning (so, not just unification) [GM09b]; and there is a translation of permissive-nominal logic to higher-order logic in [DG12b] which illustrates the differences and similarities of the two logics, and exploits some unusual model-theoretic ideas.

We also mention a translation of nominal terms to many-sorted first-order syntax by Kurz and Petrişan [KP10], and a categorical treatment of nominal Lawvere theories in [Clo09]. It may also prove useful to consider nominal languages over nominal structures other than sets, for instance over nominal domains [Tur09].

See also the ‘atlas of nominal languages’ in Appendix A.

This research is developing a topic which this author believes could become an immense field; the informal meta-level having been relatively unformalised until now for want of a denotation with names, which is what nominal sets provide.

It is important to realise that this story is not just about nominal sets, nor is it just about semantics; there is also the issue of finding appropriate syntaxes for our semantics. The logic of FM sets, nominal logic, and the Nominal Isabelle package [GP01; Pit03; Urb08] are all first-order axiomatisations of nominal sets.19 In all these cases, the syntax is that of ‘ordinary’ first- or higher-logic.20 These are denotations for syntax-with-binding.

Nominal terms and permissive-nominal terms, and the syntaxes based on them such as nominal rewriting, algebra, and permissive-nominal logic, do not follow automatically from nominal sets. They are syntaxes for meta-mathematics of independent interest. Thus, this chapter has surveyed the author’s attempts, via methods which are both syntactic and also semantic, to outline what meta-mathematics could look like if it were based on nominal foundations. The fact that—for instance—we were able to finitely axiomatise arithmetic in the nominal first-order that is PNL in Subsection 10.2, is one demonstration that this meta-mathematics is a new and different place from what the reader may be used to.

In a sense this paper is a sequel to the survey of [Gab11b] (written in 2008 and submitted in early 2009). But whereas [Gab11b] concentrated on applications of nominal sets to syntax with binding, this paper considers nominal sets as a basis for meta-mathematics. Hints of this appeared in nominal rewriting [FGM04; FG07], which allowed arbitrary oriented equality theories over nominal terms. Perhaps unwisely, we shall succumb to a wordplay: [Gab11b; GP01] explore denotation of specification with binding; whereas here we explore specification of denotation with binding.

Thus, in this document we have explored the consequences of taking FM-sets style names seriously in meta-mathematics. But even that does not exhaust the potential applications of nominal techniques. Mathematics and computer science are evolving in ways which increase the importance of names, and nominal techniques have arisen

from this; we can expect that evolution to continue.

This motivates us to revisit certain foundational design decisions; whether to admit atoms—to sound more mathematical, we say urelemente and to sound less mathematical, we say names—and what properties these should have. Linguists might well call these referents, and have been studying them for a long time.

Whatever we call them, they exist and we use them all the time. So we will conclude with two slogans:

• Names are data.

• Names with additional properties are ubiquitous.

This chapter has studied formal languages with which to specify some of the possible additional properties of names, such as ‘having a substitution action’ or ‘being universally quantifiable’. But more generally, by this combination of a new point of view and a rigorous mathematics, nominal techniques have the potential to simplify, factor out common properties, and help control some of a modern mathematics of logic and computation.

Names are not just a technical issue, to be ignored or circumvented with ‘tricks’. Names are a philosophical, foundational, linguistic, and computational issue. The mathematics of names is the mathematics of mathematics.

Dov Gabbay wrote in his preface to the second edition that

the researcher ... is having more and more in common with the tradi-tional philosopher who has been analysing such questions for centuries (unrestricted by the capabilities of any hardware). ... I believe the day is not far away in the future when the computer scientist will wake up one morning with the realisation that he is actually a kind of formal philosopher!

We would add “and philosophers, linguists—and some artists too—may wake up one morning with the realisation that they are actually a kind of abstract computer scientist”. Amen.

BIBLIOGRAPHY

[ACCL91] Martín Abadi, Luca Cardelli, Pierre-Louis Curien, and Jean-Jacques Lévy. Explicit substitutions. Journal of Functional Programming, 1(4):375–416, 1991.

[Bir35] Garrett Birkhoff. On the structure of abstract algebras. Proceedings of the Cambridge Philosophical Society, 31:433–454, 1935.

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

[BS81] Stanley N. Burris and H. P. Sankappanavar. A Course in Universal Algebra. Graduate texts in mathematics. Springer, 1981.

[Cal10] Christophe Calvès. Complexity and implementation of nominal algorithms. PhD thesis, King’s College London, 2010.

[Che04] James Cheney. The complexity of equivariant unification. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), volume 3142 of Lecture Notes in Computer Science, pages 332–344. Springer, 2004.

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

[Che05b] James Cheney. A simpler proof theory for nominal logic. In FoSSaCS, volume 3441 of Lecture Notes in Computer Science, pages 379–394. Springer, 2005.

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

[Che10] James Cheney. Equivariant unification. Journal of Automated Reasoning, 45(3):267–300, October 2010.

[Clo07] Ranald Clouston. Closed terms (unpublished notes). http://users.cecs.anu.edu.au/\~rclouston/closedterms.pdf, 2007.

[Clo09] Ranald Clouston. Equational logic for names and binding. PhD thesis, University of Cambridge, UK, 2009.

[Clo11] Ranald Clouston. Nominal Lawvere theories. In Proceedings of the 18th International Workshop on Logic, Language, and Information (WoLLIC), volume 6642 of Lecture Notes in Computer Science. Springer, 2011.

[CP07] Ranald A. Clouston and Andrew M. Pitts. Nominal equational logic. In Computation, Meaning and Logic: Articles dedicated to Gordon Plotkin, volume 172 of Electronic Notes in Theoretical Computer Science, pages 223–257. Elsevier Science, 2007.

[CU03] James Cheney and Christian Urban. System description: Alpha-Prolog, a fresh approach to logic programming modulo alpha-equivalence. In UNIF’03, pages 15–19. Universidad Politécnica de Valencia, 2003.

[CU08] James Cheney and Christian Urban. Nominal logic programming. ACM Transactions on Programming Languages and Systems (TOPLAS), 30(5):1–47, 2008.

[DG10] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010), pages 165–176, New York, 2010. ACM Press.

[DG12a] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Transactions on Computational Logic, 13(3), 2012.

[DG12b] Gilles Dowek and Murdoch J. Gabbay. PNL to HOL: from the logic of nominal sets to the logic of higher-order functions. Theoretical Computer Science, 451:38–69, 2012.

[DGM09] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. In Proceedings of the 24th Italian Conference on Computational Logic (CILC’09), 2009.

[DGM10] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification: an infinite, co-infinite approach to nominal techniques (journal version). Logic Journal of the IGPL, 18(6):769–822, 2010.

[DJ89] Nachum Dershowitz and Jean-Pierre Jouannaud. Rewrite Systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Formal Methods and Semantics, volume B. North-Holland, 1989.

[Dow01] Gilles Dowek. Higher-order unification and matching. In Handbook of automated reasoning, pages 1009–1062. Elsevier, 2001.

[Dum77] Michael Dummett. Elements of intuitionism. Clarendon Press, 1 edition, 1977.

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

[FG10] Maribel Fernández and Murdoch J. Gabbay. Closed nominal rewriting and efficiently computable nominal algebra equality. In Electronic Proceedings in Theoretical Computer Science, volume 34, pages 37–51, 2010.

[FGM04] Maribel Fernández, Murdoch J. Gabbay, and Ian Mackie. Nominal Rewriting Systems. In Proceedings of the 6th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming (PPDP 2004), pages 108–119. ACM Press, August 2004.

[FH92] Matthias Felleisen and Robert Hieb. The revised report on the syntactic theories of sequential control and state. Theoretical computer science, 103(2):235–271, 1992.

[FH10] Marcelo Fiore and Chung-Kil Hur. Second-order equational logic. In Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL 2010), Lecture Notes in Computer Science. Springer, 2010.

[FPT99] Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi. Abstract syntax and variable binding. In Proceedings of the 14th IEEE Symposium on Logic in Computer Science (LICS 1999), pages 193–202. IEEE Computer Society Press, 1999.

[Gab01] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, University of Cambridge, UK, March 2001.

[Gab05] Murdoch J. Gabbay. Axiomatisation of first-order logic (talk). In Second workshop on Computational Aspects of Nominal sets (CANS’05). King’s College, London, December 2005.

[Gab07a] Murdoch J. Gabbay. Fresh Logic. Journal of Applied Logic, 5(2):356–387, June 2007.

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

[Gab09] Murdoch J. Gabbay. Nominal Algebra and the HSP Theorem. Journal of Logic and Computation, 19(2):341–367, April 2009.

[Gab11a] Michael Gabbay. A proof-theoretic treatment of lambda-reduction with cut-elimination: lambda calculus as a logic programming language. Journal of Symbolic Logic, 76(2):673–699, June 2011.

[Gab11b] Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.

[Gab11c] Murdoch J. Gabbay. Two-level nominal sets and semantic nominal terms: an extension of nominal set theory for handling meta-variables. Mathematical Structures in Computer Science, 21:997–1033, 2011.

[Gab12a] Murdoch J. Gabbay. Meta-variables as infinite lists in nominal terms unification and rewriting. Logic Journal of the IGPL, 2012.

[Gab12b] Murdoch J. Gabbay. Unity in nominal equational reasoning: The algebra of equality on nominal sets. Journal of Applied Logic, 10:199–217, June 2012.

[GC04] Murdoch J. Gabbay and James Cheney. A Sequent Calculus for Nominal Logic. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 139–148. IEEE Computer Society, July 2004.

[Gen35] Gerhard Gentzen. Untersuchungen über das logische Schließen [Investigations into logical deduction]. Mathematische Zeitschrift 39, pages 176–210,405–431, 1935. Translated in [Sza69], pages 68–131.

[GH08] Murdoch J. Gabbay and Martin Hofmann. Nominal renaming sets. In Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), pages 158–173. Springer, November 2008.

[GM06a] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC 2006: Theoretical Aspects of Computing, volume 4281 of Lecture Notes in Computer Science, pages 198–212, November 2006.

[GM06b] Murdoch J. Gabbay and Aad Mathijssen. Nominal Algebra. In 18th Nordic Workshop on Programming Theory, October 2006.

[GM06c] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order logic. In Proceedings of the 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2006), pages 189–200. ACM, July 2006.

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

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

[GM08b] Murdoch J. Gabbay and Aad Mathijssen. The lambda-calculus is nominal algebraic. In Christoph Benzmüller, Chad Brown, Jörg Siekmann, and Rick Statman, editors, Reasoning in simple type theory: Festschrift in Honour of Peter B. Andrews on his 70th Birthday, Studies in Logic and the Foundations of Mathematics. IFCoLog, December 2008.

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

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

[GM09b] Murdoch J. Gabbay and Dominic P. Mulligan. Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables. In Proceedings of the 4th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2009), pages 64–73. ACM, August 2009.

[GM10] Murdoch J. Gabbay and Aad Mathijssen. A nominal axiomatisation of the lambda-calculus. Journal of Logic and Computation, 20(2):501–531, April 2010.

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

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

[KP10] Alexander Kurz and Daniela Petrişan. On universal algebra over nominal sets. Mathematical Structures in Computer Science, 20:285–318, 2010.

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

[LV10] Jordi Levy and Mateu Villaret. An efficient nominal unification algorithm. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA 2010), volume 6 of Leibniz International Proceedings in Informatics (LIPIcs), pages 209–226. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2010.

[LV12] Jordi Levy and Mateu Villaret. Nominal unification from a higher-order perspective. Transactions on Computational logic (TOCL), 13(2), 2012.

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

[Mel95] Paul-André Melliès. Typed lambda-calculi with explicit substitutions may not terminate. In Mariangiola Dezani-Ciancaglini and Gordon D. Plotkin, editors, Proceedings of the 2nd International Conference on Typed Lambda Calculi and Applications, (TLCA 1995), volume 902 of Lecture Notes in Computer Science, pages 328–334. Springer, April 1995.

[MM92] Saunders Mac Lane and Ieke Moerdijk. Sheaves in Geometry and Logic: A First Introduction to Topos Theory. Universitext. Springer, 1992.

[MNPS89] Dale Miller, Gopalan Nadathur, Frank Pfenning, and Andre Scedrov. Uniform proofs as a foundation for logic programming. Technical report, Durham, NC, USA, 1989.

[Pit01] Andrew M. Pitts. Nominal logic: A first order theory of names and binding. In N. Kobayashi and B. C. Pierce, editors, Proc. 4th Int’l Symposium on Theoretical Aspects of Computer Software (TACS 2001), volume 2215 of Lecture Notes in Computer Science, pages 219–242. Springer, 2001.

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

[Pit11] Andrew Pitts. Nominal sets and their applications. In Midlands Graduate School (MGS 2011), 11-15 April 2011. available online at cl.cam.ac.uk/\~amp12/talks/MGS2011_nominal_sets_ slides.pdf.

[Pra65] Dag Prawitz. Natural deduction: a prooof-theoretical study. Almquist and Wiksell, 1965. Reprinted by Dover, 2006.

[Sho67] Joseph Shoenfield. Mathematical Logic. Addison-Wesley, 1967.

[Smu68] Raymond Smullyan. First-order logic. Springer, 1968. Reprinted by Dover, 1995.

[Sza69] M. E. Szabo, editor. Collected Papers of Gerhard Gentzen. North Holland, 1969.

[Tur09] David C. Turner. Nominal Domain Theory for Concurrency. PhD thesis, University of Cambridge, 2009.

[Tze07] Nikos Tzevelekos. Full abstraction for nominal general references. In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), pages 399–410. IEEE Computer Society Press, 2007.

[UPG03] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. In Proceedings of the 17th International Workshop on Computer Science Logic (CSL 2003), volume 2803 of Lecture Notes in Computer Science, pages 513–527. Springer, December 2003.

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

[Urb08] Christian Urban. Nominal reasoning techniques in Isabelle/HOL. Journal of Automatic Reasoning, 40(4):327–356, 2008.

Appendix

A AN ATLAS OF NOMINAL LANGUAGES

The reader coming to the nominal literature could be forgiven for finding it perplexing. What are ‘Fraenkel-mostowski sets’, ‘nominal sets’, ‘nominal terms’, ‘nominal logic’, ‘nominal rewriting and algebra’, ‘αProlog’, ‘nominal equational logic’, ‘permissive-nominal algebra’, ‘permissive-nominal logic’ (with/without shift-permutations)? In this Appendix we will give a brief annotated bibliography covering, loosely, the relevant publications. This list is not meant to be exhaustive.

Traditionally, nominal sets are understood as a tool for the mathematical analysis of syntax, as described for instance in the author’s previous survey/research paper [Gab11b], or in slides of an excellent course of lectures by Pitts [Pit11]. This author takes a view of nominal sets not just as a foundation for syntax with binding, but as a foundation for mathematics itself—names and binding, after all, appear everywhere. The atlas below surveys relevant publications.

For each item in the list below, we reference where the idea was introduced to the ‘nominal’ literature, and any other relevant conference and journal papers.

FM set theory [GP99; GP01]. Fraenkel-Mostowski set theory (FM) and nominal sets (called ‘equivariant FM sets’ in that paper) are the foundational semantics for nominal techniques.

Fraenkel-Mostowski sets were already known and had been used for other purposes; see [Gab11b, Remark 2.22] for more detailed historical comments. Nominal sets were familiar as e.g. the Schanuel topos. So both semantics were known.

What was new to [GP01] was the observation by the author and Pitts of the notions of support, atoms-abstraction, the self-dual behaviour of the N quantifier, and the application to what is now called nominal abstract syntax.21

Nominal logic [Pit01; Pit03]. The constructions of [GP01] are repeated, but in a first-order axiomatisation of nominal sets rather than one of the FM cumulative hierarchy. Pitts also coined the catchy label ‘nominal’.

Sometimes authors identify the nominal logic of [Pit03] with nominal techniques in general. This is limiting, and it gets the mathematical development the wrong way round. Nominal logic is a Hilbert-style axiomatisation in first-order logic. These axioms have meaning because of the underlying nominal sets models, and not the other way around; nor does the axiomatisation per se contribute to new syntax or proof-theory with which to study names.

In order to make progress, we needed new syntax that more explicitly represents atoms and their properties.

Thus for instance the nominal logic programming developed by Cheney and Urban

[CU08] (also referenced below) is called logic-programming in nominal logic, but we also see from Figures 6, 7, and 8 of [CU08] that the syntax and axioms used are a variant of nominal terms.

Proof-theories for the N-quantifier [Gab07a; GC04; Che05b]. Some attempts have been made to give the distinctive N-quantifier of nominal techniques, a proof-theory. In arguably increasing order of elegance these are [Gab07a] (this was received by the journal in 2003 but took four years to get printed), [GC04] (written with Cheney to develop on [Gab07a]), and [Che05b].

The permissive-nominal logic (PNL) of this survey is another item on that list, and perhaps it is one of the nicest; certainly the PNL treatment of N is very different from what has come before, see Subsection 11.1.

Complete semantics for this family of logics are in [Gab07a], [Che06], and in

[DG12a]. See also Subsection 9.4 of this survey.

Nominal terms [UPG03; UPG04]. This new syntax introduced the distinctive freshness side-conditions and the nominal terms syntax, with its separation of atoms a and unknowns X into two syntactic classes. [UPG04] is where the syntactic ideas of this survey were born, if not the specific ‘permissive’ implementation, which came later (permissive-nominal terms below).

There is now quite a substantial body of work devoted to computing efficiently on nominal terms; notably [Cal10; LV10]. There is also a body of work devoted to translating between nominal terms and higher-order patterns [MNPS89]. We are far from exhaustive, but good places to start reading are [Che05a], [LV08; LV12], and [GM09b; DGM10].

Nominal rewriting [FGM04; FG07] and αProlog [CU03; CU08]. These were the first logical languages using nominal terms as a general-purpose assertion language; nominal rewriting was designed explicitly to allow us to assert (directed) equalities between terms such as β or η-equivalence. αProlog was intended by its designers for reasoning on nominal abstract syntax, and explicitly presented as such— but in retrospect it can also be viewed as a general-purpose ‘nominal’ reasoning system in the same family as nominal rewriting and later work.22

Nominal algebra [Gab05; GM06a; GM07; GM09a]. Nominal algebra is simply the undirected version of nominal rewriting.23 What makes nominal algebra interesting above and beyond nominal rewriting is the different theorems we prove about equality instead of rewriting; for instance the HSPA theorem of [Gab09] (much simplified here in Section 8), and various correctness results for axiomatisations of e.g. substitution, λ-calculus, and first-order logic [GM06a; GM08a; GM06c; GM08b; GM08c; GM10].

The paper [GM06a] is where the permutative convention of Definition 2.1.2 was introduced, used by the author consistently since then. This comes from the author’s work formalising nominal reasoning in Isabelle in [Gab01] and spares us from having to explicitly enumerate all inequalities between atoms. Thus, if pressed to be entirely formal, ‘a and b’ refers to two meta-variables ranging over distinct atoms.

Kurz and Petrişan proved an HSP theorem for nominal algebra by treating nominal algebra as a kind of many-sorted first-order logic [KP10]—the sorts are finite sets of atoms and come from the categorical view of nominal sets as presheaves. The effect of nominal theories can thus be attained in many-sorted first-order syntax. That syntax is just standard first-order syntax is potentially a big advantage, for instance if one wants to transfer results directly from universal algebra. This offers alternative and effective methods of semantic proof; e.g. [KP10] significantly simplifies the proofs of [Gab09]. We pay for this convenience with infinities; e.g. even the simplest theory is infinite since equalities are replicated at every sort. Of course, the theory may still be finitely presentable. Section 8 of the current paper contains another, further simplified, HSP proof.

Nominal equational logic [CP07; Clo11]. Call the judgement ‘a is fresh for the syntax s’ syntactic freshness and ‘a is fresh for the denotation of s’ semantic freshness. Nominal Equational Logic (NEL) closely resembles NA, but whereas both have a semantic equality judgement (s = t), NEL adds a semantic freshness judgement.

In [CP07] Clouston and Pitts claimed that NEL was significantly more complete than NA because of this, but they had missed that semantic freshness is expressible using equality and syntactic freshness (see for instance [GM07, Theorem 5.5] and [GM09a, Lemma 4.51]).24

Note that two distinct logics have been called NEL: one in [CP07], and one in [Clo11] which restricts semantic freshness to the left of the turnstile; compare Figure 5 of [CP07] with Figure 1 of [Clo11]. Both have syntactic freshness: see the side-condition a#(¯a, t, t′) in the Atm-Intro and Atm-Elim rules of Figure 5, and similar side-conditions in Figure 1. Thus, when Clouston writes in [Clo11] that “[syntactic] freshness in NA is sound, but not complete, for freshness in the underlying nominal sets interpretation [semantic freshness]”, echoing similar comments in [CP07], this omits mention that NEL also has a syntactic freshness.

It is in any case a red herring. If we can choose fresh atoms and compare elements for semantic equality, then semantic freshness makes the logic ‘do equality twice’ and just adds complexity [Gab12b]—without equality, the story can be different; this was encountered in the first attempt at a nominal functional programming language, in which we included freshness information in the types [Gab01].

Permissive-nominal terms [GM09b; DGM09; DGM10]. These simplify and im-prove classical nominal terms in two ways: we give explicitly the (countably infinite) atoms that may be free / are guaranteed to be fresh in every unknown, and since freshness information is stored directly we eliminate the need for freshness contexts. Thus good properties emerge: permissive-nominal terms can be constructed as nominal abstract syntax, we can directly choose a name fresh for a term (which is not possible in nominal terms without expanding the freshness context), and properties and proofs can then be expressed for terms alone, rather than for terms-in-freshness-context.

For instance, in classical nominal terms a solution of a nominal unification problem is a pair of a substitution and a freshness context; a nominal rewrite rule is a left and a right-hand side term and a freshness context; the proof-theory of nominal algebra requires an explicit freshness rule to generate fresh atoms, and so on. In fact, manipulating nominal terms almost always requires us to manipulate an external structure representing freshness constraints.

In contrast permissive terms are ‘self-sufficient’, like ordinary syntax. Proofs and algorithms have more of the look and feel of ordinary syntax. We have seen how, in the body of this survey. A detailed treatment of permissive-nominal syntax, including a simple translation from the nominal terms of [UPG04] into permissive-nominal terms, is also in [DGM10].

Permissive-nominal algebra ([GM09b], and Section 7). The permissive-nominal algebra of Section 7 uses permissive-nominal terms and has a significantly different proof-theory.

The notable differences are, aside from being permissive-nominal, the inclusion (if we want them) of infinitely-supported constant symbols and of infinitely-supported permutations. So previous work is a special case of the general framework of this survey, but what we do here goes strictly beyond what was possible in previous work, also in some significant mathematical properties such as satisfying an HSP instead of an HSPA result; see the discussion opening Section 8.

Permissive-nominal logic ([DG10; DG12a] and Section 9). As we discuss in this survey, permissive-nominal logic (PNL) adds universal quantification over unknowns X. This is non-evident for nominal terms because of their freshness contexts; in nominal terms X behaves like an element with cofinite support so we lose α-equivalence whereas in permissive-nominal terms X has coinfinite support and we can always α-rename bound atoms. We get a proof-theory which is pleasingly close to that of first-order logic, a sound and complete semantics, and we can axiomatise and prove correct a non-trivial and mathematically relevant theory, such as arithmetic.

NOMINAL TERMS AND NOMINAL LOGICS 95

Figure 12: Cheat-sheet of nominal languagesNameIntendedmodelRefsNotesFMsettheoryCumulativehierarchy/Cat.ofFMsets[GP99;GP01]PreviouslyusedtoproveindependenceofACNominal/FMsetsThemselves[GP99;GP01]Nominalsetscalled‘equivariantFMsets’inthesepapersNom.logicSchanueltopos/Cat.ofnom.sets[Pit01;Pit03]Statesaxiomsofnominalsets,usedword‘nominal’Nom.termsNom.sets[UPG03;UPG04]Introduceda,X,a#X,[a]X,π·XNom.rewritingNom.terms[FGM04;FG07]Firstframeworkforassertinggeneraltheo-riesonnominaltermsαPrologNom.terms[CU03;CU08]Intendedaslogicprogramminglanguageforabstractsyntax,butcanbeviewedmoregenerallyNom.algebraNom.sets[Gab05;GM06a;GM07;GM09a]Axiomatisation&modelsforbinderslike[a↦→t],λa,∀aNom.equationallogicNom.sets/Nom.LawvereTheories[CP07;Clo09]Alsoprovidessemanticsfornominalalge-braPermissive-nom.termsNom.setsorpermissive-nom.sets[DGM09;GM09b;DGM10]Eliminatefreshnesscontexts;addshift-permutation;standardiseα-equivalencePermissive-nom.algebraPermissive-nom.setsornom.sets[GM09b],thissurveyMoreexpressive,esp.inpresenceofshift-permutationPermissive-nom.logicPermissive-nom.setsornom.sets[DG10;DG12a],thissurveyAfirst-orderlogicfornom.termsFigure12:Cheat-sheetofnominallanguages

INDEX

arithmetic axiomatisation in PNL, 78 in PNL, 73 nominal model of, 78 atoms, 8 abstraction of, 15 explicit atoms of nominal term, 47 splitting set of, 8 de Bruijn shift function, 29 equivariance equivariant element, 13 equivariant extension, 17 First-order logic for PNL, 76 nominal interpretation of, 77 freshness using equality, 58 homomorphism of nominal algebra interpretations, 60 HSP/Birkhoff’s theorem, 64 lambda-calculus as a nominal algebra, 51 NEW quantifier, 82 nominal atlas of nominal languages, 91 atoms abstraction, 15 permission set, 11 permissive-nominal set, 12 rewrite rule, 39, 40 strong support, 17 support, 12 basic properties of, 15 term, 20 term signature, 19nominal algebra axiomatisation of λ-calculus, 51 axiomatisation of substitution, 51 completeness, 57 derivable equality, 52 equality judgement, 50 HSP/Birkhoff’s theorem, 64 interpretation free term model, 56 ground free term interpretation, 62 homomorphic image, 60 homomorphism of, 60 signature, 53 sorts, 53 subalgebra, 61 terms, 54 model, 54 soundness, 55 theory, 50 validity, 54 valuation, 53 variety, 64 nominal rewriting, 40 (joinable) peak, 41 closed rewrite rule, 49 confluent, 41 locally confluent, 41 normal form, 43 orthogonal rewrite theory, 44 parallel reduction, 44 position/context, 40 rewrite rule, 39 uniform rule, 42 nominal term atomic substitution, 23 closed, 48 constants of, 63 explicit atoms of, 47 fa-functional, 48 free atoms of, 22
ground term, 62 interpretation of, 54 occurrences in, 29 permissive-nominal terms, 20 position/context, 40 signature, 19 substitution, 23 substitution action, 24 support of, 21 unknowns of, 22 nominal unification instantiation ordering, 36 simplification, 31 solution, 31 principal/most general solution, 36 unification algorithm, 33 correctness of, 38 Permissive-nominal logic, see PNL permutation group of permutations, 9 permutation orbit, 15 permutative convention, 9 set with a permutation action, 12 shift permutation, 10, 26 swapping/transposition, 9 permutative convention, 8, 9 PNLadmissibility of Cut, 83 arithmetic completeness of finite axioma- tisation of, 77 soundness and completeness of finite axiomatisation of, 81 axiomatisation of arithmetic, 78 completeness, 72 derivable sequent, 66 interpretation, 68 NEW quantifier, 82 nominal abstract syntax in, 81 proposition, 66 interpretation of, 68 maximally consistent set of, 70 valid, 69 sequent, 66signature, 65 soundness, 69 term interpretation, 71 substitution as a nominal algebra, 51 support, 12 strong support, 17

Notes

1In other papers, such as [UPG04], permission sets are presented instead as syntactic freshness assumptions. ↩

2The development here is a little different from that in [DGM10] because we take permission sets to be sets of the form π·A< instead of sets of the form (A< \ A) ∪B. ↩

3This example modified from an example by Bartek Klin; private communication from Alexander Kurz. ↩

4 If all permutations in P are finite then we have as a Technical Lemma that the existence of some supporting set implies the existence of a unique least small supporting set. In the more general case where infinite permutations are allowed, it is possible to construct a set with a permutation action X and x ∈|X| such that x has a supporting set but does not have a unique least small supporting set. See [Gab07b, Lemma 21] for an example. An intermediate state is to admit infinite permutations but restrict the notion of support to consider only the finite ones. We do this in Definitions 3.1 and 3.2 and Remark 3.3 of [DG12a]. For this paper, none of this will matter directly. ↩

5Using possibly repeated powersets, arbitrarily complex structures may be constructed. Thus this example guarantees an inexhaustible supply of arbitrarily large and complex structures with which to model ...almost anything we can imagine. The survey [Gab11b] explores this in detail. ↩

6For clarity, note that we intend this set to not have a permutation action. Or, we can take this to be a nominal set with the trivial action (Definition 2.4.2). We have in mind N. ↩

7Details of how induction on nominal abstract syntax allows us to α-convert and make freshness assumptions, are the topic of [Gab11b]. A less fancy proof of both implications by a standard induction— so not this new-fangled nominal nonsense—on terms not quotiented by α-equivalence, is in Appendix A of [DGM10], proof of Lemma 4.15 on page 50. We leave it to the reader to judge which is the nicer proof. ↩

8Taking the inverse here saves writing -1 quite so many times in Definition 3.6.9, and is harmless since permutations are invertible. ↩

9We write typewriter font to avoid confusion between the symbols used in [UPG04] (which have no support) and the elements X ∈X used in this paper (which do have support). To see how to travel between these two worlds see part 2 of Example 3.1.7, or [DGM10]. ↩

10The specific choice does not matter. Intuitively this is because permutations are invertible so any one choice and be undone and redone at will. A more formal statement of this is Theorem 4.3.6. For an example of a shift-permutation concretely constructed, see Definition 3.6.9. This algorithm generates shifts just like in [UPG04] we generated freshness conditions, and for the same reason. ↩

11We do not make this formal, but since constants are structurally just like unknowns the definitions can easily be constructed by proceeding exactly as we did when we defined substitution for unknowns. ↩

12There is a deeper reason for this: they are also closed. See Example 6.2.2 and Theorem 6.2.3. ↩

13The interested reader can begin by comparing our notion of closed terms in Definition 6.1.7, based on two simpler inductive definitions, with that used in [FG07, Definition 68], based on a renamed variant of a term and an equality derivable in an extended freshness context. See also an inductive characterisation of closed terms in unpublished notes [Clo07]. ↩

14In words: ‘a is fresh for x if for some/any fresh b, (b a)·x = x’ and ‘for some/any fresh b, [b](b a)·x = [a]x’. ↩

15In [GM09a] to build the free term model we enriched syntax with n-ary term-formers applied to atoms. This idea goes back to a completeness proof in [Gab07a]. ↩

16That is:

– aX = aY for every atom a. – (x1, . . . , xn)X = (x1, . . . , xn)Y for every x1 ∈|⟦α1⟧X|, ..., xn ∈|⟦αn⟧Y|. – [a]Xx = [a]Yx for every x ∈|⟦α⟧X|. – For every term-former f in F, fX(x) = fY(x) for every x ∈|⟦α⟧X| where ar(f) = (α)τ.
↩

17The reader who would answer ‘Can you pass the salt?’ with ‘Yes.’ should note that we have to adjust ar to remove P and add X mapping X to α where (π, Xα) ∈X. ↩

18For instance, in permissive-nominal sets it is possible represent a well-order of each permission set, but not to represent a well-ordering of the set of all atoms (which is a limit of permission sets). This is also the feature which Fraenkel and Mostowksi used to prove the independence of the axiom of choice from the other axioms of set theory. ↩

19Essentially, [GP01] is the first third of the author’s thesis; [Pit03] is the same but minus the cumulative sets hierarchy; and [Urb08] is an extensive implementation in higher-order logic, with a library of powerful macros. One reason this is non-trivial has to do with automatically deriving the equivariance properties described e.g. in [Gab11b, Subsection 4.2]. ↩

20Sometimes, authors write ‘nominal logic’ for that logic obtained by adding for each atom a constant symbol to the syntax of first-order logic, and adding infinitely many axioms reflecting nominal sets (equalities of swapping atoms, fresh atoms, and so on). This is nominal sets wearing a ‘syntactic disguise’: consider by analogy a theory of arithmetic with a constant symbol for each number and an axiom for every arithmetic equality. ↩

21At the same time, Fiore Plotkin and Turi developed an approach to abstract syntax which was really exactly the same thing [FPT99]. The key difference turned out to be that nominal sets admit a relatively elementary sets-based interpretation of the presheaves. As argued in [GH08] there are ‘fewer presheaves’ in the nominal semantics, we feel that an elementary presentation of the mathematics—where this is possible—is a powerful advantage not just for the reader but also for the practicing theorist. Fiore has continued this line of research in collaboration and produced logics which in some sense which has never been made formal, parallel the development here. For an example of this see [FH10]. ↩

22James Cheney, private communication. ↩

23Actually, this is a simplification. There is a significant difference, which is described in [FG10]: nominal rewriting does not have an explicit rule to generate fresh atoms, whereas nominal algebra does. To the level of detail we wish to go into here, this does not matter. The permissive-nominal syntax of this survey makes the issue obsolete because fresh atoms are a structural fact of the permission sets. ↩

24Syntactic freshness appears in this paper as a ∉ fa(r). We considered semantic freshness in Section 11. See also Proposition 7.6.1. ↩