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

A study of substitution, using nominal techniques and Fraenkel-Mostowki sets

Murdoch J. Gabbay

http://www.gabbay.org.uk

Abstract

Fraenkel-Mostowski (FM) set theory delivers a model of names and alpha-equivalence. This model, now generally called the ‘nominal’ model, delivers inductive datatypes of syntax with alpha-equivalence — rather than inductive datatypes of syntax, quotiented by alpha-equivalence.

The treatment of names and alpha-equivalence extends to the entire sets universe. This has proven useful for developing ‘nominal’ theories of reasoning and programming on syntax with alpha-equivalence, because a sets universe includes elements representing functions, predicates, and behaviour.

Often, we want names and alpha-equivalence to model capture-avoiding substitution. In this paper we show that FM set theory models capture-avoiding subsitution for names in much the same way as it models alpha-equivalence; as an operation valid for the entire sets universe which coincides with the usual (inductively defined) operation on inductive datatypes.

In fact, more than one substitution action is possible (they all agree on sets representing syntax). We present two distinct substitution actions, making no judgement as to which one is ‘right’ — we suspect this question has the same status as asking whether classical or intuitionistic logic is ‘right’. We describe the actions in detail, and describe the overall design issues involved in creating any substitution action on a sets universe.

Along the way, we think in new ways about the structure of elements of FM set theory. This leads us to some interesting mathematical concepts, including the notions of planes and crucial elements, which we also describe in detail.1

Keywords: Substitution, nominal techniques, Fraenkel-Mostowski set theory.

Contents

1 Introduction 2

1.1 Design issues 3

2 Fraenkel-Mostowski set theory 6

2.1 Axioms, permutations, equivariance 6

2.2 Support 8

2.3 Orbits under the permutation action 11

2.4 α-abstraction 12

3 The substitution action 14

3.1 Axioms, pointwise substitution action, syntactic substitution action . . 14

3.2 A short quiz 17

3.3 The planes of a set 18

3.4 Construction of the first substitution action 19

3.5 Substitutions on syntax, substitutions commuting 26

4 New properties of FM: a-orbits and crucial elements 29

4.1 a-orbits 30

4.2 Crucial elements 34

4.3 Operations on sets of crucial elements 36

5 A second substitution action, using crucial elements 37

5.1 Definition and properties 38

5.2 Scope-extrusion and hereditarily finite crucial sets 42

6 Summary, related work, and conclusions 45

6.1 Summary of the two substitution actions 46

6.2 Related work 47

6.3 The rôle of Fraenkel-Mostowski sets 48

1. Introduction

Fraenkel-Mostowski set theory [7, 40] was originally developed to prove the independence of the axiom of Choice from the other axioms of Zermelo-Fraenkel set theory. It was re-discovered and used — rather far from its original application — by the author and Pitts to provide a model of naming and abstraction in datatypes of abstract syntax [23].

Fraenkel-Mostowski set theory is a foundational theory and part of its usefulness is that the model of naming and abstraction which it provides [23, 15], extends smoothly from sets representing abstract syntax to all sets including those representing non-syntactic entities such as functions, domains, and predicates. It has been a success story of the continuing relevance of set-theoretic foundations to computer science.

This model of names has inspired programming languages with datatypes for names and constructors to bind those names [36, 8], logics [35, 21], it has been used to study correctness properties of functional programming with storage [6], and in many other applications.

However, why should we wish naming and abstraction in the first place? In many cases, this is because we want a names with a capture-avoiding substitution action. For example, this is the behaviour displayed by variables in syntax.

In this paper we demonstrate by a non-trivial but elementary construction on sets that Fraenkel-Mostowski set theory also provides a model of capture-avoiding substitution on names. This model is compatible with the notion of abstraction from previous work; thus substitution is modelled in sets and we extend the Fraenkel-Mostowski story about names and abstraction from syntax to semantics, by showing how to model substitution on any set, not just sets representing syntax.

We shall show that in the case of sets representing abstract syntax, the substitution action coincides with the ‘usual’ substitution defined inductively on syntax. We show that on all sets — not just those representing syntax — the action satisfies the conditions laid out by an algebraic axiomatisation of substitution investigated in previous work [20, 22].

We will also show that more than one possible ‘substitution action’ exists: the behaviour on sets representing abstract syntax is constrained by the axioms; for more complex sets there is some freedom, and we explore the design space and specify two actions in full detail.

During the exploration of our two substitution actions we introduce some mathematical concepts which may be useful tools in their own right:

• Planes, in Subsection 3.3, particularly Theorems 3.12 and 3.13.

• a-orbits in Subsection 4.1. A fundamental technical result is Theorem 4.5, though Definition 4.11 and Remark 4.12 are more readable.

• Crucial elements in Subsection 4.2, notably Corollary 4.14, and the interaction of crucial elements with support, symmetric set difference, and permutation described in Corollary 4.15, Lemma 4.17, and Lemma 4.19.

1.1. Design issues

We now sketch the design issues involved in defining a substitution action on Fraenkel-Mostowski sets. Definitions and notation are given in full formal detail in this paper, and also also [23, 17].

Fraenkel-Mostowski sets contain atoms a, b, c, . . .. These are empty (x ∈a is impossible) but they are not equal to the empty set. Following the nominal style introduced in [23] we use atoms to model variable symbols;

• In [23] we showed how to construct datatypes of syntax up to α-equivalence (‘λ-terms’, ‘terms of first-order logic’, ‘π-calculus terms’, and so on) such that substitution — and other functions — could be defined on the datatypes purely inductively.

• In this paper we give a substitution action on all of the sets universe, write it z[a↦→x] and read it ‘substitute a with x in z’ (so z and x can be anything, not just elements representing syntax).

We want our new substitution to coincide with ‘usual’ substitution on elements representing syntax (i.e. representing labelled trees). This gives us useful information which we now sketch:

Atoms model variable symbols, therefore let

a[a↦→x] = x and b[a↦→x] = b

(x is any element, a and b are any two distinct atoms).

If Z is a finite set of elements then let substitution be pointwise:

Z[a↦→x] = {z[a↦→x] | z ∈Z} if Z is a finite set.

This ensures that tuples (z1, z2) = {{z1}, {z1, z2}} satisfy

(z1, z2)[a↦→x] = (z1[a↦→x], z2[a↦→x]).

The same holds for n-tuples and also, modulo some technical details, for infinite tuples (Corollary 3.27).

In nominal style we model α-abstraction by taking an α-equivalence class of ‘renamed variants’ of a set. For example the nominal model of ‘α-abstract the atom a in (a, b)’, written [a](a, b) (Definition 2.20) is

[a](a, b) = {(a, (a, b)), (c, (c, b)), (d, (d, b)), (e, (e, b)), (f, (f, b)), . . .}.

This is the model of syntax up to α-equivalence presented in [23].

For the reader to understand what follows in this paper, and why the mathematics will be set up in the way that it will be, it is important to have some intuition of how this model of abstraction works.

We give another example: [a](a, b, d) (where (z1, z2, z3) is (z1, (z2, z3))) is

[a](a, b, d) = {(a, (a, b, d)), (c, (c, b, d)), (e, (e, b, d)), (f, (f, b, d)), . . .}.

Note that

(d, (d, b)) ∈[a](a, b) and (d, (d, b, d)) ∉[a](a, b, d)

because d does not ‘clash’ with (a, b) but it does ‘clash’ with (a, b, d).

In nominal techniques, when we build equivalence classes of renamed variants like [a](a, b) and [a](a, b, d) above, we ‘avoid name-clash’.

Now, we want substitution to distribute over abstraction in a capture-avoiding way. That is,

we want ([a](a, b))[b↦→(b, d)] = [a](a, b, d).

We cannot obtain what we want by operating pointwise on the elements of [a](a, b), i.e. by letting

Z[a↦→x] = {z[a↦→x] | z ∈Z} always

— not just for finite sets Z. For, if we operated pointwise, we would not know not to put into ([a](a, b))[b↦→(b, d)] the element (d, (d, b))[b↦→(b, d)] = (d, (d, b, d)). Substitution must detect α-equivalence classes and adjust for them by adding or removing elements with ‘name-clash’.

One reason this is a difficult question is that not all sets look like the tame examples we selected above. Elements may be (amongst many other things) unions of abstractions

[a](a, b) ∪[a](a, b, d)

or equivalence classes which represent simultaneous abstraction by more than one atom

{{a, b, c}, {d, b, c}, {e, b, c}, {f, b, c}, . . . {a, d, c}, {b, d, c}, {e, d, c}, {f, d, c}, . . . {a, e, c}, {b, e, c}, {d, e, c}, {f, e, c}, . . .}

— we can think of this as ‘abstract a and b simultaneously in {a, b, c}’ and write it in an informal notation which we do not make formal as

{a, b}{a, b, c}.

If we apply [c↦→(b, d)] to this we want to ‘avoid name-clash’ with b and d, and ‘α-convert b’, and ‘fill in renamed variants mentioning c’, to obtain the element

{{a, c, (b, d)}, {d, c, (b, d)}, {e, c, (b, d)}, {f, c, (b, d)}, . . . {a, e, (b, d)}, {c, e, (b, d)}, {f, e, (b, d)}, {g, e, (b, d)}, . . . {a, e, (b, d)}, {c, e, (b, d)}, {f, e, (b, d)}, {g, e, (b, d)}, . . .}

which we can write as

{a, c}{a, c, (b, d)}.

This is only a scratch on the surface of the complexity that exists in a model of sets but it is enough to illustrate our strategy for defining a substitution action. The problem with the pointwise definition of substitution is correct maintenance of ‘points’ in α-equivalence classes so:

Given a set X, identify X as a union of some generalised notion of α-equivalence classes X = ⋃i Xi. Now carry out substitution on the individual classes, then put the results together again using sets union.

We can put it another way:

Substitution is pointwise — but the points are not elements, they are (generalised) α-equivalence classes of elements.

Our generalisation of α-equivalence classes is planes u‖A (Subsection 3.3). The set above is {a, b, c}‖{c} which is the equivalence class of all renamed variants of {a, b, c} under permutations of atoms fixing c (i.e. ‘α-abstract a and b in {a, b, c}).

If we apply [c↦→(b, d)] to this then we obtain {a, c, (b, d)}‖{b,d}. Note that this is the same set as {a, e, (b, d)}‖{b,d} and {c, e, (b, d)}‖{b,d} — it is part of our model of α-equivalence on FM sets that we can ‘α-rename abstracted atoms’ freely.

Given these ideas, the only obstacle to defining substitution on FM sets is deciding how substitution interacts with planes. This is described formally in Subsection 3.4, with several examples.

We mentioned that we give not one but two substitution actions in this paper. The second substitution action (Section 5), write it z[a↦→x]2, is based on the same ideas but with a twist. Instead of acting on all of z, the second substitution action isolates the parts of z which are responsible for it containing a (in nominal terminology; those elements responsible for a ∈ supp(z) being true; see ‘crucial elements’ in Section 4). The second substitution action acts, in a suitable sense, only on planes involving these elements. Thus the second substitution action z[a↦→x]2 is pointwise but only on points (generalised α-equivalence classes) that ‘contain a’ in a suitable sense given by crucial elements. This gives the second substitution action some different, and arguably better, properties. See Subsection 5.2 for examples and discussion.

2. Fraenkel-Mostowski set theory

2.1. Axioms, permutations, equivariance

The language of FM set theory is first-order logic with two binary predicates = (set equality) and ∈ (set membership) — just like the language of ZF set theory — and one constant symbol A called ‘the set of atoms’.

Definition 2.1

The axioms of FM set theory are given in Figure 1.

We use standard definitional extensions of the language of sets:

x = {z | z ∈x} means ∀y.(∀z.z ∈x ⇔z ∈y) ⇒x = y
y = {z ∈x | φ(z)} means ∀z.z ∈y ⇔ (z ∈x ∧φ(z))
z = {F(y) | y ∈x} means ∀u.u ∈z ⇔∃y.(F(y) = u ∧y ∈x)
z = {x, y} means ∀u.u ∈z ⇔ (u = x ∨u = y)
z = {y | ∃y′.(y ∈y′ ∧y′ ∈x)} means ∀y.y ∈z ⇔∃y′.(y ∈y′ ∧y′ ∈x)
z = {y | y ⊆x} means ∀y.y ∈z ⇔∀y′.(y′ ∈y ⇒y′ ∈x)
∅∈x means ∃z.z ∈x ∧z ∉A ∧∀z′.z′ ∉z
y ∪{z} ∈x means ∃u.u ∈x ∧∀u′.(u′ ∈u ⇔u ∈y ∨u = z)

In addition Pfin is the finite powerset, and support is described below.

(We mention the intuition of the cumulative hierarchy model of these axioms in Remark 2.12.)

Remark 2.2

We use the following notational conventions:

• An atom is a set member of A (the set of atoms).

• The permutative convention: a, b, c, . . . range over distinct atoms unless stated otherwise.

• A, B, C, S, T range over sets of atoms. For example A ⊆A.

• X, Y, Z, U, V range over elements that are not atoms and may be empty. For example X might equal ∅ or {a, ∅}, but X cannot equal a.

• x, y, z, u, v range over arbitrary elements.

(Sets) ∀x.(∃y.y ∈x) ⇒x ∉A (Extensionality) ∀x.x ∉A ⇒x = {z | z ∈x} (Comprehension) ∀x.∃y.y ∉A ∧y = {z ∈x | φ(z)} (y not free in φ) (∈-Induction)(∀x.(∀y ∈x.φ(y)) ⇒φ(x))⇒∀x.φ(x) (Replacement) ∀x.∃z.z ∉A ∧z = {F(y) | y ∈x} (Pairset) ∀x, y.∃z.z = {x, y} (Union) ∀x.∃z.z ∉A ∧z = {y | ∃y′.(y ∈y′ ∧y′ ∈x)} (Powerset) ∀x.∃z.z = {y | y ⊆x} (Infinity) ∃x.∅∈x ∧∀y.y ∈x ⇒y ∪{y} ∈x (AtmInf) A ∉Pfin(A) (Fresh) ∀x.∃S ∈Pfin(A).S supports x
Figure 1: Axioms of FM set theory
Definition 2.3

As is standard, we will write 0 = ∅ and i + 1 = i ∪{i}, and write N = {0, 1, 2, 3, . . .}.

An atom a ∈A is ‘empty’, or formally: ∀x.x ∉a. However atoms are not equal to the empty set ∅.

In ZF set theory two empty elements are equal by the axiom of extensionality. In FM set theory the axiom of extensionality (Extensionality) is weakened so that an empty element is the empty set ∅ — or is an atom.

(AtmInf) insists that there are infinitely many atoms.

Therefore, any element z is either an atom, or it is a set containing nothing but atoms and (possibly) more sets. For further details see elsewhere [15].

Definition 2.4

Write (a b) for the swapping of a and b. This is the mapping from A to itself specified by

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

Note that by our permutative naming convention a, b, and c are distinct.

Write ◦ for functional composition. Let π range over functions from A to A generated by functionally composing finitely many swappings, and call these permutations. A permutation action is defined by ϵ-induction [30]:

