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

Substitution for Fraenkel-Mostowski foundations

Murdoch J. Gabbay1 and Michael J. Gabbay2

Abstract. A fundamental and unanalysed logical concept is substitution. This seemingly innocuous operation — substituting a variable for a term or valuating a variable to an element of a domain — is hard to characterise other than by concrete constructions. It is widely viewed as a technicality to be dispensed with on the way to studying other things. Discussions of computer science foundations, and of the philosophy of logic, have largely ignored it.

We show that Fraenkel-Mostowski set theory gives a model of variables and substitution as constructions on sets. Thus models of variables and substitution are exhibited as constructions in a foundational universe, just like models of arithmetic (the ordinals) and other mathematical entities. The door is open for classes of denotations in which variables, substitution, and evaluations are constructed directly in sets and studied independently of syntax, in ways which would previously have not been possible.

1 Introduction

Computer science evolved out of the study of logic and the foundations of mathematics of the late 19th and early 20th centuries. Part of the motivation for that study was to devise a framework to explain mathematical knowledge, as can clearly by seen in the work of Gottlob Frege [10, 11]. Frege’s development of predicate calculus was, amongst other things, intended to explain the content of statements about ‘an arbitrary number’ without positing some special entity that is an arbitrary-number. In terms of the modern predicate calculus, the solution was that a statement about an arbitrary number has the form of an open or universally quantified sentence. So: the content of A(x) or ∀x.A(x) is given by the contents of A(x)[x/t] for all t that denote elements of a certain domain.

This approach leaves unexplained the phenomenon of the substitution of x for a term. Substitution is not trivial: substitutions may occur within other substitutions and when a substitution is carried out, variables must be renamed to ensure that no unwanted bindings result. Therefore the explanation of knowledge of generic mathematical statements in terms of substitutions just changes the issue to the explanation of knowledge about substitution. We might ask again what exactly we know when we know that A(x)[x/t] for any t.

In fact, attempts to formalise the theory of substitution show that the ‘explanation’ in terms of substitutions just makes matters worse. The complexity of the knowledge needing an explanation has increased, if the content of A(x) has been given in terms of the more complex A(x)[x/t]. “What is the content of the arbitrary t in A(x)[x/t]?” we may ask — an answer in terms of the even more complex A(x)[x/y][y/t] is of no help.

We find no relief in replacing talk of substitution with talk of valuations: this merely translates the problem into a different language; the content of ∀x.A(x) is given in terms of valuations A(x)⟨x↦→d⟩ for all d — but what is a valuation, and what do we know when we know the generic statement that, say A(x)⟨x↦→d⟩= ⊤ for all valuations on x?

This problem is not confined to the philosophical question of the content of an open or universally quantified statement. All formal languages used to express functions and computations, and reasoning about functions and computations, refer to substitution of variables for terms or to the resolution of a variable to a value. An account of the content of substitution and valuation would therefore shed light on functions and computation.

But are we misguided, or asking for too much, when we ask for an explanation of substitution? After all, the syntax of a formal language is impossible to formulate without using schematic variables and substitution. Research into computer science cannot get off the ground without, at least, some recourse to formal syntax. This suggests that we must be satisfied to take substitution as an unanalysable primitive — we must either take substitution as a purely formal syntactic manipulation, or accept that the only possible explanation of substitution on the syntax of one formal language must be in terms of substitution in another ‘meta’ formal language (the so-called Higher-Order Abstract Syntax approach [19]). In either case, we must give up on trying to provide a foundational theory to account for substitution independently of formal syntax.

In this paper we shall show that, on the contrary, there is an independent foundation that can interpret the action of substitution and valuation. This foundation is called Fraenkel-Mostowski set theory.3

Fraenkel-Mostowski set theory [6, 22] (FM set theory) was originally developed to prove the independence of the axiom of Choice from the other axioms of Zermelo-Fraenkel set theory. It was rediscovered and used by the first author and Pitts to model abstract syntax with binding [16]. An advantage of modelling syntax in a model of FM set theory is that datatypes of syntax quotiented by α-equivalence can be modelled inductively (rather than as quotients by α-equivalence of syntax-without-binding). This is because FM set theory delivers a model of variable symbols and α-abstraction [16] — these feature in this paper as atoms (Subsection 2) and atoms-abstraction (Subsection 2.4).

