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

Nominal renaming sets (technical report)

Murdoch J. Gabbay

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 f(x) and fx.

• a̸∈ supp(x) (‘a is not in the support of x’) and a#x (‘a is fresh for x’) have the same meaning (Remark 2.14).

2 Nominal renaming sets

2.1 Definitions and important results

We use standard sets notation; X, Y, Z range over sets of elements and x ∈X means ‘x is in X’. Note that x, y, . . . ∈X means ‘x, y, . . . are in X’. If X and Y are sets then X →Y is the set of all functions from elements of X to elements of Y . This arrow should not be confused with two other arrows which come later: −→ (arrows in a category) and ⇒ (exponentials).

Definition 2.1

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 a, b, c, . . . range over atoms.

We will adhere to a permutative convention that a, b, c range permutatively over atoms, so for example a and b range over any two distinct atoms and a̸=b always.

Remark 2.2

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 ‘x’ and ‘y’ are two distinct variable symbols. Later a valuation might associate x and y to the same value, or a subtitution might substitute x and y for the same term. Then, we might write ‘x = y’. 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.

Remark 2.3

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.

Definition 2.4

Let Fin be the set of functions σ ∈ 𝔸 → 𝔸 such that there exists some finite S ⊆ 𝔸 such that

for all b ∈ 𝔸 \ S it is the case that σ(b) = b.

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

Definition 2.5

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.

Write [a⊢→ b] for the function such that

[a⊢→ b](a) = b [a⊢→ b](b) = b and [a⊢→ b](c) = c.

Call this an atomic renaming. Intuitively, [a⊢→ b] ‘maps a to b’.

Write (a b) for the function such that

(a b)(a) = b (a b)(b) = a (a b)(c) = c.

Consistent with [14], call this a swapping. Intuitively, (a b) ‘swaps a and b’.

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.

Lemma 2.6

Fin with ∘ and id is a monoid.

Proof

That is, id ∘σ = σ ∘ id = σ and σ ∘ (σ′ ∘σ′′) = (σ ∘σ′) ∘σ′′. This follows by elementary properties of functional composition.End of proof

Definition 2.7

If S ⊆ 𝔸 and σ ∈ Fin, write σ|S for the partial function defined by

• σ|S(a) = a if a ∈S.

• σ|S(a) is undefined if a ∈ 𝔸 \ S.

Note that if σ′ ∈ Fin then

σ|S = σ′|Smeans for all a ∈𝔸, if a ∈S then σ(a) = σ′(a).
Definition 2.8

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

A finitely-supported renaming action ⋅ is a function from Fin × |𝕏| to |𝕏| such that:

• id ⋅x = x for all x ∈|𝕏|.

• σ′ ⋅ (σ ⋅x) = (σ′ ∘σ) ⋅x for all x ∈|𝕏| and σ′, σ ∈ Fin.

• For every x ∈|𝕏| there exists some finite S ⊆ 𝔸 such that for all σ, σ′ ∈ Fin if σ|S = σ′|S then σ ⋅x = σ′ ⋅x. We say that every x ∈|𝕏| has finite support.

Remark 2.9

Some jargon: a nominal renaming set 𝕏 is a set with a finitely-supported Fin-monoid action.

Remark 2.10

supp(x) coincides with ‘the variables in’ if x is abstract syntax; if the reader thinks of fv(t) every time they see supp(x), 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

Definition 2.11

Suppose that 𝕏 is a nominal renaming set and x ∈|𝕏|. Say that S ⊆ 𝔸 supports x when for all σ, σ′ ∈ Fin, if σ|S = σ′|S then σ ⋅x = σ′ ⋅x.

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:

Lemma 2.12

Suppose that 𝕏 is a nominal renaming set and suppose that x ∈|𝕏|. If S ⊆ 𝔸 supports x and S′ ⊆ 𝔸 supports x then S ∩S′ supports x.

Proof

Suppose that S ⊆ 𝔸 and S′ ⊆ 𝔸. Suppose that σ|S∩S′ = σ′|S∩S′. Define σ′′ ∈ Fin by

• σ′′(a) = σ(a) if a ∈S.

• σ′′(a) = σ′(a) if a ∈ 𝔸 \ S.

σ′′|S = σ|S so σ′′ ⋅x = σ ⋅x. Also it is not hard to verify that σ′′|S′ = σ′|S′ so σ′′ ⋅x = σ′ ⋅x. The result follows.End of proof

Theorem 2.13

Suppose that 𝕏 is nominal renaming set and suppose x ∈|𝕏|.

• There exists a unique least set of atoms supporting x, and that set is finite. Write it supp(x) and call it the support of x.

• Suppose that σ ∈ Fin and σ′ ∈ Fin. Then if σ|supp(x) = σ′|supp(x) then σ ⋅x = σ′ ⋅x.

Proof

By assumption there exist some finite S ⊆ 𝔸 supporting x. The first part follows immediately using Lemma 2.12. The second part also follows immediately using Definition 2.11.End of proof

Remark 2.14

Consistent with other work we write a#x to mean a̸∈ supp(x) and read this as ‘a is fresh for x’. We may also write a#x, y to mean ‘a#x and a#y’, and so on.

Definition 2.15

Let PFin be the nominal renaming set such that:

• |PFin| is the collection of finite sets of atoms.

• If S ⊆ 𝔸 is finite and σ ∈ Fin then

σ ⋅S = {σ(a) | a ∈S}.

As is standard, we call this the pointwise renaming action.

It is not hard to prove that supp(S) = S always. The following result generalises a known property of nominal permutation sets:

Lemma 2.16

Recall the definition of σ ⋅S from Definition 2.15. Suppose that 𝕏 is nominal renaming set and suppose x ∈|𝕏| and σ ∈ Fin. Then:

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

2. If σ is injective on supp(x), that is, if

a ∈supp(x) and y ∈supp(x) and σ(y) = σ(a) imply y = a

then

supp(σ ⋅x) = σ ⋅supp(x).
Proof

1. Suppose that σ′(a) = a for all a ∈σ ⋅ supp(x). Then (σ′ ∘ σ)|supp(x) = σ|supp(x). By assumption σ′ ⋅ (σ ⋅x) = (σ′ ∘σ) ⋅x. By Theorem 2.13 (σ′ ∘σ) ⋅x = σ ⋅x. The result follows.

2. By part 1 of this result supp(σ ⋅x) ⊆σ ⋅ supp(x). We need only prove the reverse inclusion; this is routine: Suppose that σ|supp(x) = [a1⊢→y1, . . . , an⊢→yn]. By assumption if yi = yj then i = j for 1 ≤i, j ≤n. So we can write σ′ = [y1⊢→a1, . . . , yn⊢→an]. By Theorem 2.13 σ′ ⋅σ ⋅x = x. By part 1 of this result supp(σ′ ⋅σ ⋅x) ⊆ σ′ ⋅σ ⋅ supp(x). But σ′ ⋅σ ⋅ supp(x) = supp(x) by construction, so we are done.End of proof

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 σ ⋅a = σ(a) is a nominal renaming set. supp(a) = {a}.

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 𝕏 = (|𝕏|, ⋅) trivial when σ ⋅x = x for all x ∈|𝕏| and σ ∈ Fin.

Then 𝔹 = ({⊤, ⊥}, ⋅) and ℕ = ({0, 1, 2, . . .}, ⋅), both with the trivial renaming actions, are nominal renaming sets. supp(x) = ∅ 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.

Definition 2.17

Call S ⊆ 𝔸 cofinite when 𝔸 \ S is finite.

The set of cofinite subsets of 𝔸 is a nominal renaming set with action given by

σ ⋅S = 𝔸\ (σ ⋅(𝔸\ S))

is a nominal renaming set. It is not hard to verify that supp(S) = 𝔸 \ S always.

For example, [a⊢→ b] ⋅ (𝔸 \ {a, b}) = 𝔸 \ {b}. 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. supp(S) = S if S is finite, and supp(S) = 𝔸 \ S if S 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 σ ⋅S = {σ(a) | a ∈S}, but this action is not finitely-supported.

For example if we write 𝔸 = {a1, a2, a3, a4, . . .} and let A = {a2i | 1 ≤i}

— so A is ‘every other atom’ — then A 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:

