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

Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables

Murdoch J. Gabbay Dominic P. Mulligan

Abstract

This paper develops the correspondence between equality reasoning with axioms using λ-terms syntax, and reasoning using nominal terms syntax. Both syntaxes involve name-abstraction: λ-terms represent functional abstraction; nominal terms represent atoms-abstraction in nominal sets.

It is not evident how to relate the two syntaxes because their intended denotations are so different. We use universal algebra, the logic of equational reasoning, a logical foundation based on an equality judgement form which is spartan but which is sufficiently expressive to encode mathematics in theory and practice.

We investigate how syntax, algebraic theories, and derivability relate across λ-theories (algebra over λ-terms) and nominal algebra theories.

Categories and Subject Descriptors F.4.1 [Mathematical logic]

Keywords Universal algebra, lambda-theories, nominal algebra, permissive nominal terms.

1. Introduction

λ-terms are a useful and important syntax in computer science. Nominal terms, from [32], have been more recently developed. What makes both λ-term syntax and nominal term syntax interesting is that they represent name-binding, but they do this in two different ways:

• The basic equality for λ-terms is αβ(η)-equivalence. The notion of substitution is capture-avoiding. The standard semantics of name-abstraction is functional abstraction.

• The basic equality for nominal terms is a generalised form of α-equivalence (without β or η). The notion of substitution is capturing. The standard semantics of name-abstraction is non-functional, and uses an atoms-abstraction construction in Fraenkel-Mostowski sets (documented in [19]).

Universal algebra, the theory of equality, is perhaps the simplest non-trivial logics. This paper develops the correspondence between derivability in equational theories over λ-terms (λ-theories), and

derivability in equational theories over nominal terms (nominal algebra theories).

This is the simplest forum within which to address the following question, which has been of interest right from the introduction of nominal techniques in [10, 19]:

“What connections can be made between reasoning using names and binding based on λ-abstraction, and between reasoning using names and binding based on nominal atoms-abstraction?”

For illustration, we consider some statements about first-order logic and λ-calculus, as written in the informal but rigorous language of mathematical discourse, and translate them to equalities on λ-terms and on permissive nominal terms:

• “If a does not occur in φ then ∀a.φ if and only if φ.”

• “If a does not occur in φ then ∀b.∃a.φ if and only if ∃a.∀b.φ.”

• “If a does not occur in t then λa.(ta) is equal to t.”

• “(λb.t)b is equal to t always.”

Suppose X is a permissive nominal unknown with permissions set p(X) = comb, and suppose b ∈ comb and a ∉ comb (so intuitively, X may be instantiated to a term mentioning b free but not mentioning a free; formal definitions are in the body of the paper). Then translations are as in the following small table:

λ-terms nominal terms∀λa.c = c ∀[a]X = X∃λa.∀λb.(cb) = ∀λb.∃λa.(cb) ∃[a]∀[b]X = ∀[b]∃[a]Xlamλa.(ca) = c lam[a](Xa) = X(lamλb.c)b = c (lam[b]X)b = X

Here, quantifiers feature as term-formers, and their binding behaviour is handled by (λ/nominal)-abstraction; this is standard. In the case of λ-terms, the possibility of capture is implemented using application. In the case of nominal terms, capture-avoidance is enforced by using names that are not in the permissions set comb.

Note here that lam is a term-former intended to represent λ-abstraction — whose behaviour, in the left-hand column but not in the right-hand column, is axiomatised using a λ-abstraction of a λ-terms syntax.

There are no types above, nor in the syntax we develop below. We believe that types could easily be added to the proofs which follow, and then it would be possible for example to make distinctions between variables ranging over a type of truth-values and variables ranging over a type of individuals. To the level of detail that interests us here, an untyped syntax is sufficient.

Some details of our translation between λ-terms syntax and nominal terms syntax are subtle; the translations of substitutions and theories in particular are delicately assembled. Full details are in the body of the paper.

However, it is not hard to give an overview of the technical ideas involved, and they resonate with other work. We account for the capturing substitution in nominal terms by translating to ‘raised’ λ-terms, as in previous work [6, 7, 23]. Nominal atoms-abstraction intuitively satisfies α-equivalence (not β or η), so the translation identifies λ-theories with nominal algebra theories containing ULAME, a theory which has been identified in previous work as axiomatising αβη-equivalence [16, 18] (see also Definition 14).

The translation works for ‘sufficiently large’ finite-variable fragments of both languages. As in [7] we do not present a single fixed translation of terms and derivations and we suspect (but do not prove) that such a translation does not exist. Our results only work for αβη-equivalence: αβ seems to be harder. Details follow in the body of the paper.

We will now briefly motivate algebra as a canonical ‘simple but useful’ logic, and discuss issues in the design of algebraic logics.

Algebraic logic. Algebraic logic is the theory of derivable equality between terms. For example, ‘universal algebra’ [4] is the theory of equality between first-order syntax (syntax made of variables and term-formers, also called function symbols). An algebraic theory is just a collection of equalities which are asserted as axioms, and any model of an algebraic theory should interpret derivably equal terms as denotationally identical elements.

The judgement-form of algebra is r = s. This might seem limited; for example there is no implication, so we cannot say ‘if’ or ‘but’. Yet surprisingly complex theories can be expressed using just equalities, and then the limitations become an asset: if we know that r = s then we can interchange r and s — with no ‘if’s and ‘but’s. This is particularly useful for compositional reasoning, and that may be one reason that equality reasoning has been chosen as the foundation of some large-scale implemented reasoning systems like [20]. Also, logics of equality enjoy powerful mathematical properties, like the HSP theorem [4, 11], which can be exploited to prove non-trivial properties of algebraically-specified logic and computation [1, 25, 29].

So universal algebra is interesting and important; in this paper, we use equality as a logical judgement-form with which to explore the implications of reasoning on different syntaxes with names and binding.

Choosing a syntax for algebra: first-order, higher-order, and nominal. When we design an algebraic logic we cannot choose our logical connectives — because there are none — but we have freedom in what syntax we use for r and s. So what syntax should we use?

Equality over just first-order syntax is a suitable framework for some exceedingly complex mathematics; consider for example combinators and their theory. It is also possible to study systems with binding using the so-called cylindric method [22]. This fixes a term-former for each binder; for example the spirit of cylindric algebra is that we axiomatise first-order logic in univeral algebra, and this has one term-former for ∀x, another for ∀y, and so on; likewise Salibra’s λ-abstraction algebras [25, 30] axiomatise λ-calculus in universal algebra, and they have one term-former for λx, another for λy, and so on (so cylindric algebra and λ-abstraction algebras use infinitely many term-formers, and infinitely many axioms).

However, it is still important to consider algebra over syntax with primitive support for binding. This is motivated by the need for the mathematical study of informal practice, and the creation of computing systems which match informal practice and are backed by rigorous formal methods.

One syntax extending first-order syntax with binding is λ-terms syntax quotiented by αβ- or αβη-equivalence. This is relevant to practice as well as theory: µCRL2 is an algebraic reasoning framework [20] which includes functions for usability and natural expressiveness [21]; in his book [2] Peter Andrews presents a logic Q0 for mathematics as an equational theory on (typed) λ-terms; λ-theories are equational theories on λ-calculus syntax including αβ-equivalence, studied by mathematicians, e.g. [24].

Nominal terms [32] provide primitive support for binding, via a generalisation of α-binding. Nominal algebra [17] is the logic of equality on nominal terms, introduced in [12, 13, 26]. It has been tested as a logical framework, at least in principle, by using it to axiomatise the λ-calculus and first-order logic [15, 18].

λ-terms’ natural denotation uses functions. In contrast, nominal terms admit a denotation in a cumulative sets hierarchy in which name-abstraction is interpreted using a non-functional abstraction operation described in [19] with properties much like those of an α-equivalence class (we do not consider denotations in this paper).