Unlike HOAS [19] there is no problem with ‘exotic terms’; also more functions, such as α-inequality, may be expressed; finally, and there is no need in FM for levels of carefully-constrained meta-language. Unlike de Bruijn indexes [8] the reasoning and programming principles of syntax-with-binding in FM are natural and correspond very closely to informal practice. Seven years of research, culminating in an implementation of these ideas in Isabelle [23] have demonstrated the practical potential of this technique.

What makes this all take off is that the model of variable symbols and α-abstraction provided by FM set theory is applicable to all sets, including those modelling functions, predicates, domains, games, and so on. They can be applied to denotations other than sets modelling syntax. Since the introduction of these ideas [16] there now exist programming languages [21, 7], logics [20, 14], models of storage [5], and semantics of references using game theory [1] — research continues and the work all uses the model of variable symbols and α-abstraction which emerges from FM set theory.

However we usually are interested in variable symbols and α-abstraction because we want a capture-avoiding substitution action. In this paper we demonstrate that the variable symbols in models of FM set theory admit a substitution action defined as an operation between arbitrary sets. We also show that this substitution action avoids capture with α-abstraction. In short, any model of FM set theory is also a model of something that looks like ‘substitution’ in formal syntax, but which is valid for all sets.

We envisage denotations using FM set theory in which variables and open terms are explained directly as sets — without needing valuations — and substitution in syntax is explained directly as substitution on sets.

2 Fraenkel-Mostowski set theory

2.1 Axioms, permutations, equivariance

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

Definition 1

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

In Figure 1 we use standard definitional extensions of the language of sets. Pfin(A) is the finite powerset of A (the set of finite subsets of A). ‘S supports x’ is described in Definition 4. The standard cumulative hierarchy model of these axioms is described in Remark 8.

We will use some notational conventions in the rest of this paper:

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

Remark 2

An atom a ∈A is ‘empty’ (∀x.x ∉a) but not equal to ∅. (Extensionality) is weakened so that an empty element is equal to ∅, or is an atom.

Note that (AtmInf) insists that there are infinitely many atoms.

2.2 Atoms, equivariance and support

Write (a b) for the swapping function from atoms to atoms:

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

By our permutative convention, a, b, and c are distinct.

Let π range over functions generated by composing finitely many swappings, call these functions permutations. Write ◦ for functional composition and π-1 for the inverse of π, which is also a permutation. The action of permutations extends to all sets by ϵ-induction [18]:

πX = {πx | x ∈X}.

Let φ(x1, . . . , xn) range over predicates in the language of FM set theory that mention variables in x1, . . . , xn. An n-rary function F(x1, . . . , xn) can be expressed by an n+1-ary 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 3

φ(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 follows using the standard encoding of an n-ary function as an n+1-ary predicate.End of proof

Equivariance (Theorem 3) holds because atoms have no internal set structure. It is a useful source of one-line proofs [14, 12]; we shall exploit that in this paper. Equivariance is also a sense in which atoms are ‘abstract’: if we pick some sets, containing some specific atoms, and prove a property of them, then that property is as true of the sets with the atoms permuted; the identity of atoms only matters up to permutations.

2.3 Support

Definition 4

If S ⊆A write fix(S) = {π | ∀a ∈A.π(a) = a}. Say that S ⊆A supports x when ∀π ∈ fix(A).πx = x. Define supp(x) the support of x by:

supp(x) =\ {S | S is finite, S supports x}.

supp(x) always exists in FM set theory because (Fresh) insists that a finite S supporting x exists. Write a#x when a ∉ supp(x). Read this ‘a is fresh for x’. We may write a#t1, t2 for ‘a#t1 and a#t2’, and so on.

Remark 5

For example:

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

• supp(A) = ∅.

π{a, b, c, . . .} = {π(a), π(b), π(c), . . .} = {a, b, c, d, . . .} forall π ∈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}).

