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

A General Mathematics of Names

Murdoch J. Gabbay

Heriot-Watt University, Edinburgh

Abstract

We introduce FMG (Fraenkel-Mostowski Generalised) set theory, a generalisation of FM set theory which allows binding of infinitely many names instead of just finitely many names. We apply this generalisation to show how three presentations of syntax — de Bruijn indices, FM sets, and name-carrying syntax — have a relation generalising to all sets and not only sets of syntax trees. We also give syntax-free accounts of Barendregt representatives, scope extrusion, and other phenomena associated to α-equivalence.

Our presentation uses a novel presentation based not on a theory but on a concrete model U.

Key words: Set theory, Fraenkel-Mostowski set theory, NEW quantifier, nominal techniques, alpha-conversion, names.

Contents

1 Introduction 2

1.1 Overview 2

1.2 Method of presentation 4

1.3 Mathematical overview of FMG vs FM 5

2 The universe U 5

2.1 We build U 5

2.2 Support and permutation acting on elements of U 7

2.3 More complex elements of U 9

Email address: murdoch.gabbay@gmail.com (Murdoch J. Gabbay).

1 I would like to thank Henk Barendregt, Antonino Salibra, and an anonymous referee. This work was done while at the École Polytechnique and INRIA in Paris, France.

Preprint submitted to Elsevier 18 February 2007

2.4 The И quantifier, properties of L, abstraction and concretion 12

3 Inductive datatypes 14

4 The relation between name-carrying-, FM-, and de Bruijn syntax 17

5 α-equivalence as a mathematical notion 21

5.1 Equivariance 21

5.2 A word on support 23

5.3 Abstractive functions or, syntax-free “quotient by α-equivalence” 24

5.4 Generalised И and Barendregt representatives 27

5.5 Freshness 29

5.6 Scope extrusion for И 31

6 The underlying theory of sets 33

6.1 Axioms 33

6.2 Lifting constructions in U to the set theory 37

6.3 Abstractions commute with pairsets, powersets, and more 41

6.4 An algebraic version 42

7 Future work 43

References 44

1 Introduction

1.1 Overview

This paper is about names and binding in infinitary syntax as an abstract set-theoretic notion.

In previous work [1,2] the author and Pitts introduced Fraenkel-Mostowski set theory (FM sets). This is a set theory in the style of Zermelo-Fraenkel sets (ZF sets [3,4]) in which we can build abstract syntax as inductively defined sets of abstract syntax trees. It is shown how in FM, a set-operation corresponding to quotienting by α-equivalence (in case the set is of abstract syntax trees — identical to quotienting by α-equivalence) can be defined on the entire set-universe.

Call a variable-symbol in object-level syntax (that’s the sets of abstract syntax trees we build in, say, a set theory), an atom. This is consistent with the original works [1,2].

Just like syntax has a notion of ‘variables occurring in’ and ‘variables occurring free in’, so FM sets has a notion of ‘atoms occurring in’ and ‘atoms occurring free in’, which is valid for all sets, not just those which happen to be inductively defined. We call the ‘free atoms’ of a set x its support and write it Sx.

In the FM theory literature we have so far concentrated on support, swapping (a b) · x (a notion of ‘rename a as b and vice versa’ in the support), and abstractions [a]x (a set-theoretic notion of α-equivalence). These definitions are abstract, that is they apply to all sets, and this opened up the path not only to the algebraic structure of Nominal Sets, but also Nominal Domains 2 and much other work. We give a Nominal version of FMG sets in §6.4.

In FM Sx is always finite; a Fraenkel-Mostowski set has a finite supporting set. In fact, this is an axiom of the theory (axiom (Fresh) [2]). This made FM a semantics of finitary syntax — but without the syntax.

This is (at least in the opinion of the author) a fascinating and uniquely characteristic idea with rich structure. However, it does invite the question

“but what about infinitary syntax, which can mention infinitely many different atoms?”.

So read this paper, and enjoy our answer.

While we are at it, we take a step back from the original presentation of α-equivalence in set theory and give a much more general treatment of the mathematics, even in the case of FM (finitary syntax). Notably, we generalise the Gabbay-Pitts И quantifier, prove an important basic correctness result (a form of set-theoretic scope extrusion), and exploit our possibly infinite number of atoms to give interesting characterisation of ‘name-carrying’ and ‘de Bruijn’ syntax [6]. We discover that, while FM is based on atoms, FMG is based on well-orderable streams of distinct atoms. And last but not least, we propose a slogan ‘small=well-orderable’ which generalises the ‘small=finite’ of FM sets.

2 Published since this paper was submitted for publication [5].↩

1.2 Method of presentation

Presenting this work poses some unique problems. The mathematics is not simple (i.e. it is technical, in the way that any set-theory can be), and while we would maintain that FM techniques are no harder than anything else in modern theoretical computer science, this work will not be familiar to the reader unless they have studied previous work on FM ([1,2], and other publications).

Since we cannot be simple nor familiar, we do at least try to be concrete. Thus, we do not dive straight in to the language of FMG sets 3 and its axioms.

Instead, we start with U a simple but (almost) completely sufficiently expressive fragment of the cumulative hierarchy model ([3,4]) of FMG sets. This allows us to:

• Construct U and explain FMG ideas in a concrete structure, using natural language.

• Build U directly in standard ZF (we use any sufficiently large set to interpret A).

In this paper, we begin by investigating all our significant constructions in a particular cumulative hierarchy U, and then we generalise by stages until we are in full FMG.

The technical content of this paper, section by section, is as follows:

• §2: We define U as a cumulative hierarchy and investigate its basic properties.

• §3: We construct sets describing name-carrying, de Bruijn [6], and FM syntax (that is, syntax-up-to-alpha-equivalence, in a sense which has been made formal [2] and will be made formal later in this paper) over a fixed but arbitrary signature E.

• §4: We show they are all isomorphic.

• §5: We show that the isomorphisms generalise to all elements of U (not just those which happen to represent abstract syntax trees for E).

• §6: We replace U with full FMG sets. The constructions of the concrete model U generalise and we show how.

Our voyage is therefore from what the reader most probably knows very well, namely operations on concrete syntax trees as occurs everywhere in the literature, to logical properties of a concrete cumulative set hierarchy, to logical provability in a first-order theory of FMG sets.

3 First-order logic [7,8] extended with a constant symbol A called the set of atoms and a binary relation ∈ called set inclusion.↩

1.3 Mathematical overview of FMG vs FM

So just how does FMG differ from FM sets?

An axiom of FM states that every set has finite support, so in a suitable formal sense, we can say that a set of atoms is ‘small’ when it is finite. If φ is a predicate on atoms, we write Иa.φ(a) for ‘φ is true for all but a small (finite) set of atoms’.

The slogan of FMG sets is ‘small’=‘well-orderable’. Thus in FMG sets a set of atoms is ‘small’ when there is a set which is a well-ordering of that set of atoms. If φ is a predicate Иa.φ(a) means ‘there exists a set of atoms S and a set which is a well-ordering of S, such that for all a ∉S, φ(a) holds’.

FMG in its ‘vanilla’ form makes no committment to just how large the largest well-orderable set of atoms is; but we can add an axiom saying ‘well-orderable’ means ‘finite’, or ‘countably infinite’, or whatever we please. Thus, an observation of this paper is that the only property of finite sets which we really needed in FM, was that they are well-orderable.

The technical reason well-orderability is so useful, is simply that it is a convenient way of guaranteeing that for any two small sets of atoms, one of them injects into the other (from the property of ordinals that for any two ordinals treated as ordered structures, one of them is an initial segment of the other [4, Lemma 6.3]). This guarantees that there are enough functions between small sets of atoms that we can always rename them to be fresh, and as we shall see this will be very useful.

U the concrete model where we start, takes ‘small’ to equal ‘countable’ (and ‘large’ to equal ‘uncountable’).

2 The universe U

2.1 We build U

Fix an uncountable set of atoms a, b, c, . . . ∈A.

Call a permutation π a bijection on A. Define

Sπdef={ a ∈A⏐⏐⏐ π(a) ≠ a}. (1)

Say π has countable support when Sπ is countable. Write PA for the set of permutations π with countable support, which is a group under functional composition ◦. Write Id for the identity element which is the identity function on atoms.

If S ⊆A write

Fix(S)def={ π ∈PA⏐⏐⏐∀a ∈S. π(a) = a}.

We may drop the brackets and write FixS for Fix(S) without comment. Say π ∈ FixS fixes S pointwise.

Lemma 1

(1) Sπ is the least S such that π ∈ Fix(A \ S).

(2) π ∈ FixS if and only if Sπ ∩S = ∅.

(3) FixS is a group.

The proofs are by basic group-theoretic calculations.

Write P≤ω(X) for the set of countable subsets of X.

We inductively define U a set of elements u, v, . . ., a permutation action PA →U →U which we write π · u, and a function support U →P≤ω(A) which we write Su. (The notation clash with Sπ is deliberate; the values of the two functions will turn out to be identical.)

(1) a ∈A is an element.

π · adef= π(a) and Sadef= {a}.

(2) U ∈P≤ω(U) is an element.

π · Udef={ π · u⏐⏐⏐ u ∈U}and SUdef=⋃ { Su⏐⏐⏐ u ∈U}.

Note that U can encode tuples as ⟨x, y⟩= {{x, y}, {x}} (this is the standard set-theoretic encoding [4]).

(3) If x and y are elements then the abstraction

[x]ydef={ ⟨π · x, π · y⟩⏐⏐⏐ π ∈Fix(Sy \ Sx)}(2)

is an element.

π · [x]y def= [π · x]π · y and S[x]y def= Sy \ Sx.

Write arbitrary elements of U as u, v, arbitrary atoms a, b, c, arbitrary countable sets U, V, S and arbitrary abstractions ˆu, ˆv.

In summary, any element of U has precisely one of the following three forms:

• an atom a,

• a countable collection U, or

• an abstraction [x]y.

Write

(1) x#y when Sx ∩ Sy = ∅.

(2) π#x when Sπ ∩ Sx = ∅. Unfolding definitions, this is equivalent to π ∈ Fix(Sx).

For two distinct atoms a and b write (a b) for the permutation mapping a to b, b to a, and n ≠ a, b to n. This is a swapping.

Then (a b)#a is false and (a b)#c is true, (a b)#⟨a, c⟩ is false (we assume a, b, c are all distinct). (a b)#[a]a is true, but (a b)#[a]b is false. a#[a]a and a#[a]b are both true; b#⟨[a]a, [a]b⟩ is false.

2.2 Support and permutation acting on elements of U

We prove some simple lemmas:

Lemma 2

Suppose S is a countable set of atoms. Then:

(1) π · S = {π · a | a ∈S}.