Translations between nominal unification [32] and higher-order patterns [28] have been considered; by Cheney [5], Levy and Villaret [23], and most recently by Dowek and the authors [6, 7]. This recent work uses a permissive variant of nominal terms, which offers advantages documented in [6, 7] and in this paper; to a first approximation we can ignore the difference, but this paper is self-contained and includes all relevant details of the permissive nominal syntax.

A difference between [23] and [7] is that [23] translates unifiability whereas [7] translates unification problems and their solutions. Now a substitution solving a unification problem is in a sense a ‘derivation’ or ‘proof-object’ for its unifiability.

In this paper we use the same basic ideas as in [7], but we extend them and take on the more complex task of translating derivations of equality in the presence of axioms (i.e. we translate derivations of equality modulo an arbitrary theory). This adds some technical complexity which the permissive nominal framework handles very well, but beyond that, this paper gives the details of a translation between logical reasoning over a functional syntax expressive enough to be a framework for mathematics, and a similarly expressive one over a nominal syntax.

2. Algebra-with-binding: nominal algebra and λ-theories

2.1 Permissive nominal algebra

We define permissive nominal terms (Definition 7). This features a two-level syntax inherited from [32], and a capturing substitution (Definition 10). We define an equational theory on permissive nominal terms (Definition 13); the notions of equational theory and derivability are are based on those in [12, 14, 17], but here we use a permissive nominal syntax. Proving properties of the connection between nominal algebra and the permissive variant in this paper, is future work; it will be similar to the relation between nominal unification and permissive nominal unification [7].

We define an equational theory ULAME (Definition 14); it is shown in [18] that we can think of this as ‘βη for nominal atoms-abstraction’. We will need this theory because our translation identifies the (weak) nominal atoms-abstraction with the (relatively strong) λ-terms functional abstraction.

Definition 1

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

Definition 2

If f is a function from atoms to atoms define nontriv(f) = {a | f(a) ≠ a}.1

Definition 3

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

Write π ◦π′ for the composition of π and π′ (so (π ◦π′)(a) = π(π′(a))). Write id for the identity permutation (so id(a) = a always). Write (a b) for the swapping permutation that maps a to b and b to a and all other c to themselves.

Definition 4

If S ⊆A, define the pointwise action by:

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

Call S ⊆A co-infinite when A \ S is infinite. Fix an infinite, co-infinite set comb ⊆A.

A permission set has the form π · (comb \ A) for a finite set A ⊆A. S, S′, T will range over permission sets.2

Definition 6

For each permission set S fix a disjoint countably infinite set of unknowns of sort S. X, Y , Z, will range over distinct unknowns. We write p(X) for the permission set of X.

Definition 7

Define (permissive nominal) terms by:

r, s, t, . . . ::= a | π · X | f | [a]r | r′r

We write ≡ for syntactic identity; r ≡s when r and s denote identical terms.

Note that X (the unknown) is not a term, however π · X is a term and in particular id · X is a term, which we may write as X.

The intended interpretation of permissive nominal terms follows the interpretation of nominal terms [32]: atoms represent variables; term-formers functions; unknowns meta-variables; abstraction [a]r binding; and π · X a meta-variable with a suspended substitution, like ‘t[y/x]’. The application r′r in this syntax is a priori just a convenient way to attach terms together; we could just as well have terms like f(r1, . . . , rn). For our purposes in this paper, it is more convenient to take as primitive a binary operator.

Definition 8

Define a permutation action by:

π · a ≡π(a) π · f ≡f π · (r′r) ≡(π · r′)(π · r)π · [a]r ≡[π(a)](π · r) π · (π′ · X) ≡(π◦π′) · X
Definition 9

Define free atoms fa(r) by:

fa(a) = {a} fa(f) = ∅ fa(r′r) = fa(r′) ∪fa(r)fa([a]r) = fa(r)\{a} fa(π·X) = π·p(X)

Note that fa(π · X) = π · p(X). An intuition for fa(r) is ‘the free atoms we can have after instantiation’. Since r may contain unknowns X, this need not be finite, though for each complete instantiation of r the free atoms will be finite.

Definition 10

A substitution θ is a function from unknowns to terms such that fa(θ(X)) ⊆ p(X) always (so p(X) describes the ‘permission’ we have to instantiate X, namely to terms with free atoms in S).3

θ will range over substitutions.

Write id for the identity substitution mapping X to id · X always. It will be clear whether id means the identity substitution or permutation.

Suppose fa(t)⊆p(X). Write [X:=t] for the substitution such that [X:=t](X) ≡t and [X:=t](Y) ≡ id · Y for all other Y .

Definition 11

Define a substitution action on terms by:

aθ ≡a fθ ≡f (r′r)θ ≡(r′θ)(rθ)([a]r)θ ≡[a](rθ) (π·X)θ ≡π·θ(X)

Consistent with [32] substitution for unknowns is capturing for abstraction by atoms. Note that Xθ means ‘θ acting on id · X’ and θ(X) means ‘the function θ at X’.

We now set about defining permissive nominal algebra.

Definition 12

An axiom is a pair r = s. A (permissive nominal algebra) theory is a set of axioms. T will range over theories.

Definition 13

Define derivable equality = by:

r = s s = t (Ntran) r = t(Nrefl)r = rr = s (Nsym) s = rr = s(Nabs)[a]r = [a]sr′ = s′r = s (Napp) r′r = s′s(a, b ∉fa(r)) (Nα) r = (a b) · r(Naxπ,θ r=s)π · (rθ) = π · (sθ)

If T is a theory, write T ⊢r = s when r = s is derivable, using only instances (Naxπ,σ r′=s′) where (r′ = s′) ∈ T.

Π will range over derivations.

Definition 14

Let a, b ∈ comb. Let X, Z, and Z′ have permission set comb. Let Y ′ have permission set comb \ {b}. Let X′ have permission set comb \ {a}. Define a theory ULAME by:

