Substitution for Fraenkel-Mostowski foundations
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 () or () is given by the contents of ()[] for all that denote elements of a certain domain.
This approach leaves unexplained the phenomenon of the substitution of 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 ()[] for any .
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 () has been given in terms of the more complex ()[]. “What is the content of the arbitrary in ()[]?” we may ask — an answer in terms of the even more complex ()[][] 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 () is given in terms of valuations () for all — but what is a valuation, and what do we know when we know the generic statement that, say () for all valuations on ?
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 for ‘the set of atoms’.
The axioms of FM set theory are given in Figure 1.
In Figure 1 we use standard definitional extensions of the language of sets. () is the finite powerset of (the set of finite subsets of ). ‘ supports ’ 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 (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.
An atom is ‘empty’ () 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 () for the swapping function from atoms to atoms:
By our permutative convention, , , and are distinct.
Let range over functions generated by composing finitely many swappings, call these functions permutations. Write for functional composition and for the inverse of , which is also a permutation. The action of permutations extends to all sets by -induction [18]:
Let () range over predicates in the language of FM set theory that mention variables in , . . . , . An -rary function () can be expressed by an -ary 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 follows using the standard encoding of an -ary function as an -ary predicate.
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
If write fix((. Say that supports when fix(). Define supp() the support of by:
supp() always exists in FM set theory because (Fresh) insists that a finite supporting exists. Write # when supp(). Read this ‘ is fresh for ’. We may write # for ‘# and #’, and so on.
For example:
supp(. for all fix().
supp(.
supp(. ( for all fix().
supp(. ( for all fix().
supp(.
supp(. for all fix().
supp(.
supp(.
provided that fix().
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 and # are not the same thing. supp() measures how ‘conspicuous’ is in , either by its set-membership or lack of set membership. For example:
and # and # and supp() and supp() and supp()
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 8 below. There is no finite such that if fix() then .
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 S. The reader can imagine all our constructions taking place in this model and no harm will come of it.
If and support and are finite, then so does . As a corollary, supp() is the unique smallest set supporting .
The corollary follows by calculations and by (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 Id, so . fixes pointwise so . Also fixes pointwise so (). We apply to both sides and simplify and conclude that as required.
Theorem 9 says depends only on the values of on atoms in supp(). Support goes back to Fraenkel and Mostowski [17, Chapter 4]; applications in computer science followed later [16, 12].
supports if and only if supports . As a corollary, supp( supp().
From Theorem 3.
A calculation cannot ‘create support’ not in its inputs:
supp(()) supp()supp().
If fix(S supp()) then T fix(). By Theorem 3 ((). The result follows.
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 and in and but not in and . We now show how to -abstract an atom in a set . 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 , and thus -abstracts over atoms in supp(). This is then exploited in Definition 16.
Suppose . Write
(Recall that fix((.) For example:
Since fix() is a group we have:
If fix() then ).
In words: is an equivalence class of sets which are equal ‘up to renaming atoms not in ’.
Suppose is a finite set of atoms. Then:
If supp() then supp( supp().
supp() always.
As a corollary, if supp() then supp(.
If supp() then . For example, supp( supp( and supp(.
If supp() then we use the first part. If there is some supp() then the result follows by an easy calculation illustrated by the following example:
The corollary follows.
Write () for (a set implementation of ordered pairs [18]).
Let atoms abstraction be []).
Intuitively [] is an -equivalence class of () where is abstracted, i.e. where we read () like ‘’ or ‘’:
[](() () () Write for for any . Then:
We can read ‘[]’ as the binding action of ‘’ or ‘’, and the sets above corresond 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.
Definition 16 agrees with the definition of [] from [16]:
[]( ()) #().
2.5 Further properties of support, finite sets, and -abstraction
1. supp( Ssupp() if is finite.
2. supp( supp() and if is finite then supp(.
3. supp(( supp() supp().
If is finite then supp() Ssupp() follows by Theorem 11.
Now suppose supp() for some . Choose some such that # and # for every . By Theorem 10 supp(())supp(). Since has no element such that supp(), we know that () and by Theorem 9 it must be that supp().
The second part is immediate; the third is by Definition 15.
supp([] supp() .
Thus we expect ()[]]:
()[]() () () ()
supp() Ssupp() need not necessarily hold if is not finite.
It suffices to give a counterexample; we give two: supp( but Ssupp() . supp( but Ssupp() .
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 range over distinct atoms, range over sets of atoms, range over all elements, and range over elements that are not atoms.
3.1 Axioms, naïve substitution action
A substitution action on FM set theory is a function [] expressed in the language of FM set theory taking an element , an atom , and an element , and returning an element which we write as [], satisfying:
If we read # as ‘ is not free in ’ and [] as ‘substitute for in ’ 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:
Define the naïve substitution action by
[[[[
Write and , and write 0 1 2 3.
Naïve substitution does not satisfy (), (#), or (abs), and so is not a substitution action in the sense of Definition 21.
It suffices to give counterexamples. We do this for (#) and (abs). We expect that [1] since #. We also expect that ([])[1]]([1]) since #1. But:
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
If is finite call () a plane in when
and supp(), and
is maximal in that for all where supp(),
Write plane() for the collection of planes in .
() is a plane in when is a least subset of supp() such that . For example:
1. () plane() and .
2. () plane() because .
3. () plane() because supp(.
4. ()plane() because and .
5. () plane() and .
6. () plane() and .
7. (()) plane([]) and ()() [] [].
8. plane(()
If is finite then define
(() plane() supp() supp()
We should think of () as the planes () in such that supp() ‘avoids name-clashes’ with . For example
() plane() but () plane()
The planes of ‘cover’ in the following sense:
If is finite then
As a corollary taking , S () 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() and let be some set of entirely fresh atoms (so disjoint from supp(), , , and supp()). Let ) ().
By Theorem 10 we can calculate that
Therefore supp() supp() . Also () by Lemma 13, so () (). Finally we note that ().
3.3 The substitution action, with examples
We can now define the substitution action. We use Lemma 26 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’.
If are finite then define
Define the substitution action [] and a ‘helper’ function () as follows:
[ and [, and
if then
We consider some examples.
1. []. There is one plane, ().
2. ()[]. One plane is () where # (the others give the same result).
3. []. One relevant plane is () where # (the others give the same result).
4.
One plane is (()) where # (if supp() then (()) ([])). We omit calculations showing that ()[); for a general result see Theorem 32 after these examples.
The other planes give the same result.
5. [] where for each . Two planes are (a plane for ) and (a plane for ). By calculations similar to the examples above, we calculate that
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((, so that
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, ( whereas [.
supp([]) supp()(supp()).
supp([]) supp()(supp()) need not necessarily hold.
A counterexample is [] above.
In the terminology of Definition 22, the substitution action is naïve on finite sets:
If and is finite then [[] .
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:
# if and only if for all () plane() it is the case that .
As a corollary supp( S () plane().
We may use this result in a slightly different form where we write instead of #; by part 2 of Lemma 18 these are equivalent.
By definition if () plane() then supp(). The left-to-right implication follows.
Now suppose that # for every () plane(). Choose any fresh #. By the first part of this result, # for every () plane(). Using part 1 of Lemma 26 we reason as follows:
Now supp(()) by Theorem 10 and the fact that #. The result follows.
For Theorem 36 we need a technical ‘capture-avoidance’ result:
Suppose that , , and is any element.
Suppose that is a finite set of fresh atoms (so # for 1 ). Then
Notice the on the far right subscript.
If (for all , if # then [))[]), then also (for all , if # then [))[]).
Choose fresh (so #; also # since by our permutative convention are distinct atoms). By assumption
[))[] (())[)())[]
The result follows by Theorem 9.
[] (())[] if #. As a corollary, for any if # then [))[].
We first prove the corollary. Suppose #; there are two cases depending on whether :
Suppose . Then there are three subcases:
(i)
(ii) . This contradicts # so there is nothing to prove.
(iii) (where ). [))[].
Suppose . By the first part, [] (())[]. Also by Theorem 10 #() and it follows that (())[] (()())[]. The result follows, since ()().
We now prove by -induction that [] (())[].
Suppose and #. By Lemma 35 we can assume #. Suppose the inductive hypothesis of every . We unpack the definition of substitution, using Lemma 34 to add a to the subscript on plane in the first equality (we cannot add to the subscript on plane in the second equality because we do not know #):
Suppose () (). To prove our set inclusion we exhibit () (()) such that
[](supp())() [](supp())()
We choose ) and ). By Theorem 3 we have () plane(()). Also by definition of () we know that
Now by Theorem 33 and supp() . Therefore #. It is now not hard to use Theorem 10 and some elementary set calculations to calculate that
So () (). Also since # by the inductive hypothesis [[].
It remains to show
(supp())())(supp())(())
Recall that . Then (supp())(supp()) is easily verified. Also
(() supp(())(supp())supp((())[])
Now supp(())(supp( supp()(supp()) is easily verified, and supp((())[ supp([]) follows by the inductive hypothesis. The result follows.
For all , if # then [.
If # then ([])[]([]).
If # then by Theorem 11 also #[] and
follow by Theorem 37. So suppose supp(). We sketch the rest of the proof: It is a fact that
The other planes add nothing to the final result. So
It suffices to verify that
(supp())(supp())(() supp([])
Now
(()supp())(supp())(supp([]))
(we use part 3 of Lemma 18 to calculate the support of a pairset). The result follows by set calculations.
[.
By an easy inductive argument which we sketch. The interesting case is of where we suppose [ for all (we adhere to our convention and write capital ). By definition
[ [([]) ()plane()
This easily simplifies using the inductive hypothesis to
and we use Lemma 26.
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.
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.
Let Λ be inductively defined by:
Λ is isomorphic to -terms up to -equivalence.
If Λ then [] Λ and [] is equal to what we usually call ‘capture-avoiding substitution of for in ’.
Define inl( 0) and inr( 1).
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:
This is not suitable for Theorem 43 because atoms are wrapped up in inl(inl()) and inl(inl())[ inl(inl()) . 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:
If # and Λ then
By induction on . Only the base case is interesting:
For more complex sets substitutions need not commute. That is:
There exist such that # and [][] [][[]].
[][]
(The planes of interest here are , , and .)
Intuitively, can be read as the predicate ‘is the variable , or is where is a variable other than ’; 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 representing the universe of discourse. The model also maps the variables x y of a first order language into the set of atoms. Now, if a first order sentence P is assigned the set as its semantic denotation, then the sentence xP has as its denotation the set T[] . This is more than just a translation of the syntactic substitution-for-all-terms operation into another language, for [] 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
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 and 2 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. ↩