(2) SS = S.

Proof

(1) S is a countable set, and the permutation action is defined to be pointwise.

(2) S is a countable set, so SS =⋃{Sa | a ∈S}. We now observe that by definition Sa = {a}.

2

Lemma 3

(1) If x ∈U then Sx ∈U.

(2) π · (Sx) = S(π · x).

(3) x#[x]y.

(4) If π#x then π · x = x (π#x is logically equivalent to π ∈ FixSx).

(5) If π(a) = π′(a) for all a ∈ Sx then π · x = π′ · x.

Proof

(1) Proof by induction on x; since a ∈U always it suffices to show that Sx is countable.

• {a} is countable.

• Any countable union of countable sets is necessarily countable.

• Any subset of a countable set is necessarily countable.

(2) Proof by induction on x.

• π · {a} = {π(a)}.

• π ·⋃ {Su⏐⏐⏐ u ∈U}=⋃ { π · Su⏐⏐⏐ u ∈U} and we can use the inductive hypothesis.

• π·(Sy\Sx) = (π·Sy)\(π·Sx) and again we use the inductive hypothesis.

(3) Unpacking definitions.

(4) By induction on x.

• π#a when π(a) = a and we recall that π · a = π(a).

• π#U when π#u for each u ∈U and we use the inductive hypothesis.

• We observe that π · [x]y = [π · x]π · y by definition. Now suppose π ∈ Fix(Sy \ Sx).

We note that S(π · y) \ S(π · x) = π · (Sy \ Sx) = Sy \ Sx, and also recall that Fix(Sy \ Sx) is a group. By group-theoretic calculations it follows that:

π · [x]y ={ ⟨π′ · (π · x), π′ · (π · y)⟩⏐⏐⏐ π′ ∈Fix(S(π · y) \ S(π · x))}={ ⟨π′′ · x, π′′ · y⟩⏐⏐⏐ π′′ ∈Fix(Sy \ Sx)}= [x]y.

Here π′′ is ‘morally’ π′ ◦π.

(5) This is a corollary of the last part, observing that π(a) = π′(a) for all a ∈ Sx precisely when π−1 ◦π′ ∈ Fix(Sx), and this is logically equivalent to asserting π−1 ◦π′#x.

2

Note that π · x = x does not imply π#x. For example S(a b) = {a, b} and π · {a, b} = {a, b} ((a b) is a swapping, defined at the end of §2.1).

π·([x]y) is defined componentwise as [π·x]π·y. Also, π·U is defined pointwise. Is it possible for the componentwise action on [x]y to conflict with the pointwise action on it as some U?

In fact this question does not arise since [x]y is uncountable and according to our definitions U ∈U must be countable.

However, it is easy to prove that the two collections are equal anyway:

Lemma 4

The componentwise and pointwise actions agree for abstractions:

[π · x]π · y ={ ⟨π · π′ · x, π · π′ · y⟩⏐⏐⏐ π′ ∈Fix(Sy \ Sx)}.
Proof

We must show that for any π,

{ ⟨π′ · π · x, π′ · π · y⟩⏐⏐⏐ π′ ∈Fix(Sπ · y \ Sπ · x)}={ ⟨π · π′ · x, π · π′ · y⟩⏐⏐⏐ π′ ∈Fix(Sy \ Sx)}.

We use the notation below and observe that π′ · π = π · π′π−1, and π′ ∈ Fix(Sπ · y \ Sπ · x) if and only if π′π−1 ∈ Fix(Sy \ Sx). Finally we note, as we noted before, that π′ ∈ Fix(Sy \ Sx) is a group. The result now follows by group-theoretic calculations. 2

As a matter of notation write π′π = π ◦π′ ◦π−1 (the conjugation of π′ by π [9]). It is easy to calculate that π′ maps a to b if and only if π′π maps π(a) to π(b); in particular, π′ ∈ FixS if and only if π′π ∈ Fix(π · S).

For example, if a, b, c are distinct atoms then [a]a = [b]b, [a]c = [b]c and [a][b]⟨a, b⟩= [b][a]⟨b, a⟩. These reprise well-known α-equivalences in (say) the λ-calculus and logic (but without the λ-calculus and logic; equality on abstractions is precisely α-equivalence, in a suitable formal sense which we analyse in depth in the rest of this paper).

2.3 More complex elements of U

Just that U is closed under countable subsets already gives it considerable power. For example it contains:

(1) The natural numbers N encoded as 0 def= ∅, and i + 1 def= {i, {i}}.

(2) A two-element set B encoded as {0, 1}.

(3) Ordered pairs (as we already noted)

⟨x, y⟩def= {{x}, {x, y}}.

Given X, Y ⊆U (X and Y need not necessarily be countable, and not necessarily be elements of U) write

X × Ydef= {⟨x, y⟩| x ∈X, y ∈Y }.

This is of course the standard notion of cartesian product.

(4) Disjoint sums

Inl(x)def= ⟨0, x⟩ and Inr(y) def= ⟨1, y⟩.

Given X, Y ⊆U write

X + Ydef= {Inl(x) | x ∈X} ∪{Inr(y) | y ∈Y }.

(5) Finite lists [u1, . . . , un] encoded as nested pairs. Given X ⊆U write X-list for the set of lists with elements in X.

(6) Countable streams p = [p1, p2, . . .] encoded as countable sets of finite lists of initial segments. Given X ⊆U write X-stream for the collection of countable streams of elements in X.

The details of the encodings are irrelevant; it is only important that they exist.

Call an arbitrary subset W ⊆U a class or a collection (as we did above). This need not be an element of U, and if we know for a fact that it is not, call it a proper class. By construction of U, a class is a proper class precisely when it is uncountable and not equal to [x]y for some x, y ∈U.

If u is a finite list or a stream, we may write hd(u) for u1 and tl(u) for [u2, u3, . . .], where these are defined. (We mostly use this notation much later on in this paper, to the particular case of a stream of distinct atoms p ∈L which we define below.)

We briefly consider the permutation action and support of these constructs:

Lemma 5

For all the constructs above, permutation acts componentwise and the support of the whole is the set union of the supports of the components. For example, π · i = i always and Si = ∅, and

π · [u1, u2, . . .] = [π · u1, π · u2, . . .] and S[u1, u2, . . .] =⋃Sui,

and similarly for pairs and finite lists.

Proof

For numbers, we work by induction on their construction, recalling that π acts pointwise on sets (so π · ∅= ∅, for example) and SU takes the union of Su for all u ∈U. These observations, along with some concrete calculations, prove the rest of the result for tuples, finite lists, and finally for streams. 2

Proper classes with respect to U which are of particular interest are

(1) A the set of atoms.

(2) L, which we now define.

Write p, q ∈L for the set of countable streams of distinct atoms, that is, streams p = [p1, p2, . . .] such that pi = pj implies i = j and pi ∈A for all i.

Lemma 6

Suppose p = [p1, p2, . . .] ∈L. Then:

(1) p ∈U.

(2) The permutation action is pointwise on the pi, that is, π · p = [π · p1, π · p2, . . .].

(3) Sp = {p1, p2, . . .}.

Also, L is a proper class (L ∉U).

Proof

For the first parts, the proofs are as for Lemma 5. L is a proper class since it is uncountable (and, we can check it is not an abstraction [x]y for any elements x and y). 2

Note that for p ∈L, Sp is infinite but countable. 4 Two uses of p are: to help model infinite behaviour in the presence of name-generation (so p might be a countable list of ‘generated’ names); and to help model of infinitary syntax.

p ∈L behaves like a ‘big atom’. For example L has a kind of permutation action:

Lemma 7

(1) Given p = [p1, . . .], q = [q1, . . .] ∈L, if p#q then (p q) is well-defined, where (p q)(pi) = qi and (p q)(qi) = pi and otherwise (p q)(c) = c.

(2) For p and q as in the first part, if p#q does not hold then (p q) is not necessarily well-defined.

Proof

(1) We just defined it.

(2) Consider p and q = tl(p). Then p1 maps to p2, and p2 maps to both p1 and p3.

2

4 . . . so it can never exist in FM sets, where everything has finite support.↩

2.4 The И quantifier, properties of L, abstraction and concretion

If S ⊆A is countable it follows that A\S is uncountable, and we can choose a p ∈L such that p#S. We say p is fresh for S. We use this without comment henceforth.

We may also just say ‘choose a fresh p’, meaning that p should be fresh for the union of the supports of whatever elements are under consideration at that particular moment. This would be meaningless if we intend p to be fresh for a proper class of U, but we will never do this.

If a ∈A then Sa is a singleton, which is very countable. Thus we can always choose a fresh a ∈A.

• Given some F : A →U write Иa.Fa for the unique value of F at all but countably many a ∈A, if this exists.

• Similarly for F : L →U write Иp.Fp for the unique value of F at all p#S for some countable S ⊆A, if this exists.

• Given some φ a predicate on A write ‘Иa.φ(a) is true’ (or just ‘Иa.φ(a)’) if φ is true for all atoms except for the elements of some countable S ⊆A, and ‘Иa.φ(a) is false’ if φ is false for all atoms except for the elements of some countable S ⊆A.

• Similarly for φ a predicate on L, write ‘Иp.φ is true’ or just Иp.φ when φ is true of all p ∈L such that p#S, for some countable S ⊆A, and so on.

The canonical examples are:

•Иa.a is not well-defined, but Иa.[a]a is well-defined and has value [a]a = [b]b = [c]c = . . ..

•Иa.a = b is false, and Иa.a ≠ b is true.

• Let V be a set containing uncountably many atoms, and not containing uncountably many atoms. Then Иa.a ∈V is not defined.

In practice Иblah is usually well-defined, because blah will be something we specified using a sentence in natural language or mathematical formalism, parameterised over some finite set of elements of U each of which has countable support; so blah should be either uniformly true or false away from that support. This informal argument becomes formal in FMG sets, both internally (abstractive functions in §5.3 and generalised И for them §5.4), and externally (equivariance Theorem 35).

The following result is the main reason that A and L are so important, we shall need it for later:

Lemma 8

(1) [a]u is the graph of a partial function defined precisely on

those c such that c = a or c#u (or equivalently; such that c#[a]u), with value (c a) · u where defined.

(2) [p]u is the graph of a partial function defined precisely on q#Su \ Sp (or equivalently; such that q#[p]u), with value Иr.(q r) ◦ (r p) · u.

Proof

We note that by definition, c#[a]u when c#u or c = a, and similarly q#[p]u when q#Su \ Sp.

(1) Expanding definitions,

[a]u ={ ⟨π(a), π · u⟩⏐⏐⏐ π ∈Fix(Su \ {a})}.

The first component π(a) can assume any c#u or c = a, since (c a) ∈ Fix(Su \ {a}) for these c.

