A General Mathematics of Names
Abstract
We introduce FMG (Fraenkel-Mostowski Generalised) set theory, a generalisation of FM set theory which allows binding of infinitely many names instead of just finitely many names. We apply this generalisation to show how three presentations of syntax — de Bruijn indices, FM sets, and name-carrying syntax — have a relation generalising to all sets and not only sets of syntax trees. We also give syntax-free accounts of Barendregt representatives, scope extrusion, and other phenomena associated to -equivalence.
Our presentation uses a novel presentation based not on a theory but on a concrete model .
Key words: Set theory, Fraenkel-Mostowski set theory, NEW quantifier, nominal techniques, alpha-conversion, names.
Contents
1.3 Mathematical overview of FMG vs FM 5
2.2 Support and permutation acting on elements of 7
2.3 More complex elements of 9
Email address: murdoch.gabbay@gmail.com (Murdoch J. Gabbay).
1 I would like to thank Henk Barendregt, Antonino Salibra, and an anonymous referee. This work was done while at the École Polytechnique and INRIA in Paris, France.
Preprint submitted to Elsevier 18 February 2007
2.4 The quantifier, properties of , abstraction and concretion 12
4 The relation between name-carrying-, FM-, and de Bruijn syntax 17
5 -equivalence as a mathematical notion 21
5.3 Abstractive functions or, syntax-free “quotient by -equivalence” 24
5.4 Generalised and Barendregt representatives 27
6 The underlying theory of sets 33
6.1 Axioms 33
6.2 Lifting constructions in to the set theory 37
6.3 Abstractions commute with pairsets, powersets, and more 41
References 44
1 Introduction
1.1 Overview
This paper is about names and binding in infinitary syntax as an abstract set-theoretic notion.
In previous work [1,2] the author and Pitts introduced Fraenkel-Mostowski set theory (FM sets). This is a set theory in the style of Zermelo-Fraenkel sets (ZF sets [3,4]) in which we can build abstract syntax as inductively defined sets of abstract syntax trees. It is shown how in FM, a set-operation corresponding to quotienting by -equivalence (in case the set is of abstract syntax trees — identical to quotienting by -equivalence) can be defined on the entire set-universe.
Call a variable-symbol in object-level syntax (that’s the sets of abstract syntax trees we build in, say, a set theory), an atom. This is consistent with the original works [1,2].
Just like syntax has a notion of ‘variables occurring in’ and ‘variables occurring free in’, so FM sets has a notion of ‘atoms occurring in’ and ‘atoms occurring free in’, which is valid for all sets, not just those which happen to be inductively defined. We call the ‘free atoms’ of a set its support and write it S.
In the FM theory literature we have so far concentrated on support, swapping () (a notion of ‘rename as and vice versa’ in the support), and abstractions [] (a set-theoretic notion of -equivalence). These definitions are abstract, that is they apply to all sets, and this opened up the path not only to the algebraic structure of Nominal Sets, but also Nominal Domains 2 and much other work. We give a Nominal version of FMG sets in 6.4.
In FM S is always finite; a Fraenkel-Mostowski set has a finite supporting set. In fact, this is an axiom of the theory (axiom (Fresh) [2]). This made FM a semantics of finitary syntax — but without the syntax.
This is (at least in the opinion of the author) a fascinating and uniquely characteristic idea with rich structure. However, it does invite the question
“but what about infinitary syntax, which can mention infinitely many different atoms?”.
So read this paper, and enjoy our answer.
While we are at it, we take a step back from the original presentation of -equivalence in set theory and give a much more general treatment of the mathematics, even in the case of FM (finitary syntax). Notably, we generalise the Gabbay-Pitts quantifier, prove an important basic correctness result (a form of set-theoretic scope extrusion), and exploit our possibly infinite number of atoms to give interesting characterisation of ‘name-carrying’ and ‘de Bruijn’ syntax [6]. We discover that, while FM is based on atoms, FMG is based on well-orderable streams of distinct atoms. And last but not least, we propose a slogan ‘small=well-orderable’ which generalises the ‘small=finite’ of FM sets.
2 Published since this paper was submitted for publication [5].↩
1.2 Method of presentation
Presenting this work poses some unique problems. The mathematics is not simple (i.e. it is technical, in the way that any set-theory can be), and while we would maintain that FM techniques are no harder than anything else in modern theoretical computer science, this work will not be familiar to the reader unless they have studied previous work on FM ([1,2], and other publications).
Since we cannot be simple nor familiar, we do at least try to be concrete. Thus, we do not dive straight in to the language of FMG sets 3 and its axioms.
Instead, we start with a simple but (almost) completely sufficiently expressive fragment of the cumulative hierarchy model ([3,4]) of FMG sets. This allows us to:
Construct and explain FMG ideas in a concrete structure, using natural language.
Build directly in standard ZF (we use any sufficiently large set to interpret ).
In this paper, we begin by investigating all our significant constructions in a particular cumulative hierarchy , and then we generalise by stages until we are in full FMG.
The technical content of this paper, section by section, is as follows:
2: We define as a cumulative hierarchy and investigate its basic properties.
3: We construct sets describing name-carrying, de Bruijn [6], and FM syntax (that is, syntax-up-to-alpha-equivalence, in a sense which has been made formal [2] and will be made formal later in this paper) over a fixed but arbitrary signature .
4: We show they are all isomorphic.
5: We show that the isomorphisms generalise to all elements of (not just those which happen to represent abstract syntax trees for ).
6: We replace with full FMG sets. The constructions of the concrete model generalise and we show how.
Our voyage is therefore from what the reader most probably knows very well, namely operations on concrete syntax trees as occurs everywhere in the literature, to logical properties of a concrete cumulative set hierarchy, to logical provability in a first-order theory of FMG sets.
3 First-order logic [7,8] extended with a constant symbol called the set of atoms and a binary relation called set inclusion.↩
1.3 Mathematical overview of FMG vs FM
So just how does FMG differ from FM sets?
An axiom of FM states that every set has finite support, so in a suitable formal sense, we can say that a set of atoms is ‘small’ when it is finite. If is a predicate on atoms, we write () for ‘ is true for all but a small (finite) set of atoms’.
The slogan of FMG sets is ‘small’=‘well-orderable’. Thus in FMG sets a set of atoms is ‘small’ when there is a set which is a well-ordering of that set of atoms. If is a predicate () means ‘there exists a set of atoms and a set which is a well-ordering of , such that for all , () holds’.
FMG in its ‘vanilla’ form makes no committment to just how large the largest well-orderable set of atoms is; but we can add an axiom saying ‘well-orderable’ means ‘finite’, or ‘countably infinite’, or whatever we please. Thus, an observation of this paper is that the only property of finite sets which we really needed in FM, was that they are well-orderable.
The technical reason well-orderability is so useful, is simply that it is a convenient way of guaranteeing that for any two small sets of atoms, one of them injects into the other (from the property of ordinals that for any two ordinals treated as ordered structures, one of them is an initial segment of the other [4, Lemma 6.3]). This guarantees that there are enough functions between small sets of atoms that we can always rename them to be fresh, and as we shall see this will be very useful.
the concrete model where we start, takes ‘small’ to equal ‘countable’ (and ‘large’ to equal ‘uncountable’).
2 The universe
2.1 We build
Fix an uncountable set of atoms .
Call a permutation a bijection on . Define
Say has countable support when S is countable. Write for the set of permutations with countable support, which is a group under functional composition . Write Id for the identity element which is the identity function on atoms.
If write
We may drop the brackets and write Fix for Fix() without comment. Say Fix fixes pointwise.
(1) S is the least such that Fix().
(2) Fix if and only if S.
(3) Fix is a group.
The proofs are by basic group-theoretic calculations.
Write () for the set of countable subsets of .
We inductively define a set of elements , a permutation action which we write , and a function support which we write S. (The notation clash with S is deliberate; the values of the two functions will turn out to be identical.)
(1) is an element.
(2) () is an element.
Note that can encode tuples as (this is the standard set-theoretic encoding [4]).
(3) If and are elements then the abstraction
is an element.
Write arbitrary elements of as , arbitrary atoms , arbitrary countable sets and arbitrary abstractions .
In summary, any element of has precisely one of the following three forms:
an atom ,
a countable collection , or
an abstraction [].
Write
(1) # when S S.
(2) # when S S. Unfolding definitions, this is equivalent to Fix(S).
For two distinct atoms and write () for the permutation mapping to , to , and to . This is a swapping.
Then ()# is false and ()# is true, ()# is false (we assume are all distinct). ()#[] is true, but ()#[] is false. #[] and #[] are both true; #
2.2 Support and permutation acting on elements of
We prove some simple lemmas:
Suppose is a countable set of atoms. Then:
(1)
(2)
(1) is a countable set, and the permutation action is defined to be pointwise.
(2) is a countable set, so SS. We now observe that by definition S
2
(1) If then S.
(2)
(3) #[].
(4) If # then (# is logically equivalent to FixS).
(5) If ( for all S then .
(1) Proof by induction on ; since always it suffices to show that S is countable.
is countable.
Any countable union of countable sets is necessarily countable.
Any subset of a countable set is necessarily countable.
(2) Proof by induction on .
S S and we can use the inductive hypothesis.
(SSS)(S) and again we use the inductive hypothesis.
(3) Unpacking definitions.
(4) By induction on .
# when ( and we recall that
# when # for each and we use the inductive hypothesis.
We observe that
We note that S() S( (S S S S, and also recall that Fix(S S) is a group. By group-theoretic calculations it follows that:
Here is ‘morally’ .
(5) This is a corollary of the last part, observing that (() for all S precisely when Fix(S), and this is logically equivalent to asserting #.
2
Note that does not imply #. For example S( and (() is a swapping, defined at the end of 2.1).
([]) is defined componentwise as []. Also, is defined pointwise. Is it possible for the componentwise action on [] to conflict with the pointwise action on it as some ?
In fact this question does not arise since [] is uncountable and according to our definitions must be countable.
However, it is easy to prove that the two collections are equal anyway:
The componentwise and pointwise actions agree for abstractions:
We must show that for any ,
We use the notation below and observe that , and Fix(S S) if and only if Fix(S S). Finally we note, as we noted before, that Fix(S S) is a group. The result now follows by group-theoretic calculations. 2
As a matter of notation write (the conjugation of by [9]). It is easy to calculate that maps to if and only if maps () to (); in particular, Fix if and only if Fix().
For example, if , , are distinct atoms then []], []] and [][]][]. These reprise well-known -equivalences in (say) the -calculus and logic (but without the -calculus and logic; equality on abstractions is precisely -equivalence, in a suitable formal sense which we analyse in depth in the rest of this paper).
2.3 More complex elements of
Just that is closed under countable subsets already gives it considerable power. For example it contains:
(1) The natural numbers encoded as 0 , and .
(2) A two-element set encoded as 0 1.
(3) Ordered pairs (as we already noted)
Given ( and need not necessarily be countable, and not necessarily be elements of ) write
This is of course the standard notion of cartesian product.
(4) Disjoint sums
Given write
(5) Finite lists [] encoded as nested pairs. Given write -list for the set of lists with elements in .
(6) Countable streams ] encoded as countable sets of finite lists of initial segments. Given write -stream for the collection of countable streams of elements in .
The details of the encodings are irrelevant; it is only important that they exist.
Call an arbitrary subset a class or a collection (as we did above). This need not be an element of , and if we know for a fact that it is not, call it a proper class. By construction of , a class is a proper class precisely when it is uncountable and not equal to [] for some .
If is a finite list or a stream, we may write () for and () for [], where these are defined. (We mostly use this notation much later on in this paper, to the particular case of a stream of distinct atoms which we define below.)
We briefly consider the permutation action and support of these constructs:
For all the constructs above, permutation acts componentwise and the support of the whole is the set union of the supports of the components. For example, always and S, and
and similarly for pairs and finite lists.
For numbers, we work by induction on their construction, recalling that acts pointwise on sets (so , for example) and S takes the union of S for all . These observations, along with some concrete calculations, prove the rest of the result for tuples, finite lists, and finally for streams. 2
Proper classes with respect to which are of particular interest are
(1) the set of atoms.
(2) , which we now define.
Write for the set of countable streams of distinct atoms, that is, streams ] such that implies and for all .
Suppose ] . Then:
(1) .
(2) The permutation action is pointwise on the , that is, ].
(3)
Also, is a proper class ().
For the first parts, the proofs are as for Lemma 5. is a proper class since it is uncountable (and, we can check it is not an abstraction [] for any elements and ). 2
Note that for , S is infinite but countable. 4 Two uses of are: to help model infinite behaviour in the presence of name-generation (so might be a countable list of ‘generated’ names); and to help model of infinitary syntax.
behaves like a ‘big atom’. For example has a kind of permutation action:
(1) Given ]] , if # then () is well-defined, where ()( and ()( and otherwise ()(.
(2) For and as in the first part, if # does not hold then () is not necessarily well-defined.
(1) We just defined it.
(2) Consider and (). Then maps to , and maps to both and .
2
4 . . . so it can never exist in FM sets, where everything has finite support.↩
2.4 The quantifier, properties of , abstraction and concretion
If is countable it follows that is uncountable, and we can choose a such that #. We say is fresh for . We use this without comment henceforth.
We may also just say ‘choose a fresh ’, meaning that should be fresh for the union of the supports of whatever elements are under consideration at that particular moment. This would be meaningless if we intend to be fresh for a proper class of , but we will never do this.
If then S is a singleton, which is very countable. Thus we can always choose a fresh .
Given some : write for the unique value of at all but countably many , if this exists.
Similarly for : write for the unique value of at all # for some countable , if this exists.
Given some a predicate on write ‘() is true’ (or just ‘()’) if is true for all atoms except for the elements of some countable , and ‘() is false’ if is false for all atoms except for the elements of some countable .
Similarly for a predicate on , write ‘ is true’ or just when is true of all such that #, for some countable , and so on.
The canonical examples are:
is not well-defined, but is well-defined and has value [] ].
is false, and is true.
Let be a set containing uncountably many atoms, and not containing uncountably many atoms. Then is not defined.
In practice is usually well-defined, because will be something we specified using a sentence in natural language or mathematical formalism, parameterised over some finite set of elements of each of which has countable support; so should be either uniformly true or false away from that support. This informal argument becomes formal in FMG sets, both internally (abstractive functions in 5.3 and generalised for them 5.4), and externally (equivariance Theorem 35).
The following result is the main reason that and are so important, we shall need it for later:
(1) is the graph of a partial function defined precisely on
those such that or # (or equivalently; such that #[]), with value () where defined.
(2) is the graph of a partial function defined precisely on #S S (or equivalently; such that #[]), with value () () .
We note that by definition, #[] when # or , and similarly #[] when #S S.
(1) Expanding definitions,
The first component () can assume any # or , since () Fix(S) for these .
It remains to show this is functional, i.e. if ( and Fix(S). But then and agree on S and the result follows from the last part of Lemma 3.
(2) Expanding definitions,
First we show this is functional: suppose Fix(S S) and . By the technical lemma below and Lemma 6, (() for every S. Functionality follows.
We now just need to show that for every #S S, there is some Fix(SS) such that . Choose some fresh (taking # suffices) and set ) ().
2
(Technical Lemma) Suppose ] . If then ( for every .
Lemma 6 proves the permutation action is pointwise. The result is immediate. 2
We shall write abstractions as , . We write the value or concretion of at some or , when this is defined, as @ or @ respectively.
The terminology ‘concretion’ is consistent with existing terminology in the FM literature [2, Definition 5.3].
Concretion is very useful for specifying functions, since it allows us to ‘choose the name of the bound variable’. We will use it heavily later.
(1) [@ when is an abstraction by an atom and @ is defined, and ([])@.
(2) [@ when is an abstraction by an element of and @ is defined, and ([])@.
(1) Suppose ]. By Lemma 8@) and it must be the case that . By definition
We then use the fourth part of Lemma 3, recalling that by definition #[] and that #[].
We also observe that () , so using the previous result
(2) Suppose ]. By Lemma 8@) and it must be the case that . By definitions
We then use the fourth part of Lemma 3.
2
3 Inductive datatypes
Recall from 2.3 the definitions of cartesian products , disjoint sums , lists -list, the set of natural numbers , the classes of atoms and countable streams of distinct atoms and , and so on (for any classes ).
Also write
Fix a countably infinite collection of class variable symbols , , , and so on. Then expressions of a simple class specification grammar are defined by:
Say is closed when it has no class variables. A closed denotes an actual class ⟦⟧ in a natural way. For example:
⟦, where is defined in 2.3.
⟦⟧, where + is defined in 2.3.
⟦[]⟧] ⟦⟧ (in this paper we shall only really consider ).
and so on.
Say is a signature in when it mentions at most one class variable, and that variable is . We abuse notation and write for a signature in . Given and write for a signature obtained by substituting for in . For example, ()(-list)-list) (-list).
Say permutation acts trivially on when for all . Given a class , which may be countable and thus itself an element of , say has a trivial permutation action when permutation acts trivially on every element of .
If has a trivial permutation action then [] and is a canonical way.
We consider just []; the case of [] is similar. Map to @ for any , and to [] for any . This is well-defined by Lemma 10 and the fact that permutation acts trivially on and @. 2
We need some notation: if say is equivariant when
Much more on this later in 5.1.
(1) and are equivariant.
(2) If and are equivariant, so are , , , and -list (and so on).
(1) If then , since a permutation does map atoms to atoms. The result follows since is also a group. If then the permutation action is trivial (that is, for all ) and the result is easy to prove.
(2) All results are by simple calculations. We only give one. Suppose and . Then
2
Equivariant classes are easier to work with — we know we can rename atoms without moving out of the class, see also Lemma 14 below — and sufficient to model syntax-with-binding as we are in the process of demonstrating. All classes are assumed equivariant unless stated otherwise.
For some equivariant write for the class denoted by interpreted according to the list above, where we additionally take to denote .
A signature induces a class ( for ‘initial’) which is the least class such that () .
Write and (). can be constructed as in a standard way (see [10] or [1, Section 10]). We briefly look at the only unusual aspect of this construction, which is FM(G) abstraction (it turns out to be quite easy):
Suppose . Then:
(1) [] : Suppose [] [] . Then for some and , so
(2) [] : Similarly.
2
Call an inductively defined datatype. The expression determines its constructors.
Three signatures are of particular interest to us by way of prototypical examples:
is an inductive datatype of terms of the -calculus without -equivalence. is an FM datatype of terms up to -equivalence =; the lemma
is easy to prove by induction, but we leave that for which we construct in the next section. is a de Bruijn datatype for -terms in the style of the seminal implementation of abstract syntax up to -equivalence in Automath [6] by de Bruijn and others.
The next section discusses the relationships between these signatures in detail.
We recently mentioned that equivariant classes are easier to work with. Here is another reason (known already for FM [1,2]):
(1) If is equivariant and [] then @ for any , where @ is well-defined.
(2) If is not equivariant then there may be [] such that @ is well-defined and not in .
Similarly for .
(1) If then by construction ] for some and . By Lemma 10 @) where this is defined, and by equivariance this is in .
(2) It suffices to provide a counterexample. Let
The case of [] is similar. 2
Thus if we want to use classes as a sorting system for constructing abstract syntax trees (and we do) we had best use equivariant classes, since otherwise we cannot concrete an abstraction, i.e. ‘choose a name for the abstracted variable name’ at any atom for which the concretion is defined.
4 The relation between name-carrying-, FM-, and de Bruijn syntax
Call a simple signature when all its abstractions are of the form []-. The examples of (4) are all simple.
Given a simple signature, for example ], we derive two other signatures from it as follows:
(1) the name-carrying version is with every abstraction replaced by -. For example .
(2) the de Bruijn version is with every abstraction replaced by -, and every instance of replaced by . For example .
These give rise to three inductively defined sets of abstract syntax , , and .
We now define functions and
as follows:
To define , which is out of an inductively defined set, it suffices to define the action of on its components. We let be the identity except on components where has [] (so that has ), in which case is the abstraction function .
For example : is defined as follows:
() (of course the leftmost is a term-former of and the rightmost is a term-former of ).
We define
where is defined on as follows:
() if , and () otherwise.
It is easy to inductively characterise the kernel of on :
(1) .
(2) and implies .
(3) () () implies .
A few examples suffice to convince us that the kernel of is the relation which we would naturally call -equivalence.
is defined as () where is defined as before. We also state what to do with countable powersets:
: described above is an isomorphism.
It suffices to exhibit the following isomorphisms and observe that is obtained by applying them repeatedly left-to-right. We only do the first part:
So distributes the abstraction []- down until it reaches , at which point we obtain .
We consider a selection of cases:
(1) The case .
The functions could also be written informally as [][]
However, proving this now would be hard; best to wait for later when in FMG sets we will have powerful results about (Corollary 39 and Theorem 35). For full proofs, see Theorem 42.
(2) The case . The functions are given by @) and . See Lemma 11.
(Note that for some , so @@ for any and and @) is well-defined.)
(3) The case of is similar; indeed, the result holds for any set all of whose elements have the trivial permutation action.
(4) The case
It is worth discussing this in a little detail.
Suppose we have : [](). Choose # ; we know @ is well-defined and is a countable set of elements of . We also know that #[] for any @ and so that # @. So the map above is well-defined (it does not depend on which # we choose).
Now suppose we have : ([]). This is a countable collection of elements so the support of is the union of the support of its elements; choose some such that for all ; in particular @ is well-defined for all . We know that #[] @, so the map above is well-defined (it does not depend on which we choose).
(5) The case .
So [] corresponds to if for some and to otherwise.
(6) The case . The functions are given by
This function is clearly a de Bruijn shift; the bound atom in [][] is pushed onto the head of the list of bound atoms, which is shifted up. Take . Then for example [][] maps to [ :: ]].
2
We notice that is not quite a de Bruijn datatype because it can have both dangling unbound atoms and unbound indices. Consider as constructed above; then 7 and are both terms. Generally we allow only one or the other. A little extra notation solves the problem:
Given a class write
Then we can prove by induction that Γ(). We have recovered a bona-fide de Bruijn datatype. Γ[] consists of elements of with free atoms bound in order. restricts to an isomorphism between Γ[] and Γ(), using an informal notation.
Infinitary syntax: There are various directions in which the signature (and its interpretation in ) may be made infinitary. We can extend signatures with -streams, which in are interpreted by countably infinite streams (also called lazy lists) and which give rise to sets of abstract syntax with infinitely broad branching. We can add just -streams, which permits syntax to mention infinite lists of atoms. We can add [], which permits syntax to contain bindings by infinite lists of distinct atoms.
Our results carry through to these extensions. Furthermore in the rest of this paper we extend our theory powerfully to sets not necessarily of abstract syntax trees, and which in full FMG may be much larger and more complex than anything contained in .
5 -equivalence as a mathematical notion
We have related different kinds of inductive datatype for syntax, using datatypes of abstract syntax constructed in by means of proofs based on induction on the signatures defining the datatypes. This made things nice and concrete, but it ties us to a concrete notion of signature and to working only on sets which happen to be abstract syntax trees.
We can do better: we can jettison both the signatures and their sets of abstract syntax trees, and define useful functions on general elements with no assumption of inductive structure. We call this type of reasoning ‘syntax-free’.
5.1 Equivariance
Recall that was defined with an inherently ‘syntax-free’ notion of ‘free names of ’ given by S. When S, ‘mentions no names’.
Because this is an important property we give it a fancy name: say is equivariant when S.
We introduced a notion of ‘equivariance’ in 3, for classes (not elements) of . The two notions coincide in a suitable sense:
(1) is equivariant precisely when .
(2) is equivariant precisely when .
The second part follows from the first, for suppose always and . Recall that . Then obviously . Suppose conversely implies . Then . But note that is a group, so that () and .
Now we prove the first part. Suppose is equivariant. Then # always, and by the fourth part of Lemma 3, . Now suppose always. Then by the second part of Lemma 3, S S always, and the only way this can happen is if S. 2
Call a function equivariant when for all and , is defined and
Suppose is the graph of a function. Then S if and only if always — that is, the two notions of equivariance just described, agree where they overlap.
Suppose . Then
Suppose . Then we read ( directly off the equation above. Conversely suppose is always defined and (). Then . Thus is defined at , and ( as required.
2
If is injective (and thus bijective between and ) then is equivariant if and only if is equivariant.
Choose some . Then and (.
2
How does the support of relate to the support of ?
(1) If is equivariant then S S and Fix(S) Fix(S) always.
(2) If is equivariant and injective then S S.
(3) If () is equivariant and injective, then S( S S.
(1) Suppose is equivariant, so () always. Using Lemma 3 it is also the case that S S(). Now if #S (that is, if Fix(S)) then so S S. Since this is valid for any #S, it must be that S S.
(2) Direct from the first part of this lemma, and by the previous result.
(3) Suppose ((). By the various properties we assumed, this happens precisely when and . The result follows.
2
It is generally useful to assume a function is equivariant: if not we parameterise until we obtain one that is.
A fundamental theorem of model theory is that if we systematically permute the underlying sets of a model, we obtain a new model in a natural way. Thus we know from very general principles [11] that all functions, if sufficiently parameterised, must be equivariant.
5.2 A word on support
The reader familiar with FM theory will no doubt recall that support has another characterisation in terms of freshness and . This is indeed the case here:
(1) # if and only if () (‘ is not in precisely when if we rename it to be a fresh , nothing happens’).
(2) # if and only if () (‘ is not in precisely when if we rename it to be a fresh , nothing happens’). .
(3) As a corollary of part 1, is equivariant precisely when #.
(4) As a corollary of part 2, is equivariant precisely when #.
(1) Suppose () . By part 2 of Lemma 3, also () S S. Since S is countable and all but countably many satisfy S, it follows by elementary properties of sets and part 1 of Lemma 2 that S.
Conversely suppose S. Then for each S it is the case that () by part 4 of Lemma 3. The result follows.
(2) Suppose () . That means that there is some countable set such that for all #, () . By part 2 of Lemma 6 we know S, and by part 2 of Lemma 2 S. Since all sets concerned are countable and is uncountable, there is one (actually uncountably many) # such that (). By part 2 of Lemma 3 also () S S and it follows by part 1 of Lemma 2 that #.
Conversely suppose #S. By part 3 of Lemma 6, S and we can use that part again along with part 4 of Lemma 3 to verify that for any other #S we have () . The result follows.
(3,4) Left-to-right is immediate since it follows that S. Right-to-left follows since the intersection of any set with the empty set, is empty.
2
Strictly as an aside for the reader who is not surprised by part 3 of the result above, because they have seen it in FM, we now show that is in fact rather special and that in full FMG we cannot take this result for granted.
Define an elementwise permutation action on uncountable sets as and let # be defined as above by () (as is the case in FM). Then we semi-formally (because we have not defined FMG) state:
Part 3 of Lemma 20 fails in full FMG; there exist and such that # is true, but is false.
(Of course we have not yet defined FMG set theory, but being a set theory of significant expressive power, it includes uncountable sets and in particular the ones we construct in the proof below.)
Choose any and define
S is finite
(Recall that S being finite is equivalent to ( holding for all but finitely many atoms. The canonical example of such a is (), and the canonical example of a which is not so is () for some #.)
We can easily verify that # for any , but also for any fresh # it is the case that () . 2
In fact, on of our reasons for considering is that we can build and investigate and in it, and still have part 1 of Lemma 20. We return to this issue later in 6.2 (fuzzy support in FMG sets); a suitable version of part 4 of Lemma 20 remains valid, see Lemma 43.
First, we return to because even without fuzzy support, it is by no means without novelty. . .
5.3 Abstractive functions or, syntax-free “quotient by -equivalence”
Call an equivariant function purely abstractive when
Write Id : for the identity function mapping to itself. Later it will be useful to write for Id restricted to being a partial function on some .
(1) Id is abstractive.
(2) The abstraction function : is purely abstractive.
(3) The unique function ! from to the unit set is purely abstractive.
(4) The tail-of and head-of functions : and : are purely abstractive.
(5) The ‘remove atom’ function defined for (), is purely abstractive.
(6) The tail-of and head-of functions : -stream -stream and : -stream are not purely abstractive.
(1) If Id Id then and we take equal to Id (the identity permutation; we shall always make it clear which Id we mean).
(2) Suppose []]. Choose some fresh #. Then []@ () ) ] by Lemma 8. It follows using Lemma 3 that () () (), and we observe by calculations that () () FixS([]).
(3) Suppose !. Well, that always happens, and S so it suffices to observe that () .
(4) Suppose ((). By definitions we know that ()#() and ()#(), so (
Suppose ((). Choose some #. Then observe that (()) ()) . It follows by calculations that ()) (()) , and (()) (())#
(5) Suppose . Choose some fresh # and observe that () () (). The result follows similarly to the case for abstractions.
(6) It suffices to provide a counterexample. Consider ] and ]. Then (() but there is no such that . Similarly consider and ]. Then (() but there is no such that .
2
We shall assume basic properties of permutations, freshness, and support (most notably Lemma 3) without comment henceforth.
from (5) is not purely abstractive in general. For the example of and , observe that (() but no exists to make them equal.
This example motivates the following definition:
Call Barendregt abstractive when for every in () there is a unique Fix(S)-orbit in whose support has maximal cardinality. Call an element of this orbit a Barendregt representative.
(1) 1 is Barendregt abstractive with a Barendregt representative for (any) .
(2) 1 is not Barendregt abstractive because Inl and Inr both
map to and are not related by a permutation .
(3) from 4 is Barendregt abstractive. A Barendregt representative of is .
By simple calculations. A -term satisfying the Barendregt variable convention [12] (that all bound variable names be distinct from each other and from the free variable names) is precisely what we here call a Barendregt representative. 2
It may be useful to recall that . However — all these expressions map to the same element under .
Given classes and : and : , write : and : for the obvious functions on products and sums. For convenience, write Inl
Continue the notation just established. Then:
(1) If and are purely/Barendregt abstractive then mapping Inl to Inl() and Inr to Inr() is purely/Barendregt abstractive.
(2) If and are purely/Barendregt abstractive then mapping
(3) The map is Barendregt abstractive.
As a corollary, the usual -equivalence quotient on inductive syntax is Barendregt abstractive.
(1) The Barendregt representative of Inl() is , similarly for .
(2) We consider just the case of products. Given let and be Barendregt representatives. Let be a permutation in FixS mapping any difference between S and S to some fresh set of atoms, and similarly let FixS map S S to some other fresh set of atoms. The Barendregt representative of is .
If we accept that the usual -equivalence quotient on inductive syntax is the identity on most components, and the abstraction function on where appropriate, then the result follows by induction on the datatype. 2
Second projection on a pair whose first element is in , write this , is Barendregt abstractive. Similarly for second projection on a pair whose first element is in .
Combining the previous theorem with the observations about ! which precede it. The Barendregt representatives are tuples such that #. 2
(Recall that # means S.)
There is a simple connection between Barendregt abstractive and purely abstractive functions:
A Barendregt abstractive map gives rise to a purely abstractive map on the subset of its domain consisting of elements with support of maximal cardinality.
By unpacking definitions. 2
So results of purely abstractive functions can usually be extended to ones of Barendregt abstractive functions, modulo the ‘junk’ of non-Barendregt representatives. Purely abstractive functions are a little easier to work with, so we may prefer to consider them, but this is just for convenience unless stated otherwise.
Something quite similar to all this is discussed (in the framework of ZF sets) in well-known work by McKinna and Pollack [13]. The apparatus of abstractive functions can be viewed as an abstract account of a phenomenon of which an instance is treated in [13] as a concrete methodology.
We have defined a new abstract class of functions and shown that a concrete class of functions are a subset of them. Barendregt abstraction corresponds to ‘quotient by -equivalence’.
For this to be most useful, we need a notion of ‘pick a representative’.
5.4 Generalised and Barendregt representatives
Suppose is a purely abstractive equivariant function and suppose is another equivariant function with ((). Write
We argued in the previous subsection that is a general -equivalence quotient map. We shall now show that is the condition ‘ respects ()--equivalence’.
(If is Barendregt abstractive, the result still holds, modulo the ‘junk’ of non-Barendregt representatives in ().)
Suppose we have as in the statement of the theorem. We now define : choose any and pick a representative of , that is, some () such that .
Let () .
We must show this is well-defined. So suppose is any other element such that . By the purely abstractive property there exists FixS such that . By equivariance of we know . Also by we know S S S and so FixS FixS. So FixS so by Lemma 19 we know as required.
The reverse map is given by composition: given such that ( the corresponding is .
It remains to show that these maps are inverse, that is
(1) For any , by definition ()(() for some such that (). Since is assumed purely abstractive, there is some # such that . But since also #. So .
(2) For any , by definition ()()() for some such that . So this is just .
2
If () is a two-element set we can interpret it as truth values. We may use this result for predicates without comment.
For example:
There is a 1-1 correspondence between maps out of such that
#() always, and maps out of []. This is a known principle of FM techniques [2, Lemma 6.3].
If # (restricted to those and such that #) and then is the (always true) function #. This is the known axiom (Fresh) [2, page 8].
There is a 1-1 correspondence between maps out of such that #(), and maps out of [].
. . . and so on.
The construction above is useful because it systematises the treatment of choosing representatives and calculating on them, also for sets which may be much more complicated than products and projections.
We made a simplifying assumption that , , and be all equivariant. This becomes false the moment they are parameterised over , which may contain atoms. Those parameters can simply be incorprated into the arguments, or (if the reader likes) they can verify that the proofs above do generalise to this more general situation.
5.5 Freshness
We observed in the last subsection that:
(1) ! : 1 is purely abstractive and
(2) is Barendregt abstractive.
The corresponding generalised quantifier and are the well-known FM -quantifier, choosing a fresh atom (for a parameter ).
In the rest of this section we concentrate on !: 1. In fact is more useful in practice because there the atom is chosen fresh for a parameter; the arguments below will (obviously) work for as well, just with a small overhead of writing ‘’ everywhere which we prefer to avoid.
For what sets of does () have proper meaning?
! : 1 is purely abstractive if and only if for all there exists such that .
Suppose ! is purely abstractive. S and Fix. Also !() always. Unpacking definitions, for all and there is some such that .
Conversely suppose for all and that there is some such that . Clearly this validates the condition for ! to be purely abstractive. 2
Thus ! above is purely abstractive when consists of a single orbit under .
We shall write () for , and we say that has a -quantifier. In fact it suffices for ! : 1 to be Barendregt abstractive (e.g. ), but then we can restrict attention to the elements of maximal support in (e.g. , see below) from which generalised chooses its representative. On this subset ! is purely abstractive, thus the situation of the theorem above is indeed canonical and useful.
We now show that satisfies this condition. Recall that is a countably infinite stream of distinct atoms.
For all there is a such that .
is given by () () for any #. 2
(Recall # means and for all . Recall from Lemma 7 cannot just use ().)
and are minimal and maximal sets for which a -quantifier exists, in the following sense:
If is equivariant and such that for there always exists some with , then is a quotient of under some subgroup of .
Pick any . This has countable support, so put the atoms in that support in some order and, if the set is finite, pad it with countably many distinct fresh atoms. Write this stream and declare (. It is not hard to verify that provided is equivariant then is well-defined and surjective, and that its kernel is a subgroup of . 2
(Recall we stated we would only be concerned with equivariant classes, in 3.)
We used this technology to study the -calculus [14] and models of process calculi with dynamic allocation [15]. FreshML is based on a universe with finite support, so does not appear; in a lazy programming version based on a language such as Haskell, might be useful for foundations.
A benefit of these FM(G) techniques is that they not only account for binding in the syntax, but also in the semantics, which may very well include functions and consider infinite behaviour with infinite allocation of names and thus binding by or variants of it. 5
5 A variant of this not using was developed and applied by Shinwell and Pitts to give semantics to FreshML, see [5].↩
5.6 Scope extrusion for
Generalised exhibits generalised scope-extrusion. This is the characteristic property of most notions of freshness, that if we choose a fresh name in some context, we can also choose ‘fresher’ for a wider context.
Here the annotating the arrows actually are the identity . We use this notation without comment henceforth. , as before, denotes function composition.
The proof is just by unpacking definitions. Since these have accumulated we give the process in a little detail.
The conditions on domains and images just ensure that all functions are well-defined.
() when for all and , S() S. By Lemma 19 we know S S S. Since is equivariant we know by Lemma 19 that S() S S, and we are done. Therefore the functions in question are well-defined.
Now () is the value () at any such that and has maximal support. ()() is the value of () at any such that and has maximal support and such that S S is minimal. In particular and we are done. 2
When we work with representatives we do not worry about generating names fresh for all possible contexts: this is impossible since we do not know a priori what atoms those contexts may contain.
So the above tells us what we always knew; that it does not matter because we can always extrude the scope of our choice of fresh name ad hoc. It is not unusual to see results of the form “() and []() are equivalent up to bisimilarity” (this example is of course taken from the -calculus and we have written instead of to connect the notation to the theorem above). Usually such results are proved on a case-by-case equivalence-by-equivalence basis, perhaps one day they might be stated as ‘general nonsense’ consequences of theorems like the ones above.
The following lemma is useful in Theorem 42, and we also used it ‘secretly’ when we informally wrote some isomorphisms in Theorem 15.
By the properties of we know it does not matter which Barendregt representatives we use. So suppose we used the representative () to calculate ( so that #. Then # and we can use () to calculate (). The result follows. 2
any function-class, any predicate defined in the logic of FMG. () is a predicate expressing that there exists a set which is a well-ordering of .
6 The underlying theory of sets
6.1 Axioms
FMG sets is a set theory similar to the original FM sets [1], but considerably more general. So far we have worked in , a concrete model which is an initial fragment of a standard cumulative hierarchy model of FMG. We now define the theory.
The logic of FMG sets is First-Order Logic [7,8] with a constant symbol the set of atoms and a binary predicate set inclusion.
The axioms of FMG sets are given in Figure 1.
First we make some comments on notation and our choice of axioms:
We write () for the powerset of and () for the predicate “there exists a set which is a well-ordering of the elements of ”.
A well-ordering is a well-founded trichotomous relation. A relation is trichotomous when for all , precisely one of , , or holds. A relation is well-founded when there exist no infinite strictly descending chains. The canonical example of a well-ordering is the numerical ‘less than or equal’ relation on natural numbers 0 1. This ceases to be
well-founded if we add negative numbers, and is not trichotomous if we move to the complex integers , ordered by the size of their modulous.
In (Extensionality), (Union), and (Powerset) we could use in the axioms, but the system is equivalent.
In the case of (Extensionality) this is by the rules of equality in first-order logic.
In the cases of (Union) and (Powerset) we can use the axioms as stated to deduce that some set containing the union or powerset, and then use (Collection) to deduce that the collection which is the union or powerset, is a set.
It is a general fact about this style of axiomatisation of set theory that the impact of most axioms is just to ensure that there are enough sets around; (Collection) then puts on the final touches, so to speak.
Where does FMG stand with respect to FM sets?
FM sets has a notion of a ‘small set of atoms’. The quantifier means precisely ‘for all but a small set of atoms, . . . ’.
Originally [1,16] ‘small’ was equal to ‘finite’. We also took to be countably infinite, so the () means ‘for countably many , ()’. It was folklore that we could just have well have taken to be uncountable; the important point was what we might call the ‘size of small’.
took ‘small’ to mean ‘countably infinite’. Of course we also insist be uncountable, so that is not degenerate.
FMG set theory generalises this further to:
‘small’ means ‘internally well-orderable’.
This is very nice because (rather unexpectedly, perhaps) it makes no commitment to actual size; FMG sets is consistent with any of the following axioms: “Small is finite”, “small is countable”, and “small is ” (here is the first uncountable ordinal).
If we add the first as an axiom in FMG sets we recover FM sets. The second possibility gives a set theory suitable for containing in its standard cumulative hierarchy model. Further possibilities give theories with increasingly large small sets of atoms. Or, we can add no extra axiom and consider FMG with no further assumptions.
As we mentioned in the Introduction, ‘small equals well-orderable’ seems the right choice, because it gives enough isomorphisms to rename atoms:
For any two well-orderable sets and , one is in bijection with a subset of the other.
See [4, Lemma 6.3]. 2
We obtain permutations from these injections and we can use them to rename atoms to be fresh. This turns out in practice to be the property we need a small set to satisfy: that the set can always be renamed to be fresh (and the property of a large set is that this is not the case).
Write ZF for Zermelo-Fraenkel set theory (a classic mathematical foundation [3,4]).
FMG set theory is consistent relative to ZF. In addition, for any ordinal FMG set theory with an additional axiom ‘small is ’ is consistent relative to ZF.
The first part is a corollary of the second, so we concentrate on the second part.
FMG is just a theory in first-order logic (whose axioms are presented for the delectation of future generations in Figure 1). To prove consistency of any theory in first-order logic it suffices to exhibit a model. Because of fundamental limits to logic [17, Proposition VI] a model, i.e. consistency, cannot be exhibited in any absolute sense, but only relative to assuming the consistency, i.e. the existence of a model, of another theory.
So suppose we have a model of Zermelo-Fraenkel set theory. We construct a cumulative hierarchy model of FMG set theory (with ‘small = countable’; the generalisation to any is very easy) as a subclass of the elements of that model. This suffices to prove relative consistency. We only sketch the construction, since this is an entirely standard method found often in the literature [18,19].
Choose any uncountable ZF set for . Define a hierarchy of increasing subclasses by:
(1)
(2) is the set of subsets of with small support, union with .
A set has small support when there exists a countable set of atoms such that if Fix then .
Then the model of FMG is , the union of the . Set-membership in the model is interpreted by set-membership in .
The proof that this is a model of the axioms of FMG sets given in Figure 1 is long but routine. We only sketch it here:
(1) (Sets) is valid by construction; everything in is an atom or a set of (sets of (sets of . . . )) sets of atoms.
(2) (Extensionality) is inherited from ZF.
(3) (Collection) is proved by induction on the size of , a formula in the logic of FMG (the same logic in which the axioms are expressed).
(4) (-Induction) is by the inductive nature of the construction.
(5) (Replacement) is inherited from ZF.
(6) (Pairset) and (Union) likewise.
(7) (Powerset) is inherited from ZF, bearing in mind that we only take the sets with countable support.
(8) (Infinity) is inherited from ZF.
(9) (AtmLrg) is by the fact that any set encoding a well-ordering of is invariant only under the identity permutation on .
(10) (Fresh) by the construction of the cumulative hierarchy, which only takes sets with small support.
2
In the presence of an axiom that ‘small’ is (at least) ‘countable’ we can interpret in this cumulative hierarchy and abstractions, as promised, are implementable as the collection defined in 2.1, which is now also a set.
The permutation action is defined by -induction starting at atoms and pointwise on sets, thus:
The following result corresponds in FMG to the same result in FM (see for example [2, Lemma 4.7] and [20, Proposition 2]):
(Equivariance) (1) If () is a predicate in FMG then
is always provable.
(2) If () is a function-class specified in FMG then
(1) By induction on the language of FMG (just like the similar result for FM [1,2]). The important base cases are and if and only if by the pointwise definition of permutation.
(2) A function-class is merely a predicate specifying its graph. We use the first part to deduce
and the result follows immediately.
2
In words:
Any predicate specified in (the logic of) FMG sets is equivariant over its arguments, and so is any function-class.
FMG set theory is a set theory so models of FMG sets are closed under powersets, not just countable powersets as was (nota bene: FMG powersets do not take all the subsets of the ambient foundation, only those with small support). FMG sets displays a richness of structure far exceeding .
6.2 Lifting constructions in to the set theory
is a set in FMG, identified by the predicate - . So are the natural numbers, pairs, cartesian products, disjoint sums, lists, streams, and their constructors such as , Inl Inr(), and so on; the constructions are just as in 2.3.
In particular we recall that can be implemented in sets as .
and are now sets. Function-sets are built as their graphs as is standard. is identified by:
(1) .
(2) Any permutation is the identity off some well-orderable set of atoms.
In the first part, denotes (the permutation) acting on (the function-set). denotes the function-set expressing the graph of the permutation .
(1) We observe that acts on the graph of by acting on the atoms within it; it is a fact of group theory that conjugation does the same.
(2) If supports then contains every atom such that () (since otherwise we could permute () to something else). Since is a set, it has well-orderable support. The result follows.
2
If write
We say
Finally define
(though the next result shows this is not as useful as we might imagine).
(1) If and support and are well-orderable, then so is .
(2) S does not necessarily support .
(1) Suppose and support and suppose fixes just . Let . By (AtmLrg) is not well-orderable and since certainly is, we can choose some disjoint from , , , and a supporting set for .
Since and are well-orderable and the same size, there is an idempotent permutation bijecting with and fixing all other atoms (swap the th elements of and , for arbitrary but fixed well-orderings). Now fixes so . Now fixes and also so which is equal to (since ) fixes () which includes . Therefore . Applying to both sides and simplifying we deduce that as required.
(2) It suffices to consider the example of Lemma 21.
2
So here, at least, FMG is not as tractable as FM (or )! The notion of a supporting set is still valid and useful, and we may still intersect supporting sets to obtain smaller supporting sets — but if we do this infinitely often we may ‘miss an infinitesimal bit of support’.
When S does not support , say has fuzzy support. When S does support , say it has sharp support.
identifies a convenient subset of the FMG universe which exhibits inductive datatypes of abstract syntax with infinitary binding, but still has sharp support.
(1) Permutations have sharp support, and S() .
(2) and have sharp support, and S
(3) If has sharp support, then so does .
(4) If supports then supports . As a corollary, S S.
(1) A permutation is represented as a set by its graph; e.g. ( . It is not hard to verify the requisite properties, recalling that acts pointwise on sets and is just .
(2) By concrete calculations.
(3) The property of being a supporting set can be expressed by a predicate in FMG. The result follows by part 1 of Theorem 35 (a proof by concrete calculations is also possible). The second part follows by calculations, or directly by part 2 of Theorem 35.
2
As a matter of notation write
The reader may like to compare this with the corresponding definition from 2.1, which was # when S S. The difference is of course due to the possibility of fuzzy support; if and have sharp support the two versions become equivalent.
The following result is a useful corollary of Equivariance (it also generalises Lemma 19, which there was proved for by concrete calculation):
(1) If supports , ..., and is a function-class specified in the language of FMG with parameters amongst the , then supports ().
(2) As a corollary, if () is a function-class in FMG with parameters ,... , then if # then #().
It suffices to apply the second part of Theorem 35. 2
In words:
Any function-class specified in (the logic of) FMG sets, does not create support.
We verify that a suitable version of Lemma 3 is still valid:
(1) If supports then supports . Also, (S S().
(2) #[].
(3) If # then .
(4) If ( for all for some supporting , then .
(1) Direct from Theorem 35 for the predicate ‘supports’ and the function ‘S’.
(2) From Lemma 41.
(3) # when fixes a set supporting . The result follows.
(4) By definition of supporting set.
2
Abstractions [] are defined much as in 2.1, but we must assume has sharp support, and protect against the possibility that has fuzzy support by not using S:
(1) ([]]() holds.
(2) If has sharp support then supports if and only if S supports .
(1) By part 2 of Theorem 35.
(2) In essence identical to the proof of the case for abstractions of part 4 of Lemma 3, we sketch half of it in full: We can prove by calculation that supports #S is a group.
Suppose has sharp support and supports . Suppose Fix(S). Then
Now suppose supports [] and suppose Fix( S()). Then ()
2
(It does not seem fruitful to consider [] when does not have sharp support.)
The maps between , , and , can also be constructed as before.
It is not hard to verify that Lemma 10 transfers unchanged to FMG. The discussions of purely abstractive and Barendregt abstractive functions, , and freshness, transfer almost word-for-word.
6.3 Abstractions commute with pairsets, powersets, and more
Theorem 15 generalises beautifully in FMG. We give just the case for cartesian product, and also full function spaces and powersets (not just countable ones, as we did in Theorem 15).
(1) []() ]
Similarly for , e.g. []() ] .
We consider just the cases for ; the cases of is simpler.
(1) We map
These maps are well-defined since it is easy to use Corollary 39 and part 2 of Lemma 40 to deduce #@)
We now verify that these maps are self-inverse. By Lemma 32 it suffices to check that (for one suitably fresh )
This follows easily, using Lemma 10.
(2) We map
We must check these maps are well-defined. Suppose and are given. Choose some # . Then @ and @ are well-defined and #[]( @@). Conversely suppose is given. Choose some #. Then #([]) so ([])@ is well-defined and #[]([])@.
We now verify that these maps are self-inverse. By Lemma 32 it suffices to check that (for one suitably fresh )
This follows easily, making heavy use of Lemma 10.
(3) This is a corollary of the previous lemma, taking and observing that [] is naturally isomorphic to , see Theorem 15. In full, the maps are given by:
2
This result is important because it enables us to drop the condition implicit in the construction of of considering just countable powersets. Since () is strictly larger than , and similarly is strictly larger than and (provided and have more than two elements), and they not inherit any inductive structure, this theorem is one way of making formal that our treatment of names and bindings in FMG is strictly more general than the standard model given by abstract syntax trees.
This extension to function-sets is also useful, e.g. for the existence of a monad in the semantics of FreshML used to prove the language correct, and for equalities used in understanding models of behaviour [21,15].
6.4 An algebraic version
We give an alternative presentation of and FMG in algebraic style. Fix a particular uncountable set . Let be permutations of with countable support. Then a Nominal FMG set (where small=countable) is:
Here means that holds of all but a countable set of atoms, and means that holds of countable lists of distinct atoms whose atoms may be all but a countable set of atoms.
It is easy to verify that an equivariant FMG set (for any given model of FMG sets), or an equivariant subclass of , is a Nominal FMG set. If we need more atoms we just take to be larger and to have any support strictly smaller than the size of .
(1) is a nominal FMG set with small=countable.
(2) If is such that # for all then always.
It is now easy to see that if we know that small= where is some cardinality, then similar results hold for streams of distinct atoms of length an ordinal with cardinality . This is the correct generalisation of the FM principle that # implies is equivariant.
7 Future work
Infinite binding arises in behavioural models of reactions: for example, if then the -calculus process ! is behaviourally equivalent to the ‘infinitary’ process [22]. Also, if then the -calculus process is -equivalent to the ‘infinitary’ process ((())). This equivalence can be made formal by considering a behavioural notion of model, which can display infinite structure even though the trace of any particular behaviour may be finite. One such structure is considered by Montanari et al [23] which we can view as a de Bruijn-based model of behaviour which may generate fresh names, whose main interest is in powerful optimisations which merge nodes identical except for permutations of names.
If name-binding is modelled by FM-style abstractions, there is a need for infinite FM-style abstraction in the model of behaviour. 6 We have proposed one method of obtaining this effect. We have examined the proof-principles which seem useful on these objects, and by progressive abstraction we have formalised and generalised them to obtain notions such as ‘abstraction and concretion by infinitely many atoms’, ‘abstractive functions’, ‘Barendregt representatives’, ‘generalised ’, and we have described some nice results describing their properties.
6 Since this paper was submitted for publication, a paper has been published describing a semantics for FreshML which approximates this in a category with a FM-style monad representing finitely but unboundedly many abstractions [5].↩
has an interesting capture-avoiding substitution action given as follows:
(Recall that an element of is either an atom , a countable set , or an abstraction [], and that for any abstraction there is a choice of and forming that abstraction such that S S; thus this is a total function.)
Since -reduction is given in the -calculus, this suggests that we might use the FM model of abstraction to obtain models of the -calculus that are not Scott domains, and with a set-theoretic flavour. The obstacle to this idea is that we do not know what application is. This is current work.
References
[1] M. J. Gabbay, A theory of inductive definitions with alpha-equivalence, Ph.D. thesis, Cambridge, UK (2000).
[2] M. J. Gabbay, A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing 13 (2001) 341–363.
[3] J. Bell, M. Machover, A course in mathematical logic, North-Holland, 1977.
[4] P. T. Johnstone, Notes on logic and set theory, Cambridge University Press, 1987.
[5] M. R. Shinwell, A. M. Pitts, On a monadic semantics for freshness, Theoretical Computer Science 342 (2005) 28–55.
[6] N. G. de Bruijn, Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the church-rosser theorem, Indagationes Mathematicae 5 (34) (1972) 381–392.
[7] J. Barwise, An introduction to first-order logic, in: J. Barwise (Ed.), Handbook of Mathematical Logic, North Holland, 1977, pp. 5–46.
[8] D. van Dalen, Intuitionistic logic, in: D. Gabbay, F. Guenthner (Eds.), Handbook of Philosophical Logic, 2nd Edition, Volume 5, Kluwer, 2002, pp. 1–114.
[9] J. B. Fraleigh, A First Course in Abstract Algebra, Addison-Wesley, 1994.
[10] L. C. Paulson, A fixedpoint approach to implementing (co)inductive definitions, in: CADE-12: Proceedings of the 12th International Conference on Automated Deduction, Springer-Verlag, London, UK, 1994, pp. 148–161.
[11] J. Truss, Permutations and the axiom of choice, in: H. R.Kaye (Ed.), Automorphisms of first order structures, OUP, 1994, pp. 131–152.
[12] H. P. Barendregt, The Lambda Calculus: its Syntax and Semantics (revised ed.), Vol. 103 of Studies in Logic and the Foundations of Mathematics, North-Holland, 1984. URL http://www.andrew.cmu.edu/user/cebrown/notes/barendregt.html
[13] J. McKinna, R. Pollack, Some lambda calculus and type theory formalized, Journal of Automated Reasoning 23 (3-4) (1999) 373–409.
[14] M. J. Gabbay, The -calculus in FM, in: F. Kamareddine (Ed.), Thirty-five years of Automath, Kluwer, 2003, pp. 80–149.
[15] M. J. Gabbay, Fresh graphs, submitted (November 2003).
[16] M. J. Gabbay, A. M. Pitts, A new approach to abstract syntax involving binders, in: 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, 1999, pp. 214–224.
[17] K. Gödel, On formally undecidable propositions in principia mathematica and related systems i, available online in translation by Martin Hirzel (1931).
[18] N. Brunner, 75 years of independence proofs by fraenkel-mostowski permutation models (1996).
[19] K. Kunen, Set Theory: An Introduction to Independence Proofs (Studies in Logic and the Foundations of Mathematics), Elsevier, 1980.
[20] A. M. Pitts, Nominal logic, a first order theory of names and binding, Information and Computation 186 (2003) 165–193.
[21] M. R. Shinwell, A. M. Pitts, M. J. Gabbay, FreshML: Programming with binders made simple, in: Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden, ACM Press, 2003, pp. 263–274.
[22] R. Milner, J. Parrow, D. Walker, A calculus of mobile processes, II, Information and Computation 100 (1) (1992) 41–77.
[23] U. Montanari, M. Pistore, History-dependent automata, Tech. Rep. TR-98-11, University of Pisa (5, 1998).