(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
Remark 6

Ideas from syntax match ideas from FM sets as follows: variable symbols matches atoms and free variables matches support. Of course, 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 understand 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 7

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 8 below. There is no finite S ⊆A such that if π ∈ fix(S) then π{a, c, e, g, . . .} = {a, c, e, g, . . .}.

Remark 8

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 = Si Ui. The reader can imagine all our constructions taking place in this model and no harm will come of it.

Theorem 9

If S and T support x and are finite, then so does S ∩T. As a corollary, supp(x) is the unique smallest set supporting x.

Proof

The corollary follows by calculations and by (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 π ◦π = Id, so π = π-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 9 says πx depends only on the values of π on atoms in supp(x). Support goes back to Fraenkel and Mostowski [17, Chapter 4]; applications in computer science followed later [16, 12].

Theorem 10

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

Proof

From Theorem 3.End of proof

A calculation cannot ‘create support’ not in its inputs:

Theorem 11

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

Proof

If π ∈ fix(S supp(xi)) then π ∈ T fix(xi). By Theorem 3 πF(x1, . . . , xn) = F(πx1, . . . , πxn). The result follows.End of proof

2.4 α-abstraction in models of FM set theory

Substitution is interesting and hard to characterise because of its interaction with α-equivalence, itself deceptively complex. For example, we distinguish x and y in Px and Py but not in ∀x.Px and ∀y.Py. We now show how to α-abstract an atom a in a set x. With sets, it is standard to abstract by taking an equivalence class. For example the concept ‘even number’ can be modelled as the collection of even numbers. Intuitively Definition 12 defines an equivalence class resulting from renaming atoms not in A, and thus α-abstracts over atoms in supp(x)\A. This is then exploited in Definition 16.

Definition 12

Suppose A ⊆A. Write

u|Afor {πu | π ∈fix(A)}.

(Recall that fix(A) = {π | ∀a ∈A.π(a) = a}.) 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}, . . .}

Since fix(A) is a group we have:

Lemma 13

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

In words: u|A is an equivalence class of sets which are equal ‘up to renaming atoms not in A’.

Theorem 14

Suppose A is a finite set of atoms. Then:

• If supp(u) ⊆A then supp(u|A) = supp(u).

• supp(u|A) ⊆A always.

As a corollary, if supp(u) \ A ≠ ∅ then supp(u|A) = A.

Proof

• If supp(u) ⊆A then u|A = {u}. For example, supp(a|{a}) = supp({a}) = {a} and supp(a) = a.

• If supp(u) ⊆A then we use the first part. If there is some a ∈ supp(u) \ A then the result follows by an easy calculation illustrated by the following example:

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

The corollary follows.End of proof

Definition 15

Write (x, y) for {{x}, {x, y}} (a set implementation of ordered pairs [18]).

Definition 16

Let atoms abstraction be [c]z = (c, z)|supp(z)\{c}.

Intuitively [c]z is an α-equivalence class of (c, z) where c is abstracted, i.e. where we read (c, z) like ‘λc.z’ or ‘∀c.z’:

[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), . . .}

We can read ‘[a]x’ as the binding action of ‘λa.x’ or ‘∀a.x’, and the sets above corresond with α-equivalence classes of FM sets. There is no a priori notion of λ-abstraction or universal quantification in [a]x; this is just α-abstraction, on FM sets.

Definition 16 agrees with the definition of [c]z from [16]:

Lemma 17

