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

Nominal renaming sets

Murdoch J. Gabbay1 and Martin Hofmann2

1 http://www.gabbay.org.uk 2 http://www.tcs.informatik.uni-muenchen.de/˜mhofmann/

Abstract. Nominal techniques are based on the idea of sets with a finitely-supported atoms-permutation action. We consider the idea of nominal renaming sets, which are sets with a finitely-supported atoms-renaming action; renamings can identify atoms, permutations cannot. We show that nominal renaming sets exhibit many of the useful qualities found in (permutative) nominal sets; an elementary sets-based presentation, inductive datatypes of syntax up to binding, cartesian closure, and being a topos. Unlike is the case for nominal sets, the notion of names-abstraction coincides with functional abstraction. Thus we obtain a concrete presentation of sheaves on the category of finite sets in the form of a category of sets with structure.

Keywords: Nominal renaming sets, nominal sets, abstract syntax with binding.

1 Introduction

The motivation of this work is to provide semantic foundations for formal theories of syntax with variable binding. Several such theories have been proposed in the literature [5,17,16,14,19] and used in concrete applications with varying success [15,4,25,18,21]. All but the most elementary approaches require some semantical or proof-theoretical justification asserting their soundness and also explaining the meaning of the judgements made. Functor categories (categories of (pre)sheaves) are a popular method [7,16,3,8] for providing such foundations. However, proofs involving presheaves are notoriously complicated and require a thorough working knowledge so as to be able to reduce clutter by elision of trivial steps. In some situations [21,25], a sets-based semantics is available in the form of nominal sets [14] which considerably simplifies metatheoretic reasoning. A domains version of nominal sets [20] has also become an important tool in denotational semantics of languages with dynamic allocation [1]

This paper provides a sets-based foundation for another class of systems for higher-order syntax including in particular the theory of contexts [17] which could hitherto only be modelled with functor categories. This will allow us to considerably simplify the cumbersome functor-theoretic proof of soundness of that theory [3]. In this way, we expect that our sets-based presentation of the semantics will then allow to justify further extensions which would until now be too complicated to work through.

Note that we do not propose yet another approach to higher-order syntax. Rather, we introduce a simplified presentation, up to categorical equivalence, of an existing semantic model. We now summarise the contributions of the paper in more detail.

Write I for the category of finite sets and injections between them, write F for the category of finite sets and all (not necessarily injective) functions between them, and write Set for the category of sets3 and functions between them.

Previous work presented nominal sets [13]. These can be presented as the category of pullback-preserving presheaves in SetI. Simultaneously, Fiore et al [7] and Hofmann [16] proposed to use SetF for higher-order abstract syntax. Both can be used as mathematical models for inductive specification and reasoning on syntax with binding.

In SetF for a presheaf F, the presheaf F + given by F +(X) = F(X ∪{x}) for x ∉X is isomorphic to the exponential A ⇒F. In the category of nominal sets the corresponding presheaf is isomorphic to A ⊸F, with ⊸ being the right adjoint to a tensor product different from cartesian product (it is mentioned in Theorem 34 and is written [A]X). In either case the presheaf A is given by A(S) = S. Thus, SetF seems better-suited for modelling higher-order abstract syntax, which uses typings like

lam : (var →tm) →tm (1)

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 [6,17]. In particular, in [3] the presheaf category from [16] was used to establish soundness of the theory of contexts from [17].

FreshML [23] and the deep embeddings of the nominal datatypes package [25] provide a syntactic primitive corresponding to the right adjoint ⊸ mentioned above. They use typings like

lam : (var ⊸tm) →tm. (2)

Precomposing with the canonical map (A→B) −→ (A⊸B), one could justify the typing in (1), but lam would not be injective. For the typing

lam : (tm →tm) →tm (3)

used in the Twelf system [19], another presheaf topos (ˆS in [16]) is adequate. The constructions of this paper cannot be applied to this directly, but see the Conclusions.

The nominal approach benefits from a sets-based presentation. Denotations of types are sets with structure — whence the name ‘nominal sets’ — rather than functors.

In this paper we offer a sets-based presentation of the full subcategory of SetF of functors preserving pullbacks of monos. We present it as a category of sets with a not-necessarily-injective renaming action. The pullback requirement implies that F(X∩Y) is isomorphic to ‘the intersection of’ F(X) and F(Y), in line with the intuition ‘objects with free variables from X’ for F(X). This rules out artefacts present in SetF like F(X) = if |X| > 1 then {⋆} else ∅, which never arise as denotations of types in higher-order abstract syntax.

In [16] it was argued that the internal logic of SetF qua topos might be unsuited to reasoning with higher-order abstract syntax since equality of atoms (names, variables) is not decidable in it. It was proposed in loc. cit. to import the logic of the Schanuel topos using a pullback of triposes. Our presentation of this pullback construction amounts to interpreting predicates as equivariant subsets; subsets of a renaming set stable under injective renamings. Staton and Fiore [8] define a category of substitution sets equivalent to a sheaf subcategory of SetF. Their category is not defined concretely in terms of ordinary sets but as a theory within the Schanuel topos. It does not make SetF easier to work with (and Staton and Fiore never introduced it for that purpose).

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, and in particular, to justify the theory of contexts.

Some notation: This paper uses three different kinds of arrow. For the reader’s convenience we survey their definitions; this is all standard.

− If X and Y are sets then X →Y is the set of functions from X to Y .

− If X and Y are nominal renaming sets then X −→ Y is the set of arrows from X to Y in the category Ren (Definition 5). These are maps in |X| →|Y| with empty support (Lemma 25).

− X ⇒ Y is the exponential (Definition 20 and Theorem 26). These are maps in |X| →|Y| with finite support (Lemma 21).

2 Nominal renaming sets