It remains to show this is functional, i.e. π · u = π′ · u if π(a) = π′(a) and π, π′ ∈ Fix(Su \ {a}). But then π and π′ agree on Su and the result follows from the last part of Lemma 3.

(2) Expanding definitions,

[p]u ={ ⟨π · p, π · u⟩⏐⏐⏐ π ∈Fix(Su \ Sp)}.

First we show this is functional: suppose π, π′ ∈ Fix(Su \ Sp) and π · p = π′ ·p. By the technical lemma below and Lemma 6, π(c) = π′(c) for every c ∈ Su. Functionality follows.

We now just need to show that for every q#Su \ Sp, there is some π ∈ Fix(Su\Sp) such that π ·p = q. Choose some fresh r (taking r#p, q, u suffices) and set π = (q r) ◦ (r p).

2

Lemma 9

(Technical Lemma) Suppose p = [p1, . . .] ∈L. If π · p = π′ · p then π(pi) = π′(pi) for every i.

Proof

Lemma 6 proves the permutation action is pointwise. The result is immediate. 2

We shall write abstractions as ˆu, ˆv. We write the value or concretion of ˆu at some c or q, when this is defined, as ˆu@c or ˆu@q respectively.

The terminology ‘concretion’ is consistent with existing terminology in the FM literature [2, Definition 5.3].

Concretion is very useful for specifying functions, since it allows us to ‘choose the name of the bound variable’. We will use it heavily later.

Lemma 10

(1) [c](ˆu@c) = ˆu when ˆu is an abstraction by an atom and ˆu@c is defined, and ([a]u)@a = u.

(2) [p](ˆu@p) = ˆu when ˆu is an abstraction by an element of L and ˆu@p is defined, and ([p]u)@p = u.

Proof

(1) Suppose ˆu = [a]u. By Lemma 8, ˆu@c = (c a) · u and it must be the case that c#ˆu. By definition

[c](ˆu@c) = [c](c a) · u = (c a) · ([c]u).

We then use the fourth part of Lemma 3, recalling that by definition a#[a]u and that c#[a]u.

We also observe that (a a) · u = u, so using the previous result

([a]u)@a = u follows.

(2) Suppose ˆu = [p]u. By Lemma 8, ˆu@q = (q a) · u and it must be the case that q#ˆu. By definitions

[q](ˆu@q) =Иr.[q](q r) ◦(r p) · u =Иr.(q r) ◦(r p) · ([p]u).

We then use the fourth part of Lemma 3.

2

3 Inductive datatypes

Recall from §2.3 the definitions of cartesian products X × Y , disjoint sums X + Y , lists X-list, the set of natural numbers N, the classes of atoms and countable streams of distinct atoms A and L, and so on (for any classes X, Y ⊆ U).

Also write

[X]Y for {[x]y | x ∈X, y ∈y}.

Fix a countably infinite collection of class variable symbols V , V ′, X, and so on. Then expressions of a simple class specification grammar are defined by:

E ::= X, V, V ′ . . . | E × E | [E]E | N | A | E + E | E-list | . . . (3)

Say E is closed when it has no class variables. A closed E denotes an actual class ⟦E⟧ ⊆U in a natural way. For example:

• ⟦A⟧ = A.

• ⟦N⟧ = N, where N is defined in §2.3.

• ⟦E + E′⟧ = ⟦E⟧ + ⟦E′⟧, where + is defined in §2.3.

• ⟦[E]E′⟧ = [⟦E⟧] ⟦E′⟧ (in this paper we shall only really consider E ∈{A, L}).

• and so on.

Say E is a signature in X when it mentions at most one class variable, and that variable is X. We abuse notation and write EX for a signature in X. Given EX and E′X write EE′X for a signature obtained by substituting E′X for X in EX. For example, (X × X)(X-list)X = (X-list) × (X-list).

Say permutation acts trivially on u ∈U when π · u = u for all π. Given a class X ⊆U, which may be countable and thus itself an element of U, say X has a trivial permutation action when permutation acts trivially on every element of X.

Lemma 11

If X ⊆U has a trivial permutation action then [A]X ∼= X and [L]X ∼= X is a canonical way.

Proof

We consider just [A]X; the case of [L]X is similar. Map ˆx to ˆx@a for any a, and x to [a]x for any a. This is well-defined by Lemma 10 and the fact that permutation acts trivially on x and ˆx@a. 2

We need some notation: if S ⊆U say S is equivariant when

∀x ∈U, π ∈PA. x ∈S ⇔π · x ∈S.

Much more on this later in §5.1.

Lemma 12

(1) A and N are equivariant.

(2) If X and Y are equivariant, so are X ×Y , X +Y , [X]Y , and X-list (and so on).

Proof

(1) If a ∈A then π · a ∈A, since a permutation π ∈PA does map atoms to atoms. The result follows since PA is also a group. If n ∈N then the permutation action is trivial (that is, π · n = n for all π) and the result is easy to prove.

(2) All results are by simple calculations. We only give one. Suppose x ∈X and y ∈Y . Then π · [x]y = [π · x]π · y by Lemma 4 and since π · x ∈X and π · y ∈Y , we are done.

2

Equivariant classes are easier to work with — we know we can rename atoms without moving out of the class, see also Lemma 14 below — and sufficient to model syntax-with-binding as we are in the process of demonstrating. All classes are assumed equivariant unless stated otherwise.

For some equivariant S ⊆U write ES for the class denoted by EX interpreted according to the list above, where we additionally take X to denote S.

Lemma 13

A signature induces a class ιE (ι for ‘initial’) which is the least class such that E(ιE) ⊆ιE.

Proof

Write E0X def= X and Ei+1X def= E(EX). ιE can be constructed as ⋃i EiX in a standard way (see [10] or [1, Section 10]). We briefly look at the only unusual aspect of this construction, which is FM(G) abstraction (it turns out to be quite easy):

Suppose X0 ⊆X1 ⊆X2 ⊆. . . ⊆U. Then:

(1) [⋃i Xi]Y =⋃[Xi]Y : Suppose [x]y ∈ [⋃i Xi]Y . Then x ∈Xi for some i and y ∈Y , so x ∈ [Xi]Y . Conversely if [x]y ∈⋃[Xi]Y then [x]y ∈ [Xi]Y for some i so x ∈Xi and [x]y ∈ [⋃i Xi]Y .

(2) [Y] ⋃i Xi =⋃i[Y ]Xi: Similarly.

2

Call ιE an inductively defined datatype. The expression determines its constructors.

Three signatures are of particular interest to us by way of prototypical examples:

LncXdef= A + X × X + A × X LXdef= A + X × X + [A]XLdbXdef= N + A + X × X + X(4)

ιLnc is an inductive datatype of terms of the λ-calculus without α-equivalence. ιL is an FM datatype of terms up to α-equivalence =α; the lemma

ιL ∼= ιLnc/=α

is easy to prove by induction, but we leave that for α which we construct in the next section. ιLdb is a de Bruijn datatype for λ-terms in the style of the seminal implementation of abstract syntax up to α-equivalence in Automath [6] by de Bruijn and others.

The next section discusses the relationships between these signatures in detail.

We recently mentioned that equivariant classes are easier to work with. Here is another reason (known already for FM [1,2]):

Lemma 14

(1) If X is equivariant and ˆx ∈ [A]X then ˆx@b ∈X for any b, where ˆx@b is well-defined.

(2) If X is not equivariant then there may be ˆx ∈ [A] such that ˆx@b is well-defined and not in X.

Similarly for [L]X.

Proof

(1) If ˆx ∈ [A]X then by construction ˆx = [a]x for some a ∈A and x ∈X. By Lemma 10 ˆx@b = (b a) · x where this is defined, and by equivariance this is in X.

(2) It suffices to provide a counterexample. Let X = {a} and observe that [a]a ∈ [A]X and [a]a@b = b is well-defined but b ∉X.

The case of [L]X is similar. 2

Thus if we want to use classes as a sorting system for constructing abstract syntax trees (and we do) we had best use equivariant classes, since otherwise we cannot concrete an abstraction, i.e. ‘choose a name for the abstracted variable name’ at any atom for which the concretion is defined.

4 The relation between name-carrying-, FM-, and de Bruijn syntax

Call EX a simple signature when all its abstractions are of the form [A]-. The examples of (4) are all simple.

Given a simple signature, for example LX = A + X × X + [A]X, we derive two other signatures from it as follows:

(1) EncX the name-carrying version is EX with every abstraction replaced by A × -. For example LncX = A + X × X + A × X.

(2) EdbX the de Bruijn version is EX with every abstraction replaced by -, and every instance of A replaced by N + A. For example LdbX = N + A + X × X + X.

These give rise to three inductively defined sets of abstract syntax ιEnc, ιE, and ιEdb.

We now define functions α and β

ιEncα−→ιE [L]ιEβ−→ιEdb(5)

as follows:

To define α, which is out of an inductively defined set, it suffices to define the action of α on its components. We let α be the identity except on components where EX has [A]X (so that Enc has A×X), in which case α is the abstraction function λa, x.[a]x.

For example α : ιLnc →ιL is defined as follows:

• α(a) def= a.

• α(tt′) def= α(t)α(t′).

• α(λa.t) def= λ[a]α(t) (of course the leftmost λ is a term-former of Lnc and the rightmost λ is a term-former of L).

We define

βtdef=Иl.β′(l, t)

where β′ is defined on L × ιE as follows:

• β′(l, a) def= i if a = li, and β′(l, a) def= a otherwise.

• β′(l, tt′) def= β′(l, t)β′(l, t′)

• β′(l, λˆt) def=Иa.β′(a :: l, ˆt@a).

It is easy to inductively characterise the kernel ∼ of α on ιLnc:

(1) a∼a.

(2) s∼t and s′∼t′ implies ss′∼tt′.

(3) Иc.(c a) · t =Иc.(c a′) · t′ implies λa.t∼λa′.t′.

A few examples suffice to convince us that the kernel of α is the relation which we would naturally call α-equivalence.

βx is defined as Иl.β′(l, x) where β′ is defined as before. We also state what to do with countable powersets:

β′(l, U ∈P≤ω(U))def={ β′(l, u)⏐⏐⏐ u ∈U}. (6)
Theorem 15

β : ιE →ιEdb described above is an isomorphism.

Proof

It suffices to exhibit the following isomorphisms and observe that β is obtained by applying them repeatedly left-to-right. We only do the first part:

[L](X × Y ) ∼= [L]X × [L]Y [L](X + Y ) ∼= [L]X + [L]Y[L]N ∼= N [L]B ∼= B[L]P≤ω(X) ∼= P≤ω([L]X) [L]P<ω(X) ∼= P<ω([L]X)[L](X-list) ∼= ([L]X)-list [L]A ∼= N + A [L][A]X ∼= [L]X(7)

