THE LANGUAGE OF STRATIFIED SETS IS CONFLUENT AND STRONGLY NORMALISING
Abstract. We study the properties of the language of Stratified Sets (first-order logic with and a stratification condition) as used in TST, TZT, and (with stratifiability instead of stratification) in Quine’s NF. We find that the syntax forms a nominal algebra for substitution and that stratification and stratifiability imply confluence and strong normalisation under rewrites corresponding naturally to -conversion.
Key words and phrases: Stratified syntax, typed set theory, Quine’s New Foundations, nominal rewriting, nominal algebra.
Thanks to the editor and to the anonymous referees.
1. Introduction
1.1. About Stratified Sets.
Consider Russell’s paradox, that if then if and only if . One way to avoid the term is to restrict to the language of Stratified Sets. This is first-order logic with a binary relation whose intuition is ‘ is an element of ’ and:
Variable symbols (called atoms in this paper) are assigned levels, which are typically integers or natural numbers.
We impose a stratification typing condition that we may only form if the level of is one plus the level of . level( level()1.
See Definition 5.3 for full details. Then cannot be stratified, since whatever level we assign to in we cannot make level( level()1.
Stratified Sets are one of a family of syntaxes designed to exclude Russell’s paradox:
The language of ZF set theory restricts sets comprehension to bounded comprehension .
Type Theories (such as Higher-Order Logic) impose more or less elaborate type systems. The canonical example of this is simple types .
Stratified Sets stratifies terms as described.
One feature of Stratified Sets is that we can write a term representing the universal set:
is easily stratified by giving any level we like. Likewise we can write definitions such as ‘the number 2’ to be ‘the set of all two-element sets’:
(Here we freely use syntactic sugar for readability; this can all be made fully formal.)
This feels liberating: we have the pleasure of full unbounded sets comprehension1 and we have the pleasure of more sweeping types than are possible in the usual type theories such as Higher-Order Logic and its elaborations.2
1.2. What this paper does.
The published literature using Stratified Sets does not view the basic syntax from the point of view of rewriting. On this topic, this paper makes three observations:
(1) The stratification condition implies that the syntax is confluent and strongly normalising under the natural rewrite
We can write:
Stratification confluence and strong normalisation.
Similarly for stratifiability. See Theorems 5.30 and 5.32.
(2) The syntax of normal forms becomes an algebra for substitution in a sense that will be made formal using nominal algebra. See Theorem 4.19; in fact the proof of Theorem 5.30 uses this.
(3) Our proof is constructed using nominal techniques. The proofs in this paper should be fairly directly implementable in a nominal theorem-prover, such as Nominal Isabelle [Urb08].
In some senses, this paper is deliberately conventional, even simple: we write down a syntax and a rewrite relation and prove some nice properties. But the simplicity is deceptive:
TST, TZT, and NF as usually presented do not include sets comprehension in their syntax, if that syntax is even made fully formal. So just noting that there are rewrite relations here that might be useful to look at, seems to be a new observation.
The proofs are not trivial. It is easy to give a handwaving argument (such as that given in the first half of Remark 1.6 below) but it is surprisingly difficult to give a rigorous proof with all details.
More on this in Section 6.
We use nominal techniques (see the material in Section 2) to manage the -binding in the syntax for universal quantification and sets comprehension. If the reader is unfamiliar with nominal techniques then they can just ignore this aspect: wherever we see reference to a nominal theorem, we can replace it with ‘by -conversion’ or with ‘it is a fact of syntax that’. The result should then be close to the kind of argument that might normally pass without comment or challenge.
1.3. Some remarks.
‘The language of Stratified Sets’ is a description specific to this paper. In the literature, this syntax is unnamed and presented along with the theory we express using it:
(1) TST (which stands for Typed Set Theory) is typically taken to be first-order logic with and variables stratified as 0 1 2, along with reasonable axioms for first-order logic and extensional sets equality.
(2) TZT is typically taken to be as the syntax and axioms of TST but with variables stratified as 0 1 -1 2 -2.
(3) Quine’s New Foundations (NF) uses the language of first-order logic with , and reasonable axioms, and a stratifiability condition that variables could be stratified.
So in TST we would have to write (say) (choosing a level 1 variable symbol and a level 2 variable symbol ), whereas in NF we could write just and say “we could assign level 1 and level 2”.
There is a slight ambiguity when we talk about stratification whether we insist that the syntax come delivered with an assignment of levels to all terms, or whether we insist on the weaker condition that an assignment could be made, but this assignment need not be a structural part of the formula or term. This distinguishes the languages of TST and TZT from that of NF: TST and TZT insist on stratification, and NF insists on stratifiability.
Our results will be agnostic in this choice (see for instance Theorems 5.30 and 5.32). So when we write Stratified Sets we could just as well write Stratifiable Sets and everything would still work with only minor bookkeeping changes.
The reader with a background in TST, TZT, and NF should note that this is not a paper about logical theories: it is a paper about their syntax. This is why we talk about ‘Stratified Sets’ in this paper, and not e.g. ‘Typed Set Theories’. Our protagonist is a language, not a logic.
Some authors expand TST as ‘Theory of Simple Types’. I think this terminology invites confusion with Simple Type Theory, so I prefer the alternative ‘Typed Set Theory’. I would also like to write that TZT stands for ‘Typed Zet Theory’, but really TZT just stands for itself.
For the reader interested in the logical motivations for these syntaxes we provide references:
A historical account of Russell’s paradox is in [Gri04].
For ZF set theory, see e.g. [Jec06].
Excellent discussions of TST, TZT, and NF are in [For95] and [Hol98], and a clear summary with a brief but well-chosen bibliography is in [For97].
One way to see that something like this paper should work, fingers crossed, is by an analogy:
The rewrite [:] can be rewritten as ()[:].
Extensionality is , and we can rewrite this as ().
These are of course familiar as -reduction and -expansion. The proofs need to be checked but the analogy above invites an analysis of the kind that we will now carry out.
And indeed this has been done, though not for stratified sets. In [KA10] (many thanks to an anonymous referee for bringing this to my attention) a development analogous to what is done in this paper for stratified syntax using nominal techniques, is carried out for the simply-typed lambda-calculus using de Bruijn indexes. Definitions and results bear a very nice comparison: for instance, Lemma 6 of [KA10] corresponds to Proposition 5.12.3
A technical device in [KA10], which goes back to a quite technical development in [WCPW03], is to work directly with a datatype of normal forms and substitution on them; this is just like the internal syntax and its sigma-action that we will see in this paper.
For me the motivation for setting things up in this way is partly practical and partly abstract: internal syntax with its sigma-action turns out to be a nominal sigma-algebra (Theorem 4.19) and this ties in with a literature on advanced nominal models of logic and computation [Gab16, GG17, GM08]. This paper was originally conceived as a prelude to building advanced nominal models of stratified and stratifiable syntaxes and type theories, though it has acquired independent interest.
It is therefore interesting to see analogous design choices appearing independently, motivated by apparently purely implementational concerns: what is good for the abstract mathematics also seems to be good for the proof-engineering.
2. Background on nominal techniques
Intuitively, a nominal set is “a set X whose elements X may ‘contain’ finitely many names ”. We may call names atoms. The notion of ‘contain’ used here is not the obvious notion of ‘is a set element of’: formally, we say that has finite support (Definition 2.10).
Nominal sets are formally defined in Subsection 2.1. Examples are in Subsection 2.2. The reader might prefer to read this section only briefly at first, and then use it as a reference for the later sections where these underlying ideas get applied. More detailed expositions are also in [GP01, Gab11, DG12a, Pit13].
In the context of the broader literature, the message of this section is as follows:
The reader with a category-theory background can read this section as exploring the category of nominal sets, or equivalently the Schanuel topos (more on this in [MM92, Section III.9], [Joh03, A.21, page 79], or [Gab11, Theorem 9.14]).
The reader with a sets background can read this section as stating that we use Fraenkel-Mostowski set theory (FM sets).
A discussion of this sets foundation, tailored to nominal techniques, can be found in [Gab11, Section 10]. FM sets add urelemente or atoms to the sets universe.
The reader uninterested in foundations can note that previous work [GP01, Gab11, DG12a] has shown that just assuming names as primitive entities in Definition 2.1 yields a remarkable clutch of definitions and results, including Theorem 2.12, Corollary 2.13, and Theorem 2.26.
2.1. Basic definitions.
2.1.1. Atoms and permutations.
For each fix a disjoint countably infinite set of atoms.4
Write .
If (so is an atom) write level() for the unique number such that .
We use a permutative convention that range over distinct atoms.
If we do not wish to use the permutative convention then we will refer to the atom using (see for instance (eltatm) of Figure 2).
2.1.2. Permutation actions on sets.
Suppose : is a bijection on atoms.
(1) If nontriv(() is finite then we call finite.
(2) If () then call sort-respecting.
(3) A permutation is a finite sort-respecting bijection on atoms. Henceforth will range over permutations.
We will use the following notations in the rest of this paper:
(1) Write id for the identity permutation such that id( for all .
(2) Write for composition, so that ()((()).
(3) If and then write () for the swapping (terminology from [GP01]) mapping to , to , and all other to themselves, and take (.
(4) Write for the inverse of , so that .
2.1.3. Sets with a permutation action.
If write
A set with a permutation action X is a pair (X) of an underlying set X and a permutation action written which is a group action on X, so that id and ( () for all X and permutations and .
(1) Say that supports X when fix() .
(2) If a finite supporting exists, call finitely supported (by ) and say that has finite support.
If X is a set with a permutation action then we may write
X as shorthand for X, and
X as shorthand for X.
2.1.4. Nominal sets.
Call a set with a permutation action X a nominal set when every X has finite support. X, Y, Z will range over nominal sets.
Call a function XY equivariant when ((() for all permutations and X. In this case write : XY.
The category of nominal sets and equivariant functions between them is usually called the category of nominal sets.
Suppose X is a nominal set and X. Define the support of by
Write # as shorthand for supp() and read this as is fresh for .
If write # as shorthand for #.
Given atoms and elements write # as shorthand for 1#. That is: # for every and .
Suppose X is a nominal set and X. Then supp() is the unique least finite set of atoms that supports .
See [Gab11, Theorem 2.21(1)].
(1) If ( for all supp() then . Equivalently:
(a) If fix(supp()) then .
(b) If (()#) then (see Notation 2.11).
(2) If (() for every supp() then .
(3) # if and only if (# ()).
2.2. Examples.
Suppose X and Y are nominal sets. We consider some examples, some of which will be useful later.
2.2.1. Atoms.
is a nominal set with the natural permutation action ().
2.2.2. Cartesian product.
X Y is a nominal set with underlying set () X Y and the pointwise action ().
It is routine to check that supp(( supp()supp().
2.2.3. Full function space.
XY is a set with a permutation action with underlying set all functions from X to Y, and the conjugation permutation action
2.2.4. Finite-supported function space.
XY is a nominal set with underlying set the functions from X to Y with finite support under the conjugation action, and the conjugation permutation action.
2.2.5. Full powerset.
Suppose Z is a set with a permutation action. Give subsets Z the pointwise permutation action
Then pset(Z) (the full powerset of Z) is a set with a permutation action with
underlying set Z (the set of all subsets of Z), and
the pointwise action .
A particularly useful instance of the pointwise action is for sets of atoms. As discussed in Subsection 2.2.1 above, if then (). Thus if then
Even if Z is a nominal set, pset(Z) need not be a nominal set.
Take Z which we enumerate as and we take pset(Z) to be equal to comb defined by
This does not have finite support (see also [Gab11, Remark 2.18]).
2.2.6. Finite powerset.
For this subsection, fix a nominal set X.
Write FinPow(X) for the nominal set with
underlying set the set of all finite subsets of X,
with the pointwise action from Definition 2.14.
We might write X for FinPow(X).
The first part is immediate since by assumption there is some finite that bounds supp() for all . The second part follows by an easy calculation using part 3 of Corollary 2.13; full details are in [Gab11, Theorem 2.29], of which Lemma 2.18 is a special case. Part 3 follows from the first and second parts.
2.2.7. Atoms-abstraction.
Atoms-abstraction was the first real application of nominal techniques; it was used to build inductive datatypes of syntax-with-binding. Nominal atoms-abstraction captures the essence of -binding. In this paper we use it to model the binding in universal quantification and sets comprehension (see Definition 3.3). The maths here goes back to [Gab01, GP01]; we give references to proofs in a more recent presentation [Gab11].
Assume a nominal set X and an .
Let the atoms-abstraction set []X have
Underlying set [] X where [](()) fix(supp()).
Permutation action []].
If X and then supp([] supp(). In particular #[] (Notation 2.11).
See [Gab11, Theorem 3.11].
Suppose X and . Then if # then []]().
See [Gab11, Lemma 3.12].
Suppose []X and . Write @ for the unique X such that ], if this exists.
Suppose and []X. Then # implies @ X is well-defined.
See [Gab11, Theorem 3.19].
Suppose and X and []X. Then:
(1) ([])@ and if # then ([])@).
(2) If # then [](@.
See [Gab11, Theorem 3.19].
2.3. The principle of equivariance.
We now come to the principle of equivariance (Theorem 2.26; see also [Gab11, Subsection 4.2] and [GP01, Lemma 4.7]). It enables a particularly efficient management of renaming and -conversion in syntax and semantics and captures why it is so useful to use names to model them instead of, for instance, numbers.
In a nutshell we can say
Atoms are distinguishable, but interchangable.
and we make this formal as follows:
Suppose is a list . Suppose is a (not necessarily finite) permutation and write for . Suppose Φ() is a first-order logic predicate in the language of ZFA6 with free variables . Suppose Υ() is a function specified using a first-order predicate in the language of ZFA with free variables .
Then we have the following principles:
(1) Equivariance of predicates. Φ() Φ().7
(2) Equivariance of functions. Υ().
(3) Conservation of support. If denotes elements with finite support then supp(Υ()) supp()supp().
See Theorem 4.4, Corollary 4.6, and Theorem 4.7 from [Gab11].
Theorem 2.26 states that atoms can be permuted in our theorems and lemmas provided we do so consistently in all parameters. So for instance if we have proved (), then
taking ) we also know () and
taking )()() we also know (), but
we do not necessarily know that we can deduce () (depending on this may still hold, of course, but not by equivariance since no permutation takes () to ()).
Equivariance makes explicit a sense in which atoms have a dual nature: individually, atoms behave like pointers to themselves,8 but collectively they have the flavour of variables ranging over the set of all atoms via the action of permutations.9 See also the permutative convention from Definition 2.1.
We will use Theorem 2.26 frequently in this paper, either to move permutations around (parts 1 and 2) or to get ‘free’ bounds on the support of elements (part 3). ‘Free’ here means ‘from the form of the definition, without having to verify it by calculations’. Theorem 2.26 is ‘free’ in the spirit of Wadler’s marvellously titled Theorems for free! [Wad89].10
Discussions expanding on this remark are in [Gab17] (full paper) and [Gab18] (abstract).
(1) supp(supp() (which means () supp()).
(2) # (Notation 2.11) if and only if ()#, and # if and only if ()#.
3. Internal syntax
3.1. Basic definition.
We are now ready to to define our syntax (Figure 1) and study its basic properties (with more advanced properties considered in Section 4).
Figure 1 defines a nominal datatype, in which atoms-abstraction is used to manage binding, as introduced in [GP01]. This gives us Lemma 3.6.
(1) Parts 1 and 3 of Lemma 3.6 say “We can alpha-convert”.
(2) In part 2 of Lemma 3.6, supp corresponds exactly to the notion that would normally be written “Free variables of”, and # corresponds to “ is not free in ”.
So why not just write that? Nominal techniques are a general basket of ideas with implications that go well beyond modelling syntax, but the specific benefit of using nominal techniques to model syntax is that we get alpha-conversion for free from the ambient nominal theory (see [GP01] and Section 2). We do not have to define -conversion and free variables of by induction, and then prove their properties (which is actually a more subtle undertaking than is often realised; cf. Remark 4.14).
The reader does not expect to see notions of ordered pairs, trees, numbers, functions, and function application developed from first principles every time we want to write abstract syntax and write a function on a syntax tree. It is assumed that these things have been worked out. Nominal techniques do that for binding (and more).
Write for the integers, so 0 1 -1 2 -2 and for the natural numbers, which we start at 0, so 0 1 2.
(1) Define datatypes
Pred of internal predicates and
Set for of internal (level ) sets inductively by the rules in Figure 1, where ranges over finite ordinals.
(2) Define
(3) Write age() for the least such that Pred().
(4) Write age() for the least such that Set().
If we may call atm() an internal atom.
If Pred we may call st([]) an internal comprehension.
We may call atm() or st([]) an internal set.11
We read through and comment on Definition 3.3:
(1) measures the age or stage of an element; at what point in the induction it is introduced into the datatype. This is an inductive measure.
(2) If we elide and levels and simplify, we can rewrite Definition 3.3 semi-formally as follows:
(3) neg represents negation. and represents logical conjunction.
(4) and takes a finite set rather than a pair of terms. This is a nonessential eccentricity that cuts down on cases later on. Truth is represented as and(). See Example 3.9.
(5) all represents universal quantification; read all([]) as ‘for all , ’ or in symbols: ‘’. In all([]), [] is the nominal atoms-abstraction from Definition 2.19. It implements the binding of the universal quantifier by the standard nominal method.
(6) represents a sets membership; read elt() as ‘ is an element of ’. Note here that is an atom; it does not literally have any elements. elt() represents the predicate ‘we believe that is an element of the variable ’, or in symbols: ‘’.
(7) st([]) represents sets comprehension; read st([]) as ‘the set of such that ’ or in symbols: ‘’. Again, as standard in nominal techniques, nominal atoms-abstraction is used to represent the binding.
(8) atm() is a copy of wrapped in some formal syntax atm.
Suppose Pred and and and #. Then:
(1) st([] st([]()) and all([] all([]()).
(2) #st([]) and #all([]), and supp(st([])) supp(all([])) supp().
(3) For every finite there exist and Pred such that st([] st([]) and all([] all([]).
Suppose and and Pred and Set. Then age( age(()) and age( age(()).
3.2. Some notation.
Suppose Pred and Pred. Define syntactic sugar or(), imp() and iff() by
Define F Pred and T Pred by
Intuitively, F represents the empty disjunction, and T represents the empty conjunction.
Suppose that:
and
st()Set is an internal comprehension where []Pred and and
# (equivalently#).
Then write
@ for @
Lemma 3.11 checks that Notation 3.10 makes sense:
Suppose and . Suppose Set is an internal comprehension and # and Pred. Then:
(1) @ is well-defined and @ Pred.
(2) st([](@)).
(3) If age(1 then age(@ (meaning that in an inductive argument using age, taking @ strictly decreases the inductive measure).
(4) (st([]))@ .
Recall For() from Example 3.9.
Suppose and . Define empt and set by
We conclude with an easy lemma:
Suppose and . Then:
(1) empt@ F and st([]F empt, and similarly set@ T and st([]T set.
(2) #F and #T.
(3) Definition 3.12 does not depend on the choice of .
4. The sigma-action
4.1. Basic definition and well-definedness.
Intuitively, Definition 4.1 defines a substitution action. It is slightly elaborate, especially because of (elta) of Figure 2, so it gets a fancy name (‘-action’) and we need to make formal and verify that it behaves as a substitution action should; see Remark 4.7.
Define a -action (sigma-action) to be a family of functions
where , inductively by the rules in Figure 2. For readability we write
Furthermore in Figure 2:
In rule (and), Pred.
In rule (neg), Pred.
In rule (all), Pred and for some .
In rule (elta), .
In rule (eltatm), ranges over all atoms in (not just those distinct from ).
In rule (eltb), for some .
In rule (st), Pred and for some .
Figure 2 slips in no fewer than three abuses of the mathematics:
(1) We do not know that Pred implies [] Pred, so we should not write and([] ) on the right-hand side of (and), or indeed [] on the right-hand side of (neg), and so on. In fact, all right-hand sides of Figure 2 are suspect except those of (a) and (b).
(2) We do not know whether the choice of fresh in (elta) matters, so we do not know that (elta) is well-defined.
(3) The definition looks inductive at first glance, however in the case of (elta) there is no guarantee that (on the right-hand side) is smaller than elt() (on the left-hand side). The level of is strictly lower than the level of , however levels are taken from which is totally ordered but not well-ordered by .
In fact:
Pred does indeed imply [] Pred.
The choice of fresh in (elta) is immaterial.
The levels of atoms involved are bounded below (see Definition 4.4) so we only ever work on a well-founded fragment of .
For proofs see Proposition 4.6 and Lemma 4.8.
Would it be more rigorous to interleave the proofs of these lemmas with the definition, so that at each stage we are confident that what we are writing actually makes sense? Certainly we could; the reader inclined to worry about this need only read Definition 4.1 alongside Proposition 4.6 and Lemma 4.8 as a simultaneous inductive argument.
Levels are in and are totally ordered by but not well-founded (since integers can ‘go downwards forever’).
However, any (finite) internal predicate or internal set can mention only finitely many levels, so we can calculate the minimum level of a predicate or set, which is lower bound on the levels of atoms appearing in that predicate or set. We will use this lower bound to reason inductively on levels in Propositions 4.6 and 4.13.
Define minlevel() and minlevel() the minimum level of or , inductively on Pred and Set for as follows:
Above, min() is the least element of . We add 0 in the clause for and as a ‘default value’ to exclude calculating a minimum for the empty set; any other fixed integer element would do as well or, if we do not want to make this choice, we can index minlevel over a fixed but arbitrary choice. The proofs to follow will not care.
It will be convenient to apply minlevel to a mixed list of internal predicates, atoms, and internal sets:
Define minlevel( level().
If ) is a list of elements from Pred Set then we write minlevel() for the least element of minlevel() minlevel().
Suppose and and Set.
(1) If Pred then
[] is well-defined,
minlevel([])minlevel(), and
[]Pred.
(2) If and Set then
[] is well-defined,
minlevel([])minlevel(), and
[]Set.
Fix some . We prove the Proposition for all and with minlevel() and minlevel(), by induction on
lexicographically ordered. Since was arbitrary, this suffices to prove it for all and .
We consider the possibilities for Pred:
The case of and() for Pred.
By Figure 2 (and) [and([]) We use the inductive hypothesis on each [] and some easy arithmetic calculations.
The case of neg() for Pred. By Figure 2 (neg) [ neg(([])) We use the inductive hypothesis on [].
The case of all([]) for Pred and for some .
Using Lemma 3.6(1) we may assume without loss of generality that #. By Figure 2 (all) (all([]))[ all([]([])) We use the inductive hypothesis on [].
The case of elt() for Set. There are two sub-cases:
– Suppose atm() for some . By Figure 2 (eltatm) (elt())[ elt([atm()]) We use the inductive hypothesis on [atm()].
– Suppose st([]) where @ for some fresh (so #). By Figure 2 (elta) (elt())[[[]] We have the inductive hypothesis on []. We also have the inductive hypothesis (since level(-1 level())13 on [[]], and this suffices.
The case of elt() where and Set and . By Figure 2 (eltb) and the inductive hypothesis.
We consider the possibilities for Set:
The case that is an internal atom. We use (a) or (b) of Figure 2.
The case that is an internal comprehension.
Choose fresh (so #), so that by Lemma 3.11(2) st([]@). We use the first part of this result and Figure 2 (st).
4.2. Nominal algebraic properties of the sigma-action.
Several useful properties of the -action from Definition 4.1 are naturally expressed as nominal algebra judgements — equalities subject to freshness conditions [GM09]. Some are listed for the reader’s convenience in Figure 3, which goes back to nominal axiomatic studies of substitution from [GM06, GM08].
In this paper we are dealing with a concrete model, so the judgements in Figure 3 are not assumed and are not axioms. Instead they must be proved; they are propositions and lemmas:
() is Lemma 4.8.
(#) is Lemma 4.10.
() is Proposition 4.13.
(swp) and (asc) are Corollaries 4.15 and 4.16.
(id) is Lemma 4.17.
(ren) is Lemma 4.18.
(@) is Lemma 4.12.
These are familiar properties of substitution on syntax: for instance
() looks like an -equivalence property — and indeed it is — and
(#) (Lemma 4.10) is sometimes called garbage collection and corresponds to the property “if is not free in then [”, and
() (Proposition 4.13) is often called the substitution lemma. See the discussion in Remark 4.14.
But, the proofs of these properties that we see in this paper are not replays of the familiar syntactic properties.
This is because the -action on Pred is not a simple ‘tree-grafting’ operation — not even a capture-avoiding one — because of (elta) in Figure 2. The proofs work, but we cannot take this for granted, and they require checking.
4.2.1. Alpha-equivalence of the sigma-action.
Suppose and and Set. Suppose Pred and # and Set and #. Then:
(1) [))[] and [))[].
(2) supp([]) (supp()) supp() and supp([]) (supp()) supp().
(3) If # then #[] and #[].
By induction on
We consider the possibilities for Pred:
The case of and() for Pred. By Lemma 2.18 # for every , so by the inductive hypothesis [))[]. We use Figure 2 (and) and Theorem 2.26.
The case of neg() for Pred. By Figure 2 (neg) and the inductive hypothesis for .
The case of all([]) for Pred and for some . Using Lemma 3.6(1) we may assume without loss of generality that #. We use Figure 2 (all) and the inductive hypothesis.
The case of elt() for some Set. There are two sub-cases:
– Suppose atm() for some . We reason as follows:
– Suppose st([]) where @ for some fresh (so #). We reason as follows:
The case elt() for and and Set. We reason as follows:
We consider the possibilities for Set:
The case that is an internal atom. We use (a) or (b) of Figure 2.
The case that is an internal comprehension. We use Lemma 3.11(2&3) for a fresh (so #), (st), and the inductive hypothesis.
For part 2, we note that by Theorem 2.26 and Proposition 2.28
We take a sets intersection. The case of is similar.
Part 3 follows, recalling from Notation 2.11 that # means supp().
Note for experts: We could set Definition 4.1 up differently: we could have and input abstractions
Then Lemma 4.8 would become immediate from Lemmas 2.20 and 2.21 and Theorem 2.26. This is nice but note that we incur a well-definedness proof-obligation that the choice of name for the abstracted atom does not matter. There is probably still a net gain but it is not quite as great as it might first seem. For this reason, we use the more elementary set-up in Definition 4.1.
4.2.2. Property (#) (garbage collection).
Suppose and and Set and Pred and Set for . Then
By induction on
We consider the possibilities for Pred:
The case of and() for Pred.
By Figure 2 (and) (and())[ and([] ). By Lemma 2.18(3) # for every . We use the inductive hypothesis on each .
The case of neg() for Pred. By Figure 2 (neg) neg()[ neg([]). We use the inductive hypothesis on .
The case of all([]) for Pred and for some .
Using Lemma 3.6(1) we may assume without loss of generality that #. By Figure 2 (all) (all([]))[ all([]([])). We use the inductive hypothesis on .
The case of elt() for and Set. This is impossible because we assumed #.
The case of elt() for and and Set.
By Figure 2 (eltb) (elt())[ elt([]). We use the inductive hypothesis on .
We consider the possibilities for Set:
If is an internal atom then we reason using (a) or (b) of Figure 2.
If is an internal comprehension then we use Lemma 3.11(2&3) for a fresh (so #), (st), and the inductive hypothesis.
Recall For() and Tand() from Example 3.9. Corollary 4.11 is an easy consequence of Lemma 4.10 and will be useful later:
Suppose and and Set. Then
4.2.3. commutes with atoms-concretion.
Lemma 4.12 will be useful later, starting with Proposition 4.13:
Suppose and and Set. Suppose and Set is an internal comprehension and and #. Then
(@ is from Notation 3.10.)
By Lemma 3.11(2) we may write st([]) where @. We reason as follows:
4.2.4. commutes with itself: the ‘substitution lemma’.
Suppose Pred and and Set. Suppose and and Set and suppose and and Set and #. Then
For brevity we may write
Fix some . We prove the Lemma for all and with minlevel() and minlevel() (Definition 4.4), reasoning by induction on
lexicographically ordered. Since was arbitrary, this suffices to prove it for all and .
We consider the possibilities for Pred:
The case of and() for Pred. We use rule (and) of Figure 2 and the inductive hypothesis.
The case of neg() for Pred. We use (neg) of Figure 2 and the inductive hypothesis.
The case of all([]) for Pred and for some . We use Lemma 3.6(1) to assume without loss of generality that #, and then we use (all) of Figure 2 and the inductive hypothesis.
The case of elt() for Set where . There are two sub-cases:
– Suppose atm() for some other than (we assumed # so is impossible). We reason as follows:
– Suppose st([]) where @ for some fresh (so # and level()). Note by Theorem 2.26 that # and #[]. We reason as follows:
The case of elt() for Set where . There are two sub-cases:
– Suppose atm() for some . If then we reason as follows:
If so that atm(), and atm() for some other than , then we reason as follows:
If so that atm(), and st([]) where @ for some fresh (so # and level()) then we reason as follows (note by Theorem 2.26 that # and #[]):
– Suppose st([]) where @ for some fresh (so # and level()). We reason as follows:
The case of elt() for and and Set. We reason as follows:
We consider the possibilities for Set:
If is an internal atom then we reason using (a) and (b) of Figure 2.
If is an internal comprehension then we use Lemma 3.11(2&3) for a fresh (so #), (st), and the inductive hypothesis.
Were Proposition 4.13 about the syntax of first-order logic or the -calculus, then it could be called the substitution lemma, and the proof would be a routine induction on syntax.
In fact, even in the case of first-order logic or the -calculus, the proof is not routine. Issues with binders (Figure 2 (elta), and one explicit in (st)) were the original motivation for my thesis [Gab01] and for nominal techniques in general.
For a standard non-rigorous non-nominal proof of the substitution lemma see [Bar84]; for a detailed discussion of the lemma in the context of Nominal Isabelle, see [Bar14] which includes many further references.
But the proof of Proposition 4.13 is not just a replay of the proofs; neither in the ‘classic’ sense of [Bar84] nor in the ‘nominal’ sense of [Gab01, Bar14]. This is because of the interaction of elt with the -action, mostly because of (elta) (to a lesser extent also because of the nominal binder (st)).
Suppose Pred and and Set. Suppose and and Set and suppose and and Set. Suppose # and #. Then
Suppose Pred and and Set. Suppose and and Set and suppose and and Set. Suppose # and #.14 Then
4.2.5. (id): substitution for atoms and its corollaries.
We called atm() in Definition 3.3 an internal atom. Atoms in nominal techniques interpet variables, so if we call atm() an internal atom this should suggest that atm() should behave like a variable (or a variable symbol). Rules (a) and (b) from Figure 2 are consistent with that, and Lemma 4.17 makes formal more of this intuition:
Suppose and . Then:
(1) If Pred then [atm(.
(2) If and Set then [atm(.
We reason by induction on
We consider the possibilities for Pred:
If and() for Pred or neg() for Pred then we use rules (and) and (neg) of Figure 2 and the inductive hypothesis.
If all([]) for Pred and for some then we use (all) of Figure 2 and the inductive hypothesis.
If elt()) for and and Set then we use rule (eltb) of Figure 2 and the inductive hypothesis.
If elt()) for Set then we use (eltatm) of Figure 2 and the inductive hypothesis for .
We consider the possibilities for Set:
If is an atom then we reason using (a) or (b) of Figure 2.
If is an internal comprehension then we use Lemma 3.11(2&3) for a fresh (so #), (st), and the inductive hypothesis.
Given what we have so far, Lemma 4.18 is not hard to prove.
Suppose and . Then:
If Pred and # then [atm().
If and Set and # then [atm().
4.3. Sigma-algebras and SUB.
We can now observe that our sigma-action is consistent with the nominal algebra literature in the following sense:
The syntaxes of internal predicates and internal terms, with the sigma-action from Definition 4.1, are sigma-algebras in the sense of [Gab16, GG17], and models of SUB in the sense of [GM08].
Concretely, this means that the sigma-action from Definition 4.1 and Figure 2 should
distribute through and, neg, and
distribute in a capture-avoiding manner through all, and st, and
should act on atm by direct substitution (see (a) and (b) in Figure 2), and
should satisfy the equalities in Figure 3.
Immediate from the definitions and lemmas thus far, which were designed to verify these properties.
There is redundancy in Figure 3. For instance, a nominal algebra that satisfies () satisfies (id) if and only if it satisfies (ren). One half of this implication is implicit in the proof of Lemma 4.18, which derives (ren) from (the lemmas corresponding to) () and (id); going in the other direction is no harder.
Likewise (swp) can be derived from () and (#). This does no harm: in this paper we are interested in exploring the good properties of Definition 4.1, rather than studying minimal sets of axioms for their own sake (for which see [GM08]).
We do not demand that the sigma-action should distribute through elt but this is because this is syntactically impossible: elt()[] cannot be equal to elt([]) because elt([]) is not syntax according to Figure 1.
We shall see in Subsection 4.4, however, that this all works after all, in a suitable sense, and this will become an important observation when interpreting TST in internal syntax in Section 5.
Another way to approach the proofs in this paper would be to admit elt() and an explicit substitution term-former, and orient Figure 2 as rewrite rules. We would obtain a nominal rewrite system [FG07]. Essentially this would amount to converting Figure 2 (and the proofs that use it) to a ‘small-step’ presentation, from the current ‘big-step’ form.
4.4. The sugar and its properties.
Figure 1 only permits the syntax elt(), not the syntax elt(). We can obtain the power of elt() via a more sophisticated operation which we construct out of components already available:
Suppose and Set is an internal comprehension15 and Set. Then define by
where we choose fresh (so #).
Suppose and and Set. Then define atm() and by
Suppose Pred and and and Set and #. Then (using Notation 4.23)
Suppose and Set and Set and and Set. Then:
(1)
(2) ()[[], where 1.
(3) ()[[], where .
First, suppose we have proved part 1 of this result. Then part 2 follows using Figure 2 (a) and part 3 follows using Figure 2 (b).
To prove part 1 there are three cases:
Suppose atm() for some not equal to . We reason as follows:
Suppose atm() (so that 1). There are two sub-cases:
– Suppose atm() for some . We reason as follows:
– Suppose st([]) where @ for some fresh (so #). We reason as follows:
Suppose is an internal comprehension (not an internal atom). Choose fresh (so #). We reason as follows:
Suppose and and Set and Set and #. Then
We reason as follows:
It is quite interesting to reflect on the inductive measures used in the proofs above. Collecting them a list, they are:
age() and age() in Lemmas 4.8, 4.10, and 4.17.
(level() age()) and (level() age()) in Proposition 4.6.
(level(level() age()) and (level(level() age()) in Proposition 4.13.
So we see that the inductive proofs fall into two categories:
(1) those inductive proofs that are by a direct induction on structure and are ‘fairly simple’, and
(2) those inductive proofs that depend on the hierarchy of levels and are ‘slightly harder’.
Looking deeper at the slightly harder results, the inductive quantities seem to follow a slogan of
take the sum of the levels of relevant atoms, and the age of the relevant terms, lexicographically ordered.
These inductive quantities are simple, though a certain amount of thinking was required to develop them in the first place. For future work, if e.g. a package for handling stratified syntax is implemented in a theorem-prover, then the slogan above might form the basis of a generic automated proof-method.
Though the proofs above are probably susceptible to automation by a sufficiently advanced tactic, they are not all the same.
5. The language of Typed Sets
We now have everything we need to develop the syntax of Typed Set Theory.
5.1. Syntax of Stratified Sets.
Quotienting by -equivalence means that a formula is actually an -equivalence class of syntax-trees and similarly for a term . This is a typical treatment but we could just as easily set things up differently, e.g. using nominal abstract syntax or de Bruijn indexes. Definition 5.1 as written is designed to be close to what one might find in a typical paper on TST+ or NF if the syntax were specified.16
Definition 5.3 is standard:
Suppose , , and . Then and are stratified, and , , and are not stratified.
The language of Stratified Sets consists of stratified formulae and terms.
We only care about stratified formulae and terms henceforth — that is, we restrict attention to those formulae and terms that are stratified.
So for all terms and formulae considered from now on, the reader should assume they are stratified, where:
polymorphically takes two terms of type and to a formula for each , and
sets comprehension takes an atom of type and a formula to a term of type .
We further assume that levels are arranged to respect stratification where this is required, so for example when we write [:] it is understood that we assume .
We could add equality to our syntax in Figure 4, at some modest cost in extra cases in inductive arguments. The pertinent stratification condition would be that if is a subterm then level( level(). Our results extend without issues to the syntax with equality.
5.2. Interpretation for formulae and terms.
Define an interpretation of stratified formulae and terms as in Figure 5, mapping to Pred and of level to Set.
For the reader’s convenience we give pointers for the notation used in the right-hand sides of the equalities in Figure 5:
F is from Example 3.9.
neg is from Definition 3.3.
is from Notation 4.23.
st([]) is from Definitions 2.19 and 3.3.
atm is from Definition 3.3.
Note that the translation in Figure 5 from the syntax of formulae and terms from Figure 4 to the syntax of internal predicates and internal sets from Definition 3.3 is not entirely direct: is primitive in formulae but only primitive in internal predicates if is an atom.
Define the size of a stratified formula and stratified term inductively as follows:
Suppose is a stratified formula and is a stratified term with level(. Then
By induction on size() and size():17
The case of . By Figure 5 atm(). By Definition 3.3 atm()Set.
The case of for 1 and . By Figure 5 st([]). By Definition 5.3 level . By inductive hypothesis Pred and by Definition 3.3 st([]) Set.
The case of . By Figure 5 F Pred.
The case of . From Figure 5 and Definition 3.3 using the inductive hypothesis.
The case of . From Figure 5 and Definition 3.3 using the inductive hypothesis.
The case of . From Figure 5 and Definition 3.3 using the inductive hypothesis.
The case of . We refer to Notation 4.23 and use Lemma 3.11 and Proposition 4.6.
5.3. Properties of the interpretation.
Suppose is a stratified formula and , and are stratified terms and . Then:
Note by Lemma 5.11 that Setlevel so that the -action [] above is well-defined (Definition 4.1).
By induction on size() and size(). We consider each case in turn; the interesting case is for , where we use Lemma 4.26:
The case of . We reason as follows:
The case of . We reason as follows:
The case of . We reason as follows:
The case of . We reason as follows, where we -rename if necessary to assume # (from which it follows by Theorem 2.26 that #):
The case of . By Figure 5 atm(). By assumption Setlevel so by Figure 2 (a)
The case of (any atom other than ). By Figure 5 atm(). We use rule (b) of Figure 2.
The case of . -converting if necessary assume is fresh (so #, and by Theorem 2.26 also #). We reason as follows:
The case of . We reason as follows:
Suppose is a stratified formula and is a stratified term. Suppose and level(. Then:
(1)
(2)
We reason as follows:
5.4. Confluence.
The natural injection of internal predicates and internal terms into stratified formulae and terms is clear; to save notation we elide it, thus effectively treating the syntax of internal predicates and terms from Definition 3.3 as a direct subset of the syntax of stratified formulae and terms from Figure 4. The reader who dislikes this abuse of notation can fill in an explicit injection function as required, to map the former injectively into the latter. Either way, the meaning will be the same.
Call a formula of the form a reduct.
considered as a formula, is a -normal form, and similarly for .
Reducts are impossible because the internal syntax from Figure 1 only allows us to form (written elt() in that figure) when is an atom and not a comprehension.
We can now state a kind of converse to Lemma 5.17:
(1) By induction on syntax. The interesting case is for . Suppose . Then
(2) By induction on the derivation of the rewrite (that is, on the term-context in which the rewrite takes place). We consider three cases:
Suppose [:]. By Lemma 5.13 [:].
Suppose because because . By induction hypothesis . Then using Lemma 5.13 we have
Suppose because . By induction hypothesis . We have
(3) We combine parts 1 and 2 of this result.
5.5. Strong normalisation.
Call a comprehension ternary when occurs in at least three times.18 If occurs in zero, one, or two times then we call non-ternary.
Call a formula ternary if every comprehension in it is ternary.
Call a term ternary if every comprehension in it is ternary.
Suppose is a formula and is a term. Write na() and na() for the predicate or term obtained by padding every non-ternary comprehension in or to
where .19
Suppose is a formula and is a term. Then:
(1) na() and na() are ternary.
(2) If and are ternary then [:] is ternary. Similarly for [:].
(3) If is ternary and then is ternary. Similarly for .
(1) By construction.
(2) By an easy calculation.
(3) By an easy calculation from Figure 6 and part 2 of this result.
Define the complexity of a stratified formula and stratified term as follows:
Define the number of atomic reducts of and as follows:
(1) If we view as and as then an atomic reduct is just a term of the form (). Then atomic counts the number of atomic reducts in formulae and terms , and cplx is a measure of size in which atomic reducts are skipped. Indeed, though we never use this directly, from Definition 5.10 we see that
and similarly for .
(2) Intuitively, cplx( means “ has the same complexity as ”. Technically, cplx( makes Lemma 5.24(2) hold, and allows the arithmetic in Lemma 5.26 to go through.
Suppose is a term and is a predicate. Then:
(1) cplx() 1.
(2) cplx() 3.
(3) If is not an atom (so it is a comprehension) then cplx() 4.
By calculations and induction using Definition 5.22; the base cases are and (in particular, ).
Suppose is a predicate and is a term. Suppose is an atom and is a term and level( level() (so the substitution [:] is well-defined). Then:
(1) If is an atom then
(2) If is not an atom (so is a comprehension) then
where is the number of instances of in or .
(1) By a routine induction on and using Definition 5.22.
(2) Essentially this is clear because we replace instances of each with complexity 1, with instances of each with complexity cplx(). The proof is by induction on syntax using Definition 5.22. Interesting cases of the induction are or that do not mention (so ), , , and . We consider each in turn:
If or do not mention then [: and [: and the result follows.
It is a fact that cplx( cplx(, and we calculate as follows:
It is a fact that cplx(, and we calculate as follows:
It is a fact that cplx( cplx(), and we calculate as follows:
Suppose is ternary (so mentions free at least three times) and is a term and level( level(). Then:
(1) If is an atom then
(2) If is not an atom then
If is ternary and then precisely one of the following must hold:
cplx() cplx() (in words: complexity increases).
cplx( cplx() and atomic() atomic() (in words: atomic reducts decrease).
Similarly for .
The rewrite system from Figure 6 is terminating (no infinite chain of rewrites).
We consider just the case of reducing formulae; reducing terms is no harder.
na() is just an annotated copy of , so if has an infinite chain of rewrites then so must na().20 We see that it would suffice to prove that reductions from na() are terminating.
So suppose na(, and is ternary (apply na if required). Consider and suppose . From Theorem 5.18 , and by Corollary 5.27(1)
Thus the set cplx() is bounded above by cplx(). It follows using Corollary 5.27(1&2) and considering the measure
lexicographically ordered, that any chain of reductions from must terminate.
The proof of Proposition 5.28 is not difficult.21 This is in itself interesting:
We noticed in Remark 1.6 how stratified syntax can be viewed as a fragment of the simply-typed -calculus, where corresponds to a -reduct and extensionality corresponds to an -expansion. Yet, the direct proof of strong normalisation for the simply-typed -calculus is quite different and seems harder than the proof of Proposition 5.28 (a concise but clear presentation is in Chapter 6 of [GTL89]).
Formulae and terms of Stratified Sets, with the rewrites from Figure 6, are confluent and strongly normalising.
So from Theorems 5.30 and 4.19 we see that:
(1) the syntax of formulae and terms has normal forms, and furthermore
(2) normal forms with the natural substitution action given by substitute-then-renormalise, corresponds precisely to the theory of internal predicates and terms from Definition 3.3 and 4.1, and furthermore
(3) this theory of normal forms is an instance of the notion of nominal algebras for substitution, also called sigma-algebras, as used in the previous literature studying -calculus, first-order logic, and pure substitution [GG17, Gab16, GM08].
Recall from Remarks 1.1 and 1.2 that in stratifiable syntax, as used in Quine’s NF, variables do not have predefined levels but we insist on a stratifiability condition that and are only legal if we could assign levels to their variables to stratify them. We obtain as an easy corollary:
Formulae and terms of stratifiable syntax, with the rewrites from Figure 6, are confluent and strongly normalising.
6. Conclusions and future work
Stratified Sets occupy a nice middle ground between ZF sets and simple types. They typically appear used as a foundational syntax. However, we have seen in this paper that Typed-Sets-the-syntax in and of itself forms a well-behaved rewrite system, and a well-behaved nominal algebra. This had not previously been noted, and this paper gives a reasonably full and detailed account of how rewriting and nominal algebra apply. This account is intended to be suitable for
readers familiar with rewriting who are unfamiliar with stratified sets syntax22
readers familiar with stratified sets syntax but unfamiliar with techniques from rewriting and nominal algebra.
We have also tried to smooth a path to implementing these proofs in a machine, hopefully in a nominal context. We have designed the proofs to be friendly to such an implementation as future work, yet without compromising readability for humans. Where we have cut corners (relative to a machine implementation), we tried to signpost this fact (see for instance Remark 4.2 and Notation 5.15).
Concerning other applications, it is often possible to use normal forms to build denotations. In some contexts, the normal form is the denotation of the terms that reduce to it. That will not work for Stratified Sets because we are usually interested in imposing additional axioms. But there are standard things that can be done about that, and this has been investigated in a nominal context in papers like [Gab16, GG17]. These papers build denotations for first-order logic and the -calculus using maximally consistent sets, and using nominal techniques to manage binding in denotations (extending how we used nominal techniques in this paper to manage binding in syntax). Having normal forms is useful here and the ideas in this paper can be used to give a denotational analysis of theories in the languages of Stratified and Stratifiable Sets. This is future work.
We can ask about a converse to Theorems 5.30 and 5.32. We have shown that a stratifiable formula rewrites to a normal form. Now if a formula (without levels) rewrites to normal form, is it stratifiable? We see that we cannot hope for a perfect converse by the following easy example: if we write then is not stratifiable but it rewrites to , which is stratifiable for instance as , which we could also write just as . However there may be special cases in which stratification information can be recovered from normalisation, and this is future work.
References
[Bar84]Henk P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, 1984.
[Bar14]Barendregt’s substitution lemma, June 2014. http://isabelle.in.tum.de/nominal/example.html, retrieved 2014/June/8.
[DG12a]Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Transactions on Computational Logic, 13(3), 2012.
[DG12b]Gilles Dowek and Murdoch J. Gabbay. PNL to HOL: from the logic of nominal sets to the logic of higher-order functions. Theoretical Computer Science, 451:38–69, 2012.
[FG07]Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, June 2007.
[For95]Thomas E. Forster. Set theory with a universal set: exploring an untyped universe. Clarendon Press, 1995.
[For97]Thomas E. Forster. Quine’s NF, 60 years on. American Mathematical Monthly, 104(9):838–845, 1997.
[Gab01]Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, University of Cambridge, UK, March 2001.
[Gab11]Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.
[Gab16]Murdoch J. Gabbay. Semantics out of context: nominal absolute denotations for first-order logic and computation. Journal of the ACM, 63(3):1–66, June 2016.
[Gab17]Murdoch J. Gabbay. Equivariant ZFA and the foundations of nominal techniques. Submitted. See arXiv preprint arxiv.org/abs/1801.09443, 2017.
[Gab18]Murdoch J. Gabbay. Equivariant ZFA with choice: a position paper. In Proceedings of the 25th Automated Reasoning Workshop (ARW 2018), March 2018. See arXiv preprint arxiv.org/abs/1803.08727.
[GG17]Murdoch J. Gabbay and Michael J. Gabbay. Representation and duality of the untyped lambda-calculus in nominal lattice and topological semantics, with a proof of topological completeness. Annals of Pure and Applied Logic, 168:501–621, March 2017.
[GM06]Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In Proceedings of the 3rd International Colloquium on Theoretical Aspects of Computing (ICTAC 2006), volume 4281 of Lecture Notes in Computer Science, pages 198–212, Berlin, November 2006. Springer.
[GM08]Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 2008.
[GM09]Murdoch J. Gabbay and Aad Mathijssen. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, December 2009.
[GP01]Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, July 2001.
[Gri04]Nicholas Griffin. The Prehistory of Russell’s Paradox. In Godehard Link, editor, One Hundred Years of Russell’s Paradox, number 6 in Series in Logic and Its Applications. De Gruyter, 2004.
[GTL89]Jean-Yves Girard, Paul Taylor, and Yves Lafont. Proofs and types. Cambridge University Press, 1989.
[Hol98]Randall Holmes. Elementary set theory with a universal set, volume 10. Centre National de recherches de Logique, 1998.
[Jec06]Thomas Jech. Set theory. Springer, 2006. Third edition.
[Joh03]Peter T. Johnstone. Sketches of an Elephant: A Topos Theory Compendium, volume 43 and 44 of Oxford Logic Guides. OUP, 2003.
[KA10]Chantal Keller and Thorsten Altenkirch. Hereditary substitutions for simple types, formalized. In Proceedings of the third ACM SIGPLAN workshop on Mathematically structured functional programming, pages 3–10. ACM, 2010.
[MM92]Saunders Mac Lane and Ieke Moerdijk. Sheaves in Geometry and Logic: A First Introduction to Topos Theory. Universitext. Springer, 1992.
[Pit13]Andrew M. Pitts. Nominal Sets: Names and Symmetry in Computer Science. Cambridge University Press, May 2013.
[Urb08]Christian Urban. Nominal reasoning techniques in Isabelle/HOL. Journal of Automatic Reasoning, 40(4):327–356, 2008.
[Wad89]Philip Wadler. Theorems for free! In Proceedings of the 4th International Conference on Functional Programming Languages and Computer Architecture, pages 347–359. ACM, 1989.
[WCPW03] Kevin Watkins, Iliano Cervesato, Frank Pfenning, and David Walker. A concurrent logical framework: The propositional fragment. In International Workshop on Types for Proofs and Programs, pages 355–377. Springer, 2003.
This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany
Notes
1It still needs to be stratified, of course, but by Russell’s paradox we must expect our party to be spoiled. Our choices are only: how, and where? ↩
2Two attitudes are possible with types: embrace and enrich them, which leads us in the direction of (for instance) dependent types, or minimise type structure. Stratification minimises types all the way down to just being ‘’. ↩
3There are also differences: In [KA10] the authors implement their proof in Agda, whereas implementation of the proofs in this paper for future work. On the other hand, proofs in this paper are given more-or-less in full, whereas in [KA10] the authors elide technical details. This paper proves confluence and strong normalisation, which is strictly more than [KA10] which considers only the existence of a reduction path to normal forms. ↩
4These will serve as variable symbols in Definition 3.3. ↩
5This is not necessarily true if is infinite. For instance if we take X then the reader can verify that # for every , but # does not hold for any . This is a feature of nominal techniques, not a bug; but for the case of finite sets, things are simpler. ↩
6First-order logic with equality , sets membership , and a constant or collection of constants for sets of atoms. ↩
7It is important to realise here that must contain all the variables mentioned in the predicate. It is not the case that if and only if — but it is the case that if and only if (both are false). ↩
8In the implementation of FM set theory in my PhD thesis [GP01] this was literally true: I found it convenient to use Quine atoms, meaning that . ↩
9This too can be made precise. See Subsection 2.6 and Lemma 4.17 of [DG12b]. ↩
10Finally, we can be somewhat more precise about the effort these free equivariance deductions can save: With equivariance, the cost of deducing (), given a deduction of (), is 1. Without equivariance, the cost of deducing (), given a deduction of (), is roughly where is the cost of deducing (). This is convenient in a rigorous but unmechanised proof such as the one in this paper; in an implementation it can quadratically reduce effort by saving roughly effort for each . This is the difference between -equivalence and renaming lemmas being a minor consideration, and them inflating to dominate the development. My feeling is that once renaming lemmas consume more than 80% of the developmental effort, development stalls. ↩
11So every internal comprehension or internal atom is an internal set. Another choice of terminology would be to call atm() an internal atom, st([]) an internal set, and atm() or st([]) internal elements. However, note that st([]) is not a set and neither is atm(); they are both syntax and we can call them what we like. ↩
12By concrete calculations or by Theorem 2.26. ↩
was chosen no greater than the minimum level of , , and . Now st([]), and it follows from Definition 4.4 that level(). ↩
14We expect a stronger version of Corollary 4.16 to be possible in which we do not assume #. However, the proof would require an induction resembling the proof of Proposition 4.13 — the proof assuming # can piggyback on the induction already given in Proposition 4.13. We will not need this stronger version, so we do not bother. ↩
15Terminology from Notation 3.4. So has the form st([]@) for some with #, and does not have the form atm() for any . ↩
16...which it typically is not. For instance [For95] does not formally define its syntax e.g. via an inductive definition in the style of Definition 5.1, and this is not unusual. ↩
17A structural induction on nominal abstract syntax [GP01] would also work, and in a nominal mechanised proof might be preferable. Similarly for Proposition 5.12. ↩
18This is arguably an abuse of notation; ‘ternary’ might suggest exactly three times. But we need a name. ↩
19The precise choice of does not matter since we bind it with . The level matters, so the result is stratified. ↩
20In a machine implementation we would probably want to refine Definition 5.20 to annotate with for a fresh constant-symbol or variable symbol (one for each level), instead of (). This would make it easier to automatically track the annotations. ↩
21...but not trivial. Thanks to an anonymous referee for spotting my errors. ↩
22Stratified sets syntax is not hard to define — but it requires experience to learn what kinds of predicates are and are not stratifiable. In use, stratifiability is a subtle and powerful condition. ↩