Definition 1

Fix a countably infinite set of atoms A. We assume that atoms are disjoint from numbers 0, 1, 2, . . ., truth-values ⊥, ⊤, and other standard mathematical entities. A can be viewed as a set of urelemente [2,13,10]; we view them as a model of names or variable symbols.

a, b, c, . . . will range over atoms. We follow a permutative convention that simultaneously introduced metavariables for atoms range permutatively; for example a and b range over any two distinct atoms.4

Definition 2

Let Fin be the set of functions σ ∈ A → A such that there exists some finite S ⊆ A such that for all b ∈ A \ S it is the case that σ(b) = b.

σ, τ will range over elements of Fin. We call these (finitely supported) renamings.

Definition 3

Write [a1↦→y1, . . . , ak↦→yk] for the function that maps ai to yi for 1 ≤ i ≤k and maps all other b (that is, atoms b not in the set {a1, . . . , ak}) to themselves. Note that every function in Fin can be written in this fashion.

In particular, write [a↦→b] for the function which ‘maps a to b’:

[a↦→b](a) = b [a↦→b](b) = b and [a↦→b](c) = c

We write ◦ for functional composition. For example [a↦→b] ◦ [b↦→a] = [a↦→b] (and [a↦→b] ◦ [b↦→a] ≠ [a↦→b, b↦→a]). Write id for the identity renaming. id(a) = a always.

Fin with ◦ and id is a monoid. That is, id ◦σ = σ ◦ id = σ and σ ◦ (σ′ ◦σ′′) = (σ ◦σ′) ◦σ′′. If S ⊆ A and σ ∈ Fin, write σ|S for the partial function equal to σ on S and undefined elsewhere.

Definition 4

A nominal renaming set X is a pair (|X|, ·) of an underlying set |X| and a finitely-supported renaming action ·.

A finitely-supported renaming action · is a map from Fin ×|X| to |X| such that:

− id · x = x always.

−σ′ · (σ · x) = (σ′ ◦σ) · x always.

− For every x ∈|X| there is a finite S ⊆ A such that σ|S = σ′|S implies σ ·x = σ′ ·x.

We say that every x ∈|X| has finite support.

Henceforth X and Y range over nominal renaming sets. x and x′ range over elements of |X| and y and y′ range over elements of |Y| unless stated otherwise.

Definition 5

Nominal renaming sets form a category Ren. Objects are nominal renaming sets. An arrow F : X −→ Y is a function F ∈|X| →|Y| such that σ · F(x) = F(σ · x) always. F, G, H will range over arrows.

For example: A with action σ · a = σ(a) is a nominal renaming set. We have supp(a) = {a}. We will write this renaming set by A, too. In general, we will distinguish notationally between a renaming set X and its underlying set |X|.

Call X trivial when σ·x = x for all x ∈|X| and σ ∈ Fin (so supp(x) = ∅ always). Write B = ({⊤, ⊥}, ·) for a two-element trivial nominal renaming set. We conclude with one more useful definition:

Definition 6

Let X × Y have underlying set |X| × |Y| (that is, z ∈|X × Y| is a pair (x, y) where x ∈ X and y ∈ Y) and pointwise renaming action (that is, σ · (x, y) = (σ · x, σ · y)). Call this the product of X and Y.

2.1 Support of nominal renaming sets

Definition 7

Say S ⊆ A supports x when for all σ, σ′, if σ|S = σ′|S then σ·x = σ′·x.

Lemma 8 and Theorem 9 echo [13, Proposition 3.4]. The proofs for nominal renaming set are simpler:

Lemma 8

If S, S′ ⊆ A support x then so does S ∩S′.

Proof

Suppose σ|S∩S′ = σ′|S∩S′. Define σ′′ ∈ Fin by: σ′′(a) = σ(a) if a ∈S, and σ′′(a) = σ′(a) if a ∈ A \ S. σ′′|S = σ|S so σ′′ · x = σ · x. It is not hard to verify that σ′′|S′ = σ′|S′ so σ′′ · x = σ′ · x. The result follows.

Theorem 9

−x has a unique finite least supporting set supp(x); the support of x.

−σ|supp(x) = σ′|supp(x) implies σ · x = σ′ · x.

Proof

There is a finite S ⊆ A supporting x. The first part follows by Lemma 8. The second part is then by Definition 7.

If the reader thinks of fv (free variables of) when they see supp, they will not go far wrong [13, Example 6.11]. However, support is an abstract notion valid for any element of any nominal renaming set.

As is standard in nominal techniques we write a#x for a ∉ supp(x), and read it as ‘a is fresh for x’. We may write a#x, y for ‘a#x and a#y’, and so on.

Definition 10

Let PFin have underlying set the collection of finite sets of atoms, with pointwise renaming action.

That is, if S ⊆ A is finite then σ · S = {σ(a) | a ∈S}. It is not hard to prove that supp(S) = S always.

Lemma 11

1. supp(σ · x) ⊆σ · supp(x).

2. If σ is injective on supp(x) then supp(σ · x) = σ · supp(x).

Proof

For the first part, we will show that σ · supp(x) supports σ · x. The claim then follows. To see the former suppose that σ1|σ·supp(x) = σ2|σ·supp(x). We then have (σ1◦σ)|supp(x) = (σ2◦σ)|supp(x), hence σ1·σ·x = (σ1◦σ)·x = (σ2◦σ)·x = σ2·σ·x.

For the second part, it suffices to prove the reverse inclusion. Suppose σ|supp(x) = [a1↦→y1, . . . , an↦→yn]|supp(x). By assumption if yi = yj then i = j for 1 ≤i, j ≤n. So we can form σ′ = [y1↦→a1, . . . , yn↦→an]. By Theorem 9 σ′ · σ · x = x. By part 1 of this result supp(σ′ · σ · x) ⊆σ′ · supp(σ · x). Thus, σ · supp(x) = σ · supp(σ′ · σ · x) ⊆ σ · σ′ · supp(σ · x).