Lemma 2.18

There exists a nominal renaming set 𝕏, x ∈|𝕏|, and σ ∈ Fin such that supp(σ ⋅x) ̸=σ ⋅ supp(x).

Proof

It suffices to find an example. Consider PFinexploding specified by:

• |PFinexploding| is the set of all finite subsets of 𝔸.

• σ ⋅exploding S = {σ(a) | a ∈S} if {σ(a) | a ∈S} has the same cardinality as S (that is, if σ|S is injective as a function out of S).

• σ ⋅exploding S = ∅ otherwise (that is, if there exist a ∈S and b ∈S such that σ(a) = σ(b)).

It is not hard to verify that this is a nominal renaming set, and supp(S) = S.

Note that

[a⊢→ b] ⋅supp({a, b}) = [a⊢→ b] ⋅{a, b} = {b} andsupp([a⊢→ b] ⋅exploding {a, b}) = supp(∅) = ∅,

and ∅̸= {b}.End of proof

I call this behaviour ‘exploding’ because, for example, {a, b, c} ‘explodes’ like a balloon when ‘pricked’ by the non-injective function [a⊢→ b].

Suppose 𝕏 is a nominal renaming set, suppose σ ∈ Fin, and suppose x ∈|𝕏|. If σ is injective on supp(x) then its action is invertible in the sense that if we are given σ ⋅x and σ then we can uniquely deduce what x 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 supp(x) then its action need not be invertible. For example σ acts pointwise on finite S ⊆ 𝔸 (Definition 2.15) and

[a⊢→ b] ⋅{a, b} = {b} = [a⊢→ b] ⋅{b}.

So given {b} and [a⊢→ b], there is no unique finite S ⊆ 𝔸 such that [a⊢→ b]⋅S = {b}.

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.

Definition 2.19

Let D be a (possibly infinite) indexing set. Let 𝕏I for I ∈D be an D-indexed collection of nominal renaming sets. Write (xI)I∈D or just (xI) for a D-tuple of elements xI ∈|𝕏I|. For example (xI)I∈{1,2} is an ordered pair. ΠI∈D|𝕏I| (the set of all D-tuples of elements from |𝕏I|) inherits a pointwise renaming action given by σ ⋅ (xI) = (σ ⋅xI).

Lemma 2.20

1. (xI) need not have finite support in general.

2. (xI) has finite support if and only if there exists some finite S ⊆ 𝔸 such that supp(xI) ⊆S for all I ∈D.

Proof

1. Let D = 𝔸 and consider the tuple (aI) — the tuple of all atoms, in some order. It is not hard to prove that this has no finite supporting set.

2. Suppose that S ⊆ 𝔸 is finite and supports (xI). Suppose that I′ ∈D; we show that S supports xI′. If σ|S = id|S then σ ⋅(xI) = (xI). By definition σ ⋅ (xI) = (σ ⋅xI), so σ ⋅xI′ = xI′. It follows that S supports xI′. Now suppose that S ⊆ 𝔸 is finite and supports xI for every I ∈D. By a similar calculation it is easy to verify that S supports (xI).End of proof

Using notation and terminology from Definition 2.19 and Lemma 2.20 we define:

Definition 2.21

Let D be a (possibly infinite) indexing set. Let 𝕏I for I ∈D be a D-indexed collection of nominal renaming sets. Then let ΠI∈D𝕏I be the nominal renaming set with:

• |ΠI∈D𝕏I| is those (xI) ∈ ΠI∈D|𝕏I| with finite support. That is, xI ∈|𝕏I| for each I ∈D and there exists some finite S ⊆ 𝔸 such that for all I ∈D it is the case that supp(xI) ⊆S.

• Pointwise renaming action. That is, σ ⋅ (xI) = (σ ⋅xI).

2.4 Renaming action vs. atomic renaming action

Recall from Definition 2.5 the atomic renaming [a⊢→ b] ∈ Fin which maps a to b, and swapping (a b) ∈ Fin which swaps a and b.

Lemma 2.22

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.

Proof

Atomic renamings are not injective. A functional composition of non-injective functions is also non-injective. The swapping (a b) is injective, so no functional composition of atomic renamings can generate a swapping.End of proof

In spite of Lemma 2.22 atomic renamings are enough to construct Sub, in a suitable formal sense:

Theorem 2.23

Suppose that 𝕏 = (|𝕏|, ⋅) and 𝕏′ = (|𝕏′|, ⋅′) are nominal renaming sets with the same underlying set (so |𝕏| = |𝕏′|). Suppose that for all atomic renamings [a⊢→ b] and all x ∈|𝕏| it is the case that

[a⊢→ b] ⋅x = [a⊢→ b] ⋅′ x.

Then for all σ ∈ Fin and all x ∈|𝕏| it is the case that

σ ⋅x = σ ⋅′ x,

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.

Proof

Suppose that [a⊢→ b] ⋅x = [a⊢→ b] ⋅′ x always. Suppose that x ∈|𝕏| and choose any σ ∈ Fin. We wish to show that σ ⋅x = σ ⋅′ x.

