Foundations of nominal techniques: logic and semantics of variables in abstract syntax
Abstract
We are used to the idea that computers operate on numbers, yet another kind of data is equally important: the syntax of formal languages, with variables, binding, and alpha-equivalence. The original application of nominal techniques, and the one with greatest prominence in this paper, is to reasoning on formal syntax with variables and binding.
Variables can be modelled in many ways: for instance as numbers (since we usually take countably many of them); as links (since they may ‘point’ to a binding site in the term, where they are bound); or as functions (since they often, though not always, represent ‘an unknown’).
None of these models is perfect. In every case for the models above, problems arise when trying to use them as a basis for a fully formal mechanical treatment of formal language. The problems are practical—but their underlying cause may be mathematical.
The issue is not whether formal syntax exists, since clearly it does, so much as what kind of mathematical structure it is. To illustrate this point by a parody, logical derivations can be modelled using a Gödel encoding (i.e. injected into the natural numbers). It would be false to conclude from this that proof-theory is a branch of number theory and can be understood in terms of, say, Peano’s axioms. Similarly, as it turns out, it is false to conclude from the fact that variables can be encoded e.g. as numbers, that the theory of syntax-with-binding can be understood in terms of the theory of syntax-without-binding, plus the theory of numbers (or, taking this to a logical extreme, purely in terms of the theory of numbers). It cannot; something else is going on. What that something else is, has not yet been fully understood.
In nominal techniques, variables are an instance of names, and names are data. We model names using urelemente with properties that, pleasingly enough, turn out to have been investigated by Fraenkel and Mostowski in the first half of the 20th century for a completely different purpose than modelling formal language. What makes this model really interesting is that it gives names distinctive properties which can be related to useful logic and programming principles for formal syntax.
Since the initial publications, advances in the mathematics and presentation have been introduced piecemeal in the literature. This paper provides in a single accessible document an updated development of the foundations of nominal techniques. This gives the reader easy access to updated results and new proofs which they would otherwise have to search across two or more papers to find, and full proofs that in other publications may have been elided. We also include some new material not appearing elsewhere.
Keywords: Nominal techniques, logic and set theory, nominal abstract syntax, atoms-abstraction, names, variable binding, inductive syntax up to binding, alpha-equivalence.
$Thanks to an anonymous referee and to Alexander Kurz.
URL: http://www.gabbay.org.uk (Murdoch J. Gabbay)
1. Introduction
This paper overviews the logical and semantic foundations of nominal techniques. Nominal techniques were developed with Pitts and introduced in the author’s thesis [24]. The outlines of the mathematical foundations of nominal techniques were apparent in 1999 and were presented in a conference paper [37] and in 2001 in a journal paper [38]. Papers using nominal techniques now number over a hundred [55].
If there is a single idea behind nominal techniques, it is to let names inhabit a denotation directly as a form of data (set theorists should think of urelemente). That is, the ‘’ in , , (), and has an independent denotational reality. This is, in a mathematical sense that we will make formal, a ‘real thing’: a name.
The initial application of nominal techniques (and still, arguably, the most important) is to provide a denotation for inductive datatypes of abstract syntax up to -equivalence—datatypes which admit structural induction and recursion principles while at the same time being intuitively a quotient of syntax by -equivalence (see Theorem 5.18 and Corollary 5.19).
Compare this for example with de Bruijn indexes [15], higher-order abstract syntax [56], or Bourbaki’s boxes and links notation [6, Section 1], which can also be applied to represent syntax with binding; they do not make any commitment to names having a denotational reality.
Indeed, an explicit commitment to an absence of names may be made. For example Bourbaki write and but emphasise “L’assemblage désigné par () ne contient donc pas ”, which roughly translates as “So the string denoted by () does not contain ”. There have been attempts to construct non-trivial syntaxes for logic, foundations, and programming in which variables need not even tangentially appear, e.g. combinator syntax S and K (instead of -calculus) [4], or the formalisation of set theory without variables [64, Chapter 3].
Yet names and binding are so widespread that they must surely reflect some mathematical structure that awards them an independent mathematical existence. Interpreting names as urelemente certainly does that. As it turns out, the resulting mathematics is surprisingly rich.
In the several years we have worked with this material, our understanding of the core ideas has changed. An account of this journey is strewn across a history of documents including [24, 38, 27, 34, 31, 35, 49, 28, 17]. This document is our attempt to gather the threads and tell the story as we now understand it. We hope this paper will offer an account of the basis of a useful and interesting field of enquiry.
1.1. A worked example
We consider an example of the kind of problem we address in this paper; it is drawn from material in Section 5, which fleshes out this sketch to full detail. Why is ‘abstract syntax with binding’ an issue?
Inductively define a datatype of trees representing untyped -calculus syntax not up to -equivalence. Thus, given variable symbols we define terms by:
If is a variable symbol then is a term.
If and are terms then is a term (‘ applied to ’).
If is a variable symbol and is a term then is a term (‘lambda , ’).1 Terms are labelled trees. We obtain an inductive principle on terms:
As is standard, we define free variables fv() inductively by:
We can then try to define a ‘substitution function’ as follows:
Here , , and range over distinct variable symbols. There are two problems with this:
The definition is not inductive because in the clause for ()[], [] is not a subterm of .
It is not a function unless we make some fixed but arbitrary choice of fresh .
There are various ways to fix this. We can work inductively on a measure of size, prove a lemma that [] has the same size as , and then prove that the definition above specifies a function. For each finite set of atoms we can make some fixed but arbitrary choice of ‘fresh’ atom such that and appeal to that choice where we wrote ‘ fresh’ above.
Some authors define a simultaneous substitution, as in [63, 18]; this avoids, but does not solve, some problems, and we pay a certain price in complexity. Others change the datatype entirely, as in the de Bruijn indexes and Higher-Order Abstract Syntax approaches [15, 5, 56].
What becomes apparent is that we are using a datatype whose native inductive principle is not as useful as we might first suppose. This is not a good situation to be in if our goal is to find a mathematics to represent and reason about variable symbols in abstract syntax with binders, and this we must do, if we are to apply formal methods to help design programming and theorem-proving on sentences in formal languages with binders.
The problem is pervasive and does not go away once we have defined substitution. Consider that we may define -equivalence as the least equivalence relation such that:
Here again the same features surface; choices of fresh atoms, and terms above the line that are smaller than, but are not subterms of, terms below the line.
In this paper we present a mathematics which, amongst other things, allows us to define datatypes of syntax with binding that are truly inductive, and to program on them and reason about them in a way that is very close to informal practice, while remaining mathematically completely rigorous.
1.2. Comments on the connections with previous work
For the benefit of the reader who may be familiar with the author’s previous work, we will make brief comments on how what we do here relates with that work:
Cumulative hierarchy model first. We open our technical development in Section 2 with a von Neumann style cumulative sets hierarchy. This takes names (modelled by a collection of atoms ) as urelemente and builds up using powersets. The reason we start with a cumulative hierarchy model is that this presentation should be accessible to everybody, in the sense that everybody knows, or at least is inclined to believe that they know, what a set is. It also helps us when we derive meta-mathematical properties as properties of first-order logic, like the equivariance results outlined in Section 4. The sets presentation, the introduction of names as urelemente in a cumulative hierarchy, and the use of familiar mathematical language, is also intended to be in line with classic constructions in the foundations of mathematics, such as those of ordered pairs, Dedekind cuts, graphs of functions, von Neumann ordinals, and so on.
We do not insist on finite support. Unlike in [24, 37, 38], we do not insist on finite support (Definition 2.16) when we construct our cumulative hierarchy. Nominal techniques are compatible with the existence of non-finitely-supported elements and with the axiom of choice; more on this in the body of the paper. We want to dispel a misconception that ‘nominal techniques force a change in mathematical foundations’ or that ‘nominal techniques are inconsistent with the axiom of choice’. We brought this on ourselves when we wrote sentences like ‘using a different set theory ... is not to be taken lightly’ in [38, Section 1]. It is not necessary to insist on finite support throughout the sets universe.
Axiomatic set theory. As distinct from [24, 37, 38] we de-emphasise logical foundations, that is, axiomatic set theory. For example, in Sections 2 and 3 we develop atoms-abstraction directly, without formalising the meta-language in which we develop it or the foundational axioms we assume. However, the burden of proving results without having equivariance, a fundamental meta-mathematical observation, eventually becomes too much. We introduce equivariance in Section 4 and make frequent use of it from then on. Even so, we observe equivariance as a property of first-order logic with equality and set membership (a sufficient formal language in which to conduct the mathematics in this paper). The full logical foundational view of nominal techniques, represented by the two axiomatic set theories Zermelo-Fraenkel set theory with atoms and Fraenkel-Mostowski set theory, appears in Section 10. This brings us full circle in the sense that the cumulative hierarchy model with which we open our development in Section 2 is also the canonical cumulative hierarchy model of the set theory with atoms with which we conclude it in Section 10.
Full proof that datatypes are up to -equivalence. We give a full proof that ‘nominal’ inductive syntax does yield datatypes of ‘syntax-up-to-binding’; see Theorem 5.18 and Corollary 5.19. This was stated in [37] as Theorem 5.1 and in [38] as Theorem 6.2, but only outline proofs were given. As it turns out, finding the right set of lemmas to prove this result nicely and in detail, is not entirely trivial (Definition 5.15 and Lemma 5.16 seem to be useful).
Use of equivariance. As a general rule, working with name-carrying syntax quotiented by -equivalence looks easy when viewed from afar, and it becomes difficult when viewed close up. To this, nominal techniques offer two related but distinct answers:
– use the atoms-abstraction introduced in [38] to build the datatype purely inductively (material in Section 3) or
– use equivariance Theorem 4.4 to permute names as needed, without losing the inductive hypothesis.
Atoms-abstraction is developed in this document, in Section 3. We use equivariance often in this document (as Theorem 4.4, or as one of its corollaries like Theorems 4.7 or 6.5), but elsewhere we apply equivariance in the specific case of large inductive proofs of properties by induction on formal syntax; we use it to permute names, usually to avoid some form of accidental name-capture, while preserving inductive hypotheses. From the point of view of this paper, these examples are relevant case studies. The use of permutative renamings of variable symbols predates ‘nominal’ work; see for example [50, Subsection 9.2]. The work initiated by the author and Pitts systematised the treatment of permutations and put it in a foundational context (for example, the mathematics in this paper). There is more to equivariance than ‘using permutations’. Equivariance lets us preserve inductive hypotheses ‘for free’. This is important in implementations, and its application in discursive proof—that is, to get a short, elegant proof of a theorem in a published paper—is also new. The interested reader can view the proof of Lemma 8.3 in [26]. To our knowledge this is the first use of equivariance to rename variable symbols in a discursive inductive proof on abstract syntax. See also for example the proofs of Theorems 5.1, 5.2, 5.3, and Lemma 5.7 in [35]. In short, equivariance offers working mathematicians and computer scientists a rigorous ‘short-cut’ to handle renaming in their papers—even if they do not use atoms-abstraction, and even if they are not using a theorem-prover or mechanised mathematics. We have certainly found it useful on several occasions, as referenced in the previous paragraph.
New proofs and more general results. Our presentations of atoms-abstraction in Section 3, and of the atoms-abstraction type-former in Section 8, are completely rewritten relative to [24, 38]. This paper includes some new results (notably: Theorem 3.6; most of the results in Subsection 8.3; many of the results up to and including Theorem 8.18; and Subsection 9.5). This paper also includes some results which are familiar but appear here in a slightly more general form (for example, Theorems 8.14 and 8.20). There is also a little bit of precise commentary on the connection with Mostowski’s work from the 1930s; in Remark 2.22 we make connections betweeen some results fundamental to this paper, and results in a paper by Mostowski, with exact references.2 Finally, most of the familiar results in this paper have re-worked proofs. This constitutes a substantive advance over the original presentations, it assembles bits and pieces from other developments into a new integrated discourse, and also we add new elements specific to this paper.
Nominal techniques as a general methodology, compatible with numerous frameworks. Our constructions can be realised in a variety of contexts. It may be worth making a point of sketching some of them in a brief list. This list is not exhaustive, but it demonstrates that ‘nominal techniques’ can exist conveniently in more than one framework. Here are some of the places in which the ideas reported on in this paper have been usefully applied as part of other research:
– logics (as in nominal logic [57], spatial logic [8], or one-and-a-half level logic [35]);
– programming (as in FreshOCaml [60], Prolog [12], multi-level -calculi [33, 23] and proof-terms [36]);
– semantics such as domains [62] and categories and set theories (we consider some here in Sections 9 and 10)
– game theory [2], and of course
Further applications are cited online [55]. We do not detail these applications, but in Sections 9 and 10 we put the various categories and set theories arising from nominal techniques side-by-side with each other and with the cumulative hierarchy we began with in Section 2. This attempts to give some overview of the more general mathematical semantic places in which the basic ideas of nominal techniques can be realised.3
In this paper we present the core ideas; representing finitary syntax up to -conversion. We discuss some extensions to this mathematics in Section 11.
For us, nominal techniques are not only about representing abstract syntax up to variable binding; they are a general mathematics of names. Their usefulness extends beyond their original intended application to abstract syntax. Further applications are investigated in the author’s other papers, and as listed above, the author is just one of several researchers writing papers in which these ideas are used in different and unique ways.
1.3. Notational conventions
We will use the following conventions:
and range over ordinals (Subsection 2.1).
denotes the set of atoms (Definition 2.3). and range over finitely-supported permutations of atoms and denotes the set of all finitely-supported permutations of atoms (Definition 2.13).
ranges over predicates that can be expressed in the language of ZFA set theory (see Sections 4 and 10).
ranges over functions that can be expressed using predicates , as outlined in Definition 4.5.
is the cumulative hierarchy of all elements (Definition 2.4). ranges over functions from to (not necessarily only functions expressible as a ). is the subclass of of hereditarily finitely supported elements (Definition 10.6). The intuition is that something written in calligraphic font is ‘a very large collection’.
range over elements in .
range over distinct atoms (so ‘ and ’ means ‘any two distinct atoms’; we call this the permutative convention).
range over elements in that are sets (equivalently, over elements that are not atoms).
range over finite sets of atoms.
and range over elements that are atoms-abstractions (Remark 3.9).
range over function-sets (Definition 2.10).
and range over elements of Λ (Definition 5.2). and range over elements of (Definition 5.3).
Sans-serif font indicates a category; ZFASet, FMSet, NOMSet, and NOM.
range over nominal sets (Definition 9.17).
and are functors between categories.
2. A cumulative hierarchy with names
2.1. Some background: ordinals
Ordinals were introduced by Cantor [9]. A concise introduction by Johnstone is available [43]. A Wikipedia article [1] deserves mention for its clarity and accessibility. Ordinals are a large field, so we devote a few lines to outlining what we need for this paper, with sketch definitions.
A relation is transitive when and imply .
A relation is antisymmetric when implies not .
A relation on some collection (which may or may not be a set) is total when , , or for all and in .
Write for . A relation is well-founded when there are no infinite descending -chains (that is, when is impossible).
A well-ordering is a well-founded transitive antisymmetric total relation.
Let ordinals be the collection of isomorphism classes of well-ordered collections.
Ordinals are naturally ordered by the relation ‘is an initial segment of’; when there is an order-preserving bijection of a well-ordered collection in with an initial segment of a well-ordered collection in .
Examples of ordinals (in ascending order) are:
The ordinal 1, pictured as ‘’.
The ordinal 2, pictured as ‘’.
The ordinal , pictured as ‘’ (the natural numbers, ordered in their natural order, are in this equivalence class).
The ordinal , pictured as ‘() ’ (a countable list of elements ‘going on forever’, plus one more element greater than all others).
2.2. The cumulative hierarchy universe
is the standard cumulative hierarchy model of Zermelo-Fraenkel set theory with atoms (Section 10). This construction is due to Zermelo and von Neumann [71, 69]. is a sufficiently rich structure that it can encode standard mathematical constructions (see Subsection 2.3), and it can serve as a model for nominal techniques.
Fix a countably infinite set of atoms. will range over distinct elements of ; we call this a permutative convention.
Our permutative convention is designed to model informal practice. When we write ‘xyxy’ or ‘xyx ’ we normally take it for granted that ‘x’ and ‘y’ denote a pair of distinct variable symbols. It is convenient to reflect this by letting the variables we use to range specifically over atoms, range over distinct atoms.
We define a collection of elements in the style of von Neumann [42] by ordinal induction as follows:
Write for ‘, for some ordinal ’, and read this as is an element. We let be the collection of all elements, that is, is the collection of all such that .
We will call an element that is not an atom a set.4 Examples are illustrated in Figure 1.
Let be an element. Define the rank of , write it rank(), to be the least ordinal for which is true.
For example:
More on rank in Subsection 4.1 and Lemma 5.5.
Some might find it useful to draw elements of as trees (with unordered daughters):
The tree representing an atom is a node labelled by .
The tree representing the empty set is a node with no label.
The tree representing a set is a node whose daughters are the trees representing .
(Of course, there are trees that do not represent elements of ; e.g. trees with repeated daughters like a node with two daughters and no labels or other nodes.)
Note that trees modelling sets may be infinitely broad, and the collection of paths down a tree may have no finite bound on its length (an example is in Definition 2.8). However, any single path down a tree, from the root node towards the leaves, is finitely long; this gives some intuitive justification for the rank function from Definition 2.5, and for rank induction. 3
2.3. Standard constructions in : numbers, pairs, disjoint sums, and functions
is rich enough in structure to model much useful mathematics. For completeness we include a brief sketch of the constructions. We see that they are unaffected by the presence (or absence) of atoms.
Let and be elements. Define the ordered pair () by
This model of () is known as the Kuratowski implementation.
Let and be sets. Define the product set by
Define a model of numbers as sets by and . Write 0 1 2 3. Also, write 1 2 3.
Define a model of boolean truth-values by 0 1.
Let and be elements. Define
Let and be sets. Define the disjoint sum by
Functions are implemented as graphs (():
Let be an element. Call a function-set when
(so is a set of pairs) and
Define () to be the unique such that () if this exists, and () is undefined otherwise.
We let , range over elements that are function-sets.
Let be a function-set. Define:
We call dom() the domain of , and we call img() the image of .
Write for the set
a function set dom( img()
That is, is the set of functions mapping elements of into ( is the range of , considered as an element of ). As is standard, we call this the function-space from to .
We may use -term notation to express function-sets. For example if () expresses a mapping (intuitively, are ‘parameters’ and is the ‘argument’) then we write
We will always make clear whether we are talking about a ‘real’ function, or its model as function-sets in ; exp is a ‘real’ function (which takes and returns exp, for whatever meaning exp may have), whereas exp denotes a function-set.
2.4. Permutations and support
We now begin to explore the structure of from a ‘nominal’ perspective. We start by considering how to permutatively rename atoms in elements of (Definition 2.13). The permutation action reflects the fact that atoms have no internal structure, so ‘one atom will do as well as any other atom’—later, we turn this into a theorem when we use the permutation action to define and prove equivariance in Subsection 4.2.
It is also possible to define a notion of dependency of an element on a set of atoms. We call this key notion support (Definition 2.16). Perhaps the first non-trivial observation here is that if an element has a finite supporting set of atoms, then it has a unique least finite supporting set of atoms. This is Theorem 2.21; this property is one way in which nominal techniques are distinguished from related approaches to names and binding based on presheaves [20] (see also Remark 9.13).
The reader can think of the support of an element as a generalisation of the notion of ‘free names in’, generalising this notion from abstract syntax trees to all sets. As discussed in the Introduction, not every element in has finite support, but we will be most interested in the ones that do.
A permutation is a bijection on such that () is finite (we say that has finite support). will range over permutations. We also use the following notation:
Write id for the identity permutation, so id( always.
Write for functional composition. So ()((()).
Write for the inverse of , so id .
Write for the set of all permutations.
Let be a finite set of atoms.
Write fix((.
Say that supports when for all fix().
Say has finite support when some finite supporting exists.
Define supp() the support of by
if has finite support, and supp() is undefined otherwise.5
Write # when supp() and call fresh for .6 Write # for ‘# and # and #’, and so on.
It is important to realise that supp() is not equal to .
supp() contains the ‘conspicuous’ atoms of . An atom is ‘inconspicuous’ when it can be permuted for other inconspicuous atoms without changing . Finite support ensures that there are plenty of these inconspicuous atoms around.
It is also important to realise that an atom can be conspicuous by its absence as well as its presence. For instance, supp(. It is a fact that , and that makes it conspicuous relative to the other atoms in . 3
Not every element of has finite support. Make a fixed but arbitrary choice of bijection of with the natural numbers 0 1 2 3 4 5. Let comb be the element corresponding under this bijection with the even numbers 0 2 4.
comb contains ‘every other atom’ . It forms a ‘comb’ through the set of all atoms, where the ‘teeth’ of the comb are the atoms in comb, and the ‘spaces between the teeth’ are the atoms not in comb.
There is no finite such that if fix() then comb comb. 3
supports if and only if supports .
As an immediate corollary, supp( supp().
is invertible so it suffices to show that if supports then supports . Suppose supports and suppose fix(). By easy calculations fix(). Therefore () and so (.
Let be any element. If and are finite and support then so does . As a corollary:
1. If has a finite supporting set then it has a least finite supporting set and this is equal to supp().
2. If then .
The corollary follows by elementary calculations and the definition of support in Definition 2.16.
Suppose fixes pointwise. We must show . Write
Choose an injection of into (). Define a permutation by
Note that id, so . fixes pointwise so . Also fixes pointwise so (). We apply to both sides, use Lemma 2.15, and simplify, and conclude that as required.
The constructions above have been seen before, though written in a different language (literally) and with very different aims: they correspond with certain constructions in a paper by Mostowski [53] (also in English translation [54]).
It is quite interesting to trace how these ideas appear in [53, 54]. Our notation is very different from Mostowski’s, and Mostowski’s papers embed the results relevant to us in a broader and more complex argument.7 Therefore, for the reader’s convenience we will briefly trace through a few of the common points, giving precise references.
Definition 2.14 corresponds with Definition 30 in [54]. Lemma 2.15 corresponds with Results 33 and 36. The first part of Theorem 2.19 corresponds with Result 41. The first part of Theorem 2.21 corresponds with Result 88 and the first part of the corollary (the construction of supp()) corresponds with Result 101. 3
2.5. Swappings
A particular kind of permutation will be useful later:
[38, Proposition 3.4] proves ‘if supports and () is infinite, then supports ’. For sets with finite support this is equivalent to Theorem 2.21, but the statement of Theorem 2.21 is more ‘topological’ and less ‘pointwise’.
Theorem 2.21 makes clearer the correspondence with pullback-preserving functions (cf. Theorem 9.14). The form of Theorem 2.21 is probably also more useful for considering generalisations of the notion of support, e.g. to infinite sets [27]. 3
Note that in [38] and [37], a permutation is taken to be any bijection on atoms—not just bijections with finite support. The design decision made in Definition 2.13, to use finitely-supported bijections, gives us the advantage of easier proofs: for example, in Theorem 2.21 must be finite so we can conveniently build .
In practice there need be no difference in power between the ‘finitely-supported permutation’ mathematics and the ‘all bijections’ mathematics. We will be most interested in elements with a finite supporting set. For any bijection , there exists a finitely-supported bijection with the same action on supp(). The action of away from will never be important to us (that is, we will only ever care about a finite part of ).
Restricting to finitely-supported permutations in the first place has the advantage that we can conveniently choose ‘fresh atoms’, so we have preferred this slightly stronger formulation of the definitions. 3
For each finite , fix() is a group, and is generated as a group by swappings () such that .8
As a corollary taking , is a group and is generated as a group by swappings.
It easy to verify that fix() is a group.
We now show that fix() is generated as a group by swappings. Suppose fix(). Recall from Definition 2.13 that () is finite; we work by induction on the size of this set. If () is empty then id and we are done. Otherwise, suppose is such that () . We consider (() ). It is easy to verify that fix() and that the inductive hypothesis is applicable to . The result follows.
We find Theorem 2.21 to be consistently the most convenient formulation of the notion of support. On the other hand, the later Theorem 6.2 is elegant, since we can take advantage of the many good properties of the ‘new’ quantifier introduced by the author and Pitts in [38], plus finite support (most notably, Theorem 6.5). Yet Theorem 2.21 is impredicative, and Theorem 6.2 uses a quantifier which is less well-known than, say, and . We therefore mention Theorem 2.27, which is a simple and direct way to characterise the atoms in supp():
Let be an element with finite support.
Then supp() if and only if () is finite.
Suppose has a finite supporting set. For the reader’s convenience we collect three ways of detecting atoms in supp():
supp() when for every finite such that supports (Theorem 2.21).
supp() when () for only finitely many (Theorem 2.27).
supp() when () (Theorem 6.2). The -quantifier (pronounced ‘new quantifier’) is defined in Definition 6.1.
3
2.6. Permutation and support acting on the standard constructions
We can now consider the behaviour of permutation and support on standard mathematical constructions, such as ordered pairs and functions. Theorem 2.29 seems to capture a lot of this behaviour; for example we use it to give a one-line proof of the important Corollary 2.30. We also consider the permutation action on function-sets (Theorem 2.33).
Suppose is a set, all of whose elements have finite support. If supp() is finite then supp() exists and
In particular if is finite (so that supp() is a finite union of finite sets and so is finite) then supp(supp() .
Suppose that supp() is finite. We prove two set inclusions:
supp() supp() . If supp() is finite then the result follows by Theorem 2.21 and the fact that .
supp() supp(). Suppose and supp(). Choose fresh (so # and # for every ). By Theorem 2.19 supp(())supp(). Since has no element such that supp(), we know that () and by Theorem 2.21 it must be that supp().
Let and be elements with finite support. Then
Directly from Theorem 2.29.
Corollary 2.30 is a specific corollary of a general result (Theorem 2.29). It can be obtained in another way: by Theorem 4.7 (proved later, but there is no circularity) supp(()) supp()supp(), and also, observing the existence of first- and second-projection functions, by Theorem 4.7 also supp() supp(()) and supp() supp(()).
However, Theorem 2.29 does not follow from Theorem 4.7. These are two distinct results.
3
Suppose is a function-set. Then is a function-set in , and it represents the function
This is the conjugation action.
3. Atoms-abstraction
We mentioned in Section 2 that support generalises ‘free names of’ from abstract syntax trees to all elements. It turns out that -binding admits a similar generalisation, to all elements with finite support. The construction works by building, in the sets universe , a set which is visibly an ‘-equivalence class’. In Subsection 3.1 we consider the theory of -equivalence classes in somewhat more generality than was considered in previous work [38, 24]. Definition 3.8 describes the specific instance which will be of most interest us, which is abstraction of an element with finite support by a single atom (written []), and Subsection 3.2 develops its theory.
It may be worth briefly noting how generalisations of support and abstraction are useful. Generalising ‘free names of’ to a notion of finite support applicable to elements, allows us to deal with this notion more abstractly and also lets us choose a fresh atom for a complex non-syntactic structure (e.g. an element representing a function, or a game). Generalising -equivalence similarly lets us model name-binding abstractly, and for complex non-syntactic structures. This leads to the new inductive principles described in [38] (also see Section 7) and so to its implementations, and also for example to denotational semantics ([61] and [2] are examples).
3.1. Generalised -equivalence classes
admits a model of -abstraction given by forming equivalence classes of ‘renamed variants’ of an element with finite support. For example,
models ‘-abstract in ’ (and ‘-abstract in ’, and ‘-abstract in ’). Also for example,
represents ‘abstract and simultaneously in ’.
The two examples above are equal to and respectively, in the notation developed in Definition 3.1.
In this subsection we make the model formal using permutation orbits in Definition 3.1 and the subsequent results. The immediate application of permutation orbits is to abstract atoms one at a time; see the atoms-abstraction operator described in Subsection 3.2 and its application to model syntax with binding in Definition 5.2 in Section 5. However the generalisation is of interest as ‘the mathematics behind the atoms-abstraction operator’—it also gives an elegant proof-method, it may be useful in future work (for example to give a direct model of simultaneous quantification), and indeed we have used the notion of permutation orbits in recent past work, to consider substitution as an action on (rather than on abstract syntax) [31]. Our main result here is Theorem 3.6, which states a form of soundness that permutation orbits express a notion of simultaneous -abstraction.
We call this the permutation orbit of under permutations fixing pointwise.
For example:
all .
If fix() then ).
is the permutation orbit of under the action of fix(). fix() is a group by Lemma 2.26. The result follows.
(). (The action is pointwise.)
(Lemma 3.4 may also be obtained by equivariance, Theorem 4.4.)
To prove () () take (). Then () for some fix(). It follows using Lemma 2.15 that ). It is a fact that fix(), so we are done.
The proof that ()() is similar.
Lemma 3.5 is useful for proving Theorem 3.6:
Suppose is finite and is an element with finite support. Suppose that supp() . Then
Theorem 3.6 is the technical heart of the proof of Theorem 3.11, but it stands on its own as a result describing the interaction of support with taking permutation orbits .
Suppose is finite and is an element with finite support. Then:
If supp() then supp( supp().
supp() always.
As a corollary,
If supp() then by the definition of support, if fix() then and . It is easy to verify that supp( supp().
Suppose that fix(). We use Lemmas 3.3 and 3.4:
By Theorem 2.21 the result follows. Now suppose supp(). By part 2 of this result supp() . It remains to prove the reverse inclusion.
Choose any and any . By Lemma 3.5 we know that
By Definition 2.14 and Theorem 2.19 we also know that
It follows that )(), so by Theorem 2.21 it follows that supp().
It may be useful to illustrate Theorem 3.6 with two examples:
An example where supp() .
An example where supp() .
3.2. Atoms-abstraction
We now come to atoms-abstraction [], a central component of the model of syntax-with-binding [38, 24]. Permutation orbits generalise -abstraction. We demonstrate this in Definition 3.8 by using them to build it:
By convention, variables and will range over elements that are atoms-abstractions. That is, if we write then it means we are assuming that
has finite support and ]
3
In this subsection and the next we characterise atoms-abstraction in three ways. For the reader’s convenience we assemble the characterisations with very brief comments. Full definitions and notation follow.
[]) (Definition 3.8).
This places [] as an instance of a more general construction.
[]()( ()) # (Lemma 3.13). This enumerates the elements in [] as a set and makes clear in what sense it can be considered functional.
(@ is ‘concretion’, the destructor for []-. See Lemma 3.16.) This enumerates the elements of an atoms-abstraction in terms of all possible actions of the corresponding destructor.
3
Let be an element with finite support. Let be any atom. Then
supp(( supp(). By definition []). The result follows by Theorem 3.6.
Let and be elements with finite support. Then:
1. []] if and only if # and ().
2. []] if and only if for some fresh (so #) it is the case that ()).
Suppose that []]. By Theorem 3.11 we know #. By Theorem 2.21 if fix(supp()) then () ). Since () [] it follows that (). Conversely suppose that # and (). By Theorem 3.11 and Theorem 2.21 ()[]]. The result follows by Lemma 3.4.
For the second part, suppose []] and suppose that is fresh (so #). By the first part # and (), so ()()). The result follows by Lemma 2.15 and Theorem 2.21. Now suppose that ()). By Theorem 2.19 we can calculate that #. Also ()())() and by Theorem 2.21 it follows that ().
Our definition of atoms-abstraction matches that of [38, Lemma 5.1]:
[]()( ()) #.
The reader may wonder why we define [] to be ()—would not
do as well?
We could do this, but we prefer not to for several reasons. One reason is historical: we maintain compatibility with the definition in [38]. Another reason is that () is more suggestive because it makes [] look like (), which it is designed to emulate in inductive datatypes (see Λ and in Section 5).
Finally, there is a practical reason: every representative () carries information about the ‘abstracted atom’ which can be extracted using a first projection, also, our definition always returns an infinite equivalence class whereas may be equal to if #, which is inconvenient in the sense that, if we are just given without further comment, it is not clear whether we mean ‘[]’ where it happens that #, or ‘singleton ’.10 3
Let be an atoms-abstraction (with finite support).11 Then
3.3. Concretion @; the destructor for []
Let be an atoms-abstraction (with finite support) and let be an atom such that . Then there is a unique such that ].
Define @ to be this unique element if it exists, and undefined otherwise.
Suppose ]. By construction () []. Also by construction, for fix(supp()), and it follows that (. By Theorem 2.21 and the result follows.
@ is defined if and only if .
Corollary 3.18 states a formal sets sense in which an atoms-abstraction is made up of its ‘destructed parts’, just as ( states how the pairset () is made up of its first and second projections and :
(@) .
Let be an element with finite support. Let be an element with finite support; by our convention in Remark 3.9 we assume that is an atoms-abstracton.
If # then ([])@ is defined and ([])@).
If then @ is defined and [@.
4. Meta-mathematical properties of U
The proofs of properties of elements of in this paper can be written out in a formal language, described below. We will use this to formally state and prove properties of the assertions we can make about . These are meta-mathematical properties; properties of properties of . The most important ones are rank induction (Theorem 4.2) and equivariance (Theorem 4.4, and its corollaries Corollary 4.6 and Theorem 4.7).
Consider first-order logic with:
A binary predicate symbol called equality.
A binary predicate symbol called set membership.
A constant term-former called the set of atoms.
So, terms and predicates are inductively defined by:
This is the language of ZFA set theory (Section 10) and is a sufficent language for much mathematics. For example, we can use this language to formally reason about from Definition 2.4.
4.1. Rank induction
A notational convention will be very useful in what follows:
We abbreviate a list of variables, such as , to . For example, () is shorthand for ().
By contradiction. Suppose denotes an element of least rank such that () does not hold. So for all with rank() rank() it is the case that (). By assumption it follows that ().
4.2. Equivariance
Write
Note that must contain all the variables mentioned in the predicate. Clearly, it is not the case that if and only if —but it is the case that if and only if .
We work by induction on the syntax of .
implies direct from Definition 2.14. The reverse implication is easy using .
if and only if is also direct from Definition 2.14.
The case of is trivial, and the cases of and follow using the inductive hypothesis.
, so if and only if , and if and only if , and similarly if and only if and if and only if .
The result follows.
As is standard, we can specify a map using a predicate () such that
Suppose () is a function on variables included in , which is . Suppose denotes elements with finite support. Then
As a corollary, if is injective then
The corollary follows by considering the result for and its inverse.
Suppose that fix(supp()supp()). We reason as follows:
The result follows.
Suppose () is a function on variables included in , which is . It is not necessarily the case that
It suffices to give a counterexample. We give two:
( always.
(; take and . So supp( supp() but supp( .
5. Case study: inductively-defined -terms using atoms-abstraction
We are now ready to use atoms-abstraction to build datatypes of syntax-up-to-binding in nominal style; nominal abstract syntax. Λ and are two sets, both representing -calculus syntax. represents terms not up to -equivalence—we might call this ‘raw syntax’. In this section we shall make formal a natural sense in which Λ represents -calculus syntax up to -equivalence (this is Theorem 5.18 and Corollary 5.19). Of course, we can build a set of terms up to -equivalence just by quotienting by -equivalence (Definition 5.17). However, Λ is inductively defined. In Section 7 we will exploit this, to develop new inductive reasoning principles on Λ.
First, a technical lemma:
), ], ], and (] are all impossible.
By construction has no members and () has one or two. Meanwhile, Lemma 3.13 makes it evident that [] always has infinitely many members.
We propose an inductive datatype of untyped -calculus syntax using atoms-abstraction.
By Lemma 5.1 the three ways of constructing elements of Λ are mutually exclusive.
We define an inductive datatype of untyped -calculus syntax (not up to -equivalence) using a more traditional name-carrying construction:
Here we write for ( ()).
For the rest of this section, , , and range over elements of Λ, and , , and range over elements of . For example, ‘’ means ‘some element of Λ’ and ‘()’ means ‘for all in Λ, ()’. 3
Some bounds on the rank of elements will be useful:
rank(( max(rank() rank(.
rank(inl()) rank(. rank(inr()) rank(.
rank( rank().
rank( rank(.
rank([]) rank(.
By Definition 2.7 (. Then
and so
By Definition 2.9 inl(). It follows by the first part of this result that rank(inl( max(1 rank(. Also, inr(), and it follows that rank(inr( max(2 rank(. The result follows by arithmetic.
rank( rank() by Corollary 4.6.
rank( rank( follows by construction and since rank( rank().
rank([]) rank(( follows by the previous parts and since rank(.
By rank induction (Theorem 4.2) and Lemma 5.5 we obtain inductive principles:
Λ and are elements.
In symbols: Λ and .
An easy observation:
The permutation action on elements in Λ and satisfies:
All elements of Λ and are finitely-supported, and the support of elements of Λ and satisfies:
Support matches the usual notion of ‘free variables of’ for Λ, but not for . Elements of do not ‘know’ that is supposed to be a binder. Therefore we must define the notion of free variables separately, as in Definition 5.10. 3
As is standard, we define the free variables fv() inductively by:
Define a translation - inductively from to Λ by:
Support in Λ in the sense of Definition 2.16 corresponds with ‘free variables’ in under the translation of Definition 5.11:
supp( fv().
For each finite set of atoms make some fixed but arbitrary choice of ‘fresh’ atom such that .13 We specify a substitution action on the name-carrying datatype by:
Here, is chosen according to our fixed but arbitrary choice, fresh for , , and the atoms in and .
Definition 5.13 is not inductive on syntax because in the clause for ()[], [] is not a subterm of . In fact, what we have is an inductively-specified relation, which we might write as “-[] is related with -”. For example, if and are related, and and are related, then so are () and ()(). We should prove that this specification does indeed specify a function:
Definition 5.13 specifies a well-defined function.
Also, rank([ rank().
By induction on rank().
Definition 5.15 and Lemma 5.16 are key technical constructions with which the rest of the proofs (including that of Theorem 5.18) run quite smoothly:
Define the bound atoms ba() inductively on by:
Suppose . For all atoms and , if does not occur in (that is, if #) and if ba(), then [).
By induction on :
The case of . [).
The case of . There is nothing to prove since occurs in .
The case of . [).
The case of . ()[[])([]) and ()())(()). We use the inductive hypothesis.
The case of . There is nothing to prove since ba().
The case of . There is nothing to prove since occurs in .
The case of . ()[([]) and ()((). We use the inductive hypothesis.
Define -equivalence on to be the least equivalence relation such that:
Here, is chosen according to the fixed but arbitrary choice in Definition 5.13, fresh for , , and the atoms in and .
if and only if .
We prove two implications.
We prove by induction on that
We consider only one case. Suppose
where is fresh and ba() and ba(). By Lemma 5.16 ()), so also () (). By Theorem 4.4 ()). By Lemma 5.12 # and #. By part 2 of Lemma 3.12 []] so
We also prove by induction on rank() that
We consider only one case. Suppose that [][]. By suitable -conversions in and we can ensure that ba() and ba(). By equivariance these have the same rank as the originals so we retain the inductive hypothesis. So assume without loss of generality that ba() and ba(). Let be the choice of fresh atom for the atoms in , , , and . By Lemma 5.8 # and #, so by Theorem 4.7 # and #. Therefore by part 2 of Lemma 3.12
It follows by the inductive hypothesis that [[]. We conclude that as required.
- expresses a bijection between Λ and -terms up to -equivalence.
In view of Theorem 5.18 it suffices to prove surjectivity; for every Λ there exists some such that . This is routine by induction on rank().
The next step is to explore ‘nominal’ inductive reasoning principles for Λ. We do this in Section 7, after we have constructed the -quantifier.
6. The quantifier and the ‘fresh’ binder
6.1. The quantifier
The -quantifier is a characteristic feature of nominal techniques, and was introduced in [38]. holds when holds of all but finitely many atoms (see Definition 6.1 for the formal definition). That is, means ‘all but finitely many’.
We can make connections here with quantifiers for ‘most’ and ‘many’ [70] and with generalised quantifiers [45, Section 1.2.1], which are of particular interest in linguistics. Cheney generalised the notion of ‘finitely many’ using ultrafilters, in the study of completeness for nominal logic [11], and the author has considered a generalisation of ‘finite’ to ‘well-orderable’, in the study of elements with infinite support and with abstraction by infinitely many atoms [27].
The notion of ‘all but finitely many’ is not new to the study of variables in syntax. Krivine used the notion in his book [46, Section 2, ‘-equivalence and substitution’]. What makes the in this paper different and useful is the way it interacts with equivariance and finite support; these give the -quantifier its characteristic some/any property (Theorem 6.5) and commutations with connectives and quantifiers (Theorem 6.6).
Using support, can be expressed using , and also using (Theorem 6.5). A related property of is self-duality—when the left- and right-introduction rules of a quantifier are symmetric (Remark 6.7).14
We will use in this paper, beginning with its application to inductive reasoning principles on syntax with binding in Section 7.
Freshness # (Definition 2.16) can be characterised directly using and equality (see [38, Equation 5] or [38, Equation 13]):
Suppose #. By Theorem 2.21 if () then supp(). supp() is finite by assumption. The result follows.
Now suppose that (). Choose any pair of distinct atoms and such that () and (). Note that
Therefore () always. It follows that if fix() then . Therefore supp().
has finite support if and only if ()
If is a list of variables write
Theorem 6.5 expresses the characteristic some/any property of the -quantifier:
Suppose denotes a list of elements with finite support.
1. Suppose () and () are predicates on variables included in and respectively. If # then
Here, op ranges over , , and .
2. Suppose () is a predicate on variables included in . Write fs() for the assertion ‘ is an element of finite support’, formalised in the language of ZFA (for instance as in Definition 2.16 or Corollary 6.3). Then:
3. Suppose () and () are predicates on variables included in . Then
Here, op ranges over , , and .
1. Using Theorem 6.5 and elementary properties of and .
2. Easy using Theorem 6.5.
3. We consider the case of implication, which is the least trivial. Suppose (() ()) and (). By Theorem 6.5 if # then () () and (). Choose some #; it follows that () so by Theorem 6.5 we conclude that (). Now suppose (()) (()). We use Theorem 6.5; it suffices to choose # and prove () (). Suppose (). By Theorem 6.5 (), therefore (), and by Theorem 6.5 we deduce () as required.
We call self-duality. In fact, self-duality is when the left- and right-introduction rules are symmetric with each other; in the case of classical logic with two truth-values, this is equivalent to commuting with classical negation.
Miller and Tiu have developed another self-dual quantifier , with quite similar properties [65, 52]. Tiu’s recent work [65] also emphasises equivariance. 3
6.2. The ‘fresh’ binder
Intuitively, generates fresh atoms in predicates. Sometimes it is useful to generate fresh atoms in functions too.
Definition 6.8 is well-defined, and fr (() for any fresh (so #).
The ‘fresh’ binder satisfies algebraic properties analogous to those satisfied by . These were useful when the author implemented nominal theory in Isabelle [24]. Nominal Isabelle, a major reimplementation and extension, was then developed and applied to significant case studies [67].
Suppose denotes a list of elements with finite support. Suppose () and () are functions specified using and a variable considered to range over atoms. Suppose () is a function specified using and and .
For clarity and by abuse of notation, we will just write (), (), and (); we take to be understood.
Suppose
Then
We must show that fr ((()()) is well-defined. Choose fresh (so #). It suffices to prove that #(()()). This is easy, since #() and #() by Theorem 6.5 ( form), and by Theorem 4.7.
To prove the equality, by Theorem 6.5 ( form) it suffices to choose fresh (so #) and show that
By Theorem 6.5 ( form) we know that fr (() and fr ((). The result follows.
The proof of the second part is similar.
7. Application to reasoning on abstract syntax with binding
Recall the inductive principle for Λ given in Theorem 5.6; it treats atoms-abstraction []- (Definition 3.8) like an ordered pair. It is true that [] resembles the pair () (Definition 2.7), and []- and -@ (Lemma 3.16) behave very much like ( -) and second projection. However, [] satisfies some equalities that () does not, as laid out in Theorem 3.19. As a result:
Λ is inductive, like and unlike quotiented by -equivalence.
Λ is in bijection with -terms up to -equivalence, unlike and like quotiented by -equivalence.
Theorem 7.1 exploits this to present an alternative inductive principle. This result is the motivating observation of [38] and of its implementations, starting with those in the author’s thesis [24] and progressing, for example, to Nominal Isabelle package and FreshML [68, 67, 60].
Suppose Λ has least rank such that () does not hold. We reason by cases to deduce a contradiction:
Suppose . By assumption (), a contradiction.
Suppose . By Lemma 5.5 rank() rank() and rank() rank() so by inductive hypothesis () and (), therefore by assumption (), a contradiction.
Suppose where is an atoms-abstraction. Choose fresh (so # and #). By part 3 of Theorem 3.19 @ exists and ](@). By Lemma 5.5 rank(@) rank() so by inductive hypothesis ( @). By Theorem 6.5 ( form) since # by assumption ([](@)), a contradiction.
We take a moment to state a variant of the result stated in Theorem 7.1, which uses concretion -@ instead of atoms-abstraction []-:
Here ranges over , and range over elements of Λ, and ranges over atoms-abstractions of elements in Λ (recall Remark 3.9). This variant may be more convenient if we think in terms of ‘decomposing’ a term, but this is purely a matter of convenience and the two forms are logically equivalent.
We can give a similar principle for defining functions out of Λ; this inductive principle is Theorem 6.5 of [38]. Treatments are also in [24, Subsection 10.4], and subsequently in [58]:
Suppose we are given functions (), (), and (), from to . For each fixed sequence of values for the variables , there exists a unique function-set such that dom( and such that
Here ranges over atoms and and range over elements of Λ.
Let () be the predicate
“if Λ then () exists and is uniquely defined”
formalised in the language of ZFA.15
We use the inductive principle described in Theorem 7.1:
The cases of and are easy.
We now prove that () ([]). By Theorem 6.5 ( form) it suffices to choose fresh (so #), to choose any , to suppose () and then to prove ([]). By Theorem 6.5 ( form) since #, ([]( []()). By assumption () exists and is uniquely defined, therefore so is ([]). The result follows.
Here Λ.
This corresponds with the definition of capture-avoiding substitution as written out informally, following Lemma 5.12 and letting # correspond with ‘ not free in ’.
8. Type-formers: [] and #
For typed systems based on nominal techniques, it is important to understand the behaviour of sets of atoms-abstractions. Of particular interest is the interaction with sets union, cartesian product, disjoint sum, and function-spaces. Also of interest are functions out of sets of atoms-abstractions, since this structure influences the recursive, inductive, and pattern-matching principles which can be developed for programming destructors on types of atoms-abstractions. In this section we summarise, and generalise, what is known about sets of atoms-abstraction.
8.1. [] the abstraction type-former
Some terminology will be useful.
Suppose that is a set. If has finite support say that has finite support to level 0. If has finite support and all set members of have finite support to level , say that has finite support to level .
We will only need finite support to levels 0 and 1.
We define the abstraction type-former [], following [38, Definition 5.4]:
Let be a set with finite support to level 1.16 Define
A motivation for considering [] is to inductively model syntax-with-binding. The construction of inductive datatypes is based on fixedpoints for monotone functions.
[]- is monotone on sets with finite support to level 1.
That is, if and are sets with finite support to level 1 then implies [] [] .
Definition 8.2 is oriented towards constructing elements of []. There is another characterisation of [] more oriented towards destructing elements:
Let be a set with finite support to level 1. Then
We prove two set inclusions.
[][]([])@. Suppose , , and #. We use Theorem 6.5 ( form). Choose fresh (so #). By Theorems 4.4 and 2.21 (). By part 1 of Theorem 3.19 ()])@. The result follows.
[]([])@ []. Suppose , , and ([])@. We use Theorem 6.5 ( form). Choose fresh (so #). By part 3 of Theorem 3.19 [](([])@]. The result follows.
8.2. The set of finitely-supported functions
This short subsection is devoted to sets of finitely-supported functions (Definition 8.5). This is used in Subsection 8.3 below, but it is more generally important than that. For example, is used to build the arrows in the category FMSet in Definition 9.5, and it is the basis of the exponential of the categories FMSet and NOMSet (Lemma 9.7).
In words: is the set of finitely-supported functions from to .
It is not the case that () in general. For example take and . Recall comb from Remark 2.18. Define
The reader can verify that () ().
Note that can be non-empty even if and contain elements without finite support. For example, take to be the set of total orderings of , and take . Then the identity function-set is in , as are the function-set for ‘reverse the order’, and many other functions that treat their arguments equivariantly.
Similarly, can be non-empty even if does not have finite support. However, if does not have finite support then no has finite support and is the empty set. We could address this, if we were so inclined, by considering a function space of finitely-supported partial functions. 3
8.3. # the -fresh type-former
Suppose and are sets and suppose (Definition 2.12) is a function-set. Write when is a bijection. Write when some exists such that .
Definition 8.8 reprises a comment in [37, Section 7, page 9]. The mathematics that follows on from it is new:
Call this the -fresh version of .
If and are sets with finite support to level 1 and , write
We will be most interested in and for the case that # and #.
# does not necessarily imply that .
Consider #. Then .
A basic result of -fresh sets is Theorem 8.10:
Suppose and are sets with finite support to level 1. Suppose . Suppose is an atom such that #, # , and #. Then
As an immediate corollary, if and only if .
Intuitively, this means that if is a set and #, then captures all of the important structure present in .
Suppose . It follows using Theorem 4.7 that . By a similar argument for the inverse of , and by some elementary calculations, we see that is a bijection.
Now suppose . We must show that is surjective and injective.
Surjective. Choose any element . If # then and by assumption () for some . So suppose supp(). Let be a fresh atom (so #). By Theorem 2.21 () . By equivariance () . By Theorem 2.19 #(), so ()() for some . By Theorem 2.21 () and (). By equivariance () and (()).
Injective. Choose any two distinct elements . Let be a fresh atom (so that #). By Theorem 2.19 #() and #(). By Theorem 2.21 () and (). By equivariance () and (). By assumption (()) (()). By equivariance again, () ().
For the corollary, if then is immediate. Conversely, if then we take to be the identity on , so that is the identity of , and we deduce that , that is, .
We now prove that - distributes over several constructs which are useful in constructing inductive (and indeed coinductive) datatypes.
Let and be two sets with finite support to level 1. Let be an atom such that # . Then
for op one of , , . In addition, if is a function-set then
The cases of , , and are by easy calculations using Corollary 2.30. The case of unions is routine.
Recall the definition of the ‘fresh’ binder fr from Definition 6.8.
Let and be two sets with finite support to level 1. Let be an atom such that # . Then
The bijection is given by:
There are a number of things to check:
. By Theorem 4.7 has finite support. Suppose . So # and # then by Theorem 4.7 #(). The result follows.
is well-defined and . Suppose and is fresh (so #). Recall that # and # ; by Theorems 4.4 and 2.21 it follows that (). Since # we know (())() is well-defined and (())() . Since #(())() by Lemma 6.9 fr (())() is well-defined. The result follows.
#. By Theorem 2.19 it suffices to choose fresh (so #) and prove that () . Choose any . Choose fresh (so #). By Theorem 6.5 ( form) (())( (()())(). By Theorem 2.19 #(). By Lemma 2.15 and Theorem 2.21 ()() (). The result follows.
. Suppose (). Unpacking definitions,
Choose any , and choose fresh (so #). By Theorem 6.5 ( form) it suffices to prove
(recall that # and #). Now and #, thus, . The result follows.
. Unpacking definitions,
Choose and choose fresh (so #). By Theorem 6.5 ( form) it suffices to prove
We reason as follows:
The result follows.
8.4. Using # to prove properties of []
Let be a set with finite support to level 1. Let be an atom such that #. Then
Suppose [](). By construction (Definition 8.2) there are two possibilities:
] where . Note that [] [] and by Theorem 3.11 #[]. It follows that [] ([]).
] where and #. Note that [] [] and by Theorem 3.11 #[]. It follows that [] ([]).
Now suppose ([]). Again, there are two possibilities:
] where # (#[] is guaranteed by Theorem 3.11). Choose a fresh (so #). By part 1 of Lemma 3.12 ](). By Theorem 2.19 #(). Therefore []() []().
] where #[] and #. Choose a fresh (so #). By part 1 of Lemma 3.12 ](). By Theorem 3.11 # so by Theorem 2.19 #(). Therefore []() []().
Let be a set with finite support to level 1. Let be an atom such that #. Then
where and its inverse, we write it , are given by:
(By Lemma 3.17 @ exists, since we assume .)
We must show that the maps map between elements of ([]) and elements of .
To show that [] [] we must show that #. This is by assumption.
To show that @ there are two cases:
– Suppose that [] because ] for some and #. By part 2 of Theorem 3.19 @ and so @.
– Suppose that [] because ] for some and #, where is different from . By part 1 of Theorem 3.19 @). By Lemma 8.4 and Theorem 6.5 ( form) since # also @.
We must show that the maps are inverse. This is easy:
([])@ by part 2 of Theorem 3.19.
[@ by part 3 of Theorem 3.19.
One of the observations in [24] is that atoms-abstraction is remarkably well-behaved, and commutes even with function-spaces (see Corollary 9.6.9 of [24] or Remark 5.6 of [38]). We can use -fresh sets to give some quite slick proofs of these facts:
We give the reasoning for []( ) and for indexed unions; the other cases are similar and no harder.
For functions, we reason as follows; we take fresh (so # and #):
if and only if (Theorem 8.14) ([]()) ([]) ([]) if and only if (Lemma 8.12) ([]()) ([] []) if and only if (Theorem 8.10) []() [] []
Here, the top bijection is the identity, and we take fresh (so #).
Now suppose that is a function-set with finite support and suppose that supp() is finite. We obtain a bijection between [](()) and []() straight from Lemma 8.11 and Theorem 8.14, but to exhibit an equality we have to do some new calculations.17 We prove two set inclusions:
[](()) [](). Suppose that [] [](()). Then there exists some dom() such that () and # (). Choose fresh (so # and, because of (1), # for every dom()). It follows by Theorem 4.4 and Theorem 4.7 that ()(). So there exists some dom() such that ()(). By Theorem 4.7 #() so []() []() — (1) helps make sure that #. It follows by part 2 of Lemma 3.12 that [] []() and the result follows.
[]() [](()). By Theorem 8.3.
The sense in which the abstraction type-former commutes with unions given in Theorem 8.15 is slightly more general than that given in [38] (Section 6, page 14, just after equation (50)). Here, we do not insist that is definable in the language of ZFA. We replace that with the condition that have finite support and satisfy (1). 3
We explicitly unpack the bijection in the proof Theorem 8.15 in the cases of and :
([] []) bijects with []().
[]() bijects with []fr []( @@) and [] [] bijects with fr [](([])@)
3
Theorems 8.18 and 8.20 characterise the functions out of [] in two different ways.
Let and be sets with finite support to level 1. Let be an atom such that # and # .
Then
(Note that by Theorem 8.10 we can settle an equality between and by examining equality between and , so in that sense Theorem 8.18 really does characterise all the functions out of [] , and not just those that is fresh for.)
Let be a set with finite support to level 1, and let be a set with finite support (to level
0). Define
Then a bijection
is given by the maps
There are several things to prove; we consider the less trivial ones:
is well-defined and is in [] . Fix []. Choose fresh (so #). @ exists by Lemma 3.17. @ by Lemma 8.4. So (@) is well-defined and in . #() is the condition required for fr (@) to be well-defined.
() is such that #(). By Theorem 6.5 ( form) it suffices to take any and some fresh (so #) and check that #([]). This is by Theorems 3.11 and 4.7.
By Theorem 6.5 ( form) it suffices to check that for any and some fresh it is the case that ( ([])@(). This is by part 2 of Theorem 3.19.
By Theorem 6.5 ( form) it suffices to check that for any and some fresh (so ) it is the case that ([@). This is by part 3 of Theorem 3.19.
(Theorem 8.20 is slightly more general than a similar result in the literature [38, Lemma 6.3] in the sense that here we consider the more general case where and are not necessarily equivariant.)
9. Categories arising from U
from Definition 2.4 gives rise to some interesting concrete categories, which we now explore.
The categorical work on names and binding in nominal style has used concrete categories (essentially, the three categories considered below). It remains to develop abstract characterisations in category-theoretic language—that is, using diagrams and universal properties—of the properties of nominal techniques which make it useful. Work in this direction has been carried out first by Menni [51], and recently by Clouston and Pitts [13].
9.1. Three categories: ZFASet, FMSet, and NOMSet
We now set about constructing FMSet and NOMSet.
Call an element equivariant when supp(.
For example, is not equivariant and is equivariant.
Let and be equivariant sets. Let be a function-set. Then
is equivariant if and only if ((() for all and all permutations .
We obtain two categories from in addition to ZFASet:
The category FMSet of FM (Fraenkel-Mostowski) sets, with objects sets with finite support to level 1 (Definition 8.1), and with arrows finitely-supported function-sets between them (elements from Definition 8.5).
The category NOMSet of nominal sets, with objects equivariant (Definition 9.3) sets with finite support to level 1, and with arrows equivariant function-sets between them.
If we write : FMSet this means: “ and are elements of with finite support to level 1, and is a function-set from to with finite support; that is, ”.
If we write : NOMSet this means something something a little different: “ and are equivariant elements of with finite support to level 1, and is an equivariant function-set from to ”. 3
Let , , and be sets with finite support (to level 0). Then
where and its inverse, which we write , are given by
The bijection restricts to equivariant elements of () and ().
If and are equivariant then so is .
By Theorem 4.7.
The categories FMSet and NOMSet are cartesian closed.
Let be a set with finite support. There is a bijection between finitely-supported subsets of , and .
The maps are well-known:
corresponds with ( and
corresponds with ( 1) ( 0) . ( is the graph of if then 1 else 0.)
It is easy to show that these maps are inverse, and they map finitely-supported elements with finitely-supported elements by Theorem 4.7.
The categories FMSet and NOMSet are boolean toposes.
9.2. Presheaf presentation of NOMSet the category of nominal sets
Let be the category whose objects are finite sets of atoms and whose arrows are injective functions between them.
An important property of support is that if supports and supports then supports , as described in Theorem 2.21.
This means that if has a finite supporting set then it has a unique least finite supporting set. This key fact allows a compact presentation of a certain collection of presheaves, as sets. We do this in Theorem 9.14.
From the point of view of the presheaf presentation, the important point is that the presheaves should ‘preserve sets intersections’, or to re-frame this in categorical language, that they preserve pullbacks of monos. Every arrow in is mono, so this condition is not fully visible in Theorem 9.14.
In [32], we consider presheaves that preserve pullbacks of monos over an indexing category not all of whose arrows are monos, and we use a ‘preserves pullbacks of monos’ condition to develop a sets-based presentation of the resulting category that is not dissimilar to NOMSet the category of nominal sets. Contrast this with work using presheaves that do not necessarily preserve of pullbacks of monos [20, 19]. 3
NOMSet is equivalent with the category of pullback-preserving functors in FMSet (pullback-preserving presheaves on , to the category of FM sets).
On objects, maps are given by:
NOMSet maps to the presheaf () such that
where is any permutation such that (() for all .
FMSet maps to
where is the least equivalence relation on pairs (()) where () such that (())(()) if there is an injection : such that ()().
Consider a FMSet that preserves pullbacks. It follows that preserves monos and that if and then () is isomorphic with () (). Therefore, for every (()) there is a unique least and () such that (()(()).
Using this way of choosing representative elements, it is routine to establish equivalences between and (), and between () and .
It can be shown that the category of pullback-preserving presheaves is equivalent with the Schanuel Topos, see [47, Section III.9] or [44, A.21, page 79].
9.3. From NOMSet to the category of nominal sets, and back
The notion of a nominal set was introduced in [37, Section 3], where it was called ‘FM-sets’; it appeared in the journal version of the same paper [38] as ‘()-sets with the finite support property’, and also featured in [59, 24].
A nominal set is a pair () of a set with a finitely-supported -group action, where:
A -group action is a function
such that
Finite support means there is some finite set of atoms such that if and ( for every , then , that is, has finite supporting set in the sense of Definition 2.16.
We call an element of .
Suppose that are nominal sets. Call a function
equivariant when
for all .
(Definition 9.16 is in harmony with Definition 9.3; see Lemma 9.4.)
Let NOM be the category of nominal sets and equivariant functions between them.
We need a subsidiary definition and two lemmas for Theorem 9.21:
Suppose . Define the transitive closure tc() by:
tc(.
tc(tc() for .
For each set make a fixed but arbitrary choice of equivariant element fresh() such that fresh() tc(). Also choose a fixed but arbitrary bijective map from atoms to the natural numbers .
Define an operation () (for deatom) inductively as follows:
(()) for .
(() for .
Intuitively, () replaces each atom with the pair (()) throughout .
Provided tc(), the map () bijects with ().
By a routine calculation.
Suppose is equivariant. Then so is ().
By a routine inductive argument using Theorem 2.29.
NOM is categorically equivalent with NOMSet (Definition 9.5).
The maps of the equivalence are given by:
An equivariant in NOMSet maps to () where . An equivariant function NOMSet maps to (().
An object NOM maps to ( ()) where fresh() and
An arrow : NOM maps to () which maps
The proof is easy. We sketch it below. d ensures that atoms in do not interact ‘by accident’ with the permutation action when they are viewed as elements in .18
() is well-defined. That is,
Suppose . We use equivariance of to derive
The result follows.
() . We biject with [(id ())] using Lemma 9.19. We check this bijection is equivariant:
() . We biject [( ())] with using Lemma 9.19.
NOM and NOMSet are not quite the same thing, because NOMSet comes equipped with rank induction inherited from . 3
9.4. Functors and non-functors on FMSet and NOMSet
[]- from Definition 8.2 can be viewed as a functor on FMSet. Definition 8.2 gives the action on objects, it remains to specify the action on arrows:
[] is well-defined by Theorem 3.11 and Lemma 3.17. By Theorem 4.7 it is finitely-supported, and it is in [] [] .
If FMSet define
If : FMSet define
By Theorem 4.7 #(()) and it follows that : . It is not hard to verify that - is a functor.
- is right-adjoint to []- as an endofunctor on FMSet.
We state the unit, counit, and the correspondence between arrows:
The unit : ([]) FMSet is given by
The counit : []() is given by
: [] corresponds with ([]) : .
: corresponds with []fr @) : [] .
Let and be finitely-supported sets to level 1 (Definition 8.1). Define
is an endofunctor on NOMSet on both its arguments; we consider only the first:
If : NOMSet define
By Theorem 4.7 supp(()) supp() so (()) . It is easy to check that this defines a functorial action from NOMSet to itself.
- is not functorial on FMSet because supp()supp( does not imply supp(())supp(. This is unlike the case for NOMSet, because in FMSet we do not assume that supp(. 3
- is left-adjoint to []- as an endofunctor on NOMSet.
We state the unit, counit, and the correspondence between arrows:
The unit : []() is given by
The counit : ([]) is given by
: corresponds with fr []().
: [] corresponds with ()[]().
- from Definition 8.8 is not an endofunctor on FMSet or NOMSet for the following reasons:
FMSet. Suppose : FMSet and and #. It does not follow that #().
NOMSet. Suppose NOMSet. # is false in general, so is not in general an object in NOMSet.
- can be viewed as a functor from NOMSet to FMSet. If : NOMSet define (). By Theorem 4.7 #(). More on this in Subsection 9.5. 3
An easy corollary of Theorem 8.14 is that the full subcategory of FMSet on elements of the form ([]), is categorically equivalent to FMSet itself. The relevant maps are given in Theorem 8.14: abstraction []- : ([]), and concretion -@ : ([]). In words: atoms-abstraction is inverse to (fresh) atoms-concretion. 3
9.5. ‘Fresh for’ and ‘fresh for all elements of’ are distinct, but isomorphic
Suppose is a set in . Consider the notions ‘fresh for’ versus ‘fresh for all elements of’. In symbols, consider the predicates
If is finite then ‘fresh for’ and ‘fresh for all elements of’ coincide (this is a corollary of Theorem 2.29).
A characteristic feature of nominal techniques is that if is infinite then the two notions part company, and no particular implication connects them in general. For example:
# but it is not the case that # for every (take ), and
it is not the case that # but it is the case that # for every .
(This expands on the discussion in Remark 2.17; see also Lemma 8.9.)
So just because # does not mean that is fresh for every element in , and conversely, just because # for every does not mean that is fresh for overall.
However, with the mathematics now available to us we can state and prove a different, but still very close, relation between these two notions.
In Definition 9.33 we will define two categories; FMSet#a and . They both implement notions of ‘exclude ’:
In FMSet#a, is excluded in the sense of ‘fresh for all the elements of’.
In , is excluded in the sense of ‘fresh for’.
In Theorem 9.42 we will then prove that FMSet#a and are isomorphic. In this precise sense, being ‘fresh for’ and being ‘fresh for all elements of’ are reunited, modulo a natural isomorphism of categories.
For the rest of this subsection fix an atom .
Define a category FMSet#a by:
– Objects are elements of FMSet such that #.
– Arrows are arrows : FMSet.
Define a category by:
– Objects are elements of FMSet such that #.
– Arrows are arrows : FMSet such that #.
We read as restrict in (some reason for this choice of terminology is indicated in Lemma 9.36).
Definition 9.34 is clearly related to Definition 3.1. We can make this formal:
Suppose is an object in FMSet. Then .
Suppose is an object in FMset.
1. supp() supp().
2. It is not true in general that supp( supp().
3. # if and only if .
1. It is easy to check that if fix(supp()) then . The result follows by Theorem 2.21.
2. It suffices to provide a counterexample. Choose any and take ) () (Definition 2.7). It is easy to check that .
3. Suppose #. Suppose fix(supp()) and . By Theorems 4.4 and 2.21, . It follows easily that . Conversely, if then by part 1 of this result #.
1. Suppose is an object in . Then (.
2. Suppose is an object in FMSet#a. Then ().
For the first part, we prove two set inclusions:
Proof that (). Suppose . Choose some fresh (so #). By Theorem 2.21 () and furthermore by Theorem 2.19 (). It follows from Definition 9.34 that ().
Proof that () . Suppose (). So for some fix(supp()) and some . By Theorem 4.7 supp() supp(). Therefore fix(supp()). Now , so by Theorem 2.21 .
For the second part, again we prove two set inclusions:
Proof that (). Suppose (so #). Then and it is immediate that ().
Proof that (). Suppose (). So for some fix(supp()) and some (so #). Now choose some entirely fresh (so #) and write )(). It is a fact that fix(supp()), so by Theorem 2.21 . Since #, it is also a fact that . By Theorem 2.21 . It follows that , and by Theorem 2.19 it also follows that #.
We read as restrict in .
If : FMSet#a then is well-defined and : .
Furthermore, supp() supp().
First, we review what has to be proved. Suppose . Choose some fresh (so #). By Theorem 6.5 ( form), to calculate it suffices to calculate ()(()), and this must be well-defined. If so, then Definition 6.8 requires us to check that #()(()). We must also check that supp() is finite, and #; there is no need for a separate proof of this, since it is subsumed by a proof that supp() supp().
We sketch each part of the proof in turn:
()(()) well-defined. It follows by Theorem 2.19 that #(). What is slightly non-trivial here is to prove that if then (). Since and FMSet#a, there exists some fix(supp()) and some such that and #. We reason as follows:
It is a fact that (()()) fix(supp()) and it follows by Theorems 4.4 and 2.21 that ().
#()(()). Using Theorem 2.19.
#()(()) . It is a fact that (()) . The result follows by the definition of .
We now prove that supp() supp(). By Theorem 4.7 supp() supp(). By Theorems 6.2 and 6.5 ( form) it then suffices to check that ()( for some fresh (so #). Choose some and some fresh . We reason as follows:
Recall from Definition 8.8 that if : then is defined by ().
If : then : FMSet#a.
Suppose : . In particular, #. It follows using Theorem 4.7 that : .
The following data specifies a pair of functors between and :
- : FMSet#a maps to and : to : .
- : FMSet# maps to and : to : .
By routine calculations.
- and - define an isomorphism of categories between FMSet#a and .
That the functors are inverse on objects follows quickly from Lemma 9.37.
We check that these functors are inverse on arrows. Suppose : . So and # . We must check that (. Take any and choose some entirely fresh . We reason as follows:
Suppose : FMSet#a. So . We must check that (). Take any and choose some entirely fresh . We reason as follows:
10. Two set theories: ZFA and FM
Having considered the categories relevant to nominal techniques in Section 9, we now consider the relevant axiomatic set theories. These are Fraenkel-Mostowski set theory (FM) and Zermelo-Fraenkel set theory with atoms (ZFA). FM and ZFA are logical theories (sets of axioms) in first-order logic, in a signature with
one constant symbol and
two binary atomic predicate symbols (equality) and (set membership).
Fraenkel-Mostowski set theory was originally created to prove the independence of the axiom of choice from the other axioms of set theory [7]. It was rediscovered and applied by the author and Pitts to the problem of syntax-with-binding [24, 38].
Unfortunately, in [38, Section 1] we gave the impression that a change of foundations is necessary to carry out nominal techniques. This is not so. It is useful to work in ZFA rather than Zermelo-Fraenkel set theory (without atoms), because this gives us equivariance. It is not necessary to insist, as FM does, that all elements have finite support. Thus, the body of this paper has been conducted in the cumulative hierarchy model , and this admits elements without finite support (Remark 2.18).
10.1. Axioms of the two theories
is the only binder; we identify formulae up to -equivalence as is standard.
We will write:
Symbols bind in the following precedence, with the leftmost binding tightest:
associates to the right. The scope of and extends as far to the right as possible.
A theory is a set of formulas, which we call axioms.
The axioms of Fraenkel-Mostowski set theory are listed in Figure 2. The axioms of Zermelo-Fraenkel set theory are as for Fraenkel-Mostowski set theory but without (AtmInf) and without (Fresh).
In Figure 2 we use the following shorthand:
The permutation action is as in Definition 2.14. The notion of support is as in Definition 2.16. The -quantifier is as in Definition 6.1. Permutation, support, and can all be formalised in the language of FM. The in the axiom (Replacement) denotes a function definable in the language of FM, possibly with parameters, in the usual way. 3
10.2. Relative consistency of FM with respect to ZFA
Recall from Definition 10.3 the definitions of ZFA and FM. By Gödel’s incompleteness we cannot prove ‘FM is consistent’. We can prove a relative consistency result: if ZFA has a model, then so does FM.
Consistency of ZFA relative to Zermelo-Fraenkel set theory is well-known; see for example [41, Problem 1, Chapter 4].
We constructed a model of ZFA in Definition 2.4.19
Let the hereditarily finitely supported sets be inductively defined by:
If is finitely supported and , then is hereditarily finitely supported.
For example and if then (because and are finitely supported, and so are all their elements, of which they have none). Also, (the set of all atoms) is in . The set comb (Remark 2.18) is not in because it is not finitely supported.
Define (fs for finitely supported) by:
( is finitely supported
Suppose that . Then:
1. (.
2. () .
Suppose that .
1. Suppose (). By construction has finite support. Also, if then and so . Therefore . Conversely, if then has finite support. The equality follows.
2. so has finite support. By Theorem 4.7 also () has finite support. We have just shown that all () are in . It follows that () .
is a model of FM.
We observed that . We interpret the term-language of FM in the class in the natural way. It remains to show that validates the axioms in Figure 2. This is by a routine verification using Theorem 4.7 and Lemma 10.8. For more details see [24, Subsection 11.5] for the full proof, or [41, Chapter 4] for a more general result of which this lemma is an instance.
FM is consistent with respect to ZFA.
10.3. Fraenkel-Mostowski set theory and choice
10.3.1. The axiom of choice
Given an element write The axiom of choice is
Intuitively, is a function-set (Definition 2.10) that picks out an element from , for every .
The original application of FM was to prove the independence of (AC) from the other axioms of ZFA [22]. Four decades later Cohen proved AC was independent from set theory without atoms (ZF), via his forcing method [14]. Also see [41] for a survey.
(AC) is inconsistent with FM.
Let be the set of sets of unordered pairs of distinct atoms. Suppose there exists a choice function for .
By (Fresh) the choice function has finite support. Choose #. By Theorems 4.4 and 2.21, () is fixed by (). However, neither nor is fixed by (), so cannot be a choice function; a contradiction.
Therefore does not exist.
In spite of Theorem 10.11, nominal techniques are consistent with the axiom of choice.
In Definition 2.4 we constructed , the standard cumulative hierarchy model of ZFA. ZFA is consistent with the axiom of choice. We insist on finite support when we need it; what Theorem 10.11 uses is the fact that a choice function for a finitely-supported set, need not itself be finitely-supported.
There is no overall inconsistency here—just, as is so often the case, some constructions which make sense when applied to elements with the right properties, and may not make sense otherwise. (One cannot reasonably argue, for example, that addition is inconsistent with the existence of elements that are not numbers.)
FM may be convenient in situations where everything we wish to consider will have finite support. (Just as, for example, arithmetic is convenient in situations where we happen to know that we wish to consider numbers.) 3
10.3.2. Hilbert’s choice
Careful formulations of the definition of capture-avoiding substitution may use a choice function for picking out fresh variables; an example is [63, Section 2]. If we work in Fraenkel-Mostowski set theory then we should not do this; see Theorem 10.13. As we have seen, the use of atoms as a primitive concept, and the -quantifier and ‘fresh’ are well-suited to replace for this task, and indeed they bring benefits exemplified by equivariance (Theorem 4.4) support (Theorems 2.21 and 4.7) and the some/any property (Theorem 6.5).
We can still use when we want the full power of choice, but this takes us into Zermelo-Fraenkel set theory with atoms.
It is inconsistent to extend the language and axioms of FM with Hilbert’s choice.
That is, we extend the term-language with a binder (), extend existing axiom-schemes to include the resulting new terms and predicates, and add a new schema of axioms
By an easy adaptation of the proof of Theorem 10.11.
10.3.3. Unique choice
Unique choice is not a problem:
Suppose that () is a formula on and a list of variables . As is standard, write !() for
Read this as ‘there is a unique such that ()’.
It is consistent to extend the language and axioms of FM with unique choice (or definite description).
That is, we extend the term-language with a binder (), extend existing axiom-schemes to include the resulting new terms and predicates, and add a new schema of axioms
Take some model of FM. Suppose () is a formula and suppose some values for . There are two cases:
If !() is false then interpret () by .
If !() is true then interpret () as the unique element making () true.
With this interpretation, !() (()) is always true.
11. Extensions of the semantics
In this paper we have marked out a certain body of work, spanning eight years of research. This is, however, not the whole story. In this section we indicate, in broad strokes, answers to three questions which are often asked of nominal techniques:
1. What about infinitary syntax, and what about atoms-abstraction over several (or infinitely many) atoms at a time?
2. Can we base a theory of names on renamings (not necessarily bijective maps on atoms), rather than on permutations, and if so, what does it look like?
3. What about substitution?
11.1. Infinitely many names
We investigate the quantifier and the model of name-abstraction in Subsections 6.1 and 3.2 on a general assumption of finite support. However, infinitary syntax may generate elements that do not have finite support; for example an infinite tuple of distinct atoms () does not have finite support.
The central question is: what sense of ‘small’ should replace the word ‘finite’ in ‘finite supporting set of atoms’ used in this paper?
One obvious answer is to replace ‘finite’ with ‘countable’ (and to take the set of all atoms to be uncountable).
Another answer is to replace ‘finite’ with a notion of support ideal introduced by Cheney [11]. A support ideal is a set of sets of atoms that does not contain , is closed under sets unions, is down-closed with respect to subset inclusion, and contains all the finite sets of atoms. That is, a support ideal is such that every is a subset and furthermore:
.
If and then .
If and then .
If is finite then .
Support ideals distil in axiomatic form those properties of finite sets of atoms that are actually needed when we construct atoms-abstraction and nominal abstract syntax; a support ideal has enough of the behaviour of the set of finite sets of atoms that ‘nominal’ constructions can still be carried out.
Another answer, developed in [25] and then in [27], is to replace ‘finite’ with ‘well-orderable’. That is, we identify the essential and useful quality of a ‘finite’ set of atoms, with being well-orderable. In particular, this allow us also to generalise atoms-abstraction and permutation to infinitely many atoms. We use well-orderings to build permutations to rename well-orderable sets of atoms (we might do this because, for example, we are proving a generalised version of Theorem 2.21 and we want to rename infinitely many atoms to be fresh). See [27] for details.
11.2. Permutations vs. renamings and function-spaces
Recall from Definition 9.12 that we write for the category of finite sets of atoms and injections between them. Write Set for the category of all sets and functions between them. Write also for the category of finite sets and all (not necessarily injective) functions between them.
Higher-order abstract syntax (HOAS) [56] uses functions to represent syntactic abstraction using types, in particular the so-called weak HOAS (as exemplified for example in [16]) uses types like
These require semantic or proof-theoretic justifications.
In this paper we have discussed the category NOM of nominal sets. From Theorem 9.14 and Theorem 9.21 it follows that this can be presented as the category of pullback-preserving presheaves in FMSet.20 Fiore et al [20] and Hofmann [39] proposed to use Set as a semantic foundation 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 with the exponential . In the category NOM of nominal sets the corresponding presheaf is isomorphic with our construction [], with []- being the right adjoint to a tensor product different from cartesian product (see Theorem 9.30). In either case is given as a presheaf by (. Thus, Set seems better-suited for modelling higher-order abstract syntax and its typings lam : ( tm) tm 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 [16, 40].
In [32] we propose 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 finitely-supported not-necessarily-injective functions on atoms (we call it a renaming action). This is to be contrasted with the work in this paper, which is based on finitely-supported injective functions on atoms (permutations).
The pullback requirement implies that () is isomorphic with ‘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.
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.
(Staton and Fiore [21] define a category of substitution sets equivalent with a sheaf subcategory of Set. Their category is not defined concretely in terms of ordinary sets and it does not make Set easier to work with.)
11.3. Substitution on the sets hierarchy
Given an inductive datatype we may define a substitution action on it. Of what general mathematical entity are these substitution actions instances?
Two related answers are given in [34, 20]. These study abstract notions of substitution algebra as an algebraic structure (parameterised over a signature) independently of an inductively-defined carrier set; [34] uses nominal algebra to do this (a purpose-built logic for expressing axioms with binding introduced in Mathijssen’s thesis [49], with a semantics in nominal sets), whereas [20] expresses its axiomatisation as a diagram-scheme, parameterised over binding signatures, of diagrams in Set.
In [31] we take a direct approach which exists at the level of the cumulative hierarchy itself. We define a substitution action directly on the powerset constructor, that is, we show how given any finitely-supported set , atom , and element , we can define a set [] which means in some sensible way ‘ with replaced by ’.
We now briefly sketch why this is non-trivial in terms of our cumulative hierarchy .
We want our new substitution to coincide with ‘usual’ substitution on elements representing syntax (i.e. representing labelled trees). Atoms model variable symbols, therefore we let
Recall from Subsections 3.1 and 3.2 that the atoms-abstraction is formed by taking an -equivalence class of ‘renamed variants’ of a set. For example the abstraction of the atom in the ordered pair (), written []() (Definition 3.8) is
Also consider the -abstraction of in the ordered 3-tuple (): []() (here () is ( ())):
Note that
because does not ‘clash’ with () but it does ‘clash’ with ().
We want substitution to distribute over abstraction in a capture-avoiding way. That is, we want
We cannot obtain this by operating pointwise on the elements of [](), i.e. by letting
always, for in that case, we would not know not to put into ([]())[()] the element ( ())[( ()). Substitution must detect -equivalence classes and adjust for them by adding or removing elements.
This is the major difficulty of defining substitution on powersets.
Not all sets look like the tame examples we selected above. Elements may be (amongst many other things) unions of abstractions
or equivalence classes which represent simultaneous abstraction by more than one atom
— we can think of this as ‘abstract and simultaneously (in no particular order) in ’. If we apply [()] to this we want to ‘avoid name-clash’ with and , and ‘-convert ’, and ‘fill in renamed variants mentioning ’, to obtain the element
which we can think of as ‘abstract and simultaneously in ()’.
We note the same issue with interaction with equivalence classes; () is not in this set, so substitution cannot be defined in a purely pointwise manner.
Our strategy for defining substitution as an action purely on sets of elements is as follows:
Given a set , identify as a union of some generalised notion of -equivalence classes . Now carry out substitution on the individual classes, then put the results together again using sets union.
We can put it another way:
Substitution acts pointwise on (generalised) -equivalence classes of elements.
Our generalisation of -equivalence classes is from Subsection 3.1.
The set above is which is the equivalence class of all renamed variants of under permutations of atoms fixing (i.e. ‘-abstract and in ). If we apply [()] to this then we obtain (). Note that this is the same set as () and ()—it is part of our model of -equivalence on FM that we can ‘-rename abstracted atoms’ freely.
Given these ideas, it remains only to decide how substitution interacts with the generalised -equivalence classes. Full details are in [31, 29].
References
[1] Ordinal numbers (Wikipedia), 23 September 2008, en.wikipedia.org/wiki/Ordinal number.
[2] 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, Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), IEEE Computer Society Press, 2004, pp. 150–159.
[3] Brian Aydemir, Aaron Bohannon, and Stephanie Weirich, Nominal reasoning techniques in Coq, Electronic Notes in Theoretical Computer Science 174 (2007), no. 5, 69–77.
[4] Henk P. Barendregt, The lambda calculus: its syntax and semantics (revised ed.), North-Holland, 1984.
[5] Stefan Berghofer and Christian Urban, A head-to-head comparison of de Bruijn indices and names, Electronic Notes in Theoretical Computer Science 174 (2007), no. 5, 53–67.
[6] Nicolas Bourbaki, Théorie des ensembles, Hermann, Paris, 1970.
[7] Norbert Brunner, 75 years of independence proofs by Fraenkel-Mostowski permutation models, Mathematica Japonica 43 (1996), 177–199.
[8] Luís Caires and Luca Cardelli, A spatial logic for concurrency (part II), Theoretical Computer Science 322 (2004), no. 3, 517–565.
[9] Georg Cantor, Beiträge zur Begründung der transfiniten Mengenlehre II, Mathematische Annalen 2 (1897), no. 49, 481–512.
[10] James Cheney, A simpler proof theory for nominal logic, FoSSaCS, Lecture Notes in Computer Science, vol. 3441, Springer, 2005, pp. 379–394.
[11], Completeness and Herbrand theorems for nominal logic, Journal of Symbolic Logic 71 (2006), 299–320.
[12] James Cheney and Christian Urban, System description: Alpha-Prolog, a fresh approach to logic programming modulo alpha-equivalence, Tech. Report DSIC-II/12/03, Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, 2003.
[13] Ranald Clouston, Equational logic for names and binding, Ph.D. thesis, University of Cambridge, UK, 2010, Pending graduation.
[14] Paul J. Cohen, The independence of the continuum hypothesis, Proceedings of the National Academy of Sciences of the United States of America (PNAS) 50 (1963), no. 6, 1143–1148.
[15] Nicolaas G. de Bruijn, Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem, Indagationes Mathematicae 5 (1972), no. 34, 381–392.
[16] Joëlle Despeyroux and André Hirschowitz, Higher-order abstract syntax with induction in COQ, LPAR’94, Lecture Notes in Computer Science, vol. 822, Springer, 1994, pp. 159–173.
[17] Gilles Dowek and Murdoch J. Gabbay, Permissive Nominal Logic, Principles and Practice of Declarative Programming, 12th International ACM SIGPLAN Symposium (PPDP 2010), 2010.
[18] Heinz-Dieter Ebbinghaus, Jörg Flum, and Wolfgang Thomas, Mathematical logic, second ed., Springer, 1994.
[19] Marcelo Fiore and Daniele Turi, Semantics of name and value passing, Proceedings of the 16th IEEE Symposium on Logic in Computer Science (LICS 2001), IEEE Computer Society Press, 2001, pp. 93–104.
[20] Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi, Abstract syntax and variable binding, Proceedings of the 14th IEEE Symposium on Logic in Computer Science (LICS 1999), IEEE Computer Society Press, 1999, pp. 193–202.
[21] Marcelo P. Fiore and Sam Staton, A congruence rule format for name-passing process calculi from mathematical structural operational semantics, Proceedings of the 21st IEEE Symposium on Logic in Computer Science (LICS 2006), IEEE Computer Society Press, 2006, pp. 49–58.
[22] Abraham Fraenkel, Der Begriff “definit” und die Unabhngigkeit des Auswahlsaxioms, Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse (1922), 253–257, Reprinted in English translation in “From Frege to Godel: A source book in mathematical logic 1879 - 1931”, Harvard University Press, second edition, 1971.
[23] Dov Gabbay, Elementary logics: A procedural perspective, Prentice Hall, 1998.
[24] Murdoch J. Gabbay, A Theory of Inductive Definitions with alpha-Equivalence, Ph.D. thesis, University of Cambridge, UK, 2000.
[25], FM-HOL, a higher-order theory of names, 35 Years of Automath (F. Kamareddine, ed.), 2002.
[26], Fresh Logic, Journal of Applied Logic 5 (2007), no. 2, 356–387.
[27], A General Mathematics of Names, Information and Computation 205 (2007), no. 7, 982–1011.
[28], Nominal Algebra and the HSP Theorem, Journal of Logic and Computation 19 (2009), no. 2, 341–367.
[29], A study of substitution, using nominal techniques and Fraenkel-Mostowski sets, Theoretical Computer Science 410 (2009), no. 12-13, 1159–1189.
[30] Murdoch J. Gabbay and James Cheney, A Sequent Calculus for Nominal Logic, Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), IEEE Computer Society, 2004, pp. 139–148.
[31] Murdoch J. Gabbay and Michael Gabbay, Substitution for Fraenkel-Mostowski foundations, Proceedings of the 2008 AISB Symposium on Computing and Philosophy, 2008, pp. 65–72.
[32] Murdoch J. Gabbay and Martin Hofmann, Nominal renaming sets, Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), Springer, 2008, pp. 158–173.
[33] Murdoch J. Gabbay and Stéphane Lengrand, The lambda-context calculus, Electronic Notes in Theoretical Computer Science 196 (2008), 19–35.
[34] Murdoch J. Gabbay and Aad Mathijssen, Capture-Avoiding Substitution as a Nominal Algebra, Formal Aspects of Computing 20 (2008), no. 4-5, 451–479.
[35], One-and-a-halfth-order Logic, Journal of Logic and Computation 18 (2008), no. 4, 521– 562.
[36] Murdoch J. Gabbay and Dominic P. Mulligan, One-and-a-halfth Order Terms: Curry-Howard for Incomplete Derivations, Proceedings of 15th Workshop on Logic, Language and Information in Computation (WoLLIC 2008), Lecture Notes in Artificial Intelligence, vol. 5110, 2008, pp. 180–194.
[37] Murdoch J. Gabbay and Andrew M. Pitts, A New Approach to Abstract Syntax Involving Binders, 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, 1999, pp. 214–224.
[38], A New Approach to Abstract Syntax with Variable Binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.
[39] Martin Hofmann, Semantical analysis of higher-order abstract syntax, Proceedings of the 14th Annual Symposium on Logic in Computer Science (LICS 1999), IEEE Computer Society Press, 1999, pp. 204–213.
[40] Furio Honsell, Marino Miculan, and Ivan Scagnetto, An axiomatic approach to metareasoning on nominal algebras in HOAS, Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001), vol. 2076, Lecture Notes in Computer Science, 2001, pp. 963–978.
[41] Thomas Jech, The axiom of choice, North-Holland, 1973.
[42], Set theory, Springer, 2006, Third edition.
[43] Peter T. Johnstone, Notes on logic and set theory, Cambridge University Press, 1987.
[44], Sketches of an elephant: A topos theory compendium, Oxford Logic Guides, vol. 43 and 44, OUP, 2003.
[45] Edward Keenan and Dag Westerståhl, Generalized quantifiers in linguistics and logic, Handbook of Logic and Language (J. Van Benthem and A. Ter Meulen, eds.), Elsevier, 1996, pp. 837–894.
[46] Jean Louis Krivine and Rene Cori, Lambda-calculus, types and models, Ellis Horwood, 1993, Translated by Rene Cori.
[47] Saunders Mac Lane and Ieke Moerdijk, Sheaves in geometry and logic: A first introduction to topos theory, Universitext, Springer, 1992.
[48] Michael Makkai, Avoiding the axiom of choice in general category theory, Journal of Pure and Applied Algebra 108 (1996), no. 2, 109–173.
[49] Aad Mathijssen, Logical calculi for reasoning with binding, Ph.D. thesis, Technische Universiteit Eindhoven, 2007.
[50] James McKinna and Randy Pollack, Pure Type Systems formalized, Proceedings of the International Conference on Typed Lambda Calculi and Applications (TLCA 1993), LNCS, no. 664, Springer-Verlag, March 1993, pp. 289–305.
[51] Matias Menni, About -quantifiers, Applied Categorical Structures 11 (2003), no. 5, 421–445.
[52] Dale Miller and Alwen Tiu, A proof theory for generic judgments (extended abstract), Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), IEEE Computer Society Press, 2003, pp. 118–127.
[53] Andrzej Mostowski, Über die Unabhängigkeit des Wohlordnungssatzes vom Ordnungsprinzip, Fundamenta Mathematicae 32 (1939), 201–252.
[54], On the independence of the well-ordering theorem from the ordering principle, Foundational Studies (volume 1), Studies in logic and the foundations of mathematics, vol. 93, North-Holland, 1979, pp. 290–338.
[55] Dominic P. Mulligan, Online nominal bibliography, www.citeulike.org/group/11951/, 2010.
[56] Frank Pfenning and Conal Elliott, Higher-order abstract syntax, PLDI (Programming Language Design and Implementation), ACM Press, 1988, pp. 199–208.
[57] Andrew M. Pitts, Nominal logic, a first order theory of names and binding, Information and Computation 186 (2003), no. 2, 165–193.
[58], Alpha-structural recursion and induction, Journal of the ACM 53 (2006), no. 3, 459–506.
[59] Andrew M. Pitts and Murdoch J. Gabbay, A Metalanguage for Programming with Bound Names Modulo Renaming, MPC2000, Lecture Notes in Computer Science, vol. 1837, Springer, 2000, pp. 230–255.
[60] Mark R. Shinwell and Andrew M. Pitts, Fresh objective Caml user manual, Tech. Report UCAM-CL-TR-621, University of Cambridge, 2005.
[61], On a monadic semantics for freshness, Theoretical Computer Science 342 (2005), no. 1, 28–55.
[62] Mark R. Shinwell, Andrew M. Pitts, and Murdoch J. Gabbay, FreshML: Programming with Binders Made Simple, Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), vol. 38, ACM Press, 2003, pp. 263–274.
[63] Allen Stoughton, Substitution revisited, Theoretical Computer Science 59 (1988), no. 3, 317– 325.
[64] Alfred Tarski and Steven Givant, A formalization of set theory without variables, vol. 41, American Mathematical Society Colloquium Publications, 1987.
[65] Alwen Tiu, A logic for reasoning about generic judgments, Electronic Notes in Theoretical Computer Science 174 (2007), no. 5, 3–18.
[66] Christian Urban, Nominal reasoning techniques in Isabelle/HOL, Journal of Automatic Reasoning 40 (2008), no. 4, 327–356.
[67] Christian Urban, James Cheney, and Stefan Berghofer, Mechanising the metatheory of LF, Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LICS 2008), IEEE Computer Society Press, 2008, pp. 45–56.
[68] Christian Urban and Christine Tasson, Nominal techniques in Isabelle/HOL, CADE’05, Lecture Notes in Artificial Intelligence, vol. 3632, 2005, pp. 38–53.
[69] John von Neumann, Zur Einführung der transfiniten Zahlen, Acta Szeged (Sectio Math.) (1923), no. 1, 199–208, Reprinted in English translation in “From Frege to Godel: A source book in mathematical logic 1879 - 1931”, Harvard University Press, second edition, 1971.
[70] Dag Westerståhl, Quantifiers in formal and natural languages, Handbook of Philosophical Logic (Gabbay and Günthner, eds.), Synthèse, vol. 4, Reidel, 1989, pp. 1–131.
[71] Ernst Zermelo, Über Grenzzahlen und Mengenbereichebe, Fundamenta Mathematicae 16 (1930), 29–47.
Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.
Notes
1This is expressed compactly by a BNF definition as follows: . ↩
2Thanks to an anonymous referee for suggesting we do this. ↩
3We have in mind a referee who had one of our papers rejected on the grounds that ‘nominal techniques only have equivariant functions’ and that we had used in our paper a non-equivariant function. The referee had confused arrows in the category of nominal sets NOM (Definition 9.17) with functions in the underlying set of an exponential and more generally had confused the use of a particular category with an ontological commitment. This convinced us that something like Sections 9 and 10 is necessary. Any given paper may emphasise one particular presentation (set theory, cumulative hierarchy, sets category, presheafs . . . ) if only to keep within space limits. This may give the reader of that paper, unfamiliar with the broader context, a mistakenly impression that nominal techniques ‘are’ the category of nominal sets, or that they ‘are’ FM set theory, or whatever. ↩
4If is a set then . This is not the case of atoms. For example . ↩
5Using standard notation, we can write supp( a finite set of atoms supporting ↩
6In the original conference paper [37] # was read ‘ is apart from ’, but this terminology seems to be obsolete now. For example by the time we wrote the journal version [38] we were reading # as fresh for. ↩
7In [53, 54] it is shown by an argument based on constructing a model with a permutation action, that in ZF plus an axiom that every set can be linearly ordered, we cannot derive that every set can be well-ordered. ↩
8As is standard, ‘generated as a group’ means ‘every element can be made by finite combinations with group composition and group inverse, starting from the generators’. ↩
9This also follows from equivariance (Theorem 4.4), developed later: function-set application is equivariant so (()(). ↩
10There is some analogy here with anamorphisms [48], which can be thought of as functors annotated with extra information about choices of representative; analogously, we can write functions on an atoms-abstraction [] by writing functions on representatives (), which are annotated with extra information which is a ‘name’ for the bound atom. See Theorem 8.20. ↩
11There are no atoms-abstractions without finite support because in Definition 3.8 we only form [] when has finite support. ↩
12In fact, Λ is an element of , but we prove that in Lemma 5.7. First, we have to specify the extension of Λ—the elements it contains—and while we do this we call Λ a collection, as in ‘collection of elements’. ↩
13Note that this choice can be represented as an element in . Such a representation will not have finite support, but is allowed to contain elements that do not have finite support because it is the cumulative hierarchy model of Zermelo-Fraenkel set theory with atoms (not of Fraenkel-Mostowski set theory). See Section 10. ↩
14The proof theory of the quantifier was considered by the author [26] and in collaboration with Cheney [30], and then improved by Cheney [10]. Another view on is given in [17, Subsection 7.3]. ↩
15The formalisation is not entirely evident. We consider the set of all function-sets defined on initial segments of Λ and prove they must agree where they are defined. For more details see [43, Chapter 5], in particular Theorem 5.4. ↩
16We require the elements to have finite support so that [] makes sense. This condition might be relaxed at the expense of complicating the definition. Seeing as we will not use the extra generality we retain the stricter, easier condition on . ↩
17So we do not use the case of in Lemma 8.11, but we retain it for completeness. ↩
18For example, with trivial action always, is an object in NOM. However, the atoms in the underlying set are completely irrelevant to the desired permutation action. d removes them to prevent an ‘accidental capture’ by the permutation action in NOMSet, which would see them and permute them if we allowed it to. A design alternative would be to insist that tc() , i.e. that the underlying set of a nominal set be a ‘normal’ set, without atoms—or we could impose the slightly weaker condition of equivariance for all elements of . However, this would only push d over to mapping NOMSet to NOM. Our design seems a little more elegant. ↩
19If ZFA is inconsistent then does not exist. Thus, this is a relative consistency result. Yet if does not exist, then our ontological commitment to sets and powersets is wrong. In that case, how can we and the reader be doing mathematics at all? Such questions are outside the scope of our current enquiry. ↩
20We write FMSet and not Set so as to account for atoms. In fact we could take Set to be equal to FMSet, either by foundationally admitting that ‘atoms actually exist’, or alternatively by declaring ‘secretly, atoms were sets, for example, they were numbers all along’. The distinction between FMSet and Set is more a matter of taste than of mathematical substance but we maintain it, for consistency. ↩