Now, if a ∈ supp(σ · x) then by part 1 of this result we can write a = σ(b) for some b ∈ supp(x). So, σ · σ′ · a = σ · σ′ · σ · b = σ · b = a. We have thus shown σ · σ′ · supp(σ · x) ⊆ supp(σ · x) and hence the claim.

We remark that the extra assumption of injectivity for the second part is not redundant.

Corollary 12 helps to calculate support:

Corollary 12

If a ∈ supp(x) then [a↦→b] · x ≠ x. Taking the contrapositive, if [a↦→b] · x = x then a#x. Note that a ≠ b is an implicit assumption.

Proof

By part 1 of Lemma 11 a ∉ supp([a↦→b] · x). We assumed a ∈ supp(x), the result follows.

Lemma 13

S ⊆A supports x if and only if σ|S = id|S implies σ · x = x for all σ.

Proof

The left-to-right implication is direct from the definition of ‘supports’. For the right-to-left implication we will show supp(x) ⊆S. To that end, pick a ∈ supp(x) and b ∉ supp(x). From Corollary 12 we then obtain σ · x ≠ x for σ = [a↦→b]. Hence σ|S ≠ id|S, hence a ∈S.

We need Lemma 14 for Lemma 33 and Corollary 29:

Lemma 14

Suppose c#x and c#x′.

Then [a↦→c] · x = [a′↦→c] · x′ if and only if a′#x and x′ = [a↦→a′] · x.

Proof

Suppose a′#x and x′ = [a↦→a′] · x. We reason as follows:

[a′↦→c] · x′ = [a′↦→c] · [a↦→a′] · x x′ = [a↦→a′] · x= [a↦→c] · x Theorem 9, a′#x

Conversely if [a↦→c] · x = [a′↦→c] · x′ then [c↦→a′] · [a↦→c] · x = [c↦→a′] · [a′↦→c] · x′. By Theorem 9 [c↦→a′] · [a′↦→c] · x′ = x′ and [c↦→a′] · [a↦→c] · x = [a↦→a′] · x. It follows that x′ = [a↦→a′] · x. By similar reasoning x = [a′↦→a] · x′, and by part 1 of Lemma 11 it follows that a′#x.

3 The exponential

Definition 15

Let |X ⇒ Y| be the set of functions f ∈|X| →|Y| such that there exists some finite Sf ⊆ A (for each f, we fix one such Sf) such that for all σ ∈ Fin and x ∈|X| if σ|Sf = id|Sf then

σ · f(x) = f(σ · x). (4)

|X ⇒ Y| serves as an underlying set in Definition 20. First, we consider some examples and prove properties of |X ⇒ Y|.

Remark 16

−π1 ∈|X × Y| →|X| mapping (x, y) to x is in |(X × Y) ⇒ X|.

− The map = ∈|A × A| →|B| mapping (x, y) to ⊤ if x = y and to ⊥ if x ≠ y, is not an element of |(A × A) ⇒ B|. Unpacking definitions, the reason is that there is no finite S ⊆ A such that if σ|S = id|S then for all x, y ∈ A, x = y if and only if σ(x) = σ(y).

− suppX ∈|X| →|PFin| mapping x to supp(x), may or may not be an element of |X ⇒ PFin|. If X = A then supp(a) = {a} and σ · supp(a) = σ · {a} = {σ(a)} = supp(σ(a)). Therefore suppA ∈|A ⇒ PFin|. Similarly for suppPFin.

On the other hand if we let X have |X| = |PFin| (finite sets of atoms) and the renaming action such that σ · S = {σ(a) | a ∈S} if σ|S is injective, and σ · S = ∅ otherwise, then suppX ∉|X ⇒ PFin|.

Remark 17

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.

Elements of |X ⇒ Y| are determined by their ‘asymptotic behaviour’:

Lemma 18

Suppose f ∈|X ⇒ Y| and g ∈|X ⇒ Y|. Suppose also S ⊆ A is finite and assume that for all x ∈|X| if supp(x) ∩S = ∅ then f(x) = g(x). Then f = g.

Proof

Choose any x ∈|X|. There are two cases:

− If supp(x) ∩S = ∅ then by assumption f(x) = g(x).

− If supp(x) ∩S ≠ ∅ then let C = {c1, . . . , ck} be a fresh choice of atoms (so C ∩ (S ∪Sf ∪Sg ∪ supp(x)) = ∅). Let τ = [a1↦→c1, . . . , ak↦→ck] and τ T = [c1↦→a1, . . . , ck↦→ak]. By Lemma 11 supp(τ · x) ∩S = ∅. We reason as follows:

f(x) = f(τ T · τ · x) Theorem 9= τ T · f(τ · x) (4), Definition 15= τ T · g(τ · x) Assumption= g(τ T · τ · x) (4), Definition 15= g(x) Theorem 9

An element f of the function space can be reconstructed from ‘asymptotic’ behaviour:

Lemma 19

Suppose f is a partial function from |X| to |Y|. Suppose S ⊆ A is finite and: supp(x) ∩S = ∅ implies f(x) is defined, and σ|S = id|S implies σ · f(x) = f(σ · x), where both are defined.

Then there is a unique f ′ ∈|X ⇒ Y| extending f (so f ′(x) = f(x) if f(x) is defined).

Proof

First, we define f ′. Consider x ∈|X|, write supp(x) = {a1, . . . , ak} = S. Let C = {c1, . . . , ck} be fresh atoms (so C ∩ supp(x) = ∅= C ∩S). Define

