HTML reading edition · 14 source pages · Open the source PDF

An observation on support and freshness in nominal sets (Technical report)

Murdoch J. Gabbay

There are two natural ways of excluding an atom a in nominal techniques: we can either consider the sets X such that a is fresh for X, or we can consider the sets X such that a is fresh for every x ∈ X.

The statements of ‘being fresh for all the elements of that set’ and ‘being fresh for a set’ are not the same: it is not the case that ∀x ∈ X.a#x if and only if a#X.

Both notions encode natural notions of ‘fresh a’. In this paper, it is proved that these notions lead naturally to two categories that are isomorphic, so that in a suitable generalised sense they are the same.

The result is mathematically attractive and has an interesting reading: it is equivalent to add a fresh atom to the underlying universe, and to add a symbol to the meta-language referencing a fresh atom. Or to put it slightly differently: we prove the intuitively appealing but non-obvious fact that a fresh atom in the object-level is categorically isomorphic to a fresh atom in the meta-level.

May 18, 2010 ⃝c Gabbay

1 Introduction

1.1 A little background on nominal semantics

Nominal techniques were introduced in [14]. With Pitts, we considered the problem of giving semantics to inductive definitions with binding. We did this by considering inductively defined datatypes in Fraenkel-Mostowski set theory (FM sets).

FM sets was developed to prove the independence of the Axiom of Choice [2]. It is not obvious that a representation of binding is to be found in a set theory from the earlier half of the 20th century, but it is. This semantics is now used directly or through various logical and operational presentations such as nominal logic, FreshML, or the nominal datatypes package. See Mulligan’s online bibliography [21].

Nominal techniques give variable symbols a denotational reality as atoms, or urelemente. If the reader is familiar with nominal logic [23], FreshML [26], or the nominal datatypes package in Isabelle [28], they will recognise this idea in the datatype of atoms A, used to represent variable symbols. Atoms are data.

The specific mathematical content here is in the fact that in FM sets and the systems which were then derived from it, this ‘datatype of atoms’ displays some striking behaviour which is a good semantic model of names and binding. This behaviour is distinctive and distinguishes nominal techniques from models of variable symbols based on functions [22], numbers [5], or links [1, Section 1].

Much of the content of FM sets is shared with work using presheaves [8]. The extra benefit of using FM sets is its sets-based presentation, which enjoys a unique notion of support.1

1.2 The support of a set X is not the support of its elements x ∈ X

In FM sets, every element has a notion of support, supp(x) (full definitions will follow). This generalises the syntactic notion of ‘free variable symbols of’. In the case that the set represents an abstract syntax tree, support and ‘free variable symbols of’ can be made to coincide in a natural way.

However, the support of X does not coincide with ‘atoms in the transitive closure of X’, nor with ‘union of the supports of all x ∈ X’.2

In my own experience, it is hard for people to see how a set that ‘contains a’ might not contain a in its support. There are strong intuitions that a ∈ X should imply a ∈ supp(X), and that a ∉ x for all x ∈ X should imply a ∉ supp(X).

This will be very familiar to some readers, and perhaps less so to others. Here are two illustrative examples:

Example 1.1

• supp(A) = ∅ but the atoms in the transitive closure of A is A. Also ⋃{supp(x) | x ∈A} = A.

a is ‘in’ the set of all atoms, but because so is every other atom, it is not in the support of the set of all atoms.

• Also, supp(A\{a}) = {a} but the atoms in the transitive closure of A\{a} and ⋃{supp(x) | x ∈A\{a}} are both equal to A\{a}. a is ‘not in’ the set of all atoms minus a, but since it thus distinguishes itself by this absence, it is in the support of the set of all atoms minus a.

The behaviour illustrated above is important: the correctness of the self-duality of the И-quantifier, of atoms-abstraction, and the nominal model of abstract-syntax-with-binding, intimately depend on this.

As standard, write a#x for a ∉ supp(x). The fact is that it is not the case that a#X if and only if ∀x ∈ X.a#x. This is why we not only do not, but can not define supp by induction on sets (whereas ‘free variables of’ is and must be defined by induction). Thinking of X as a predicate and x ∈ X as a datum, and using a bit of nominal jargon, this is related to the fact that in nominal semantics equivariant functions and predicates can and do act on non-equivariant data.

