A study of substitution, using nominal techniques and Fraenkel-Mostowki sets
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
2 Fraenkel-Mostowski set theory 6
2.1 Axioms, permutations, equivariance 6
2.3 Orbits under the permutation action 11
2.4 -abstraction 12
3.1 Axioms, pointwise substitution action, syntactic substitution action . . 14
3.2 A short quiz 17
3.4 Construction of the first substitution action 19
3.5 Substitutions on syntax, substitutions commuting 26
4 New properties of FM: -orbits and crucial elements 29
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
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.
-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 . These are empty ( 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 [] and read it ‘substitute with in ’ (so and 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
( is any element, and are any two distinct atoms).
If is a finite set of elements then let substitution be pointwise:
This ensures that tuples ( satisfy
The same holds for -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 in ()’, written []() (Definition 2.20) is
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: []() (where () is ( ())) is
Note that
because does not ‘clash’ with () but it does ‘clash’ with ().
In nominal techniques, when we build equivalence classes of renamed variants like []() and []() above, we ‘avoid name-clash’.
Now, we want substitution to distribute over abstraction in a capture-avoiding way. That is,
we want ([]())[(]()
We cannot obtain what we want by operating pointwise on the elements of [](), i.e. by letting
— not just for finite sets . For, if we operated pointwise, we would not know not to put into ([]())[()] the element ( ())[( ()). 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
or equivalence classes which represent simultaneous abstraction by more than one atom
— we can think of this as ‘abstract and simultaneously in ’ and write it in an informal notation which we do not make formal as
If we apply [()] to this we want to ‘avoid name-clash’ with and , and ‘-convert ’, and ‘fill in renamed variants mentioning ’, to obtain the element
which we can write as
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 , identify as a union of some generalised notion of -equivalence classes . 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 (Subsection 3.3). The set above is which is the equivalence class of all renamed variants of under permutations of atoms fixing (i.e. ‘-abstract and in ).
If we apply [()] to this then we obtain (). Note that this is the same set as () and () — 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 [, is based on the same ideas but with a twist. Instead of acting on all of , the second substitution action isolates the parts of which are responsible for it containing (in nominal terminology; those elements responsible for supp() 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 [ is pointwise but only on points (generalised -equivalence classes) that ‘contain ’ 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 called ‘the set of atoms’.
The axioms of FM set theory are given in Figure 1.
We use standard definitional extensions of the language of sets:
| means | () | |
| means | (()) | |
| means | (() | |
| means | () | |
| () | means | () |
| means | () | |
| means | ||
| means | () |
In addition 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.)
We use the following notational conventions:
An atom is a set member of (the set of atoms).
The permutative convention: range over distinct atoms unless stated otherwise.
range over sets of atoms. For example .
range over elements that are not atoms and may be empty. For example might equal or , but cannot equal .
range over arbitrary elements.
As is standard, we will write and , and write 0 1 2 3.
An atom is ‘empty’, or formally: . 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 is either an atom, or it is a set containing nothing but atoms and (possibly) more sets. For further details see elsewhere [15].
Write () for the swapping of and . This is the mapping from to itself specified by
Note that by our permutative naming convention , , and are distinct.
Write for functional composition. Let range over functions from to generated by functionally composing finitely many swappings, and call these permutations. A permutation action is defined by -induction [30]:
The permutation action satisfies equivariance. This very useful property is also very easy to prove. Let () range over predicates in the language of FM set theory which mention variables in , ..., . An -rary function () can be expressed by a predicate () such that for each ,..., there is a unique making true. Then equivariance is the following two properties:
() (), and
always hold.
The first part is by an easy induction on the syntax of . We consider just one case: implies follows directly from the fact that . The reverse implication uses .
The second part, for , follows using the encoding of functions as predicates.
2.2. Support
If write
Say that supports when
We write
and call this the support of . supp is well-defined because (Fresh) insists that some finite supporting must exist.
We write # when supp() and read this as is fresh for . We may write # for ‘# and #’, 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].
For example:
supp(. for all fix().
supp(.
supp(
supp(
supp(
supp(. for all fix().
supp(.
provided that fix().
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 and # are not the same thing. supp measures how ‘conspicuous’ is in , either by its set membership or lack of set membership. For example:
Not every collection has finite support.
(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 such that if fix then .
A set well-ordering atoms is not finitely supported, and is excluded from the cumulative hierarchy model of Remark 2.12:
There is no finite such that if fix 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:
There is no finite such that if fix then .
Theorem 2.10 was the reason Fraenkel-Mostowski set theory was originally created and studied:
The axiom of choice is inconsistent with the axioms of FM.
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]
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 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 have a finite supporting set’.
(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 defined as follows:
Then . 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 instead of only 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:
If and support and are finite, then so does .
As a corollary, supp is the unique smallest finite set supporting .
The corollary follows by elementary calculations and (Fresh).
Suppose fixes pointwise. We must show . Write for () . Choose an injection of into () (we can say ‘ freshens ’). Let (() and (( for , and ( otherwise. Note that . fixes pointwise so . Also fixes pointwise so (). We apply to both sides and simplify and conclude that as required.
Theorem 2.13 means that the action of on depends only on the values of on the atoms in supp
supports if and only if supports . As a corollary, supp( supp().
From Theorem 2.5.
supp(()) supp
Suppose supp
2.3. Orbits under the permutation action
We introduce a new notion which we will make much use of in what follows:
Suppose . Write
(Recall that fix((.) We call a set of renamed variants of under permutations fixing atoms in .
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, is a natural sets model of the intuition
“simultaneously -abstract in for all atoms not in .”
This is made formal in Theorem 2.18 and Subsection 2.4.
For example:
If fix then ).
is the orbit of under the action of fix fix is a group. The result follows.
Note that all .
Suppose is a finite set of atoms. Then:
1. If supp
2. supp() always.
As a corollary,
1. If supp() then by the definition of support, if fix() then and
2. Suppose that fix. We reason using Theorem 2.5 and Lemma 2.17:
By Theorem 2.13 the result follows.
We illustrate why the corollary is ‘obvious’ with an example:
Here supp
Now for the proof. Suppose that supp
Suppose . If supp() then by Theorem 2.14 supp() for all . If supp() then by Theorem 2.14 supp() for all .
Suppose . Since supp() by Theorem 2.14 there exist some such that supp, and some such that supp
Thus, we can recover from using the function
By Theorem 2.15 it follows that supp
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].
Write () for .
Define the atoms-abstraction by ).
We can read ‘’ as the binding action of ‘’ or ‘’, 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 is the -equivalence class of () where is abstracted, i.e. where we read () like ‘’ or ‘’. The avoids atoms in supp
Write for
Definition 2.20 gives a result equal to the original definition of atoms-abstraction in FM set theory [23]:
[]( ()) #().
As a corollary, if ()
If supp
In particular if is finite (so that supp
supp( supp and if is finite then supp(.
supp() supp() always, by Theorem 2.15. We now prove the reverse inclusion. Suppose that supp() is finite. Now suppose supp() for some . Choose some such that # and # for every . By Theorem 2.14 supp(())supp(). Since has no element such that supp, we know that () and by Theorem 2.13 it must be that supp
The second part follows easily.
supp(( supp
supp([] supp
So for example, we expect ()[]] since supp(, and
supp
It suffices to give a counterexample; we give two: supp( but supp
3. The substitution action
We recall our notational convention that range over distinct atoms, range over sets of atoms, lowercase range over all elements, and uppercase range over elements that are not atoms.
3.1. Axioms, pointwise substitution action, syntactic substitution action
A substitution action on FM set theory is a function [] expressed in the language of FM set theory (and so satisfying equivariance Theorem 2.5) taking any , an atom , and any , satisfying:
Here by our convention range over elements of the Fraenkel-Mostowski sets universe. , , and range over distinct atoms. An equivariance rule from [22] is omitted here because it is guaranteed by Theorem 2.5.
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:
The pointwise substitution action is defined by
Pointwise substitution does not satisfy (#), or (abs). Therefore, it is not a substitution action in the sense of Definition 3.1.
It suffices to produce counterexamples. We do this for (#) and (abs). We expect that [1] since #. We also expect that ([])[1] []([1]) since #1. But:
Here is another attempt:
The syntactic substitution action is defined by:
| [[ ( finite) | [ (otherwise) |
[ 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 [ we do not include them.
[ 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]. [ 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
If we expand definitions this becomes
Here we write . Now
If we expand definitions this becomes
Thus ()[1] and ([])[1] 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 and () respectively.) For another example:
Compared to the only difference is to place an ordered pair such as () in the first position, instead of just . 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
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 # differs from ‘ is in the transitive closure of ’. For example
and
(See Theorem 2.18 for the necessary results about supp().)
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:
If are finite then define
Any substitution action satisfies that
[Quiz] Recall from Definition 2.3 that we write and , and write 0 1 2 3. Note that supp( for all .
Q. What is (() )[1]?
This makes the minimum change consistent with Lemma 3.8.3
Q. What is (() )[1]?
This makes the minimum change consistent with Lemma 3.8 — and we replace the ‘missing ’ 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
Suppose that is finite. Call () a plane in when is a minimal subset of supp such that .
Write plane for the collection of planes in .
It is easy to see that if () plane then .
Unpacking Definition 3.10, () is a plane in when supp() and and for all (), if supp then
For example:
1. (
2. () plane() because .
3. (
4. ()plane() because
5. (
6. () plane and .
7. (()
8. plane(
If is finite then define
We should think of () as the planes () in such that the support of ‘avoids clashes’ with atoms in , where this is possible. For example
It will later be useful to know that the planes of ‘cover’ in a suitable sense:
If is finite then
As a corollary taking , () plane.
We prove two set inclusions: The left-to-right inclusion is by construction. For the right-to-left inclusion, choose any . Let be equal to supp
By Theorem 2.14 we can calculate that
Therefore supp() supp() . Also () by Lemma 2.17, so () (). Finally we note that ().
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:
If is finite then
By definition if () () then supp. It therefore suffices to prove that if for all () () it is the case that , then #.
Suppose for every () (). Choose any fresh #, so that for every () (). We reason as follows:
Now supp(()) by Theorem 2.14 and the fact that #. The result follows.
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 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 () from Definition 3.7.
Define the substitution action [] and a ‘helper’ function () as follows:
If then
We consider some examples.
1. []. There is one plane, (
2. ()[]. One plane is (
3. []. One relevant plane is () where # (the others give the same result).
4.
One plane is (()
The other planes give the same result.
5. [] where, for a given , we write
and that [ where we write
The other planes give the same results.
6.
One plane is (()) (the other planes give the same result). Note that supp( and supp((
In all other examples is equal to . Here, we see how is not equal to . This corrects for the fact that supp([]) supp()().
Suppose that are finite. Note that () and [] do not coincide. For example, (
Now we show how this construction satisfies the axioms (#), (var), (id), and (abs), and we investigate for what it satisfies (F).
[.
We work by -induction.
The base cases of are easy:
Now suppose (we adhere to our notational convention and write capital ‘’). Suppose the inductive hypothesis of all . By definition
Suppose () plane, so by definition
By inductive hypothesis [, so that supp([ supp. Then we can simplify:
So we have this:
The result follows by Theorem 3.12.
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.
If then define the symmetric difference (the XOR or exclusive or) of and by:
In words, means ‘the set of elements in precisely one of and ’.
Fix any , a finite set of atoms , and any . Suppose that is a permutation, write
Suppose that (supp
Fix , , and . Suppose that is a finite set of fresh atoms (so # for 1 ). Then
(Notice the on the far right subscript.)
By definition
Choose any
Unpacking definitions this means
Now choose some fresh , ..., (so # for 1 ) and write . Write
We show that
1. () plane
2. supp() (supp
— and
3.
This will suffice to prove the result.
1. By Theorem 2.5 () plane(). Now by Theorem 2.13. Also by construction supp and supp( supp so
and therefore
We conclude that () plane as required.
2. supp(supp so by Theorem 2.13. By Theorem 2.5
and we simplify this to
But by Theorem 2.14 we know that supp() so by further elementary set calculations we conclude that
as required.
3. We use Lemma 3.18. We need only check that
and this is by construction.
We use the following technical lemma in Theorem 3.21:
Fix some , , and . Suppose that
Then also
Suppose . If # then [] (())[].
As a corollary, for any if # then [))[].
We first prove the corollary. Suppose that . Then there are three cases:
[ and (())[ and .
# is false, so there is nothing to prove for the case of [].
[ and (())[ and .
Now suppose that (we adhere to our convention and write capital ‘’). Assume that # implies [] (())[] for all .
Now suppose #. Then [] (())[]. Also by Theorem 2.14 #() and it follows that (())[] (()())[]. Now ()() , and the result follows.
For the first part, we work by -induction. Suppose and suppose #. By Lemma 3.20 we can also assume #. Suppose the inductive hypothesis of every . Using the definition of substitution and using Lemma 3.19 for the first equality (to add a to the subscript on plane; we cannot add to the subscript on plane in the second equality because we do not know #)
Suppose () . To prove our set inclusion we just need to exhibit some () (()) such that
We choose ) and ). Then () plane(()) by Theorem 2.5. Also by definition of we know that
Now by construction and supp() . Therefore #. It is now not hard to use Theorem 2.14 and some elementary set calculations to calculate that
So () . Since # by the inductive hypothesis [ [].
It remains to show
Recall that . Then (supp())(supp()) is easily verified. Also
Now supp(())(supp( supp()(supp()) is easily verified, and it follows by the inductive hypothesis that (())[], and we are done.
If # then [.
We work by -induction. We start with the base cases:
# is false so there is nothing to prove for [].
Now suppose (we adhere to our notational convention and write capital ‘’) and # and suppose the inductive hypothesis of all . By definition
Consider any () . By assumption
By construction , so # and by inductive hypothesis [. Now (supp(, and
So
The result follows by Theorem 3.12.
Recall the notion of atoms-abstraction from Definition 2.20.
plane([](( ()) supp
By construction ( supp
by Lemma 2.17. Therefore (( ()) supp
Now take any ()
If # then ([])[]([]).
If # then by Theorem 2.15 also #[] and
follow by Theorem 3.22. So suppose supp. By Lemma 3.23
Using Lemma 3.18 we can calculate that if # then
([])(supp())(()) (())[])(supp())((()))
We can also calculate using Theorems 2.13 and 2.5 that if #[] then
supp([]) )(supp([]) supp(()([]))
By Lemma 2.17 we also have
By Theorems 2.5 and 2.13 ()([))[]. The definitions now simplify to this:
So it suffices to verify that
Now (()supp
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.
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.
If and is a finite set then [[] .
The functions (, inl(), and inr( (), all commute with the substitution action.
Let be any set of elements with empty support, so if then supp( (an example is from Definition 2.3, a non-example is the set of atoms ). Let be an -indexed collection of elements and write () . Then
The results for pairing, inl, and inr follow from Theorem 3.26.
The second part follows noting that the planes of are precisely ( supp()) for , since for all if then .
Let Λ be the datatype of abstract syntax defined inductively by
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.
If Λ then [] Λ and [] is equal to what we would normally call ‘capture-avoiding substitution of for in ’.
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:
This is not suitable for Theorem 3.29 because atoms are wrapped up in inl(inl()) and inl(inl())[ inl(inl()) . 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 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:
If # and Λ then [][[][[]].
By induction on .
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 illustrated below, and also for ‘name-generating’ coinductive datatypes in the style of [16] such as illustrated below:5
(We can also specify this as and
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.
For less structured sets, substitutions need not commute:
(The planes of interest here are , , and .)
Intuitively,
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; for a category in which inequality between names can be determined, and 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: -orbits and crucial elements
To define our next substitution action we have to develop the theory of crucial elements. Given a set we will define a set , the -crucial elements of , which measures ‘how far away is from satisfying #’.
For example
will be equal to and is ‘one away from satisfying #’ (because ).
() will be equal to and is also ‘one away from satisfying #’ (because ).
will be equal to and already satisfies # (even though ).
With reference to the examples above,
An interesting analogy can be drawn between and swapping (): Swapping is very much like atoms-renaming []. 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 . 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 -orbits:
4.1. -orbits
If and any , write
for the set
Call the -orbit of .
For example:
To prove Theorem 4.5 below we need some easy technical lemmas:
1. If # then
2. If # then is an infinite set.
If # and # then (). As a corollary, #().
If is a finite set of atoms such that # and # then () [].
The permutation action is pointwise, so ()(). The result follows by Lemma 2.22 and easy calculations.
The main technical result on -orbits is this:
Suppose (#) and (#). Then precisely one of the following three possibilities holds:
1. is empty.
2. is a singleton. In this case all of the following hold:
supp
supp
3.
If then we are done. So suppose that .
By definition
Here and for the rest of this proof, and range over all atoms (and may be equal to or each other).
Then ) and ) for some and , for which there are several possibilities:
If and then and we fall into the third case.
and is impossible because supp() and by Theorem 2.14 supp(()).
Similarly if and .
Suppose that and and . Then and we fall into the third case.
Suppose that and and . We have supposed that () (), recall that # and #. By Theorem 2.14
Using Lemma 4.4 we can calculate that this can only happen if
We now verify by easy calculations that we fall into the second case.
For example:
Suppose (#) and (#). Then precisely one of the following holds:
1. is empty.
2. and
3. and is a singleton. In this case all of the following hold:
supp
supp
4.
Choose some fresh (so #). By Theorem 2.14 (#()) and (#()). Also by Lemma 4.3 we know that
Using Theorem 4.5 we calculate that there are three possibilities:
1. is empty.
2. is a singleton In this case (here and range over all atoms, and in particular may be equal to , , , or each other):
supp(()) supp(()
supp(()) supp(()
Now we must consider some further possibilities:
Suppose . Then we can use Lemma 4.4 to calculate it must be that supp( supp(), and so that . Therefore and
The case is similar.
Suppose and . Then:
– Using Lemma 4.4 and our assumption that supp we know that supp
– Using Lemma 4.4 and our assumption that supp we know that supp
– By Theorem 2.13 and our assumption that # we know that ().
– By Theorem 2.13 and our assumption that # we know that ().
3. and ()). By Theorem 2.14 and our assumption that # we deduce that #. By Theorem 2.13 and Theorem 2.5 we further deduce that )() ) as required.
We need a new definition and a technical lemma before we prove Theorem 4.9: We call cofinite when is finite.
If is cofinite then supp(.
The following result is a well-known property of FM set theory [23]:
is either finite or cofinite, and not both.
We know that supp exists and is finite by Theorem 2.13. So for any fix(supp()). It follows by an easy calculation that is either finite or cofinite. cannot be both finite and cofinite, because (AtmInf) insists that be infinite.
Suppose # and . # if and only if
is finite and , or
is cofinite and .
Let () (here ranges over all atoms, and may equal ). Choose some fresh (so #). is either finite or cofinite by Lemma 4.8. By Lemma 2.22 if is finite then supp(. By Lemma 4.7 if is cofinite then supp(.
Now we just consider the possibilities:
Suppose is finite and . Then . Also using Theorem 2.13 and the fact that # we have:
It follows that #.
Suppose is finite and . Then . By similar reasoning we deduce that ()) (). Now we assumed that # so by Theorem 2.14 we know that ). It follows that #.
The cases for cofinite are similar.
4.2. Crucial elements
is defined in Definition 3.17. The following properties are easy to prove —
— we use them without comment henceforth.
()()) (()), and if # and # then # .
Call -crucial for when
#.
(#()).
Write when is -crucial for .
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 ’ in that is responsible for supp(
Note that it is not necessarily the case that if then . For example,
is a measure of whether is ‘conspicuous’ in , at least as far as supp is concerned — either by its absence or its presence. We make this measure by looking at whether is in, or is not in, the intersection of its own -orbit with .
For example: the -orbit of is , and is conspicuously absent from ( , so .
Write
# if and only if for every , if # then #().
Suppose #. Consider some such that # and write . We use part 2 of Theorem 4.9:
Suppose is finite and . Choose some such that () and #. We observe that (), which by Theorem 2.13 contradicts our assumption that # and #. So and therefore #.
Suppose is cofinite and . We choose some such that () and #, and reason similarly.
Now suppose #() for every such that (#). Choose any #. We can calculate that (#) and so
Recall from Remark 4.1 that we mentioned that is a measure of ‘how far is away from satisfying #’. Corollary 4.14 makes that formal:
# if and only if .
As a matter of convenient notation, write
supp()
There are two parts to this result: we show that #() always, and that if # then #().
For the first part, by Theorem 4.13 it suffices to show that for every such that (#) it is the case that:
If () is finite then () .
If () is cofinite then () .
Now () is finite or cofinite if and only if is finite or cofinite respectively, since by construction never has more than one element.
Also note that if (#) then if and only if . This suffices to prove the first part.
For the second part, suppose that #. Then # by Theorem 2.15, and so #() by the same theorem.
Note that supp() need not be equal to supp in general. For example take (); then and .
4.3. Operations on sets of crucial elements
() ().
By easy calculations.
() ().
Support is not preserved under taking unions in general. For example supp( and supp( supp(, so it is not the case that supp() is related in any useful way to supp
Likewise, it is not in general the case that # if and only if # for all . Corollary 4.14 identifies , or equivalently , as a notion of membership which is similar to sets membership, but which interacts nicely with support.
If then .
In particular (.
The following lemma connects the permutation action with crucial elements:
If # then ()) ().
It is useful to note a non-result.
It is not necessarily the case that ( .
Likewise it is not necessarily the case that ( .
(
However, we do have the following useful ‘pointwise’ property in the case that sets are finite:
If is a finite set then #.
Take such that #. Then if and only if #(). By Lemma 2.22 we know that #() if and only if # for some such that #. The result follows.
If is a finite set then is a finite set.
By Lemma 4.21 #. So and in particular is finite.
The converse to Corollary 4.22 does not hold. For example (the natural numbers implemented in set theory e.g. as ) and satisfy , 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: [].
Where there is any danger of ambiguity we write the substitution action of Definition 3.14 as [ and the substitution action of Definition 5.1 below as [. All unannotated uses of the notation [] 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
and
Here we see that a ‘missing ’ is replaced by a ‘missing 1’. This behaviour is symmetric between ‘missing’ and ‘not missing’;
Here a ‘missing ’ 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:
range over arbitrary elements.
range over elements that are not atoms (i.e. ‘sets’).
range permutatively over atoms (so and ).
range over sets of atoms.
Suppose is any element. Define the substitution action [] by:
If then
Suppose that is a finite set of atoms and suppose that # for 1 . Then
By the same method as the proof of Lemma 3.19.
[.
If # then [))[].
We work by -induction.
The base cases of are easy:
[))[] by definition.
# is false so there is nothing to prove for the case [].
[))[] by definition.
Now suppose (we adhere to our notational convention and write capital ‘Z’). We expand the definition of (())[]:
By Corollary 4.15 we know that
By Theorems 2.5 and 2.13 we deduce that
So it would suffice if we show that
The proof of this is almost identical to the proof of Theorem 3.21.
If # then [.
We work by -induction. We start with the base cases:
# is false so there is nothing to prove for []. We need not check that [, because it is not the case that #.
[ by definition.
Now suppose (we adhere to our notational convention and write capital ‘Z’). The result now follows easily expanding definitions, noting that by Corollary 4.14.
To prove Theorem 5.10 below we need a number of technical results:
If # and # then
Suppose that . We want to show that . By construction # and #(). By Corollary 4.6 precisely one of the following holds:
1.
It is a fact that # so we can discount this option.
2. and
3. and is a singleton. Then supp() supp( for some # and () (). But this is not possible because #() and also #() by Theorem 2.14.
4.
This is impossible because by construction contains infinitely many such that #, but contains only one; we use Theorem 2.14.
Now suppose that . So either or for some # it is the case that ). We want to show that .
Suppose . Since # it suffices to also show that #. By Corollary 4.6 we know that and by Lemma 2.22 we know # so we are done.
Suppose ) for some #. By Theorem 2.14 we know # so it suffices to show that #(). We consider the various possibilities in Corollary 4.6 and see that it must be that
If # and # then .
Like [ from Definition 3.14, [ is pointwise on finite sets:
If is a finite set then
()[[][]).
By two uses of Lemma 5.8.
If # then ([])[]([]).
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.
If Λ then [] Λ and [] is equal to what we would normally call ‘capture-avoiding substitution of for in ’.
By an easy induction similar to the proof of Theorem 3.29.
If # and Λ then [][[][[]].
By induction on .
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:
[ 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:
Suppose and and .
The condition that and 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 and . If we let (because is empty; it has no set elements) then ()[, which is not in general equal to . If we let (just to see what happens) then ()[, which is again not in general equal to . Similarly if we let .
The question itself may be misguided: is the symmetric difference of and and so is all about the elements of and . 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.
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 ’ 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
— the ‘missing ’ has been replaced by a ‘missing ’.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’.
Suppose that is a set such that # . Suppose also that .8 Then ()[ ([]).
The substitution action [, like [, is not necessarily pointwise on infinite sets:
It is not necessarily the case that if then [] [].
It suffices to provide a counterexample. [ and [ by Theorem 5.5. We note that [].
Call finite crucial when is finite for all atoms . As a matter of convention call 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:
If is finite crucial then [) [] .
1. If is finite crucial then so is .
2. If and are finite crucial then so is .
3. If is finite crucial then so is .
Define the class of hereditarily finite crucial sets inductively by:
is hereditarily finite crucial.
is hereditarily finite crucial if is finite crucial and every is hereditarily finite crucial.
The following technical properties will be useful soon:
1. Any finite set is finite crucial.
2. A finite set is hereditarily finite crucial if all of its elements are.
3. If and are hereditarily finite crucial then so is .
4. If is hereditarily finite crucial then so is .
5. If is hereditarily finite crucial then so is .
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 .
4. Suppose is hereditarily finite crucial. Then by part 1 of Lemma 5.21 is finite crucial, so it suffices to show that all its elements are hereditarily finite crucial. Take any . By definition, either or that there is some # such that (). If then is hereditarily finite crucial by our assumption that is hereditarily finite crucial. Otherwise () and so () is hereditarily finite crucial. By Theorem 2.5 it follows that is hereditarily finite crucial.
5. The result follows by parts 3 and 4.
If and are hereditarily finite crucial then [] is hereditarily finite crucial.
We reason by -induction. First we consider the base cases:
[. We assumed is hereditarily finite and the result follows.
[. By definition is hereditarily finite crucial and the result follows.
Now suppose . We can rewrite as () . By assumption is finite, by Corollary 4.15 also #(). By Theorem 5.20 also
By parts 2 and 3 of Lemma 5.23 it now suffices to show that
[] is hereditarily finite crucial for each . This follows by the inductive hypothesis (and Theorem 2.5; we do not know that but for some and that is enough).
If , , and are hereditarily finite crucial and if #, then
We work by -induction. The base cases are easy:
Now suppose . We can rewrite using Lemma 4.17 to
By Corollary 4.15 #() and #(). Therefore by scope-extrusion Theorem 5.14 we can write:
[][) ) [][]
It is a fact of the definitions that for each there is some permutation such that . We use Theorem 2.5 and the inductive hypothesis:
[][)) [][[]]
We now reverse our previous reasoning to obtain the result.
Hereditarily finite crucial sets 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
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. [ and [ both do the following to : they decompose 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 () but we do not want to base a substitution action on this decomposition since # but # and #().
Care goes into the design of the expression (supp()) () 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 [ introduces , the -crucial elements of . In a certain sense this only substitutes on those elements ‘responsible’ for # (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 (
On (sets modelling) syntax the behaviour is as we expect:
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:
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 considered as the function maps to []?
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 representing the universe of discourse; variables x y of a first-order language map to the set of atoms; if a first-order sentence P is assigned the set as its semantic denotation, then the sentence xP has as its denotation the set [] . This is more than just a translation of the syntactic substitution-for-all-terms operation into another language, for [] 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 [[] always, like the pointwise substitution action [ from Definition 3.3.
CIAO Prolog [25, Extra-logical predicates] and -logic [18] include a predicate var which is true of when 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, and 2 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 [, or [[], then and 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 whose elements have a substitution action; in that case, we can define substitution actions on 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; concreted at is [].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(
4If supp then (()
is based on work in [16]. To see in what sense an element can represent an infinite name-generating — and infinitely name-generating — coinductive structure, consider the case where is the set of finite lists of atoms. We will write for the empty list and for the -element list with in the th position for 1 , and we consider the element which we can then write as:
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.
↩is the category of finite sets and maps between them. is the category of finite sets and injections between them. It may be worth noting that the name-for-name substitution action modelled in 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 (and also in ), 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 # need not necessarily hold. For example . ↩
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. ↩