πX = {πx | x ∈X}

The permutation action satisfies equivariance. This very useful property is also very easy to prove. Let φ(x1, . . . , xn) range over predicates in the language of FM set theory which mention variables in x1, ..., xn. An n-rary function F(x1, . . . , xn) can be expressed by a predicate φF (x1, . . . , xn, z) such that for each x1,..., xn there is a unique z making φF true. Then equivariance is the following two properties:

Theorem 2.5

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

π(F(x1, . . . , xn)) = F(πx1, . . . , πxn)

always hold.

Proof

The first part is by an easy induction on the syntax of φ. We consider just one case: x ∈y implies πx ∈πy follows directly from the fact that πy = {πy′ | y′ ∈y}. The reverse implication uses π-1.

The second part, for F, follows using the encoding of functions as predicates.End of proof

2.2. Support

Definition 2.6

If A ⊆A write

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

Say that A ⊆A supports x when

∀π ∈fix(A).πx = x.

• We write

supp(x) for⋂{S | S is finite and supports x}

and call this the support of x. supp(x) is well-defined because (Fresh) insists that some finite S supporting x must exist.

• We write a#x when a ∉ supp(x) and read this as a is fresh for x. We may write a#t1, t2 for ‘a#t1 and a#t2’, and so on.

The notion of support goes back to Fraenkel and Mostowski [29, Chapter 4]. The application in computer science came later [23, 15].

Remark 2.7

For example:

• supp(∅) = ∅. π∅= ∅ for all π ∈ fix(∅).

• supp(A) = ∅.

π{a, b, c, . . .} = {π(a), π(b), π(c), . . .} = {a, b, c, d, . . .} for all π ∈fix(∅).

• supp(a) = {a}. π(a) = a for all π ∈ fix({a}).

• supp({a}) = {a}. π({a}) = {a} for all π ∈ fix({a}).

• supp(A \ {a}) = {a}.

π{b, c, d, . . .} = {π(b), π(c), π(d), . . .} = {b, c, d, . . .} for all π ∈fix({a}).

• supp({a, b}) = {a, b}. π{a, b}={a, b} for all π∈fix({a, b}).

• supp(A \ {a, b}) = {a, b}.

π{c, d, e, . . .} = {π(c), π(d), π(e), . . .} = {c, d, e, . . .} for all π ∈fix({a, b}).
• supp({a, {a}, {c}, {d}, . . .}) = {a, b}. π({a,{a},{c},{d}, . . .}) ={π(a),{π(a)},{π(c)},{π(d)}, . . .}) ={a,{a},{c},{d}, . . .}

provided that π ∈ fix({a, b}).

Remark 2.8

Ideas from syntax match ideas from FM sets as follows:

• variable symbols matches atoms and

• free variables matches support.

It is possible to take the complement of a set, but not possible to take the complement of a syntax tree. It is therefore important to realise that sets are more general than syntax, and in particular that a ∉X and a#X are not the same thing. supp(X) measures how ‘conspicuous’ a is in X, either by its set membership or lack of set membership. For example:

a ∈A and a#A a ∉∅ and a#∅ a ∉a and a∈supp(a) a ∈{a} and a∈supp({a}) a ∉A\{a} and a∈supp(A\{a})
Remark 2.9

Not every collection has finite support.

• {a, c, e, g, . . .} (the set of ‘every other atom’) is not finitely supported, and is excluded from the cumulative hierarchy model of Remark 2.12 below. There is no finite S ⊆A such that if π ∈ fix(S) then π{a, c, e, g, . . .} = {a, c, e, g, . . .}.

• A set well-ordering atoms ≤ is not finitely supported, and is excluded from the cumulative hierarchy model of Remark 2.12:

≤= {{a}, {a, b}, {a, b, c}, {a, b, c, d}, . . .}

There is no finite S ⊆A such that if π ∈ fix(S) then π ≤=≤.

• A set ϵ choosing from every unordered pair of atoms, an atom (the ‘greater’ one according to ≤ above), is not finitely supported and is excluded from the cumulative hierarchy model of Remark 2.12:

ϵ = {{{a, b}, b}, {{a, c}, c} {{a, d}, d}, . . . {{b, c}, c}, {{b, d}, d} {{b, e}, e}, . . . . . .}

There is no finite S ⊆A such that if π ∈ fix(S) then πϵ = ϵ.

Theorem 2.10 was the reason Fraenkel-Mostowski set theory was originally created and studied:

Theorem 2.10

The axiom of choice is inconsistent with the axioms of FM.

Proof

Given the examples above it is easy to see that choice functions, and well-orderings on sets, are not in general finitely supported. For more details see [7]End of proof

Remark 2.11

Theorem 2.10 may give the impression that the model of syntax-with-binding from Fraenkel-Mostowski techniques is inconsistent with the axiom of choice, but this is not so.

Set theory is untyped. It does no harm to admit the existence of elements that do not have finite support, so long as we do not try proving results involving freshness about them, i.e. all the non-trivial results which are the topic of this paper. We work in Fraenkel-Mostowski sets because it saves us writing ‘if x, y, z, . . . have finite supporting sets’ at the start of all our results.

Specifically, if we drop (Fresh) from Figure 1, which asserts that every element must have finite support, then we obtain another standard set theory; Zermelo-Fraenkel set theory with atoms. This still satisfies equivariance (Theorem 2.5) because equivariance is a property of any first-order theory with atoms; models of Zermelo-Fraenkel set theory can contain elements representing well-orderings and choice functions (which may not have finite support); and all the results in this paper can easily be proven, subject to a clause ‘provided x, y, z, . . . have a finite supporting set’.

Remark 2.12

(The cumulative hierarchy model) FM is a theory in first-order logic. As is often the case, we have a clear intuition in mind for a standard model; the cumulative hierarchy model is the collection U defined as follows:

U0 = A Ui+1 = Ui ∪{X ⊆Ui | X has a finite supporting set}

Then U = ⋃i Ui. The reader can imagine all our constructions taking place in this model and no harm will come of it.

The cumulative hierarchy of Zermelo-Fraenkel set theory with atoms is obtained by taking all X instead of only X with finite support, at each stage. That is, the cumulative hierarchy of ‘well-behaved’ Fraenkel-Mostowski sets naturally embeds in a larger universe of Zermelo-Fraenkel sets with atoms, containing elements representing choice functions, well-orderings, and so on — but in which not all elements can be assigned substitution actions for atoms, and so on, as we shall now construct.

We now prove Theorem 2.13, Theorem 2.14, and Theorem 2.15. These are three basic results about support, which will be very useful in what follows:

Theorem 2.13

If S and T support x and are finite, then so does S ∩T.

As a corollary, supp(x) is the unique smallest finite set supporting x.

Proof

The corollary follows by elementary calculations and (Fresh).

Suppose κ fixes S ∩T pointwise. We must show κx = x. Write K for {a | κ(a) ≠ a}. Choose an injection ι of T \ S into A \ (S ∪T ∪K) (we can say ‘ι freshens T \ S’). Let π(a) = ι(a) and π(ι(a)) = a for a ∈T \ S, and π(a) = a otherwise. Note that π = π-1. π fixes S pointwise so πx = x. Also π ◦κ ◦π fixes T pointwise so (π ◦κ ◦π)x = x. We apply π to both sides and simplify and conclude that κx = x as required.End of proof

Theorem 2.13 means that the action of π on x depends only on the values of π on the atoms in supp(x).

Theorem 2.14

S supports x if and only if πS supports πx. As a corollary, πsupp(x) = supp(πx).

Proof

From Theorem 2.5.End of proof

Theorem 2.15

supp(F(x1, . . . , xn)) ⊆ supp(x1) ∪· · · ∪ supp(xn).

Proof

Suppose S = supp(x1) ∪. . . ∪ supp(xn). By Theorem 2.5 πF(x1, . . . , xn) = F(πx1, . . . , πxn). If π ∈ fix(S) then π ∈ fix(x1) ∩. . . ∩ fix(xn) and the result follows.End of proof

2.3. Orbits under the permutation action

We introduce a new notion which we will make much use of in what follows:

Definition 2.16

Suppose A ⊆A. Write

u‖A for {πu | π ∈fix(A)}.

(Recall that fix(A) = {π | ∀a ∈A.π(a) = a}.) We call u‖A a set of renamed variants of u under permutations fixing atoms in A.

As discussed in Remark 2.8 the idea from syntax of ‘free variables of’ matches the idea in Fraenkel-Mostowski sets of ‘support’. α-equivalence is how we remove free variables from terms. Taking equivalence classes is a standard way to abstract structure using sets. Thus, u‖A is a natural sets model of the intuition

“simultaneously α-abstract in u for all atoms not in A.”

This is made formal in Theorem 2.18 and Subsection 2.4.

For example:

{a}‖∅= {a, b, c, d, e, f, . . .} {a}‖{a} = {a} {b}‖{a} = {b, c, d, e, f, . . .} {a, b}‖{a,c} = {{a, b}, {a, d}, {a, e}, {a, f}, . . .}
Lemma 2.17

If π ∈ fix(A) then u‖A = (πu)‖A.

Proof

u‖A is the orbit of u under the action of fix(A). fix(A) is a group. The result follows.End of proof

Note that u‖∅= {πu | all π}.

Theorem 2.18

Suppose A is a finite set of atoms. Then:

1. If supp(u) ⊆A then supp(u‖A) = supp(u).

2. supp(u‖A) ⊆A always.

As a corollary,

supp(u) \ A ≠ ∅ implies supp(u‖A) = A.
Proof

1. If supp(u) ⊆A then by the definition of support, if π ∈ fix(A) then πu = u and u‖A = {u}. It is easy to verify that supp({u}) = supp(u).

2. Suppose that π ∈ fix(A). We reason using Theorem 2.5 and Lemma 2.17:

π(u‖A) = (πu)‖πA = (πu)‖A = u‖A.

By Theorem 2.13 the result follows.

We illustrate why the corollary is ‘obvious’ with an example:

a‖{b} = {a, c, d, e, f, . . .} = A \ {b}.

Here supp(a) \ {b} = {a} and supp(A \ {b}) = {b}.

Now for the proof. Suppose that supp(u) \ A ≠ ∅. By part 2 of this result supp(u‖A) ⊆A. We prove the reverse inclusion. We note the following two points:

• Suppose a ∈A. If a ∈ supp(u) ∩A then by Theorem 2.14 a ∈ supp(u′) for all u′ ∈u‖A. If a ∈A \ supp(u) then by Theorem 2.14 a ∉ supp(u′) for all u′ ∈u‖A.

• Suppose a ∉A. Since supp(u) \ A ≠ ∅ by Theorem 2.14 there exist some u′ ∈u‖A such that a ∈ supp(u′), and some u′ ∈u‖A such that a ∉ supp(u′).

Thus, we can recover A from X = u‖A using the function

F(X) = {a | (∀x ∈X.a ∈supp(x)) ∨(∀x ∈X.a ∉supp(x))}.

By Theorem 2.15 it follows that supp(A) ⊆ supp(u‖A). But A is finite; by Lemma 2.22 A = supp(A) and so we have A ⊆ supp(u‖A) as required.2End of proof

2.4. α-abstraction

The model of α-equivalence in FM sets was introduced in [23, 15]. The presentation here is revised.

Definition 2.19 is the standard Kuratowski implementation of ordered pairs in sets [30].

Definition 2.19

Write (x, y) for {{x}, {x, y}}.

Definition 2.20

Define the atoms-abstraction by [c]z = (c, z)‖supp(z)\{c}.

We can read ‘[c]z’ as the binding action of ‘λc.z’ or ‘∀c.z’, and the sets above correspond with α-equivalence classes of FM sets. There is no a priori notion of λ-abstraction or universal quantification in; this is just α-abstraction, on FM sets. So [c]z is the α-equivalence class of (c, z) where c is abstracted, i.e. where we read (c, z) like ‘λc.z’ or ‘∀c.z’. The avoids atoms in supp(z) \ {c}, thus, supp(z) plays the rôle that ‘the free variable symbols of’ plays in syntax (but generalises it to all sets):

[a]a = {(a, a), (b, b), (c, c), (d, d), (e, e), (f, f), . . .} [a]{a, b} = {(a, {a, b}), (c, {c, b}), (d, {d, b}), (e, {e, b}), . . .} [a](A\{a}) = {(a, A\{a}), (b, A\{b}), (c, A\{c}), . . .} [a](A\{a, b}) = {(a, A\{a, b}), (c, A\{c, b}), (d, A\{d, b}), . . .}

Write Uab for {a} ∪{{a}, {c}, {d}, {e}, . . .} for any a, b. Then:

[a]Uab = {(a, Uab), (c, Ucb), (d, Udb)(e, Ueb), . . .} [c]Uab = {(c, Uab), (d, Uab), (e, Uab), . . .}

Definition 2.20 gives a result equal to the original definition of atoms-abstraction in FM set theory [23]:

Lemma 2.21