[c]z = {(x, (x c)z) | x ∈A, x ≠ c, x#z} ∪{(c, z)}.

2.5 Further properties of support, finite sets, and α-abstraction

Lemma 18

1. supp(X) = S{supp(x) | x ∈X} if X is finite.

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

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

Proof

If X is finite then supp(X) ⊆ S{supp(x) | x ∈X} follows by Theorem 11.

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 10 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 9 it must be that a ∈ supp(X).

The second part is immediate; the third is by Definition 15.End of proof

Theorem 19

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

Proof

By part 3 of Lemma 18 supp((c, z)) = supp(z) ∪{c}. By definition [c]z = (c, z)|supp(z)\{c}. The result follows by Theorem 14.End of proof

Thus we expect (a d)[a]{a, b} = [a]{a, b}:

[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 20

supp(X) ⊆ S{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 S{supp(a) | a ∈A} = A. supp(A\{c})={c} but S{supp(a) | a∈A ∧a≠c} = A\{c}.End of proof

3 The substitution action

We now turn to defining an operation on sets that matches the syntactic operation of substitution. It must interact correctly with the α-abstraction of Definition 16.

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

3.1 Axioms, naïve substitution action

Definition 21

A substitution action on FM set theory is a function z[a↦→x] expressed in the language of FM set theory taking an element z, an atom a, and an element x, and returning an element which we write as z[a↦→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])

If we read a#x as ‘a is not free in x’ and z[a↦→x] as ‘substitute x for a in z’ then, clearly, the axioms of Definition 21 are sound for the standard syntactic model. In [13] they are also proved complete.4

FM set theory has notions of ‘name’ and ‘free in’, and ‘abstraction’. We can therefore try to build a function which models ‘capture-avoiding substitution’ in the sense made precise by the axioms of Definition 21.

Definition 22 is probably what we might first consider:

Definition 22

Define the naïve substitution action by

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

Write 0 = ∅ and i + 1 = i ∪{i}, and write N = {0, 1, 2, 3, . . .}.

Lemma 23

Naïve substitution does not satisfy (α), (#↦→), or (abs↦→), and so is not a substitution action in the sense of Definition 21.

Proof

It suffices to give 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

The naïve substitution action does not take into account that substitutions should be capture avoiding and does not interact property with the FM treatment of abstraction. We need a more subtle substitution action that ‘unpacks’ an FM set to discern the ‘free’ atoms and equate the ‘bound’ atoms. The basic units of such an unpacking are the planes defined in Definition 24.

3.2 The planes of a set

Definition 24

If A ⊆A is finite call (u, A) a plane in Z when

• u|A ⊆Z and A ⊆ supp(Z), and

• u|A is maximal in that for all u′|A′ ⊆Z where A′ ⊆ supp(Z),

u|A ⊆u′|A′implies u′|A′ = u|A.

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

(u, A) is a plane in Z when A is a least subset of supp(Z) such that u|A ⊆Z. 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 25

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 supp(u) ‘avoids name-clashes’ with S. For example

(a, {}) ∈plane{}(A) but (a, {}) ∉plane{a}(A) and

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

The planes of Z ‘cover’ Z in the following sense:

Lemma 26

If S ⊆A is finite then

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

As a corollary taking S = ∅, 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 10 we can calculate that

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

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

3.3 The substitution action, with examples

We can now define the substitution action. We use Lemma 26 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’.

Definition 27

If A, S ⊆A are finite then define

A(a↦→S) =( (A \ {a}) ∪S if a ∈AA if a ∉A.
Definition 28

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

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

• 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 (if c ∈ supp(x) then ((c, a), {a}) ∉ planesupp(x)∪{a}([c]a)). We omit calculations showing that (c, a)[a↦→x] = (c, x); for a general result see Theorem 32 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 Ub = {a} ∪{{a}, {c}, {d}, . . .} for each b. 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 29

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

Lemma 30

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

Proof

By Theorem 11 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 11

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

The result follows using Theorem 10.End of proof

Lemma 31

supp(z[a↦→x]) ⊇ supp(z)(a↦→supp(x)) need not necessarily hold.

Proof

A counterexample is Ub[a↦→{b}] above.End of proof

In the terminology of Definition 22, the substitution action is naïve on finite sets:

Theorem 32

If Z ∉A and Z is finite 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 part 1 of Lemma 18 that supp(u) ⊆ A and u|A = {u}.

By Lemma 30 supp(u[a↦→x]) ⊆ supp(u)(a↦→supp(x)), so

δ(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

3.4 The substitution action is a substitution action

We now sketch how substitution satisfies (α), (#↦→), (var↦→), (id↦→), and (abs↦→), from Definition 21.

Theorem 33 is a useful technical result:

Theorem 33

b#Z if and only if for all (u, A) ∈ plane(Z) it is the case that b ∉A.

As a corollary supp(Z) = S{A | (u, A) ∈ plane(Z)}.

We may use this result in a slightly different form where we write b ∉A instead of b#A; by part 2 of Lemma 18 these are equivalent.

Proof

By definition if (u, A) ∈ plane(Z) then A ⊆ supp(Z). The left-to-right implication follows.

Now suppose that b#A for every (u, A) ∈ plane(Z). Choose any fresh b′#Z. By the first part of this result, b′#A for every (u, A) ∈ plane(Z). Using part 1 of Lemma 26 we reason as follows:

(b′ b)Z = (b′ b) S{(u|A) | (u, A) ∈plane(Z)}=S{(b′ b)(u|A) | (u, A) ∈plane(Z)}Theorem 9=S{u|A | (u, A) ∈plane(Z)}= Z

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

For Theorem 36 we need a technical ‘capture-avoidance’ result:

Lemma 34

Suppose that Z ∉A, a ∈A, and x is any element.

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

A routine calculation demonstrates that if (u, A) ∈ plane(Z) and supp(u) ‘clashes’ with atoms in B, then we can find a π ∈ fix(A) such that supp(πu) does not ‘clash’ with atoms in B; by Lemma 13 the result follows using Lemma 26.End of proof

Lemma 35

If (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 fresh c (so c#z; also c#a, b since by our permutative convention c, a, b are distinct atoms). 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 9.End of proof

Theorem 36 ((α)).

Z[a↦→x] ⊆ ((b a)Z)[b↦→x] if b#Z. 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 b#z; there are two cases depending on whether z ∈A:

• Suppose z ∈A. Then there are three subcases:

(i) z = a. z[a↦→x] = a[a↦→x] = x = ((b a)a)[b↦→x] = x.

(ii) z = b. This contradicts b#z so there is nothing to prove.

(iii) z = c (where c ∉{a, b}). c[a↦→x] = c = ((b a)c)[b↦→x].

• Suppose Z ∉A. By the first part, Z[a↦→x] ⊆ ((b a)Z)[b↦→x]. Also by Theorem 10 a#(b a)Z and it follows that ((b a)Z)[b↦→x] ⊆ ((b a)(b a)Z)[a↦→x]. The result follows, since (b a)(b a)Z = Z.

We now prove by ϵ-induction that Z[a↦→x] ⊆ ((b a)Z)[b↦→x].

Suppose Z ∉A and b#Z. By Lemma 35 we can assume b#x. Suppose the inductive hypothesis of every u ∈Z. We unpack the definition of substitution, using Lemma 34 to add a {b} to the subscript on plane in the first equality (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 exhibit (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. By Theorem 3 we have (u′, A′) ∈ plane((b a)Z). 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 Theorem 33 and b ∈ supp(x) ∪{a, b}. Therefore b#u. It is now not hard to use Theorem 10 and some elementary set calculations to calculate that

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

So (u′, A′) ∈ planesupp(x)∪{b}(Z). Also 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 supp(((b a)u)[b↦→x]) = supp(u[a↦→x]) follows by the inductive hypothesis. The result follows.End of proof

Theorem 37 ((#↦→)).

For all a ∈A, if a#z then z[a↦→x] = z.

Proof

We work by ϵ-induction. The interesting case is when Z ∉A (we adhere to our convention and write capital Z) and a#Z. 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)}.

For any (u, A) ∈ planesupp(x)∪{a}(Z) by assumption

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

By Theorem 33 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) = ∅ andZ[a↦→x] =[ {u|A | (u, A) ∈planesupp(x)∪{a}(Z)}.

The result follows by part 2 of Lemma 26.End of proof

Theorem 38 ((abs↦→)).

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

Proof

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

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

follow by Theorem 37. So suppose a ∈ supp(z). We sketch the rest of the proof: It is a fact that

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

The other planes add nothing to the final result. So

[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}.

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 part 3 of Lemma 18 to calculate the support of a pairset). The result follows by set calculations.End of proof

Theorem 39 ((id↦→)).

z[a↦→a] = z.

Proof

By an easy inductive argument which we sketch. The interesting case is of Z ∉A where we suppose u[a↦→a] = u for all u ∈Z (we adhere to our convention and write capital Z). By definition

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

This easily simplifies using the inductive hypothesis to

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

and we use Lemma 26.End of proof

Theorem 40

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

Proof

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

3.5 Substitution and abstract syntax

As a sanity check we prove that our substitution action extends the substitution on syntax, if we express syntax in a model of FM set theory as outlined in previous work [15]. In other words: our substitution action coincides with our expectations of what substitution does to syntax, in a sense which we make precise in Theorem 43.

Definition 41

Let Λ be inductively defined by:

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

Λ is isomorphic to λ-terms up to α-equivalence.

Proof

This is the FM standard construction of abstract-syntax-with-binding [16] slightly modified (see Remark 44 below).End of proof

Theorem 43

If z, x ∈ Λ then z[a↦→x] ∈ Λ and z[a↦→x] is equal to what we usually 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]) from Definition 15 and Theorem 32.

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

Define inl(x) = (x, 0) and inr(x) = (x, 1).

Remark 44

Theorem 43 works generically for any datatype of syntax-with-binding. Note that we must interpret atoms as themselves and not ‘wrapped up’: our construction is an isomorphic version of the datatype from [16] 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 43 because atoms are wrapped up in inl(inl(a)) and inl(inl(a))[a↦→x] = inl(inl(x)) ≠ x. There is no canonical implementation of the tree-structure of datatypes — the FM substitution action cannot ‘guess’ which implementation we chose for inl and inr.

Atoms are a distinct class of elements in a model of FM set theory so it does not harm to insert them ‘unwrapped’ into Λ.

3.6 Commuting substitutions

It is routine to prove the usual commutativity property of substitutions. The proof is generic and would work for any datatype:

Corollary 45

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. Only the base case is interesting:

a[a↦→x][b↦→y] = x[b↦→y] = a[b↦→y][a↦→x[b↦→y]].End of proof

For more complex sets substitutions need not commute. That is:

Lemma 46

There exist z, a, x, b, y such that a#y and z[a↦→x][b↦→y] ≠ z[b↦→y][a↦→x[b↦→y]].

Proof

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

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 c’; see the Conclusions. Predicates which reflect on their own variables cannot be expressed in standard logics such as first-order logics; non-commutativity of substitution only holds on sets which intuitively ‘reflect on atoms’ in which case the results obtained may depend on the order in which those atoms are substituted.

4 Conclusions

We have exhibited substitution as an operation in models of FM set theory, with the same status as ‘the graph of a function’, ‘ordered pairs’, ‘ordinals’, and other basic concepts of mathematics. The foundations of computer science are not set in stone, and by paying attention to them, new insights can be gained.

From the philosophical point of view the FM universe provides a basis by which we can obtain a semantics for formal languages where the structure of denotations matches the structure of syntax very closely, also for open terms. In the case that the denotations are of formal syntax, the two coincide as exemplified in Section 3.5.

Since our intention here is to the lay the foundations provided by FM set theory, a full semantic treatment of first order logic is beyond the scope of this paper. However we can hint at how it works. An FM model of first order logic maps the sentences P, Q . . . of first order logic, open or closed, into subsets of an FM set U representing the universe of discourse. The model also maps the variables x, y . . . of a first order language into the set A of atoms. Now, 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 T{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 a particular set theoretic operation constructable from the axioms of FM set theory.

Future work is to use the substitution action above as the basis of semantics for formal languages essential to philosophy and computer science — first-order logic and the λ-calculus are two candidates. It is also possible to investigate ‘rewriting on sets’; starting with investigating the unifiers of two sets.

REFERENCES

[1]S. Abramsky, D. R. Ghica, A. S. Murawski, C.-H. L. Ong, and I. D. B. Stark, ‘Nominal games and full abstraction for the nu-calculus’, in LICS, pp. 150–159. IEEE, (2004).

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

[3]Peter Aczel, ‘Generalised set theory’, CSLI lecture notes, 1(58), 1–17, (1996).

[4]Peter Aczel and Rachel Lunnon, ‘Universes and parameters’, CSLI lecture notes, 2, 3–24, (1991).

[5]Nick Benton and Benjamin Leperchey, ‘Relational reasoning in a nominal semantics for storage.’, in Proc. of the 7th Int’l Conf. on Typed Lambda Calculi and Applications (TLCA), volume 3461 of LNCS, pp. 86–101, (2005).

[6]N. Brunner. 75 years of independence proofs by Fraenkel-Mostowski permutation models, 1996.

[7]James Cheney and Christian Urban, ‘Alpha-prolog: A logic programming language with names, binding and alpha-equivalence’, in Proc. of the 20th Int’l Conf. on Logic Programming (ICLP 2004), eds., Bart Demoen and Vladimir Lifschitz, number 3132 in LNCS, pp. 269–283. Springer-Verlag, (2004).

[8]N. G. de Bruijn, ‘Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem’, Indagationes Mathematicae, 5(34), 381–392, (1972).

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

[10]Gottlob Frege, The Foundations of Arithmetic, Blackwell, Oxford, 1953. Translated by J. L. Austin.

[11]Gottlob Frege, ‘Begriffsschrift, eine der Arithmetischen Nachgebildete Formelsprache des Reinen Denkens’, in From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, ed., J. van Heijenoort, Harvard University Press, (2002). Translated by S. Bauer-Mengelberg as ‘Concept Script, a formal language of pure thought modelled upon that of arithmetic’.

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

[13]Murdoch J. Gabbay and Aad Mathijssen, ‘Capture-avoiding substitution as a nominal algebra’, Formal Aspects of Computing, (2008). Available online.

[14]Murdoch J. Gabbay and Aad Mathijssen, ‘One-and-a-halfth-order logic’, Journal of Logic and Computation, (2008). Available online.

[15]Murdoch J. Gabbay and A. M. Pitts, ‘A new approach to abstract syntax involving binders’, in 14th Annual Symposium on Logic in Computer Science, pp. 214–224. IEEE Computer Society Press, (1999).

[16]Murdoch J. Gabbay and A. M. Pitts, ‘A new approach to abstract syntax with variable binding’, Formal Aspects of Computing, 13(3–5), 341– 363, (2001).

[17]Thomas Jech, ‘Set theory’, in The Stanford Encyclopedia of Philosophy, ed., Edward N. Zalta, (Fall 2002).

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

[19]D. Miller, ‘Abstract syntax for variable binders: An overview’, Lecture Notes in Articial Intelligence, 1861, 239–253, (July 2000).

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

[21]A. M. Pitts and Murdoch J. Gabbay, ‘A metalanguage for programming with bound names modulo renaming’, in Proceedings of the 5th international conference on the Mathematics of Program Construction (MPC2000), eds., R. Backhouse and J. N. Oliveira, volume 1837 of LNCS, pp. 230–255. Springer, (July 2000).

[22]J. Truss, ‘Permutations and the axiom of choice’, in Automorphisms of first order structures, ed., H.D.Macpherson R.Kaye, 131–152, OUP, (1994).

[23]Christian Urban and Christine Tasson, ‘Nominal techniques in Isabelle/HOL’, in CADE 2005, volume 3632 of Lecture Notes in Artificial Intelligence, pp. 38–53, (2005).

Notes

1 http://www.gabbay.org.uk ↩

2 michael.gabbay(at)kcl.ac.uk, Michael Gabbay gratefully acknowledges the support of the British Academy under grant PDF/2006/509. ↩

3 We know of no set-theoretic foundational account of substitution in the literature, besides this paper. However, there have been many attempts to axiomatise the properties that such an account should have. Fine [9] has axiomatised ‘arbitrary objects’, especially investigation of dependency between arbitrary objects; the intuition is that both x and 2 ∗x are arbitrary objects, but they are correlated. It remains to be seen whether a model of FM set theory can be considered as a model of Fine’s axioms. Aczel’s ‘generalised set theory’ [3] and ‘universes with parameters’ [4] model variable symbols (Aczel calls them parameters) as atoms in a ZFA-like set theory. The resemblance ends there; Aczel imposes all the structure he needs as explicit axioms on names, and the substitution action is not capture-avoiding, which is one of the most difficult technical aspects of the work in this paper. The application is also quite different; Aczel investigates coinductive structures and non-wellfounded set theory [2] as a semantics for behaviour. ↩

4 An equivariance rule from [13] is omitted here because it is guaranteed by Theorem 3. Instead of (id↦→) we use a rule (ren↦→) in [13]. A proof that the two formulations are equivalent is not hard (and was observed by an anonymous referee of [13]). The proof is included in a recent work pending publication. ↩