Now suppose that x ∈|𝕏| and σ ∈ Fin. Write supp(x) = {c1, . . . , ck}. Choose some fresh {c′ 1, . . . , c′ k} (so c′ i#x and σ(c′ i) = c′ i for 1 ≤i ≤k). Define

τ = [c1⊢→c′ 1, . . . , ck⊢→c′ k] and τ ′ = [c′ 1⊢→σ(c1), ⋅⋅⋅ , ck⊢→σ(ck)].

Note that

τ = [c1⊢→c′ 1] ∘⋅⋅⋅ ∘[ck⊢→c′ k] and τ ′ = [c′ 1⊢→σ(c1)] ∘⋅⋅⋅ ∘[c′ k⊢→σ(ck)].

That is, both τ and τ ′ can be expressed as functional compositions of atomic renamings. Also, by Theorem 2.13

(τ ′ ∘τ) ⋅x = σ ⋅x.

The result follows.End of proof

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.

Corollary 2.24

Suppose that 𝕏 is a nominal renaming set and suppose that x ∈|𝕏|. If a ∈ supp(x) and c̸∈ supp(x) then [a⊢→ c] ⋅x̸=x.

Taking the contrapositive, if there exists some c#x such that [a⊢→ c] ⋅x = x, then a#x.

Proof

By part 1 of Lemma 2.16

supp([a⊢→ c] ⋅x) ⊆[a⊢→ c] ⋅supp(x) = (supp(x) \ {a}) ∪{c}.

In particular,

a̸∈ (supp[a⊢→ c] ⋅x).

Since we assumed that a ∈ supp(x), the result follows.End of proof

Lemma 2.25 is useful for proving Lemma 5.6 and Corollary 5.2:

Lemma 2.25

Suppose that 𝕏 is a nominal renaming set, x, x′ ∈|𝕏|, and a, a′ ∈ 𝔸. Suppose that c#x and c#x′.

Then [a⊢→ c] ⋅x = [a′⊢→c] ⋅x′ if and only if a′#x and x′ = [a⊢→ a′] ⋅x.

Proof

Note that by our permutative convention, c, a, and a′ are all distinct.

Suppose that a′#x and x′ = [a⊢→ a′] ⋅x. Then we reason as follows:

[a′⊢→c] ⋅x′ = [a′⊢→c] ⋅[a⊢→ a′] ⋅x x′ = [a⊢→ a′] ⋅x= [a⊢→ c] ⋅x Theorem 2.13, a′#x

Conversely suppose that [a⊢→ c] ⋅x = [a′⊢→c] ⋅x′. Then

[c⊢→ a′] ⋅[a⊢→ c] ⋅x = [c⊢→ a′] ⋅[a′⊢→c] ⋅x′.

By Theorem 2.13

[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 we have that x = [a′⊢→a] ⋅x′. By Lemma 2.16 it then follows that a′#x.End of proof

3 Nominal renaming sets and the exponential

Recall from Subsection 2.1 that |𝕏| →|𝕐| is the set of functions from the set |𝕏| to the set |𝕐|.

Definition 3.1

Suppose that 𝕏 and 𝕐 are nominal renaming sets. Let |𝕏 ⇒ 𝕐| be the set of functions f ∈|𝕏| →|𝕐| such that there exists some finite Sf ⊆ 𝔸 (for each f, we fix one such Sf) such that for all σ ∈ Fin and x ∈|𝕏| if σ|Sf = id|Sf then

σ ⋅f(x) = f(σ ⋅x). (1)

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 |𝕏 ⇒ 𝕐|.

Remark 3.2

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 π1 ∈|𝕏 × 𝕐| →|𝕏| mapping (x, y) to x is in |(𝕏 × 𝕐) ⇒ 𝕏|.

2. The map =∈|𝔸 × 𝔸| →|𝔹| mapping (x, y) to ⊤ if x = y and mapping (x, y) to ⊥ if x̸=y, is not an element of |(𝔸 × 𝔸) ⇒ 𝔹|. This is because there is no finite set S such that if σ|S = id|S then for all x, y ∈ 𝔸 it is the case that x = y if and only if σ(x) = σ(y).

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 supp𝕏∈|𝕏| →|PFin| mapping x to supp(x), is sometimes an element of |𝕏 ⇒ PFin| — and sometimes not. In the case that 𝕏 = 𝔸 then supp(a) = {a} and

σ ⋅supp(a) = σ ⋅{a} = {σ(a)} = supp(σ(a)).

Therefore supp𝔸∈|𝔸 ⇒ PFin|. Similarly for suppPFin 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 supp𝕏∈|𝕏 ⇒ PFin|. Taking the example from the proof of Lemma 2.18 we note that for any finite S ⊆ 𝔸 we can take a, b̸∈ S and

[a⊢→ b]⋅supp({a, b}) = {b} whereas supp([a⊢→ b]⋅exploding{a, b}) = supp(∅) = ∅.
Remark 3.3

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:

Lemma 3.4

Suppose that f ∈|𝕏 ⇒ 𝕐| and g ∈|𝕏 ⇒ 𝕐|. Suppose that S ⊆ 𝔸 is finite and assume that for all x ∈|𝕏| if supp(x) ∩S = ∅ (‘asymptotic’ is in the sense of ‘supp(x) ∩S = ∅’) then f(x) = g(x). Then f = g.

Proof

Without loss of generality (extending S with Sf ∪Sg if necessary) we may suppose that if supp(x) ∩S = ∅ then

σ ⋅f(x) = f(σ ⋅x) and σ ⋅g(x) = g(σ ⋅x).

Now choose any 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 = ∅). Let

τ = [a1⊢→c1, . . . , ak⊢→ck] and τ -1 = [c1⊢→a1, . . . , ck⊢→ak].

By Lemma 2.16 we know that supp(τ ⋅x) ∩S = ∅. By Theorem 2.13 we know that x = τ -1 ⋅τ ⋅x. Therefore we reason as follows:

f(x) = f(τ -1 ⋅τ ⋅x) Theorem 2.13= τ -1 ⋅f(τ ⋅x) (1), Definition 3.1= τ -1 ⋅g(τ ⋅x) Assumption= g(τ -1 ⋅τ ⋅x) (1), Definition 3.1= g(x) Theorem 2.13

The result follows.End of proof

Following on from Lemma 3.4, a total function can be uniquely reconstructed from its ‘asymptotic’ behaviour:

Lemma 3.5

Suppose that f ∈|𝕏| ⇀ |𝕐| is a partial function from |𝕏| to |𝕐|. Suppose also that there exists some finite S ⊆ 𝔸 such that:

• For all x ∈|𝕏| if supp(x) ∩S = ∅ then f(x) is defined.

• For all σ such that σ|S = id|S, if f(x) and f(σ ⋅x) are both defined then σ ⋅ f(x) = f(σ ⋅x).

Then there exists a unique total function f ′ ∈|𝕏 ⇒ 𝕐| extending the partial function f, in the sense that f ′(x) = f(x) if f(x) is defined.

Proof

The proof splits into three parts:

1. The statement of the definition of f ′.

2. A proof that the statement is well-defined.

3. A proof that f ′ is unique.

We consider each part in turn:

1. Statement of the definition of f ′.

Consider any x ∈|𝕏|. Suppose supp(x) = {a1, . . . , ak}. There are two cases:

• If supp(x) ∩S = ∅ then we set

f ′(x) = f(x).

• If supp(x) ∩S̸=∅ then let C = {c1, . . . , ck} be a choice of fresh atoms (so C ∩S = ∅ and C ∩ supp(x) = ∅). Let

τ = [a1⊢→c1, . . . , ak⊢→ck] and τ -1 = [c1⊢→a1, . . . , ck⊢→ak].

We set

f ′(x) = τ -1 ⋅f(τ ⋅x).

2. Proof that the statement is well-defined.

We must show that the choice of fresh C does not matter. Suppose that C′ = {c′ 1, . . . , c′ k} is some other choice of fresh atoms (so C′ ∩S = ∅ and C′ ∩ supp(x) = ∅). Write

τ ′ = [a1⊢→c′ 1, . . . , ak⊢→c′ k] and τ ′-1 = [c′ 1⊢→a1, . . . , c′ k⊢→ak].

We must show that

τ -1 ⋅f(τ ⋅x) = τ ′-1 ⋅f(τ ′ ⋅x)

Without loss of generality we assume the special case that

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

The general case then 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 μ-1 = [c′ 1⊢→c1, . . . , c′ k⊢→ck].

By Theorem 2.13 and our assumption that C′ ∩ supp(x) = ∅, we know that τ ′ ⋅x = μ ⋅τ ⋅x. Also, by our assumption that C′ ∩S = ∅, we know that f(τ ′ ⋅x) = μ ⋅f(τ ⋅x). It follows that

τ ′-1 ⋅f(τ ′ ⋅x) = τ -1 ⋅μ-1 ⋅μ ⋅f(τ ⋅x).

By Theorem 2.13 and our assumption that C′∩supp(f(τ ⋅x)) = ∅ it follows that

μ-1 ⋅μ ⋅f(τ ⋅x) = f(τ ⋅x).

The result follows.

3. Proof that f ′ is unique.

This follows from Lemma 3.4.End of proof

Definition 3.6

If 𝕏 and 𝕐 are nominal renaming sets let 𝕏 ⇒ 𝕐 be specified as follows:

• |𝕏 ⇒ 𝕐| is defined in Definition 3.1.

• We specify a renaming action by

(σ ⋅f)x = σ ⋅f(x) (2)

for x ∈|𝕏| such that supp(x) ∩Sf = ∅ (Sf fixed in Definition 3.1). By Lemma 3.5 the renaming action is uniquely specified for all x ∈|𝕏|.

Theorem 3.7

Suppose that 𝕏 and 𝕐 are nominal renaming sets, x ∈|𝕏|, and f ∈|𝕏 ⇒ 𝕐|.

Then σ ⋅ f(x) = (σ ⋅f)(σ ⋅x) always.

As an immediate corollary if σ ⋅x = x then (σ ⋅f)x = σ ⋅ f(x).

Proof

Write supp(x) = {a1, . . . , ak}. Make some choice of fresh C = {c1, . . . , ck} — so that

• C ∩ supp(x) = ∅.

• C ∩Sf = ∅.

• C ∩Sσ⋅f = ∅.

• σ(c) = c for all c ∈C.

Let

τ = [a1⊢→c1, . . . , ak⊢→ck] and τ -1 = [c1⊢→a1, . . . , ck⊢→ak].

Define σ′ by

• σ′(ci) = cj if 1 ≤i ≤k and σ(ai) ̸=ai and σ(ai) = aj.

• σ′(y) = y otherwise.

We now note three equalities in (3), (4), and (5). Because C ∩ supp(x) = ∅ is easy to verify that

(τ -1 ∘σ′ ∘τ)|supp(x) = σ|supp(x). (3)

Because σ(c) = c for all c ∈C, and by the construction of σ′, we have that

τ -1 ∘σ′ ∘σ = σ ∘τ -1. (4)

By construction

(τ -1 ∘σ′)|Sσ⋅f = id|Sσ⋅f . (5)

Then we reason as follows:

(σ ⋅f)(σ ⋅x) = (σ ⋅f)((τ -1 ∘σ′) ⋅τ ⋅x) Theorem 2.13 and (3) = (τ -1 ∘σ′) ⋅(σ ⋅f)(τ ⋅x) (5) and (1), Definition 3.1 = (τ -1 ∘σ′) ⋅σ ⋅f(τ ⋅x) (5) and (2), Definition 3.6 = (σ ∘τ -1) ⋅f(τ ⋅x) (4) = σ ⋅f(τ -1 ⋅τ ⋅x) (1), Definition 3.1 = σ ⋅f(x) Theorem 2.13End of proof
Corollary 3.8

Suppose that 𝕏 and 𝕐 are nominal renaming sets. Suppose that f ∈|𝕏 ⇒ 𝕐|. Then S ⊆ 𝔸 is such that

for all x ∈|𝕏| if σ|S = id|S then σ ⋅f(x) = f(σ ⋅x)

if and only if supp(f) ⊆S.

Proof

Suppose σ|supp(f) = id|supp(f). By Theorems 3.7 and 2.13 we have

σ ⋅f(x) = (σ ⋅f)(σ ⋅x) = f(σ ⋅x)

for any x ∈|𝕏|.

Conversely suppose that S ⊆ 𝔸 is such that for all 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 2.13) we are done. Suppose that σ|S = id|S. By Theorem 3.7

