Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables
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 does not occur in then if and only if .”
“If does not occur in then if and only if .”
“If does not occur in then () is equal to .”
“() is equal to always.”
Suppose is a permissive nominal unknown with permissions set p( comb, and suppose comb and comb (so intuitively, may be instantiated to a term mentioning free but not mentioning free; formal definitions are in the body of the paper). Then translations are as in the following small table:
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 . 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 then we can interchange and — 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 and . 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 , another for , and so on; likewise Salibra’s -abstraction algebras [25, 30] axiomatise -calculus in universal algebra, and they have one term-former for , another for , 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 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.
Fix a countably infinite set of atoms. 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.
If is a function from atoms to atoms define nontriv(() .1
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 ()( (())). Write id for the identity permutation (so id( always). Write () for the swapping permutation that maps to and to and all other to themselves.
If , define the pointwise action by:
Call co-infinite when is infinite. Fix an infinite, co-infinite set comb .
A permission set has the form (comb ) for a finite set . will range over permission sets.2
For each permission set fix a disjoint countably infinite set of unknowns of sort . , , , will range over distinct unknowns. We write p() for the permission set of .
Define (permissive nominal) terms by:
We write for syntactic identity; when and denote identical terms.
Note that (the unknown) is not a term, however is a term and in particular id is a term, which we may write as .
The intended interpretation of permissive nominal terms follows the interpretation of nominal terms [32]: atoms represent variables; term-formers functions; unknowns meta-variables; abstraction [] binding; and a meta-variable with a suspended substitution, like ‘[]’. The application in this syntax is a priori just a convenient way to attach terms together; we could just as well have terms like f(). For our purposes in this paper, it is more convenient to take as primitive a binary operator.
Define a permutation action by:
Define free atoms fa() by:
Note that fa( p(). An intuition for fa() is ‘the free atoms we can have after instantiation’. Since may contain unknowns , this need not be finite, though for each complete instantiation of the free atoms will be finite.
A substitution is a function from unknowns to terms such that fa(()) p() always (so p() describes the ‘permission’ we have to instantiate , namely to terms with free atoms in ).3
will range over substitutions.
Write id for the identity substitution mapping to id always. It will be clear whether id means the identity substitution or permutation.
Suppose fa()p(). Write [] for the substitution such that []() and []() id for all other .
Define a substitution action on terms by:
Consistent with [32] substitution for unknowns is capturing for abstraction by atoms. Note that means ‘ acting on id ’ and () means ‘the function at ’.
We now set about defining permissive nominal algebra.
An axiom is a pair . A (permissive nominal algebra) theory is a set of axioms. T will range over theories.
Define derivable equality by:
If T is a theory, write T when is derivable, using only instances (Nax) where () T.
Π will range over derivations.
Let comb. Let , , and have permission set comb. Let have permission set comb . Let have permission set comb . Define a theory ULAME by:
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).
Suppose p(p(comb and comb. We sketch two ULAME derivations in calculational style; the full derivation trees can easily be reconstructed:
Here, we choose fresh, so comb (and by our permutative convention is not equal to or ).
Define fV () by:
Lemma 18 is a key difference from nominal terms. Later, when we write ‘choose fresh’, we are using Lemma 18:
fa() is always infinite.
By induction on . We consider one case: fa( p() and by assumption ( p()) is infinite.
The following lemmas are proved by inductions just as in [32]:
id , and () () .
fa( fa().
() ().
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 [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
Define -terms by:
Here f ranges over term-formers, ranges over atoms, and ranges over unknowns. will range over -terms.
Define a permutation action by:
Define free atoms by:
Call a function from unknowns to -terms a (-calculus) substitution. will range over substitutions.
Write [] for the substitution which maps to and maps all other to .
Define the capture-avoiding substitution action on -terms by:
An axiom is a pair . A (-)theory is a set of axioms. L will range over theories.
Define derivable equality by:
Write L when is derivable using only instances (Lax) for () L. Also: - Write when . - Write when with a derivation that does not use (L). - Write when with a derivation that does not use (L), (Lvar), (L#), (Lid), (L), or (Lapp). - Write when with a derivation that does not use (L), (Lvar), (L#), (Lid), (L), or (Lapp). Λ will range over derivations.
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) 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 [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 (Lvar), (Lid), (L), and (Lapp) 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 . 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 [] can be obtained by (), and the effect of the capturing substitution [] on the nominal term [] can be obtained by the capture-avoiding substitution []. Here, is ‘raised’ over .
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 [] to -terms functional abstraction . 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 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 -, 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 to a vector (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.
Call a finite list of distinct atoms a vector. will range over vectors. Write [] for the vector containing , ... , in that order.
We use the following notation: Suppose . - Write for the vector of atoms in that occur in , in order; thus [] ]. - Write when every atom in is in . - Write when every atom in is in . - Write for the set of atoms appearing in or . - If and are vectors, write when every atom in is contained in (not necessarily in the same order). - If is a permutation and ], write for the vector [()()] (the pointwise action).
Suppose ]. Write as shorthand for (a list of -abstractions). Write as shorthand for (a list of applications).
Write atoms() for the set of atoms appearing in . Similarly write atoms() for the set of atoms appearing in (for example, atoms(() atoms([][]); 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)).
For each finite set of atoms make a fixed but arbitrary choice of order on .
Translate a nominal term to a -term by:
Extend the translation to substitutions, equalities, and theories by:
In the translation of T, is atoms() atoms() in the order chosen in Definition 34.
id , and () ()
().
If nontriv() fa() then ().
The first two parts can be proved by inductions on a measure of the size of .
For the third part, we work by induction on the length of . If has one element we use the first part. Suppose has more than one element. Write () ) , head(, and tail( (head() is the first element in and tail() is the other elements). There are two cases, depending on whether ( or () . We consider only the case () ; the other is similar.
Note the following facts: (() for every in , (, nontriv() fa() , and (() ) . We reason as follows: ()() ()()() Facts
By induction on .
fa() fa().
By induction on . We consider one case. - The case . We reason as follows, where [
fa( fa(() ()) Definition 35
If atoms() then .
Suppose comb and comb. Consider []() where p( comb. Note that atoms( . Take ] and ]. It is a fact that ().
Take id. Then () (), and
Take ]. Then () , and
Finally, take ]. Then () , and
Now take and ], so that the condition of Theorem 40 fails. It is a fact that . Take id. Then ( and
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).
If Π is a derivation of T and T then there exists a derivation of , and atoms atoms().
Similarly, if Λ is a derivation of L and L then there exists a derivation of , and atoms atoms().
Since a derivation that mentions only axioms in T (or L) is also one that mentions only axioms in (or ).
Suppose Π is a derivation of T . Suppose atoms(Π) . Then there is a derivation Π of T .
By induction on Π. - (Nref), (Ntran), (Napp), and (N) translate to (Lref), (Ltran), (Lapp), and (L) respectively. - The case (N). Suppose fa(). Then fa() by Lemma 39. By (L), () . We use Lemma 42. - The case (Nax) for () T.
Let be the vector of atoms containing atoms() atoms() chosen in Definition 35. We need to show that T () (). First, we note the following:
The use of Lemma 37 is valid since nontriv() by assumption. The use of Theorem 40 is valid since atoms() by assumption. By the same reasoning for we note that
We use Lemma 42 and (Lax).
Suppose p( comb and suppose comb and comb. Consider term-formers A and E.
Consider a theory F with one axiom E[]A[] E[]. Then FEA( E().
There is a trivial derivation of F E[]A[] E[]. Take ]. It is not hard to construct a derivation of F EA( E(), by instantiating to in F.
Suppose () ULAME. For every and , () ().
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 -, 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 . Our -terms have no capturing substitution, so this makes sense; the vector in - is just there to obtain inverse properties with respect to -, 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.
Suppose ]. Continuing Definition 32 write [] as shorthand for [] [] (a list of atoms-abstractions).
If is a -term and is a vector of atoms, define a nominal term by:
Call good when fa(()) p() for all . Extend the translation to good substitutions, equalities, and theories by:
We take to be undefined if is not good. The condition fa(()) p() is sufficient to ensure that fa() p() always, so that 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, is atoms()atoms() 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 (Lvar), (L#), (Lid), (L), (Lapp), and (L).
fa() fa().
By induction on .
Suppose fa(()) for every fV () and suppose is good. Then ULAME .
Call a derivation Λ good when is good for every (ax) in Λ.
Suppose Λ is a good derivation of L . Then for any there is a derivation Λ of L .
We work by induction on Λ: - (Lrefl), (Ltran), (Lapp), and (L) translate to (Nrefl), (Ntran), (Napp), and (Nabs) respectively. - The case (Lax). We want that L .
By Lemma 49 L and L
(here [] is the empty list of atoms). Also by (Nax) we have L id ( id (. The result follows using (Ltran) and Lemma 36. - The case (L#). There are two cases:
- L () where fa(), and is the atom we chose to use in the axiom (N#) of ULAME (Definition 14). - L () where fa(), and is different from the atom we chose to use in axiom (N#). We consider only the second case; the first case is similar. Let be any permutation such that ( and such that (fa() fa()) comb (that is, maps to and maps the atoms in fa() to be inside comb, and the atoms in fa() to be inside comb). Let be the substitution mapping to () and to () and every other to id . We consider (Nax), where (([]) (N#). We verify that this gives the right result: By Lemmas 20 and 48 fa(()) comb and fa( ()) comb. Therefore, is a substitution (Definition 10). Also:
Similarly, () as required. - The case of (L) is similar (we translate to an instance of (Nax) for (N), and use Lemma 48). - (Lvar), (L), (Lapp) translate to instances of (Nax) for (Nvar), (N), and (Napp) respectively.
Suppose p( comb and suppose comb and comb. Consider term-formers A and E.
Consider a theory G with one axiom EA( E(). Then GE[]A[](([]) E[](([])).
There is a trivial derivation of G EA( E(). Take . It is not hard to construct a derivation of G E[]A[]( E[](), by instantiating to in G and using (Nid).
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.
Suppose Π is a derivation of T . Suppose atoms(Π) . Then Π from Theorem 43 is a good derivation of T .
Call a bijection on unknowns a renaming. will range over renamings.
Each is also a substitution (Definition 25). Write for acting on as a substitution. Write L for the set () L. Write (Λ) for the tree obtained by mapping every (ax) to (ax).
It is a fact that if Λ is a derivation of L then (Λ) is a derivation of L.
Suppose Λ is a derivation of L . Then there exists a such that (Λ) is a good derivation of L.
Let be the set of all atoms mentioned in Λ. It suffices to choose such that for each mentioned in Λ, p(()).
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.
ULAME ([]).
If nontriv() fa() then ULAME ([])( .
For the first two parts, we reason as follows:
The proof of the third part is like the proof of the third part of Lemma 37.
If atoms() then ULAME . As a corollary, if atoms() and ULAMET then T .
.
As a corollary, L always.
The corollary follows by Lemma 42. We prove the first part by induction on . We consider one case: - The case . Write p(). We reason as follows:
Suppose T and are two theories. Write T when for all and , T if and only if .
Similarly for L and .
T if and only if T for every ( ) and also for every () T.
Similarly for L and .
The left-to-right implication is immediate. The right-to-left implication is by a routine induction on derivations.
We observe the following set inclusions:
By routine inductions on and .
If ULAME T then T T.
L L always.
We use Lemma 60.
Suppose () T. Let be the vector of atoms chosen for atoms() atoms() in Definition 34. By Lemma 61 atoms()atoms( atoms(). Therefore, T. By assumption atoms() and atoms() . The result follows by (Ntran) and by Lemma 57.
Conversely, suppose () T. From Definition 47 and Lemma 61 there are two cases: - () ULAME. - ( ) for some ( ) T.
We use Lemma 57 as before. Suppose () L. Let be the vector of atoms chosen for atoms() atoms() in Definition 34. By Lemma 61 atoms()atoms( atoms(). Therefore, ( ) L. We use (Ltran) and Lemma 58.
Suppose () L. There are two possibilities: - ( ) for some () ULAME.
By Theorem 45 and Lemma 42, L . - ( ) for some ( ) L.
We use Lemma 58 as before.
4.4 The translations - and - are inverse on derivations, if 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 . 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].
If Π is a derivation of T then there exists a derivation Π of T . Furthermore, atoms(Π) atoms(Π) atoms(Π) fa(()) occurs in Π.
We apply to every term in Π to obtain Π and verify by induction that Π is a derivation of T .
Suppose Π is a derivation of T . Suppose atoms(ULAME). Then there is a derivation of T , and atoms(Π)atoms()atoms(Π).
Suppose ULAME T. - Suppose Π is a derivation of T . Then Π is a derivation of T for any such that atoms(Π) . - Suppose T and atoms() atoms() .
Then T . - Suppose Λ is a derivation of L . There exists a renaming (Definition 54) such that for any , L .
- Suppose L for some and some . Then
- This is Theorem 43. - Suppose T where atoms()atoms() .
By Lemma 53 and Theorem 51 T . By Theorem 62 T T. By Lemma 57 since ULAME T and atoms() , T , and similarly for . It follows by (Ltran) that T as required. - By Lemma 55 there exists a such that (Λ) is a good derivation of L. The result follows by Theorem 51. - Suppose Π is a derivation of L . Choose any such that atoms(Π) atoms(ULAME) . By Corollary 64 there is a derivation of L and atoms() . By Theorem 43 L . By Theorem 62 L L. By Lemma 58, L , and similarly for . It follows by (Ltran) that L. Since is invertible, we can use Lemma 55 to verify that L as required.
Suppose Φ() is some assertion (in English) which depends on a vector . Write “Φ() holds for sufficiently large ” to mean “there exists a such that for all , if (Definition 31) then Φ()”.
Suppose ULAME T. Then: - T if and only if T for sufficiently large . - For any , L if and only if there exists a such that
Direct from Theorem 65.
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() is sufficiently large for relevant ” (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 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 p() 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 #; these correspond in the notation of this paper with p() (“ is not in the permissions set of ”). Thus the translation of Definition 35 would be indexed by , so we might write it as .
The difference is that we may need to change , and there is no natural notion of fa(). Often, we must obtain fresh atoms; see for example the case [] 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() . Then for any , there exists some freshly extended such that .
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 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 ) for finite . What we have defined here, will be enough for our needs. ↩
3 ‘fa(()) p()’ 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 ‘#()’ 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 - and - 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. ↩