Nominal renaming sets
Abstract. Nominal techniques are based on the idea of sets with a finitely-supported atoms-permutation action. We consider the idea of nominal renaming sets, which are sets with a finitely-supported atoms-renaming action; renamings can identify atoms, permutations cannot. We show that nominal renaming sets exhibit many of the useful qualities found in (permutative) nominal sets; an elementary sets-based presentation, inductive datatypes of syntax up to binding, cartesian closure, and being a topos. Unlike is the case for nominal sets, the notion of names-abstraction coincides with functional abstraction. Thus we obtain a concrete presentation of sheaves on the category of finite sets in the form of a category of sets with structure.
Keywords: Nominal renaming sets, nominal sets, abstract syntax with binding.
1 Introduction
The motivation of this work is to provide semantic foundations for formal theories of syntax with variable binding. Several such theories have been proposed in the literature [5,17,16,14,19] and used in concrete applications with varying success [15,4,25,18,21]. All but the most elementary approaches require some semantical or proof-theoretical justification asserting their soundness and also explaining the meaning of the judgements made. Functor categories (categories of (pre)sheaves) are a popular method [7,16,3,8] for providing such foundations. However, proofs involving presheaves are notoriously complicated and require a thorough working knowledge so as to be able to reduce clutter by elision of trivial steps. In some situations [21,25], a sets-based semantics is available in the form of nominal sets [14] which considerably simplifies metatheoretic reasoning. A domains version of nominal sets [20] has also become an important tool in denotational semantics of languages with dynamic allocation [1]
This paper provides a sets-based foundation for another class of systems for higher-order syntax including in particular the theory of contexts [17] which could hitherto only be modelled with functor categories. This will allow us to considerably simplify the cumbersome functor-theoretic proof of soundness of that theory [3]. In this way, we expect that our sets-based presentation of the semantics will then allow to justify further extensions which would until now be too complicated to work through.
Note that we do not propose yet another approach to higher-order syntax. Rather, we introduce a simplified presentation, up to categorical equivalence, of an existing semantic model. We now summarise the contributions of the paper in more detail.
Write for the category of finite sets and injections between them, write for the category of finite sets and all (not necessarily injective) functions between them, and write Set for the category of sets3 and functions between them.
Previous work presented nominal sets [13]. These can be presented as the category of pullback-preserving presheaves in Set. Simultaneously, Fiore et al [7] and Hofmann [16] proposed to use Set for higher-order abstract syntax. Both can be used as mathematical models for inductive specification and reasoning on syntax with binding.
In Set for a presheaf , the presheaf given by (() for is isomorphic to the exponential A . In the category of nominal sets the corresponding presheaf is isomorphic to A , with being the right adjoint to a tensor product different from cartesian product (it is mentioned in Theorem 34 and is written [A]X). In either case the presheaf A is given by A(. Thus, Set seems better-suited for modelling higher-order abstract syntax, which uses typings like
for variable binding constructs (in this case: ‘lambda’). This arises when using an existing theorem prover or type theory (for example Coq) to model higher-order abstract syntax [6,17]. In particular, in [3] the presheaf category from [16] was used to establish soundness of the theory of contexts from [17].
FreshML [23] and the deep embeddings of the nominal datatypes package [25] provide a syntactic primitive corresponding to the right adjoint mentioned above. They use typings like
Precomposing with the canonical map () (), one could justify the typing in (1), but lam would not be injective. For the typing
used in the Twelf system [19], another presheaf topos ( in [16]) is adequate. The constructions of this paper cannot be applied to this directly, but see the Conclusions.
The nominal approach benefits from a sets-based presentation. Denotations of types are sets with structure — whence the name ‘nominal sets’ — rather than functors.
In this paper we offer a sets-based presentation of the full subcategory of Set of functors preserving pullbacks of monos. We present it as a category of sets with a not-necessarily-injective renaming action. The pullback requirement implies that () is isomorphic to ‘the intersection of’ () and (), in line with the intuition ‘objects with free variables from ’ for (). This rules out artefacts present in Set like ( if 1 then else , which never arise as denotations of types in higher-order abstract syntax.
In [16] it was argued that the internal logic of Set qua topos might be unsuited to reasoning with higher-order abstract syntax since equality of atoms (names, variables) is not decidable in it. It was proposed in loc. cit. to import the logic of the Schanuel topos using a pullback of triposes. Our presentation of this pullback construction amounts to interpreting predicates as equivariant subsets; subsets of a renaming set stable under injective renamings. Staton and Fiore [8] define a category of substitution sets equivalent to a sheaf subcategory of Set. Their category is not defined concretely in terms of ordinary sets but as a theory within the Schanuel topos. It does not make Set easier to work with (and Staton and Fiore never introduced it for that purpose).
We also characterise the function space of nominal renaming sets as a set of functions, rather than a Kripke exponential transported along the equivalence, and we identify the tripos structure needed to reason about renaming sets in a robust way, and in particular, to justify the theory of contexts.
Some notation: This paper uses three different kinds of arrow. For the reader’s convenience we survey their definitions; this is all standard.
If and are sets then is the set of functions from to .
If X and Y are nominal renaming sets then X Y is the set of arrows from X to Y in the category Ren (Definition 5). These are maps in XY with empty support (Lemma 25).
X Y is the exponential (Definition 20 and Theorem 26). These are maps in XY with finite support (Lemma 21).
2 Nominal renaming sets
Fix a countably infinite set of atoms A. We assume that atoms are disjoint from numbers 0 1 2, truth-values , and other standard mathematical entities. A can be viewed as a set of urelemente [2,13,10]; we view them as a model of names or variable symbols.
will range over atoms. We follow a permutative convention that simultaneously introduced metavariables for atoms range permutatively; for example and range over any two distinct atoms.4
Let Fin be the set of functions A A such that there exists some finite A such that for all A it is the case that (.
will range over elements of Fin. We call these (finitely supported) renamings.
Write [] for the function that maps to for 1 and maps all other (that is, atoms not in the set ) to themselves. Note that every function in Fin can be written in this fashion.
In particular, write [] for the function which ‘maps to ’:
We write for functional composition. For example [] [] (and [] [] ]). Write id for the identity renaming. id( always.
Fin with and id is a monoid. That is, id id and ( () . If A and Fin, write for the partial function equal to on and undefined elsewhere.
A nominal renaming set X is a pair (X) of an underlying set X and a finitely-supported renaming action .
A finitely-supported renaming action is a map from Fin X to X such that:
id always.
() always.
For every X there is a finite A such that implies .
We say that every X has finite support.
Henceforth X and Y range over nominal renaming sets. and range over elements of X and and range over elements of Y unless stated otherwise.
Nominal renaming sets form a category Ren. Objects are nominal renaming sets. An arrow : X Y is a function XY such that (() always. will range over arrows.
For example: A with action () is a nominal renaming set. We have supp(. We will write this renaming set by A, too. In general, we will distinguish notationally between a renaming set X and its underlying set X.
Call X trivial when for all X and Fin (so supp( always). Write B ) for a two-element trivial nominal renaming set. We conclude with one more useful definition:
Let X Y have underlying set XY (that is, X Y is a pair () where X and Y) and pointwise renaming action (that is, ( ()). Call this the product of X and Y.
2.1 Support of nominal renaming sets
Say A supports when for all , if then .
Lemma 8 and Theorem 9 echo [13, Proposition 3.4]. The proofs for nominal renaming set are simpler:
If A support then so does .
Suppose . Define Fin by: (() if , and (() if A . so . It is not hard to verify that so . The result follows.
has a unique finite least supporting set supp(); the support of .
implies .
If the reader thinks of fv (free variables of) when they see supp, they will not go far wrong [13, Example 6.11]. However, support is an abstract notion valid for any element of any nominal renaming set.
As is standard in nominal techniques we write # for supp(), and read it as ‘ is fresh for ’. We may write # for ‘# and #’, and so on.
Let PFin have underlying set the collection of finite sets of atoms, with pointwise renaming action.
That is, if A is finite then () . It is not hard to prove that supp( always.
1. supp() supp().
2. If is injective on supp() then supp( supp().
For the first part, we will show that supp() supports . The claim then follows. To see the former suppose that . We then have ()), hence )).
For the second part, it suffices to prove the reverse inclusion. Suppose []. By assumption if then for 1 . So we can form ]. By Theorem 9 . By part 1 of this result supp() supp(). Thus, supp( supp() supp().
Now, if supp() then by part 1 of this result we can write () for some supp(). So, . We have thus shown supp() supp() and hence the claim.
We remark that the extra assumption of injectivity for the second part is not redundant.
Corollary 12 helps to calculate support:
If supp() then [] . Taking the contrapositive, if [] then #. Note that is an implicit assumption.
By part 1 of Lemma 11 supp([] ). We assumed supp(), the result follows.
supports if and only if id implies for all .
The left-to-right implication is direct from the definition of ‘supports’. For the right-to-left implication we will show supp() . To that end, pick supp() and supp(). From Corollary 12 we then obtain for ]. Hence id, hence .
We need Lemma 14 for Lemma 33 and Corollary 29:
Suppose # and #.
Then [] ] if and only if # and ] .
3 The exponential
Let X Y be the set of functions XY such that there exists some finite A (for each , we fix one such ) such that for all Fin and X if id then
X Y serves as an underlying set in Definition 20. First, we consider some examples and prove properties of X Y.
X YX mapping () to is in (X Y) X.
The map A AB mapping () to if and to if , is not an element of (A A) B. Unpacking definitions, the reason is that there is no finite A such that if id then for all A, if and only if (().
XPFin mapping to supp(), may or may not be an element of X PFin. If X A then supp( and supp(() supp(()). Therefore A PFin. Similarly for .
On the other hand if we let X have XPFin (finite sets of atoms) and the renaming action such that () if is injective, and otherwise, then X PFin.
Intuitively, a map that does not compare atoms in its argument for inequality will be in the underlying set of the exponential. A map that compares atoms for inequality, will not. See the Conclusions for further discussion.
Elements of X Y are determined by their ‘asymptotic behaviour’:
Suppose X Y and X Y. Suppose also A is finite and assume that for all X if supp() then ((). Then .
Choose any X. There are two cases:
If supp() then by assumption (().
If supp() then let be a fresh choice of atoms (so ( supp(). Let ] and T []. By Lemma 11 supp() . We reason as follows:
An element of the function space can be reconstructed from ‘asymptotic’ behaviour:
Suppose is a partial function from X to Y. Suppose A is finite and: supp() implies () is defined, and id implies ( (), where both are defined.
Then there is a unique X Y extending (so (() if () is defined).
First, we define . Consider X, write supp(. Let be fresh atoms (so supp(). Define
] T ] and ( ()
We first show the choice of fresh does not matter. Suppose is also fresh (so supp(). We put ] and ]. We must show ((). We assume the special case that
The general case follows by two applications of the special case for an ‘even fresher’ set of fresh atoms . We write ] and ]. By Theorem 9 and supp( we have . Also, by we have ((). Therefore ( ()
We recall (5); by Theorem 9 and supp((, (() The claim that the choice of fresh does not matter, follows.
To see that indeed extends we suppose that X and that () is defined. Then supp() so () is also defined. By assumption on we have (( () where the last equality uses Theorem 9.
To see that X Y we put . Suppose that id. We have seen that the choice of the fresh does not matter so that we can assume that and T commute with . We then have ( ( (().
Uniqueness of is now by Lemma 18.
Let X Y have underlying set X Y with renaming action
By Lemma 19 this uniquely determines the renaming action for all X.
X Y is a nominal renaming set.
X Y is supported by the set from Definition 15, for suppose that id By Lemma 13 it suffices to show . Now put () . This is a finite set so by Lemma 18 it suffices to show ()(() for all such that supp() . Fix such an . By Theorem 9 so by (6) we know ()((). supp() by assumption so by (4) we know ((). Then (() since . The result follows.
()(), for X Y.
Write supp() supp() () . Choose fresh , so (supp() and id. Define
If XY then the following are equivalent:
For all X and Fin, if id then (().
supp() .
Compare Corollary 24 with [13, Example 4.9, (24)]:
supp(()) supp() supp() always, for X Y.
Arrows : X Y are exactly X Y such that supp(.
- - is an exponential in Ren.
We show that currying and uncurrying are arrows between (X Y) Z and X (Y Z). The equations are then inherited. Currying: Take (X Y) Z. For X we put Y()). We show that X X (Y Z):
If we put supp(). If id then ( (((), so X Y.
To see that is an arrow pick arbitrary . We need to show . Appealing to Lemma 18 we choose Y with and supp() disjoint from supp( supp(). We then have ()((( (((). Uncurrying: Take X (YZ). We show that ()X Y()() (X Y) Z:
It suffices to show that ()(()(). Now ()( ())() by Theorem 22 and (() by Definition 5.
Lemma 27 does for Ren what [13, Lemma 6.3] does for the category of nominal sets. We can develop similar inductive and recursive principles for syntax-with-binding as are exhibited using the Gabbay-Pitts -quantifier in Theorem 6.5 in [13].
There is a bijection between : (A X) Y such that #() always, and (A X) Y.
We define mappings as follows:
maps to A X() where (as is standard [13]) () is equal to () for any such that #.
maps to () A X(A[] ).
We can prove this is well-defined, and the result follows by calculations.
4 The atoms-exponential A X
If A X then A[] for some X and #.
By Definition 20 A X when AX and there is a finite A such that Fin, A, and id imply ((()). Choose and A. Then (([] ] (), and we take ().
Two functions on atoms are equal if they agree for one fresh atom; compare this for example with axiom () in the theory of contexts [17, Figure 4] and the extensionality principle for concretion of the Gabbay-Pitts model of atoms-abstraction in nominal sets [13, Proposition 5.5, equation (48)]:
Suppose A X and suppose # and #. Then ( () if and only if .
Suppose A Y. Then # if and only if #(), for any # (by our permutative convention, ).
Equivalently, supp( supp(()) for any #.
A[] is supported by supp(); thus A[]AX.
The corollary is immediate given the first part, by Definition 15. We now prove that supp() supports A[]. By Corollary 23 it suffices to show id implies A[] A[] .
So suppose id. By Corollary 29 it suffices to check
for fresh . Choose such that #A[] , #A[] , ( and #. By Theorem 22 since ( we have that
So it suffices to check that []]. We assumed id and #. It follows that ( [])]. By Theorem 9 the result follows.
supp(A[] supp() .
Suppose X, and A. Then A[] A[] if and only if # and ] .
The reader may recognise these results from the theory of the Gabbay-Pitts model of atoms-abstraction in nominal sets [13, Definition 5.4]. A nominal renaming set is also a nominal permutation set (by ‘forgetting’ the action for non-bijective ); using Corollary 12 it can be proved [11, Theorem 4.8] that the notions of support coincide. In the spirit of [13, (35)] we can write5 []()( [] ) # and [A]X[] AX. The proof of Theorem 34 is now routine [11, Theorem 5.7]:
A X is in bijective correspondence with [A]X. Inverse mappings are given by:
maps [A]X to A[] , for ().
maps A X to [](), for #.
5 Presheaf and topos structure of Ren
For convenience, take the finite sets in and from the Introduction to be finite .
We could now go on and exhibit the subobject classifier in Ren, thus establishing that Ren is a topos, and hence is a model of higher-order logic. This is not hard to do: a subobject classifier is the renaming set with underlying set those Fin such that:
If then for all Fin.
There exists finite A such that and id imply .
The renaming action is given by . The proof that this makes Ren into a topos is by standard calculations. We also remark that Ren is a Grothendieck topos for a topology on the opposite of the category of finite sets and functions and thus a full subcategory of the functor category Set. The required topology has for basic covers of an object nonempty families of monos : . The interested reader is referred to [24] where a proof of a similar result is worked out.
We now characterise Ren as a category of presheaves.
Let PBM be the category of presheaves in Set that preserve pullbacks of pairs of monos, and natural transformations between them.
If is a function let its image img() be () . Note that monos in and Ren are injections, and that a pullback of a pair of monos is given by set intersection with the natural inclusion maps. Write ‘ : ’ for “ and we write for the subset inclusion arrow in ”.
Fix PBM. Let () range over pairs where A is finite and (). Write for the least equivalence relation such that : implies () (()()).
If : and : and () () () then there exists some () such that () (). Thus, each -equivalence class has a unique least representative (), ‘least’ in the sense that if () () then : and ()().
Ren is equivalent to PBM.
X maps to mapping to X supp() and mapping : to the renaming action of extended to a total function which is the identity off . This is a presheaf by part 1 of Lemma 11 and we can prove that it preserves pullbacks of monos using Lemma 8. maps to the set of unique least representative elements of -equivalence classes, as constructed in Lemma 37 with action given by () is the representative of the -equivalence class of (()()). The result follows by routine calculations.
Preserving pullbacks of monos, and the corollary that we have ‘least representatives’, makes possible the sets-based presentation of nominal sets and nominal renaming sets, contrasting with the purely presheaf-based presentations of [7,16].
6 Tripos structure on Ren
As argued in [16] the topos logic of , thus also that of Ren, is unsuited to reasoning about syntax with binding. For example equality of atoms is not decidable in that logic. In fact, in the topos logic of Ren and , the proposition A() holds.
It was proposed in [16] to use the tripos obtained by pulling back the logic from the Schanuel topos instead. In particular, the tripos so obtained is needed to justify the theory of contexts [17] (well — almost; the restriction to pullback-preserving functors had not been made explicit in that paper.)
In keeping with our goal of making these constructions concrete and usable for direct calculations, we make this construction explicit at the level of Ren.
For a nominal renaming set X let Pred(X) be the set of those subsets of X that are preserved by bijective renamings, i.e., for which implies provided that Fin is bijective, i.e., a permutation.
Pred(X) is ordered by subset inclusion and Pred() extends to a functor Ren Poset where Pred()(() when : X Y and Pred(Y).
We remark that in the topos logic of Ren a predicate is a subset preserved by all renamings, not just the bijective ones.
Theorem 40 is a consequence of the folklore result stated in [16] which asserts that triposes can be pulled back along finite-limit-preserving functors with a right adjoint (‘geometric morphisms’). Rather than detailing this argument we illustrate the tripos structure by concrete constructions below.
The pair (Ren Pred) forms a tripos.
This means there is enough structure to interpret higher-order logic. In particular, predicates are closed under boolean operations, universal quantification over renaming sets, and there is a renaming set O of propositions such that morphisms X O are in 1-1 correspondence with elements of Pred(X). We explicitly construct these ingredients in order to demonstrate that the logic for Ren is quite close to classical set-theoretic reasoning in contrast to the functorial reasoning that was used in [17].
The object of propositions O in the tripos (Ren Pred) has underlying set those Fin such that:
If and Fin is a permutation then
There exists finite X such that if then iff .
The renaming action in O is given by .
If Pred(X) then a morphism : X O is defined by ( . Conversely, if : X O is a morphism then we associate the predicate ( where O is given by Fin.
The logic of (Ren Pred) is classical.
It suffices to show that if Pred(X) is a predicate then its set-theoretic complement is again a predicate. But if Fin is a permutation and then for otherwise .
Let Pred(X Y) (possibly given by a morphism X Y O). Its universal quantification Pred(X) is given by Y() .
Suppose that Pred(X). We have to show that is a predicate and that the following are equivalent:
for all X and Y if then ()
for all X if then
The equivalence being obvious from the definition it only remains to show that is indeed a predicate. So assume that Fin is a permutation and consider that . If Y then () since . So, () since is a renaming set. Hence, since was arbitrary, as required.
Logical operations in (Ren Pred) are given by their standard meanings in classical set theory. Propositions are elements of O rather than of 0 1. Note that the axiom of unique choice (which identifies functional relations with morphisms) is not valid in (Ren Pred). Indeed, a functional relation, i.e., a predicate on XY such that for all X there is a unique Y such that () , does not in general give rise to a morphism from X to Y. Indeed, in [16] it was shown that the Axiom of Unique Choice is an inconsistent extension of the theory of contexts. There is a unique function such that (()) for all X but in general it will be invariant under permutations, not all renamings.
7 Conclusions
Nominal renaming sets are a natural evolution of nominal sets. The connection between Ren and the category of nominal sets [13] is evident. However, the details are not entirely straightforward; proofs have to be changed and sometimes they take on a very different character. In particular the definition of the action for function spaces in the permutative case ()(() does not carry over, because need not exist. It is replaced by an a priori partial definition (Definition 20) which is totalised with a unique extension theorem (Lemma 19).
Nominal renaming sets are related to Set as featured in [7] and [16]; they correspond to the pullback-preserving presheaves (Theorem 38). Ren has appeared before; the first author discussed the idea in his thesis [9, Section 11.1] and studied a generalisation of nominal renaming sets as an algebraic theory over nominal sets in [12]. Meanwhile, a category equivalent to Ren was independently presented, also as an algebraic theory over nominal sets, in [8, Definition 2.4]. The constructions presented in this paper, notably the exponential and the tripos structure, are new and do not follow directly from these earlier results. It is thanks to these explicit constructions that Ren can serve as a sets-based semantic underpinning for weak HOAS, i.e. that we can do calculations entirely within Ren, without switching to a functor category. To our knowledge, we are the first to suggest applying renaming sets as a semantic basis for weak HOAS in the sense of Despeyroux [5] and in particular the theory of contexts [17].
Future work.
It will be interesting to give details of a proof of validity of the theory of contexts using nominal renaming sets. In this conference paper we have not done that, but such a proof could be based on the one in [17], and should be simplified thanks to the use of set-theoretic language (most of the time). Note that no notion of forcing is required.
Nominal sets have been generalised to ‘nominal domains’ [22] thus giving access to fresh names in denotational semantics. It would be interesting to generalise renaming sets in this way as well, giving access to fresh names with substitution within a functional metalanguage. Here, our explicitation of the exponential (Section 3) may be particularly useful.
Nominal renaming sets belong to a family of structures with a finitely supported substitution action. Probably they are the simplest, but others may also be interesting. For example, define a nominal substitution set to be a pair of a nominal renaming set X and a function sub : ((A X) X) X such that
If # then [.
If # then [][[][[]].
Here we write [] for sub(A[]). A category of nominal substitution sets has arrows maps : X Y such that ([())[()].
(This can also be phrased directly using ‘normal’ sets.) We conjecture that this definition or a refinement of it will be useful to give semantics to typings like (tm tm) tm used for binders, for example in Twelf [19], for which hitherto only purely presheaf semantics are available [16].
References
1. Nick Benton and Benjamin Leperchey. Relational reasoning in a nominal semantics for storage. In Pawel Urzyczyn, editor, TLCA, volume 3461 of Lecture Notes in Computer Science, pages 86–101. Springer, 2005.
2. Norbert Brunner. 75 years of independence proofs by Fraenkel-Mostowski permutation models. Mathematica Japonica, 43:177–199, 1996.
3. Anna Bucalo, Furio Honsell, Marino Miculan, Ivan Scagnetto, and Martin Hofmann. Consistency of the theory of contexts. Journal of Functional Programming, 16(3):327–395, 2006.
4. Joelle Despeyroux. A higher-order specification of the –calculus. In IFIP TCS, pages 425–439, 2000.
5. Joëlle Despeyroux, Amy P. Felty, and André Hirschowitz. Higher-order abstract syntax in COQ. In TLCA’95, volume 3461 of Lecture Notes in Computer Science, pages 124–138, 1995.
6. Joëlle Despeyroux and André Hirschowitz. Higher-order abstract syntax with induction in COQ. In LPAR’94, volume 822 of Lecture Notes in Computer Science, pages 159–173. Springer, 1994.
7. Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi. Abstract syntax and variable binding. In LICS’99, pages 193–202. IEEE, 1999.
8. Marcelo P. Fiore and Sam Staton. A congruence rule format for name-passing process calculi from mathematical structural operational semantics. In LICS’06, pages 49–58. IEEE, 2006.
9. Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
10. Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205:982–1011, July 2007.
11. Murdoch J. Gabbay. Nominal renaming sets. Technical Report HW-MACS-TR-0058, Heriot-Watt University, 2007.
12. Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC, volume 4281 of Lecture Notes in Computer Science, pages 198–212, 2006.
13. Murdoch J. Gabbay and A. M. Pitts. A New Approach to Abstract Syntax with Variable Binding (journal version). Formal Aspects of Computing, 13(3–5):341–363, 2001.
14. Murdoch J. Gabbay and Andrew M. Pitts. A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, 1999.
15. Daniel Hirschkoff. A full formalization of pi-calculus theory in the Calculus of Constructions. In E. Gunter and A. Felty, editors, Proceedings of TPHOLs’97, pages 153–169, Murray Hill, 1997.
16. Martin Hofmann. Semantical analysis of higher-order abstract syntax. In 14th Annual Symposium on Logic in Computer Science, pages 204–213. IEEE, 1999.
17. Furio Honsell, Marino Miculan, and Ivan Scagnetto. An axiomatic approach to metareasoning on nominal algebras in HOAS. In ICALP’01, volume 2076, pages 963–978. Lecture Notes in Computer Science, 2001.
18. James McKinna and Robert Pollack. Some lambda calculus and type theory formalized. Journal of Automated Reasoning, 23(3-4):373–409, 1999.
19. Frank Pfenning and Carsten Schürmann. System description: Twelf - a meta-logical framework for deductive systems. In CADE’16, volume 1632 of Lecture Notes in Computer Science, pages 202–206. Springer, 1999.
20. M. R. Shinwell. The Fresh Approach: Functional Programming with Names and Binders. PhD thesis, Computer Laboratory, University of Cambridge, December 2004.
21. M. R. Shinwell, A. M. Pitts, and Murdoch J. Gabbay. FreshML: Programming with binders made simple. In ICFP’2003, volume 38(9) of SIGPLAN Not., pages 263–274. ACM Press, 2003.
22. Mark R. Shinwell and Andrew M. Pitts. On a monadic semantics for freshness. Theoretical Computer Science, 342(1):28–55, 2005.
23. M.R. Shinwell and A.M. Pitts. Fresh objective Caml user manual. Technical Report UCAM-CL-TR-621, University of Cambridge, 2005.
24. Sam Staton. Name-passing process calculi: operational models and structural operational semantics. PhD thesis, University of Cambridge, 2007.
25. Christian Urban and Christine Tasson. Nominal techniques in Isabelle/HOL. In CADE’05, volume 3632 of Lecture Notes in Artificial Intelligence, pages 38–53, 2005.
Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.
Notes
3 It is convenient, but not necessary, to take this to be the category of ‘ordinary’ ZF sets (not mentioning atoms). Since we are working at the meta-level, this is in fact not important and any sufficiently rich collection of collections of elements will do. ↩
4 Note that we are working in the usual naïve set-theoretic metalanguage; atoms form a set. At that level, atoms have a decidable equality. ↩
5 The use of [] instead of the swapping () (swapping defined in [13, (3)]) is immaterial because # and so the actions coincide by Theorem 9. ↩