σ ⋅f(x) = (σ ⋅f)(σ ⋅x).

By assumption

σ ⋅f(x) = f(σ ⋅x).

By Theorem 2.13 if supp(x) ∩S = ∅ then σ ⋅x = x. So for all x such that supp(x) ∩S = ∅ we have that

(σ ⋅f)x = fx.

It follows by Lemma 3.4 that σ ⋅f = f, as required.End of proof

Compare Corollary 3.9 with [14, Example 4.9, (24)].

Corollary 3.9

Suppose that 𝕏 and 𝕐 are nominal renaming sets. Suppose that x ∈|𝕏| and f ∈|𝕏 ⇒ 𝕐|. Then

supp(f(x)) ⊆supp(f) ∪supp(x).
Proof

Suppose that σ|supp(f)∪supp(x) = σ′|supp(f)∪supp(x). Using Theorem 3.7 and Theorem 2.13 we easily calculate that σ ⋅f(x) = σ′ ⋅f(x).End of proof

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]:

Definition 4.1

Let Per be the set of bijective functions from 𝔸 to 𝔸 (permutations) such that there exists some finite S ⊆ 𝔸 such that

for all b ∈ 𝔸 \ S it is the case that π(b) = b.

π, π′ will range over elements of Per. We call these (finitely supported) permutations.

Lemma 4.2

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.

Proof

Routine.End of proof

Definition 4.3

A nominal permutation set ℙ is a pair (|ℙ|, ⋅) of an underlying set |ℙ| and finitely-supported permutation action ⋅.

A finitely-supported permutation action ⋅ is a function from Per × |ℙ| to |ℙ| such that:

• id ⋅x = x for all x ∈|ℙ|.

• π′ ⋅ (π ⋅x) = (π′ ∘π) ⋅x for all x ∈|𝕏| and π′, π ∈ Per. (So ⋅ is a group action.)

• For every x ∈|ℙ| there exists some finite S ⊆ 𝔸 such that for all π ∈ Per and π′ ∈ Per, if π|S = π′|S then π ⋅x = π′ ⋅x. We say that every x ∈|ℙ| has finite support.

Definition 4.4

Suppose that ℙ is a nominal permutation set and x ∈|ℙ|. Say that S ⊆ 𝔸 supports x when for all π ∈ Per and π′ ∈ Per, if π|S = π′|S then π ⋅x = π′ ⋅x.

Remark 4.5

A nominal permutation set ℙ is a set with a finitely-supported Per-group action.

Lemma 4.6

If 𝕏 is a nominal renaming set then (|𝕏|, ⋅) where ⋅ is restricted to Per, is a nominal permutation set.

Proof

Routine.End of proof

Lemma 4.7

supp(x) from Theorem 2.13 (the minimal set of atoms that supports x as an element of a nominal renaming set) is a subset of S from Definition 4.3 (a set of atoms that supports x as an element of a nominal permutation set).

Proof