τ = [a1↦→c1, . . . , ak↦→ck] τ T = [c1↦→a1, . . . , ck↦→ak] and f ′(x) = τ T · f(τ · x).

We first show the choice of fresh C does not matter. Suppose C′ = {c′ 1, . . . , c′ k} is also fresh (so C′ ∩ supp(x) = ∅= C′ ∩S). We put τ ′ = [a1↦→c′ 1, . . . , ak↦→c′ k] and τ ′T = [c′ 1↦→a1, . . . , c′ k↦→ak]. We must show τ T · f(τ · x) = τ ′T · f(τ ′ · x). We assume the special case that

C ∩C′ = ∅ and C′ ∩supp(f(τ · x)) = ∅. (5)

The general case follows by two applications of the special case for an ‘even fresher’ set of fresh atoms C′′. We write µ = [c1↦→c′ 1, . . . , ck↦→c′ k] and µT = [c′ 1↦→c1, . . . , c′ k↦→ck]. By Theorem 9 and C ∩ supp(x) = ∅ we have τ ′ · x = µ · τ · x. Also, by C′ ∩S = ∅ we have f(τ ′ · x) = µ · f(τ · x). Therefore τ ′T · f(τ ′ · x) = τ T · µT · µ · f(τ · x).

We recall (5); by Theorem 9 and C′∩supp(f(τ ·x)) = ∅, µT·µ·f(τ ·x) = f(τ ·x). The claim that the choice of fresh C does not matter, follows.

To see that f ′ indeed extends f we suppose that x ∈|X| and that f(x) is defined. Then supp(τ · x) ∩S = ∅ so f(τ · x) is also defined. By assumption on f we have τ T · f(τ · x) = f(τ T · τ · x) = f(x) where the last equality uses Theorem 9.

To see that f ′ ∈|X ⇒ Y| we put Sf ′ = S. Suppose that σ|S = id|S. We have seen that the choice of the fresh C does not matter so that we can assume that τ and τ T commute with σ. We then have σ·f ′(x) = σ·τ T ·f(τ ·x) = τ T ·σ·f(τ ·x) = f ′(σ·x).

Uniqueness of f ′ is now by Lemma 18.

Definition 20

Let X ⇒ Y have underlying set |X ⇒ Y| with renaming action

if σ · x = x then (σ · f)x = σ · f(x). (6)

By Lemma 19 this uniquely determines the renaming action for all x ∈|X|.

Lemma 21

X ⇒ Y is a nominal renaming set.

Proof

f ∈|X ⇒ Y| is supported by the set Sf from Definition 15, for suppose that σ|Sf = id|Sf. By Lemma 13 it suffices to show σ · f = f. Now put S = Sf ∪{b | σ(b) ≠ b}. This is a finite set so by Lemma 18 it suffices to show (σ · f)(x) = f(x) for all x such that supp(x) ∩S = ∅. Fix such an x. By Theorem 9 σ · x = x so by (6) we know (σ · f)(x) = σ · f(x). supp(x) ∩Sf = ∅ by assumption so by (4) we know σ · f(x) = f(σ · x). Then f(σ · x) = f(x) since σ · x = x. The result follows.

Theorem 22

σ · f(x) = (σ · f)(σ · x), for f ∈|X ⇒ Y|.

Proof

Write supp(f) ∪ supp(σ · f) ∪{a | σ(a) ≠ a} = {a1, . . . , ak}. Choose fresh C = {c1, . . . , ck}, so C ∩ (supp(x) ∪Sf ∪Sσ·f) = ∅ and σ|C = id|C. Define

τ = [a1↦→c1, . . . , ak↦→ck] τ T = [c1↦→a1, . . . , ck↦→ak] π = [a1↦→c1, c1↦→a1, . . . , ak↦→ck, ck↦→ak] σ′ = π ◦σ ◦π.
Then: (τ T ◦σ′ ◦τ)|supp(x) = σ|supp(x)C ∩supp(x) = ∅ (7)τ T ◦σ′ ◦σ = σ ◦τ Tσ(c)=c for all c∈C (8)(τ T ◦σ′)|Sσ·f = id|Sσ·fBy construction (9)
So: (σ · f)(σ · x) = (σ · f)((τ T ◦σ′) · τ · x) Th. 9 and (7)= (τ T ◦σ′) · (σ · f)(τ · x) (9) and (4), Def. 15= (τ T ◦σ′) · σ · f(τ · x) (9) and (6), Def. 20= (σ ◦τ T) · f(τ · x) (8)= σ · f(τ T · τ · x) (4), Def. 15= σ · f(x) Theorem 9
Corollary 23

If f∈|X⇒Y| then the following are equivalent:

− For all x ∈|X| and σ ∈ Fin, if σ|S = id|S then σ·f(x) = f(σ·x).

− supp(f) ⊆S.

Proof

If σ|supp(f) = id|supp(f) then by Theorems 22 and 9, σ·f(x) = (σ·f)(σ·x) = f(σ · x).

Now suppose S ⊆ A and for all x ∈|X| if σ|S = id|S then σ·f(x) = f(σ·x). If we show that S supports f then by the ‘unique least’ property of support (Theorem 9) we are done. Suppose σ|S = id|S and take any x ∈|X| such that σ|supp(x) = id|supp(x):

f(x)Theorem 9= f(σ · x)Assumption= σ · f(x)Theorem 22= (σ · f)(σ · x)Theorem 9= (σ · f)(x).

By Lemma 18 σ · f = f as required.

Compare Corollary 24 with [13, Example 4.9, (24)]:

Corollary 24

supp(f(x)) ⊆ supp(f) ∪ supp(x) always, for f ∈|X ⇒ Y|.

Proof

Using Theorems 22 and 9.

Lemma 25