([a]a)X = X (Nβvar)([a]X′)X = X′(Nβ#)([a]Z)a = Z (Nβid)([a]([b]Z))Y ′ = [b](([a]Z)Y ′) (Nβabs)([a](Z′Z))X= (([a]Z′)X)(([a]Z)X)(Nβapp)[a](X′a) = X′(Nη)
Remark 15

ULAME is a set with six elements. It is not an infinite set determined by axiom-schemes.

The choice of atoms and unknowns in the axioms of ULAME is not important because (Nax) has facilities to rename atoms permutatively using a permutation π, and to instantiate unknowns using a substitution θ. The choice of atoms and unknowns in the axioms of ULAME can be important for the technical details of the proofs; see for example the case of (Lβ#) in Theorem 51.

ULAME originates in [16, 18], where the theory is proved sound and complete for λ-terms quotiented by αβη-equivalence (with no other equalities).

Example 16

Suppose p(X)=p(Y )=comb and a, b∈comb. We sketch two ULAME derivations in calculational style; the full derivation trees can easily be reconstructed:

([b]([a]X))Y = ([b]([a′](a′ a) · X))Y (Nα) a, a′∉fa([a]X)= [a′](([b]((a′ a) · X))Y ) (Nβabs)([b]([a]b))a = ([b]([a′]b))a (Nα) a, a′∉fa([a]b)= [a′](([b]b)a) (Nβabs)= [a′]a (Nβvar)

Here, we choose a′ fresh, so a′ ∉ comb (and by our permutative convention a′ is not equal to a or b).

Definition 17

Define fV (r) by:

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

Lemma 18 is a key difference from nominal terms. Later, when we write ‘choose a fresh’, we are using Lemma 18:

Lemma 18

A \ fa(r) is always infinite.

Proof

By induction on r. We consider one case: fa(π · X) = π · p(X) and by assumption A \ (π · p(X)) is infinite.End of proof

The following lemmas are proved by inductions just as in [32]:

Lemma 19

id · r ≡r, and π′ · (π · r) ≡ (π′ ◦π) · r.

Lemma 20

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

Lemma 21

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

2.2 λ-theories

Just as we did for nominal terms, we define λ-terms syntax and their (standard) capture-avoiding substitution action (Definitions 22 and 26). We define a notion of derivable equality (Definition 28) up to αβη-equality, plus equational axioms; this is similar to Andrews’s equational axiomatisation Q0 [2] and to the axioms of Salibra’s Lambda-Abstraction Algebras [30].

Note that we need η-equivalence for our later proofs to work. The use of η-equivalence is consistent with other work, e.g. on higher-order unification [8]. η-equivalence does sometimes make theory easier; this paper is a case in point. We do not know if our constructions can be made to work without η, perhaps in a more complicated form.4

Definition 22

Define λ-terms by:

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

Here f ranges over term-formers, a ranges over atoms, and X ranges over unknowns. g, h, k will range over λ-terms.

Definition 23

Define a permutation action by:

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

Define free atoms by:

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

Call a function σ from unknowns to λ-terms a (λ-calculus) substitution. σ will range over substitutions.

Write [X:=h] for the substitution which maps X to h and maps all other Y to Y .

Definition 26

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

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

An axiom is a pair g = h. A (λ-)theory is a set of axioms. L will range over theories.

Definition 28

Define derivable equality by:

g = g′g′ = g′′(Ltran)g = g′′(Lrefl)g = gg = h(Lsym)h = g(Lβvar)(λa.a)g = g(a ∉fa(h))(Lβ#)(λa.h)g = h(Lβid)(λa.h)a = h(b ∉fa(g))(Lβλ)(λa.(λb.h))g = λb.((λa.h)g) (Lβapp)(λa.(h′h))g = ((λa.h′)g)((λa.h)g)(a ∉fa(g))(Lη)λa.(ga) = gg = h(Lλ)λa.g = λa.hg = g′h = h′(Lapp)gh = g′h′(a, b ∉fa(g))(Lα)g = (a b) · g(Laxσ g=h)gσ = hσ

Write L ⊢g = h when g = h is derivable using only instances (Laxσ g′=h′) for (g′ = h′) ∈ L. Also: - Write g =αβη h when ∅⊢g = h. - Write g =αβ h when ∅⊢g = h with a derivation that does not use (Lη). - Write g =η h when ∅⊢g = h with a derivation that does not use (Lα), (Lβvar), (Lβ#), (Lβid), (Lβλ), or (Lβapp). - Write g =α h when ∅⊢g = h with a derivation that does not use (Lη), (Lβvar), (Lβ#), (Lβid), (Lβλ), or (Lβapp). Λ will range over derivations.

Remark 29

Some comments on the provenance of these rules: - (Lrefl), (Lapp), (Lλ), and (Ltran), have to do with equality and are as one would expect. - (Laxσ g=h) is the axiom rule. The substitution σ allows us to instantiate unknowns in axioms (atoms can be substituted for using λ-abstraction and β-reduction). - Other axioms are adapted from Andrews’s logic Q0 [2], which includes equality axioms for β-conversion (though they also look a lot like Salibra’s axioms of Lambda-Abstraction Algebras [25, Definition 20], and probably like other similar axiomatisations too).5 (Lβvar), (Lβid), (Lβλ), and (Lβapp) are exactly Andrews’s axioms (42), (44), and (43). In the presence of α-conversion, rules (43) and (44) let us ‘push a β-reduct into a term’ and it is a fact that they give the power of (Lβ#). (Lη) is η-equivalence. Andrews’s system does not include η — if it had, it would probably have looked like (Lη). (Lα) is α-equivalence. Andrews’s system includes an extensionality axiom expressed using an axiomatised ∀ quantifier ((3αβ) in [31, page 20]). It is possible to derive every instance of (Lα) in Q0. Since we do not axiomatise ∀, we must include (Lα) (compare also with [25, Definition 20, rule (α)]).

3. Translating nominal terms into the λ-calculus

We are now ready to translate nominal terms to λ-terms (Definition 35). The translation follows [7] and is indexed by a vector of atoms (Definition 30).

What does this vector mean? A difference between nominal terms and λ-terms is that the former permits capturing substitution and the latter does not. However, as is well-known, the effect of a capturing substitution can be obtained in λ-terms by ‘raising’. For example, the effect of the nominal term [a]X can be obtained by λa.(Xa), and the effect of the capturing substitution [X:=a] on the nominal term [a]X can be obtained by the capture-avoiding substitution [X:=λa.a]. Here, X is ‘raised’ over a.

Intuitively, the vector of the translation maps nominal terms to ‘raised’ λ-terms; we raise over the indexing vector, thus deciding once and for all, for each vector chosen, for which atoms we permit capture. There is no canonical vector to raise over, but if we are given a derivation in nominal algebra then we can raise over the atoms in that derivation and, with a little further work, obtain a valid derivation in λ-calculus. This is Theorem 43.

The translation maps nominal terms atoms-abstraction [a]r to λ-terms functional abstraction λa.g. Therefore, we also verify that the axioms in ULAME translate to valid αβη-equivalences between λ-terms (Theorem 45).

Because theories may be infinite, we do not collect all the atoms mentioned in a theory when we decide on an index to translate it. Instead, we calculate the appropriate vector on an axiom-by-axiom basis (⟦T⟧, Definition 35). One unfortunate side-effect of this is that when we try to use the translation of an axiom in the translation of a derivation, the vectors may not match and we may need to ‘reindex’. This is achieved by indexing the translation of substitutions ⟦θ⟧E D in Definition 35 over two vectors of atoms. The same thing happened in [7] but for apparently different technical reasons, and there may be some mathematics here to be brought out proving the inevitability of this, in future work.

3.1 The translation ⟦-⟧D, and its compositionality

We define the translation in Definition 35, and we prove a compositionality result (Theorem 40) for substitution relative to the translation; as discussed above, it is convenient to build into this result the possibility to ‘reindex’ from a vector D to a vector E (this did not happen in [7]). Note that compositionality holds only if there are ‘enough atoms’, where ‘enough’ varies depending on the complexity of the term and substitution we are considering.

Definition 30

Call a finite list of distinct atoms a vector. D will range over vectors. Write [d1, . . . , dn] for the vector containing d1, ... , dn in that order.

Definition 31

We use the following notation: Suppose A ⊆A. - Write D ∩A for the vector of atoms in D that occur in A, in order; thus [a1, a2, a3] ∩{a1, a3, a5} = [a1, a3]. - Write D ⊆A when every atom in D is in A. - Write A ⊆D when every atom in A is in D. - Write D ∪A for the set of atoms appearing in D or A. - If D and D′ are vectors, write D ⊆D′ when every atom in D is contained in D′ (not necessarily in the same order). - If π is a permutation and D = [d1, . . . , dn], write π · D for the vector [π(d1), . . . , π(dn)] (the pointwise action).

Definition 32

Suppose D = [d1, . . . , dn]. Write λD.g as shorthand for λd1. . . . λdn.g (a list of λ-abstractions). Write g D as shorthand for g d1. . . dn (a list of applications).

Definition 33

Write atoms(D) for the set of atoms appearing in D. Similarly write atoms(r) for the set of atoms appearing in r (for example, atoms((a b) · X) = atoms([a][b]X) = {a, b}); an inductive definition will be in a longer version of this paper. We will extend this notation to other tree-like structures as convenient, including to derivations (as in atoms(Π)) and to theories (as in atoms(ULAME)).

Definition 34

For each finite set of atoms S make a fixed but arbitrary choice of order on S.

Definition 35

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

⟦a⟧D ≡a ⟦π · X⟧D ≡X(π · (D ∩p(X)))⟦[a]r⟧D ≡λa.⟦r⟧D⟦r′r⟧D ≡⟦r′⟧D⟦r⟧D⟦f⟧D ≡f

Extend the translation to substitutions, equalities, and theories by:

⟦θ⟧E D(X) ≡λ(D ∩p(X)).⟦θ(X)⟧E⟦r = s⟧D ≡⟦r⟧D = ⟦s⟧D⟦T⟧ = {⟦r = s⟧D | r = s ∈T}

In the translation of T, D is atoms(r) ∪ atoms(s) in the order chosen in Definition 34.

Lemma 36

id · g ≡g, and π · (π′ · g) ≡ (π ◦π′) · g

Lemma 37

(λa.g)a =αβ g.

b ∉fa(g) implies (λa.g)b =αβ (a b) · g.

If nontriv(π) ∩ fa(g) ⊆D then (λD.g)π · D =αβ π · g.

Proof

The first two parts can be proved by inductions on a measure of the size of g.

For the third part, we work by induction on the length of D. If D has one element we use the first part. Suppose D has more than one element. Write π′ = (π(a) a) ◦π, head(D) = a, and tail(D) = D′ (head(D) is the first element in D and tail(D) is the other elements). There are two cases, depending on whether π(a) = a or π(a) ≠ a. We consider only the case π(a) ≠ a; the other is similar.

Note the following facts: π′(a′) = π(a′) for every a′ in D′, π′(a) = a, nontriv(π′) ∩ fa(g) ⊆D′, and (π(a) a) ◦π′ = π. We reason as follows: (λD.g)(π · D) ≡ (λa.λD′.g)π(a)(π′ · D′) Facts

=αβ (a π(a)) · ((λD′.g)π′·D′) First part, π(a)∈D′=αβ (a π(a)) · (π′ · g) Ind. hyp.≡π · g Lemma 36End of proof
Lemma 38

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

Proof

By induction on r.End of proof

Lemma 39

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

Proof

By induction on r. We consider one case. - The case π · X. We reason as follows, where [d1, . . . , dn] =

D ∩p(X):

fa(⟦π · X⟧D) = fa(Xπ(d1) . . . π(dn)) Definition 35

= fa(π(d1)) ∪. . . ∪fa(π(dn)) Definition 24= π · (fa(d1) ∪. . . ∪fa(dn)) Fact⊆π · fa(X) Definition 9= fa(π · X) Definition 9End of proof
Theorem 40

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

Proof

By induction on r.

- The case π · X. ⟦θ⟧E D(X) = λ(D ∩ p(X)).⟦θ(X)⟧E by Definition 35. Then: ⟦(π·X)θ⟧E ≡⟦π · θ(X)⟧E Definition 10

≡π · ⟦θ(X)⟧ELemma 38=αβ (λ(D∩p(X)).⟦θ(X)⟧E)(π·(D∩p(X))) Lemma 37≡(X(π · (D ∩p(X))))⟦θ⟧E DDefinition 35≡⟦π · X⟧D⟦θ⟧E DDefinition 35

The use of Lemma 37 above is valid, since by assumption nontriv(π) ⊆D, and so nontriv(π) ∩ fa(θ(X)) ⊆D. The result follows. - The case [a]r. Choose b fresh, so b ∉ fa(⟦rθ⟧D), b ∉

⋃X∈fV (⟦r⟧D) fa(⟦θ⟧E D(X)), and b ∉fa(⟦r⟧)D. Then: ⟦([a]r)θ⟧E ≡⟦[a](rθ)⟧EDefinition 10≡λa.(⟦rθ⟧E) Definition 35=α λb.(b a) · ⟦rθ⟧ELemma 39, b fresh=αβ λb.(b a) · (⟦r⟧D⟦θ⟧E D) Inductive hypothesis≡(λb.(b a) · ⟦r⟧D)⟦θ⟧E Db fresh=α (λa.⟦r⟧D)⟦θ⟧E DLemma 39, b fresh≡(⟦[a]r⟧D)⟦θ⟧E DDefinition 35

The result follows.End of proof

Example 41

Suppose a, a′ ∈ comb and b ∉ comb. Consider r ≡ [b](b a) · X where p(X) = comb. Note that atoms(r) = {a, b}. Take D = [a, b] and E = [a, a′, b]. It is a fact that ⟦r⟧D ≡λb.(Xb).

Take θ = id. Then ⟦θ⟧E D(X) ≡λa.(Xaa′), and

⟦r⟧D⟦θ⟧E D ≡(λb.(Xb))[X:=λa.(Xaa′)] ≡λb.((λa.(Xaa′))b) =αβ λb.(Xba′) ⟦r⟧E ≡λb.(Xba′)

Take θ = [X:=a]. Then ⟦θ⟧E D(X) ≡λa.a, and

⟦r⟧D⟦θ⟧E D ≡(λb.(Xb))[X:=λa.a] ≡λb.((λa.a)b) =αβ λb.b ⟦rθ⟧E ≡⟦[b]b⟧E ≡λb.b

Finally, take θ = [X:=a′]. Then ⟦θ⟧E D(X) ≡λa.a′, and

⟦r⟧D⟦θ⟧E D ≡(λb.(Xb))[X:=λa.a′] ≡λb.((λa.a′)b) =αβ λb.a′⟦rθ⟧E ≡⟦[b]a′⟧E ≡λb.a′

Now take D = [] and E = [a, a′, b], so that the condition of Theorem 40 fails. It is a fact that ⟦r⟧D ≡λb.X. Take θ = id. Then ⟦θ⟧E D(X) = Xaa′ and

⟦r⟧D⟦θ⟧E D ≡((λb.X)[X:=Xaa′] ≡λb.(Xaa′) ⟦r⟧E ≡λb.(Xba′)

3.2 Soundness of the translation

In Theorem 43 we show that derivable equality is preserved by the translation, provided that the indexing vector is ‘large enough’. We also verify that the axioms in ULAME translate to valid αβη-equivalences between λ-terms (Theorem 45).

Lemma 42

If Π is a derivation of T ⊢r = s and T ⊆ T′ then there exists a derivation Π′ of T′ ⊢r = s, and atoms(Π) = atoms(Π′).

Similarly, if Λ is a derivation of L ⊢g = h and L ⊆ L′ then there exists a derivation Λ′ of L′ ⊢g = h, and atoms(Λ) = atoms(Λ′).

Proof

Since a derivation that mentions only axioms in T (or L) is also one that mentions only axioms in T′ (or L′).End of proof

Theorem 43

Suppose Π is a derivation of T ⊢r = s. Suppose atoms(Π) ⊆E. Then there is a derivation ⟦Π⟧E of ⟦T⟧ ⊢⟦r⟧E = ⟦s⟧E.

Proof

By induction on Π. - (Nref), (Ntran), (Napp), and (Nλ) translate to (Lref), (Ltran), (Lapp), and (Lλ) respectively. - The case (Nα). Suppose a, b ∉ fa(r). Then a, b ∉ fa(⟦r⟧E) by Lemma 39. By (Lα), g =α (a b) · g. We use Lemma 42. - The case (Naxπ,θ r=s) for (r = s) ∈ T.

Let D be the vector of atoms containing atoms(r) ∪ atoms(s) chosen in Definition 35. We need to show that ⟦T⟧ ⊢⟦π · (rθ)⟧E = ⟦π · (sθ)⟧E. First, we note the following:

⟦π · (rθ)⟧E ≡π · ⟦rθ⟧ELemma 38=αβ (λE.⟦rθ⟧E)π · E Lemma 37=αβ (λE.(⟦r⟧D⟦θ⟧E D))π · E Theorem 40

The use of Lemma 37 is valid since nontriv(π) ⊆E by assumption. The use of Theorem 40 is valid since atoms(r) ⊆ D by assumption. By the same reasoning for s we note that

⟦π · (sθ)⟧E =αβ (λE.(⟦s⟧D⟦θ⟧E D))π · E.

We use Lemma 42 and (Lax⟦θ⟧E D ⟦r=s⟧D).End of proof

Example 44

Suppose p(X) = comb and suppose a, a′ ∈ comb and b ∉ comb. Consider term-formers A and E.

Consider a theory F with one axiom E[a]A[b]X = E[a]X. Then ⟦F⟧ = {Eλa.Aλb.(Xa) = Eλa.(Xa)}.

There is a trivial derivation of F ⊢ E[a]A[b]X = E[a]X. Take E = [a′, a, b]. It is not hard to construct a derivation of ⟦F⟧ ⊢ Eλa.Aλb.(Xa′a) = Eλa.(Xa′a), by instantiating X to Xa′ in ⟦F⟧.

Theorem 45

Suppose (r = s) ∈ ULAME. For every π and θ, ⟦π · (rθ)⟧D =αβη ⟦π · (sθ)⟧D.

Proof

We consider just two axioms of ULAME: - Axiom (Nβvar). Since (λa.a)g =αβη g and (λb.b)g =αβη g always, by (Lβvar). - Axiom (Nβ#). The unknown X′ in (Nβ#) has permission set comb \ {a}. By Definition 10 a ∉ fa(θ(X′)). By Lemma 39 also a ∉ fa(⟦θ(X′)⟧D). The result follows using (Lβ#).End of proof

4. Translating back

In Section 3 we translated nominal algebra theories to λ-theories. Now, we translate λ-theories to nominal algebra theories. As already discussed our translation identifies λ-abstraction with nominal atoms abstraction. Accordingly, it generates nominal algebra theories that include ULAME (Definition 14).

4.1 The translation ⦅-⦆D, and soundness

We define the inverse translation in Definition 47, then prove a compositionality result (Lemma 49). This resembles Theorem 40 but it is technically simpler, and holds for all vectors E. Our λ-terms have no capturing substitution, so this makes sense; the vector in ⦅-⦆D is just there to obtain inverse properties with respect to ⟦-⟧D, as we shall see later in Subsections 4.3 and 4.4.

We prove a soundness result for the translation (Theorem 51). This resembles Theorem 43 but again, it is valid for all vectors.

Definition 46

Suppose D = [d1, . . . , dn]. Continuing Definition 32 write [D]r as shorthand for [d1] . . . [dn]r (a list of atoms-abstractions).

Definition 47

If g is a λ-term and D is a vector of atoms, define a nominal term ⦅g⦆D by:

⦅a⦆D ≡a ⦅f⦆D ≡f ⦅X⦆D ≡[D ∩p(X)]X⦅λa.g⦆D ≡[a](⦅g⦆D) ⦅g′g⦆D ≡⦅g′⦆D⦅g⦆D

Call σ good when fa(σ(X)) ⊆ p(X) for all X. Extend the translation to good substitutions, equalities, and theories by:

⦅σ⦆E D(X) ≡⦅σ(X)⦆E(D ∩p(X)) (σ good)⦅g = h⦆D ≡(⦅g⦆D = ⦅h⦆D) ⦅L⦆ = {⦅g = h⦆D | g = h ∈T} ∪ULAME

We take ⦅σ⦆E D to be undefined if σ is not good. The condition fa(σ(X)) ⊆ p(X) is sufficient to ensure that fa(⦅σ⦆E D) ⊆ p(X) always, so that ⦅σ⦆E D is a substitution when it is defined (Definition 10). This condition is ‘soft’ in a sense discussed in Subsection 4.2.

In the definition of ⦅L⦆, D is atoms(g)∪atoms(h) in the order chosen in Definition 34.

Note that ⦅L⦆ is the translation of the axioms in L, plus ULAME; intuitively, ULAME represents the rules (Lβvar), (Lβ#), (Lβid), (Lβλ), (Lβapp), and (Lη).

Lemma 48

fa(⦅g⦆D) ⊆ fa(g).

Proof

By induction on g.End of proof

Lemma 49

Suppose fa(σ(X)) ∩D = [] for every X ∈ fV (g) and suppose σ is good. Then ULAME ⊢⦅gσ⦆E D = ⦅g⦆D⦅σ⦆E D.

Proof

By induction on g. We consider one case: - The case of X. Write S = p(X). We reason as follows:

ULAME ⊢⦅X⦆D⦅σ⦆E D ≡ ([D ∩S]X)⦅σ⦆E D Definition 47

≡[D ∩S]⦅σ⦆E D(X) Definition 11≡[D ∩S](⦅σ(X)⦆E(D ∩S)) Definition 47= ⦅σ(X)⦆E(Nη)

The final step is valid, since fa(σ(X)) ∩D = ∅ by assumption and therefore by Lemma 48 also fa(⦅σ(X)⦆E) ∩ (D ∩S) = ∅.End of proof

Definition 50

Call a derivation Λ good when σ is good for every (axσ g=h) in Λ.

Theorem 51

Suppose Λ is a good derivation of L ⊢g = h. Then for any E there is a derivation ⦅Λ⦆E of ⦅L⦆ ⊢⦅g⦆E = ⦅h⦆E.

Proof

We work by induction on Λ: - (Lrefl), (Ltran), (Lapp), and (Lλ) translate to (Nrefl), (Ntran), (Napp), and (Nabs) respectively. - The case (Laxσ g=h). We want that ⦅L⦆ ⊢⦅gσ⦆E = ⦅hσ⦆E.

By Lemma 49 ⦅L⦆ ⊢⦅gσ⦆E = ⦅g⦆[]⦅σ⦆E [] and ⦅L⦆ ⊢⦅hσ⦆E =E

⦅h⦆[]⦅σ⦆E [] (here [] is the empty list of atoms). Also by (Naxid,⦅σ⦆[] ⦅g=h⦆[]) we have ⦅L⦆ ⊢ id · (⦅g⦆E⦅σ⦆E []) = id · (⦅h⦆[]⦅σ⦆E []). The result follows using (Ltran) and Lemma 36. - The case (Lβ#). There are two cases:

- L ⊢ (λa.h)g = h where a ∉ fa(h), and a is the atom we chose to use in the axiom (Nβ#) of ULAME (Definition 14). - L ⊢ (λa′.h)g = h where a′ ∉ fa(h), and a′ is different from the atom a we chose to use in axiom (Nβ#). We consider only the second case; the first case is similar. Let π be any permutation such that π(a′) = a and such that π · (fa(h) ∪ fa(g)) ⊆ comb (that is, π maps a′ to a and maps the atoms in fa(h) to be inside comb, and the atoms in fa(g) to be inside comb). Let θ be the substitution mapping X′ to π-1 · (⦅h⦆E) and X to π-1 · (⦅g⦆E) and every other Y to id · Y . We consider (Naxπ,θ ([a]X′)X=X′), where (([a]X′)X = X′) = (Nβ#). We verify that this gives the right result: By Lemmas 20 and 48 fa(π·(⦅h⦆E)) ⊆ comb\{a} and fa(π · (⦅g⦆E)) ⊆ comb. Therefore, θ is a substitution (Definition 10). Also:

π · ((([a]X′)X)θ) ≡π · ([a]π-1·(⦅h⦆E))(π-1·(⦅g⦆E)) Definition 11≡([a′](⦅h⦆E))(⦅g⦆E) Def. 8, Lem. 36≡⦅([a′]h)g⦆EDefinition 47

Similarly, π · (X′θ) ≡⦅h⦆E as required. - The case of (Lη) is similar (we translate to an instance of (Nax) for (Nη), and use Lemma 48). - (Lβvar), (Lβλ), (Lβapp) translate to instances of (Nax) for (Nβvar), (Nβλ), and (Nβapp) respectively.End of proof

Example 52

Suppose p(X) = comb and suppose a, a′ ∈ comb and b ∉ comb. Consider term-formers A and E.

Consider a theory G with one axiom Eλa.Aλb.(Xa) = Eλa.(Xa). Then ⦅G⦆ = {E[a]A[b](([a]X)a) = E[a](([a]X)a)}.

There is a trivial derivation of G ⊢ Eλa.Aλb.(Xa) = Eλa.(Xa). Take E = []. It is not hard to construct a derivation of ⦅G⦆ ⊢ E[a]A[b](Xa) = E[a](Xa), by instantiating X to Xa in ⦅G⦆ and using (Nβid).

4.2 Making derivations good

Theorem 51 uses a condition that Λ is ‘good’ (Definition 50). But what if we are given a Λ that is not? Lemmas 53 and 55 give senses in which we need not worry about this.

Lemma 53

Suppose Π is a derivation of T ⊢r = s. Suppose atoms(Π) ⊆E. Then ⟦Π⟧E from Theorem 43 is a good derivation of ⟦T⟧E ⊢⟦r⟧E = ⟦s⟧E.

Proof

Examining the construction of ⟦Π⟧E in the proof of Theorem 43, it suffices to check that ⟦θ⟧E D is good for every θ in Π. Expanding definitions, we must check that fa(λD∩p(X).⟦θ(X)⟧E) ⊆ p(X) always. This is by Lemma 39 (with r ≡ id · X).End of proof

Definition 54

Call a bijection on unknowns a renaming. ρ will range over renamings.

Each ρ is also a substitution (Definition 25). Write gρ for ρ acting on g as a substitution. Write Lρ for the set {gρ = hρ | (g = h) ∈ L}. Write (ρ-1Λ) for the tree obtained by mapping every (axσ g=h) to (axρ-1◦σ gρ=hρ).

It is a fact that if Λ is a derivation of L ⊢g = h then (ρ-1Λ) is a derivation of Lρ ⊢g = h.

Lemma 55

Suppose Λ is a derivation of L ⊢g = h. Then there exists a ρ such that (ρ-1Λ) is a good derivation of Lρ ⊢g = h.

Proof

Let A be the set of all atoms mentioned in Λ. It suffices to choose ρ such that for each X mentioned in Λ, A ⊆ p(ρ(X)).End of proof

4.3 The translations ⟦-⟧ and ⦅-⦆ are inverse on theories

Our main result is Theorem 62. This matches λ-theories with theories in nominal algebra that include ULAME.

Right from [32] the intuition of nominal terms and nominal algebra has been that this is a weaker syntax and logic than λ-terms and λ-theories; something that drops β(η)–equivalence, but retains just enough power to express binding. Theorem 62 is a way to make this intuition formal, by identifying arbitrary theories over λ-terms with nominal algebra theories over ULAME.

Lemma 56

ULAME ⊢ ([a]r)a = r.

b ∉fa(r) implies ULAME ⊢([a]r)b = (a b) · r.

If nontriv(π) ∩ fa(r) ⊆D then ULAME ⊢ ([D]r)(π · D) = π · r.

Proof

For the first two parts, we reason as follows:

ULAME ⊢([a]r)a = r (Nβid)ULAME ⊢([a]r)b = ([b](a b) · r)b (Nα), a, b ∉fa([a]r)= (a b) · r (Nβid)

The proof of the third part is like the proof of the third part of Lemma 37.End of proof

Lemma 57

If atoms(r)⊆D then ULAME ⊢⦅⟦r⟧D⦆D = r. As a corollary, if atoms(r)⊆D and ULAME⊆T then T ⊢⦅⟦r⟧D⦆D = r.

Proof

The corollary follows by Lemma 42. We prove the first part by induction on r: - The case π · X. Write S = p(X). We reason as follows: ULAME ⊢⦅⟦π · X⟧D⦆D ≡⦅X(π · (D ∩S))⦆D Definition 35

≡([D ∩S]X)(π · (D ∩S)) Definition 47= π · X Lemma 56

The use of Lemma 56 here is valid since nontriv(π) ⊆D by assumption and S ⊆D, and it follows by Definition 9 that nontriv(π) ∩ fa(X) ⊆D ∩S.End of proof

Lemma 58

⟦⦅g⦆D⟧D =η g.

As a corollary, L ⊢⟦⦅g⦆D⟧D = g always.

Proof

The corollary follows by Lemma 42. We prove the first part by induction on g. We consider one case: - The case X. Write S = p(X). We reason as follows:

⟦⦅X⦆D⟧D ≡⟦[D ∩S]X⟧DDefinition 47≡λ(D ∩S).(X(D ∩S)) Definition 35=η X (Lη)End of proof
Definition 59

Suppose T and T′ are two theories. Write T ⊣⊢ T′ when for all g and h, T ⊢g = h if and only if T′ ⊢g = h.

Similarly for L and L′.

Lemma 60

T ⊣⊢ T′ if and only if T ⊢g′ = h′ for every (g′ = h′) ∈ T′ and also T′ ⊢g = h for every (g = h) ∈ T.

Similarly for L and L′.

Proof

The left-to-right implication is immediate. The right-to-left implication is by a routine induction on derivations.End of proof

Lemma 61

We observe the following set inclusions:

atoms(r) ⊆atoms(⟦r⟧D) ⊆atoms(r) ∪D atoms(g) ⊆atoms(⦅g⦆D) ⊆atoms(g) ∪D
Proof

By routine inductions on r and g.End of proof

Theorem 62

If ULAME ⊆ T then ⦅⟦T⟧⦆ ⊣⊢ T.

⟦⦅L⦆⟧ ⊣⊢ L always.

Proof

We use Lemma 60.

Suppose (r = s) ∈ T. Let D be the vector of atoms chosen for atoms(r) ∪ atoms(s) in Definition 34. By Lemma 61 atoms(⟦r⟧D)∪atoms(⟦s⟧D) = atoms(D). Therefore, ⦅⟦r⟧D⦆D = ⦅⟦s⟧D⦆D ∈⦅⟦T⟧⦆. By assumption atoms(r) ⊆D and atoms(s) ⊆ D. The result follows by (Ntran) and by Lemma 57.

Conversely, suppose (r = s) ∈⦅⟦T⟧⦆. From Definition 47 and Lemma 61 there are two cases: - (r = s) ∈ ULAME. - (r = s) = (⦅⟦r′⟧D⦆D = ⦅⟦s′⟧D⦆D) for some (r′ = s′) ∈ T.

We use Lemma 57 as before. Suppose (g = h) ∈ L. Let D be the vector of atoms chosen for atoms(g) ∪ atoms(h) in Definition 34. By Lemma 61 atoms(⦅g⦆D)∪atoms(⦅h⦆D) = atoms(D). Therefore, (⟦⦅g⦆D⟧D = ⟦⦅h⦆D⟧D) ∈⟦⦅L⦆⟧. We use (Ltran) and Lemma 58.

Suppose (g = h) ∈⟦⦅L⦆⟧. There are two possibilities: - (g = h) = (⟦r⟧D = ⟦s⟧D) for some (r = s) ∈ ULAME.

By Theorem 45 and Lemma 42, L ⊢g = h. - (g = h) = (⟦⦅g′⦆D⟧D = ⟦⦅h′⦆D⟧D) for some (g′ = h′) ∈ L.

We use Lemma 58 as before.End of proof

4.4 The translations ⟦-⟧D and ⦅-⦆D are inverse on derivations, if D is sufficiently large

We now come to our main result; Theorem 67. Intuitively we can read this as follows: we can translate between nominal algebra theories (with ULAME) and λ-theories. In both directions the translation uses a finite vector of atoms E. For derivability of equality to be preserved in both directions, this vector must be ‘large enough’.

Thus, there is no fixed 1-1 correspondence between nominal terms and λ-terms, but we can translate between theories (Subsection 4.3) and for any given derivation of an equality, if we take a large enough indexing vector, then we can also translate that derivation accurately between the two theories. There may always be another derivation of a different equality, or even of the same equality, that requires a different (possibly longer, possibly shorter) vector.

Note that we have not attempted to exhibit a ‘minimal’ vector such that the translation works; this is future work. Perhaps the notion of the capturable atoms of a nominal term may be relevant here; it was used to measure the minimal raising required to translate between nominal and higher-order unification [7].

Lemma 63

If Π is a derivation of T ⊢r = s then there exists a derivation Πθ of T ⊢rθ = sθ. Furthermore, atoms(Π) ⊆ atoms(Πθ) ⊆ atoms(Π) ∪⋃{fa(θ(X)) | X occurs in Π}.

Proof

We apply θ to every term in Π to obtain Πθ and verify by induction that Πθ is a derivation of T ⊢rθ = sθ.End of proof

Corollary 64

Suppose Π is a derivation of T ⊢⦅g⦆D = ⦅h⦆D. Suppose atoms(ULAME)⊆D⊆E. Then there is a derivation Π′ of T ⊢⦅g⦆E = ⦅h⦆E, and atoms(Π)⊆atoms(Π′)⊆atoms(Π)∪E.

Proof

By Lemma 63 Π⦅id⦆E D is a derivation of T ⊢⦅g⦆D⦅id⦆E D = ⦅h⦆D⦅id⦆E D, and atoms(Π) ⊆ atoms(Π⦅id⦆E D) ⊆ atoms(Π)∪D. By Lemma 49 T ⊢⦅g⦆D⦅id⦆E D = ⦅g⦆E and we see from the proof of Lemma 49 that the atoms in the derivation are in atoms(g) ∪ E ⊆ atoms(Π) ∪E. Similarly for h. We use (Ltran).End of proof

Theorem 65

Suppose ULAME ⊆ T. - Suppose Π is a derivation of T ⊢r = s. Then ⟦Π⟧E is a derivation of ⟦T⟧ ⊢⟦r⟧E = ⟦s⟧E for any E such that atoms(Π) ⊆E. - Suppose ⟦T⟧ ⊢⟦r⟧E = ⟦s⟧E and atoms(r) ∪ atoms(s) ⊆E.

Then T ⊢r = s. - Suppose Λ is a derivation of L ⊢g = h. There exists a renaming ρ (Definition 54) such that for any E, ⦅Lρ⦆ ⊢⦅g⦆E = ⦅h⦆E.

- Suppose ⦅Lρ⦆ ⊢⦅g⦆E = ⦅h⦆E for some ρ and some E. Then

L ⊢g = h.
Proof

- This is Theorem 43. - Suppose ⟦T⟧ ⊢⟦r⟧E = ⟦s⟧E where atoms(r)∪atoms(s) ⊆E.

By Lemma 53 and Theorem 51 ⦅⟦T⟧⦆ ⊢⦅⟦r⟧E⦆E = ⦅⟦s⟧E⦆E. By Theorem 62 ⦅⟦T⟧⦆ ⊣⊢ T. By Lemma 57 since ULAME ⊆ T and atoms(r) ⊆E, T ⊢⦅⟦r⟧E⦆E = r, and similarly for s. It follows by (Ltran) that T ⊢r = s as required. - By Lemma 55 there exists a ρ such that (ρ-1Λ) is a good derivation of Lρ ⊢g = h. The result follows by Theorem 51. - Suppose Π is a derivation of ⦅Lρ⦆ ⊢⦅g⦆E = ⦅h⦆E. Choose any E′ such that E ∪ atoms(Π) ∪ atoms(ULAME) ⊆E′. By Corollary 64 there is a derivation Π′ of ⦅Lρ⦆ ⊢⦅g⦆E′ = ⦅h⦆E′ and atoms(Π′) ⊆E′. By Theorem 43 ⟦⦅Lρ⦆⟧ ⊢⟦⦅g⦆E′⟧E′ = ⟦⦅h⦆E′⟧E′. By Theorem 62 ⟦⦅Lρ⦆⟧ ⊣⊢ Lρ. By Lemma 58, Lρ ⊢⟦⦅g⦆E′⟧E′ = g, and similarly for h. It follows by (Ltran) that Lρ ⊢g = h. Since ρ is invertible, we can use Lemma 55 to verify that L ⊢g = h as required.End of proof

Definition 66

Suppose Φ(D) is some assertion (in English) which depends on a vector D. Write “Φ(D) holds for sufficiently large D” to mean “there exists a D such that for all D′, if D ⊆D′ (Definition 31) then Φ(D′)”.

Theorem 67

Suppose ULAME ⊆ T. Then: - T ⊢r = s if and only if ⟦T⟧ ⊢⟦r⟧E = ⟦s⟧E for sufficiently large E. - For any E, L ⊢g = h if and only if there exists a ρ such that

⦅Lρ⦆ ⊢⦅g⦆E = ⦅h⦆E.
Proof

Direct from Theorem 65.End of proof

A stronger version of part 2 of Theorem 67 holds, where we echo part 1 and write “for sufficiently permissive ρ”, meaning for “ρ such that p(X) is sufficiently large for relevant X” (generalising Definition 66 to sets). Making this formal is for a longer paper.

5. Conclusions

Equational reasoning is simple, yet powerful. In this arena we have addressed the question “what is the connection between truth and derivability over nominal syntax, and truth and derivability over higher-order syntax”.

No single translation offers itself — but for any given derivation we can find a sufficiently large indexing set to translate it between the two worlds. This makes sense, because nominal terms unknowns X intuitively represent ‘any term, with a capturing substitution’, and a term may mention finite but unboundedly many atoms. The translation also brings out some nice features of using (permissive) nominal terms syntax, compared to λ-terms syntax:

• Nominal terms are more elementary, in the sense that the primitive theory of equality over nominal terms (no axioms) has fewer axioms than the primitive theory of equality over λ-terms (which the results in this paper identify in a certain precise sense with the axioms of ULAME). In other words: to reason in permissive nominal algebra we do not need to include the behaviour captured by the axioms in ULAME if we do not want it, whereas to reason using λ-terms, we must include that behaviour whether we want it or not (perhaps minus (Lη)).6

• By design, nominal terms have a two-level variable structure which directly models the behaviour of the informal meta-level of mathematical discourse with its ‘object-level variables’ and ‘meta-level variables’ (see the example statements about first-order logic and λ-calculus in the Introduction). As we move under abstractions, it is not necessary to maintain a list of names for which we wish to permit capture; this list appears in this paper as the D ∩ p(X) in Definitions 35 and 47.

It is possible that logics based on nominal terms, of which permissive nominal algebra is one example, might offer convenient reasoning frameworks for formalising informal reasoning about logic and computation. It is a natural next step to study reasoning using nominal terms in more detail, and this includes considering logics with richer judgement-forms. We hope the techniques used here will be prototypical for such logics.

Choice of permissive nominal terms over nominal terms The nominal algebra presented in this paper is not identical to that presented in [14, 26]. We use a ‘permissive’ variant which we find simpler to define and manipulate. The connection with ‘standard’ nominal algebra will formally be developed in a later paper. We will, however, sketch why we prefer to use permissive nominal terms; for definitions and notation for nominal terms, see [32].

Nominal terms have no permissions sets. Instead there is a freshness context, usually written ∆. ∆ is a finite set of assertions a#X; these correspond in the notation of this paper with a ∉ p(X) (“a is not in the permissions set of X”). Thus the translation of Definition 35 would be indexed by ∆, so we might write it as ⟦r⟧D ∆.

The difference is that we may need to change ∆, and there is no natural notion of fa(r). Often, we must obtain fresh atoms; see for example the case [a]r in Theorem 40. Using permissive nominal terms such fresh atoms are readily available by Lemma 18. In the theory of nominal terms this is not the case; for example ∆ may be empty and so provide no fresh atoms at all. Therefore, we would have to extend ∆ to a ‘freshly extended’ freshness context ∆′ ⊇∆. It might be useful to sketch what Theorem 40 would become: Suppose atoms(r) ⊆D. Then for any ∆, there exists some freshly extended ∆′ ⊇∆ such that ⟦rθ⟧E ∆′ =αβ ⟦r⟧D ∆′⟦θ⟧∆′ E D.

There is nothing mathematically wrong with this, but it is more complex and this complexity propagates. Uses of the result may involve reasoning on and possible extension of the freshness context; this lengthens proofs, propagates to the statements of following results, and it introduces a non-trivial notion of state into our reasoning in the sense that the freshness contexts may get larger at each reasoning step.

The use of permissive nominal syntax avoids this and so gives us shorter and sweeter proofs.

Future work The algebras considered in this paper are unsorted and untyped. λ-terms are routinely given types; we could do the same for nominal terms. A ‘function type’ α →β would just indicate a term binding of a variable of type α in a term of type β — but using axioms like those in ULAME we could also endow this with functional behaviour if we wished.

The encoding of λ-theories into nominal algebra theories suggests we might be able to apply nominal algebra theorems to study existing work on logic and computation phrased in universal algebra. We have particularly in mind Salibra’s study of λ-theories. Nominal algebra satisfies some stronger properties than univeral algebra, notably a strong version of the HSP theorem [11] which factors also over atoms-abstraction. It may be possible to put some constructions of Salibra, which he carries out specifically for Lambda-Abstraction Algebras, into a nominal algebraic setting.

As discussed in Subsection 2.2, the proofs in this paper require η-equivalence. [16, 18] consider a non-extensional theory ULAM (it lacks (Nη)). It is future work to see whether the proof-methods here can be adjusted to work without it. An overview of some denotations for logic over non-extensional λ-terms is [3].

It should be possible to use the translation of λ-theories into nominal algebra, to construct denotations for them in nominal sets or variants of nominal sets. Conversely, if a nominal algebra theory contains ULAME then it should be possible to give it a denotation in functions (probably a rather large one, involving all possible indexes over vectors of atoms).

It would be interesting to find a translation which is sound and complete for atoms-abstraction without ULAME: that is, can we interpret nominal atoms-abstraction in λ-syntax such that the image of the translation does not satisfy β-equivalence? It might then be possible to give denotations based on functions (as well as those based on nominal sets [17]) to nominal terms and (arbitrary) nominal algebra theories.

References

[1] Beatrice Amrhein. Birkhoff’s HSP-theorem for cumulative logic programs. Lecture Notes in Computer Science, 798:24– 36, 1994.

[2] Peter B. Andrews. An introduction to mathematical logic and type theory: to truth through proof. Academic Press, 1986.

[3] Christoph Benzmüller, Chad E. Brown, and Michael Kohlhase. Higher-order semantics and extensionality. Journal of Symbolic Logic, 69:1027–1088, 2004.

[4] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Graduate texts in mathematics. Springer, 1981.

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

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

[7] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. In CILC, 24th Italian Conference on Computational Logic, 2009.

[8] Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Higher-order unification via explicit substitutions. Information and Computation, 157, 2000.

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

[10] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.

[11] Murdoch J. Gabbay. Nominal Algebra and the HSP Theorem. Journal of Logic and Computation, 19(2):341–367, 2009.

[12] Murdoch J. Gabbay and Aad Mathijssen. Nominal Algebra. In 18th Nordic Workshop on Programming Theory, 2006.

[13] Murdoch J. Gabbay and Aad Mathijssen. Nominal Algebra. Technical Report HW-MACS-TR-0045, Heriott-Watt, 2006.

[14] 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, 2007.

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

[16] Murdoch J. Gabbay and Aad Mathijssen. Reasoning in simple type theory: Festschrift in Honour of Peter B. Andrews on his 70th Birthday, chapter The lambda-calculus is nominal algebraic. Studies in Logic and the Foundations of Mathematics. IFCoLog, December 2008.

[17] Murdoch J. Gabbay and Aad Mathijssen. Nominal Algebra. Journal of Logic and Computation, 2009. In press.

[18] Murdoch J. Gabbay and Aad Mathijssen. A nominal axiomatisation of the lambda-calculus. Journal of Logic and Computation, 2009. In press.

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

[20] Jan Friso Groote, Aad Mathijssen, Michel Reniers, Yaroslav Usenko, and Muck van Weerdenburg. The formal specification language mCRL2. In Methods for Modelling Software Systems (MMOSS), number 06351 in Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), 2007.

[21] Jan Friso Groote, Aad Mathijssen, Muck van Weerdenburg, and Yaroslav S. Usenko. From µCRL to mCRL2: motivation and outline. In Proc. Workshop Algebraic Process Calculi: The First Twenty Five Years and Beyond, BRICS NS-05-3, pages 126–131, 2005.

[22] Leon Henkin, J. Donald Monk, and Alfred Tarski. Cylindric Algebras. North Holland, 1971 and 1985. Parts I and II.

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

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

[25] Giulio Manzonetto and Antonino Salibra. Applying universal algebra to lambda calculus. Journal of Logic and computation, 2009. Online first.

[26] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.

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

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

[29] Donald Monk. On the representation theory for cylindric algebras. Pacific Journal of Mathematics, 11(4):1447–1457, 1961.

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

[31] Li-Yang Tan. Formalizing the meta-theory of Q0 in the calculus of inductive constructions. PhD thesis, Henry Edwin Sever Graduate School of Washington University, 2006.

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

Notes

1 We call this the support of π in [19]. There, ‘support’ has a specific technical meaning in the universe of Fraenkel-Mostowski sets. Here, we prefer nontriv (for ‘nontrivial’) because the terminology immediately suggests its definition. ↩

2 Two notes about previous work: Nominal sets [19] disallow comb because it lacks finite support; here, we are working at the meta-level, and we can talk about any subset we like. In [6, 7] we allow slightly more permissions sets, of the form (comb ∪B)\ A for finite B. What we have defined here, will be enough for our needs. ↩

3 ‘fa(θ(X)) ⊆ p(X)’ looks absent in nominal terms theory ([32, Definition 2.13], [9, Definition 4]), yet it is there: see the conditions ‘∇′ ⊢θ(∇)’ in Lemma 2.14, and ‘∇⊢a#θ(t)’ in Definition 3.1 of [32]. ↩

4 To be specific: we use η-equivalence in Lemma 58. We need something like this result for Theorems 62 and 65. If we drop η then we should modify the translations ⟦-⟧D and ⦅-⦆D to be ‘more intelligent’, i.e. more complicated, to compensate so that the η-equivalence of Lemma 58 becomes syntactic identity or perhaps an αβ-equivalence. ↩

5 We first obtained the axioms from Tan’s thesis [31]. We are grateful for his clear and accessible presentation of Andrews’s work. ↩

6 This point also motivates higher-order patterns [27]. See [6, 7, 23] for the connection with nominal terms. ↩