Nominal semantics for predicate logic: algebras, substitution, quantifiers, and limits
Abstract. We define a model of predicate logic in which every term and predicate, open or closed, has an absolute denotation independently of a valuation of the variables. For each variable , the domain of the model contains an element which is the denotation of the term (which is also a variable symbol). Similarly, the algebra interpreting predicates in the model directly interprets open predicates. Because of this models must also incorporate notions of substitution and quantification.
These notions are axiomatic, and need not be applied only to sets of syntax. We prove soundness and show how every ‘ordinary’ model (i.e. model based on sets and valuations) can be translated to one of our nominal models, and thus also prove completeness.
Keywords: Lattices and algebra; First-order logic; Nominal semantics
1 Introduction
What is a notion of algebraic truth suitable for interpreting predicate logic?
For propositional logic an answer is clear: Heyting algebra for the intuitionistic case, and Boolean algebra for the classical case.1 This is not sufficient for interpreting predicate logic because predicates can contain variable symbols.
The standard method, due to Tarski [25], uses valuations. We assume a domain and a valuation mapping variables to , and then terms and predicates are given denotation in the context of the valuation: and . Intuitively, valuations convert predicates to propositions, which reduces the problem of truth to the infinite propositional case.
Thus with the usual notion of model, names denote semantic objects, but semantic objects have no inherent notion of names.
We propose an alternative. Allow semantic objects to be aware of names. Then, we can map a variable to a representation of itself in the denotation. Thus, open terms and open predicates map to open elements of a domain and algebra of truth-values, like so: and . Connectives, including quantifiers, just become operations on the domain. So, the denotation of is and the denotation of is some operation applied to .
What it means for an element to be open is given for us by the recently-developed theory of nominal semantics, which was designed to provide semantics for variable symbols in inductive syntax-with-binding [20,12]. In this paper we apply nominal ideas to semantic objects which, unlike the syntax of terms and predicates, need not be inductively defined. We use nominal algebra to axiomatise substitution following [17,18] and a simple theory of #fresh limits in partial orders, which is introduced in this paper. Using #fresh limits we show how , , and the quantifier are all just greatest #lower fresh bounds for suitable finite sets. Specifically:
– is the greatest lower bound for the empty set .
– is the greatest lower bound for the set , i.e. .
– is the greatest #lower bound for the set , i.e. .
We use this to construct a nominal algebraic semantics for first-order logic and prove it sound and complete. The completeness proof is a little unorthodox: instead of a direct proof (which is not hard) we give a more general lifting construction from Tarski-style valuation models, to our nominal models. This gives a direct translation of the familiar semantics into our new one and we obtain completeness as a corollary.
Map of the paper Section 2 presents the technical background: nominal sets and first-order logic. Section 3 introduces nominal posets and substitution algebras. This material is partly new (nominal posets and ) and partly a restatement of [17,18] (substitution algebras; though to be fair, the presentation here is significantly simplified and updated). Section 4 introduces nominal Boolean algebras, which is a mathematically precise answer to the question with which we opened this Introduction, and proves soundness. Finally, Section 5 presents the ‘lifting’ operation on models and proves completeness.
2 Technical background
2.1 Background on nominal sets
Nominal sets were introduced in [20] (where they were called equivariant Fraenkel-Mostowski sets). The presentation below is quite self-contained; see [20] or [12] for more details.
We want names to ‘exist’ in the denotation. We do this by endowing sets with a symmetry group action over name permutations (Definition 2.3). We extract from this the key idea of support (Definition 2.4), which captures the degree of asymmetry of an element under the group action. We use this to define a nominal set X (Definition 2.6) as a set with a group action all of whose elements are at most finitely asymmetric (have finite support), where # and supp() mean the same thing: “ is symmetric over/does not depend on the name ”. We do not a priori assume e.g. a substitution action on names; in our framework this is algebraically definable just from the more primitive notion of permutable names and finite asymmetry (see e.g. Figure 2).
Fix a countably infinite set of atoms . We use a permutative convention that range over distinct atoms.
A (finite) permutation is a bijection on the set 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 id . Write () for the swapping (terminology from [20]) mapping to , to , and all other to themselves, and take ( id.
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 for every , if ( for every then . If some finite supporting exists, then call finitely-supported. Then define the support of by
Write # as shorthand for supp() and read this as is fresh for .
Suppose X is a set with a permutation action and X. Then if has finite support then supp() supports and is the unique least finite supporting set of .
Suppose X is a set with a permutation action. 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.
– is a nominal set where (). It is easy to check that
– The sets of terms and predicates from Definition 2.12 below, are nominal sets if we let permutation act in the natural way on the atoms (considered as variable symbols) inside them. It is easy to check that supp() or supp() is equal to the atoms occurring in or if we do not take terms up to -equivalence, and supp() or supp() is equal to the atoms occurring free in or if we do take or up to -equivalence. A detailed study of this is in [12, Section 5]; see also [4].
Later on in this paper we shall see more examples. Notably, the sets from Definition 5.9 are nominal sets, and the set of valuations from Definition 5.3 is a set with a permutation action but not a nominal set (see Remark 5.8 and associated footnote). For more examples see [12].
Call a function XY equivariant when ( () for all permutations and X. In this case write : X Y.
supp(() supp().
It is not hard to check that supports if and only if () supports . We use Theorem 2.5.
1. If ( for all supp() then .
2. If (() for every supp() then .
3. # if and only if # ().
2.2 First-order logic
First-order logic is of course standard. The reader can find any number of presentations in the literature, for instance [27].
Here and for the rest of this paper fix a signature
of term-formers and predicate-formers and an arity function arity mapping TermFormers PredicateFormers to 0 1 2. We let f range over distinct term-formers and P range over distinct predicate-formers.
We take predicates up to -equivalence as usual (so for instance P(P() where arity(P
We write [] and [] for the usual capture-avoiding substitution on terms and predicates. For instance, f()[ f() and (P())[ P().
Let and range over finite sets of predicates. A sequent is a pair . We define the derivable sequents as usual for classical first-order logic by the rules in Figure 1.
3 Partial orders and substitution
We obtain our nominal semantics for first-order logic by combining two things: a partial order, and a substitution action. We need the partial order to interpret entailment. We need the substitution action to interpret variables and substitutions. These are Subsections 3.1 and 3.2.
Of course, these two things interact via quantifiers. Thus we introduce the novel notion of , an #greatest lower bound for a set (Notation 3.3). It turns out that this generalises , , and into a single definition.
3.1 Nominal posets (nominal partially ordered set)
We can now begin to ask what happens if we combine the notion of partially ordered set with the notion of nominal set. In particular, we can think about greatest lower and least upper bounds in the presence of nominal freshness. This leads us to the idea of and ; greatest lower and least upper bounds amongst elements that do not include in their support.
A nominal poset is a tuple ) such that () is a nominal set and is an equivariant partial order.2
Call finitely fresh-complete when for every finite subset and every finite set of atoms the set of -fresh lower bounds
has a -greatest element .
Similarly call finitely fresh-cocomplete when for every finite and as above the set of -fresh upper bounds supp( has a -least element .
and are unique if they exist.
From the fact that for a partial order, and imply .
Suppose ) is a finitely fresh-complete and -cocomplete nominal poset. Suppose and are finite. Then:
– Call an #greatest lower bound (‘-fresh greatest lower bound’) of . If then we may just call this a greatest lower bound. If we may just call this an #greatest lower bound and write it .
– Call an #least upper bound of . If then we may just call this a least upper bound. If we may just call this an #least upper bound and write it .
Suppose ) is a nominal poset.
– Write for the greatest lower bound and for the least upper bound of the empty set , where these exist.
– Write for the greatest lower bound and for the least upper bound of , where these exist.
– Write for the #greatest lower bound and for the #least upper bound of , where these exist.
Suppose is a partial order (it does not matter whether it is nominal). Call a complement of when and . If every has a complement say that has complements, and write the complement of as .
Complements are unique if they exist.
Suppose ) is a nominal poset.
1. Suppose is finite and , and exists.
2. Suppose , and suppose exists. Then supp( supp().
3.2 Substitution algebra
The reader may be used to seeing substitution as a concrete operation on sets. However, using nominal sets we can powerfully (and axiomatically) generalise substitution to be an abstract (nominal) algebraic structure.
A termlike substitution algebra over is a tuple U (U atm sub) where:
– (U) is a nominal set.
– atm : U is an equivariant injection, usually written invisibly (so we write atm() just as ).
– sub : UUU is an equivariant substitution action, written infix [].
such that the equalities (Suba) to (Sub) of Figure 2 hold, where , , and range over elements of U.
Suppose U U sub atm) is a termlike substitution algebra. A substitution algebra over U is a tuple B B sub) where:
– (B) is a nonempty nominal set.
– sub : BU B is an equivariant substitution function satisfying the axioms (Subid) to (Sub) of Figure 2, where ranges over elements of B and and range over elements of U.
1. The set of atoms is a termlike substitution algebra where atm( and [ and [.
2. Terms from Definition 2.12 are a termlike substitution algebra with atm( and [] equal to [].
3. Predicates from Definition 2.12 are not a termlike substitution algebra, because there are no predicate variables or substitution for predicates. Predicates are however a substitution algebra over terms.
In Corollary 5.13 we will prove that from Definition 5.11 is a termlike substitution algebra, and from Definition 5.11 is a substitution algebra. For different and non-trivial classes of substitution algebras see [11,13].
4 The model
4.1 Nominal Boolean algebra
Definition 4.1 is the culminating definition of this paper; we define a notion of Boolean algebraic structure suitable for giving an ‘absolute’ interpretation of first-order logic. This means that variables, substitution, and quantification must be part of the model just as much as conjunction and negation are part of ordinary Boolean algebras. With our definitions so far, this is now not difficult.
Definition 4.1 is not quite enough to interpret first-order logic on its own. For that, we need the notion of model which we develop next in Subsection 4.2.
Suppose U is a termlike substitution algebra. A nominal Boolean algebra over U is a tuple B B sub) such that:
– (B) is a finitely fresh-complete nominal poset with complements.
– (B sub) is a substitution algebra over U.
– The partial order is compatible with the substitution action:
A more accurate name for ‘nominal Boolean algebra’ might be ‘nominal partial order’. But that is a bit of a mouthful.4 It is quite easy to derive some basic properties of nominal Boolean algebras, which are useful for Theorem 4.13.
If # then ()[([]).
This is just (Compat ) where . Recall that by our permutative convention .
if and only if .
Both hold if and only if is a greatest lower bound for .
1. ()[[] ([]).
2.
From (Compat ) and (Compat) respectively.
If then [] []. As a further corollary, if and # then [] for every U.
Suppose B and U and . Then [].
Suppose B and . Then and # imply .
This is the #greatest lower bound property of with respect to .
is the greatest lower bound of [] U in B.
4.2 Soundness
For the rest of this section fix a model U B -).
Define an interpretation function - mapping terms and predicates (Definition 2.12) to elements of U and B respectively, as follows:
Write when and call valid in .
[][] and [][].
If then .
– Soundness of (L) and (R) follows from being a greatest -lower bound of and .
– Soundness of (L) and (R) follows from the fact of complements that if and only if .
– Soundness of (L) follows from being the complement of the greatest lower bound of .
– Soundness of (L) follows using Lemma 4.6 and Proposition 4.12, and soundness of (R) follows from Lemma 4.7.
5 Lifting ordinary models to nominal models
We have to recall the (standard) definition of model for first-oder logic. This is Subsection 5.1. Then in Subsection 5.2 we show how to lift this to a nominal model and obtain completeness as an immediate corollary (Theorem 5.18 and Corollary 5.19).
5.1 Ordinary model of first-order logic
We briefly sketch the ordinary model of first-order classical logic, with valuations and without atoms. This model is not intended to be sophisticated; we will just need that one exists.
To avoid the confusion between sets and nominal sets, we may write ordinary set for the former.
An ordinary model -) is a tuple such that:
– is some non-empty (ordinary) underlying set.
– - assigns to each term-former f a function f : and to each predicate-former P a function P : .
Write for the set of functions from atoms to . Let range over elements of and call these valuations (to ).
Also if then write [] for the function such that ([])( and ([])(().
is a complete Boolean algebra. We use standard definitions, such as , , , and without further comment
Define an interpretation function - mapping terms and predicates (Definition 2.12) to elements of and (considered as a Boolean algebra) respectively, as follows:
Theorem 5.6 expresses the usual soundness and completeness result for first-order logic; for details and proofs see e.g. [27, Subsection 1.5]:
is derivable if and only if for every ordinary model and every valuation to it is the case that implies .
5.2 Constructing a nominal model from an ordinary model
We now show how to ‘lift’ a model over ordinary sets to a nominal model (Proposition 5.16). We then deduce completeness for nominal Boolean algebras (Corollary 5.19).
Give valuations a permutation action by
forms a set with a permutation action (Definition 2.3). This is not in general a nominal set because it has elements without finite support5 for our purposes that will not be a problem.
In fact, the action from Definition 5.7 is a special case of the standard conjugation action ()((()) where we use the trivial action for every . This is standard; for a specifically ‘nominal’ discussion see [14, Definition 2.4.2].
Given an ordinary set write ) for
– is the set of functions from to such that there exists a finite set such that if (() for every then ((), and
– the permutation action is defined by
We will be most interested in and .
It is routine to verify that the permutation action is indeed a group action. It remains to check finite support.
Suppose ( for every (notation from Definition 5.9). By Definition 5.9 ()((). By Definition 5.7 ()((()). Now by assumption ((()) for every . Therefore, ()(() for every , and so ((), and so ()((). Thus, has finite support (and is supported by ).
Suppose is an ordinary set and . Then if (() for every supp() then (().
Suppose (() for every supp(). It suffices to show that if supp() and then ([().
Choose fresh : (so ). By part 1 of Corollary 2.10 (), since supp(). We reason as follows:
from Definition 5.11 is indeed a termlike substitution algebra, and is indeed a substitution algebra over .
Suppose . Write when () ().
() is a finitely fresh-complete lattice with complements.
It is easy to check that defined by ()((()) is a complement to .
Now suppose and are finite, and suppose supp( and . Define
It is routine to verify that this is an #greatest lower bound for .
( sub) is a nominal Boolean algebra over .
The interpretation of term-formers and predicate-formers is simple:
( -) determines a model in the sense of Def. 4.9.
If , then there exists a termlike substitution algebra U and a nominal Boolean algebra M over U such that .
As a corollary, if is inconsistent (that is, if ) then has a model.
It is also possible give a direct proof of completeness of first-order logic with respect to the models of Definition 4.9, using a model based on syntax quotiented by derivable equality. The advantage of the proof of completeness used here is that it also shows that completeness does not hold just because the only models available are syntax-based. Topological models [13] and set-theoretic models [11] also exist (those papers predate the consideration of lattices and #fresh limits of this paper).
6 Conclusions
The usual Tarski semantics, based on valuations, has names in the syntax but not in the semantics. Names can be used to name semantic objects but these objects do not themselves contain names. We have challenged the prejudice that only syntax contains names, and proposed a framework where names are (also) in denotation.
This is related to a broad debate in philosophy about to what extent names are real. One investigation in that literature deserves special mention: Kit Fine’s notion of arbitrary object [8], which corresponds to our notion of ‘names in denotation’ and in particular to our notion of nominal substitution set, though the technical details of Fine’s constructions are quite different from ours.7
This paper is part of a broader research context. For instance in [13] we built a representation theorem for first-order logic (in retrospect this also provides a class of ‘topological’ models for the axioms in this paper, distinct from the ‘lifted’ models of Section 5). In [11] we show that, remarkably, a large subclass of the cumulative hierarchy model of Fraenkel-Mostowski sets forms a substitution algebra.
In this paper we apply the technology to the theory of lattices, in particular identifying #fresh limits as the single unifying notion of greatest lower bound needed to model both conjunction and universal quantification. This is another step towards a ‘nominal’ view of logic and computation whereby names, and associated structures, are treated as integral to denotation.
Related and future work A nominal style semantics related to the semantics of this paper has been given for the -calculus [19]. Nominal lattices have not been considered to date. The author and collaborators considered a notion of Banona in [16] (Boolean algebra with ) which is tangentially related to this paper. Domain theory in nominal sets is considered in [26] and a notion of FM category is considered in [3,2]. The notion of #fresh limit seems to be new though, as is the specifically lattice-theoretic treatment.
A relative of nominal lattices is cylindric set algebras [22,21], a semantics expressed in terms of relations between elements of the domain of the model, where quantification is interpreted using projection and cylindrification. Instead of designing semantics for first-order logic based on relations, projection, and cylindrification, we have taken the novel approach of giving a direct interpretation to variables in the model. In fact, the ‘ordinary models’ we build in Subsection 5.1 correspond to locally finite dimensional regular cylindric set algebras [22]. There is no non-nominal precedent to the nominal Boolean algebras from Definition 4.1.
There are two natural avenues for future work:
Add binders to the term-language. Part of the challenge of this is to develop a suitable new syntax extending first-order logic with term-formers that can bind. Once we have this, it is easy to interpret binders, because our (nominal) denotation supports atoms-abstraction as primitive.8
In particular, we see this being applied computationally in formalising mathematics, where binders are everywhere, as an improvement over first-order logic (where term-formers cannot bind) or higher-order logic (which may already be unnecessarily powerful).
This would be related to the permissive-nominal logic of [5,6] except that here, we would want to take substitution as primitive. This is related to work by Fiore and his students [10,9] which tries to develop (purely in category theory) a unified account of names, binding, and substitution; a non-exhaustive but accessible introduction to these ideas is in [24]. Slightly further afield, Beeson’s lambda-logic [1] enriches first-order logic with a term-language that is specifically the untyped -calculus; the denotational assumptions used are completely different, but the spirit of allowing binding term-formers in a first-order logic is similar. Of course this also goes back to the first author’s Binding Logic [7].
Generalise to categories. Another obvious next step is to generalise the constructions in this paper from lattices to categories, and so obtain an enriched category theory. By this view, we note that lattices are just a special case of categories, and our #fresh limits are just limits in a subcategory of elements of the lattice for which is fresh. Much can be done here. For instance, we can try to identify the correct common generalisation of this new view of quantifiers and the standard one based on left- and right-adjoints to projection [23, Section 5.5].
Slightly less ambitiously, we can simply consider a general notion of nominal lattice, which enriches ordinary lattices with (a greatest #lower bound for ) but without necessarily assuming a substitution action.9 Clearly, there is a rich theory of nominal preorders which remains to be explored.
References
1. Michael Beeson. Lambda logic. In Second International Joint Conference on Automated Reasoning (IJCAR 2004), volume 3097 of Lecture Notes in Computer Science, pages 460–474. Springer, 2004.
2. Ranald Clouston. Equational logic for names and binding. PhD thesis, University of Cambridge, UK, 2009.
3. Ranald Clouston. Nominal Lawvere theories. In Proceedings of the 18th International Workshop on Logic, Language, and Information (WoLLIC), volume 6642 of Lecture Notes in Computer Science. Springer, 2011.
4. Roy L. Crole. -equivalence equalities. Theoretical Computer Science, 2012. In press.
5. Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010), pages 165–176. ACM Press, 2010.
6. Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Transactions on Computational Logic, 2012. In press.
7. Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Binding logic: Proofs and models. In Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2002), pages 130–144. Springer, 2002.
8. Kit Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.
9. Marcelo Fiore and Chung-Kil Hur. Term equational systems and logics. Electronic Notes in Theoretical Computer Science, 218:171–192, 2008.
10. Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi. Abstract syntax and variable binding. In Proceedings of the 14th IEEE Symposium on Logic in Computer Science (LICS 1999), pages 193–202. IEEE Computer Society Press, 1999.
11. Murdoch J. Gabbay. A study of substitution, using nominal techniques and Fraenkel-Mostowski sets. Theoretical Computer Science, 410(12-13):1159–1189, March 2009.
12. Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.
13. Murdoch J. Gabbay. Stone duality for First-Order Logic: a nominal approach. In Howard Barringer Festschrift. December 2011.
14. Murdoch J. Gabbay. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012.
15. 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 (FOSSACS 2011), volume 6604 of Lecture Notes in Computer Science, pages 365–380. Springer, 2011.
16. Murdoch J. Gabbay, Tadeusz Litak, and Daniela Petrişan. Stone duality for nominal Boolean algebras with NEW. In Proceedings of the 4th international conference on algebra and coalgebra in computer science (CALCO 2011), volume 6859 of Lecture Notes in Computer Science, pages 192–207. Springer, 2011.
17. Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC 2006: Theoretical Aspects of Computing, volume 4281 of Lecture Notes in Computer Science, pages 198–212, November 2006.
18. Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 2008.
19. Murdoch J. Gabbay and Dominic Mulligan. Nominal Henkin Semantics: simply-typed lambda-calculus models in nominal sets. In Proceedings of the 6th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2011), volume 71 of EPTCS, pages 58–75, September 2011.
20. 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.
21. Leon Henkin, J. Donald Monk, and Alfred Tarski. Cylindric Algebras. North Holland, 1971 and 1985. Parts I and II.
22. Donald Monk. An introduction to cylindric set algebras. Logic journal of the IGPL, 8(4):451–492, 2000.
23. Andrew M. Pitts. Categorical logic. In S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, Volume 5. Algebraic and Logical Structures, chapter 2. Oxford University Press, 2000.
24. John Power. Abstract syntax: Substitution and binders: Invited address. Electronic Notes in Theoretical Computer Science, 173:3–16, 2007.
25. Alfred Tarski. The semantic conception of truth and the foundations of semantics. Philosophy and Phenomenological Research, 4, 1944.
26. David C. Turner. Nominal Domain Theory for Concurrency. PhD thesis, University of Cambridge, 2009.
27. Dirk van Dalen. Logic and Structure. Universitext. Springer, 1994. Third, augmented edition.
28. Steve Vickers. Topology via Logic, volume 5 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1989.
Acknowledgements. The second author acknowledges the support of the Leverhulme trust.
Notes
1 Accessible references for Heyting and Boolean algebra are easily found online. For a modern and encyclopaedic treatment, see e.g. [28]. ↩
2 So if and only if . ↩
3 This is just a fancy way of observing that since the definition of is symmetric in atoms, the the result must be at least as symmetric as the inputs. ↩
4 A possibly nice classification is to define a notion of bounded nominal lattice which is equipped with , , , —and also with . Then our nominal Boolean algebra is just a nominal lattice with complements and a compatible substitution action. ↩
5 The finitely-supported are such that there exists a finite such that for all , ((); it is not worth our while to impose this restriction, though it would do no harm to do so. ↩
6 So we abuse notation by overloading with the nominal set, and is: the underlying set of the substitution algebra obtained from the underlying set of the ordinary model . What could be simpler? ↩ ↩
7 Fine did not have permutations or finite support independently of and preceding the notion of substitution. ↩
8 Atoms-abstraction [] is the native (non-functional) notion of abstraction in nominal techniques. It was introduced in [20]. ↩
9 The of [16] is not an instance of this because it commutes with negation, but the (dual of) from [15] is an instance of this. There are two distinct ‘restriction’ operations here. ↩