So β distributes the abstraction [L]- down until it reaches A, at which point we obtain N + A.

We consider a selection of cases:

(1) The case X × Y .

ˆu : [L](X × Y )↦ −→Иl.⟨[l]π1(ˆu@l), [l]π2(ˆu@l)⟩⟨ˆu, ˆu′⟩: ([L]X) × ([L]Y )↦ −→Иl.[l]⟨ˆu@l, ˆu′@l⟩

The functions could also be written informally as [l]⟨u, u′⟩↦→⟨[l]u, [l′]u⟩ and ⟨[l]u, [l]u′⟩↦→ [l]⟨u, u′⟩. This makes it intuitively obvious that they are well-defined and mutually inverse.

However, proving this now would be hard; best to wait for later when in FMG sets we will have powerful results about И (Corollary 39 and Theorem 35). For full proofs, see Theorem 42.

(2) The case N. The functions are given by λˆn.Иl.(ˆn@l) and λn.Иl.[l]n. See Lemma 11.

(Note that ˆn ={ ⟨l, n⟩⏐⏐⏐ l ∈L} for some n, so ˆn@l = ˆn@l′ for any l and l′ and Иl.(ˆn@l) is well-defined.)

(3) The case of B is similar; indeed, the result holds for any set all of whose elements have the trivial permutation action.

(4) The case P≤ω(X).

ˆU : [L]P≤ω(X)↦ −→Иl.{ [l]u⏐⏐⏐ u ∈ˆU@l}U : P≤ω([L]X))↦ −→Иl.[l]{ ˆu@l⏐⏐⏐ ˆu ∈U}

It is worth discussing this in a little detail.

Suppose we have ˆU : [L]P≤ω(X). Choose l# ˆU; we know ˆU@l is well-defined and is a countable set of elements of U. We also know that l#[l]u for any u ∈ˆU@l and so that l# {[l]u⏐⏐⏐ u ∈ˆU@l}. So the map above is well-defined (it does not depend on which l# ˆU we choose).

Now suppose we have U : P≤ω([L]X). This is a countable collection of elements so the support of U is the union of the support of its elements; choose some l such that l#ˆu for all ˆu ∈U; in particular ˆu@l is well-defined for all ˆu ∈U. We know that l#[l] { ˆu@l⏐⏐⏐ ˆu ∈U}, so the map above is well-defined (it does not depend on which l we choose).

(5) The case A.

ˆa : [L]A↦ −→Иl.if a = li then i else ai : N↦ −→Иl.[l]lia : A↦ −→Иl.[l]a.

So [l]a corresponds to i if a = li for some i and to a otherwise.

(6) The case [A]X. The functions are given by

ˆˆx : [L][A]X↦ −→Иl.Иa.[a :: l](ˆˆx@l@a) : [L]Xˆx : [L]X↦ −→Иl.[tl(l)][hd(l)](ˆx@l) : [L][A]X.

This function is clearly a de Bruijn shift; the bound atom in [L][A]X is pushed onto the head of the list of bound atoms, which is shifted up. Take X = A. Then for example [l][n]l2 maps to [n :: l]l2 = [l]l3.

2

We notice that ιEdb is not quite a de Bruijn datatype because it can have both dangling unbound atoms and unbound indices. Consider ιLdb as constructed above; then λ7 and λa are both terms. Generally we allow only one or the other. A little extra notation solves the problem:

Given a class V ⊆U write

ΓVdef={ u ∈V⏐⏐⏐ Su = ∅}.

Then we can prove by induction that ΓιLdb = ι(N + X × X + X). We have recovered a bona-fide de Bruijn datatype. Γ[L]ιE consists of elements of ιE with free atoms bound in order. β restricts to an isomorphism between Γ[L]ιE and Γι(E[A↦→N,[A]X↦→X]), using an informal notation.

Infinitary syntax: There are various directions in which the signature E (and its interpretation in U) may be made infinitary. We can extend signatures with E-streams, which in U are interpreted by countably infinite streams (also called lazy lists) and which give rise to sets of abstract syntax with infinitely broad branching. We can add just A-streams, which permits syntax to mention infinite lists of atoms. We can add [L]E, which permits syntax to contain bindings by infinite lists of distinct atoms.

Our results carry through to these extensions. Furthermore in the rest of this paper we extend our theory powerfully to sets not necessarily of abstract syntax trees, and which in full FMG may be much larger and more complex than anything contained in U.

5 α-equivalence as a mathematical notion

We have related different kinds of inductive datatype for syntax, using datatypes of abstract syntax constructed in U by means of proofs based on induction on the signatures defining the datatypes. This made things nice and concrete, but it ties us to a concrete notion of signature and to working only on sets which happen to be abstract syntax trees.

We can do better: we can jettison both the signatures and their sets of abstract syntax trees, and define useful functions on general elements u ∈U with no assumption of inductive structure. We call this type of reasoning ‘syntax-free’.

5.1 Equivariance

Recall that U was defined with an inherently ‘syntax-free’ notion of ‘free names of u’ given by Su. When Su = ∅, u ‘mentions no names’.

Because this is an important property we give it a fancy name: say u is equivariant when Su = ∅.

We introduced a notion of ‘equivariance’ in §3, for classes (not elements) of U. The two notions coincide in a suitable sense:

Lemma 16

(1) u is equivariant precisely when ∀π. π · u = u.

(2) u is equivariant precisely when ∀y, π. y ∈u ⇒π · y ∈u.

Proof

The second part follows from the first, for suppose π · u = u always and y ∈u. Recall that π · u = {π · y | y ∈u}. Then obviously π · y ∈u. Suppose conversely y ∈u implies π · y ∈u. Then π · u ⊆u. But note that PA is a group, so that y = π−1 · (π · y) ∈u and u ⊆π · u.

Now we prove the first part. Suppose u is equivariant. Then π#u always, and by the fourth part of Lemma 3, π · u = u. Now suppose π · u = u always. Then by the second part of Lemma 3, π · Su = Su always, and the only way this can happen is if Su = ∅. 2

Call a function f equivariant when for all π and x, fπ · x is defined and

π · fx = fπ · x. (8)
Lemma 17

Suppose f ∈U is the graph of a function. Then Sf = ∅ if and only if π · fx = fπ · x always — that is, the two notions of equivariance just described, agree where they overlap.

Proof

Suppose f = {⟨x, fx⟩| x ∈dom(f)}. Then

π · f = {⟨π · x, π · fx⟩| x ∈dom(f)}.

Suppose π · f = f. Then we read f(π · x) = π · fx directly off the equation above. Conversely suppose fπ · x is always defined and π · fx = f(π · x). Then ⟨π · x, π · fx⟩∈f. Thus f is defined at π · x, and f(π · x) = π · fx as required.

2

Lemma 18

If f is injective (and thus bijective between imgf and domf) then f is equivariant if and only if f −1 is equivariant.

Proof

Choose some y = fx. Then π·y = fπ·x and (f −1π·y) = π·x = π·f −1y.

2

How does the support of fx relate to the support of x?

Lemma 19

(1) If f is equivariant then Sfx ⊆ Sx and Fix(Sx) ⊆ Fix(Sfx) always.

(2) If f is equivariant and injective then Sfx = Sx.

(3) If f(x, y) is equivariant and injective, then Sf(x, y) = Sx ∪ Sy.

Proof

(1) Suppose f is equivariant, so π · fx = f(π · x) always. Using Lemma 3 it is also the case that π · Sfx = Sf(π · x). Now if π#Sx (that is, if π ∈ Fix(Sx)) then π · x = x so π · Sfx = Sfx. Since this is valid for any π#Sx, it must be that Sfx ⊆ Sx.

(2) Direct from the first part of this lemma, and by the previous result.

(3) Suppose π · f(x, y) = f(x, y). By the various properties we assumed, this happens precisely when π · x = x and π · y = y. The result follows.

2

It is generally useful to assume a function is equivariant: if not we parameterise until we obtain one that is.

A fundamental theorem of model theory is that if we systematically permute the underlying sets of a model, we obtain a new model in a natural way. Thus we know from very general principles [11] that all functions, if sufficiently parameterised, must be equivariant.

5.2 A word on support

The reader familiar with FM theory will no doubt recall that support has another characterisation in terms of freshness and И. This is indeed the case here:

Lemma 20

(1) a#x if and only if Иb.(b a) · x = x (‘a is not in x precisely when if we rename it to be a fresh b, nothing happens’).

(2) p#x if and only if Иq.(q p) · x = x (‘p is not in x precisely when if we rename it to be a fresh q, nothing happens’). .

(3) As a corollary of part 1, x is equivariant precisely when ∀a. a#x.

(4) As a corollary of part 2, x is equivariant precisely when ∀p. p#x.

Proof

(1) Suppose Иb.(b a) · x = x. By part 2 of Lemma 3, also Иb.(b a) · Sx = Sx. Since Sx is countable and all but countably many b satisfy b ∉ Sx, it follows by elementary properties of sets and part 1 of Lemma 2 that a ∉ Sx.

Conversely suppose a ∉ Sx. Then for each b ∉ Sx it is the case that (b a) · x = x by part 4 of Lemma 3. The result follows.

(2) Suppose Иq.(q p) · x = x. That means that there is some countable set S such that for all q#S, (q p) · x = x. By part 2 of Lemma 6 we know Sq = {q1, q2, . . .}, and by part 2 of Lemma 2 SS = S. Since all sets concerned are countable and A is uncountable, there is one (actually uncountably many) q#S, p, x such that (q p)·x = x. By part 2 of Lemma 3 also (q p) · Sx = Sx and it follows by part 1 of Lemma 2 that p#x.

Conversely suppose p#Sx. By part 3 of Lemma 6, {p1, p2, . . .}∩Sx = ∅ and we can use that part again along with part 4 of Lemma 3 to verify that for any other q#Sx we have (q p) · x = x. The result follows.

(3,4) Left-to-right is immediate since it follows that Sx = ∅. Right-to-left follows since the intersection of any set with the empty set, is empty.

2

Strictly as an aside for the reader who is not surprised by part 3 of the result above, because they have seen it in FM, we now show that U is in fact rather special and that in full FMG we cannot take this result for granted.

Define an elementwise permutation action on uncountable sets C ⊆U as π · C = {π · u | u ∈C} and let a#C be defined as above by Иb.(b a) · C = C (as is the case in FM). Then we semi-formally (because we have not defined FMG) state:

Lemma 21

Part 3 of Lemma 20 fails in full FMG; there exist C and π such that ∀a. a#C is true, but π · C = C is false.

(Of course we have not yet defined FMG set theory, but being a set theory of significant expressive power, it includes uncountable sets and in particular the ones we construct in the proof below.)