Arrows F : X −→ Y are exactly f ∈|X ⇒ Y| such that supp(f) = ∅.

Proof

F : X −→ Y is a map in |X| →|Y|. By definition σ · F(x) = F(σ · x). By Corollary 23, supp(F) = ∅. Conversely if f ∈|X ⇒ Y| and supp(f) = ∅ then f is a map in |X| →|Y|. Also, σ · f(x) = f(σ · x) by Theorems 22 and 9.

Theorem 26

- ⇒ - is an exponential in Ren.

Proof

We show that currying and uncurrying are arrows between (X × Y) −→ Z and X −→ (Y ⇒ Z). The βη equations are then inherited. Currying: Take F ∈ (X × Y) −→ Z. For x ∈ X we put Fx = (λy∈|Y|.F(x, y)). We show that λx∈|X|.Fx ∈ X −→ (Y ⇒ Z):

If x ∈|X| we put SFx = supp(x). If σ|supp(x) = id|supp(x) then σ · Fx(y) = F(σ · x, σ · y) = F(x, σ · y) = Fx(σ · y), so Fx ∈|X ⇒ Y|.

To see that x↦ →Fx is an arrow pick arbitrary σ. We need to show σ · Fx = Fσ·x. Appealing to Lemma 18 we choose y ∈ Y with σ · y = y and supp(y) disjoint from supp(x) = supp(Fx). We then have (σ · Fx)(y) = σ · F(x, σ · y) = σ · F(x, y) = F(σ · x, σ · y) = F(σ · x, y) = Fσ·x(y). Uncurrying: Take G ∈ X −→ (Y⇒Z). We show that λ(x, y)∈|X × Y|.G(x)(y) ∈ (X × Y) −→ Z:

It suffices to show that σ · G(x)(y) = G(σ · x)(σ · y). Now σ · G(x)(y) = (σ · G(x))(σ · y) by Theorem 22 and σ · G(x) = G(σ · x) by Definition 5.

Lemma 27 does for Ren what [13, Lemma 6.3] does for the category of nominal sets. We can develop similar inductive and recursive principles for syntax-with-binding as are exhibited using the Gabbay-Pitts N-quantifier in Theorem 6.5 in [13].

Lemma 27

There is a bijection between F : (A × X) −→ Y such that a#F(a, x) always, and G ∈ (A ⇒ X) −→ Y.

Proof

We define mappings as follows:

−F maps to λf ∈|A ⇒ X|.Na. F(a, fa) where (as is standard [13]) Na. F(a, fa) is equal to F(a, fa) for any a such that a#f.

−G maps to λ(a, x) ∈|A × X|.G(λy∈A.[a↦→y] · x).

We can prove this is well-defined, and the result follows by calculations.

4 The atoms-exponential A ⇒ X

Lemma 28

If f ∈|A ⇒ X| then f = λy∈A.[a↦→y] · x for some x ∈|X| and a#f.

Proof

By Definition 20 f ∈|A ⇒ X| when f ∈|A| →|X| and there is a finite S ⊆ A such that σ ∈ Fin, a ∈ A, and σ|S = id|S imply σ · f(a) = f(σ(a)). Choose a ∉S and y ∈ A. Then f(y) = f([a↦→y] · a) = [a↦→y] · f(a), and we take x = f(a).

Two functions on atoms are equal if they agree for one fresh atom; compare this for example with axiom (Extτ ν) in the theory of contexts [17, Figure 4] and the extensionality principle for concretion of the Gabbay-Pitts model of atoms-abstraction in nominal sets [13, Proposition 5.5, equation (48)]:

Corollary 29

Suppose f, f ′ ∈|A ⇒ X| and suppose c#f and c#f ′. Then f(c) = f ′(c) if and only if f = f ′.

Proof

The right-to-left implication is easy. Assume f(c) = f ′(c). By Lemma 28

• there exist x ∈|X| and a ∈ A such that a#f and f = λy∈A.[a↦→y] · x, and

• there exist x′ ∈|X| and a′ ∈ A such that a′#f ′ and f ′ = λy∈A.[a′↦→y] · x′.

We assumed that f(c) = f ′(c) so [a↦→c] · x = [a′↦→c] · x′. By Lemma 14 a′#x and x′ = [a↦→a′] · x. Choose any y ∈ A. We reason as follows:

f ′(y) = [a′↦→y] · x′f ′ = λy∈A.[a′↦→y] · x′= [a′↦→y] · [a↦→a′] · x. x′ = [a↦→a′] · x= [a↦→y] · x Theorem 9, a′#x
Lemma 30

Suppose f ∈|A ⇒ Y|. Then a#f if and only if a#f(b), for any b#f (by our permutative convention, b ≠ a).

Equivalently, supp(f) = supp(f(b)) \ {b} for any b#f.

Proof

We prove two implications. Choose any b#f.

If a#f then by Corollary 24 a#fb and we are done. Suppose that a#f(b). We have assumed b#f so by Corollary 12 it suffices to prove [a↦→b]·f = f. Choose a fresh c (so c#f and c#[a↦→b] · f). By Corollary 29 it suffices to check that f(c) = ([a↦→b] · f)(c). Note that by Corollary 24 a#f(c). We reason as follows:

fc = [a↦→b] · f(c) Theorem 9 and Corollary 24= ([a↦→b] · f)([a↦→b] · c) Theorem 22= ([a↦→b] · f)c [a↦→b] · c = c
Lemma 31

λy∈A.[a↦→y]·x is supported by supp(x); thus λy∈A.[a↦→y]·x∈|A⇒X|.

Proof

The corollary is immediate given the first part, by Definition 15. We now prove that supp(x) supports λy∈A.[a↦→y]·x. By Corollary 23 it suffices to show σ|supp(x) = id|supp(x) implies σ · λy∈A.[a↦→y] · x = λy∈A.[a↦→y] · x.