[c]z = {(n, (n c)z) | n ≠ c ∧n#z} ∪{(c, z)}.

As a corollary, if (x, y) ∈ [c]z then supp(y) = (supp(z) \ {c}) ∪{x}.

Proof

We note that (c, z) ∈ [c]z and also that (n c) ∈ fix(supp(z) \ {c}). By Theorem 2.5 we can calculate that

{(n, (n c)z) | n ≠ c ∧n#z} ∪{(c, z)} ⊆[c]z.

Conversely, by Theorem 2.13 if π ∈ fix(supp(z) \ {c}) then πx = (πc c)x and it follows by an easy calculation that

[c]z ⊆{(n, (n c)z) | n ≠ c ∧n#z} ∪{(c, z)}.

For the corollary, by Theorem 2.14 supp((n c)z) = (n c)supp(z) and the result follows.End of proof

Lemma 2.22

• If ⋃{supp(x) | x ∈X} is finite then

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

In particular if X is finite (so that ⋃{supp(x) | x ∈X} is a finite union of finite sets and so is finite) then supp(X) = ⋃{supp(x) | x ∈X}.

• supp({x}) = supp(x) and if A ⊆A is finite then supp(A) = A.

Proof

supp(X) ⊆⋃{supp(x) | x ∈X} always, by Theorem 2.15. We now prove the reverse inclusion. Suppose that ⋃{supp(x) | x ∈X} is finite. Now suppose a ∈ supp(x) for some x ∈X. Choose some b such that b#X and b#x′ for every x′ ∈X. By Theorem 2.14 supp((b a)x) = (b a)supp(x). Since X has no element y such that b ∈ supp(y), we know that (b a)X ≠ X and by Theorem 2.13 it must be that a ∈ supp(X).

The second part follows easily.End of proof

Lemma 2.23

supp((x, y)) = supp(x) ∪ supp(y).

Proof

From Definition 2.19 and Lemma 2.22.End of proof

Corollary 2.24

supp([c]z) = supp(z) \ {c}.

Proof

By Lemma 2.23 supp((c, z)) = supp(z)∪{c}. By definition [c]z = (c, z)‖supp(z)\{c}. The result follows by Theorem 2.18.End of proof

So for example, we expect (a d)[a]{a, b} = [a]{a, b} since supp({a, b}) = {a, b}, and {a, b}\{a} = {b}, and (a d) ∈ fix({b}). We can verify this by routine calculations:

[a]{a,b} = {(a, {a,b}), (c, {c,b}), (d, {d,b}), (e, {e,b}), . . .} (a d)[a]{a,b} = {(d, {d,b}), (c, {c,b}), (a, {a,b}), (e, {e,b}), . . .}
Lemma 2.25

supp(X) ⊆⋃{supp(x) | x ∈X} need not necessarily hold if X is not finite.

Proof

It suffices to give a counterexample; we give two: supp(A) = ∅ but ⋃{supp(a) | a ∈A} = A. supp(A\{c})={c} but ⋃{supp(a) | a∈A ∧a≠c} = A\{c}.End of proof

3. The substitution action

We recall our notational convention that a, b, c range over distinct atoms, A, B, C, S, T range over sets of atoms, lowercase x, y, z, u, v range over all elements, and uppercase X, Y, Z, U, V range over elements that are not atoms.

3.1. Axioms, pointwise substitution action, syntactic substitution action

Definition 3.1

A substitution action on FM set theory is a function z[a↦→x] expressed in the language of FM set theory (and so satisfying equivariance Theorem 2.5) taking any z, an atom a, and any x, satisfying:

(α) b#z ⇒z[a↦→x] = ((b a)z)[b↦→x] (#↦→) a#z ⇒z[a↦→x] = z (var↦→) a[a↦→x] = x (id↦→) z[a↦→a] = z (abs↦→) c#x ⇒([c]z)[a↦→x] = [c](z[a↦→x])

Here by our convention x, y, z range over elements of the Fraenkel-Mostowski sets universe. a, b, and c range over distinct atoms. An equivariance rule from [22] is omitted here because it is guaranteed by Theorem 2.5.

Remark 3.2

FM set theory supports generalisations of the notions of ‘name’, ‘freshness’, and ‘abstraction’ which exist in syntax [23]. The author commented on the potential to extend this apparatus to a notion of substitution [15].

The axioms from Definition 3.1 came later in work with Mathijssen [22]. They are sound and complete for a model based on capture-avoiding substitution on syntax.

The axioms are only properties we require of the construction — our two substitution actions demonstrate that they specify, but not uniquely, substitution on sets. These axioms do rule out an ‘obvious’ definition, perhaps the first that we would consider:

Definition 3.3

The pointwise substitution action is defined by

a[a↦→x]n = x b[a↦→x]n = b Z[a↦→x]n = {z[a↦→x]n | z ∈Z}.
Lemma 3.4

Pointwise substitution does not satisfy (α), (#↦→), or (abs↦→). Therefore, it is not a substitution action in the sense of Definition 3.1.

Proof

It suffices to produce counterexamples. We do this for (#↦→) and (abs↦→). We expect that A[a↦→1]n = A since a#A. We also expect that ([c]a)[a↦→1]n = [c](a[a↦→1]) since c#1. But:

A[a↦→1]n =(A \ {a}) ∪{1}
([c]a)[a↦→1]n ={(b, a), (c, a), (d, a), (e, a), . . .}[a↦→1]n ={(b, 1), (c, 1), (d, 1), (e, 1), . . .}
[c](a[a↦→1]n) =[c]1 ={(a, 1), (b, 1), (c, 1), (d, 1), (e, 1), . . .}.End of proof

Here is another attempt:

Definition 3.5

The syntactic substitution action is defined by:

a[a↦→x]t = x b[a↦→x]t = b Z[a↦→x]t = Z (a#Z) Z[a↦→a]t = Z Z[a↦→b]t = (b a)Z (b#Z) ([c]z)[a↦→x]t = [c](z[a↦→x]t) (c#x)
Z[a↦→x]t = {z[a↦→x]t | z ∈Z} (Z finite) Z[a↦→x]t = ∅ (otherwise).
Theorem 3.6

[a↦→x]t is well-defined and satisfies the axioms of substitution.

The proof of this theorem is by easy but uninteresting calculations. Since we are in any case not happy with [a↦→x]t we do not include them.

[a↦→x]t reprises a similar definition on abstract syntax trees from the author’s thesis [15, Definition 10.7.13], and a construction in the same spirit (but using diagrams) in presheaf categories [14, Definition of substitution by structural recursion, page 6]. [a↦→x]t is capture-avoiding substitution — on the subclass of (any model of) FM set theory that represents abstract syntax trees. On the rest of the FM sets universe the definition ‘gives up’ and defaults to ∅.

This could be suitable for providing a semantics to a generic substitution function, and might have applications, for example to generic programming [31, 9]. This is for future work.

The syntactic substitution action runs into another kind of trouble because of how it ‘gives up’ on sets that do not represent abstract syntax trees. For example

(A \ {a})[a↦→1]t = ∅.

If we expand definitions this becomes

{b, c, d, e, f, . . .}[a↦→1]t = {}.

Here we write A = {a, b, c, d, e, f, . . .}. Now

([c]a)[a↦→1]t = [c]1.

If we expand definitions this becomes

{(b, a), (c, a), (d, a), (e, a), (f, a), . . .}[a↦→1]t = {(a, 1), (b, 1), (c, 1), (d, 1), (e, 1), (f, 1), . . .}.

Thus (A \ {a})[a↦→1]t and ([c]a)[a↦→1]t return very different answers — yet both are equivalence classes of renamed variants in the sense of Definition 2.16. (In the examples above, the equivalence classes are renamed variants of c and (c, a) respectively.) For another example:

{((b, b), a), ((c, c), a), ((d, d), a), ((e, e), a), ((f, f), a), . . .}[a↦→1]t = ∅.

Compared to [c]a the only difference is to place an ordered pair such as (b, b) in the first position, instead of just b. The effect on the result of a substitution is dramatic.

Clearly, this is an artefact of the definitions and has no deeper mathematical justification. The structures of the two sets

{((b, b), a), ((c, c), a), ((d, d), a), ((e, e), a), ((f, f), a), . . .} [c]a ={(b, a), (c, a), (d, a), (e, a), (f, a), . . .}

are sufficiently close that we could implement atoms-abstraction just as well using one as using the other. We expect them to behave in roughly analogous ways with respect to substitution, and they do not.

This issue is important:

• Equivalence classes of renamed variants are the mechanism by which FM sets model binding (Definition 2.20).

• They are also part of the mechanism by which a#x differs from ‘a is in the transitive closure of x’. For example

a ∈A = a‖∅ yet a#A

and

a ∉(A \ {a}) = b‖{a} but a ∈supp(A \ {a}).

(See Theorem 2.18 for the necessary results about supp(u‖A).)

Therefore, correct interaction of substitution with equivalence classes of renamed variables is directly relevant to motivation of this paper, which is to define a capture-avoiding substitution action on models of FM sets.

3.2. A short quiz

As we shall see, there is design freedom in building a substitution action. We motivate this with a short quiz. Some technical definitions will be useful:

Definition 3.7

If A, S ⊆A are finite then define

A(a↦→S) ={ (A \ {a}) ∪S if a ∈A A if a ∉A.
Lemma 3.8

Any substitution action satisfies that

supp(z[a↦→x]) ⊆supp(z)(a↦→supp(x)).
Proof

By Theorem 2.15

supp(z[a↦→x]) ⊆supp(z) ∪{a} ∪supp(x).

Choose some fresh b (so b#z, a, x). By the axiom (α) z[a↦→x] = ((b a)z)[b↦→x]. By Theorem 2.15

supp(((b a)z)[b↦→x]) ⊆supp((b a)z) ∪{b} ∪supp(x).

The result follows using Theorem 2.14.End of proof

Remark 3.9

[Quiz] Recall from Definition 2.3 that we write 0 = ∅ and i+1 = i∪{i}, and write N = {0, 1, 2, 3, . . .}. Note that supp(i) = ∅ for all i ∈N.

• Q. What is ((A \ {a}) ∪N)[a↦→1]?

A. A ∪N.

This makes the minimum change consistent with Lemma 3.8.3

• Q. What is ((A \ {a}) ∪N)[a↦→1]?

A. A ∪(N \ {1}).

This makes the minimum change consistent with Lemma 3.8 — and we replace the ‘missing a’ by a ‘missing 1’. Since we are defining substitution on sets, we should think how substitution behaves on syntax denoting sets: substitution commutes with logical negation in the syntax of logic, and this is modelled by replacing ‘missing elements’ by other ‘missing elements’. More on this in Subsection 5.2.

In this paper we will not attempt to argue whether one substitution action is better than another. We lay down two substitution actions representing two ‘reasonable extremes’ in the design space.

• The first one, presented immediately, belongs to the first class of substitutions in Remark 3.9 above.

• The second one, presented later beginning with Section 5, belongs to the second class of substitutions.

It is for future research to study the class of all possible substitution actions. In this paper we show some of what is possible and give methods by which these possibilities can be explored.

The reader might be tempted to expect some mathematical ‘lattice of substitutions’ similar perhaps to the ‘lattice of λ-theories’ which Salibra and others have studied [33]. This is just one of the interesting questions invited by the existence of a sets model of substitution. A moment of reflection shows that the answer is not obvious. Substitution is a function, not a relation — a λ-theory is a relation on λ-term syntax, so λ-theories are naturally ordered by inclusion.

3.3. The planes of a set

Definition 3.10

Suppose that A ⊆A is finite. Call (u, A) a plane in Z when A is a minimal subset of supp(Z) such that u‖A ⊆Z.

Write plane(Z) for the collection of planes in Z.

It is easy to see that if (u, A) ∈ plane(Z) then u ∈Z.

Unpacking Definition 3.10, (u, A) is a plane in Z when A ⊆ supp(Z) and u‖A ⊆ Z and for all (u′, A′), if A′ ⊆ supp(Z) then

u‖A ⊆u′‖A′ ⊆Z implies u′‖A′ = u‖A.

For example:

1. (a, {a}) ∈ plane({a}) and a‖{a} = {a} ⊆{a}.

2. (a, {}) ∉ plane({a}) because a‖{} = A ⊈{a}.

3. (a, {a}) ∉ plane(A) because {a} ⊈ supp(A) = ∅.

4. (a, {a, b})∉plane({a}) because a‖{a,b} = {a} = a‖{a} and {a}⊈{a, b}.

5. (c, {a}) ∈ plane(A\{a}) and c‖{a} = A\{a} ⊆A\{a}.

6. (a, {}) ∈ plane(A) and a‖{} = A ⊆A.

7. ((c, a), {a}) ∈ plane([c]a) and (c, a)‖{a} = {(x, a) | x ≠ a} = [c]a ⊆ [c]a.

8. plane({a} ∪{{a}, {c}, {d}, . . .}) ={(a, {a})} ∪

{({x}, {b}) | x∈A, x≠b}. a‖{a} = {a} ⊆{a} ∪{{a}, {c}, {d}, . . .}. {x}‖{b} = {{a}, {c}, {d}, . . .} ⊆{a} ∪{{a}, {c}, {d}, . . .}.
Definition 3.11

If S ⊆A is finite then define

planeS(Z) = {(u, A) ∈plane(Z) | supp(u) ∩S ⊆supp(u) ∩A}.

We should think of planeS(Z) as the planes (u, A) in Z such that the support of u ‘avoids clashes’ with atoms in S, where this is possible. For example

(a, {}) ∈plane{}(A) but (a, {}) ∉plane{a}(A) and (c, {a}) ∈plane{b}(A\{a}) but (b, {a}) ∉plane{b}(A\{a}).

It will later be useful to know that the planes of Z ‘cover’ Z in a suitable sense:

Theorem 3.12

If S ⊆A is finite then

⋃{u‖A | (u, A) ∈planeS(Z)} = Z.

As a corollary taking S = ∅, ⋃{u‖A | (u, A) ∈ plane(Z)} = Z.

Proof

We prove two set inclusions: The left-to-right inclusion is by construction. For the right-to-left inclusion, choose any u ∈Z. Let B = {b1, . . . , bk} be equal to supp(u) \ A and let B′ = {b′ 1, . . . , b′ k} be some set of entirely fresh atoms (so disjoint from supp(u), A, S, and supp(Z)). Let π = (b1 b′ 1) ◦. . . ◦ (bk b′ k).

By Theorem 2.14 we can calculate that

supp(πu) ∩S = (supp(u) ∩A) ∩S and supp(πu) ∩A = supp(u) ∩A.

Therefore supp(πu) ∩S ⊆ supp(πu) ∩A. Also (πu)‖A = u‖A by Lemma 2.17, so (πu, A) ∈ planeS(Z). Finally we note that u ∈ (πu)‖A.End of proof

Planes do not just cover a set (Theorem 3.12), they cover its support, all of its support, and nothing but its support. Compare Lemma 2.25 with Theorem 3.13:

Theorem 3.13

If S ⊆A is finite then

supp(Z) =⋃{A | (u, A) ∈planeS(Z)}.
Proof

By definition if (u, A) ∈ planeS(Z) then A ⊆ supp(Z). It therefore suffices to prove that if for all (u, A) ∈ planeS(Z) it is the case that b ∉A, then b#Z.

Suppose b ∉A for every (u, A) ∈ planeS(Z). Choose any fresh b′#Z, so that b′ ∉A for every (u, A) ∈ planeS(Z). We reason as follows:

(b′ b)Z = (b′ b) ⋃{(u‖A) | (u, A) ∈planeS(Z)} Theorem 3.12 =⋃{(b′ b)(u‖A) | (u, A) ∈planeS(Z)} Definition 2.4 =⋃{u‖A | (u, A) ∈plane(Z)} Theorems 2.13 and 2.18 = Z Theorem 3.12

Now b ∉ supp((b′ b)Z) by Theorem 2.14 and the fact that b′#Z. The result follows.End of proof

3.4. Construction of the first substitution action

We can now define the substitution action. We use Theorem 3.12 to view an FM set Z as a union of planes; the ‘capture-avoiding’ aspect of substitution is easy to manage on a ‘plane-by-plane basis’. Recall the definition of A(a↦→S) from Definition 3.7.

Definition 3.14

Define the substitution action z[a↦→x] and a ‘helper’ function δ(z, a, x) as follows:

• a[a↦→x] = x.

• b[a↦→x] = b.

• If Z ∉A then

Z[a↦→x] =⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(Z)} δ(u, a, x) = (supp(u)(a↦→supp(x))) \ supp(u[a↦→x]).

We consider some examples.

1. {a}[a↦→x]. There is one plane, (a, {a}).

δ(a, a, x) = {a}(a↦→supp(x)) \ supp(x) = ∅. {a}(a↦→supp(x)) \ δ(a, a, x) = supp(x) \ ∅= supp(x) {a}[a↦→x] = a[a↦→x]‖supp(x) = x‖supp(x) = x.

2. (A \ {a})[a↦→x]. One plane is (b, {a}) where b#x (the others give the same result).

δ(b, a, x) = {b}(a↦→supp(x)) \ {b} = ∅ {a}(a↦→supp(x)) \ ∅= supp(x) (A \ {a})[a↦→x] = b‖supp(x) = A \ supp(x)

3. A[a↦→x]. One relevant plane is (b, ∅) where b#x (the others give the same result).

δ(b, a, x) = ∅ ∅(a↦→supp(x)) \ ∅= ∅ A[a↦→x] = b‖∅= A

4. ([c]a)[a↦→x] = {(b, a), (c, a), (d, a), . . .}[a↦→x].

One plane is ((c, a), {a}) where c#x.4 We omit calculations showing that (c, a)[a↦→x] = (c, x); for a general result see Theorem 3.26 after these examples.

δ((c, a), a, x) = {c, a}(a↦→supp(x)) \ supp((c, x)) = (supp(x) ∪{c}) \ (supp(x) ∪{c}) = ∅ {a}(a↦→supp(x)) \ ∅= supp(x) ([c]a)[a↦→x] = (c, x)‖supp(x) = [c]x

The other planes give the same result.

5. Ub[a↦→{b}] where, for a given b, we write Ub = {a} ∪{{a}, {c}, {d}, . . .}. Two planes are a‖{a} (a plane for {a}) and {a}‖{b} (a plane for {{a}, {c}, {d}, . . .}). By calculations similar to the examples above, we calculate that

a[a↦→{b}] = {b} and {{a}, {c}, {d}, . . .}[a↦→{b}] = {{a}, {c}, {d}, . . .}

and that Ub[a↦→{b}] = U where we write

U = {{a}, {b}, {c}, {d}, . . .}.

The other planes give the same results.

6. ([c]Ub)[a↦→{b}] = {(c, Ub), (d, Ub), . . .}[a↦→{b}].

One plane is ((c, Ub), {a, b}) (the other planes give the same result). Note that supp(U) = ∅ and supp((c, U)) = {c}, so that

δ((c, Ub), a, {b}) = {a, b, c}(a↦→{b}) \ {c} = {b} {a, b}(a↦→{b}) \ {b} = ∅ ([c]Ub)[a↦→{b}] = (c, U)‖∅= [c]U.

In all other examples δ is equal to ∅. Here, we see how δ is not equal to ∅. This corrects for the fact that supp(Ub[a↦→{b}]) ≠ supp(Ub)(a↦→{b}).

Remark 3.15

Suppose that A, S ⊆A are finite. Note that A(a↦→S) and A[a↦→S] do not coincide. For example, {a}(a↦→{a}) = {a} whereas {a}[a↦→{a}] = {{a}}.

Now we show how this construction satisfies the axioms (α), (#↦→), (var↦→), (id↦→), and (abs↦→), and we investigate for what F it satisfies (F↦→).

Theorem 3.16 ((id↦→)).

z[a↦→a] = z.

Proof

We work by ϵ-induction.

The base cases of z ∈A are easy:

• a[a↦→a] = a.

• b[a↦→a] = b.

Now suppose Z ∉A (we adhere to our notational convention and write capital ‘Z’). Suppose the inductive hypothesis of all u ∈Z. By definition

Z[a↦→a] =⋃{(u[a↦→a])‖A(a↦→{a})\δ(u,a,a) | (u, A) ∈plane{a}(Z)}

Suppose (u, A) ∈ plane{a}(Z), so by definition

supp(u) ∩{a} ⊆supp(u) ∩A.

By inductive hypothesis u[a↦→a] = u, so that supp(u[a↦→a]) = supp(u). Then we can simplify:

A(a↦→{a}) \ (supp(u)(a↦→{a}) \ supp(u[a↦→a])) = A \ (supp(u) \ supp(u)) = A.

So we have this:

Z[a↦→a] =⋃{u‖A | (u, A) ∈plane{a}(Z)}

The result follows by Theorem 3.12.End of proof

For Theorem 3.21 we need Lemma 3.19, a technical lemma giving a form of ‘capture-avoidance’ result. The proof is detailed, but not very hard.

Definition 3.17

If X, Y ∉A then define the symmetric difference (the XOR or exclusive or) of X and Y by:

X ∆Y = {z | (z ∈X ∧z ∉Y ) ∨(z ∉X ∧z ∈Y )}

In words, X ∆Y means ‘the set of elements in precisely one of X and Y ’.

Lemma 3.18

Fix any u, a finite set of atoms A, and any x. Suppose that π is a permutation, write

C = {x ∈A | π(x) ≠ x}.

Suppose that C ∩ (supp(x) ∪A ∪{a}) = ∅ (so C is fresh for everything except for u). Then

u[a↦→x]‖A(a↦→supp(x))\δ(u,a,x) = (πu)[a↦→x]‖A(a↦→supp(x))\δ(πu,a,x).
Proof

By Theorem 2.13 πx = x. By Theorem 2.5 δ(πu, a, x) = πδ(u, a, x) and so

δ(u, a, x) ∆δ(πu, a, x) ⊆C.

We assumed that C ∩(A∪supp(x)) = ∅ and by elementary set calculations we deduce that

A(a↦→supp(x)) \ δ(πu, a, x) = A(a↦→supp(x)) \ δ(u, a, x).

Also (πu)[a↦→x] = π(u[a↦→x]) by Theorem 2.5. Therefore

(πu)[a↦→x]‖A(a↦→supp(x))\δ(πu,a,x) = (π(u[a↦→x]))‖A(a↦→supp(x))\δ(u,a,x). Theorem 2.18= (u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x)

as required.End of proof

Lemma 3.19

Fix Z ∉A, a ∈A, and x. Suppose that B = {b1, . . . , bn} is a finite set of fresh atoms (so bi#x, Z for 1 ≤i ≤n). Then

Z[a↦→x] =⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}∪B(Z)}.

(Notice the B on the far right subscript.)

Proof

By definition

Z[a↦→x] =⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(Z)}.

Choose any

(u, A) ∈planesupp(x)∪{a}(Z).

Unpacking definitions this means

(u, A) ∈plane(Z) and supp(u) ∩(supp(x) ∪{a}) ⊆supp(u) ∩A.

Now choose some fresh b′ 1, ..., b′ n (so b′ i#u, A, B, x, Z for 1 ≤i ≤n) and write B′ = {b′ 1, . . . , b′ n}. Write

π = (b1 b′ 1) ◦. . . ◦(bn b′ n).

We show that

1. (πu, A) ∈ plane(Z),

2. supp(πu) ∩ (supp(x) ∪{a} ∪B) ⊆ supp(πu) ∩A — so that

(πu, A) ∈planesupp(x)∪{a}∪B(Z)

— and

3. (πu)[a↦→x]‖A(a↦→supp(x))\δ(πu,a,x) = u[a↦→x]‖A(a↦→supp(x))\δ(u,a,x).

This will suffice to prove the result.

1. By Theorem 2.5 (πu, πA) ∈ plane(πZ). Now πZ = Z by Theorem 2.13. Also by construction A ⊆ supp(Z) and B ∩ supp(Z) = ∅= B′ ∩ supp(Z), so

B ∩A = ∅, B′ ∩A = ∅, and therefore πA = A.

We conclude that (πu, A) ∈ plane(Z) as required.

2. B ∩supp(x) = ∅= B′ ∩supp(x) so πx = x by Theorem 2.13. By Theorem 2.5

supp(πu) ∩(supp(πx) ∪{a}) ⊆supp(πu) ∩πA

and we simplify this to

supp(πu) ∩(supp(x) ∪{a}) ⊆supp(πu) ∩A.

But by Theorem 2.14 we know that supp(πu) ∩B = ∅ so by further elementary set calculations we conclude that

supp(πu) ∩(supp(x) ∪{a} ∪B) ⊆supp(πu) ∩A

as required.

3. We use Lemma 3.18. We need only check that

(B ∪B′) ∩(supp(x) ∪A ∪{a}) = ∅

and this is by construction.End of proof

We use the following technical lemma in Theorem 3.21:

Lemma 3.20

Fix some Z, a, and x. Suppose that

for all b, if b#Z, x then Z[a↦→x] ⊆((b a)Z)[b↦→x].

Then also

for all b, if b#Z then Z[a↦→x] ⊆((b a)Z)[b↦→x].
Proof

Choose some fresh c (so c#Z, a, b, c). By assumption

Z[a↦→x] = ((c a)Z)[c↦→x] ((b a)Z)[b↦→x] = ((c b)(b a)Z)[c↦→x].

The result follows by Theorem 2.13.End of proof

Theorem 3.21 ((α)).

Suppose Z ∉A. If b#Z then Z[a↦→x] ⊆ ((b a)Z)[b↦→x].

As a corollary, for any z if b#z then z[a↦→x] = ((b a)z)[b↦→x].

Proof

We first prove the corollary. Suppose that z ∈A. Then there are three cases:

• a[a↦→x] = x and ((b a)a)[b↦→x] = x and x = x.

• b#b is false, so there is nothing to prove for the case of b[a↦→x].

• c[a↦→x] = c and ((b a)c)[b↦→x] = c and c = c.

Now suppose that Z ∉A (we adhere to our convention and write capital ‘Z’). Assume that b#Z implies Z[a↦→x] ⊆ ((b a)Z)[b↦→x] for all b, Z, a, x.

Now suppose b#Z. Then Z[a↦→x] ⊆ ((b a)Z)[b↦→x]. Also by Theorem 2.14 a#(b a)Z and it follows that ((b a)Z)[b↦→x] ⊆ ((b a)(b a)Z)[a↦→x]. Now (b a)(b a)Z = Z, and the result follows.

For the first part, we work by ϵ-induction. Suppose Z ∉A and suppose b#Z. By Lemma 3.20 we can also assume b#x. Suppose the inductive hypothesis of every u ∈Z. Using the definition of substitution and using Lemma 3.19 for the first equality (to add a {b} to the subscript on plane; we cannot add {a} to the subscript on plane in the second equality because we do not know a#x)

Z[a↦→x] =⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a,b}(Z)} ((b a)Z)[b↦→x] =⋃{(u′[b↦→x])‖A′(b↦→supp(x))\δ(u′,b,x) | (u′, A′) ∈planesupp(x)∪{b}((b a)Z)}.

Suppose (u, A) ∈ planesupp(x)∪{a,b}(Z). To prove our set inclusion we just need to exhibit some (u′, A′) ∈ planesupp(x)∪{b}((b a)Z) such that

u[a↦→x]‖A(a↦→supp(x))\δ(u,a,x) = u′[b↦→x]‖A′(b↦→supp(x))\δ(u′,b,x).

We choose u′ = (b a)u and A′ = (b a)A. Then (u′, A′) ∈ plane((b a)Z) by Theorem 2.5. Also by definition of planesupp(x)∪{a,b}(Z) we know that

supp(u) ∩(supp(x) ∪{a, b}) ⊆supp(u) ∩A.

Now b ∉A by construction and b ∈ supp(x) ∪{a, b}. Therefore b#u. It is now not hard to use Theorem 2.14 and some elementary set calculations to calculate that

supp(u′) ∩(supp(x) ∪{b}) ⊆supp(u′) ∩A′.

So (u′, A′) ∈ planesupp(x)∪{b}(Z). Since b#u by the inductive hypothesis u′[b↦→x] = u[a↦→x].

It remains to show

A(a↦→supp(x)) \ δ(u, a, x) = ((b a)A)(b↦→supp(x)) \ δ((b a)u, b, x).

Recall that b ∉A. Then A(a↦→supp(x)) = ((b a)A)(b↦→supp(x)) is easily verified. Also

δ((b a)u, b, x) = supp((b a)u)(b↦→supp(x)) \ supp(((b a)u)[b↦→x]).

Now supp((b a)u)(b↦→supp(x)) = supp(u)(a↦→supp(x)) is easily verified, and it follows by the inductive hypothesis that ((b a)u)[b↦→x], and we are done.End of proof

Theorem 3.22 ((#↦→)).

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

Proof

We work by ϵ-induction. We start with the base cases:

• a#a is false so there is nothing to prove for a[a↦→x].

• b[a↦→x] = b.

Now suppose Z ∉A (we adhere to our notational convention and write capital ‘Z’) and a#Z and suppose the inductive hypothesis of all u ∈Z. By definition

Z[a↦→x] =⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(Z)}.

Consider any (u, A) ∈ planesupp(x)∪{a}(Z). By assumption

supp(u) ∩(supp(x) ∪{a}) ⊆supp(u) ∩A.

By construction a ∉A, so a#u and by inductive hypothesis u[a↦→x] = u. Now A(a↦→supp(x)) = A, and

δ(u, a, x) = supp(u)(a↦→supp(x)) \ supp(u[a↦→x]) = supp(u) \ supp(u) = ∅.

So

Z[a↦→x] =⋃{u‖A | (u, A) ∈planesupp(x)∪{a}(Z)}.

The result follows by Theorem 3.12.End of proof

Recall the notion of atoms-abstraction [c]z from Definition 2.20.

Lemma 3.23

plane([c]z) ={((c′, (c′ c)z), supp(z) \ {c}) | c′#z} ∪

{((c, z), supp(z) \ {c})}
Proof

By construction (c, supp(z) \ {c}) ∈ plane([c]z). Also

(c′, (c′ c)z)‖supp(z)\{c} = (c, z)‖supp(z)\{c} = [c]z

by Lemma 2.17. Therefore ((c′, (c′ c)z), supp(z) \ {c}) ∈ plane([c]z) for each c′#z.

Now take any (c′, z′) ∈ [c]z (by our permutative convention, c′ ≠ c). By construction (c′, z′) = (c′, (c′ c)z) for some c′#z. The result follows.End of proof

Theorem 3.24 ((abs↦→)).

If c#x then ([c]z)[a↦→x] = [c](z[a↦→x]).

Proof

If a#z then by Theorem 2.15 also a#[c]z and

([c]z)[a↦→x] = [c]z and [c](z[a↦→x]) = [c]z

follow by Theorem 3.22. So suppose a ∈ supp(z). By Lemma 3.23

plane([c]z) = {((c′, (c′ c)z), supp(z) \ {c}) | c′#z} ∪{((c, z), supp(z) \ {c})}.

Using Lemma 3.18 we can calculate that if c′#x then

(c, z[a↦→x])‖A(a↦→supp(x))\δ((c,z),a,x) = (c′, ((c′ c)z)[a↦→x])‖A(a↦→supp(x))\δ((c′,(c′ c)z),a,x).

We can also calculate using Theorems 2.13 and 2.5 that if c′#z[a↦→x] then

supp(z[a↦→x]) \ {c} = (c′ c)(supp(z[a↦→x]) \ {c}) = supp((c′ c)(z[a↦→x])) \ {c′}.

By Lemma 2.17 we also have

(c, z[a↦→x])‖supp(z[a↦→x])\{c} = (c′, ((c′ c)z)[a↦→x])‖supp((c′ c)(z[a↦→x]))\{c′}.

By Theorems 2.5 and 2.13 (c′ c)(z[a↦→x]) = ((c′ c)z)[a↦→x]. The definitions now simplify to this:

[c]z = (c, z)‖supp(z)\{c} ([c]z)[a↦→x] = (c, z[a↦→x])‖(supp(z)\{c})(a↦→supp(x))\δ((c,z),a,x) [c](z[a↦→x]) = (c, z[a↦→x])‖supp(z[a↦→x])\{c}

So it suffices to verify that

(supp(z) \ {c})(a↦→supp(x)) \ δ((c, z), a, x) = supp(z[a↦→x]) \ {c}.

Now δ((c, z), a, x) = (supp(z) ∪{c})(a↦→supp(x)) \ (supp(z[a↦→x]) ∪{c}) (we use Lemma 2.23 to calculate the support of a pairset) and the result follows by set calculations.End of proof

Theorem 3.25

Definition 3.14 is equivariant and satisfies (α), (#↦→), (var↦→), (id↦→), and (abs↦→) from Subsection 3.1.

Proof

Equivariance is automatic by Theorem 2.5. (var↦→) is direct from the definition. Each of (α), (#↦→), (id↦→), and (abs↦→) is by one of the theorems proved above.End of proof

3.5. Substitutions on syntax, substitutions commuting

We prove that on sets representing syntax substitution coincides with capture-avoiding substitution as we might inductively define it. This is Theorem 3.29 and Corollary 3.31.

Theorem 3.26

If Z ∉A and Z is a finite set then Z[a↦→x] = {z[a↦→x] | z ∈Z}.

Proof

By definition,

Z[a↦→x] =⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(Z)}

Suppose (u, A) ∈ planesupp(x)∪{a}(Z). Since u‖A ⊆Z and Z is finite, u‖A is finite. It follows by Lemma 2.22 that supp(u) ⊆A and u‖A = {u}.

Now recall that by Lemma 3.8 supp(u[a↦→x]) ⊆ supp(u)(a↦→supp(x)), and by definition

δ(u, a, x) = (supp(u)(a↦→supp(x))) \ supp(u[a↦→x]).

It follows by set calculations that

supp(u[a↦→x]) ⊆A(a↦→supp(x)) \ δ(u, a, x)

and the result follows.End of proof

Corollary 3.27

The functions (x, y) = {{x}, {x, y}}, inl(x) = (x, ∅), and inr(x) = (x, {∅}), all commute with the substitution action.

Let I be any set of elements with empty support, so if i ∈I then supp(i) = ∅ (an example is N from Definition 2.3, a non-example is the set of atoms A). Let zi be an I-indexed collection of elements and write (zi)i∈I = {(i, zi) | i ∈I}. Then

(zi)i∈I[a↦→x] = (zi[a↦→x])i∈I.
Proof

The results for pairing, inl, and inr follow from Theorem 3.26.

The second part follows noting that the planes of (zi)i∈I are precisely (zi, supp(zi)) for i ∈I, since for all i, j ∈I if πi = j then i = j.End of proof

Definition 3.28

Let Λ be the datatype of abstract syntax defined inductively by

a ∈A a ∈Λ x, y ∈Λ (x, y) ∈Λ a ∈A x ∈Λ [a]x ∈Λ

It is not hard to show that Λ is isomorphic to λ-terms up to α-equivalence [23]; this is the FM standard construction of abstract-syntax-with-binding, slightly modified (see Remark 3.30 below). Atoms have zero elements, pairs have two, and abstractions have infinitely many, so no atom is a pair or an abstraction, and no pair is an abstraction.

Theorem 3.29

If z, x ∈ Λ then z[a↦→x] ∈ Λ and z[a↦→x] is equal to what we would normally call ‘capture-avoiding substitution of x for a in z’.

Proof

We work by induction on Λ.

• a[a↦→x] = x and b[a↦→x] = b.

• (z1, z2)[a↦→x] = (z1[a↦→x], z2[a↦→x]) by Corollary 3.27.

• ([c]z)[a↦→x] = [c](z[a↦→x]) providing c#x by Theorem 3.24. It is not hard to use Lemma 2.23 and Corollary 2.24 to prove that c#x corresponds precisely to ‘c is not free in x’ when x ∈ Λ.End of proof

Remark 3.30

Theorem 3.29 is generic and works for any datatype of syntax. We must interpret atoms as themselves and not ‘wrapped up’ in the following sense: our construction is an isomorphic version of the datatype from [23] given by:

a ∈A inl(inl(a)) ∈Λ x, y ∈Λ inl(inr((x, y))) ∈Λ a ∈A x ∈Λ inr([a]x) ∈Λ

This is not suitable for Theorem 3.29 because atoms are wrapped up in inl(inl(a)) and inl(inl(a))[a↦→x] = inl(inl(x)) ≠ x. No substitution action can anticipate our particular implementation of the tree-structure of datatypes; since atoms are a distinct class of elements in a model of FM set theory it is valid to insert them ‘unwrapped’ into the inductive type as we have done.

At first blush this appears to rule out datatypes with two or more different kinds of name (type variables, term variables, channel names, locations, and so on), since the datatypes concerned ‘contain more than one copy of A’. A good solution is to hypothesise many sets of atoms — for example a set of disjoint countably infinite sets of atoms, and to add to axiom (Fresh) a quantification over all the sets of atoms (that is, to insist on finite support with respect to each set). This makes no difference to the results in this paper aside from slightly complicating their presentation; our constructions require a countably infinite set of atoms; it makes no difference whether other sets of atoms are also present in the sets universe.

We can prove inductively that the usual commutativity property of substitution holds. Again, the proof is generic and would work as well for any FM-style datatype of abstract syntax with binding:

Corollary 3.31

If a#y and x, y, z ∈ Λ then z[a↦→x][b↦→y] = z[b↦→y][a↦→x[b↦→y]].

Proof

By induction on z.End of proof

Theorem 3.29 and Corollary 3.31 seem empirically to be quite robust results. Analogous results hold also for other structures including coinductive datatypes such as the datatype of infinite lists L illustrated below, and also for ‘name-generating’ coinductive datatypes in the style of [16] such as Lng illustrated below:5

x ∈X l ∈L x :: l ∈L x ∈X l ∈Lng x :: [a]l ∈Lng

(We can also specify this as L = X × L and Lng = X × [A]Lng.)

Substitution commutes with the operations from which these sets are routinely built — atoms, tuples (of any size; see the second part of Corollary 3.27), and taking equivalence classes of renamed variants.

Remark 3.32

For less structured sets, substitutions need not commute:

{a, {a}, {c}, {d}, . . .}[a↦→{b}][b↦→{c}] = {{a}, {b}, {c}, {d}, . . .}[b↦→{c}] = {{a}, {b}, {c}, {d}, . . .} {a, {a}, {c}, {d}, . . .}[b↦→{c}][a↦→{{c}}] = {a, {a}, {b}, {d}, . . .}[a↦→{{c}}] = {{a}, {b}, {{c}}, {d}, . . .}

(The planes of interest here are a‖{a}, {a}‖{b}, and {a}‖{c}.)

Intuitively, {a, {a}, {c}, {d}, . . .} can be read as the predicate ‘is the variable a, or is {x} where x is a variable other than b’. Standard logics such as first-order logics cannot express predicates that reflect on their own syntax; intuitively, non-commutativity of substitution holds on sets that ‘reflect on atoms’ so that the results depend on the order in which those atoms are substituted. We can also approach this proof-theoretically [18].

An analogous phenomenon appears in work based on categories, treating names and behaviour in name-passing calculi that require a name-for-name substitution [13]. To model the syntax of the name-passing calculus and to model reasoning on it, a category in which inequality between names can be determined is required; to model behaviour, a category in which names can be substituted for other names is required. These two requirements seem incompatible since deciding inequality between names does not commute with name-for-name substitution. In [13] a nice solution is discussed which goes back to [28]: two categories, related by adjoint functors, are used for this purpose; SetI for a category in which inequality between names can be determined, and SetF for a category in which names can be substituted for other names; see [13, Equation 28].6 Since set theory is untyped, the sets for which substitution commutes, and those for which it does not, all populate the same universe.

4. New properties of FM: a-orbits and crucial elements

To define our next substitution action we have to develop the theory of crucial elements. Given a set X we will define a set CaX, the a-crucial elements of X, which measures ‘how far away X is from satisfying a#X’.

For example

• Ca{a} will be equal to {a} and {a} is ‘one a away from satisfying a#{a}’ (because a ∈{a}).

• Ca(A\{a}) will be equal to {a} and A\{a} is also ‘one a away from satisfying a#A \ {a}’ (because a ∉A \ {a}).

• CaA will be equal to ∅ and A already satisfies a#A (even though a ∈A).

Remark 4.1

Recall the definition of symmetric difference from Definition 3.17:

X ∆Y = {z | (z ∈X ∧z ∉Y ) ∨(z ∉X ∧z ∈Y )}

We shall show that a#(X ∆CaX) always (Corollary 4.15). So if CaX intuitively measures ‘how far away X is from satisfying a#X’, then ∆ is dimension along which to travel this ‘distance’.

With reference to the examples above, {a} ∆ {a} = ∅, and (A \ {a}) ∆ {a} = A, and A ∆∅= A, and in all cases a is fresh for the result.

An interesting analogy can be drawn between ∆ and swapping (a b): Swapping is very much like atoms-renaming [a↦→b]. It is used in FM theory to do many of the things that are traditionally done using atoms-renaming [23]. An advantage of swapping is that it is invertible; FM techniques owe much of their convenience to this property.

∆ is a bit like like sets union ⋃ and a bit like sets subtraction \, and it can be used to do many of the same things. It is also an invertible operation in the sense that X ∆Y ∆Y = X. This invertibility will prove useful at important points in the proofs below, for example in Lemma 4.21.

We develop the theory of crucial elements in Subsection 4.2. First, we must discuss a-orbits:

4.1. a-orbits

If a ∈A and any u, write

|u|a for the set u‖supp(u)\{a}.

Call |u|a the a-orbit of u.

For example:

|a|a = A |b|a = {b}
|{a, b}|a = {{a, b}, {c, b}, {d, b}, . . .} |{a, b}|b = {{a, b}, {a, c}, {a, d}, . . .}.

To prove Theorem 4.5 below we need some easy technical lemmas:

Lemma 4.2

1. If a#u then |u|a = {u}.

2. If ¬a#u then |u|a is an infinite set.

Proof

1. Suppose a#u. Then |u|a = u‖supp(u) and the result follows by the definition of ‖ and by Theorem 2.13.

2. Suppose ¬a#u. By Theorem 2.14 for c, c′#u it is the case that supp((c a)u) ≠ supp((c′ a)u), so that (c a)u ≠ (c′ a)u. The result follows.End of proof

Lemma 4.3

If ¬a#u and b#u then |u|a = |(b a)u|b. As a corollary, a#(|u|a).

Proof

The first part is by Theorem 2.5 (a proof by calculations is also easy). For the second part, by Theorem 2.14 we can calculate that a#(b a)u. Then the result follows by Theorem 2.15.End of proof

Lemma 4.4

If S is a finite set of atoms such that ¬a#S and b#S then (b a)S = S[a↦→b].

Proof

The permutation action is pointwise, so (b a)S = {(b a)x | x ∈S}. The result follows by Lemma 2.22 and easy calculations.End of proof

The main technical result on a-orbits is this:

Theorem 4.5

Suppose ¬(a#u) and ¬(a#u′). Then precisely one of the following three possibilities holds:

1. |u|a ∩|u′|a is empty.

2. |u|a ∩|u′|a is a singleton. In this case all of the following hold:

• supp(u) \ supp(u′) = {b} for some b#u′.

• supp(u′) \ supp(u) = {b′} for some b′#u.

• |u|a ∩|u′|a = {(b a)u′}.
• |u|a ∩|u′|a = {(b′ a)u}.

3. |u|a = |u′|a and u = u′.

Proof

If |u|a ∩|u′|a = ∅ then we are done. So suppose that z ∈|u|a ∩|u′|a.

By definition

|u|a = {(n a)u | n = a ∨n#u} and |u′|a = {(n′ a)u′ | n′ = a ∨n′#u′}.

Here and for the rest of this proof, n and n′ range over all atoms (and may be equal to a or each other).

Then z = (n a)u and z = (n′ a)u′ for some n and n′, for which there are several possibilities:

• If n = a and n′ = a then u = u′ and we fall into the third case.

• n = a and n′ ≠ a is impossible because a ∈ supp(u) and by Theorem 2.14 a ∉ supp((n′ a)u′).

• Similarly if n ≠ a and n′ = a.

• Suppose that n ≠ a and n′ ≠ a and n = n′. Then u = u′ and we fall into the third case.

• Suppose that n ≠ a and n′ ≠ a and n ≠ n′. We have supposed that (n a)u = (n′ a)u′, recall that n#u and n′#u′. By Theorem 2.14

(n a)supp(u) = (n′ a)supp(u′).

Using Lemma 4.4 we can calculate that this can only happen if

supp(u) \ supp(u′) = {n′} and supp(u′) \ supp(u) = {n}.

We now verify by easy calculations that we fall into the second case.End of proof

For example:

• |a|a ∩|(a, b)|a = ∅.
• |(a, b)|a ∩|(c, a)|a = {(c, b)} = {(b a)(c, a)}.
• |(a, b)|a ∩|(a, b)|a = |(a, b)|a.
Corollary 4.6

Suppose ¬(a#u) and ¬(a′#u′). Then precisely one of the following holds:

1. |u|a ∩|u′|a′ is empty.

2. u = u′ and |u|a ∩|u|a′ = {u}.

3. u ≠ u′ and |u|a ∩|u′|a′ is a singleton. In this case all of the following hold:

• supp(u) \ supp(u′) = {b, a} for some b#u′.

• supp(u′) \ supp(u) = {b, a′} for some b#u.

• |u|a ∩|u′|a′ = {(b a′)u′}.
• |u|a ∩|u′|a = {(b a)u}.

4. |u|a = |u′|a′, a′#u, and u = (a a′)u′.

Proof

Choose some fresh c (so c#a, a′, u, u′). By Theorem 2.14 ¬(c#(c a)u) and ¬(c#(c a′)u′). Also by Lemma 4.3 we know that

|u|a = |(c a)u|c and |u′|a′ = |(c a′)u′|c.

Using Theorem 4.5 we calculate that there are three possibilities:

1. |u|a ∩|u′|a′ is empty.

2. |u|a ∩|u′|a′ is a singleton {z}. In this case (here n and n′ range over all atoms, and in particular may be equal to a, a′, c, or each other):

• supp((c a)u) \ supp((c a′)u′) = {n} for some n#(c a′)u′.

• supp((c′ a′)u′) \ supp((c a)u) = {n′} for some n′#(c a)u.

• |u|a ∩|u′|a′ = {(n c)(c a′)u′}.
• |u|a ∩|u′|a′ = {(n′ c)(c a)u}.

Now we must consider some further possibilities:

• Suppose n = a′. Then we can use Lemma 4.4 to calculate it must be that supp(u′) = supp(u), and so that n′ = a. Therefore u = u′ and |u|a ∩|u′|a′ = {u}.

• The case n′ = a is similar.

• Suppose n ≠ a′ and n′ ≠ a. Then:

– Using Lemma 4.4 and our assumption that a ∈ supp(u) we know that supp(u) \ supp(u′) = {n, c}. (It easily follows that u ≠ u′.)

– Using Lemma 4.4 and our assumption that a′ ∈ supp(u′) we know that supp(u′) \ supp(u) = {n′, c}.

– By Theorem 2.13 and our assumption that c#u′ we know that |u|a ∩ |u′|a′ = {(n a′)u′}.

– By Theorem 2.13 and our assumption that c#u we know that |u|a ∩ |u′|a′ = {(n′ a)u}.

3. |u|a = |u′|a′ and (c a)u = (c a′)u′. By Theorem 2.14 and our assumption that c#u, u′ we deduce that a′#u. By Theorem 2.13 and Theorem 2.5 we further deduce that u = (c a)(c a′)u′ = (a a′)u′ as required.End of proof

We need a new definition and a technical lemma before we prove Theorem 4.9: We call A ⊆A cofinite when A \ A is finite.

Lemma 4.7

If S ⊆A is cofinite then supp(S) = A \ S.

Proof

By Theorem 2.15 we know that supp(A\S) ⊆ supp(S). By the same Theorem we know that supp(S) ⊆ supp(A \ S). The result follows by Lemma 2.22.End of proof

The following result is a well-known property of FM set theory [23]:

Lemma 4.8

A ∈P(A) is either finite or cofinite, and not both.

Proof

We know that supp(A) exists and is finite by Theorem 2.13. So πA = A for any π ∈ fix(supp(A)). It follows by an easy calculation that A is either finite or cofinite. A cannot be both finite and cofinite, because (AtmInf) insists that A be infinite.End of proof

Theorem 4.9

Suppose ¬a#u and U ⊆|u|a. a#U if and only if

• U is finite and u ∉U, or

• U is cofinite and u ∈U.

Proof

Let S = {n | (n a)u ∈|u|a} (here n ranges over all atoms, and may equal a). Choose some fresh c (so c#S, u, U). S is either finite or cofinite by Lemma 4.8. By Lemma 2.22 if S is finite then supp(S) = S. By Lemma 4.7 if S is cofinite then supp(S) = A \ S.

Now we just consider the possibilities:

• Suppose S is finite and a ∉S. Then u ∉U. Also using Theorem 2.13 and the fact that c#u we have:

(c a)U = {(c a)(n a)u | n ∈S} = {(n c)(c a)u | n ∈S} = {(n a)u | n ∈S} = U.

It follows that a#U.

• Suppose S is finite and a ∈S. Then u ∈U. By similar reasoning we deduce that (c a)U = (U\{u}) ∪{(c a)u}. Now we assumed that ¬a#u so by Theorem 2.14 we know that u ≠ (c a)u. It follows that ¬a#U.

• The cases for U cofinite are similar.End of proof

4.2. Crucial elements

∆ is defined in Definition 3.17. The following properties are easy to prove —

• X ∆X = ∅.

• X ∆∅= X.

• X ∆Y = Y ∆X.

• (X ∆Y ) ∆Z = X ∆(Y ∆Z).

— we use them without comment henceforth.

Lemma 4.10

(b a)(X ∆Y ) = ((b a)X) ∆ ((b a)Y), and if a#X and a#Y then a#X ∆Y .

Proof

By Theorems 2.5 and 2.15.End of proof

Definition 4.11

Call u a-crucial for X when

• ¬a#u.

• ¬(a#(|u|a ∩X)).

Write u εa X when u is a-crucial for X.

Remark 4.12

In nominal techniques it is known that an element can be as important by its absence from a set, as by its inclusion in that set. For example it is the ‘missing a’ in A \ {a} that is responsible for supp(A \ {a}) = {a}.

Note that it is not necessarily the case that if u εa X then u ∈X. For example,

a εa A \ {a}.

u εa X is a measure of whether u is ‘conspicuous’ in X, at least as far as a ∈ supp(X) is concerned — either by its absence or its presence. We make this measure by looking at whether u is in, or is not in, the intersection of its own a-orbit with X.

For example: the a-orbit of a is A, and a is conspicuously absent from A ∩ (A \ {a}) = A \ {a}, so a εa A \ {a}.

Write

CaX for {x | x εa X}.
Theorem 4.13

a#X if and only if for every u, if ¬a#u then a#(X ∩|u|a).

Proof

Suppose a#X. Consider some u such that ¬a#u and write U = X ∩|u|a. We use part 2 of Theorem 4.9:

• Suppose U is finite and u ∈U. Choose some b such that (b a)u ∉U and b#X. We observe that (b a)X ≠ X, which by Theorem 2.13 contradicts our assumption that a#X and b#X. So u ∉U and therefore a#U.

• Suppose U is cofinite and u ∉U. We choose some b such that (b a)u ∈U and b#X, and reason similarly.

Now suppose a#(X ∩|u|a) for every u such that ¬(a#u). Choose any b#X. We can calculate that X = ⋃{X ∩|u|a | ¬(a#u)} and so

(b a)X =⋃{(b a)(X ∩|u|a) | ¬(a#u)} =⋃{X ∩|u|a | ¬(a#u)} = XEnd of proof

Recall from Remark 4.1 that we mentioned that CaX is a measure of ‘how far X is away from satisfying a#X’. Corollary 4.14 makes that formal:

Corollary 4.14

a#X if and only if CaX = ∅.

Proof

Suppose a#X. By Theorem 4.13 we know that a#(X ∩|u|a) for every u such that ¬(a#u). It follows that CaX = ∅.

Conversely suppose that CaX = ∅. This means that if ¬a#u then a#(X ∩|u|a). It follows by Theorem 4.13 that a#X.End of proof

As a matter of convenient notation, write

X −a for X ∆CaX.
Corollary 4.15

supp(X −a) ⊆supp(X) \ {a}.

Proof

There are two parts to this result: we show that a#(X −a) always, and that if b#X then b#(X −a).

For the first part, by Theorem 4.13 it suffices to show that for every u such that ¬(a#u) it is the case that:

• If (X −a) ∩|u|a is finite then u ∉ (X −a) ∩|u|a.

• If (X −a) ∩|u|a is cofinite then u ∈ (X −a) ∩|u|a.

Now (X −a) ∩|u|a is finite or cofinite if and only if X ∩|u|a is finite or cofinite respectively, since by construction CaX ∩|u|a never has more than one element.

Also note that if ¬(a#u) then u ∈X −a if and only if u ∉X. This suffices to prove the first part.

For the second part, suppose that b#X. Then b#CaX by Theorem 2.15, and so b#(X −a) by the same theorem.End of proof

Note that supp(X −a) need not be equal to supp(X)\{a} in general. For example take X = {(a, b)}; then CaX = X and X −a = ∅.

4.3. Operations on sets of crucial elements

Lemma 4.16

A ∩ (X ∆Y ) = (A ∩X) ∆ (A ∩Y).

Proof

By easy calculations.End of proof

Lemma 4.17

Ca(X ∆Y ) = (CaX) ∆ (CaY).

Proof

Pick any u such that ¬a#u. So for any Z, u ∈CaZ if and only if ¬a#(|u|a ∩ Z).

Write A = |u|a ∩X and B = |u|a ∩Y . By Lemma 4.16 we can simplify:

• u ∈Ca(X ∆Y) when ¬a#A ∆B.

• u ∈CaX when ¬a#A.

• u ∈CaY when ¬a#B.

The result now follows reasoning by cases on whether A and B are finite, using part 2 of Theorem 4.9.End of proof

Support is not preserved under taking unions in general. For example supp(A) = ∅ and supp({a}) = supp(A \ {a}) = {a}, so it is not the case that supp(X ∪Y) is related in any useful way to supp(X) ∪ supp(Y ). Lemma 4.17 identifies ∆ as a way of combining sets which is similar to sets union, but which interacts nicely with support.

Likewise, it is not in general the case that a#X if and only if a#x for all x ∈X. Corollary 4.14 identifies x εa X, or equivalently x ∈CaX, as a notion of membership which is similar to sets membership, but which interacts nicely with support.

Lemma 4.18

If U ⊆CaZ then CaU = U.

In particular Ca(CaZ) = CaZ.

Proof

By the construction of Ca and by Theorem 4.5 we know that U ∩|u|a ⊆{u}. Since u ∈CaZ we know that ¬a#u.

Suppose u ∈U. By Lemma 2.22 ¬a#{u} and so u ∈CaU. Suppose u ∈CaU. Then ¬a#(U ∩|u|a) and so U ∩|u|a = ∅ is impossible and U ∩|u|a = {u}. Therefore u ∈U.End of proof

The following lemma connects the permutation action with crucial elements:

Lemma 4.19

If b#Z then (b a)Z = (Z −a) ∆ (b a)CaZ.

Proof

By elementary calculations Z = (Z −a) ∆CaZ so by Lemma 4.10

(b a)Z = (b a)(Z −a) ∆(b a)CaZ.

By Corollary 4.15 we know a#(Z −a) and b#(Z −a). By Theorem 2.13 we know (b a)(Z −a) = Z −a. The result follows.End of proof

It is useful to note a non-result.

Lemma 4.20

• It is not necessarily the case that Ca(X ∩Y ) = CaX ∩CaY .

• Likewise it is not necessarily the case that Ca(X ∪Y ) = CaX ∪CaY .

Proof

• Ca(A ∩{a}) = {a} but CaA ∩Ca{a} = ∅∩{a} = ∅.

• Ca((A \ {a}) ∪{a}) = ∅ but Ca(A \ {a}) = {a} and Ca({a}) = {a}.End of proof

However, we do have the following useful ‘pointwise’ property in the case that sets are finite:

Lemma 4.21

If X is a finite set then CaX = ⋃{x ∈X | ¬a#x}.

Proof

Take u such that ¬a#u. Then u ∈CaX if and only if ¬a#(|u|a ∩X). By Lemma 2.22 we know that ¬a#(|u|a ∩X) if and only if ¬a#x for some x ∈X such that ¬a#x. The result follows.End of proof

Corollary 4.22

If X is a finite set then CaX is a finite set.

Proof

By Lemma 4.21 CaX = {x ∈X | ¬a#x}. So CaX ⊆X and in particular CaX is finite.End of proof

The converse to Corollary 4.22 does not hold. For example N (the natural numbers implemented in set theory e.g. as {∅, {∅}, {∅, {∅}}, . . .}) and A satisfy CaN = CaA = ∅, but they are not finite sets.

5. A second substitution action, using crucial elements

We now define a second substitution action. By shameless abuse of notation we shall use the same notation as we did for the first: [a↦→x].

Where there is any danger of ambiguity we write the substitution action of Definition 3.14 as [a↦→x]1 and the substitution action of Definition 5.1 below as [a↦→x]2. All unannotated uses of the notation [a↦→x] in this section, refer to Definition 5.1 below.

The second substitution action gives the second possible answer to the quiz in Remark 3.9. For example

{a}[a↦→1] = {1} and a#(A ∪N),

and

((A \ {a}) ∪N)[a↦→1]2 = A ∪(N \ {1}).

Here we see that a ‘missing a’ is replaced by a ‘missing 1’. This behaviour is symmetric between ‘missing’ and ‘not missing’;

(A \ {a})[a↦→1]2 = A ∪{1}.

Here a ‘missing a’ is replaced by a ‘missing missing 1’!

Intuitively, imagine sets as collections of binary switches describing what is and what is not an element of the set; the second substitution action flips these switches between ‘on’ and ‘off’. More on this in Subsection 6.1.

5.1. Definition and properties

We recall our notational conventions:

• x, y, z, u, v range over arbitrary elements.

• X, Y, Z, U, V range over elements that are not atoms (i.e. ‘sets’).

• a, b, c, a′, . . . range permutatively over atoms (so a ≠ a′ and a ≠ b).

• A, B, C, S, T range over sets of atoms.

Definition 5.1

Suppose x is any element. Define the substitution action [a↦→x] by:

• a[a↦→x] = x.

• b[a↦→x] = b.

• If Z ∉A then

Z[a↦→x] = (Z −a) ∆⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(CaZ)} δ(u, a, x) = (supp(u)(a↦→supp(x))) \ supp(u[a↦→x]).
Lemma 5.2

Suppose that B = {b1, . . . , bn} is a finite set of atoms and suppose that bi#x, Z for 1 ≤i ≤n. Then

Z[a↦→x] = (Z −a) ∆⋃{(u[a↦→x])‖A(a↦→supp(u))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}∪B(CaZ)}.
Proof

By the same method as the proof of Lemma 3.19.End of proof

Theorem 5.3 ((id↦→)).

z[a↦→a] = z.

Proof

We work by ϵ-induction.

The base cases of z ∈A are easy:

• a[a↦→a] = a.

• b[a↦→a] = c.

Now suppose Z ∉A (we adhere to our notational convention and write capital ‘Z’). Then using Lemma 5.2 we have:

Z[a↦→a] = (Z −a) ∆⋃{(u[a↦→a])‖A(a↦→a)\δ(u,a,a) | (u, A) ∈plane{a}(CaZ)}

By reasoning similar to that in Theorem 3.16 we can deduce that

⋃{(u[a↦→a])‖A(a↦→a)\δ(u,a,a) | (u, A) ∈plane{a}(CaZ)} = CaZ.

The result follows.End of proof

Theorem 5.4 ((α)).

If b#z, a then z[a↦→x] = ((b a)z)[b↦→x].

Proof

We work by ϵ-induction.

The base cases of z ∈A are easy:

• a[a↦→x] = x = ((b a)a)[a↦→x] by definition.

• b#b is false so there is nothing to prove for the case b[a↦→x].

• c[a↦→x] = c = ((b a)c)[a↦→x] by definition.

Now suppose Z ∉A (we adhere to our notational convention and write capital ‘Z’). We expand the definition of ((b a)Z)[b↦→x]:

((b a)Z)[b↦→x] = ((b a)Z ∆Cb(b a)Z) ∆⋃{(u′[b↦→x])‖A′(b↦→x)\δ(u′,b,x) | (u′, A′) ∈planesupp(x)∪{b}(Cb(b a)Z)}

By Corollary 4.15 we know that

a#((b a)Z ∆Cb(b a)Z) and b#((b a)Z ∆Cb(b a)Z).

By Theorems 2.5 and 2.13 we deduce that

((b a)Z ∆Cb(b a)Z) = Z −a.

So it would suffice if we show that

⋃{(u′[b↦→x])‖A′(b↦→x)\δ(u′,b,x) | (u′, A′) ∈planesupp(x)∪{b}(Cb(b a)Z)} = ⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,b,x) | (u, A) ∈planesupp(x)∪{a}(CaZ)}

The proof of this is almost identical to the proof of Theorem 3.21.End of proof

Theorem 5.5 ((#↦→)).

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

Proof

We work by ϵ-induction. We start with the base cases:

• a#a is false so there is nothing to prove for a[a↦→x]. We need not check that a[a↦→x] = a, because it is not the case that a#a.

• b[a↦→x] = b by definition.

Now suppose Z ∉A (we adhere to our notational convention and write capital ‘Z’). The result now follows easily expanding definitions, noting that CaZ = ∅ by Corollary 4.14.End of proof

To prove Theorem 5.10 below we need a number of technical results:

Lemma 5.6

If ¬a#z and ¬c#z then Ca|z|c = |z|c.

Proof

Suppose that u ∈Ca|z|c. We want to show that u ∈|z|c. By construction ¬a#u and ¬a#(|u|a ∩|z|c). By Corollary 4.6 precisely one of the following holds:

1. |u|a ∩|z|c = ∅.

It is a fact that a#∅ so we can discount this option.

2. u = z and |u|a ∩|z|c = {u}.

Then u ∈|z|c.

3. u ≠ z and |u|a ∩|z|c is a singleton. Then supp(z) \ supp(u) = {b, a} for some b#u and |z|c ∩|u|a = {(b a)u} = {(b c)z}. But this is not possible because a#(b a)u and also ¬a#(b c)z by Theorem 2.14.

4. |u|a = |z|c.

This is impossible because by construction |z|c contains infinitely many v such that ¬a#v, but |u|a contains only one; we use Theorem 2.14.

Now suppose that u ∈|z|c. So either u = z or for some b#z it is the case that u = (b c)z. We want to show that u ∈Ca|z|c.

Suppose u = z. Since ¬a#z it suffices to also show that ¬a#|z|a ∩|z|c. By Corollary 4.6 we know that |z|a ∩|z|c = {z} and by Lemma 2.22 we know ¬a#{z} so we are done.

Suppose u = (b c)z for some b#z. By Theorem 2.14 we know ¬a#u so it suffices to show that ¬a#(|u|a∩|z|c). We consider the various possibilities in Corollary 4.6 and see that it must be that |u|a ∩|z|c = {u}. The result follows again using Lemma 2.22.End of proof

Lemma 5.7

If a#z and ¬c#z then Ca|z|c = ∅.

Proof

By Theorem 2.15 and Corollary 4.14.End of proof

Like [a↦→t]1 from Definition 3.14, [a↦→t]2 is pointwise on finite sets:

Lemma 5.8

If Z is a finite set then

Z[a↦→x] = {z[a↦→x] | z ∈Z}.
Proof

Unpacking definitions,

Z[a↦→x] = (Z −a) ∆⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(CaZ)}.

By Lemma 4.21 Z −a = {u | u ∈Z, a#u}, and by Theorem 5.5

Z −a = {u[a↦→x] | u ∈Z, a#u}.

By reasoning similar to that in the proof of Theorem 3.26,

⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(CaZ)} = {u[a↦→x] | u ∈Z, ¬a#u}.

The result follows.End of proof

Corollary 5.9

(z, z′)[a↦→x] = (z[a↦→x], z′[a↦→x]).

Proof

By two uses of Lemma 5.8.End of proof

Theorem 5.10 ((abs↦→)).

If c#x then ([c]z)[a↦→x] = [c](z[a↦→x]).

Proof

If a#z then by Theorem 2.15 also a#[c]z and

([c]z)[a↦→x] = [c]z and [c](z[a↦→x]) = [c]z

follow by Theorem 5.5. So suppose a ∈ supp(z). We unpack definitions:

([c]z)[a↦→x] = ([c]z −a) ∆⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(Ca([c]z))}.

By Lemma 5.6 Ca[c]z = [c]z and so ([c]z −a) = ∅ and we simplify ([c]z)[a↦→x] to:

⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}([c]z)}.

The result now follows by reasoning similar to that in the proof of Theorem 3.24.End of proof

Theorem 5.11

Definition 5.1 is equivariant and satisfies (α), (#↦→), (var↦→), (id↦→), and (abs↦→) from Subsection 3.1.

Proof

Equivariance is automatic by Theorem 2.5. (var↦→) is direct from the definition. Each of (α), (#↦→), (id↦→), and (abs↦→) is by one of the theorems proved above.End of proof

Theorem 5.12

If z, x ∈ Λ then z[a↦→x] ∈ Λ and z[a↦→x] is equal to what we would normally call ‘capture-avoiding substitution of x for a in z’.

Proof

By an easy induction similar to the proof of Theorem 3.29.End of proof

Corollary 5.13

If a#y and x, y, z ∈ Λ then z[a↦→x][b↦→y] = z[b↦→y][a↦→x[b↦→y]].

Proof

By induction on z.End of proof

Like Theorem 3.29 and Corollary 3.31, Theorem 5.12 and Corollary 5.13 are generic and work for any datatype of syntax implemented in FM set theory.

5.2. Scope-extrusion and hereditarily finite crucial sets

Scope-extrusion is an expression used to describe how binders can sometimes increase (‘extrude’) their scope over a connective — usually up to some notion of equivalence, usually subject to a freshness side-condition on free variables. Examples include behaviour displayed by π-calculus name-restriction and first-order logic universal quantification:

P | νa.Q is equivalent with νa.(P | Q) if a not free in P
φ ⇒∀a.ψ is equivalent with ∀a.(φ ⇒ψ) if a not free in φ

[a↦→x]2 satisfies a form of scope-extrusion with respect to ∆ and subject to a nominal freshness side-conditions. With the results we have so far, the proof is easy:

Theorem 5.14

Suppose a ∈A and Z ∉A and Z′ ∉A.

If a#Z then (Z ∆Z′)[a↦→x] = Z ∆(Z′[a↦→x]).
Proof

Recall that CaZ = ∅ by Corollary 4.14. We unpack definitions using Lemma 4.17,

(Z ∆Z′)[a↦→x] = Z ∆(Z′ −a) ∆⋃{(u[a↦→x])‖A(a↦→supp(x))\δ(u,a,x) | (u, A) ∈planesupp(x)∪{a}(CaZ′)},

and this is precisely equal to Z ∆ (Z′[a↦→x]) as required.End of proof

Remark 5.15

The condition that Z ∉A and Z′ ∉A on Theorem 5.14 excludes the case that ∆ is undefined (see Definition 3.17). There seems no plausible way to extend ∆ to atoms so that Theorem 5.14 makes sense. The problem case is when Z ∉A and Z′ = a. If we let Z ∆a = Z (because a is empty; it has no set elements) then (Z ∆a)[a↦→x] = Z, which is not in general equal to Z ∆x. If we let Z ∆a = a (just to see what happens) then (Z ∆a)[a↦→x] = x, which is again not in general equal to Z ∆x. Similarly if we let Z ∆a = ∅.

The question itself may be misguided: Z ∆Z′ is the symmetric difference of Z and Z′ and so is all about the elements of Z and Z′. Atoms are not determined by their extension; they have no elements but are not equal to the empty set. Thus, ∆ (an extensional creature) applied to atoms (intensional creatures) is a mild category (‘typing’) error. For this reason, we let ∆ be undefined in Definition 3.17 and leave the side-conditions in Theorem 5.14.

Remark 5.16

Scope-extrusion is familiar from syntax. It is nice to see it reproduced for ∆. Scope-extrusion for ∆ has a broader meaning. To understand why, we recall some of the research context of this work.

Recall our second answer in the quiz in Remark 3.9, which discussed substituting a ‘missing a’ for a ‘missing 1’.

‘Nominal techniques’ were introduced by the author with Pitts in [23], emerging from Fraenkel-Mostowski sets. One of their distinctive features was the use of permutations — bijective renamings of names (modelled in FM sets by atoms) — to handle α-equivalence. A benefit of permutation is that they move around ‘missing atoms’. For example

(b a)(A \ {a}) = A \ {b}

— the ‘missing a’ has been replaced by a ‘missing b’.7 From this we can take a lesson that a conspicuous absence of an element can be as important as its presence. Corollary 5.17 makes formal a sense in which scope-extrusion (Theorem 5.14) gives the second substitution action the same kind of behaviour with respect to ‘missing elements’.

Corollary 5.17

Suppose that V is a set such that a#V . Suppose also that P ⊆V .8 Then (V \ P)[a↦→x] = V ∆ (P[a↦→x]).

Proof

We rewrite V \P as V ∆P. The result follows by Theorems 5.14 and 5.5.End of proof

The substitution action [a↦→t]2, like [a↦→t]1, is not necessarily pointwise on infinite sets:

Lemma 5.18

It is not necessarily the case that if z ∈Z then z[a↦→x] ∈Z[a↦→x].

Proof

It suffices to provide a counterexample. a[a↦→∅] = ∅ and A[a↦→∅] = A by Theorem 5.5. We note that ∅∉A[a↦→∅].End of proof

Definition 5.19

Call Z finite crucial when CaZ is finite for all atoms a. As a matter of convention call a ∈A finite crucial as well.

We can use Theorem 5.14, along with the notion of finite crucial sets, to obtain an elementary characterisation of the substitution action on a broad class of sets:

Theorem 5.20

If Z is finite crucial then Z[a↦→x] = (Z −a) ∆{z[a↦→x] | z ∈CaZ}.

Proof

By Theorem 5.14

Z[a↦→x] = (Z −a) ∆(CaZ)[a↦→x].

We use Lemma 5.8.End of proof

Lemma 5.21

1. If Z is finite crucial then so is CaZ.

2. If X and Y are finite crucial then so is X ∆Y .

3. If Z is finite crucial then so is Z −a.

Proof

1. Ca(CaZ) = CaZ by Lemma 4.18, and this is finite.

2. By Lemma 4.17 and some easy calculations on sets.

3. By the first two parts.End of proof

Definition 5.22

Define the class of hereditarily finite crucial sets inductively by:

• a ∈A is hereditarily finite crucial.

• Z is hereditarily finite crucial if Z is finite crucial and every z ∈Z is hereditarily finite crucial.

The following technical properties will be useful soon:

Lemma 5.23

1. Any finite set is finite crucial.

2. A finite set is hereditarily finite crucial if all of its elements are.

3. If X and Y are hereditarily finite crucial then so is X ∆Y .

4. If Z is hereditarily finite crucial then so is CaZ.

5. If Z is hereditarily finite crucial then so is Z −a.

Proof

1. By Corollary 4.22.

2. By the first part and from the inductive definition of hereditarily finite crucial.

3. Using part 2 of Lemma 5.21 and the fact that X ∆Y ⊆X ∪Y .

4. Suppose Z is hereditarily finite crucial. Then by part 1 of Lemma 5.21 CaZ is finite crucial, so it suffices to show that all its elements are hereditarily finite crucial. Take any z ∈CaZ. By definition, either z ∈Z or that there is some b#z such that (b a)z ∈Z. If z ∈Z then z is hereditarily finite crucial by our assumption that Z is hereditarily finite crucial. Otherwise (b a)z ∈Z and so (b a)z ∈Z is hereditarily finite crucial. By Theorem 2.5 it follows that z is hereditarily finite crucial.

5. The result follows by parts 3 and 4.End of proof

Corollary 5.24

If z and x are hereditarily finite crucial then z[a↦→x] is hereditarily finite crucial.

Proof

We reason by ϵ-induction. First we consider the base cases:

• a[a↦→x] = x. We assumed x is hereditarily finite and the result follows.

• b[a↦→x] = b. By definition b is hereditarily finite crucial and the result follows.

Now suppose Z ∉A. We can rewrite Z as (Z −a) ∆CaZ. By assumption CaZ is finite, by Corollary 4.15 also a#(Z −a). By Theorem 5.20 also

Z[a↦→x] = (Z −a) ∆{z[a↦→x] | z ∈CaZ}.

By parts 2 and 3 of Lemma 5.23 it now suffices to show that

z[a↦→x] is hereditarily finite crucial for each z ∈CaZ. This follows by the inductive hypothesis (and Theorem 2.5; we do not know that z ∈Z but πz ∈Z for some π and that is enough).End of proof

Theorem 5.25

If z, x, and y are hereditarily finite crucial and if a#y, then

z[a↦→x][b↦→y] = z[b↦→y][a↦→x[b↦→y]].
Proof

We work by ϵ-induction. The base cases are easy:

• a[a↦→x][b↦→y] = x[b↦→y] = a[b↦→y][a↦→x[b↦→y]].

• b[a↦→x][b↦→y] = y = b[b↦→y][a↦→x[b↦→y]].

• c[a↦→x][b↦→y] = c = c[b↦→y][a↦→x[b↦→y]].

Now suppose Z ∉A. We can rewrite Z using Lemma 4.17 to

Z = (Z −a) ∆CaZ = ((Z −a) −b) ∆Cb(Z ∆CaZ) ∆CaZ = ((Z −a) −b) ∆CbZ ∆CbCaZ ∆CaZ.

By Corollary 4.15 b#(Z −a)−b and a#(Z −a)−b. Therefore by scope-extrusion Theorem 5.14 we can write:

Z[a↦→x][b↦→y] = ((Z −a) −b) ∆{z[a↦→x][b↦→y] | z ∈CbZ ∆CbCaZ ∆CaZ}.

It is a fact of the definitions that for each z ∈CbZ ∆CbCaZ ∆CaZ there is some permutation π such that πz ∈Z. We use Theorem 2.5 and the inductive hypothesis:

Z[a↦→x][b↦→y] = ((Z−a)−b) ∆{z[b↦→y][a↦→x[b↦→y]] | z ∈CbZ ∆CbCaZ ∆CaZ}.

We now reverse our previous reasoning to obtain the result.End of proof

Hereditarily finite crucial sets z generalise syntax trees. They need not be finite, but for each atom they do have only finitely many elements ‘responsible’ for that atom being in supp(z).

6. Summary, related work, and conclusions

Our substitution actions were discovered in a set theory known for the better part of a century [7, 40]. The substitution arises spontaneously; there is nothing in the axioms of FM set theory to suggest that a substitution action should be possible. Even after the author and Pitts re-discovered Fraenkel-Mostowski set theory and applied it to syntax-with-binding [23], the substitution action remained hidden. This is good; it suggests that we have not built into our model the behaviour we want. ‘Substitution’ arises as a mathematical operation derived naturally from the basic foundational assumptions determined by the axioms of Fraenkel-Mostowski set theory. This is an interesting contribution for set theory, computer science, and their intersection.

We see three broad avenues for future work: to look at how substitution interacts with ‘objects of behaviour’, by this we mean sets representing for example traces of actions in process calculi; with graphs of functions represented as sets; and with equivalence classes of syntax quotiented for example by αβ-equivalence. We did consider this in a little more detail at the end of Subsection 6.1. Preliminary investigations, not written up in this paper, suggest that the techniques presented in this paper can be applied in all three cases above, modulo some technical adaptations to the specific domain. This paper provides the technical basis for investigating these, and we hope other applications, in future work.

6.1. Summary of the two substitution actions

In Subsection 1.1 we sketched the design issues involved in defining a substitution action on a sets universe. [a↦→x]1 and [a↦→x]2 both do the following to Z: they decompose Z into component planes, calculate substitution component-wise, and combine the results.

There may even be other notions of decomposition other than the planes used in this paper, but what is certain is that not every decomposition is suitable. For example A = {a} ∪ (A \ {a}) but we do not want to base a substitution action on this decomposition since a#A but ¬a#{a} and ¬a#(A \ {a}).

Care goes into the design of the expression A(a↦→supp(x)) \ δ(u, a, x) in Definition 3.14. This ‘intelligently adjusts ‖-orbits’ for changes in support caused by substitution on representatives — part of the mechanism of getting generalised α-equivalence classes right — and it describes the interaction of substitution with planes. Other choices may also be possible here.

The design of [a↦→x]2 introduces CaZ, the a-crucial elements of Z. In a certain sense this only substitutes on those elements ‘responsible’ for ¬a#Z (if any). It is more complex but has somewhat better properties; notably it satisfies scope-extrusion Theorem 5.14, treats ‘missing elements’ and set-subtraction in an elegant way (Corollary 5.17), and interacts well with hereditarily finite crucial sets (Theorem 5.25).

On ‘easy sets’ the two substitution actions that we have defined coincide (Theorems 3.29 and 5.12). The important differences are in the treatment of ‘missing elements’. For example (recall that Ca(A \ {a}) = {a}):

(A \ {a})[a↦→∅]1 = A (A \ {a})[a↦→∅]2 = A ∪{∅} (A \ {a})[a↦→(a, a)]1 = A (A \ {a})[a↦→(a, a)]2 = A ∪{(a, a)}

On (sets modelling) syntax the behaviour is as we expect:

(a, ∅)[a↦→∅]1 = (∅, ∅) (a, ∅)[a↦→∅]2 = (∅, ∅) (a, b)[a↦→b]1 = (b, b) (a, b)[a↦→b]2 = (b, b)

Behaviour may become counterintuitive, if we base our intuitions only on the behaviour for syntax and then extend these intuitions to the universe of sets:

((A\{a})∪{∅})[a↦→∅]1 = A∪{∅} ((A\{a})∪{∅})[a↦→∅]2 = A ((A\{a})∪{(a, a)})[a↦→(a, a)]1 = A∪{(a, a)} ((A\{a})∪{(a, a)})[a↦→(a, a)]2 = A {a, ∅}[a↦→∅]1 = {∅} {a, ∅}[a↦→∅]2 = ∅ {a, b}[a↦→b]1 = {b} {a, b}[a↦→b]2 = ∅

We conclude by asking: what other technical demands can we make of a substitution action?

• What sets have most general unifiers (what is the theory of ‘set unification’)?

• What is the computational content of an element z considered as the function x maps to z[a↦→x]?

• Can we provide a denotational semantics for first-order rewriting [39]?

• Can we model the λ-calculus [4], the π-calculus [34] and its related name-passing calculi, or first-order predicate logic [27], using a substitution action to directly model substitution?

• It may be possible to model first-order logic by mapping sentences P, Q . . ., open or closed, to subsets of an FM set U representing the universe of discourse; variables x, y . . . of a first-order language map to the set A of atoms; if a first-order sentence P is assigned the set y ⊆U as its semantic denotation, then the sentence ∀xP has as its denotation the set ⋂u{y[a↦→u] | u ∈U}. This is more than just a translation of the syntactic substitution-for-all-terms operation into another language, for [a↦→u] represents an operation directly on the sets universe which can be constructed from the axioms of FM sets.

6.2. Related work

The axioms for substitution in this paper are taken from [22]. This paper continues that work by showing how the Fraenkel-Mostowski sets universe can be made a model of those axioms; in some sense which it may be possible to make formal in future work, it is a largest possible model.

Higher-order logic uses substitution to reflect function application in syntax [42]. Substitution does not exist in denotation, and neither do variables.

Calculi of explicit substitutions analyse the structure of carrying out a substitution, but to our knowledge they are purely operational systems without denotation [32].

Aczel’s ‘generalised set theory’ [2] and ‘universes with parameters’ [3] model variable symbols (Aczel calls them parameters) as atoms in a ZFA-like set theory. However, Aczel imposes all the structure he needs as specific axioms on names. What Aczel does with his sets is also very different; it concerns coinductive structures and non-wellfounded set theory [1] as a semantics for behaviour. Aczel’s substitution action is such that Z[a↦→x] = {z′[a↦→x] | z′ ∈Z} always, like the pointwise substitution action [a↦→x]n from Definition 3.3.

CIAO Prolog [25, Extra-logical predicates] and a-logic [18] include a predicate var(x) which is true of x when x is a variable symbol. It is used to implement shallow embeddings of programming languages — for more details see [25]. The functional programming language CURRY [26] has similar constructs. The designers of these languages struggle to bring current denotational methods to bear on these constructs, because they put variables in the denotation, just as we have done. Making a connection with our work is current research.

Fine [12] has undertaken a philosophical axiomatic investigation of dependency between objects. For example, z and 2 ∗z are ‘arbitrary numbers’ but they are also connected. A formal connection might be established with our constructions if we take substitution to give a notion of ‘correlation’ between sets; for example if z[a↦→x] = z′, or z[a↦→x] = z′[a↦→x], then z and z′ are ‘correlated’.

Nominal terms [41] come equipped with a substitution action, but this is for context variables and is not capture-avoiding. It should not be confused with the capture-avoiding substitution action for atoms of this paper.

Other axioms for substitution exist; for example in work by Salibra [37], by Beeson [5], by Crabbé [10], and by Feldmann [11]. The axioms of Crabbé and Feldmann are not of capture-avoiding substitution; the axioms of Salibra and Beeson are. Salibra is interested in models but his models are abstract (he does universal algebra). Beeson is interested in theorem-proving. The axioms of Salibra and Beeson for substitution are embedded in larger theories of Turing-complete computation based on the λ-calculus, which gives their treatment a very different flavour from ours. Feldman’s axioms are based on a concrete model using environments (functions mapping variables to denotational objects) which is very different from our model which is based on a set theory (a far larger construction) and in which variables inhabit the denotation. Fiore, Plotkin, and Turi consider substitution in [14]. The models they build use presheaf categories not dissimilar to the category of nominal sets from [23] (there, we called them ‘FM-sets’). Modulo inessential differences, the ‘definition of substitution by structural recursion’ on pages 6 to 7 of that paper corresponds with the substitution by structural recursion in [24], while the treatment of ‘substitution algebras’ on page 7 corresponds with our axiomatisation in nominal algebra of capture-avoiding substitution [22].9

Schmidt-Schauß and Siekmann introduce unification algebra [38] and Williams introduces instantiation theory [43]. The idea is to free the theory of unification from (the shackles of) syntax. An axiomatic approach is taken to substitution. The work is ‘bespoke’ in the sense that the specification of the model includes a specification of the object of study; substitution, instantiation, and unification. In this paper we do not consider unification but we do extract substitution from an independent structure (the axioms of set theory).

6.3. The rôle of Fraenkel-Mostowski sets

We will conclude with some words on our use of Fraenkel-Mostowski sets.

The substitution actions we build in Definitions 3.14 and 5.1 rely on having a collection Z whose elements have a substitution action; in that case, we can define substitution actions on Z as well. So we can read our substitution actions informally as follows:

Given a collection of elements with a substitution action, the collection of finitely supported subsets of that collection (the ‘finitely supported powerset’) also has a substitution action — and in at least two different ways!

So this is not quite about Fraenkel-Mostowski set theory; it is about sets with a substitution action, their finitely supported powersets, and ways to extend the substitution action from the base set to its set of finitely supported powersets.

The cumulative hierarchy model is built from the set of atoms, taking finitely supported powersets transfinitely (Remark 2.12). Thus, defining our substitution action on a cumulative hierarchy model lets us get on with studying a substitution action, without having first to express a theory of ‘sets with a substitution action’.

This is convenient, but there is more to our design choice than convenience. It is an empirical observation that most interesting mathematical structures — probably, all the ones we normally consider — can be modelled by taking powersets and using sets comprehension to whittle down the resulting structures to something representing what we want. Powersets are a foundation for mathematics.

Our substitution actions act on every mathematical structure that we can model using powersets. This concrete model is not universal in a categorical sense; it is universal in the sense that it operates on mathematical universes and everything that can be built within them. That is something new and unexpected.

We illustrate this with a possible application. Our substitution actions make the atoms-concretion function from [23] into a total function by substituting for the abstracted atom; [a]z concreted at x is z[a↦→x].10 This happens automatically, because the Gabbay-Pitts atoms-abstraction can be modelled using powersets.

References

[1] Peter Aczel. Non-wellfounded Set Theory. Number 14 in CSLI lecture notes. CSLI, 1988.

[2] Peter Aczel. Generalised set theory. CSLI lecture notes, 1(58):1–17, 1996.

[3] Peter Aczel and Rachel Lunnon. Universes and parameters. CSLI lecture notes, 2:3–24, 1991.

[4] H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, 1984.

[5] Michael Beeson. Lambda logic. In Second International Joint Conference on Automated Reasoning (IJCAR 2004), volume 3097 of Lecture Notes in Computer Science, pages 460–474. Springer, 2004.

[6] 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 Lecture Notes in Computer Science, pages 86–101, 2005.

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

[8] James Cheney and Christian Urban. Alpha-prolog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proc. of the 20th Int’l Conf. on Logic Programming (ICLP 2004), number 3132 in Lecture Notes in Computer Science, pages 269–283. Springer, 2004.

[9] D. Clarke, R. Hinze, J. Jeuring, A. oh, and J. de Wit. The generic haskell user’s guide. Technical Report UU-CS-2001-26, November 2001.

[10] M. Crabbé. On the notion of substitution. Logic Journal of the IGPL, 12 n.2:111– 124, 2004.

[11] Norman Feldman. Axiomatization of polynomial substitution algebras. Journal of Symbolic Logic, 47(3):481–492, 1982.

[12] Kit Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.

[13] Marcelo Fiore and Daniele Turi. Semantics of name and value passing. In Proc. 16th LICS Conf., pages 93–104. IEEE, Computer Society Press, 2001.

[14] Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi. Abstract syntax and variable binding. In LICS ’99: 14th Annual Symposium on Logic in Computer Science, pages 193–202. IEEE, 1999.

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

[16] Murdoch J. Gabbay. The pi-calculus in FM. In Fairouz Kamareddine, editor, Thirty-five years of Automath, volume 28 of Kluwer applied logic series, pages 247–269. Kluwer, November 2003.

[17] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982–1011, July 2007.

[18] Murdoch J. Gabbay and Michael J. Gabbay. a-logic. In We Will Show Them: Essays in Honour of Dov Gabbay, volume 1. College Publications, 2005.

[19] Murdoch J. Gabbay and Martin Hofmann. Nominal renaming sets. In LPAR’08, 2008.

[20] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC 2006: Theoretical Aspects of Computing, volume 4281 of Lecture Notes in Computer Science, pages 198–212, 2006.

[21] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order logic. In PPDP ’06: Proc. of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, pages 189–200. ACM, 2006.

[22] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, January 2008.

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

[24] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax Involving Binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, 1999.

[25] CLIP group. CIAO Prolog documentation project. http://www.ciaohome.org.

[26] Michael Hanus, Sergio Antoy, Herbert Kuchen, Francisco J. López-Fraguas, Wolfgang Lux, Juan José Moreno-Navarro, and Frank Steiner. Curry: An integrated functional logic language. 2003.

[27] Wilfrid Hodges. Elementary predicate logic. In D.M. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer, 2001.

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

[29] Thomas Jech. Set theory. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Fall 2002.

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

[31] Ralf Lämmel and Simon Peyton Jones. Scrap your boilerplate: a practical design pattern for generic programming. In TLDI, pages 26–37. ACM, 2003.

[32] Pierre Lescanne. From lambda-sigma to lambda-upsilon: a journey through calculi of explicit substitutions. In POPL, pages 60–69. ACM, 1994.

[33] S. Lusin and A. Salibra. The lattice of lambda theories. Journal of Logic and Computation, 14 n.3:373–394, 2004.

[34] Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, II. Information and Computation, 100(1):41–77, 1992.

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

[36] A. M. Pitts and Murdoch J. Gabbay. A metalanguage for programming with bound names modulo renaming. In MPC2000, volume 1837 of Lecture Notes in Computer Science, pages 230–255. Springer, 2000.

[37] Antonino Salibra. On the algebraic models of lambda calculus. Theoretical Computer Science, 249(1):197–240, 2000.

[38] Manfred Schmidt-Schauß and Jörg Siekmann. Unification algebras: An axiomatic approach to unification, equation solving and constraint solving. Technical Report SEKI-report SR-88-09, FB Informatik, Universität Kaiserslautern, 1988.

[39] Terese. Term Rewriting Systems. Number 55 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2003.

[40] J. Truss. Permutations and the axiom of choice. In H.D.Macpherson R.Kaye, editor, Automorphisms of first order structures, pages 131–152. OUP, 1994.

[41] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, 2004.

[42] Johan van Benthem. Higher-order logic. In Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 189–244. Kluwer, 2001.

[43] James Williams. Instantiation theory. Technical Report M-90-04, The Mitre Corporation, 1990.

Notes

1Thanks to Arnon Avron. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid. ↩

2This argument is due to an anonymous referee. ↩

3supp(A \ {a}) = {a} and supp(A) = ∅. ↩

4If c ∈ supp(x) then ((c, a), {a}) ∉ planesupp(x)∪{a}([c]a). ↩

5Lng is based on work in [16]. To see in what sense an element Lng can represent an infinite name-generating — and infinitely name-generating — coinductive structure, consider the case where X is the set of finite lists of atoms. We will write ⟨⟩ for the empty list and ⟨x1, . . . , xn⟩ for the n-element list with xi in the ith position for 1 ≤i ≤n, and we consider the element which we can then write as:

⟨⟩:: [a]⟨a⟩:: [b]⟨a, b⟩:: [c]⟨a, b, c⟩:: [d]⟨a, b, c, d⟩:: . . .

We can read this as an accumulator, with a state which is a list of atoms, and which at each step of its behaviour generates a fresh atom and pushes it onto the tail of its state.

↩

6F is the category of finite sets and maps between them. I is the category of finite sets and injections between them. It may be worth noting that the name-for-name substitution action modelled in SetF is not quite a special case of any substitution action based on the work in this paper, even allowing for the different presentations (categories versus sets). This is because in SetF (and also in SetI), all presheaves are considered and not only presheaves preserving pullbacks of monos. The ‘preserves pullbacks of monos’ corresponds with Theorem 2.13 and ensures that ‘every element has a unique least supporting set’. It is this property which makes possible the ‘sets-based’ presentations characteristic of nominal techniques. See [19] for a further discussion. ↩

7This particular fact enters into the axioms for substitution via (id↦→) in Definition 3.1. ↩

8Note that a#P need not necessarily hold. For example {a} ⊆A. ↩

9From the point of view of [14, 22] the existence of multiple substitution actions on a model of Fraenkel-Mostowski sets, as exhibited in this paper, corresponds with the observation that the underlying set of a substitution algebra as specified in [14], or of a substitution set as specified in [22], may support two or more distinct substitution actions. ↩

10Thanks to Andrew Pitts for this observation. ↩