Proof.

Choose any p ∈L and define

Cdef= {π · p | Sπ is finite}.

(Recall that Sπ being finite is equivalent to π(a) = a holding for all but finitely many atoms. The canonical example of such a π is (a b), and the canonical example of a π which is not so is (q p) for some q#p.)

We can easily verify that a#C for any a, but also for any fresh q#p it is the case that (q p) · C ≠ C. 2

In fact, on of our reasons for considering U is that we can build and investigate L and И in it, and still have part 1 of Lemma 20. We return to this issue later in §6.2 (fuzzy support in FMG sets); a suitable version of part 4 of Lemma 20 remains valid, see Lemma 43.

First, we return to U because even without fuzzy support, it is by no means without novelty. . .

5.3 Abstractive functions or, syntax-free “quotient by α-equivalence”

Call an equivariant function f purely abstractive when

∀x, x′ ∈dom(f). fx = fx′ ⇒∃π ∈Fix(Sfx). x′ = π · x.

Write Id : U →U for the identity function mapping u to itself. Later it will be useful to write IdX for Id restricted to being a partial function on some X ⊆U.

Lemma 22

(1) Id is abstractive.

(2) The abstraction function λa, x.[a]x : A × U →U is purely abstractive.

(3) The unique function ! from A to the unit set 1 = {∗} is purely abstractive.

(4) The tail-of and head-of functions tl : L →L and hd : L →A are purely abstractive.

(5) The ‘remove atom’ function λU, a.U \ {a} defined for U ∈P≤ω(A), is purely abstractive.

(6) The tail-of and head-of functions tl : A-stream →A-stream and hd : A-stream →A are not purely abstractive.

Proof

(1) If Idx = Idy then x = y and we take π equal to Id (the identity permutation; we shall always make it clear which Id we mean).

(2) Suppose [a]x = [a′]x′. Choose some fresh c#a, x, a′, x′. Then [a]x@c = (c a) · x = (c a′) · x′ = [a′]x′ by Lemma 8. It follows using Lemma 3 that (a, x) = (a c) ◦ (c a′) · (a′, x′), and we observe by calculations that (a c) ◦ (c a′) ∈ FixS([a]x).

(3) Suppose !a =!b. Well, that always happens, and S∗= ∅ so it suffices to observe that (b a) · a = b.

(4) Suppose tl(p) = tl(q). By definitions we know that hd(p)#tl(p) and hd(q)#tl(q), so (hd(p) hd(q)) ∈ Stl(p). Now observe that (hd(p) hd(q)) · p = q.

Suppose hd(p) = hd(q). Choose some r#p, q. Then observe that (r tl(p)) · p = (r tl(q)) · q. It follows by calculations that p = (r tl(p)) ◦ (r tl(q)) · q, and (r tl(p)) ◦ (r tl(q))#hd(p), hd(q).

(5) Suppose U\{a} = U ′\{a′}. Choose some fresh c#a, U, a′, U ′ and observe that (c a) · (U\{a}) = (c a′) · (U ′\{a′}). The result follows similarly to the case for abstractions.

(6) It suffices to provide a counterexample. Consider s = [a, a, a, a, a, . . .] and s′ = [b, a, a, a, a, . . .]. Then tl(s) = tl(s′) but there is no π such that π·s′ = s. Similarly consider s and s′′ = [a, b, b, b, b, . . .]. Then hd(s) = hd(s′′) but there is no π such that π · s = s′′.

2

We shall assume basic properties of permutations, freshness, and support (most notably Lemma 3) without comment henceforth.

α from (5) is not purely abstractive in general. For the example of L and Lnc, observe that α(λa.λb.b) = α(λa.λa.a) but no π exists to make them equal.

This example motivates the following definition:

Call f Barendregt abstractive when for every y in img(f) there is a unique Fix(Sy)-orbit in f −1y whose support has maximal cardinality. Call an element of this orbit a Barendregt representative.

Lemma 23

(1) A × A → 1 is Barendregt abstractive with a Barendregt representative ⟨a, b⟩ for (any) a ≠ b.

(2) A + A → 1 is not Barendregt abstractive because Inl(a) and Inr(a) both

map to ∗ and are not related by a permutation π.

(3) α from §4 is Barendregt abstractive. A Barendregt representative of λ[a]λ[a]a is λa.λb.b.

Proof

By simple calculations. A λ-term satisfying the Barendregt variable convention [12] (that all bound variable names be distinct from each other and from the free variable names) is precisely what we here call a Barendregt representative. 2

It may be useful to recall that λ[a]λ[b]b = λ[a′]λ[b′]b′ = λ[a]λ[a]a ∈ιL. However λa.λb.b ≠ λa′.λb′.b′ ≠ λa.λa.a ∈ιLnc — all these expressions map to the same element under α.

Given classes X, X′, Y, Y ′ ⊆U and f : X →X′ and g : Y →Y ′, write f × g : X × Y →X′ × Y ′ and f + g : X + Y →X′ + Y ′ for the obvious functions on products and sums. For convenience, write Inl(X) ⊆X + Y for the left-hand component of the disjoint sum, and similarly for Inr(Y ).

Theorem 24

Continue the notation just established. Then:

(1) If f and g are purely/Barendregt abstractive then f + g mapping Inl(x) to Inl(fx) and Inr(y) to Inr(gy) is purely/Barendregt abstractive.

(2) If f and g are purely/Barendregt abstractive then f × g mapping ⟨x, y⟩∈ dom(f) × dom(g) to ⟨fx, gy⟩ is Barendregt abstractive.

(3) The map λx, y.[x]y is Barendregt abstractive.

As a corollary, the usual α-equivalence quotient on inductive syntax is Barendregt abstractive.

Proof

(1) The Barendregt representative of fx ∈ Inl(X′) is x, similarly for fy.

(2) We consider just the case of products. Given z = ⟨zx, zy⟩∈X′ × Y ′ let x and y be Barendregt representatives. Let πx be a permutation in FixSzx mapping any difference between Sx and Szx to some fresh set of atoms, and similarly let πy ∈ FixSzy map Sy \ Szy to some other fresh set of atoms. The Barendregt representative of z is ⟨πx · x, πy · y⟩.

If we accept that the usual α-equivalence quotient on inductive syntax is the identity on most components, and the abstraction function λa, x.[a]x on A×X where appropriate, then the result follows by induction on the datatype. 2

Corollary 25

Second projection on a pair whose first element is in A, write this π2 = λa, x.x, is Barendregt abstractive. Similarly for second projection on a pair whose first element is in L.

Proof

Combining the previous theorem with the observations about ! which precede it. The Barendregt representatives are tuples ⟨a, z⟩ such that a#z. 2

(Recall that a#z means a ∉ Sz.)

There is a simple connection between Barendregt abstractive and purely abstractive functions:

Lemma 26

A Barendregt abstractive map gives rise to a purely abstractive map on the subset of its domain consisting of elements with support of maximal cardinality.

Proof

By unpacking definitions. 2

So results of purely abstractive functions can usually be extended to ones of Barendregt abstractive functions, modulo the ‘junk’ of non-Barendregt representatives. Purely abstractive functions are a little easier to work with, so we may prefer to consider them, but this is just for convenience unless stated otherwise.

Something quite similar to all this is discussed (in the framework of ZF sets) in well-known work by McKinna and Pollack [13]. The apparatus of abstractive functions can be viewed as an abstract account of a phenomenon of which an instance is treated in [13] as a concrete methodology.

We have defined a new abstract class of functions and shown that a concrete class of functions are a subset of them. Barendregt abstraction corresponds to ‘quotient by α-equivalence’.

For this to be most useful, we need a notion of ‘pick a representative’.

5.4 Generalised И and Barendregt representatives

Suppose f is a purely abstractive equivariant function and suppose F is another equivariant function with dom(F) = dom(f). Write

F <ab f when for all x ∈dom(f), SFx ⊆Sfx.

We argued in the previous subsection that f is a general α-equivalence quotient map. We shall now show that F <ab f is the condition ‘F respects (f)-α-equivalence’.

Theorem 27

For fixed f there is a one-to-one correspondence between F <ab f and equivariant h such that dom(h) = img(f) and img(h) = img(F). Write ИfF for the unique h corresponding to F:

•F<abff••ИfF(9)

(If f is Barendregt abstractive, the result still holds, modulo the ‘junk’ of non-Barendregt representatives in dom(f).)

Proof.

Suppose we have F as in the statement of the theorem. We now define ИfF: choose any y ∈img(f) and pick a representative of y, that is, some x ∈dom(f) such that fx = y.

Let ИfF(y) def= Fx.

We must show this is well-defined. So suppose x′ is any other element such that fx′ = y. By the purely abstractive property there exists π ∈ FixSy such that x′ = π · x. By equivariance of F we know Fx′ = Fπ · x = π · Fx. Also by F <ab f we know SFx ⊆ Sfx = Sy and so FixSy ⊆ FixSFx. So π ∈ FixSFx so by Lemma 19 we know Fx′ = π · Fx = Fx as required.

The reverse map is given by composition: given h such that dom(h) = img(f) the corresponding F is h ◦f.

It remains to show that these maps are inverse, that is

(ИfF) ◦f = F andИf(h ◦f) = h. (10)

(1) For any x, by definition (ИfF)(fx) = F(x′) for some x′ such that fx′ = (fx). Since f is assumed purely abstractive, there is some π#fx such that x′ = π · x. But since F <ab f also π#Fx. So Fx′ = π · Fx = Fx.

(2) For any y, by definition Иf(h ◦f)(y) = (h ◦f)(x) for some x such that fx = y. So this is just hy.

2

If img(f) is a two-element set we can interpret it as truth values. We may use this result for predicates without comment.

For example:

• There is a 1-1 correspondence between maps f out of A × X such that

a#f(a, x) always, and maps out of [A]X. This is a known principle of FM techniques [2, Lemma 6.3].

• If F = λa, z.a#z (restricted to those a and z such that a#z) and f = π2 = λa, z.z then h is the (always true) function λz.Иa.a#z. This is the known axiom (Fresh) [2, page 8].

• There is a 1-1 correspondence between maps f out of L × X such that p#f(p, x), and maps out of [L]X.

• . . . and so on.

The construction above is useful because it systematises the treatment of choosing representatives and calculating on them, also for sets which may be much more complicated than products and projections.

We made a simplifying assumption that f, F, and h be all equivariant. This becomes false the moment they are parameterised over z′, which may contain atoms. Those parameters can simply be incorprated into the arguments, or (if the reader likes) they can verify that the proofs above do generalise to this more general situation.

5.5 Freshness

We observed in the last subsection that:

(1) ! : A → 1 is purely abstractive and

(2) π2: A × Z →Z is Barendregt abstractive.

The corresponding generalised И quantifier И!F and Иπ2F are the well-known FM И-quantifier, choosing a fresh atom (for a parameter z ∈Z).

In the rest of this section we concentrate on !:X → 1. In fact π2: X×Z →Z is more useful in practice because there the atom is chosen fresh for a parameter; the arguments below will (obviously) work for π2 as well, just with a small overhead of writing ‘Z’ everywhere which we prefer to avoid.

For what sets of X does Иx ∈X.φ(x) have proper meaning?

Theorem 28

! : X → 1 is purely abstractive if and only if for all x, x′ ∈X there exists π such that x′ = π · x.

Proof

Suppose ! is purely abstractive. S∗∈1 = ∅ and Fix∅= PA. Also !(x) =!(x′) always. Unpacking definitions, for all x and x′ there is some π such that π · x = x′.

Conversely suppose for all x and x′ that there is some π such that π · x = x′. Clearly this validates the condition for ! to be purely abstractive. 2

Thus ! above is purely abstractive when X consists of a single orbit under PA.

We shall write Иx ∈X.F(x, z) for Иπ2F, and we say that X has a И-quantifier. In fact it suffices for ! : X → 1 to be Barendregt abstractive (e.g. X = Aω), but then we can restrict attention to the elements of maximal support in X (e.g. L ⊆X, see below) from which generalised И chooses its representative. On this subset ! is purely abstractive, thus the situation of the theorem above is indeed canonical and useful.

We now show that L satisfies this condition. Recall that p ∈L is a countably infinite stream of distinct atoms.

Lemma 29

For all l, l′ ∈L there is a π such that l′ = π · l.

Proof

π is given by (l r) ◦ (r l′) for any r#l, l′. 2

(Recall r#l, l′ means ri ≠ lj and ri ≠ l′ j′ for all i, j, j′. Recall from Lemma 7 cannot just use (l′ l).)

A and L are minimal and maximal sets for which a И-quantifier exists, in the following sense:

Lemma 30

If X is equivariant and such that for x, x′ ∈X there always exists some π with π · x = x′, then X is a quotient of L under some subgroup of PA.

Proof

Pick any x ∈X. This has countable support, so put the atoms in that support in some order and, if the set is finite, pad it with countably many distinct fresh atoms. Write this stream p ∈L and declare φ(π · p) = π · x. It is not hard to verify that provided X is equivariant then φ is well-defined and surjective, and that its kernel is a subgroup of PA. 2

(Recall we stated we would only be concerned with equivariant classes, in §3.)

We used this technology to study the π-calculus [14] and models of process calculi with dynamic allocation [15]. FreshML is based on a universe with finite support, so L does not appear; in a lazy programming version based on a language such as Haskell, L might be useful for foundations.

A benefit of these FM(G) techniques is that they not only account for binding in the syntax, but also in the semantics, which may very well include functions and consider infinite behaviour with infinite allocation of names and thus binding by L or variants of it. 5

5 A variant of this not using L was developed and applied by Shinwell and Pitts to give semantics to FreshML, see [5].↩

5.6 Scope extrusion for И

Generalised И exhibits generalised scope-extrusion. This is the characteristic property of most notions of freshness, that if we choose a fresh name in some context, we can also choose ‘fresher’ for a wider context.

Theorem 31

Suppose f, F, and G are equivariant. Suppose f is abstractive, that domF = domf = X, that imgf = X′, that imgF = Y , that domG = Z × Y , and that imgG = U.

Suppose F <ab f. Then λz, x.G(z, Fx) <ab IdZ×f, ИfF and Иf(λz, x.G(z, Fx)) are both well-defined, and

G(z,ИfFx) =ИIdZ×fG(z, Fx). (11)

In pictures, the left-hand diagram commutes if and only if the right-hand diagram commutes:

Z × XG◦(Z×F)Z×fUZ × X′G◦(Z×(ИfF))⇔Z × XG◦(Z×F)Z×fUZ × X′ИZ×f(G◦(Z×F))(12)

Here the Z annotating the arrows actually are the identity IdZ. We use this notation without comment henceforth. ◦, as before, denotes function composition.

Proof.

The proof is just by unpacking definitions. Since these have accumulated we give the process in a little detail.

The conditions on domains and images just ensure that all functions are well-defined.

λz, x.G(z, Fx) <ab IdZ × f when for all z and x, SG(z, Fx) ⊆ S⟨z, fx⟩. By Lemma 19 we know S⟨z, fx⟩= Sz ∪ Sfx. Since G is equivariant we know by Lemma 19 that SG(z, Fx) ⊆ Sz ∪ SFx, and we are done. Therefore the functions in question are well-defined.

Now G(z,ИfFy) is the value G(z, Fx) at any x such that fx = y and x has maximal support. Иfλz, x.G(z, Fx)(z, y) is the value of G(z, Fx′) at any x′ such that fx′ = y and x′ has maximal support and such that Sx′ ∩ Sz is minimal. In particular Fx = Fx′ and we are done. 2

When we work with representatives we do not worry about generating names fresh for all possible contexts: this is impossible since we do not know a priori what atoms those contexts may contain.

So the above tells us what we always knew; that it does not matter because we can always extrude the scope of our choice of fresh name ad hoc. It is not unusual to see results of the form “(ν[a]P) | Z and ν[a](P | Z) are equivalent up to bisimilarity” (this example is of course taken from the π-calculus and we have written Z instead of Q to connect the notation to the theorem above). Usually such results are proved on a case-by-case equivalence-by-equivalence basis, perhaps one day they might be stated as ‘general nonsense’ consequences of theorems like the ones above.

The following lemma is useful in Theorem 42, and we also used it ‘secretly’ when we informally wrote some isomorphisms in Theorem 15.

Lemma 32

Suppose F, and G are equivariant. Suppose that domF = L×X, imgF = Y , domG = L×Y , and imgG = U. Suppose further that F, G <ab π2 (that is if l#x and l#y then l#F(l, x) and l#G(l, y)).

Then λl, x.G(l, F(l, x)) <ab π2 and Иl.G(l,Иl.F(l, x)) =Иl.G(l, F(l, x)) (and this is all well-defined).

In pictures, the left-hand diagram commutes if and only if the right-hand diagram commutes:

L × L × XG◦(L×F)π2◦π2UXИπ2G◦(L×Иπ2F)⇔L × Xλl,x.G(l,F(l,x))π2UXИπ2λl,x.G(l,F(l,x))(13)
Proof

By the properties of И we know it does not matter which Barendregt representatives we use. So suppose we used the representative (l, x) to calculate F(l, x) = y so that l#x. Then l#y and we can use (l, y) to calculate G(l, y). The result follows. 2

∀x, y. x ∈y ⇒y ∉A (Sets)∀x, y ∉A. (∀z. z ∈x ⇔z ∈y) ⇒x = y (Extensionality)∀x. ∃y ∉A. ∀z. z ∈y ⇒(z ∈x ∧φ) (y not free in φ) (Collection)(∀x. (∀y ∈x. [y/x]φ) ⇒φ) ⇒∀x. φ (∈-Induction)∀x. ∃z. ∀y. y ∈z ⇒∃x′. (x′ ∈x ∧y = F(x′)) (Replacement)∀x, y. ∃z. x ∈z ∧y ∈z (Pairset)∀x. ∃y. ∀z. z ∈y ⇒(∃w ∈x. z ∈w) (Union)∀x. ∃y. ∀z. z ∈y ⇒∀w ∈z. w ∈x (Powerset)∃x. ∃y. y ∈x ∧∀y ∈x. ∃w ∈x. y ∈w (Infinity)¬wo(A) (AtmLrg)∀x. ∃S ∈P(A). wo(S) ∧S supports x (Fresh)

F any function-class, φ any predicate defined in the logic of FMG. wo(x) is a predicate expressing that there exists a set which is a well-ordering of x.

Fig. 1. Axioms of FMG

6 The underlying theory of sets

6.1 Axioms

FMG sets is a set theory similar to the original FM sets [1], but considerably more general. So far we have worked in U, a concrete model which is an initial fragment of a standard cumulative hierarchy model of FMG. We now define the theory.

The logic of FMG sets is First-Order Logic [7,8] with a constant symbol A the set of atoms and a binary predicate ∈ set inclusion.

The axioms of FMG sets are given in Figure 1.

First we make some comments on notation and our choice of axioms:

• We write P(x) for the powerset of x and wo(x) for the predicate “there exists a set which is a well-ordering of the elements of x”.

• A well-ordering is a well-founded trichotomous relation. A relation R ⊆x×x is trichotomous when for all z, z′ ∈x, precisely one of zRz′, z = z′, or z′Rz holds. A relation is well-founded when there exist no infinite strictly descending chains. The canonical example of a well-ordering is the numerical ‘less than or equal’ relation on natural numbers 0, 1, . . .. This ceases to be

well-founded if we add negative numbers, and is not trichotomous if we move to the complex integers a + ib, ordered by the size of their modulous.

• In (Extensionality), (Union), and (Powerset) we could use ⇔ in the axioms, but the system is equivalent.

In the case of (Extensionality) this is by the rules of equality in first-order logic.

In the cases of (Union) and (Powerset) we can use the axioms as stated to deduce that some set containing the union or powerset, and then use (Collection) to deduce that the collection which is the union or powerset, is a set.

It is a general fact about this style of axiomatisation of set theory that the impact of most axioms is just to ensure that there are enough sets around; (Collection) then puts on the final touches, so to speak.

Where does FMG stand with respect to FM sets?

FM sets has a notion of a ‘small set of atoms’. The И quantifier means precisely ‘for all but a small set of atoms, . . . ’.

Originally [1,16] ‘small’ was equal to ‘finite’. We also took A to be countably infinite, so the Иa.φ(a) means ‘for countably many a, φ(a)’. It was folklore that we could just have well have taken A to be uncountable; the important point was what we might call the ‘size of small’.

U took ‘small’ to mean ‘countably infinite’. Of course we also insist A be uncountable, so that И is not degenerate.

FMG set theory generalises this further to:

‘small’ means ‘internally well-orderable’.

This is very nice because (rather unexpectedly, perhaps) it makes no commitment to actual size; FMG sets is consistent with any of the following axioms: “Small is finite”, “small is countable”, and “small is ωω” (here ω is the first uncountable ordinal).

If we add the first as an axiom in FMG sets we recover FM sets. The second possibility gives a set theory suitable for containing U in its standard cumulative hierarchy model. Further possibilities give theories with increasingly large small sets of atoms. Or, we can add no extra axiom and consider FMG with no further assumptions.

As we mentioned in the Introduction, ‘small equals well-orderable’ seems the right choice, because it gives enough isomorphisms to rename atoms:

Lemma 33

For any two well-orderable sets α and β, one is in bijection with a subset of the other.

Proof

See [4, Lemma 6.3]. 2

We obtain permutations from these injections and we can use them to rename atoms to be fresh. This turns out in practice to be the property we need a small set to satisfy: that the set can always be renamed to be fresh (and the property of a large set is that this is not the case).

Write ZF for Zermelo-Fraenkel set theory (a classic mathematical foundation [3,4]).

Theorem 34

FMG set theory is consistent relative to ZF. In addition, for any ordinal α FMG set theory with an additional axiom ‘small is α’ is consistent relative to ZF.

Proof

The first part is a corollary of the second, so we concentrate on the second part.

FMG is just a theory in first-order logic (whose axioms are presented for the delectation of future generations in Figure 1). To prove consistency of any theory in first-order logic it suffices to exhibit a model. Because of fundamental limits to logic [17, Proposition VI] a model, i.e. consistency, cannot be exhibited in any absolute sense, but only relative to assuming the consistency, i.e. the existence of a model, of another theory.

So suppose we have a model of Zermelo-Fraenkel set theory. We construct a cumulative hierarchy model of FMG set theory (with ‘small = countable’; the generalisation to any α is very easy) as a subclass of the elements of that model. This suffices to prove relative consistency. We only sketch the construction, since this is an entirely standard method found often in the literature [18,19].

Choose any uncountable ZF set for A. Define a hierarchy of increasing subclasses by:

(1) V0 = A.

(2) Vα+1 is the set of subsets of Vα with small support, union with Vα.

A set x has small support when there exists a countable set of atoms S such that if π ∈ FixS then π · x = x.

Then the model of FMG is V =⋃i Vi, the union of the Vi. Set-membership in the model is interpreted by set-membership in V .

The proof that this is a model of the axioms of FMG sets given in Figure 1 is long but routine. We only sketch it here:

(1) (Sets) is valid by construction; everything in V is an atom or a set of (sets of (sets of . . . )) sets of atoms.

(2) (Extensionality) is inherited from ZF.

(3) (Collection) is proved by induction on the size of φ, a formula in the logic of FMG (the same logic in which the axioms are expressed).

(4) (∈-Induction) is by the inductive nature of the construction.

(5) (Replacement) is inherited from ZF.

(6) (Pairset) and (Union) likewise.

(7) (Powerset) is inherited from ZF, bearing in mind that we only take the sets with countable support.

(8) (Infinity) is inherited from ZF.

(9) (AtmLrg) is by the fact that any set encoding a well-ordering of A is invariant only under the identity permutation on A.

(10) (Fresh) by the construction of the cumulative hierarchy, which only takes sets with small support.

2

In the presence of an axiom that ‘small’ is (at least) ‘countable’ we can interpret U in this cumulative hierarchy and abstractions, as promised, are implementable as the collection defined in §2.1, which is now also a set.

The permutation action π · x is defined by ϵ-induction starting at atoms and pointwise on sets, thus:

π · a = π(a) π · x = {π · x′ | x′ ∈x}

The following result corresponds in FMG to the same result in FM (see for example [2, Lemma 4.7] and [20, Proposition 2]):

Theorem 35

(Equivariance) (1) If φ(x1, . . . , xn) is a predicate in FMG then

φ(x1, . . . , xn) ⇔φ(π · x1, . . . , π · xn)

is always provable.

(2) If f(x1, . . . , xn) is a function-class specified in FMG then

π · f(x1, . . . , xn) = f(π · x1, . . . , π · xn).
Proof

(1) By induction on the language of FMG (just like the similar result for FM [1,2]). The important base cases are π · A = A and x ∈y if and only if π · x ∈π · y by the pointwise definition of permutation.

(2) A function-class is merely a predicate specifying its graph. We use the first part to deduce

φ(x1, . . . , xn, z) ⇔φ(π · x1, . . . , π · xn, π · z)

and the result follows immediately.

2

In words:

Any predicate specified in (the logic of) FMG sets is equivariant over its arguments, and so is any function-class.

FMG set theory is a set theory so models of FMG sets are closed under powersets, not just countable powersets as U was (nota bene: FMG powersets do not take all the subsets of the ambient foundation, only those with small support). FMG sets displays a richness of structure far exceeding U.

6.2 Lifting constructions in U to the set theory

A is a set in FMG, identified by the predicate - ∈A. So are the natural numbers, pairs, cartesian products, disjoint sums, lists, streams, and their constructors such as ⟨x, y⟩, Inl(x), Inr(x), and so on; the constructions are just as in §2.3.

In particular we recall that ⟨x, y⟩ can be implemented in sets as {{x}, {x, y}}.

L and A are now sets. Function-sets are built as their graphs as is standard. PA is identified by:

PAdef={ f : A →A⏐⏐⏐ f bijective}.
Lemma 36

(1) π′ · π = ππ′.

(2) Any permutation π ∈PA is the identity off some well-orderable set of atoms.

In the first part, π′ ·π denotes π′ (the permutation) acting on π (the function-set). ππ′ denotes the function-set expressing the graph of the permutation π′ ◦π ◦π′−1.

Proof.

(1) We observe that π′ acts on the graph of π by acting on the atoms within it; it is a fact of group theory that conjugation does the same.

(2) If S supports π then S contains every atom such that π(a) ≠ a (since otherwise we could permute π(a) to something else). Since π is a set, it has well-orderable support. The result follows.

2

If S ⊆A write

Fix(S) for {π ∈PA | ∀a ∈S. π(a) = a}.

We say

S supports x when ∀π ∈PA. π ∈Fix(S) ⇒π · x = x.

Finally define

Sx by⋂ { S ⊆A⏐⏐⏐ ∀π. π ∈Fix(S) ⇒π · x = x},

(though the next result shows this is not as useful as we might imagine).

Lemma 37

(1) If S and T support x and are well-orderable, then so is S∩T.

(2) Sx does not necessarily support x.

Proof

(1) Suppose S and T support x and suppose π′ fixes just S∩T. Let U = S\T. By (AtmLrg) A is not well-orderable and since U certainly is, we can choose some U ′ disjoint from S, T, U, and a supporting set for π′.

Since U and U ′ are well-orderable and the same size, there is an idempotent permutation π = π−1 bijecting U with U ′ and fixing all other atoms (swap the ith elements of U and U ′, for arbitrary but fixed well-orderings). Now π fixes T so π · x = x. Now π′ fixes S ∩T and also U ′ so π ◦π′ ◦π which is equal to π′π (since π = π−1) fixes π · (S ∩T) ∪π · U ′ which includes S. Therefore π ◦π′ ◦π · x = x. Applying π to both sides and simplifying we deduce that π′ · x = x as required.

(2) It suffices to consider the example of Lemma 21.

2

So here, at least, FMG is not as tractable as FM (or U)! The notion of a supporting set is still valid and useful, and we may still intersect supporting sets to obtain smaller supporting sets — but if we do this infinitely often we may ‘miss an infinitesimal bit of support’.

When Sx does not support x, say x has fuzzy support. When Sx does support x, say it has sharp support.

U identifies a convenient subset of the FMG universe which exhibits inductive datatypes of abstract syntax with infinitary binding, but still has sharp support.

Lemma 38

(1) Permutations have sharp support, and Sπ = {a | π(a) ≠ a}.

(2) a ∈A and p ∈L have sharp support, and Sa = {a} and Sp = {p1, p2, . . .}.

(As before) π · p = [π · p1, . . .].

(3) If x has sharp support, then so does π · x.

(4) If S supports x then π · S supports π · x. As a corollary, Sπ · x = π · Sx.

Proof

(1) A permutation is represented as a set by its graph; e.g. (a b) = {⟨a, b⟩, ⟨b, a⟩, ⟨c, c⟩, ⟨d, d⟩, . . .}. It is not hard to verify the requisite properties, recalling that π acts pointwise on sets and ⟨x, y⟩ is just {{x}, {x, y}}.

(2) By concrete calculations.

(3) The property of being a supporting set can be expressed by a predicate φ in FMG. The result follows by part 1 of Theorem 35 (a proof by concrete calculations is also possible). The second part follows by calculations, or directly by part 2 of Theorem 35.

2

As a matter of notation write

x#y when ∃S, T. S supports x ∧T supports y ∧S ∩T = ∅.

The reader may like to compare this with the corresponding definition from §2.1, which was x#y when Sx ∩ Sy = ∅. The difference is of course due to the possibility of fuzzy support; if x and y have sharp support the two versions become equivalent.

The following result is a useful corollary of Equivariance (it also generalises Lemma 19, which there was proved for U by concrete calculation):

Corollary 39

(1) If S supports x1, ..., xn and f is a function-class specified in the language of FMG with parameters amongst the xi, then S supports f(x1, . . . , xn).

(2) As a corollary, if f(x1, . . . , xn) is a function-class in FMG with parameters x1,... xn, then if p#x1, . . . , xn then p#f(x1, . . . , xn).

Proof

It suffices to apply the second part of Theorem 35. 2

In words:

Any function-class specified in (the logic of) FMG sets, does not create support.

We verify that a suitable version of Lemma 3 is still valid:

Lemma 40

(1) If S supports x then π · S supports π · x. Also, π · (Sx) = S(π · x).

(2) x#[x]y.

(3) If π#x then π · x = x.

(4) If π(a) = π′(a) for all a ∈S for some S supporting x, then π · x = π′ · x.

Proof

(1) Direct from Theorem 35 for the predicate ‘supports’ and the function ‘S’.

(2) From Lemma 41.

(3) π#x when π fixes a set supporting x. The result follows.

(4) By definition of supporting set.

2

Abstractions [x]y are defined much as in §2.1, but we must assume x has sharp support, and protect against the possibility that y has fuzzy support by not using Sy:

[x]ydef= {⟨π · x, π · y⟩| ∃S. S supports y ∧π#S\Sx}.
Lemma 41

(1) π · ([x]y) = [π · x](π · y) holds.

(2) If x has sharp support then S supports y if and only if S\Sx supports [x]y.

Proof

(1) By part 2 of Theorem 35.

(2) In essence identical to the proof of the case for abstractions of part 4 of Lemma 3, we sketch half of it in full: We can prove by calculation that {π | ∃S. S supports y ∧π#S\Sx} is a group.

Suppose x has sharp support and S supports y. Suppose π ∈ Fix(S\Sx). Then

π·[x]y ={ ⟨π′ · (π · x), π′ · (π · y)⟩⏐⏐⏐ ∃S′, π′. S′ supports π · y ∧π′ ∈Fix(S′\π · Sx)}={ ⟨π′′ · x, π′′ · y⟩⏐⏐⏐ ∃S′, π′′. S′ supports y ∧π′′ ∈Fix(S′ \ Sx)}= [x]y.

Now suppose S supports [x]y and suppose π ∈ Fix(S ∪ S(x)). Then (πx, πy) ∈ [x]y. The result follows from the fact that {π | ∃S. S supports y∧ π#S\S(x)} is a group.

2

(It does not seem fruitful to consider [x]y when x does not have sharp support.)

The maps between ιE, ιEnc, and ιEdb, can also be constructed as before.

It is not hard to verify that Lemma 10 transfers unchanged to FMG. The discussions of purely abstractive and Barendregt abstractive functions, И, and freshness, transfer almost word-for-word.

6.3 Abstractions commute with pairsets, powersets, and more

Theorem 15 generalises beautifully in FMG. We give just the case for cartesian product, and also full function spaces and powersets (not just countable ones, as we did in Theorem 15).

Theorem 42

(1) [L](X × Y) ∼= [L]X × [L]Y .

(2) [L](Y X) ∼= [L]Y [L]X.
(3) [L]P(X) ∼= P([L]X).

Similarly for A, e.g. [A](Y X) ∼= [A]Y [A]X.

Proof

We consider just the cases for L; the cases of A is simpler.

(1) We map

ˆu ∈[L](X × Y ) toИl.⟨[l]π1(ˆu@l), [l]π2(ˆu@l)⟩⟨ˆu1, ˆu2⟩∈([L]X) × ([L]Y ) toИl.[l]⟨ˆu1@l, ˆu2@l⟩

These maps are well-defined since it is easy to use Corollary 39 and part 2 of Lemma 40 to deduce l#⟨[l]π1(ˆu@l), [l]π2(ˆu@l)⟩ and l#[l]⟨ˆu1@l, ˆu2@l⟩.

We now verify that these maps are self-inverse. By Lemma 32 it suffices to check that (for one suitably fresh l)

ˆu = [l]⟨([l]π1ˆu@l)@l, ([l]π2ˆu@l)@l⟩ ⟨ˆu1, ˆu2⟩= ⟨[l]π1([l]⟨ˆu1@l, ˆu2@l⟩)@l, [l]π2([l]⟨ˆu1@l, ˆu2@l⟩)@l⟩.

This follows easily, using Lemma 10.

(2) We map

ˆf ∈[L](Y X) to λˆx.Иl.[l](( ˆf@l)(ˆx@l))f ∈([L]Y )[L]XtoИl.[l](λx.f([l]x)@l)

We must check these maps are well-defined. Suppose ˆf and ˆx are given. Choose some l# ˆf, ˆx. Then ˆf@l and ˆx@l are well-defined and l#[l]( ˆf@l)(ˆx@l). Conversely suppose f is given. Choose some l#f. Then l#f([l]x) so f([l]x)@l is well-defined and l#[l]λx.f([l]x)@l.

We now verify that these maps are self-inverse. By Lemma 32 it suffices to check that (for one suitably fresh l)

( ˆf@l)x =([l]( ˆf@l)(([l]x)@l))@l f ˆx = [l]([l](λx.f([l]x)@l)@l)(ˆx@l)

This follows easily, making heavy use of Lemma 10.

(3) This is a corollary of the previous lemma, taking Y = B and observing that [L]B is naturally isomorphic to B, see Theorem 15. In full, the maps are given by:

ˆU ∈[L]P(X) toˆU ′def=Иp.{ [p]u⏐⏐⏐ u ∈ˆU@p}U ⊆[L]X to U ′def=Иp.[p]{ ˆu@p⏐⏐⏐ ˆu ∈U ∧p#ˆu}.

2

This result is important because it enables us to drop the condition implicit in the construction of U of considering just countable powersets. Since P(X) is strictly larger than X, and similarly Y X is strictly larger than Y and X (provided Y and X have more than two elements), and they not inherit any inductive structure, this theorem is one way of making formal that our treatment of names and bindings in FMG is strictly more general than the standard model given by abstract syntax trees.

This extension to function-sets is also useful, e.g. for the existence of a monad in the semantics of FreshML used to prove the language correct, and for equalities used in understanding models of behaviour [21,15].

6.4 An algebraic version

We give an alternative presentation of U and FMG in algebraic style. Fix a particular uncountable set A. Let PA be permutations of A with countable support. Then a Nominal FMG set (where small=countable) is:

∀x. Id · x = x ∀π, π′, x. π · π′ · x = π ◦π′ · x∀x.Иp.Иq.(p q) · x = x ∀x.Иa.Иb.(a b) · x = x.(14)

Here Иa.φ means that φ holds of all but a countable set of atoms, and Иp.φ means that φ holds of countable lists of distinct atoms whose atoms may be all but a countable set of atoms.

It is easy to verify that an equivariant FMG set (for any given model of FMG sets), or an equivariant subclass of U, is a Nominal FMG set. If we need more atoms we just take A to be larger and π ∈PA to have any support strictly smaller than the size of A.

Lemma 43

(1) L is a nominal FMG set with small=countable.

(2) If x ∈X is such that l#x for all l ∈L then π · x = x always.

Proof

(1) By part 2 of Lemma 38.

(2) By part 1 of Lemma 38 we know that π permutes only countably many atoms. Let S support x (we use it in a moment). We choose some l′ suitably fresh for π, S and deduce that π · (l′ l) · x = π · x. By part 3 of Lemma 38 we conclude that π · (l′ l) · x = x.

2

It is now easy to see that if we know that small=X where X is some cardinality, then similar results hold for streams of distinct atoms of length an ordinal with cardinality X. This is the correct generalisation of the FM principle that ∀a. a#x implies x is equivariant.

7 Future work

Infinite binding arises in behavioural models of reactions: for example, if P def= ν[a]aa then the π-calculus process !P is behaviourally equivalent to the ‘infinitary’ process P | P | . . . [22]. Also, if ω3def= λx.xxx then the λ-calculus process ω3ω3 is αβ-equivalent to the ‘infinitary’ process (((. . . ω3)ω3)ω3)ω3. This equivalence can be made formal by considering a behavioural notion of model, which can display infinite structure even though the trace of any particular behaviour may be finite. One such structure is considered by Montanari et al [23] which we can view as a de Bruijn-based model of behaviour which may generate fresh names, whose main interest is in powerful optimisations which merge nodes identical except for permutations of names.

If name-binding is modelled by FM-style abstractions, there is a need for infinite FM-style abstraction in the model of behaviour. 6 We have proposed one method of obtaining this effect. We have examined the proof-principles which seem useful on these objects, and by progressive abstraction we have formalised and generalised them to obtain notions such as ‘abstraction and concretion by infinitely many atoms’, ‘abstractive functions’, ‘Barendregt representatives’, ‘generalised И’, and we have described some nice results describing their properties.

6 Since this paper was submitted for publication, a paper has been published describing a semantics for FreshML which approximates this in a category with a FM-style monad representing finitely but unboundedly many abstractions [5].↩

U has an interesting capture-avoiding substitution action given as follows:

a{a↦→u} = u b{a↦→u} = b V {a↦→u} ={ v{a↦→u}⏐⏐⏐ v ∈V}([v′]v){a↦→u} = [v′](v{a↦→u}) Sv′ ∩Su = ∅(15)

(Recall that an element of U is either an atom a, a countable set V , or an abstraction [v′]v, and that for any abstraction there is a choice of v′ and v forming that abstraction such that Sv′ ∩ Su = ∅; thus this is a total function.)

Since β-reduction is given in the λ-calculus, this suggests that we might use the FM model of abstraction to obtain models of the λ-calculus that are not Scott domains, and with a set-theoretic flavour. The obstacle to this idea is that we do not know what application is. This is current work.

References

[1] M. J. Gabbay, A theory of inductive definitions with alpha-equivalence, Ph.D. thesis, Cambridge, UK (2000).

[2] M. J. Gabbay, A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing 13 (2001) 341–363.

[3] J. Bell, M. Machover, A course in mathematical logic, North-Holland, 1977.

[4] P. T. Johnstone, Notes on logic and set theory, Cambridge University Press, 1987.

[5] M. R. Shinwell, A. M. Pitts, On a monadic semantics for freshness, Theoretical Computer Science 342 (2005) 28–55.

[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) (1972) 381–392.

[7] J. Barwise, An introduction to first-order logic, in: J. Barwise (Ed.), Handbook of Mathematical Logic, North Holland, 1977, pp. 5–46.

[8] D. van Dalen, Intuitionistic logic, in: D. Gabbay, F. Guenthner (Eds.), Handbook of Philosophical Logic, 2nd Edition, Volume 5, Kluwer, 2002, pp. 1–114.

[9] J. B. Fraleigh, A First Course in Abstract Algebra, Addison-Wesley, 1994.

[10] L. C. Paulson, A fixedpoint approach to implementing (co)inductive definitions, in: CADE-12: Proceedings of the 12th International Conference on Automated Deduction, Springer-Verlag, London, UK, 1994, pp. 148–161.

[11] J. Truss, Permutations and the axiom of choice, in: H. R.Kaye (Ed.), Automorphisms of first order structures, OUP, 1994, pp. 131–152.

[12] H. P. Barendregt, The Lambda Calculus: its Syntax and Semantics (revised ed.), Vol. 103 of Studies in Logic and the Foundations of Mathematics, North-Holland, 1984. URL http://www.andrew.cmu.edu/user/cebrown/notes/barendregt.html

[13] J. McKinna, R. Pollack, Some lambda calculus and type theory formalized, Journal of Automated Reasoning 23 (3-4) (1999) 373–409.

[14] M. J. Gabbay, The π-calculus in FM, in: F. Kamareddine (Ed.), Thirty-five years of Automath, Kluwer, 2003, pp. 80–149.

[15] M. J. Gabbay, Fresh graphs, submitted (November 2003).

[16] M. J. Gabbay, A. M. Pitts, A new approach to abstract syntax involving binders, in: 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, 1999, pp. 214–224.

[17] K. Gödel, On formally undecidable propositions in principia mathematica and related systems i, available online in translation by Martin Hirzel (1931).

[18] N. Brunner, 75 years of independence proofs by fraenkel-mostowski permutation models (1996).

[19] K. Kunen, Set Theory: An Introduction to Independence Proofs (Studies in Logic and the Foundations of Mathematics), Elsevier, 1980.

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

[21] M. R. Shinwell, A. M. Pitts, M. J. Gabbay, FreshML: Programming with binders made simple, in: Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden, ACM Press, 2003, pp. 263–274.

[22] R. Milner, J. Parrow, D. Walker, A calculus of mobile processes, II, Information and Computation 100 (1) (1992) 41–77.

[23] U. Montanari, M. Pistore, History-dependent automata, Tech. Rep. TR-98-11, University of Pisa (5, 1998).