Stone duality for nominal Boolean algebras with ‘new’: topologising Banonas
Abstract. We define Boolean algebras over nominal sets with a function-symbol mirroring the ‘fresh name’ quantifier. We also define dual notions of nominal topology and Stone space, prove a representation theorem over fields of nominal sets, and extend this to a Stone duality.
1 Introduction
() means ‘for fresh , () holds’. Here is intended to be an atomic resource: examples are a variable symbol, memory location, channel name, or (in security) nonce.
is interesting from both a mathematical and computational point of view. It is self-dual (() ()) and this gives a computationally useful some/any property: to prove we check () for some fresh name, but we can then use any fresh . (Definitions below or in [18,14].)
also appears to be useful. It has been applied to syntax-with-binding [18], resource generation in functional programming [29], local names in incomplete trees [5], -calculus name-restriction [3], game semantics [1,33], and domains [32]. See Example 3.6 for more discussion.
Proof-theories for have been suggested [11,15,7,10], but no equational axiomatisation or representation theorem. Nominal domains have been studied, but not topologies. As we shall see, algebra and topology with are non-trivial and interesting.
In this paper we study Boolean logic with in nominal sets. We introduce Banonas (Boolean Algebra, NOminal with a) and nominal Stone spaces, and prove representation and duality theorems.
Stone’s representation does not generalise easily to nominal sets: the ultra-filter lemma breaks down (since a union of finitely-supported sets need not be finitely-supported). To ‘fix’ this, a name-restriction operation seems to be required. So Banonas seem to arise naturally from the proofs: the mathematics leads us to this structure even if we did not start off with it. On that topic, Banonas are also Boolean algebra objects in the category Res of nominal restriction sets considered recently in [26,27]. There seems to be convergence in the recent literature, on name-restriction as an interesting object of study.
One application of Stone duality relates coalgebras for ‘sufficently well-behaved’ functors on sets, with algebras for ‘sufficently well-behaved’ functors on Boolean algebras (definitions in [21]). This allows a uniform construction of logic(s) for coalgebras. So this paper lays the groundwork for a duality-based approach to nominal coalgebraic logic with built-in name generation. Coalgebras on nominal sets do provide a natural semantics for name-passing calculi such as -calculus (see e.g. [9, Section 1.2] and [30] for information and references). See Example 3.6 and the Conclusions for more discussion of applications.
The results in this paper describe a natural mathematical building-block of inherent mathematical elegance, which seems to arise spontaneously by considering algebra and topology in a ‘nominal’ setting, and with potential practical interest. We discuss further work in the Conclusions.
2 Basic definitions for nominal sets
A nominal set is a ‘set with names’. The notion of a name being ‘in’ an element is given by support supp() (Definition 2.7). For more details of nominal sets, see [18,14]. The reader can reasonably think of supp() as ‘the free atoms of ’, but without committing to being syntax—on the contrary, could have any structure provided it admits a permutation action, and this includes taking powersets as we see later in Section 5.
Fix a countably infinite set of atoms . We use a permutative convention that range over distinct atoms.
A (finite) permutation is a bijection on atoms such that nontriv(() is finite.
Write id for the identity permutation such that id( for all . Write for composition, so that ()((()). Write for inverse, so that . Write () for the swapping (terminology from [18]) mapping to , to , and all other to themselves, and take (
If define fix((.
A set with a permutation action X is a pair (X) of an underlying set X and a permutation action written which is a group action on X, so that id and () for all X and permutations and .
Say that supports X when fix() . If a finite supporting exists, call finitely-supported.
Call a set with a permutation action X a nominal set when every X has finite support. X, Y, Z will range over nominal sets.
Call a function XY equivariant when ( () for all permutations and X. In this case write : X Y.
Suppose X is a nominal set and X. Define the support of by supp( supports Write # as shorthand for supp() and read this as is fresh for .
Write for the partial function which is restricted to .
1. If ( for all supp() then .
2. If then .
3. # if and only if # ().
supp(() supp() (cf. Definition 5.1).
3 Nominal Boolean algebra with
Banonas arise naturally as nominal powersets (Section 5), just as Boolean algebras arise naturally as ‘ordinary’ powersets. For an example consider any (for simplicity) unary predicate on some syntax, represented as the set of terms of which it is true. Then asserting that holds ‘if is fresh’ (as in ‘if is fresh then for all , [) is an instance of .
(Commute), (Assoc), and (Huntington) axiomatise Boolean algebra (see, e.g., [25]). We write for , for (), and for . With these definitions, the axioms ensure standard properties of Boolean algebra including: absorption, distributivity, and poset properties.
is a name-restriction operation in the sense of [26, Definition 1] since it satisfies (Swap), (Garbage), and (Alpha). So each Banona has an underlying nominal restriction set. (Distrib), (SelfDual) imply that and are morphisms in the category Res [27], thus Banonas are Boolean algebra objects in Res.
All these axioms are valid properties of the -quantifier [18] (Definition 4.3, in this paper). See Theorem 5.9 for a proof.1
If then . In words: is monotone.
By we mean . So (. We use (Distrib).
#. As a corollary, .
Choose a fresh (so #). By (Alpha) (). By equivariance ()). By Proposition 2.11 #(). The result follows. The corollary follows using (Garbage).
Call a function B a (Banona) morphism when:
Write BAnona for the category of Banonas and Banona morphisms.
– Call a set cofinite when is finite. The set of finite or cofinite sets of atoms is a Banona where conjunction and negation are interpreted as intersection and complement respectively, and if is finite, and if is cofinite (cf. Example 5.3). In Section 5 we exhibit a class of Banonas given by nominal powersets; The results in Section 6 prove this class complete for all possible examples in a certain formal sense.
– The discrete nominal restriction set True False from [27, Section 3.2] is also a Banona.
– The term model for nominal logic constructed by Cheney and Urban in [8] is a Banona where we interpret conjunction as conjunction, negation as negation, and as ‘for fresh , ’ as specified in Figure 9 of [8].
– Predicates of Cardelli and Gordon’s ambient calculus up to logical equivalence form a (very richly-structured) Banona where is interpreted as as defined in Definition 4.3 of [6] (see [6, Corollary 4.5]).
– Formulas of hybrid logic with downarrow (see, e.g, [2]) up to logical equivalence, where atoms serve as world variables, permutation is syntactic permutation and freshness is ‘not free in’, are a Banona where maps to . A broader class of Banonas (with additional operators) can be constructed by adapting an abstract equational class of algebras including sets denotations for hybrid logic defined in [22] to nominal setting.
4 Equivariance and the -quantifier
Our reasoning can be formalised in Zermelo-Fraenkel set theory with atoms (ZFA). Nominal sets can be implemented in ZFA sets such that nominal sets map to equivariant elements (elements with empty support) and the permutation action maps to ‘real’ permutation of atoms in the model [14, Subsection 9.3]. From this, follow short and elegant proofs of theorems about equivariance and support. For more details, see [14, Section 4].
If denotes a list , write for .
Suppose () is a ZFA predicate on variables included in . Suppose () is a ZFA function specified using a list of variables included in . Then we have the following principles:
1. Equivariance of predicates. () ().2
2. Equivariance of functions. (().
3. Conservation of support. If denotes elements with finite support then supp(()) supp()supp().
Suppose () is a predicate on variables included in .3 Suppose denotes elements with finite support. Then the following are equivalent:
This is the some/any property: to prove a -quantified property we test it for one fresh atom; we may then use it for any fresh atom.
5 The nominal powerset as an algebra
Define the nominal powerset pow(X) by:
– X has the pointwise action .
– pow(X) is the set of finitely-supported X.
pow() is the set of finite and cofinite subsets of atoms and n is characterised on pow() by:
– If is finite then n.
– If is cofinite then n.
In the case of pow(X) for general X, the elements added/removed by n are called crucial elements in [13, Subsection 4.2] and correspond to adding/removing elements from -orbits [13, Subsection 4.1]. In fact n is equal to the operation described in [13, Subsection 4.2], used there for different purposes.
If pow(X) then npow(X).
By Theorem 4.2 supp(n) supp() .
1. If # then n.
2.
3.
As a corollary, if then n n .
Suppose #. Choose X and fresh (so #). By the pointwise action and Corollary 2.10 () if and only if .
Choose X and fresh (so #). Then () if and only if () and () .
Choose X and fresh (so #X). Then ()X if and only if ().
# implies n n(). As a corollary, #n.
Choose fresh (so #) and X. By the pointwise action ()() if and only if ()(). By Corollary 2.10 ()() (). The result follows.
nn nn.
By routine calculations using the fact that ()())().
(pow(X)X- n) is an object of BAnona.
If # then if and only if n.
Choose fresh (so #). By definition n when (). By Corollary 2.10 (). The result follows.
6 A representation theorem
We introduce n-filters of a Banona B (Definition 6.1). We define the canonical extension B as the nominal powerset of its maximal n-filters (Definition 6.20). Finally we prove B isomorphic to a subalgebra of B (Theorem 6.25).
6.1 n-Filters
Suppose and . Then:
If B and then supp() supp() and is an n-filter.
Call an n-filter B maximal when for all n-filters B if then .
We now show that every n-filter is contained in a maximal n-filter (Theorem 6.17). We use Zorn’s lemma, but this requires a bound on support. Thus we consider n-filters maximal amongst n-filters with smaller support. Surprisingly, these n-filters are the maximal n-filters (Lemma 6.13).
Suppose is an n-filter and suppose . Write for the set . Then is an n-filter.
That and () () is routine. () follows from the fact that if is fresh (so #) then by (Garbage), (SelfDual), and (Distrib), () ) .
is maximal if and only if .
If is an n-filter and supp() then so is .
Follows from Lemma 6.4.
Suppose is an n-filter such that for all n-filters , and supp() supp() imply . Then ().
is a maximal n-filter if and only if for all n-filters , and supp() supp() imply .
The left-to-right implication is trivial. Now suppose is maximal amongst n-filters with smaller support. By Proposition 6.10 it suffices to show that if and only if .
and is impossible by conditions 1 and 2 of Definition 6.1.
Now suppose and also . Write supp() and . By definition, (SelfDual), and Lemma 6.12 and .
By Lemma 6.9, is an n-filter. Also, whereas , so . By Theorem 4.2 supp() supp(). This contradicts the existence of .
Given a nominal set X, call X bounded-supported when supp() is finite.
Consider a nominal set X and a partial order on X ( need not be equivariant, but when we use this in Theorem 6.17, it will be). If every chain pow(X) has an upper bound () with supp(()) supp() then for every X the set X supp() supp() has a maximal element.
By Remark 6.15 every chain in is finitely-supported and supp() supp(). Then has an upper bound () such that supp(()) supp(). Thus () . The result follows using Zorn’s lemma for .
For every n-filter , there is a maximal n-filter with .
If is a finitely-supported chain in the nominal set of n-filters on B ordered by subset inclusion, then an upper bound for is defined by , and by Theorem 4.2 supp() supp(). By Lemma 6.16 the set of n-filters such that and supp() supp() has a maximal element with respect to inclusion.
Then is a maximal amongst n-filters with smaller support and . Indeed, if is such that and supp() supp() then , hence . By Lemma 6.13 is a maximal n-filter (Definition 6.8).
6.2 The canonical extension -•
points(B) is a nominal set.
By Theorem 4.2 the predicate ‘ is a maximal n-filter’ holds if and only if the predicate ‘ is a maximal n-filter’ holds.
Define the canonical extension Bpow(points(B))):
and will range over elements of B. (n defined in Definition 5.2.)
B is a nominal Boolean algebra with .
From Theorem 5.9.
We need to check that - does map to B. It suffices to show that supp() supp(). This follows by Theorem 4.2.
- is an arrow in BAnona (Definition 3.5).
Equivariance is by Theorem 4.2.
1. () points(B). By assumption in Definition 6.1 if and only if and and it follows that () .
2. () points(B). We use Proposition 6.10.
3. () points(B). Suppose (). Choose fresh (so #). By (Alpha) (). By definition () . By Lemma 6.12 (). By definition (). By Proposition 5.10 n(). By Lemma 5.7 n() n.
Note the ‘internal’ and ‘external’ names in part 3 of the proof of Proposition 6.23. We begin with ‘internally restricted’ with . We use (Alpha) to apply an ‘external’ renaming of to ‘externally’ fresh . This is picked up by the definition of n-filter and Proposition 5.10 moves to the ‘external’ .
In part 3 # implies #—but this does not matter; we choose fresh.
- is injective, thus B is isomorphic to a subalgebra of B.
7 Nominal Stone duality
We introduce nominal topological spaces. As expected, the carrier set and topology are nominal sets and open sets are finitely-supported (this can restrict— sometimes considerably; see Example 5.3—the available open sets). Thus we cannot take arbitrary unions of open sets, but only finitely-supported unions. Banonas correspond to nominal topological spaces with additional properties which we call nominal Stone spaces with (Definition 7.4). To the new-binder corresponds on the topological side the semantic n (Definition 5.2); elements correspond to clopen sets (sets that are both open and closed), so clopens must be closed under n. The notion of compactness must also be subtly tweaked to take into account the role of n. We conclude with a duality theorem.
A nominal topological space T is a pair (
– and T
– implies .
– pow() implies ; we call this a finitely-supported union.
Call equivariant continuous when implies . Write nTop for the category of nominal topological spaces and continuous maps.
Call n-closed when ( n). Call pow() a cover when T. If is a cover and is n-closed then call an n-cover. Call T n-compact when every n-cover has a finite subcover.
If pow() is finite then #. As a corollary, T is n-compact when every n-cover has an n-closed finite subcover.
Call closed when T, and clopen when is open and closed. Call T totally separated when for every T there is a clopen with and .
Say T is a nominal topological space with when n for every clopen .5 Write nTop for the full subcategory of nTop on T with .
A nominal Stone space with is a totally separated n-compact nominal topological space with . Write nStone for the full subcategory of nTop on nominal Stone spaces with .
(B) is indeed a nominal topological space, for if pow() then is open. The next lemma shows that () is well-defined.
For : B in BAnona and points(), -1() points(B).
If is n-closed then so is .
Choose fresh (so #). If then . By Lemma 5.6 n() n and by assumption n.
(B) is totally separated and n-compact.
Consider distinct (B). Without loss of generality take . By Definition 6.20, and . So is an open set separating and . By Proposition 6.10 points(B) ), so is also closed.
Consider an n-cover pow(). It suffices to find a finite subcover of , since for every there exists .
Write where denotes closure under finite intersections. So has a finite subcover if and only if . By Proposition 6.23 and Lemma 7.7 satisfies conditions 2 and 3 of Definition 6.1. If satisfied also then would be an n-filter; by Theorem 6.17 for some point ; it would follow that , a contradiction. Therefore .
If (B) is clopen then for some B.
is a functor from BAnona to nStone.
Map T nStone to a (T) BAnona defined by:
– (T) is clopen.
– , , and are interpreted as intersection, complement, and n.
Given : T in nStone define () : () (T) by ()(
is a functor from nStone to BAnona.
If is clopen then n is open by Definition 7.4. n is closed from the fact that n(TT n, immediate from part 3 of Lemma 5.6. It is routine to check that (T) is an object of BAnona.
Consider continuous : T . If is clopen then so is -1(). () is equivariant because is, and preserves intersections and complements. Given a clopen, ()(n n()() follows from Definitions 5.2 and 7.11 and the equivariance of . Thus () is a morphism in BAnona.
Suppose T nTop is n-compact and is a finitely-supported set of closed sets with the finite intersection property: the intersection of finitely many sets in is nonempty. Then n implies .
defines an equivalence between BAnona and nStone.
We use [23, Theorem 1, Chapter IV, Section 4].
G is essentially surjective on objects. Given B in BAnona and B, is clopen. By Lemma 7.9 if is clopen then for some B. By Theorem 6.25, the map - defines an isomorphism between (B) and B.
G is faithful. From the fact that nominal Stone spaces are totally separated.
G is full. Given T in nStone and : () (T) in BAnona we construct a morphism : T in nStone, such that (.
Define T (T) by (T) .
is well defined: () is supported by supp(), and is indeed a maximal n-filter. We must also show that # and () imply n(); this follows from Proposition 5.10.
That is injective follows, as in for the classical Stone duality, from the totally separatedness of the spaces. For surjectivity, consider a maximal n-filter (T). This is a finitely-supported set of closed sets of T with the finite intersection property such that and # imply n. By Lemma 7.13 there exists some T. That () follows from maximality of . and are continuous. The proof is analoguous to the classical case, see [4].
We set () . This is continuous and (.
8 Conclusions
We have seen how Boolean algebras in nominal sets naturally support an operation corresponding to the -quantifier from [18]. So nominal sets are sufficiently different that this paper is not a pure ‘replay’ of the standard proofs—on the contrary, the fine detail is extremely subtle.
In particular, as an empirical observation the proofs seem to ‘want’ . They break for nominal Boolean algebras without (remove and its axioms from Definition 3.1, presumably to obtain a Bano). Without we would need to use finitely-supported filters, rather than n-filters. But then the proofs of Lemma 6.13 and Theorem 6.17 would break. Banonas seem to be natural; a representation theorem for Banos is future work.
That our results are consistent with the full structure of classical logic (if we want it) is interesting, but note that our proofs do not depend on it. We believe that they should adapt to subreducts (e.g., Heyting algebras, distributive lattices) and expansions with operations/operators. A concrete example of a Hanona (Heyting algebras with ; weaken the initial three axioms appropriately and add ()() in Figure 1) is a intuitionistic hybrid logic with (cf. Example 3.6 and [28]). We believe that, modulo an easy syntactic translation, the logic by Tiu [31] is another.
On related work, Sections 5.3 and 5.4 of [34] outline the Jónsson-Tarski representation of Boolean algebras with operators, i.e., normal modalities. Does it suffice to consider and permutations as families of modalities? Yes, but this paper gives a strictly stronger result. Nominal sets have an ‘external’ theory of names and freshness given by permutations and support (extending the ‘external’ set intersection and complement corresponding to ‘internal’ conjunction and negation of Boolean algebra). An ‘internal’ notion of freshness is ; a similar idea is used in cylindric/polyadic algebras and Lambda Abstraction Algebras [24]. Our challenge has been to make ‘internal’ and ‘external’ theories coincide for boolean connectives, and to represent as n (Definition 5.2), permutation as permutation, and to satisfy e.g. # implies .
Some speculation on computational applications: fresh names create symmetry, since ‘it does not matter’ which are chosen. It is known by those working in satisfiability checkers (e.g. SMT solvers) that symmetry is important in reducing search space. Domain-specific symmetries are a major theme. Banonas and nominal sets give an explanatory foundation for freshly generated resources—a fairly common case. We might use this to extend problem input languages with explicit statements of these symmetries, thus improving and automating their recognition. Then this paper guarantees that a satisfiability checker based on nominal sets and n would be adequate for any classical logic with a .
On pow(), n is the unique function satisfying the axioms of Definition 3.1. We do not know whether n is uniquely determined by those axioms on arbitrary nominal powersets. (The map if # then else fails (SelfDual).)
Nominal powersets (Definition 5.1) have rich structure. In particular, function-symbols could be added to reflect freshness # and name-restriction fix(supp()) [16]. We do not believe that these can be represented using n. Note that n does not equal . For instance is true, but n is false in general.6 So there are two natural name-restrictions on nominal sets. Nominal sets have been around for a decade, but their structure is not fully understood. For future work we hope to characterise the structure of nominal powersets, as complete atomic Boolean algebras do for ‘ordinary’ powersets.
References
1. Samson Abramsky, Dan R. Ghica, Andrzej S. Murawski, C.-H. Luke Ong, and Ian D. B. Stark. Nominal games and full abstraction for the nu-calculus. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 150–159. IEEE Computer Society Press, 2004.
2. Carlos Areces and Balder ten Cate. Hybrid logics. In P. Blackburn, J. van Benthem, and F. Wolter, editors, Handbook of Modal Logic. Elsevier, 2007.
3. Jesper Bengtson and Joachim Parrow. Formalising the -calculus using nominal logic. In FOSSACS’07: Proceedings of the 10th international conference on Foundations of software science and computational structures, pages 63–77. Springer, 2007.
4. S. Burris and H. Sankappanavar. A Course in Universal Algebra. Graduate texts in mathematics. Springer, 1981.
5. Luís Caires and Luca Cardelli. A spatial logic for concurrency (part I). Information and Computation, 186(2):194–235, 2003.
6. Luca Cardelli and Andrew Gordon. Logical properites of name restriction. In Typed Lambda Calculi and Applications, volume 2044 of Lecture Notes in Computer Science, pages 46–60. Springer, 2001.
7. James Cheney. A simpler proof theory for nominal logic. In FoSSaCS, volume 3441 of Lecture Notes in Computer Science, pages 379–394. Springer, 2005.
8. James Cheney and Christian Urban. Nominal logic programming. ACM Transactions on Programming Languages and Systems (TOPLAS), 30(5):1–47, 2008.
9. C. Cirstea, A. Kurz, D. Pattinson, L. Schröder, and Y. Venema. Modal logics are coalgebraic. The Computer Journal, 2009.
10. Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic. In Principles and Practice of Declarative Programming, 12th International ACM SIGPLAN Symposium (PPDP 2010), 2010.
11. Murdoch J. Gabbay. Fresh Logic. Journal of Applied Logic, 5(2):356–387, June 2007.
12. Murdoch J. Gabbay. Nominal Algebra and the HSP Theorem. Journal of Logic and Computation, 19(2):341–367, April 2009.
13. Murdoch J. Gabbay. A study of substitution, using nominal techniques and Fraenkel-Mostowski sets. Theoretical Computer Science, 410(12-13):1159–1189, March 2009.
14. Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 2011. In press.
15. Murdoch J. Gabbay and James Cheney. A Sequent Calculus for Nominal Logic. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 139–148. IEEE Computer Society, July 2004.
16. Murdoch J. Gabbay and Vincenzo Ciancia. Freshness and name-restriction in sets of traces with names. In Foundations of software science and computation structures, 14th International Conference, 2011.
17. Murdoch J. Gabbay and Aad Mathijssen. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, December 2009.
18. Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, July 2001.
19. Edward Keenan and Dag Westerståhl. Generalized quantifiers in linguistics and logic. In J. Van Benthem and A. Ter Meulen, editors, Handbook of Logic and Language, pages 837–894. Elsevier, 1996.
20. Alexander Kurz and Daniela Petrişan. On universal algebra over nominal sets. Mathematical Structures in Computer Science, 20:285–318, 2010.
21. Alexander Kurz and Jirí Rosický. The Goldblatt-Thomason theorem for coalgebras. In Till Mossakowski, Ugo Montanari, and Magne Haveraaen, editors, CALCO, volume 4624 of Lecture Notes in Computer Science, pages 342–355. Springer, 2007.
22. Tadeusz Litak. Algebraization of hybrid logic with binders. In Renate Schmidt, editor, Relations and Kleene Algebra in Computer Science, volume 4136 of Lecture Notes in Computer Science, pages 281–295. Springer Berlin / Heidelberg, 2006.
23. Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer, 1971.
24. Giulio Manzonetto and Antonino Salibra. Applying universal algebra to lambda calculus. Journal of Logic and computation, 20(4):877–915, August 2010.
25. William McCune. Solution of the Robbins problem. Journal of Automated Reasoning, 19:263–276, 1997. 10.1023/A:1005843212881.
26. Andrew M. Pitts. Nominal system T. In Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2010), pages 159–170. ACM Press, January 2010.
27. Andrew M. Pitts. Structural recursion with locally scoped names. submitted for publication, September 2010.
28. Jason Reed. Hybridizing a logical framework. Electronic Notes in Theoretical Computer Science, 174(6):135 – 148, 2007. Proceedings of the International Workshop on Hybrid Logic (HyLo 2006).
29. Mark R. Shinwell, Andrew M. Pitts, and Murdoch J. Gabbay. FreshML: Programming with Binders Made Simple. In Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), volume 38, pages 263–274. ACM Press, August 2003.
30. Sam Staton. Name-passing process calculi: operational models and structural operational semantics. Technical Report UCAM-CL-TR-688, University of Cambridge, Computer Laboratory, June 2007.
31. Alwen Tiu. A logic for reasoning about generic judgments. Electronic Notes in Theoretical Computer Science, 174(5):3–18, 2007.
32. David C Turner. Nominal Domain Theory for Concurrency. PhD thesis, University of Cambridge, 2009.
33. Nikos Tzevelekos. Full abstraction for nominal general references. In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), pages 399–410. IEEE Computer Society Press, 2007.
34. Yde Venema. Algebras and coalgebras. In P. Blackburn, J. Van Benthem, and P. Wolter, editors, Handbook of modal logic, volume 3 of Studies in logic and practical reasoning, chapter 6. Elsevier, 2007.
35. Dag Westerståhl. Quantifiers in formal and natural languages. In Gabbay and Günthner, editors, Handbook of Philosophical Logic, volume 4 of Synthèse, chapter 2, pages 1–131. Reidel, 1989.
Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.
Notes
1 The axioms are nominal algebraic because of their freshness side-conditions. In a sense which has been made formal, nominal algebra is an equational logic [17,12,20], and is sound and complete for nominal sets. ↩
must contain all the variables mentioned in the predicate. It is not the case that if and only if —but it is the case that if and only if . ↩
has to be expressible in the language of ZFA set theory without choice. Every used in this paper will satisfy this property. ↩
4 In fact it can be proved by a further calculation that supp( supp(). ↩
5 We need not require n to be open for all ; of course, we do not forbid it either. ↩
6 The of [26], which Pitts calls name-restriction, is purely axiomatic and does not commit to any concrete representation. ↩