If supp(x) = ∅ the result is immediate. Suppose that a ∈ supp(x) (that is, suppose that a#x does not hold). Choose fresh c (so c#x and c̸∈ T).

Recall swappings (a c) (Definition 2.5). By Theorem 2.13 [a⊢→ c]⋅x = (a c)⋅x. By Corollary 2.24 [a⊢→ c]⋅x̸=x. It follows that (a c)⋅x̸=x. Therefore a ∈S.End of proof

Theorem 4.8

Suppose that S ⊆ 𝔸 is finite. Suppose that |𝕏| is a nominal renaming set and suppose that x ∈|𝕏|.

Then S supports x in the sense of Definition 4.3 (considering x as an element of a nominal permutation set) if and only if S supports x in the sense of Definition 2.8 (considering x as an element of a nominal renaming set).

Proof

We must show that

for all π, π′ ∈Per, if π|S = π′|S then π ⋅x = π′ ⋅x,

if and only if

for all σ, σ′ ∈Fin, if σ|S = σ′|S then σ ⋅x = σ′ ⋅x.

The bottom-to-top implication is immediate from Lemma 4.2. The top-to-bottom implication is an easy corollary of Lemma 4.7.End of proof

Remark 4.9

An informal corollary of Theorem 4.8, which can be made formal, is this:

If 𝕏 is a nominal renaming set and x ∈|𝕏| 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(x)’ and use results about support such as Theorem 2.13 and Lemma 2.16 without concern for whether we consider x as acted on by Fin (all renamings) or we consider x as acted on by Per (only permutations).

4.2 The Gabbay-Pitts (nominal) model of abstraction

Definition 4.10

Suppose 𝕏 is a nominal renaming set and suppose x ∈|𝕏| and a ∈ 𝔸. Define

[a]x = {(a, x)} ∪{(c, [a⊢→ c] ⋅x) | c#x}.

Define |[𝔸]𝕏| by

|[𝔸]𝕏| = {[a]x | a ∈𝔸, x ∈|𝕏|}.

A renaming action will follow in Definition 5.11. Recall from Definition 2.5 that the swapping (a b) in the function on atoms which swaps a and b.

Remark 4.11

By Theorem 2.13 if c#x then (a c) ⋅x = [c⊢→ a] ⋅x. 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.

Lemma 4.12

Suppose that 𝕏 is a nominal renaming set. Suppose that x, x′ ∈ |𝕏|, and suppose that a, a′ ∈ 𝔸.

Then [a]x = [a′]x′ if and only if a′#x and x′ = [a⊢→ a′] ⋅x.

Proof

By calculations from [14, Lemma 5.1].End of proof

Lemma 4.13

Suppose that 𝕏 is a nominal renaming set, suppose x ∈|𝕏|, and suppose that a, b ∈ 𝔸 and b#x. Then

[a]x = [b]((b a) ⋅x) = [b]([a⊢→ b] ⋅x).
Proof

By calculations from [14, Lemma 5.1], and by Theorem 2.13.End of proof

Lemma 4.14

Suppose that 𝕏 is a nominal renaming set and suppose z ∈ |[𝔸]𝕏|. Then if (a, x) ∈z then z = [a]x.

Proof

By calculations from [14, Lemma 5.1].End of proof

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.

Lemma 5.1

For every f ∈|𝔸 ⇒ 𝕏| there exists some x ∈|𝕏| and a#f such that f = λy∈𝔸. [a⊢→ y] ⋅x.

Proof

We unpack Definition 3.6. f ∈|𝔸 ⇒ 𝕏| when f ∈|𝔸| →|𝕏| and there exists some finite S ⊆ 𝔸 such that for all σ ∈ Fin and a ∈ 𝔸, if σ|S = id|S then σ ⋅ f(a) = f(σ(a)).

Choose a̸∈ S and any y ∈ 𝔸. Then

f(y) = f([a⊢→ y] ⋅a) = [a⊢→ y] ⋅f(a).

So take x = f(a) and we are done.End of proof

Corollary 5.2

Suppose that 𝕏 is a nominal renaming set. Suppose that f ∈ |𝔸 ⇒ 𝕏| and f ′ ∈|𝔸 ⇒ 𝕏| and suppose that c#f and c#f ′.

Then fc = f ′c if and only if f = f ′.

Proof

The right-to-left implication is immediate. So assume that fc = f ′c. By Lemma 5.1

• there exists some x ∈|𝕏| and a ∈ 𝔸 such that a#f and f = λy∈𝔸. [a⊢→ y]⋅ x, and

• there exists some x′ ∈|𝕏| and a′ ∈ 𝔸 such that a′#f ′ and f ′ = λy∈𝔸. [a′⊢→y] ⋅x′.

We assumed that fc = f ′c so [a⊢→ c] ⋅x = [a′⊢→c] ⋅x′. By Lemma 2.25

a′#x and x′ = [a⊢→ a′] ⋅x.

Choose any y ∈ 𝔸. We reason as follows:

f ′y = [a′⊢→y] ⋅x′f ′ = λy∈𝔸. [a′⊢→y] ⋅x′= [a′⊢→y] ⋅[a⊢→ a′] ⋅x. x′ = [a⊢→ a′] ⋅x= [a⊢→ y] ⋅x Theorem 2.13, a′#xEnd of proof
Lemma 5.3

Suppose that f ∈|𝕏 ⇒ 𝕐|.

Then a#f if and only if a#fb, for any b#f (by our permutative convention, b̸=a).

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

Proof

We prove two implications. Choose any b#f.

If a#f then by Corollary 3.9 a#fb and we are done. Suppose that a#fb. We have assumed b#f so by Corollary 2.24 it suffices to prove [a⊢→ b] ⋅f = f. Choose a fresh c (so c#f and c#[a⊢→ b] ⋅f). By Corollary 5.2 it suffices to check that fc = ([a⊢→ b]⋅f)(c). Note that by Corollary 3.9 a#fc. We reason as follows:

fc = [a⊢→ b] ⋅(fc) Theorem 2.13 and Corollary 3.9= ([a⊢→ b] ⋅f)([a⊢→ b] ⋅c) Theorem 3.7= ([a⊢→ b] ⋅f)c [a⊢→ b] ⋅c = cEnd of proof
Lemma 5.4

Suppose that 𝕏 is a nominal renaming set and suppose that x ∈ |𝕏| and a ∈ 𝔸.

Then λy∈𝔸. [a⊢→ y] ⋅x is supported by supp(x). As a corollary, λy∈𝔸. [a⊢→ y] ⋅x ∈|𝔸 ⇒ 𝕏|.

Proof

Unpacking Definition 3.1, λy∈𝔸. [a⊢→ y] ⋅x ∈|𝔸 ⇒ 𝕏| when

• λy∈𝔸. [a⊢→ y] ⋅x ∈ 𝔸 →|𝕏| — this is true by construction — and

• λy∈𝔸. [a⊢→ y] ⋅x has a finite supporting set.

Therefore, the corollary is immediate given the first part. We now prove that supp(x) supports λy∈𝔸. [a⊢→ y] ⋅x.

By Corollary 3.8 it suffices to show that for all σ ∈ Fin

σ|supp(x) = id|supp(x)implies σ ⋅λy∈𝔸. [a⊢→ y] ⋅x = λy∈𝔸. [a⊢→ y] ⋅x.

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

(σ ⋅λy∈𝔸. [a⊢→ y] ⋅x)c = (λy∈𝔸. [a⊢→ y] ⋅x)c

for fresh c. So choose c such that

c#σ ⋅λy∈𝔸. [a⊢→ y] ⋅x, c#λy∈𝔸. [a⊢→ y] ⋅x, σ(c) = c, and c#x.

We assumed that σ(c) = c so using Theorem 3.7 it suffices to check that

σ ⋅[a⊢→ c] ⋅x = [a⊢→ c] ⋅x.

Now we assumed that σ|supp(x) = id|supp(x) and c̸∈ supp(x). It follows that (σ ∘ [a⊢→ c])|supp(x) = [a⊢→ c]|supp(x). By Theorem 2.13 the result follows.End of proof

Corollary 5.5

Suppose that 𝕏 is a nominal renaming set and suppose that x ∈|𝕏|. Then supp(λy∈𝔸. [a⊢→ y] ⋅x) = supp(x) \ {a}.

Proof

Choose some fresh b (so b#λy∈𝔸. [a⊢→ y] ⋅x and b#x). By Lemma 5.4 λy∈𝔸. [a⊢→ y] ⋅x ∈|𝔸 ⇒ 𝕏|. Therefore by Lemma 5.3 we know that

supp(λy∈𝔸. [a⊢→ y] ⋅x) = supp([a⊢→ b] ⋅x) \ {b}.

Since b#x by Theorem 2.13 [a⊢→ b] ⋅x = (b a) ⋅x. By part 2 of Lemma 2.16 supp((a b) ⋅x) = (supp(x) \ {a}) ∪ {b}. The result follows.End of proof

Lemma 5.6

Suppose that 𝕏 is a nominal renaming set, x, x′ ∈|𝕏|, and a, a′ ∈ 𝔸.

Then λy∈𝔸. [a⊢→ y] ⋅x = λy∈𝔸. [a′⊢→y] ⋅x′ if and only if a′#x and x′ = [a⊢→ a′] ⋅x.

(Here y ∈ 𝔸 and y may be equal to a or a′. By our permutative convention a̸=a′.)

Proof

Choose some fresh c (so c#x, c#x′, and c̸=a and c̸=a′).

If λy∈𝔸. [a⊢→ y] ⋅x = λy∈𝔸. [a′⊢→y] ⋅x′ then [a⊢→ c] ⋅x = [a′⊢→c] ⋅x′. By Lemma 2.25 a′#x and x′ = [a⊢→ a′] ⋅x and we are done.

Conversely if a′#x and x′ = [a⊢→ a′] ⋅x then by Lemma 2.25 [a⊢→ c] ⋅x = [a′⊢→c] ⋅x′. Now by Theorem 2.13

[c⊢→ y] ⋅[a⊢→ c] ⋅x = [a⊢→ y] ⋅x and [c⊢→ y] ⋅[a′⊢→c] ⋅x′ = [a′⊢→y] ⋅x′,

for any y ∈ 𝔸. The result follows.End of proof

If 𝕏 is a nominal renaming set then nominal abstractions [𝔸]𝕏 (Definition 4.10) and function-spaces 𝔸 ⇒ 𝕏 are related in a very strict sense:

Theorem 5.7

|𝔸 ⇒ 𝕏| is in bijection with |[𝔸]𝕏|. The mutually inverse mappings are given by:

• α maps z ∈|[𝔸]𝕏| to λy∈𝔸. [a⊢→ y] ⋅x, for (a, x) ∈z.

• β maps f ∈|𝔸 ⇒ 𝕏| to [a](fa), for a#f.

Proof

Given our results so far, proving this is not hard. We show that α and β are well-defined:

• α is well-defined. Suppose that (a, x) ∈z and (a′, x′) ∈z (recall that by our permutative convention a̸=a′). By Lemma 4.12 a′#x and x′ = [a⊢→ a′] ⋅x. By Lemma 5.6 λy∈𝔸. [a⊢→ y] ⋅x = λy∈𝔸. [a′⊢→y] ⋅x′.

• β is well-defined. Suppose that a#f and b#f. By Lemma 4.13 [a](fa) = [b]([a⊢→ b] ⋅ (fa)). Since a#f by (1) from Definition 3.1

[a⊢→ b] ⋅(fa) = f([a⊢→ b] ⋅a).

The result follows.

We show that α is injective and surjective:4

• α is surjective.

Suppose f ∈|𝔸 ⇒ 𝕏|. By Lemma 5.1 there exists some x ∈|𝕏| and a#f such that f = λy∈𝔸. [a⊢→ y] ⋅x. By construction (a, x) ∈ [a]x so by construction α([a]x) = f.

• α is injective.

Suppose that (a, x) ∈z and (a′, x′) ∈z′ and λy∈𝔸. [a⊢→ y] ⋅x = λy∈𝔸. [a′⊢→y]⋅x′. By Lemma 5.6 a′#x and x′ = [a⊢→ a′]⋅x. By Lemma 4.12

it follows that [a]x = [a′]x′ as required.

Finally, we prove that α and β are mutually inverse:

• α followed by β is the identity.

Suppose that z ∈|[𝔸]𝕏| and (a, x) ∈z. Then α(z) = λy∈𝔸. [a⊢→ y] ⋅x. By Corollary 5.5 a#α(z), so

β(α(z)) = [a]([a⊢→ a] ⋅x) = [a]x.

By Lemma 4.14 we are done.

• β followed by α is the identity. Suppose that f ∈|𝔸 ⇒ 𝕏| and a#f. Then β(f) = [a](fa). By construction (a, fa) ∈ [a](fa) so that

α(β(f)) = λy∈𝔸. [a⊢→ y] ⋅(fa).

By (1) from Definition 3.1

[a⊢→ y] ⋅(fa) = f([a⊢→ y] ⋅a) = f(y).

The result follows.End of proof

Remark 5.8

From previous work [14, 10] we know that if ℙ is a nominal permutation set then |[𝔸]ℙ| has a permutation action. It is given by π ⋅ [a]x = [π(a)]π ⋅x. 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:

Definition 5.9

Write a#σ when

• σ(a) = a and

• for all y ∈ 𝔸 \ {a} it is the case that σ(y) ̸=a.

Remark 5.10

a#σ is merely a convenient notation; we do not give a renaming action to Fin.

Definition 5.11

If 𝕏 is a nominal renaming set let [𝔸]𝕏 be defined by:

• The underlying set of [𝔸]𝕏 is |[𝔸]𝕏| from Definition 3.1.

• σ ⋅ [a]x = [a]σ ⋅x provided that a#σ.

Lemma 5.12

The renaming action in Definition 5.11 is total and well-defined.

Proof

We must show that:

• The renaming action is total. That is, for every z ∈|[𝔸]𝕏| there exists some a ∈ 𝔸 and x ∈|𝕏| such that z = [a]x and a#σ.

• The renaming action is well-defined. If [a]x = [a′]x′ and a#σ and a′#σ then [a]σ ⋅x = [a′]σ ⋅x′.

We consider each point in turn.

• By construction if z ∈|[𝔸]𝕏| then there exist a ∈ 𝔸 and x ∈|𝕏| such that z = [a]x. By Lemma 4.13 we may assume (renaming a to be fresh if necessary) that a#σ.

• We reason as follows:

[a]σ ⋅x = σ ⋅[a]x = σ ⋅[a′]x′ = [a′]σ ⋅x′.End of proof

We need a technical lemma for Theorem 5.14:

Lemma 5.13

If a#σ and c#σ then [a⊢→ c] ∘σ = σ ∘ [a⊢→ c].

Proof

By unpacking Definition 5.9 and by elementary calculations.End of proof

Theorem 5.14

α and β from Theorem 5.7 are arrows in Sub (Definition 7.1). That is, suppose that 𝕏 is a nominal renaming set and suppose that z ∈|[𝔸]𝕏|. Then:

• σ ⋅α(f) = α(σ ⋅f).

• σ ⋅β(z) = β(σ ⋅z).

Furthermore, the renaming action on |[𝔸]𝕏| (Definition 5.11) is that induced by the renaming action on |𝔸 ⇒ 𝕏| via the isomorphism expressed by α and β. That is,

σ ⋅z = β(σ ⋅(α(z))).
Proof

We shall show that

σ ⋅α(f) = α(σ ⋅f).

Choose some fresh a (so a#f and a#σ). Since a#σ by Definition 5.9 σ(a) = a. Therefore by Theorem 3.7 we have that (σ ⋅f)a = σ ⋅ (fa) and so

α(f) = [a](fa) α(σ ⋅f) = [a]σ ⋅(fa).

By Definition 5.11 σ ⋅ [a](fa) = [a]σ ⋅ (fa), and we are done.

We shall show that

σ ⋅β(f) = β(σ ⋅f).

We unpack definitions:

β([a]x) = λy∈𝔸. [a⊢→ y] ⋅x β([a]σ ⋅x) = λy∈𝔸. [a⊢→ y] ⋅σ ⋅x.

We wish to show that

σ ⋅λy∈𝔸. [a⊢→ y] ⋅x = λy∈𝔸. [a⊢→ y] ⋅σ ⋅x.

By Corollary 5.2 it suffices to check this for a fresh c (so c#σ ⋅λy∈𝔸. [a⊢→ y] ⋅x, c#λy∈𝔸. [a⊢→ y] ⋅σ ⋅x, and c#σ). We reason as follows:

(σ ⋅λy∈𝔸. [a⊢→ y] ⋅x)c = σ ⋅[a⊢→ c] ⋅x Theorem 3.7 and σ(c) = c= [a⊢→ c] ⋅σ ⋅x a#σ, c#σ, Lemma 5.13= (λy∈𝔸. [a⊢→ y] ⋅σ ⋅x)c

We have just proved that σ ⋅ β(z) = β(σ ⋅z). We apply α to both sides and use Theorem 5.7 and the previous parts of this result to conclude

σ ⋅z = β(σ ⋅(α(z)))

as required.End of proof

We make one final ‘sanity check’ calculation about the relationship between [𝔸]𝕏 and 𝔸 ⇒ 𝕏.

Theorem 5.15

In previous work [14, 10] |[𝔸]𝕏| was endowed with a permutation action specified by

π ⋅[a]x = [π(a)]π ⋅x.

The renaming action σ ⋅ [a]x from Definition 5.11 coincides with this definition when σ ∈ Per.

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.

Proof

According to Definition 5.11, if π ∈ Per and a#π (Lemma 5.13) then π ⋅ [a]x = [a]π ⋅x. Also, it is a fact that if a#π then π(a) = a. Therefore if a#π then π ⋅ [a]x = [π(a)]π ⋅x as required.

So suppose that a#π is false. Choose some fresh b (so b#x and b#π). By Lemma 4.13 [a]x = [b]([a⊢→ b] ⋅x). Using Definition 5.11

π ⋅[a]x = [b](π ∘[a⊢→ b]) ⋅x.

By part 2 of Lemma 2.16 π(a)#(π ∘ [a⊢→ b]) ⋅x. Therefore by Lemma 4.13

[b](π ∘[a⊢→ b]) ⋅x = [π(a)]([b⊢→ π(a)] ∘π ∘[a⊢→ b]) ⋅x.

We assumed b#x so by Theorem 2.13

([b⊢→ π(a)] ∘π ∘[a⊢→ b]) ⋅x = π ⋅x.

The result follows.End of proof

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.

Definition 6.1

Suppose that 𝕏 = (|𝕏|, ⋅) and 𝕏 = (|𝕏′|, ⋅′) are nominal renaming sets. Write 𝕏 ⊆ 𝕏′ when:

• |𝕏| ⊆|𝕏′|.

• For all σ ∈ Fin and x ∈|𝕏|, σ ⋅x = σ ⋅′ x.

Lemma 6.2

• 𝕏 ⊆ 𝕏.

• If 𝕏 ⊆ 𝕏′ and 𝕏′ ⊆ 𝕏′′ then 𝕏 ⊆ 𝕏′′.

Proof

Routine.End of proof

Definition 6.3

A countably ascending chain of nominal renaming sets is a sequence 𝕏i for 0 ≤i such that 𝕏i ⊆ 𝕏i+1 for 0 ≤i.

That is, a countably ascending chain of nominal renaming sets looks like this:

𝕏0 ⊆𝕏1 ⊆𝕏2 ⊆𝕏3 ⊆. . .

Write ⋃i 𝕏i for the nominal renaming set specified by:

• | ⋃i 𝕏i| = ⋃i |𝕏i|.

• The renaming action is constructed elementwise. That is, if σ ∈ Fin and x ∈| ⋃i 𝕏i| because x ∈|𝕏i| for some i, then σ acting on x as an element of | ⋃i 𝕏i| is equal to σ acting on x as an element of 𝕏i, included as an element of | ⋃i 𝕏i|.

Definition 6.4

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 ℱ⋃i 𝕏i = ⋃i ℱ𝕏i.

Definition 6.5

As is standard, write 𝔸 ⇒ - for the mapping from nominal renaming sets to nominal renaming sets, which maps 𝕏 to 𝔸 ⇒ 𝕏.

Lemma 6.6

𝔸 ⇒ - preserves inclusions and preserves unions of countably ascending chains.

Proof

𝔸 ⇒ - preserves inclusions. Suppose that 𝕏 ⊆ 𝕏′. Unpacking Definition 3.1, f ∈|𝔸 ⇒ 𝕏| is a function f ∈|𝔸| →|𝕏| with finite support. By elementary properties of functions, f is also an element of |𝔸| →|𝕏′| with finite support. Therefore 𝔸 ⇒ 𝕏 ⊆ 𝔸 ⇒ 𝕏′.

𝔸 ⇒ - preserves unions of countably ascending chains. Suppose that f ∈ |𝔸 ⇒⋃i 𝕏i|. Then f ∈|𝔸| →⋃i |𝕏i| and f has finite support.

By Lemma 5.1 there exists some a ∈ 𝔸 and x ∈⋃i |𝕏i| such that

f = λy∈𝔸. [a⊢→ y] ⋅x. By construction x ∈ 𝕏i for some i such that 0 ≤i. It follows by Lemma 5.4 that f ∈|𝔸 ⇒ 𝕏i|. Therefore f ∈⋃i |𝔸 ⇒ 𝕏i|.

Now suppose that f ∈⋃i |𝔸 ⇒ 𝕏i|. Then f ∈|𝔸 ⇒ 𝕏i|. That is, f ∈

𝔸 →|𝕏i| and f has finite support. Since |𝕏i| ⊆⋃i |𝕏i| = | ⋃i 𝕏i| the result follows.End of proof

Definition 6.7

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 𝕏 ⊆ 𝕐.

Definition 6.8

Suppose that ℱ maps nominal renaming sets to nominal renaming sets. Suppose that 𝕏 is a nominal renaming set. Define ℱi𝕏 for 0 ≤i inductively by:

• ℱ0𝕏= 𝕏.
• ℱi+1𝕏= ℱ(ℱi𝕏).

That is, ℱi𝕏 is ‘ℱ applied i times to 𝕏’.

Lemma 6.9

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 μ(ℱ).

Proof

We take μ(ℱ) = ⋃i ℱi∅. The proof that this is a least fixedpoint of ℱ is well-known and due to Tarski [26].End of proof

Definition 6.10

Suppose that 𝕏 and 𝕐 are nominal renaming sets. Let 𝕏 × 𝕐 be the nominal renaming set with

• underlying set |𝕏 × 𝕐| = |𝕏| × |𝕐| (that is, z ∈|𝕏 × 𝕐| is a pair (x, y) where x ∈ 𝕏 and y ∈ 𝕐) and

• pointwise renaming action (that is, σ ⋅ (x, y) = (σ ⋅x, σ ⋅y)).

Call this the cartesian product of 𝕏 and 𝕐.5

Let 𝕏 + 𝕐 be the nominal renaming set with

• underlying set |𝕏| + |𝕐| (that is, z ∈|𝕏 + 𝕐| is either inl(x) where x ∈|𝕏| or inr(y) where y ∈|𝕐|) and

• pointwise renaming action (that is, σ ⋅ inl(x) = σ ⋅ inl(x) and σ ⋅ inr(y) = inr(σ ⋅y).

Call this the disjoint sum of 𝕏 and 𝕐.

Theorem 6.11

The map ℱ from nominal renaming sets to nominal renaming sets specified by

ℱ𝕏= 𝔸+ 𝕏× 𝕏+ 𝔸⇒𝕏

has a least fixedpoint, write it Λ. |Λ| can be identified with untyped λ-terms.

Proof

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). [a]x 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.End of proof

For the rest of this section we informally discuss the Gabbay-Pitts N-quantifier and inductive reasoning principles for Λ.

Suppose that ϕ(y) is a predicate on atoms (we discuss what that means, below). Write Ny. ϕ(y) for the predicate which is:

• True if the set {y ∈ 𝔸 | ϕ(y) is false} is finite.

• False otherwise.

For example if a ∈ 𝔸 then:

•Ny. (a = y) is false, because only finitely many atoms are equal to a.

•Ny. (a̸=y) is true, because infinitely many atoms are not equal to a.

This is the Gabbay-Pitts N quantifier [14].

The following inductive reasoning principle is from [14]:

(∀a ∈𝔸. ϕ(var(a))∧ ∀x, y ∈Λ. ϕ(x) ∧ϕ(y) ⇒ϕ(app(x, y))∧ ∀f ∈𝔸⇒Λ. (Ny. ϕ(fy)) ⇒ϕ(lam(f)))⇒∀x ∈Λ. ϕ(x)

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

Definition 7.1

Nominal renaming sets form a category Sub as follows:

• An object is a nominal renaming set 𝕏.

• An arrow F : 𝕏 −→ 𝕐 is a function F ∈|𝕏| →|𝕐| such that for all σ ∈ Fin and all x ∈|𝕏| it is the case that

σ ⋅F(x) = F(σ ⋅x). (6)

We let F, G, H range over arrows.

7.1 Support and arrows

Lemma 7.2

Arrows F : 𝕏 −→ 𝕐 are precisely the elements f ∈|𝕏 ⇒ 𝕐| such that supp(f) = ∅.

Proof

Suppose that F : 𝕏 −→ 𝕐 is an arrow. By Definition 7.1 F ∈|𝕏| →|𝕐|. According to Definition 3.1 to show that F ∈|𝕏 ⇒ 𝕐| we must exhibit some finite S ⊆ 𝔸 such that for all σ ∈ Fin and x ∈|𝕏| if σ|S = id|S then σ ⋅F(x) = F(σ ⋅x). It suffices to take S = ∅. By Corollary 3.8, supp(F) = ∅.

Now suppose that f ∈|𝕏 ⇒ 𝕐| is such that supp(f) = ∅. By Definition 3.1 f ∈|𝕏| →|𝕐|. According to Definition 7.1 we must show that for all σ ∈ Fin and x ∈|𝕏| it is the case that σ ⋅ f(x) = f(σ ⋅x). This is immediate from Corollary 3.8.End of proof

Lemma 7.3

If F : 𝕏 −→ 𝕐 is an arrow in Sub then

supp(F(x)) ⊆supp(x).
Proof

A corollary of Corollaries 3.9 and 3.8.End of proof

7.2 The exponential in Sub

Definition 7.4

Suppose that 𝕏 and 𝕐 are nominal renaming sets. Let app𝕏,𝕐, or just app for short, be the function from |𝕏 ⇒ 𝕐| × |𝕏| mapping f ∈|𝕏 ⇒ 𝕐| and x ∈|𝕏| to f(x) ∈|𝕐|. We call this application.

Lemma 7.5

Suppose that 𝕏 and 𝕐 are nominal renaming sets. Then application app ∈ (|𝕏 ⇒ 𝕐| × |𝕏|) →|𝕐| from Definition 7.4 is an arrow in Sub.

Proof

Unpacking Definition 6.10, application maps from |(𝕏 ⇒ 𝕐) × 𝕏| to |𝕐|. The result follows by Theorem 3.7.End of proof

Theorem 7.6

𝕏 ⇒ 𝕐 is an exponential in Sub.

Proof

Suppose F ∈ (𝕏 × 𝕐) −→ ℤ. We must show that

λx∈|𝕏|. (λy∈|𝕐|. F(x, y)) ∈𝕏−→ (𝕐⇒ℤ).

It suffices to show that if σ|supp(x) = id|supp(x) then

σ ⋅F(x, y) = F(x, σ ⋅y).

This is immediate using (6) and Theorem 2.13.

Now suppose that G ∈ 𝕏 −→ (𝕐 ⇒ ℤ). We must show that

λ(x, y)∈|𝕏× 𝕐|. G(x)(y) ∈(𝕏× 𝕐) −→ ℤ.

It suffices to show that

σ ⋅G(x)(y) = G(σ ⋅x)(σ ⋅y).

Now σ ⋅G(x)(y) = (σ ⋅G(x))(σ ⋅y) by Theorem 3.7 and σ ⋅ G(x) = G(σ ⋅x) by

(6). The result follows.End of proof

Corollary 7.7

Sub is cartesian closed.

Proof

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.End of proof

7.3 Limits and colimits

Recall the definition of tuples (uI) from Definition 2.21.

Theorem 7.8

Suppose that D is a diagram in Sub. Then:

• The limit ∫I∈DD exists in Sub and can be concretely constructed as

∫I∈DD = {(uI) ∈∏I∈DD(I) | ∀f : I →J ∈D. fuI = uJ}.

• The colimit I∈D∫D also exists in Sub and can be concretely constructed as

I∈D∫D = {[vI]∼| I ∈D, vI ∈D(I)}

where

– ∼ is the equivalence relation generated by vI ∼D(f)(vI) for every vI ∈ D(I) and f : I →J ∈D, and

– [vI]∼ is the ∼-equivalence class of vI.

Proof

Limits. Suppose X is a cone over D with arrows ξI. The corresponding map takes x ∈X to (ξIx). The only nontrivial part is to verify that (ξIx) has finite support, which is immediate from the fact that supp(ξIx) ⊆ supp(x) by Corollary 3.9, and from part 2 of Lemma 2.20.

Colimits. The argument for colimits is similar, but simpler.End of proof

7.4 Sub is a topos

Definition 7.9

Let Ω be specified by:

• |Ω| is the set of U ⊆ Fin such that:

– If σ ∈U then μ ∘σ ∈U for all μ ∈ Fin.

– There exists some finite S ⊆ 𝔸 such that if μ ∈U then

for all σ ∈Fin if σ|S = id|S then μ ∘σ ∈U.

• If U ∈|Ω| and σ ∈ Fin then σ ⋅U is defined by

σ ⋅U = {μ | μ ∘σ ∈U}.
Lemma 7.10

U ∈|Ω| is finitely supported according to the renaming action defined in Definition 7.9. Therefore, Ω is a nominal renaming set.

Proof

Direct from the construction.End of proof

Remark 7.11

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).

Lemma 7.12

Suppose that U ∈|Ω| and μ, σ ∈ Fin.

Then μ ∈σ ⋅U if and only if μ ∘σ ∈U.

As an immediate corollary, id ∈σ ⋅U if and only if σ ∈U.

Proof

By definition σ ⋅U = {μ | μ ∘σ ∈U}. The result follows.End of proof

Lemma 7.13

Suppose that U ∈|Ω|.

Then id ∈U if and only if U = Fin.

Proof

We prove two implications. If U = Fin then id ∈U is immediate.

Now suppose that id ∈U. By Definition 7.9, if σ ∈U then μ ∘σ ∈U for all μ ∈ Fin. The result follows taking σ = id.End of proof

Theorem 7.14

A 1-1 correspondence (a bijection) between subobjects of 𝕏 and arrows 𝕏 → Ω in Sub is given by:

• α 𝕌 ⊆|𝕏| maps to α(𝕌) = λx∈|𝕏|. {μ | μ ⋅x ∈|𝕌|}.

• β F : 𝕏 −→ Ω maps to β(F) = {x | id ∈ F(x)} (with the renaming action inherited from 𝕏).

Proof

We check that α and β are inverse. Suppose that 𝕌 ⊆ 𝕏 and suppose that F : 𝕏 −→ Ω. Then:

β(α(𝕌)) = {x | id ∈α(𝕌)(x)} = {x | id ∈{μ | μ ⋅x ∈|𝕌|}} = {x | x ∈|𝕌|} = 𝕌 α(β(F)) = α({x | id ∈F(x)}) = λx′∈|𝕏|. {μ | μ ⋅x′ ∈{x | id ∈F(x)}} = λx′∈|𝕏|. {μ | id ∈F(μ ⋅x′)} = λx′∈|𝕏|. {μ | μ ∈F(x′)} Lemma 7.12 = λx′∈|𝕏|. F(x′) = F

Suppose that 𝕌 ⊆ 𝕏. We check that α(𝕌) maps |𝕏| to |Ω|. Suppose that x ∈|𝕏|. It suffices to verify that:

• If σ ∈α(𝕌)(x) then μ ∘σ ∈α(𝕌)(x). If σ ∈α(𝕌)(x) then σ ⋅x ∈|𝕌|. |𝕌| is closed under the renaming action, so also μ ⋅σ ⋅x ∈|𝕌|. It follows that μ ∘σ ∈α(𝕌)(x). The result follows.

• There exists some finite S ⊆ 𝔸 such that if μ ∈α(𝕌)(x) and σ|S = id|S then μ ∘σ ∈α(𝕌)(x).

Take S = supp(x). If μ ∈α(𝕌)(x) then μ ⋅x ∈|𝕌|. By Theorem 2.13 σ ⋅x = x, therefore μ ⋅σ ⋅x ∈|𝕌|. Therefore μ ∘σ ∈α(𝕌)(x) as required.

We check that α(𝕌) is an arrow, that is, σ ⋅α(𝕌)(x) = α(𝕌)(σ ⋅x):

σ ⋅α(𝕌) = σ ⋅{μ | μ ⋅x ∈𝕌} = {μ′ | μ′ ∘σ ∈{μ | μ ⋅x ∈𝕌}} = {μ | (μ ∘σ) ⋅x ∈𝕌} = α(𝕌)(σ ⋅x) (μ ∘σ) ⋅x = μ ⋅(σ ⋅x).

We check that β(F) is a subobject of 𝕏. By construction β(F) ⊆|𝕏|. It suffices to check that if x ∈β(F) then σ ⋅x ∈β(F). Suppose that x ∈ β(F). So id ∈ F(x). We must show that id ∈F(σ ⋅x). Now F is an arrow so F(σ ⋅x) = σ ⋅F(x). Unfolding definitions,

σ ⋅F(x) = {μ | μ ∘σ ∈F(x)}.

So we must show that σ ∈F(x). By Lemma 7.13 since id ∈F(x) we know that F(x) = Fin, and therefore σ ∈F(x) as required.End of proof

Suppose that 𝕏 and 𝕐 are nominal renaming sets.

Lemma 7.15

F : 𝕏 −→ 𝕐 is mono if and only if F as a map on underlying sets F ∈|𝕏| →|𝕐| is injective.

Proof

Routine.End of proof

Lemma 7.16

A subobject of 𝕏 may be uniquely identified with a nominal renaming set 𝕌 such that 𝕌 ⊆ 𝕏 (Definition 6.1).

Proof

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 x ∈|𝕌| to itself, that is, to x ∈|𝕏|.End of proof

Definition 7.17

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.

Lemma 7.18

A diagram

𝕌→𝟙𝕏ι𝕌↓↓F→Ω⊤ ↓↓

is a pullback if and only if {x | id ∈ F(x)} = |𝕌|.

Proof

By routine calculations.End of proof

Corollary 7.19

Sub is a topos.

Proof

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.End of proof

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 ‘ϕ(x)’ is the set of renamings such that ϕ is true of σ ⋅x. Intuitively, a truth-value of ‘x = y’ in Sub is the collection of unifiers of x and y.

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(σ ⋅x) = σ ⋅ supp(x) 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

[a⊢→ b] ⋅[a′⊢→b′] ⋅x = [a′⊢→b′] ⋅x ⇒[a⊢→ b] ⋅x = x

for all a′, b′, a, x ∈|𝕏|, and fresh b (so b̸∈ S where S 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 F : 𝕏 −→ 𝕐 that σ ⋅F(x) = F(σ ⋅x) for all σ ∈ Fin and x ∈|𝕏|. We can alternatively insist just that π ⋅F(x) = F(π ⋅x) for all π ∈ Per and x ∈|𝕏|. 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:

Definition 8.1

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).

Definition 8.2

For A ∈ Var write y(A) for the functor taking B to Var(A, B), with the natural right-composition action on arrows.

Specify a topology on SetVar by letting its basis be those subfunctors of y(A) generated by some injection f : A→B.

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:

a#x ⊢x[a⊢→ b] = x x[a⊢→ b][a′⊢→b′] = x[a′⊢→b′][a⊢→ b] x[a⊢→ b][b⊢→ c] = x[a⊢→ c][b⊢→ c] x[a⊢→ a] = x x[a⊢→ c][b⊢→ c] = x[b⊢→ c][a⊢→ c]

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 ‘X plus finite support’ for different values of X.

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 (TLCA), 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] G´erard 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 Sch¨urmann. 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. ↩