So suppose σ|supp(x) = id|supp(x). By Corollary 29 it suffices to check

(σ · λy∈A.[a↦→y] · x)c = (λy∈A.[a↦→y] · x)c

for fresh c. Choose c such that c#σ · λy∈A.[a↦→y] · x, c#λy∈A.[a↦→y] · x, σ(c) = c and c#x. By Theorem 22 since σ(c) = c we have that

σ · ((λy∈A.[a↦→y] · x)c) = (σ · λy∈A.[a↦→y] · x)c.

So it suffices to check that σ·[a↦→c]·x = [a↦→c]·x. We assumed σ|supp(x) = id|supp(x) and c#x. It follows that (σ ◦ [a↦→c])|supp(x) = [a↦→c]|supp(x). By Theorem 9 the result follows.

Corollary 32

supp(λy∈A.[a↦→y] · x) = supp(x) \ {a}.

Proof

Choose some fresh b (so b#λy∈A.[a↦→y] · x and b#x). By Lemma 31 λy∈A.[a↦→y] · x ∈|A ⇒ X|. Therefore by Lemma 30 we know that

supp(λy∈A.[a↦→y] · x) = supp([a↦→b] · x) \ {b}.

Since b#x by part 2 of Lemma 11 supp([a↦→b] · x) = (supp(x) \ {a}) ∪{b}.

Lemma 33

Suppose x, x′∈ |X|, and a, a′∈ A. Then λy∈A.[a↦→y] · x = λy∈A.[a′↦→y] · x′ if and only if a′#x and x′ = [a↦→a′] · x.

Proof

Using Lemma 14 and Corollary 29.

The reader may recognise these results from the theory of the Gabbay-Pitts model of atoms-abstraction in nominal sets [13, Definition 5.4]. A nominal renaming set is also a nominal permutation set (by ‘forgetting’ the action for non-bijective σ); using Corollary 12 it can be proved [11, Theorem 4.8] that the notions of support coincide. In the spirit of [13, (35)] we can write5 [a]x = {(a, x)} ∪{(c, [a↦→c] · x) | c#x} and |[A]X| = {[a]x | a ∈ A, x ∈|X|}. The proof of Theorem 34 is now routine [11, Theorem 5.7]:

Theorem 34

|A ⇒ X| is in bijective correspondence with |[A]X|. Inverse mappings are given by:

−α maps z ∈|[A]X| to λy∈A.[a↦→y] · x, for (a, x)∈z.

−β maps f ∈|A ⇒ X| to [a](fa), for a#f.

5 Presheaf and topos structure of Ren

For convenience, take the finite sets in I and F from the Introduction to be finite S ⊆A.

We could now go on and exhibit the subobject classifier in Ren, thus establishing that Ren is a topos, and hence is a model of higher-order logic. This is not hard to do: a subobject classifier is the renaming set Ω with underlying set |Ω| those U ⊆ Fin such that:

− If σ ∈U then µ ◦σ ∈U for all µ ∈ Fin.

− There exists finite S ⊆ A such that µ ∈U and σ|S = id|S imply µ ◦σ ∈U.

The renaming action is given by σ · U = {µ | µ ◦σ ∈U}. The proof that this makes Ren into a topos is by standard calculations. We also remark that Ren is a Grothendieck topos for a topology on the opposite of the category of finite sets and functions and thus a full subcategory of the functor category SetF. The required topology has for basic covers of an object X nonempty families of monos fi : X −→Xi. The interested reader is referred to [24] where a proof of a similar result is worked out.

We now characterise Ren as a category of presheaves.

Definition 35

Let PBM be the category of presheaves in SetF that preserve pullbacks of pairs of monos, and natural transformations between them.

If f ∈X →Y is a function let its image img(f) be {f(x) | x ∈X} ⊆Y . Note that monos in F and Ren are injections, and that a pullback of a pair of monos is given by set intersection with the natural inclusion maps. Write ‘ι : S ⊆S′’ for “S ⊆S′ and we write ι for the subset inclusion arrow in F”.

Definition 36

Fix F ∈ PBM. Let (S, x) range over pairs where S ⊆ A is finite and x ∈F(S). Write ∼ for the least equivalence relation such that ι : S ⊆S′ implies (S, x) ∼ (S′, F(ι)(x)).

Lemma 37

If ι1 : S1 ⊆S′ and ι2 : S2 ⊆S′ and (S1, x1) ∼ (S′, x′) ∼ (S2, x2) then there exists some x ∈F(S1 ∩S2) such that (S1 ∩S2, x) ∼ (S′, x′). Thus, each ∼-equivalence class has a unique least representative (S, x), ‘least’ in the sense that if (S, x) ∼ (S′, x′) then ι : S ⊆S′ and x′ = F(ι)(x).

Theorem 38

Ren is equivalent to PBM.

Proof

X maps to FX mapping S ∈F to {x ∈|X| | supp(x) ⊆S} and mapping τ : S →S′ to the renaming action of τ extended to a total function which is the identity off S. This is a presheaf by part 1 of Lemma 11 and we can prove that it preserves pullbacks of monos using Lemma 8. F maps to the set of unique least representative elements of ∼-equivalence classes, as constructed in Lemma 37 with action given by τ · (S, x) is the representative of the ∼-equivalence class of (τ · S, F(τ|S)(x)). The result follows by routine calculations.

Preserving pullbacks of monos, and the corollary that we have ‘least representatives’, makes possible the sets-based presentation of nominal sets and nominal renaming sets, contrasting with the purely presheaf-based presentations of [7,16].

6 Tripos structure on Ren

As argued in [16] the topos logic of F, thus also that of Ren, is unsuited to reasoning about syntax with binding. For example equality of atoms is not decidable in that logic. In fact, in the topos logic of Ren and F, the proposition ∀x, y∈A.¬¬(x=y) holds.

It was proposed in [16] to use the tripos obtained by pulling back the logic from the Schanuel topos instead. In particular, the tripos so obtained is needed to justify the theory of contexts [17] (well — almost; the restriction to pullback-preserving functors had not been made explicit in that paper.)

In keeping with our goal of making these constructions concrete and usable for direct calculations, we make this construction explicit at the level of Ren.

Definition 39

For a nominal renaming set X let Pred(X) be the set of those subsets U of |X| that are preserved by bijective renamings, i.e., for which x ∈U implies σ·x ∈U provided that σ ∈ Fin is bijective, i.e., a permutation.

Pred(X) is ordered by subset inclusion and Pred(−) extends to a functor Renop → Poset where Pred(f)(U) = {x | f(x) ∈U} when f : X → Y and U ∈ Pred(Y).

We remark that in the topos logic of Ren a predicate is a subset preserved by all renamings, not just the bijective ones.

Theorem 40 is a consequence of the folklore result stated in [16] which asserts that triposes can be pulled back along finite-limit-preserving functors with a right adjoint (‘geometric morphisms’). Rather than detailing this argument we illustrate the tripos structure by concrete constructions below.

Theorem 40

The pair (Ren, Pred) forms a tripos.

This means there is enough structure to interpret higher-order logic. In particular, predicates are closed under boolean operations, universal quantification over renaming sets, and there is a renaming set O of propositions such that morphisms X → O are in 1-1 correspondence with elements of Pred(X). We explicitly construct these ingredients in order to demonstrate that the logic for Ren is quite close to classical set-theoretic reasoning in contrast to the functorial reasoning that was used in [17].

Proposition 41

The object of propositions O in the tripos (Ren, Pred) has underlying set those U ⊆ Fin such that:

− If σ ∈U and π ∈ Fin is a permutation then π ◦σ ∈U

− There exists finite S ⊆ X such that if σ|S = σ′|S then σ ∈U iff σ′ ∈U.

The renaming action in O is given by σ · U = {µ | µ ◦σ ∈U}.

Proof (Sketch).

If P ∈ Pred(X) then a morphism χP : X → O is defined by χP (a) = {σ | σ · a ∈P}. Conversely, if m : X → O is a morphism then we associate the predicate Pm = {a | m(a) = ⊤} where ⊤∈ O is given by ⊤= Fin.

Proposition 42

The logic of (Ren, Pred) is classical.

Proof

It suffices to show that if P ∈ Pred(X) is a predicate then its set-theoretic complement {x | x ∉P} is again a predicate. But if π ∈ Fin is a permutation and x ∉P then π · x ∉P for otherwise x = π-1 · π · x ∈P.

Proposition 43 (universal quantification).

Let P ∈ Pred(X × Y) (possibly given by a morphism X × Y → O). Its universal quantification ∀P ∈ Pred(X) is given by ∀P = {x | ∀y∈Y.(x, y) ∈P}.

Proof

Suppose that Q ∈ Pred(X). We have to show that ∀P is a predicate and that the following are equivalent:

− for all x ∈ X and y ∈ Y if x ∈Q then (x, y) ∈P

− for all x ∈ X if x ∈Q then x ∈∀P

The equivalence being obvious from the definition it only remains to show that ∀P is indeed a predicate. So assume that π ∈ Fin is a permutation and consider that x ∈∀P. If y ∈ Y then (x, π-1 · y) ∈P since x ∈∀P. So, (π · x, y) ∈P since P is a renaming set. Hence, since y was arbitrary, π · x ∈∀P as required.

Logical operations in (Ren, Pred) are given by their standard meanings in classical set theory. Propositions are elements of O rather than of {0, 1}. Note that the axiom of unique choice (which identifies functional relations with morphisms) is not valid in (Ren, Pred). Indeed, a functional relation, i.e., a predicate P on X×Y such that for all x ∈|X| there is a unique y ∈|Y| such that (x, y) ∈P, does not in general give rise to a morphism from X to Y. Indeed, in [16] it was shown that the Axiom of Unique Choice is an inconsistent extension of the theory of contexts. There is a unique function f such that (x, f(x)) ∈P for all x ∈|X| but in general it will be invariant under permutations, not all renamings.

7 Conclusions

Nominal renaming sets are a natural evolution of nominal sets. The connection between Ren and the category of nominal sets [13] is evident. However, the details are not entirely straightforward; proofs have to be changed and sometimes they take on a very different character. In particular the definition of the action for function spaces in the permutative case (σ · f)(x) = σ-1 · f(σ · x) does not carry over, because σ-1 need not exist. It is replaced by an a priori partial definition (Definition 20) which is totalised with a unique extension theorem (Lemma 19).

Nominal renaming sets are related to SetF as featured in [7] and [16]; they correspond to the pullback-preserving presheaves (Theorem 38). Ren has appeared before; the first author discussed the idea in his thesis [9, Section 11.1] and studied a generalisation of nominal renaming sets as an algebraic theory over nominal sets in [12]. Meanwhile, a category equivalent to Ren was independently presented, also as an algebraic theory over nominal sets, in [8, Definition 2.4]. The constructions presented in this paper, notably the exponential and the tripos structure, are new and do not follow directly from these earlier results. It is thanks to these explicit constructions that Ren can serve as a sets-based semantic underpinning for weak HOAS, i.e. that we can do calculations entirely within Ren, without switching to a functor category. To our knowledge, we are the first to suggest applying renaming sets as a semantic basis for weak HOAS in the sense of Despeyroux [5] and in particular the theory of contexts [17].

Future work.

It will be interesting to give details of a proof of validity of the theory of contexts using nominal renaming sets. In this conference paper we have not done that, but such a proof could be based on the one in [17], and should be simplified thanks to the use of set-theoretic language (most of the time). Note that no notion of forcing is required.

Nominal sets have been generalised to ‘nominal domains’ [22] thus giving access to fresh names in denotational semantics. It would be interesting to generalise renaming sets in this way as well, giving access to fresh names with substitution within a functional metalanguage. Here, our explicitation of the exponential (Section 3) may be particularly useful.

Nominal renaming sets belong to a family of structures with a finitely supported substitution action. Probably they are the simplest, but others may also be interesting. For example, define a nominal substitution set to be a pair of a nominal renaming set X and a function sub : ((A ⇒ X) × X) ⇒ X such that

− If a#z then z[a↦→x] = z.

− If a#y then z[a↦→x][b↦→y] = z[b↦→y][a↦→x[b↦→y]].

Here we write z[a↦→x] for sub(λy∈A.[a↦→y]·z, x). A category of nominal substitution sets has arrows maps F : X −→ Y such that F(z[a↦→x]) = (F(z))[a↦→F(x)].

(This can also be phrased directly using ‘normal’ sets.) We conjecture that this definition or a refinement of it will be useful to give semantics to typings like (tm → tm) → tm used for binders, for example in Twelf [19], for which hitherto only purely presheaf semantics are available [16].

References

1. Nick Benton and Benjamin Leperchey. Relational reasoning in a nominal semantics for storage. In Pawel Urzyczyn, editor, TLCA, volume 3461 of Lecture Notes in Computer Science, pages 86–101. Springer, 2005.

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

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

4. Joelle Despeyroux. A higher-order specification of the π–calculus. In IFIP TCS, pages 425–439, 2000.

5. Joëlle Despeyroux, Amy P. Felty, and André Hirschowitz. Higher-order abstract syntax in COQ. In TLCA’95, volume 3461 of Lecture Notes in Computer Science, pages 124–138, 1995.

6. Joëlle Despeyroux and André Hirschowitz. Higher-order abstract syntax with induction in COQ. In LPAR’94, volume 822 of Lecture Notes in Computer Science, pages 159–173. Springer, 1994.

7. Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi. Abstract syntax and variable binding. In LICS’99, pages 193–202. IEEE, 1999.

8. Marcelo P. Fiore and Sam Staton. A congruence rule format for name-passing process calculi from mathematical structural operational semantics. In LICS’06, pages 49–58. IEEE, 2006.

9. Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.

10. Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205:982–1011, July 2007.

11. Murdoch J. Gabbay. Nominal renaming sets. Technical Report HW-MACS-TR-0058, Heriot-Watt University, 2007.

12. Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC, volume 4281 of Lecture Notes in Computer Science, pages 198–212, 2006.

13. Murdoch J. Gabbay and A. M. Pitts. A New Approach to Abstract Syntax with Variable Binding (journal version). Formal Aspects of Computing, 13(3–5):341–363, 2001.

14. Murdoch J. Gabbay and Andrew M. Pitts. A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, 1999.

15. Daniel Hirschkoff. A full formalization of pi-calculus theory in the Calculus of Constructions. In E. Gunter and A. Felty, editors, Proceedings of TPHOLs’97, pages 153–169, Murray Hill, 1997.

16. Martin Hofmann. Semantical analysis of higher-order abstract syntax. In 14th Annual Symposium on Logic in Computer Science, pages 204–213. IEEE, 1999.

17. Furio Honsell, Marino Miculan, and Ivan Scagnetto. An axiomatic approach to metareasoning on nominal algebras in HOAS. In ICALP’01, volume 2076, pages 963–978. Lecture Notes in Computer Science, 2001.

18. James McKinna and Robert Pollack. Some lambda calculus and type theory formalized. Journal of Automated Reasoning, 23(3-4):373–409, 1999.

19. Frank Pfenning and Carsten Schürmann. System description: Twelf - a meta-logical framework for deductive systems. In CADE’16, volume 1632 of Lecture Notes in Computer Science, pages 202–206. Springer, 1999.

20. M. R. Shinwell. The Fresh Approach: Functional Programming with Names and Binders. PhD thesis, Computer Laboratory, University of Cambridge, December 2004.

21. M. R. Shinwell, A. M. Pitts, and Murdoch J. Gabbay. FreshML: Programming with binders made simple. In ICFP’2003, volume 38(9) of SIGPLAN Not., pages 263–274. ACM Press, 2003.

22. Mark R. Shinwell and Andrew M. Pitts. On a monadic semantics for freshness. Theoretical Computer Science, 342(1):28–55, 2005.

23. M.R. Shinwell and A.M. Pitts. Fresh objective Caml user manual. Technical Report UCAM-CL-TR-621, University of Cambridge, 2005.

24. Sam Staton. Name-passing process calculi: operational models and structural operational semantics. PhD thesis, University of Cambridge, 2007.

25. Christian Urban and Christine Tasson. Nominal techniques in Isabelle/HOL. In CADE’05, volume 3632 of Lecture Notes in Artificial Intelligence, pages 38–53, 2005.

Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.

Notes

3 It is convenient, but not necessary, to take this to be the category of ‘ordinary’ ZF sets (not mentioning atoms). Since we are working at the meta-level, this is in fact not important and any sufficiently rich collection of collections of elements will do. ↩

4 Note that we are working in the usual naïve set-theoretic metalanguage; atoms form a set. At that level, atoms have a decidable equality. ↩

5 The use of [a↦→c] instead of the swapping (a c) (swapping defined in [13, (3)]) is immaterial because c#x and so the actions coincide by Theorem 9. ↩