Nominal renaming sets (technical report)
December 19, 2007
Abstract
Nominal techniques are based on the idea of sets with a finitely-supported atoms-permutation action.
In this paper we consider the idea of sets with a finitely-supported atoms-renaming action (renamings can identify atoms; permutations cannot). We show that these exhibit many of the useful qualities found in traditional nominal techniques; an elementary sets-based presentation, inductive datatypes of syntax up to binding, cartesian closure, and being a topos. Unlike in nominal techniques, the notion of names-abstraction coincides with functional abstraction.1
1 Introduction
It can be surprisingly difficult to find the right approach to handling variable symbols in abstract syntax. We need to do this in order to process sentences in formal languages, such as -calculus terms or logical predicates. Binders are particularly troublesome and they arise frequently: for example with -binding, -quantification, declarations of formal parameters in procedures, name-restriction as in the -calculus, and so on.
To deal with binders informally is usually not a problem (though sometimes significant errors are made). The difficulty is in handling binders in implementation, notably in program transformation systems and theorem provers.
My thesis [10] started the ‘nominal’ approach (supervised by Pitts). This is based on a structure called a nominal set. Nominal sets ([14] or Definition 4.3) are based on two ideas:
An underlying set with a permutation action, with
finite support.
Remarkably, the two ideas of ‘permutation action’ and ‘finite support’ suffice to build an account of names and binding in abstract syntax. That is, we can construct a set which is an inductive datatype of syntax-up-to-binding, and develop programming and reasoning principles on it.
In this paper we revisit these ideas and ask: how much of ‘nominal’ had to be that way, and how much of it depends on the choices which we happened to make at the time? During my thesis I suggested an alternative nominal approach2 based on:
An underlying set with a renaming action (Definition 2.8), with
finite support.
It turns out that
‘renaming action’ and ‘finite support’
is just as sufficent as
‘permutation action’ and ‘finite support’
to capture much of the flavour of nominal techniques.
In this paper we shall explore this idea and show how it is possible to build an account of names and binding very similar in spirit to that familiar in the nominal literature based on permutations — only using renamings.
A few words on notation.
We will call ‘nominal sets’ from the literature ([14, 10] or Definition 4.3) nominal permutation sets. This is to distinguish them from nominal renaming sets (Definition 2.8) introduced in this paper.
We will write function application both as and .
(‘ is not in the support of ’) and # (‘ is fresh for ’) have the same meaning (Remark 2.14).
2 Nominal renaming sets
2.1 Definitions and important results
We use standard sets notation; range over sets of elements and means ‘ is in ’. Note that means ‘, , are in ’. If and are sets then is the set of all functions from elements of to elements of . This arrow should not be confused with two other arrows which come later: (arrows in a category) and (exponentials).
Fix a countably infinite set of atoms 𝔸. We assume that atoms are disjoint from numbers 0 1 2, truth-values , and other standard mathematical entities.3 We let range over atoms.
We will adhere to a permutative convention that range permutatively over atoms, so for example and range over any two distinct atoms and always.
We adopt a permutative convention because one of the major uses of atoms is to model variable symbols in abstract syntax (see [14] or Theorem 6.11); it is a fact that ‘’ and ‘’ are two distinct variable symbols. Later a valuation might associate and to the same value, or a subtitution might substitute and for the same term. Then, we might write ‘’. However, we must not forget that this is a different kind of equality which arises only after the abstract syntax has been constructed and associated to a denotation.
The slogan in nominal techniques is:
Names exist.
Definition 2.1 makes that formal.
For comparison, techniques based on Higher-Order Abstract Syntax [23] (variable symbol are modelled by variables, which exist at the meta-level), and de Bruijn indexes [6] (variable symbols are numbered indexes, pointing to positions) do not give names concrete reality in the underlying sets. In the context of the current state of the art, Definition 2.1 is not taken for granted.
Let Fin be the set of functions 𝔸 𝔸 such that there exists some finite 𝔸 such that
for all 𝔸 it is the case that .
will range over elements of Fin. We call these (finitely supported) renamings.
Write [] for the function that maps to for 1 and maps all other (that is, atoms not in the set ) to themselves.
Write [] for the function such that
Call this an atomic renaming. Intuitively, [] ‘maps to ’.
Write for the function such that
Consistent with [14], call this a swapping. Intuitively, ‘swaps and ’.
We write for functional composition. For example [] [] (and [] [] []). Write id for the identity renaming. always.
Fin with and id is a monoid.
That is, id id and () . This follows by elementary properties of functional composition.
If 𝔸 and Fin, write for the partial function defined by
( if .
is undefined if 𝔸 .
Note that if Fin then
A nominal renaming set 𝕏 is a pair (
A finitely-supported renaming action is a function from Fin 𝕏 to such that:
id for all 𝕏.
() for all 𝕏 and Fin.
For every 𝕏 there exists some finite 𝔸 such that for all Fin if then . We say that every 𝕏 has finite support.
Some jargon: a nominal renaming set 𝕏 is a set with a finitely-supported Fin-monoid action.
supp() coincides with ‘the variables in’ if is abstract syntax; if the reader thinks of every time they see then they will not go too far wrong [14, Example 6.11]. However support is an abstract notion valid for any nominal renaming set. As we shall see, there are very many nominal renaming sets that are not built of abstract syntax.
2.2 The support of a nominal renaming set
Suppose that 𝕏 is a nominal renaming set and 𝕏. Say that 𝔸 supports when for all Fin, if then .
Lemma 2.12 and Theorem 2.13 echoes [14, Proposition 3.4] (definition of support for a nominal permutation set). The proofs for nominal renaming set are simpler:
Suppose that 𝕏 is a nominal renaming set and suppose that 𝕏. If 𝔸 supports and 𝔸 supports then supports .
Suppose that 𝔸 and 𝔸. Suppose that . Define Fin by
( if .
(() if 𝔸 .
so . Also it is not hard to verify that so . The result follows.
Suppose that 𝕏 is nominal renaming set and suppose 𝕏.
There exists a unique least set of atoms supporting , and that set is finite. Write it and call it the support of .
Suppose that Fin and Fin. Then if then .
By assumption there exist some finite 𝔸 supporting . The first part follows immediately using Lemma 2.12. The second part also follows immediately using Definition 2.11.
Consistent with other work we write # to mean supp and read this as ‘ is fresh for ’. We may also write # to mean ‘# and #’, and so on.
Let PFin be the nominal renaming set such that:
PFin is the collection of finite sets of atoms.
If 𝔸 is finite and Fin then
As is standard, we call this the pointwise renaming action.
It is not hard to prove that always. The following result generalises a known property of nominal permutation sets:
Recall the definition of from Definition 2.15. Suppose that 𝕏 is nominal renaming set and suppose 𝕏 and Fin. Then:
1. supp()
2. If is injective on that is, if
then
1. Suppose that ( for all supp Then ( ). By assumption () . By Theorem 2.13 () . The result follows.
2. By part 1 of this result supp() We need only prove the reverse inclusion; this is routine: Suppose that ]. By assumption if then for 1 . So we can write ]. By Theorem 2.13 . By part 1 of this result supp() But by construction, so we are done.
For a counterexample to converse of the inclusion in part 1 of Lemma 2.16, see Lemma 2.18.
2.3 Examples of nominal renaming sets
The set of atoms.
𝔸 with action is a nominal renaming set.
Above, we wrote 𝔸 for the set of atoms. We will not be pedantic enough to change notation now, so we write 𝔸 for both 𝔸 (the nominal renaming set) and 𝔸 (its underlying set). For all other nominal rewriting sets 𝕏 we will distinguish between 𝕏 and
Sets with a trivial renaming action.
The empty nominal renaming set 𝟘 ) and the unit nominal renaming set 𝟙 ) are nominal renaming sets; in both cases there is only one possible renaming action.
More generally, call a nominal renaming set 𝕏
Then 𝔹 ) and ℕ 0 1 2), both with the trivial renaming actions, are nominal renaming sets. always.
Finite and cofinite sets of atoms.
Recall the example of PFin (the set of finite sets of atoms, with pointwise renaming action) from Definition 2.15.
Call 𝔸 cofinite when 𝔸 is finite.
The set of cofinite subsets of 𝔸 is a nominal renaming set with action given by
is a nominal renaming set. It is not hard to verify that 𝔸 always.
For example, [] (𝔸 𝔸 Finally, the set of all finite or cofinite sets of atoms is a nominal renaming set with action obtained by combining the two actions just given, is a nominal renaming set. if is finite, and 𝔸 if is cofinite.
Examples of sets with renaming actions that are not nominal renaming sets.
The set of all subsets of 𝔸 is not a nominal renaming set. It has a pointwise renaming action given by , but this action is not finitely-supported.
For example if we write 𝔸 and let 1
— so is ‘every other atom’ — then has no finite supporting set. See also Lemma 2.20 below.
Exploding models.
The converse inclusion in part 1 of Lemma 2.16 need not hold. That is:
There exists a nominal renaming set 𝕏, 𝕏, and Fin such that supp()
It suffices to find an example. Consider specified by:
is the set of all finite subsets of 𝔸.
if has the same cardinality as (that is, if is injective as a function out of ).
otherwise (that is, if there exist and such that ()).
It is not hard to verify that this is a nominal renaming set, and .
Note that
and
I call this behaviour ‘exploding’ because, for example, ‘explodes’ like a balloon when ‘pricked’ by the non-injective function [].
Suppose 𝕏 is a nominal renaming set, suppose Fin, and suppose 𝕏. If is injective on then its action is invertible in the sense that if we are given and then we can uniquely deduce what must have been (the construction is in the proof of part 2 of Lemma 2.16).
Nominal permutative techniques [14] only admit permutations, and their action is always invertible, so this is the only situation considered so far in the literature on nominal techniques.
If Fin is not injective on then its action need not be invertible. For example acts pointwise on finite 𝔸 (Definition 2.15) and
So given and [], there is no unique finite 𝔸 such that []
The point which exploding models make is that the action on the underlying set of a nominal renaming set might be far more non-invertible than we expect, if our intuitions are based only on the behaviour of renamings acting on abstract syntax.
(Possibly infinite) tuples.
Let be a (possibly infinite) indexing set. Let for be an -indexed collection of nominal renaming sets. Write or just for a -tuple of elements . For example is an ordered pair. (the set of all -tuples of elements from ) inherits a pointwise renaming action given by ).
1. need not have finite support in general.
2. has finite support if and only if there exists some finite 𝔸 such that for all .
1. Let 𝔸 and consider the tuple () — the tuple of all atoms, in some order. It is not hard to prove that this has no finite supporting set.
2. Suppose that 𝔸 is finite and supports (). Suppose that ; we show that supports . If id then (). By definition ), so . It follows that supports . Now suppose that 𝔸 is finite and supports for every . By a similar calculation it is easy to verify that supports
Using notation and terminology from Definition 2.19 and Lemma 2.20 we define:
Let be a (possibly infinite) indexing set. Let for be a -indexed collection of nominal renaming sets. Then let be the nominal renaming set with:
is those with finite support. That is, for each and there exists some finite 𝔸 such that for all it is the case that .
Pointwise renaming action. That is, ).
2.4 Renaming action vs. atomic renaming action
Recall from Definition 2.5 the atomic renaming [] Fin which maps to , and swapping Fin which swaps and .
Fin is not generated as a monoid (under functional composition) by atomic renamings. In other words, atomic renamings are not enough to generate every Fin.
Atomic renamings are not injective. A functional composition of non-injective functions is also non-injective. The swapping () is injective, so no functional composition of atomic renamings can generate a swapping.
In spite of Lemma 2.22 atomic renamings are enough to construct Sub, in a suitable formal sense:
Suppose that 𝕏
Then for all Fin and all 𝕏 it is the case that
and so 𝕏 .
In words:
The renaming action is determined by the atomic renaming action.
In view of Lemma 2.22 the issue is that not every finitely-supported renaming can be expressed as a chain of atomic renamings. For comparison, it is the case that every finitely-supported permutation can be expressed as a chain of atomic permutations, so Theorem 2.23 is simply not an issue in nominal permutative techniques.
Suppose that [] ] always. Suppose that 𝕏 and choose any Fin. We wish to show that .
Now suppose that 𝕏 and Fin. Write . Choose some fresh (so # and ( for 1 ). Define
Note that
That is, both and can be expressed as functional compositions of atomic renamings. Also, by Theorem 2.13
The result follows.
Atomic renamings have the benefits of simplicity and concreteness. We now prove Corollary 2.24 and Lemma 2.25. These use atomic renamings, and they are useful for concrete calculations we shall perform later.
Corollary 2.24 is a corollary of part 1 of Lemma 2.16. It gives a concrete way to calculate support. We will find it useful for Lemmas 4.7 and 5.3.
Suppose that 𝕏 is a nominal renaming set and suppose that 𝕏. If and then [] .
Taking the contrapositive, if there exists some # such that [] , then #.
Lemma 2.25 is useful for proving Lemma 5.6 and Corollary 5.2:
Suppose that 𝕏 is a nominal renaming set, 𝕏, and 𝔸. Suppose that # and #.
Then [] ] if and only if # and ] .
Note that by our permutative convention, , , and are all distinct.
Suppose that # and ] . Then we reason as follows:
Conversely suppose that [] ] . Then
By Theorem 2.13
It follows that ] .
By similar reasoning we have that ] . By Lemma 2.16 it then follows that #.
3 Nominal renaming sets and the exponential
Recall from Subsection 2.1 that 𝕏𝕐 is the set of functions from the set to the set
Suppose that 𝕏 and 𝕐 are nominal renaming sets. Let 𝕏 𝕐 be the set of functions 𝕏𝕐 such that there exists some finite 𝔸 (for each , we fix one such ) such that for all Fin and 𝕏 if id then
In Definition 3.6 𝕏 𝕐 will serve as the underlying set of a nominal renaming set 𝕏 𝕐. In Theorem 7.6 we will prove that 𝕏 𝕐 is an exponential in a suitable cateogory of nominal renaming sets. First, we consider some examples and some properties of 𝕏 𝕐.
Recall from Subsection 2.3 that 𝔹 has underlying set and trivial renaming action so that and always.
For example:
1. Let 𝕏 and 𝕐 be nominal renaming sets. The map 𝕏 𝕐𝕏 mapping () to is in (𝕏 𝕐) 𝕏.
2. The map =𝔸 𝔸𝔹 mapping () to if and mapping () to if , is not an element of (𝔸 𝔸) 𝔹. This is because there is no finite set such that if id then for all 𝔸 it is the case that if and only if
3. Recall from Definition 2.15 that PFin is the set of finite sets of atoms with pointwise renaming action. Suppose that 𝕏 is any nominal renaming set. The map 𝕏PFin mapping to is sometimes an element of 𝕏 PFin — and sometimes not. In the case that 𝕏 𝔸 then and
Therefore 𝔸 PFin. Similarly for and for many other examples. In the case that 𝕏 is an ‘exploding model’, as discussed in Lemma 2.18, it is not necessarily the case that 𝕏 PFin. Taking the example from the proof of Lemma 2.18 we note that for any finite 𝔸 we can take and
Intuitively, a map that does not compare atoms in its argument for inequality will be in the underlying set of the exponential. A map that compares atoms for inequality, will not. See the Conclusions for further discussion.
A key technical lemma is that elements of 𝕏 𝕐 are determined only by their ‘asymptotic behaviour’, in the following sense:
Suppose that 𝕏 𝕐 and 𝕏 𝕐. Suppose that 𝔸 is finite and assume that for all 𝕏 if (‘asymptotic’ is in the sense of ‘supp
Without loss of generality (extending with if necessary) we may suppose that if then
Now choose any 𝕏. There are two cases:
If then by assumption
If then let be a fresh choice of atoms (so ). Let
By Lemma 2.16 we know that supp() . By Theorem 2.13 we know that . Therefore we reason as follows:
The result follows.
Following on from Lemma 3.4, a total function can be uniquely reconstructed from its ‘asymptotic’ behaviour:
Suppose that 𝕏
For all 𝕏 if then is defined.
For all such that id, if and () are both defined then ().
Then there exists a unique total function 𝕏 𝕐 extending the partial function , in the sense that ( if is defined.
The proof splits into three parts:
1. The statement of the definition of .
2. A proof that the statement is well-defined.
3. A proof that is unique.
We consider each part in turn:
1. Statement of the definition of .
Consider any 𝕏. Suppose . There are two cases:
If then we set
If then let be a choice of fresh atoms (so and ). Let
We set
2. Proof that the statement is well-defined.
We must show that the choice of fresh does not matter. Suppose that is some other choice of fresh atoms (so and ). Write
We must show that
Without loss of generality we assume the special case that
The general case then follows by two applications of the special case for an ‘even fresher’ set of fresh atoms . We write
By Theorem 2.13 and our assumption that , we know that . Also, by our assumption that , we know that ((). It follows that
By Theorem 2.13 and our assumption that supp(( it follows that
The result follows.
3. Proof that is unique.
This follows from Lemma 3.4.
If 𝕏 and 𝕐 are nominal renaming sets let 𝕏 𝕐 be specified as follows:
𝕏 𝕐 is defined in Definition 3.1.
We specify a renaming action by
for 𝕏 such that ( fixed in Definition 3.1). By Lemma 3.5 the renaming action is uniquely specified for all 𝕏.
Suppose that 𝕏 and 𝕐 are nominal renaming sets, 𝕏, and 𝕏 𝕐.
Then )() always.
As an immediate corollary if then ()
Suppose that 𝕏 and 𝕐 are nominal renaming sets. Suppose that 𝕏 𝕐. Then 𝔸 is such that
if and only if .
Suppose id. By Theorems 3.7 and 2.13 we have
for any 𝕏.
Conversely suppose that 𝔸 is such that for all 𝕏 if id then (). If we show that supports then by the ‘unique least’ property of support (Theorem 2.13) we are done. Suppose that id. By Theorem 3.7
By assumption
By Theorem 2.13 if then . So for all such that we have that
It follows by Lemma 3.4 that , as required.
Compare Corollary 3.9 with [14, Example 4.9, (24)].
Suppose that 𝕏 and 𝕐 are nominal renaming sets. Suppose that 𝕏 and 𝕏 𝕐. Then
Suppose that . Using Theorem 3.7 and Theorem 2.13 we easily calculate that (().
4 Nominal permutation sets
In this section we recall definitions and results from nominal techniques based on permutations, which will be useful for Section 5 and later sections.
4.1 Definitions and results, and connection with nominal renaming sets
The following definition is taken from [14]:
Let Per be the set of bijective functions from 𝔸 to 𝔸 (permutations) such that there exists some finite 𝔸 such that
for all 𝔸 it is the case that .
will range over elements of Per. We call these (finitely supported) permutations.
Per is a group, with identity id (the identity on atoms) and group composition function composition .
Furthermore, Per Fin from Definition 2.4 and Per is a submonoid of Fin.
Routine.
A nominal permutation set ℙ is a pair (
A finitely-supported permutation action is a function from Per ℙ to such that:
id for all ℙ.
() for all 𝕏 and Per. (So is a group action.)
For every ℙ there exists some finite 𝔸 such that for all Per and Per, if then . We say that every ℙ has finite support.
Suppose that ℙ is a nominal permutation set and ℙ. Say that 𝔸 supports when for all Per and Per, if then .
A nominal permutation set ℙ is a set with a finitely-supported Per-group action.
If 𝕏 is a nominal renaming set then (
Routine.
supp from Theorem 2.13 (the minimal set of atoms that supports as an element of a nominal renaming set) is a subset of from Definition 4.3 (a set of atoms that supports as an element of a nominal permutation set).
If supp( the result is immediate. Suppose that supp() (that is, suppose that # does not hold). Choose fresh (so # and ).
Recall swappings () (Definition 2.5). By Theorem 2.13 []). By Corollary 2.24 []. It follows that (). Therefore .
Suppose that 𝔸 is finite. Suppose that is a nominal renaming set and suppose that 𝕏.
Then supports in the sense of Definition 4.3 (considering as an element of a nominal permutation set) if and only if supports in the sense of Definition 2.8 (considering as an element of a nominal renaming set).
An informal corollary of Theorem 4.8, which can be made formal, is this:
If 𝕏 is a nominal renaming set and 𝕏 then the notion of support from Theorem 2.13 coincides with the notion of support obtained by restricting to permutations and using Definition 4.4 (plus known results from nominal permutative techniques, such as [14, Proposition 3.4]).
We shall write ‘supp()’ and use results about support such as Theorem 2.13 and Lemma 2.16 without concern for whether we consider as acted on by Fin (all renamings) or we consider as acted on by Per (only permutations).
4.2 The Gabbay-Pitts (nominal) model of abstraction
Suppose 𝕏 is a nominal renaming set and suppose 𝕏 and 𝔸. Define
Define 𝕏 by
A renaming action will follow in Definition 5.11. Recall from Definition 2.5 that the swapping () in the function on atoms which swaps and .
By Theorem 2.13 if # then () ] . Therefore, 𝕏 in Definition 4.10 is the same set as underlying set of abstraction from [14, Lemma 5.1].
We now recall properties of abstraction which will be useful later. By Theorem 4.8 results about abstractions built in nominal permutation sets can be directly imported to abstractions built using nominal renaming sets; as we have observed, the underlying sets are identical and notions of support are the same.
Suppose that 𝕏 is a nominal renaming set. Suppose that , and suppose that 𝔸.
Then ] if and only if # and ] .
By calculations from [14, Lemma 5.1].
Suppose that 𝕏 is a nominal renaming set, suppose 𝕏, and suppose that 𝔸 and #. Then
By calculations from [14, Lemma 5.1], and by Theorem 2.13.
Suppose that 𝕏 is a nominal renaming set and suppose 𝕏. Then if () then ].
By calculations from [14, Lemma 5.1].
5 The atoms-exponential 𝔸 𝕏 as a nominal-style atoms-abstraction
The results of this subsection demonstrate that if 𝕏 is a nominal renaming set then 𝔸 𝕏 and [𝔸]𝕏 are essentially the same thing.
From the point of view of research into nominal techniques, this is one of the important technical points of this paper because it makes a connection between nominal techniques as we know them from previous work [14, 10], and functional abstraction as supported by — and extensively used in — most major theorem-provers and programming languages [7].
Work based on presheaves also exhibits an abstraction as a function-space [8, Equation (8)]. We discuss this further in the Conclusions.
For every 𝔸 𝕏 there exists some 𝕏 and # such that 𝔸 [] .
We unpack Definition 3.6. 𝔸 𝕏 when 𝔸𝕏 and there exists some finite 𝔸 such that for all Fin and 𝔸, if id then (()).
Choose and any 𝔸. Then
So take and we are done.
Suppose that 𝕏 is a nominal renaming set. Suppose that 𝔸 𝕏 and 𝔸 𝕏 and suppose that # and #.
Then if and only if .
The right-to-left implication is immediate. So assume that . By Lemma 5.1
there exists some 𝕏 and 𝔸 such that # and 𝔸 [] , and
there exists some 𝕏 and 𝔸 such that # and 𝔸 [] .
We assumed that so [] ] . By Lemma 2.25
Choose any 𝔸. We reason as follows:
Suppose that 𝕏 𝕐.
Then # if and only if #, for any # (by our permutative convention, ).
Equivalently, for any #.
We prove two implications. Choose any #.
If # then by Corollary 3.9 # and we are done. Suppose that #. We have assumed # so by Corollary 2.24 it suffices to prove [] . Choose a fresh (so # and #[] ). By Corollary 5.2 it suffices to check that ])(). Note that by Corollary 3.9 #. We reason as follows:
Suppose that 𝕏 is a nominal renaming set and suppose that and 𝔸.
Then 𝔸 [] is supported by As a corollary, 𝔸 [] 𝔸 𝕏.
Unpacking Definition 3.1, 𝔸 [] 𝔸 𝕏 when
𝔸 [] 𝔸 𝕏 — this is true by construction — and
𝔸 [] has a finite supporting set.
Therefore, the corollary is immediate given the first part. We now prove that supports 𝔸 [] .
By Corollary 3.8 it suffices to show that for all Fin
So suppose id. By Corollary 5.2 it suffices to check
for fresh . So choose such that
We assumed that so using Theorem 3.7 it suffices to check that
Now we assumed that id and It follows that ( [])]. By Theorem 2.13 the result follows.
Suppose that 𝕏 is a nominal renaming set and suppose that 𝕏. Then supp(𝔸 []
Choose some fresh (so #𝔸 [] and #). By Lemma 5.4 𝔸 [] 𝔸 𝕏. Therefore by Lemma 5.3 we know that
Since # by Theorem 2.13 [] ) . By part 2 of Lemma 2.16 supp(() supp
Suppose that 𝕏 is a nominal renaming set, 𝕏, and 𝔸.
Then 𝔸 [] 𝔸 [] if and only if # and [] .
(Here 𝔸 and may be equal to or . By our permutative convention .)
Choose some fresh (so #, #, and and ).
If 𝔸 [] 𝔸 [] then [] ] . By Lemma 2.25 # and ] and we are done.
Conversely if # and ] then by Lemma 2.25 [] [] . Now by Theorem 2.13
for any 𝔸. The result follows.
If 𝕏 is a nominal renaming set then nominal abstractions [𝔸]𝕏 (Definition 4.10) and function-spaces 𝔸 𝕏 are related in a very strict sense:
𝔸 𝕏 is in bijection with 𝕏. The mutually inverse mappings are given by:
maps 𝕏 to 𝔸 [] , for () .
maps 𝔸 𝕏 to [](), for #.
Given our results so far, proving this is not hard. We show that and are well-defined:
is well-defined. Suppose that () and () (recall that by our permutative convention ). By Lemma 4.12 # and ] . By Lemma 5.6 𝔸 [] 𝔸 [] .
is well-defined. Suppose that # and #. By Lemma 4.13 [](]([] ()). Since # by (1) from Definition 3.1
The result follows.
We show that is injective and surjective:4
is surjective.
Suppose 𝔸 𝕏. By Lemma 5.1 there exists some 𝕏 and # such that 𝔸 [] . By construction ()
is injective.
Suppose that () and () and 𝔸 [] 𝔸 []. By Lemma 5.6 # and ]. By Lemma 4.12
it follows that []] as required.
Finally, we prove that and are mutually inverse:
followed by is the identity.
Suppose that 𝕏 and () . Then 𝔸 [] . By Corollary 5.5 #(), so
By Lemma 4.14 we are done.
followed by is the identity. Suppose that 𝔸 𝕏 and #. Then ](). By construction () []() so that
By (1) from Definition 3.1
The result follows.
From previous work [14, 10] we know that if ℙ is a nominal permutation set then ℙ has a permutation action. It is given by [()]. Informally, we can say:
A nominal permutation action on induces one on ℙ in a natural way.
𝔸 𝕏 is a nominal renaming set with action defined in Definition 3.6. By unpacking the maps and from the statement of Theorem 5.7 we can give 𝕏 a nominal renaming set action. Informally, we can say:
A nominal renaming action on 𝕏 induces one on 𝕏 in a natural way.
We need a technical definition:
Write # when
and
for all 𝔸 it is the case that .
# is merely a convenient notation; we do not give a renaming action to Fin.
If 𝕏 is a nominal renaming set let 𝕏 be defined by:
The underlying set of 𝕏 is 𝕏 from Definition 3.1.
The renaming action in Definition 5.11 is total and well-defined.
We must show that:
The renaming action is total. That is, for every 𝕏 there exists some 𝔸 and 𝕏 such that ] and #.
The renaming action is well-defined. If []] and # and # then []].
We consider each point in turn.
By construction if 𝕏 then there exist 𝔸 and 𝕏 such that ]. By Lemma 4.13 we may assume (renaming to be fresh if necessary) that #.
We reason as follows:
We need a technical lemma for Theorem 5.14:
If # and # then [] [].
By unpacking Definition 5.9 and by elementary calculations.
and from Theorem 5.7 are arrows in Sub (Definition 7.1). That is, suppose that 𝕏 is a nominal renaming set and suppose that 𝕏. Then:
Furthermore, the renaming action on 𝕏 (Definition 5.11) is that induced by the renaming action on 𝔸 𝕏 via the isomorphism expressed by and . That is,
We shall show that
Choose some fresh (so # and #). Since # by Definition 5.9 . Therefore by Theorem 3.7 we have that () and so
By Definition 5.11 [](] and we are done.
We shall show that
We unpack definitions:
We wish to show that
By Corollary 5.2 it suffices to check this for a fresh (so #𝔸 [] , #𝔸 [] , and #). We reason as follows:
We have just proved that (). We apply to both sides and use Theorem 5.7 and the previous parts of this result to conclude
as required.
We make one final ‘sanity check’ calculation about the relationship between 𝕏 and 𝔸 𝕏.
In previous work [14, 10] 𝕏 was endowed with a permutation action specified by
The renaming action
That is, if the renaming happens to be a permutation then the renaming action on abstractions emerging from the results above, coincides with the known permutation action on abstractions.
According to Definition 5.11, if Per and # (Lemma 5.13) then
So suppose that # is false. Choose some fresh (so # and #). By Lemma 4.13 []]([] ). Using Definition 5.11
By part 2 of Lemma 2.16 ()#( []) . Therefore by Lemma 4.13
We assumed # so by Theorem 2.13
The result follows.
6 Inductive datatypes of syntax-with-binding using nominal renaming sets
The first motivation for developing nominal (permutation) techniques was to construct datatypes of abstract syntax with binding.
We now have the results we need to quite easily construct a very similar theory of inductively defined sets of syntax-up-to-binding using 𝔸 -.
That is, if we build abstract syntax in Sub using using 𝔸 - to model abstraction (in a kind of ‘nominal weak higher-order abstract syntax’ style) then we obtain a nominal renaming set with exactly the same underlying set as that of the nominal permutation set which we obtain if we build abstract syntax in the category of nominal permutation sets, using [𝔸]-, and which therefore admits ‘nominal-style’ inductive reasoning.
Clearly, the fact that 𝔸 𝕏 equals 𝕏 (Theorem 5.7) is a strong hint in this direction.
Suppose that 𝕏
𝕏.
For all Fin and 𝕏, .
𝕏 𝕏.
If 𝕏 and then 𝕏 .
Routine.
A countably ascending chain of nominal renaming sets is a sequence for 0 such that for 0 .
That is, a countably ascending chain of nominal renaming sets looks like this:
Write for the nominal renaming set specified by:
The renaming action is constructed elementwise. That is, if Fin and because for some , then acting on as an element of is equal to acting on as an element of , included as an element of .
Suppose that maps nominal renaming sets to nominal renaming sets.
Say that preserves inclusions when 𝕏 𝕐 implies 𝕏 𝕐.
Say that preserves unions of countably ascending chains when .
As is standard, write 𝔸 - for the mapping from nominal renaming sets to nominal renaming sets, which maps 𝕏 to 𝔸 𝕏.
𝔸 - preserves inclusions and preserves unions of countably ascending chains.
𝔸 - preserves inclusions. Suppose that 𝕏 . Unpacking Definition 3.1, 𝔸 𝕏 is a function 𝔸𝕏 with finite support. By elementary properties of functions, is also an element of 𝔸 with finite support. Therefore 𝔸 𝕏 𝔸 .
𝔸 - preserves unions of countably ascending chains. Suppose that 𝔸 . Then 𝔸 and has finite support.
By Lemma 5.1 there exists some 𝔸 and such that
𝔸 [] . By construction for some such that 0 . It follows by Lemma 5.4 that 𝔸 . Therefore 𝔸 .
Now suppose that 𝔸 . Then 𝔸 . That is,
𝔸 and has finite support. Since the result follows.
Suppose that maps nominal renaming sets to nominal renaming sets.
A fixedpoint of is a nominal renaming set 𝕏 such that 𝕏 𝕏.
A least fixedpoint of is a fixedpoint 𝕏 of such that in addition, for all 𝕐 if 𝕐 𝕐 then 𝕏 𝕐.
Suppose that maps nominal renaming sets to nominal renaming sets. Suppose that 𝕏 is a nominal renaming set. Define 𝕏 for 0 inductively by:
That is, 𝕏 is ‘ applied times to 𝕏’.
If a map from nominal renaming sets to nominal renaming sets preserves inclusions and preserves unions of countably ascending chains, then it has a least fixedpoint
We take (. The proof that this is a least fixedpoint of is well-known and due to Tarski [26].
Suppose that 𝕏 and 𝕐 are nominal renaming sets. Let 𝕏 𝕐 be the nominal renaming set with
underlying set 𝕏 𝕐𝕏𝕐 (that is, 𝕏 𝕐 is a pair () where 𝕏 and 𝕐) and
pointwise renaming action (that is, ()).
Call this the cartesian product of 𝕏 and 𝕐.5
Let 𝕏 𝕐 be the nominal renaming set with
underlying set
pointwise renaming action (that is, and inr().
Call this the disjoint sum of 𝕏 and 𝕐.
The map from nominal renaming sets to nominal renaming sets specified by
has a least fixedpoint, write it Λ. can be identified with untyped -terms.
It routine to prove that maps built up using product -- and disjoint sum - + - preserve inclusions and preserve unions of countably ascending chains. By Lemma 6.6 we can also use 𝔸 -. 𝔸 𝕏 coincides with 𝕏 (Theorem 5.7). can be viewed as an -equivalence class and from previous work [14, 10, 17] (or by a long and detailed, but routine calculation [17]) we can verify that is indeed -terms up to -equivalence.
For the rest of this section we informally discuss the Gabbay-Pitts -quantifier and inductive reasoning principles for Λ.
Suppose that is a predicate on atoms (we discuss what that means, below). Write for the predicate which is:
True if the set 𝔸 is false is finite.
False otherwise.
For example if 𝔸 then:
() is false, because only finitely many atoms are equal to .
() is true, because infinitely many atoms are not equal to .
This is the Gabbay-Pitts quantifier [14].
The following inductive reasoning principle is from [14]:
Every nominal renaming set can be considered as a nominal permutation set. This inductive principle is as true of Λ viewed as a nominal renaming set, as it is of Λ viewed as a nominal permutation set in [14].
But for which inductive hypotheses ? We shall see that the category of nominal renaming sets (see Definition 7.1 in just a moment) is a topos, but it is not a boolean topos. It is therefore important to distinguish between ‘internal’ and ‘external’ inductive hypotheses.
External. We can admit the predicates of Fraenkel-Mostowski sets, as in [14]; this includes everything that occurs in reasonable practice. Constructing the language of Fraenkel-Mostowski sets and proving the validity of the inductive principle above is not hard, but it is outside the scope of this document. For more details of Fraenkel-Mostowski sets see [10, 14]. What amounts to nearly the same thing, but presented using the language of categories instead of the language of sets, is that we can use an adjunction between the category Sub (see below) and the category of nominal permutation sets from [14], in the style of [9, Section 3].
Internal. Recall Remark 3.3: intuitively, we can admit predicates that do not compare atoms for inequality, but the notion of truth for these predicates is not two-valued. See Subsection 7.4.
7 The category Sub
Nominal renaming sets form a category Sub as follows:
An object is a nominal renaming set 𝕏.
An arrow : 𝕏 𝕐 is a function 𝕏𝕐 such that for all Fin and all 𝕏 it is the case that
We let range over arrows.
7.1 Support and arrows
Arrows : 𝕏 𝕐 are precisely the elements 𝕏 𝕐 such that .
Suppose that : 𝕏 𝕐 is an arrow. By Definition 7.1 𝕏𝕐. According to Definition 3.1 to show that 𝕏 𝕐 we must exhibit some finite 𝔸 such that for all Fin and 𝕏 if id then ( (). It suffices to take . By Corollary 3.8, supp(.
Now suppose that 𝕏 𝕐 is such that . By Definition 3.1 𝕏𝕐. According to Definition 7.1 we must show that for all Fin and 𝕏 it is the case that (). This is immediate from Corollary 3.8.
If : 𝕏 𝕐 is an arrow in Sub then
A corollary of Corollaries 3.9 and 3.8.
7.2 The exponential in Sub
Suppose that 𝕏 and 𝕐 are nominal renaming sets. Let , or just app for short, be the function from 𝕏 𝕐𝕏 mapping 𝕏 𝕐 and 𝕏 to 𝕐. We call this application.
Suppose that 𝕏 and 𝕐 are nominal renaming sets. Then application app (𝕏 𝕐𝕏) 𝕐 from Definition 7.4 is an arrow in Sub.
Unpacking Definition 6.10, application maps from (𝕏 𝕐) 𝕏 to The result follows by Theorem 3.7.
𝕏 𝕐 is an exponential in Sub.
Suppose (𝕏 𝕐) ℤ. We must show that
It suffices to show that if id then
This is immediate using (6) and Theorem 2.13.
Now suppose that 𝕏 (𝕐 ℤ). We must show that
It suffices to show that
Now ()(())() by Theorem 3.7 and () by
(6). The result follows.
Sub is cartesian closed.
We must show that
Sub has a terminal object.
Sub has cartesian products.
Sub has exponentials.
It is routine to prove that 𝟙 ) ( for all Fin) from Subsection 2.3 is a terminal object in Sub.
Cartesian products are described in Definition 6.10. Exponentials are described in Theorem 7.6.
7.3 Limits and colimits
Recall the definition of tuples () from Definition 2.21.
Suppose that is a diagram in Sub. Then:
The limit exists in Sub and can be concretely constructed as
The colimit also exists in Sub and can be concretely constructed as
where
– is the equivalence relation generated by ()() for every and : , and
– is the -equivalence class of .
Limits. Suppose is a cone over with arrows . The corresponding map takes to The only nontrivial part is to verify that has finite support, which is immediate from the fact that by Corollary 3.9, and from part 2 of Lemma 2.20.
Colimits. The argument for colimits is similar, but simpler.
7.4 Sub is a topos
Let Ω be specified by:
Ω is the set of Fin such that:
– If then for all Fin.
– There exists some finite 𝔸 such that if then
If Ω and Fin then is defined by
Ω is finitely supported according to the renaming action defined in Definition 7.9. Therefore, Ω is a nominal renaming set.
Direct from the construction.
For example:
Fin and are in . As an immediate corollary is non-empty.
Fin ( not bijective) is in
Per is not in (the set of finitely supported permutations; Definition 4.1).
Suppose that Ω and Fin.
Then if and only if .
As an immediate corollary, id if and only if .
By definition . The result follows.
Suppose that Ω.
Then id if and only if Fin.
We prove two implications. If Fin then id is immediate.
Now suppose that id . By Definition 7.9, if then for all Fin. The result follows taking id.
A 1-1 correspondence (a bijection) between subobjects of 𝕏 and arrows 𝕏 Ω in Sub is given by:
𝕌 𝕏 maps to 𝕏𝕌.
: 𝕏 Ω maps to ( id
We check that and are inverse. Suppose that 𝕌 𝕏 and suppose that : 𝕏 Ω. Then:
Suppose that 𝕌 𝕏. We check that maps to Suppose that 𝕏. It suffices to verify that:
If (𝕌)() then (𝕌)(). If (𝕌)() then 𝕌. is closed under the renaming action, so also 𝕌. It follows that (𝕌)(). The result follows.
There exists some finite 𝔸 such that if (𝕌)() and id then (𝕌)().
Take If (𝕌)() then 𝕌. By Theorem 2.13 , therefore 𝕌. Therefore (𝕌)() as required.
We check that is an arrow, that is, (𝕌)((𝕌)():
We check that () is a subobject of 𝕏. By construction
So we must show that (). By Lemma 7.13 since id () we know that ( Fin, and therefore () as required.
Suppose that 𝕏 and 𝕐 are nominal renaming sets.
: 𝕏 𝕐 is mono if and only if as a map on underlying sets 𝕏𝕐 is injective.
Routine.
A subobject of 𝕏 may be uniquely identified with a nominal renaming set 𝕌 such that 𝕌 𝕏 (Definition 6.1).
A subobject of 𝕏 is an equivalence class of isomorphic monos into 𝕏. It is not hard to see that 𝕌 identifies the equivalence class of the mono which is the natural inclusion function, which we write
mapping 𝕌 to itself, that is, to 𝕏.
Write for the map from 𝟙 (Subsection 2.3) to mapping 𝟙 to Fin Ω. It is not hard to check that is an arrow. By Lemma 7.15 is also mono.
A diagram
is a pullback if and only if
By routine calculations.
Sub is a topos.
It suffices (see [3, Volume III, Definition 5.1.3]) to prove that:
Sub has finite limits.
Sub is cartesian closed.
Sub has a subobject classifier.
Sub is cartesian closed by Theorem 7.6. Sub has (finite) limits by Theorem 7.8. Ω is a subobject classifier by Theorem 7.14, and Lemmas 7.16 and 7.18.
Sub is not a boolean topos (the category of nominal sets is [14]). We can read off what kind of logic Sub gives rise to; truth values are sets of substitutions. Intuitively, the truth-value associated to ‘()’ is the set of renamings such that is true of . Intuitively, a truth-value of ‘’ in Sub is the collection of unifiers of and .
This will remain true also if we generalise the renaming action to substitute arbitrary elements (from some set) for atoms. Therefore, relatives of Sub might be useful for studying rewriting and unification. This is future work.
8 Conclusions
8.1 Variants on the theme of nominal renaming sets
Exploding models. Renaming sets are a set with a substitution action (of atoms for atoms). One of our long-term research aims is to suggest that substitution is a mathematical phenomenon worthy of independent study [13, 17].
Substitution is traditionally understood as a syntactic adjunct to function application. Function-application is modelled by function application in denotation (more-or-less by definition) — but by -equivalence in syntax. -equivalence in turn is implemented using substitution; substitution does not feature in the denotation and indeed neither do variable symbols (here, compare with Definition 2.1).
Exploding models (Subsection 2.3) display behaviour different from what we expect of datatypes of abstract syntax. There are two ways to look at this: as proof that substitution is more interesting than generally acknowledged, or as proof that Sub is not quite what we should be looking at. I prefer the former interpretation, but note that if we insist that supp( in Definition 2.8 then the problem goes away by definition (and the resulting category seems to behave much like Sub in other respects; verifying this in full detail is future work). It is not hard to show that this can also be expressed by the condition
for all , , , 𝕏, and fresh (so where is defined in Definition 2.8). This gives rise to a full subcategory of Sub containing precisely the ‘non-exploding’ models.
Models with more arrows. We just discussed how to remove parts of Sub. We can also reasonably add to it. In Definition 7.1 we insisted of an arrow : 𝕏 𝕐 that (() for all Fin and 𝕏. We can alternatively insist just that (() for all Per and 𝕏. This is the notion of arrow from nominal permutative techniques, but now it is pressed into service between sets with a renaming action.
An advantage is that there are more arrows between objects and more functions can be captured in the category, including those that distinguish between atoms.
This issue could also be addressed in the style of [9, Section 3] by setting up an adjunction between the category of nominal sets [14] and Sub; there should be no technical difficulty in doing this.
More general substitutions. Finally, we can consider a category of sets based on ‘substitution plus finite support’ where the substitution is of atoms for elements (for some collection of elements). A direct connection is possible with previous work by the myself with Mathijssen, where precisely this scenario is considered — but using purely syntactic techniques [13, 17].
It remains to investigate all of the variations above.
A basic message of this paper is that ‘nominal techniques’ can encompass ‘substitution plus finite support’ just as easily as ‘permutations plus finite support’, and the precise notion of ‘substitution’ and indeed of ‘arrow’ can be fine-tuned. We have considered a renaming action (substitution of atoms for atoms) in this paper — but it is clear that other design decisions in the same style but with different details, are possible. We hope that the mathematics in this paper will be a stimulus for research to use categories similar to Sub as denotations for more than sets with a renaming action alone.
8.2 Nominal renaming sets and higher-order abstract syntax
I was involved in developing nominal techniques. As discussed, this paper makes a point that the inductive datatypes which ‘permutations plus finite support’ was developed to support, are supported just as well by ‘renamings and finite support’.
A problem with nominal techniques is that their non-standard universe is not easily supported (see [11] and [10, Chapter 3]) by existing technology. This existing technology is almost universally based on Higher-Order Logic (HOL) or Zermelo-Fraenkel set theory (ZF) [7, 27, 22, 16] (I would also include COQ in this group [15]).
This puts nominal techniques at a disadvantage relative to other techniques, such as de Bruijn indexes [6] or weak or strong Higher-Order Abstract Syntax (HOAS) [23]. These have their own issues to overcome; a good argument in favour of nominal techniques is in [25]. Nevertheless, other techniques are easier to implement from a standing start and they have been studied longer and more extensively. Thus, at least for the moment, they exist in more highly-developed form (for example [24]) than the most advanced nominal-style implementation [5]. The current state of the art is that these difficulties can be circumvented but not removed.
A large part of the problem can be traced to the fact that [𝔸]𝕏 is not a set of functions (it is a set of partial functions [14, Equation (42)]). Therefore Theorem 5.7 of this paper holds out a hope for a ‘nominal HOAS’. A place to begin checking this is to check whether the Theory of Contexts [18] is sound in Sub. This collection of axioms formalises some desirable properties of abstract syntax — properties which have a noticable ‘nominal’ flavour. The Theory of Contexts was developed independently but recent developments have exploited nominal methods [19]; perhaps Sub will serve as a useful stepping-stone between nominal techniques and the HOAS-style Theory of Contexts.
Another place to look for connections is to build Miller and Tiu’s -quantifier using a model based on Sub [21], or provide a semantics for higher-order patterns, also by Miller [20].
There is therefore a reasonable possibility that Sub will give useful guidance on how to reconcile nominal techniques with existing higher-order logic technology, be it with HOAS or just for an independently-developed implementation. This is future work.
8.3 Related work
An interesting feature of nominal techniques is that they do not give denotation only to datatypes of abstract syntax. Nominal notions such as ‘freshness’ and ‘abstraction’ can be applied equally to non-syntactic structures such as function-spaces. This has been done, for example, in work on ‘nominal pointers’ [2] and ‘nominal games’ [1]. This gives nominal techniques a distinct foundational flavour. It is common to identify ‘nominal techniqes’ as ‘an approach to syntax with binding’. That is certainly part of the story, but only a part; they are a mathematical model of names. This paper demonstrates that the model accommodates names that can be renamed as well as permuted.
The semantic approach to names is in common with work based on categories of presheaves [9, 8]. In that work, abstraction is also modelled using an exponential [8, Equation (8)]. Nevertheless, Sub is distinct from these. The crucial difference is Theorem 2.13, which states that every has a single unique least supporting set. This property is enjoyed in the categories of nominal permutation sets and nominal renaming sets. It is not enjoyed in the work based on presheaves, and this property leads to the (in my opinion, simple) sets-based presentation used in this paper and elsewhere.
We now propose two hypotheses:
Let Var be the category with objects finite subsets of 𝔸 and arrows functions between them. Let Set be the category of all sets and all functions between them.
Let PBM be the category of presheaves in SetVar (functors from Var to Set) that preserve pullbacks of pairs of monos in Var (injections), and natural transformations between them.
Hypothesis 8.1. Sub is equivalent to PBM.
Intuitively, the property of preserving pullbacks of pairs of monos is the property of preserving intersections (see Lemma 2.12).
For Var write for the functor taking to Var(), with the natural right-composition action on arrows.
Specify a topology on SetVar by letting its basis be those subfunctors of generated by some injection : .
Hypothesis 8.2. PBM can be presented as a topos for the topology of Definition 8.2.
In previous work with Mathijssen we have developed Nominal Algebra [17]. This is a framework for algebraic reasoning in the presence of binding. Using notation from [17] we propose one more hypothesis:
Hypothesis 8.3. Sub is equivalent to the category of models of the following theory in nominal algebra:
There is scope for a whole second paper in the checking (and possible refinement) of these hypotheses. This is future work.
We hope that Sub can be the basis of future research directly — starting perhaps with the Theory of Contexts and with the three hypotheses above — and will serve as an example of other, similar, objects of study based on the idea ‘ plus finite support’ for different values of .
References
[1] S. Abramsky, D. R. Ghica, A. S. Murawski, C.-H. L. Ong, and I. D. B. Stark. Nominal games and full abstraction for the nu-calculus. In LICS, pages 150–159. IEEE, 2004.
[2] Nick Benton and Benjamin Leperchey. Relational reasoning in a nominal semantics for storage. In Proc. of the 7th Int’l Conf. on Typed Lambda Calculi and Applications volume 3461 of LNCS, pages 86–101, 2005.
[3] F. Borceux. Handbook of Categorical Algebra. Number 50, 51, 52 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, Great Britain, 1994.
[4] N. Brunner. 75 years of independence proofs by fraenkel-mostowski permutation models, 1996.
[5] Christine Tasson Christian Urban. Nominal techniques in isabelle/hol. In CADE 2005, volume 3632 of Lecture Notes in Artificial Intelligence, pages 38–53, 2005.
[6] N. 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(34):381–392, 1972.
[7] William M. Farmer. The seven virtues of simple type theory. Technical Report 18, McMaster University, SQRL, 2003 (revised 2006).
[8] M. P. Fiore, G. D. Plotkin, and D. Turi. Abstract syntax and variable binding. In 14th Annual Symposium on Logic in Computer Science, pages 193–202. IEEE Computer Society Press, 1999.
[9] Marcelo Fiore and Daniele Turi. Semantics of name and value passing. In Proc. 16th LICS Conf., pages 93–104. IEEE, Computer Society Press, 2001.
[10] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
[11] Murdoch J. Gabbay. FM-HOL, a higher-order theory of names. In F. Kamareddine, editor, 35 Years of Automath, 2002.
[12] Murdoch J. Gabbay. A general mathematics of names. Information and Computation, 205(7):982–1011, 2007.
[13] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding substitution as a nominal algebra (journal version). Formal Aspects of Computing, 2008. Available online.
[14] Murdoch J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.
[15] Huet, Gilles Kahn, and Christine Paulin-Mohring. The Coq proof assistant, a tutorial. http://pauillac.inria.fr/coq/doc/tutorial.html. LogiCal Project.
[16] Thomas Jech. Set theory. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Fall 2002.
[17] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.
[18] Marino Miculan. Developing (meta)theory of lambda-calculus in the theory of contexts. ENTCS, 1(58), 2001.
[19] Marino Miculan, Ivan Scagnetto, and Furio Honsell. Translating specifications from nominal logic to cic with the theory of contexts. In MERLIN, pages 41–49. ACM, 2005.
[20] Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Extensions of Logic Programming, 475:253–281, 1991.
[21] Dale Miller and Alwen Tiu. A proof theory for generic judgments: An extended abstract. In LICS, pages 118–127. IEEE, 2003.
[22] Lawrence C. Paulson. The foundation of a generic theorem prover. Journal of Automated Reasoning, 5(3):363–397, 1989.
[23] F. Pfenning and C. Elliot. Higher-order abstract syntax. In PLDI ’88: Proc. of the ACM SIGPLAN 1988 conf. on Programming Language design and Implementation, pages 199–208. ACM Press, 1988.
[24] Frank Pfenning and Carsten . System description: Twelf -a meta-logical framework for deductive systems. In H. Ganzinger, editor, CADE-16, 16th Int’l Conf. on Automated Deduction, pages 202–206. Springer, 1999.
[25] Andrew M. Pitts. Equivariant syntax and semantics. In ICALP, pages 32–36. Springer-Verlag, 2002.
[26] A. Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5:285–309, 1955.
[27] Johan van Benthem. Higher-order logic. In D.M. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 189–244. Kluwer, 2001.
Notes
1I am grateful to Andrew Pitts for his comments on these ideas while he was supervising my thesis. I am also indebted to Martin Hofmann for his comments and suggestions during a visit to Munich, to Marino Miculan, to David Richter, and to Michael Gabbay. ↩
2Unpublished manuscript discussed with Andrew Pitts and later with Martin Hoffman. ↩
3𝔸 is a collection of urelemente [4, 14, 12]. ↩
4This follows also from the next step, in which we prove that and are mutually inverse. It is nevertheless instructive to spell out the calculations for proving injectivity and surjectivity. ↩
5This is nothing more than a special case of Definition 2.21. However, it is a very useful special case. ↩