1.3 The main results

In this paper, I will use a little bit of category theory and some elementary sets constructions to exhibit a sense in which natural generalisations of ‘support of X’ and ‘support of all x ∈ X’ — are equivalent.

For the reader already familiar with nominal techniques I will now briefly sketch the main definition and two results of this paper; full details will follow.

Write FMSet for the category with objects FM sets and arrows function(-sets) between them (see Definition 3.2 for the precise definition).

Our first main result is Theorem 3.3. This presents the strongest positive and direct connection I know of in general, between the support of X in FMSet and the support of x ∈ X.

To state the next result we need just a little notation.

Definition 1.2

Fix some atom a and define two new categories using FMSet:

• Define a category FMSet#a by:

– Objects are elements X of FMSet such that ∀x∈X.a#x.

– Arrows are the full set of arrows f : X −→ Y ∈ FMSet.

• Define a category FMSetνa by:

– Objects are elements X of FMSet such that a#X.

– Arrows are arrows f : X −→ Y ∈ FMSet such that a# f .

Remark 1.3

FMSet#a and FMSetνa both implement notions of ‘exclude a’:

• In FMSet#a, a is excluded in the sense of ‘fresh for all the elements of’.

• In FMSetνa, a is excluded in the sense of ‘fresh for’.

The second main result of this paper is Theorem 5.11. This states that FMSet#a and FMSetνa are isomorphic categories. In this sense, ‘fresh for’ and ‘fresh for all elements of’ are the same after all.

Another way of reading this is particularly interesting.

• In FMSet#a a is fresh ‘at the object level’; the arrows represent functions that operate on elements without a in their support. Note that the functions themselves will have a in their support; think of the characteristic function of A\{a}.

• In FMSetνa a is fresh ‘at the meta-level’; the arrows represent functions without a in their support. Note that the functions may operate on elements with a in their support; think of the characteristic function of A.

(Just to locate all of this relative to the category of nominal sets NOM: the category NOM of equivariant FM sets and equivariant functions between them is a limit of the νa construction. It represents a totally equivariant meta-language, operating on data that need not be equivariant.)

The main result asserts an equivalence between freshness at the meta-level and freshness at the object-level in the sense above. Or, to put it slightly differently: we prove the intuitively appealing but non-obvious fact that a fresh atom in the object-level is categorically isomorphic to a fresh atom in the meta-level.

This paper presents part of the mathematics of a larger manuscript [11], in a more accessible form and with an exposition tailored to Theorems 3.3 and 5.11.

2 Basic nominal constructions

2.1 The cumulative hierarchy

Definition 2.1

Fix a countably infinite set A of atoms. a,b,c,... will range over distinct elements of A. We call this the permutative convention.

Definition 2.2

We define a collection of elements U in the style of von Neumann [17] by ordinal induction as follows:

1. U0 = A.

2. If α < β and U ∈ Uα then U ∈ Uβ.

3. If U ⊆⋃ α<β Uα then U ∈ Uβ.

We let U be the collection of all x such that x ∈ Uα for some α.

U is a standard cumulative hierarchy model of Zermelo-Fraenkel set theory with atoms (ZFA). Examples are illustrated in Figure 1. This construction has been used for example in [9, 14, 4].

U is the least pre-fixedpoint of the operator ‘take the powerset of’; powerset(U ) ⊆ U .

Definition 2.3

Write x ∈ U for ‘x ∈ Uα, for some ordinal α’, and read this as x is an element. x will range over elements of U .

Definition 2.4

Call a non-atomic element a set. That is, x is a set when x ∈ U and x ∉A.

If X is a set then X = {x | x ∈ X}. This is not the case of atoms. For example a ≠ {x | x ∈ a} = ∅.

Definition 2.5

Let x and y be elements. Let X and Y be sets. Implement the ordered pair (x,y) and product set X ×Y by

(x,y) = {{x},{x,y}} X ×Y = {(x,y) | x ∈X, y ∈Y}.

Functions are implemented as graphs f = {(x, f (x)} that are sets, as is standard. We let f , g range over elements that are function-sets.

Write X → Y for the set of function-sets with domain X and range a subset of Y.

a ∈U0b ∈U0∅⊆U0A ⊆U0{a} ∈U1{a,b} ∈U1∅∈U1A ∈U1{{a},{a,b}} ∈U2{∅} ∈U2A∪{A} ∈U2... N = {0,1,2,...} ∈Uω...
Figure 1: Example sets in the cumulative hierarchy

2.2 Permutations

Definition 2.6

A permutation π is a bijection on A such that {a | π(a) ≠ a} 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(a) = a always.

• Write ◦ for functional composition. So (π ◦ π′)(a) = π(π′(a)).

• Write π-1 for the inverse of π, so π ◦ π-1 = id = π-1 ◦ π.

• Write P for the set of all permutations.

Definition 2.7

We define a permutation action inductively by:

π·a = π(a) π·X = {π·x | x ∈X} (X not an atom)
Lemma 2.8

id·x = x and π′·(π·x) = (π′ ◦ π)·x.

In words: permutation is a group action on U .

Proof

By a routine induction on U .

• The case of an atom a. From Definition 2.7 it is immediate that id·a = a and π′·(π·a) = π′(π(a)) = (π′ ◦ π)·a.

• The case of a set X. From Definition 2.7 and the inductive hypothesis for every x ∈ X.End of proof

2.3 Support

Definition 2.9

Let A be a finite set of atoms.

• Write fix(A) = {π | ∀a ∈ A.π(a) = a}.

• Say that A supports x when π·x = x for all π ∈ fix(A).

• Say x has finite support when some finite A supporting x exists.

• Define supp(x) the support of x by

supp(x) =⋂ {A | A a finite set of atoms supporting x}

if x has finite support, and supp(x) is undefined otherwise.

• Write a#x when a ∉ supp(x) and call a fresh for x. Write a#x,y,z for ‘a#x and a#y and a#z’, and so on.

Remark 2.10

Not every element of U has finite support. Make a fixed but arbitrary choice of bijection of A with the natural numbers {0,1,2,3,4,5,...}. Let comb ⊆A be the element corresponding under this bijection with the even numbers {0,2,4,...}.

comb contains ‘every other atom’ {a,c,e,g,...}. There is no finite A ⊆A such that if π ∈ fix(A) then π·comb = comb.

Theorem 2.11

A supports x if and only if π·A supports π·x.

As an immediate corollary, π·supp(x) = supp(π·x).

Definition 2.12

If π is a permutation and A ⊆A is a set of atoms, write π|A for the partial function such that

π|A(a) ={ π(a) if a ∈Aundefined if a ∈A\A.
Theorem 2.13

Let x be any element. If A and B are finite and support x then so does A ∩ B. As a corollary:

1. If x has a finite supporting set then it has a least finite supporting set and this is equal to supp(x).

2. If π|supp(x) = π′|supp(x) then π·x = π′x.

Proof

Suppose τ fixes A ∩ B pointwise. We must show τ·x = x. Write

K for {a | τ(a) ≠ a}.

Choose an injection ι of B \ A into A\ (A ∪ B ∪ K). Define a permutation π by π(a) = ι(a) if a ∈ B \ A, π(ι(a)) = a if a ∈ B \ A, and π(b) = b if b ∉ B \ A and ι-1(b) ∉ B \ A. Note that π ◦ π = id, so π = π-1. π fixes A pointwise so π·x = x. Also π ◦ τ ◦ π fixes B pointwise so (π ◦ τ ◦ π)·x = x. We apply π to both sides, use Lemma 2.8, and simplify, and conclude that τ·x = x as required.

The first corollary follows from the fact that a descending chain of finite sets ordered by strict subset inclusion, is finite. The second corollary follows directly from the definition of support in Definition 2.9.End of proof

2.4 Equivariance

Definition 2.14

The language of ZFA set theory is first-order logic with equality = and a binary predicate ∈ called set inclusion. φ will range over predicates in this language.

Theorem 2.15

Suppose φ(x) is a predicate mentioning only variables from the list x. Then

φ(x) ⇔φ(π·x).
Sketch proof

Atoms are atomic; if we build one model of ZFA sets then we can permute its atoms to obtain another model. The result follows by soundness and completeness of first-order logic [27].End of proof

The reader can find much more on permutations in [25]. Indeed, the use of permutations of variable symbols predates nominal techniques; see for example [19, Subsection 9.2].

Definition 2.16

As is standard, we can specify a map χ using a predicate φ(x,z) such that

∀x.((∃z.φ(x,z))∧(∀z,z′.φ(x,z)∧φ(x,z′) ⇒z = z′)).
Corollary 2.17

Suppose χ(x) is a function specified using a predicate mentioning only variables from the list x,z. Then

π·χ(x) = χ(π·x).
Proof

We unpack Definition 2.16 and use equivariance (Theorem 2.15).End of proof

Theorem 2.18 is useful and easy to prove:

Theorem 2.18

Suppose χ(x) is a function on variables included in x, which is x1,...,xn. Suppose x denotes elements with finite support. Then

supp(χ(x)) ⊆supp(x1)∪···∪supp(xn).

As a corollary, if χ is injective then

supp(χ(x)) = supp(x1)∪···∪supp(xn).
Proof

The corollary follows by considering the result for χ and its inverse.

Suppose that π ∈ fix(supp(x1) ∪···∪ supp(xn)). We reason as follows:

π·χ(x) = χ(π·x) Corollary 2.17= χ(x) Theorem 2.13

The result follows.End of proof

3 Relation between supp(X) and supp(x) for x ∈ X

Definition 3.1

Suppose that X is a set. If X has finite support and all x ∈ X have finite support then say that X has finite support to level 1.

X and Y will range over sets with finite support to level 1.

Consider the notions ‘fresh for’ versus ‘fresh for all elements of’. In symbols, consider the predicates

a#X versus ∀x ∈X.a#x.

If X is finite then ‘fresh for’ and ‘fresh for all elements of’ coincide. This matches the naive expection discussed in the Introduction; this is exactly the behaviour displayed by (finite) name-carrying abstract syntax.

Also as discussed in the Introduction, a central feature of nominal techniques is that if X is infinite then the two notions part company, and no particular implication connects them in general. Recall Example 1.1.

So just because a#X does not mean that a is fresh for every element in X, and conversely, just because a#x for every x ∈ X does not mean that a is fresh for X overall.

Definition 3.2

Define the category FMSet by:

• Objects are sets X in U with finite support to level 1.

• Arrows f : X −→ Y are the function-sets in X → Y with finite support.

In [9, 14] we use the hereditarily finitely supported sets; in Definition 3.2 we use sets with finite support to level 1, which is not quite the same. The difference will not be important.

Theorem 3.3 is new to the best of my knowledge. It gives the strongest direct equality I know of between supp(X) and supp(x) for x ∈ X.

Theorem 3.3

Suppose X has finite support to level 1. If ⋃{supp(x) | x ∈ X} is finite then

supp(X) =⋃ {supp(x) | x ∈X}.
Proof

Suppose that ⋃{supp(x) | x ∈ X} is finite. We prove two set inclusions:

• supp(X) ⊆⋃{supp(x) | x ∈ X}. If ⋃{supp(x) | x ∈ X} is finite then the result follows by Theorem 2.13 and the fact that π·X = {π·x | x ∈ X}.

• ⋃{supp(x) | x ∈ X} ⊆ supp(X). Suppose x ∈ X and a ∈ supp(x). Choose fresh b (so b#X and b#x′ for every x′ ∈ X). By Theorem 2.11 supp((b a)·x) = (b a)·supp(x). Since X has no element y such that b ∈ supp(y), we know that (b a)·x ≠ X and by Theorem 2.13 it must be that a ∈ supp(X).End of proof

Remark 3.4

The special case of Theorem 3.3 where X is a finite set is known. See for example [10, Lemma 2.22] or [16]. Note that Theorem 3.3 is more general, and holds for X infinite.

Thanks to anonymous referees of previous papers for suggesting the precise form of the result stated here, and for providing the reference to the Isabelle code.

4 The И quantifier

Definition 4.1

Suppose φ(z,a) is a predicate on variables included in z,a — here z is shorthand for ‘any other variables mentioned in φ’, and we intend a to range over atoms.

The NEW quantifier Иa.φ(z,a) is defined by

Иa.φ(z,a) is true when {a ∈A | φ(z,a) is false} is finite.

Definition 4.2

If z is a list of variables z1,...,zn write

a#z for a#z1 ∧...∧a#zn.

Theorem 4.3 expresses the characteristic some/any property of the И-quantifier:

Theorem 4.3

Suppose φ(z,a) is a predicate on variables included in z,a. Suppose z denotes a list of elements with finite support. Then the following are equivalent:

∀a. (a ∈A∧a#z) =⇒φ(z,a) ∀form ofИa.φ(z,a)Иa.φ(z,a) ∃a. a ∈A∧a#z∧φ(z,a) ∃form ofИa.φ(z,a)
Proof

All top-to-bottom implications are easy. Now suppose there exists some atom a such that a#z ∧ φ(z,a). Choose any other atom b such that b#z. By Theorems 2.15 and 2.13 it follows that φ(z,b). The result follows.End of proof

Freshness a#x (Definition 2.9) can be characterised directly using И and equality (see [14, Equation 5] or [14, Equation 13]):

Theorem 4.4

Let x be an element with finite support. Then

a#x if and only ifИb.(b a)·x = x.
Proof

Suppose a#x. By Theorem 2.13 if (b a)·x ≠ x then b ∈ supp(x). supp(x) is finite by assumption. The result follows.

Now suppose that Иb.(b a)·x = x. Let B be a finite set such that for all b ∈A\B, (b a)·x = x. Choose any pair of distinct atoms b and b′ in B. Note that

(b b′) = (b b′)◦(b a)◦(b a) = (b a)◦(b′ a)◦(b a).

Therefore (b b′)·x = x always.

fix(B ∪{a}) is generated as a group by elements of the form (b′ b) and (b a) as considered above. It follows that if π ∈ fix(B ∪{a}) then π·x = x. Therefore a ∉ supp(x).End of proof

5 Statement and proof of the isomorphism

Fix an atom a. Recall Definitions 3.1 and 1.2 for the definitions of FMSet, FMSet#a and FMSetνa.

5.1 a-fresh sets

Definition 5.1

If X ∈ FMSet write

X#a = {x ∈X | a#x}.

Call this the a-fresh version of X.

If X ∈ FMSet and Y ∈ FMSet and f ∈ X −→ Y, write

f#a = {(x, f(x)) | x ∈X#a}.

Definition 5.1 reprises a comment in [13, Section 7, page 9]. In [11] we use the construction to give some nice proofs of properties of atoms-abstraction. The same construction is used by Clouston in [4].

Lemma 5.2 underlines the distinctness of ‘fresh for’ and ‘fresh for all elements of’:

Lemma 5.2

a#X does not necessarily imply that X#a = X.

Proof

Consider a#A. Then A#a = A\{a} ≠ A.End of proof

Lemma 5.3

If f : X −→ Y ∈ FMSetνa then f#a : X#a −→ Y#a ∈ FMSet#a.

Proof

Suppose f : X −→ Y ∈ FMSetνa. In particular, a# f . It follows using Theorem 2.18 that f#a : X#a −→ Y#a.End of proof

5.2 Atoms-restriction

A notion of atoms-restriction will be useful:

Definition 5.4

Suppose X is an object in FMSet. Define νa.X by

νa.X = {π′·x′ | π′ ∈fix(supp(X)\{a}), x′ ∈X}.

We read νa.X as restrict a in X.

νa.X is a model of the name-restriction of [6] and [24]; it is closely related to the permutation orbits of [10].

Lemma 5.5

Suppose X is an object in FMset.

1. supp(νa.X) ⊆ supp(X) \{a}.

2. It is not true in general that supp(νa.X) = supp(X) \{a}.

3. a#X if and only if νa.X = X.

Proof

1. It is easy to check that if π ∈ fix(supp(X) \ {a}) then π·νa.X = νa.X. The result follows by Theorem 2.13.

2. It suffices to provide a counterexample. Choose any b and take X = (A × A) \ {(a,b)} (Definition 2.5). It is easy to check that νa.X = A×A.

3. Suppose a#X. Suppose π′ ∈ fix(supp(X) \ {a}) and x′ ∈ X. By Theorems 2.15 and 2.13, π′·x′ ∈ X. It follows easily that νa.X = X. Conversely, if νa.X = X then by part 1 of this result a#X.End of proof

Lemma 5.6

1. Suppose X is an object in FMSetνa. Then νa.(X#a) = X.

2. Suppose X is an object in FMSet#a. Then (νa.X)#a = X.

Proof

For the first part, we prove two set inclusions:

• Proof that X ⊆ νa.(X#a). Suppose x ∈ X. Choose some fresh b (so b#x,X). By Theorem 2.13 (b a)·x ∈ X and furthermore by Theorem 2.11 (b a)·x ∈ X#a. It follows from Definition 5.4 that x ∈ νa.(X#a).

• Proof that νa.(X#a) ⊆ X. Suppose x ∈ νa.(X#a). So x = π′·x′ for some π′ ∈ fix(supp(X#a)\{a}) and some x′ ∈ X#a. By Theorem 2.18 supp(X#a) \{a} ⊆ supp(X). Therefore π′ ∈ fix(supp(X)). Now x′ ∈ X, so by Theorem 2.13 π′·x′ ∈ X.

For the second part, again we prove two set inclusions:

• Proof that X ⊆ (νa.X)#a. Suppose x ∈ X (so a#x). Then x ∈ νa.X and it is immediate that x ∈ (νa.X)#a.

• Proof that (νa.X)#a ⊆ X. Suppose x ∈ (νa.X)#a. So x = π′·x′ for some π′ ∈ fix(supp(X)\{a}) and some x′ ∈ X (so a#x′). Now choose some entirely fresh b (so b#X,x,a,π′) and write π = (b a) ◦ π′ ◦ (b a). It is a fact that π ∈ fix(supp(X) ∪{a}), so by Theorem 2.13 π·X = X. Since a#x′, it is also a fact that π|supp(x′) = π′|supp(x′). By Theorem 2.13 π′·x′ = π·x′. It follows that x ∈ X, and by Theorem 2.11 it also follows that a#x.End of proof

Proposition 5.7

Suppose f ∈ X → Y is a function-set. Then π· f is a function-set in π·X → π·Y, and it represents the function

λx ∈π·X.π·(f(π-1·x)).

This is the conjugation action.

Proof

From equivariance (Theorem 2.15).End of proof

Definition 5.8

Suppose f : X −→ Y ∈ FMSet#a. Define νa. f as follows: if x ∈ νa.X then we set

Иb. (νa.f)(x) = (b a)·f((b a)·x).

We read νa. f as restrict a in f .

Lemma 5.9

If f : X −→ Y ∈ FMSet#a then:

• νa. f is well-defined (the choice of fresh b does not matter).

• νa. f : νa.X −→ νa.Y ∈ FMSetνa.

• supp(νa. f ) ⊆ supp( f ) \{a}.

Proof

First, we review what has to be proved.

Suppose x ∈ νa.X. Choose some fresh b (so b# f ,a,x).

By Theorem 4.3 (∃ form), to calculate νa. f it suffices to calculate (b a)· f ((b a)·x). It is a fact that if b#(b a)· f ((b a)·x) then this result does not depend on the choice of fresh b.

We must also check that supp(νa. f ) is finite, and a#νa. f ; there is no need for a separate proof of this, since it is subsumed by a proof that supp(νa. f ) ⊆ supp( f ) \{a}.

We sketch each part of the proof in turn:

• (b a)· f ((b a)·x) well-defined. b#(b a)· f ((b a)·x) is immediate because we assumed that f ∈ FMSet#a. What is slightly non-trivial is to prove that if x ∈ νa.X then (b a)·x ∈ X. Since x ∈ νa.X and X ∈ FMSet#a, there exists some π′ ∈ fix(supp(X) \ {a}) and some x′ ∈ X such that x = π′·x′ and a#x′. We reason as follows:

(b a)·x fact= (b a)·π′·x′ Lem. 2.8= ((b a)◦π′ ◦(b a))·(b a)·x′ a,b#x′,Thm. 2.13= ((b a)◦π′ ◦(b a))·x′

It is a fact that ((b a) ◦ π′ ◦ (b a)) ∈ fix(supp(X)) and it follows by Theorems 2.15 and 2.13 that (b a)·x ∈ X.

• b#(b a)· f ((b a)·x). Using Theorem 2.11.

• b#(b a)· f ((b a)·x) ∈ νa.Y. It is a fact that f ((b a)·x) ∈ Y. The result follows by the definition of νa.Y.

We now prove that supp(νa. f ) ⊆ supp( f ) \{a}. By Theorem 2.18 supp(νa. f ) ⊆ supp( f ) ∪{a}. By Theorems 4.4 and 4.3 (∃ form) it then suffices to check that (a′ a)·(νa. f ) = νa. f for some fresh a′ (so a′# f ,a). Choose some x ∈ νa.X and some fresh b. We reason as follows:

((a′ a)·νa.f)(x) = (b a)·((a′ a)·f)((b a)·(a′ a)·x) Theorem 4.3 (∀form)= (b a)·(a′ a)·f((b a)·x) Proposition 5.7 and Lemma 2.8= (b a)·f((b a)·x). Theorems 2.18 and 2.11= (νa.f)(x) Theorem 4.3 (∃form)End of proof

5.3 Statement and proof of the main result

Lemma 5.10

The following data specifies a pair of functors between FMSet#a and FMSetνa:

• -#a : FMSetνa−→FMSet#a maps X to X#a and f : X −→ Y to f#a : X#a → Y#a.

• -νa : FMSet#a−→FMSetνa maps X to νa.X and f : X −→ Y to νa. f : νa.X → νa.Y.

Proof

By routine calculations.End of proof

Theorem 5.11

-#a and -νa define an isomorphism of categories between FMSet#a and FMSetνa.

Proof

That the functors are inverse on objects follows quickly from Lemma 5.6.

We check that these functors are inverse on arrows. Suppose f : X −→ Y ∈ FMSetνa. So f ∈ X → Y and a# f ,X,Y. We must check that νa.( f#a) = f . Take any x ∈ X and choose some entirely fresh b. We reason as follows:

(νa.(f#a))(x) = (b a)·f((b a)·x) Definition 5.4, Theorem 4.3 (∀form)= f((b a)·(b a)·x) Theorems 2.15 and 2.13= f(x) Lemma 2.8.

Suppose f : X −→ Y ∈ FMSet#a. So f ∈ X#a → Y#a. We must check that (νa. f )#a = f . Take any x ∈ X#a and choose some entirely fresh b. We reason as follows:

(νa.f)#a(x) = (b a)·f((b a)·x) Definition 5.4= (b a)·f(x) Theorem 2.13= f(x) Theorems 2.18 and 2.13.End of proof

6 Conclusions and related work

It is known that the category of nominal sets admits a representation as pullback-preserving presheafs, but abstract categorical presentations of the properties of this ‘nominal’ category that makes it ‘nominal’, have been lacking. There has been quite a lot of interest, especially recently, in more abstract accounts of what ‘nominal’ really is.

As far as I know Menni was the first to think about this, for the И-quantifier [20]. Pitts and Clouston are developing a notion of ‘FM category’ [4]. Kurz and Petrisan are pursuing not dissimilar ideas, coming (speaking very roughly) from the point of view of many-sorted logic and cylindric algebra [18]. Fiore and Hur are developing their own categorical framework [7], of which aspects of nominal techniques are in a certain sense they make formal a special case. There are, of course, other models of of names at a very abstract semantic level; examples include [3] (not strictly speaking categorical) and [15].

Here, this paper could be timely and the observations in it could be of some use; to suggest categorical equivalences to look for in the authors’ respective environments, or indeed directly as a property of the category of FM sets FMSet.

Let me suggest an alternative reading of the results in this paper. FMSet#a and FMSetνa are both categories with ‘an atom missing’. In FMSet#a, the atom is missing because it is fresh for individual data. In FMSetνa, the atom is missing because it is fresh for the objects and arrows. Let us shift our point of view and consider a reading of FMSet as a version of FMSet#a and FMSetνa with an extra atom put in. In that sense, the two notions of freshness considered in this paper correspond to two notions of ‘add a fresh atom’: if we start from FMSet#a and add an atom to the underlying data, we get FMSet; and if we start from FMSetνa and give the language the power to resolve a, we also get FMSet. The main result of this paper is that these two starting-points are isomorphic.

The equivalence of FMSet#a and FMSetνa seems an elegant result. Up to a categorical isomorphism, there is only one way to add/subtract an atom.

References

[1] Nicolas Bourbaki, Théorie des ensembles, Hermann, Paris, 1970.

[2] Norbert Brunner, 75 years of independence proofs by Fraenkel-Mostowski permutation models, Mathematica Japonica 43 (1996), 177–199.

[3] Anna Bucalo, Furio Honsell, Marino Miculan, Ivan Scagnetto, and Martin Hofmann, Consistency of the theory of contexts, Journal of Functional Programming 16 (2006), no. 3, 327–395.

[4] Ranald Clouston, Equational logic for names and binding, Ph.D. thesis, University of Cambridge, UK, 2010, Pending graduation.

[5] 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.

[6] Maribel Fernández and Murdoch J. Gabbay, Nominal rewriting with name generation: abstraction vs. locality, Proceedings of the 7th ACM SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2005), ACM Press, 2005, pp. 47–58.

[7] Marcelo Fiore and Chung-Kil Hur, Term equational systems and logics, Electronic Notes in Theoretical Computer Science 218 (2008), 171–192.

[8] 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.

[9] Murdoch J. Gabbay, A Theory of Inductive Definitions with alpha-Equivalence, Ph.D. thesis, University of Cambridge, UK, 2000.

[10]—, A study of substitution, using nominal techniques and Fraenkel-Mostowski sets, Theoretical Computer Science 410 (2009), no. 12-13, 1159–1189.

[11]—, The mathematical foundations of nominal techniques, (2010), Accepted subject to revision.

[12] 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.

[13] 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.

[14]—, A New Approach to Abstract Syntax with Variable Binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.

[15] 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.

[16] Isabelle/HOL/Nominal, Lemma supp of fin sets, 2009, http://isabelle.in.tum.de/repos/ isabelle/file/Isabelle2009-1/src/HOL/Nominal/Nominal.thy#l2331.

[17] Thomas Jech, Set theory, Springer, 2006, Third edition.

[18] Alexander Kurz and Daniela Petrisan, On universal algebra over nominal sets, Mathematical Structures in Computer Science 20 (2010), 285–318.

[19] 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.

[20] Matias Menni, About И-quantifiers, Applied Categorical Structures 11 (2003), no. 5, 421–445.

[21] Dominic P. Mulligan, Online nominal bibliography, www.citeulike.org/group/11951/, 2010.

[22] Frank Pfenning and Conal Elliott, Higher-order abstract syntax, PLDI (Programming Language Design and Implementation), ACM Press, 1988, pp. 199–208.

[23] Andrew M. Pitts, Nominal logic, a first order theory of names and binding, Information and Computation 186 (2003), no. 2, 165–193.

[24]—, Nominal system T, Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2010), ACM Press, January 2010, pp. 159–170.

[25] Dugald Macpherson Richard Kaye (ed.), Automorphisms of first-order structures, Oxford University Press, 1994.

[26] Mark R. Shinwell, The fresh approach: Functional programming with names and binders, Ph.D. thesis, Computer Laboratory, University of Cambridge, December 2004.

[27] Joseph Shoenfield, Mathematical logic, Addison-Wesley, 1967.

[28] Christian Urban, Nominal reasoning techniques in Isabelle/HOL, Journal of Automatic Reasoning 40 (2008), no. 4, 327–356.

Notes

1Presheaves have a version of support, but in a sense that can be made entirely formal, it is possible for an element to have many distinct supports. See [12] for a more detailed discussion. ↩

2The transitive closure of X is the set containing the elements of X, the elements of the elements of X, and so on. It is the least fixedpoint of the mapping X ↦→ X ∪⋃X. ↩