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

THE LANGUAGE OF STRATIFIED SETS IS CONFLUENT AND STRONGLY NORMALISING

MURDOCH J. GABBAY

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 s = {a | a ∉a} then s ∈s if and only if s ∉s. One way to avoid the term s is to restrict to the language of Stratified Sets. This is first-order logic with a binary relation t∈s whose intuition is ‘t is an element of s’ and:

• Variable symbols a (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 t∈s if the level of s is one plus the level of t. level(s) = level(t)+1.

See Definition 5.3 for full details. Then s = {a | a ∉a} cannot be stratified, since whatever level we assign to a in a ∈a we cannot make level(a) = level(a)+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 {a ∈X | φ}.

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

univ = {a | ⊤}

is easily stratified by giving a any level we like. Likewise we can write definitions such as ‘the number 2’ to be ‘the set of all two-element sets’:

2 = {a | ∃b, c.(a = {b, c} ∧b ≠ c)}

(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

t ∈{a | φ} → φ[a:=t].

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.

Remark 1.1

‘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) a1 ∈b2 (choosing a level 1 variable symbol a and a level 2 variable symbol b), whereas in NF we could write just a ∈b and say “we could assign a level 1 and b level 2”.

Remark 1.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.

Remark 1.3

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.

Remark 1.4 (Some words on terminology).

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.

Remark 1.5 (References).

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

Remark 1.6 (Connection to the λ-calculus).

One way to see that something like this paper should work, fingers crossed, is by an analogy:

• The rewrite t ∈{a | φ} →φ[a:=t] can be rewritten as (λa.φ)t →φ[a:=t].

• Extensionality is s = {b | b ∈s}, and we can rewrite this as s = λb.(sb).

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 ∈ X may ‘contain’ finitely many names a, b, c ∈𝔸”. 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 x 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.

Definition 2.1

• For each i∈ℤ fix a disjoint countably infinite set 𝔸i of atoms.4

• Write 𝔸 = ⋃i∈ℤ 𝔸i.

• If a∈𝔸 (so a is an atom) write level(a) for the unique number such that a∈𝔸level(a).

• We use a permutative convention that a, b, c, . . . range over distinct atoms.

If we do not wish to use the permutative convention then we will refer to the atom using n (see for instance (σeltatm) of Figure 2).

2.1.2. Permutation actions on sets.

Definition 2.2

Suppose π : 𝔸 ∼= 𝔸 is a bijection on atoms.

(1) If nontriv(π) = {a | π(a) ≠ a} is finite then we call π finite.

(2) If π(a) ∈𝔸i ⇔a ∈𝔸i 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:

Notation 2.3

(1) Write id for the identity permutation such that id(a) = a for all a.

(2) Write π′ ◦π for composition, so that (π′ ◦π)(a) = π′(π(a)).

(3) If i∈ℤ and a, b∈𝔸i then write (a b) for the swapping (terminology from [GP01]) mapping a to b, b to a, and all other c to themselves, and take (a a) = id.

(4) Write π-1 for the inverse of π, so that π-1 ◦π = id = π ◦π-1.

2.1.3. Sets with a permutation action.

Notation 2.4

If A ⊆𝔸 write

fix(A) = {π | ∀a∈A.π(a) = a}.
Definition 2.5

A set with a permutation action X is a pair (|X|, ·) of an underlying set |X| and a permutation action written π·x which is a group action on |X|, so that id·x = x and π·(π′·x) = (π ◦π′)·x for all x ∈ X and permutations π and π′.

Definition 2.6

(1) Say that A ⊆𝔸 supports x ∈ X when ∀π.π ∈ fix(A) ⇒π·x = x.

(2) If a finite A ⊆𝔸 supporting x exists, call x finitely supported (by A) and say that x has finite support.

Notation 2.7

If X is a set with a permutation action then we may write

• x ∈ X as shorthand for x ∈|X|, and

• X ⊆ X as shorthand for X ⊆|X|.

2.1.4. Nominal sets.

Definition 2.8

Call a set with a permutation action X a nominal set when every x ∈ X has finite support. X, Y, Z will range over nominal sets.

Definition 2.9

Call a function f ∈ X⇒Y equivariant when π·(f(x)) = f(π·x) for all permutations π and x ∈ X. In this case write f : X⇒Y.

The category of nominal sets and equivariant functions between them is usually called the category of nominal sets.

Definition 2.10

Suppose X is a nominal set and x ∈ X. Define the support of x by

supp(x) =⋂{A⊆𝔸 | A is finite and supports x}.
Notation 2.11

• Write a#x as shorthand for a ∉ supp(x) and read this as a is fresh for x.

• If T⊆𝔸 write T #x as shorthand for ∀a∈T.a#x.

• Given atoms a1, . . . , an and elements x1, . . . , xm write a1, . . . , an#x1, . . . , xm as shorthand for ∀1≤j≤m.{a1, . . . , an}#xj. That is: ai#xj for every i and j.

Theorem 2.12

Suppose X is a nominal set and x ∈ X. Then supp(x) is the unique least finite set of atoms that supports x.

Proof

See [Gab11, Theorem 2.21(1)].End of proof

Corollary 2.13

(1) If π(a) = a for all a ∈ supp(x) then π·x = x. Equivalently:

(a) If π∈fix(supp(x)) then π·x = x.

(b) If ∀a∈𝔸.(π(a)≠a ⇒a#x) then π·x = x (see Notation 2.11).

(2) If π(a) = π′(a) for every a∈supp(x) then π·x = π′·x.

(3) a#x if and only if ∃b.(b#x ∧ (b a)·x = x).

Proof

By routine calculations from the definitions and from Theorem 2.12 (see also [Gab11, Theorem 2.21(2)]).End of proof

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 π·a = π(a).

2.2.2. Cartesian product.

X × Y is a nominal set with underlying set {(x, y) | x ∈ X, y ∈ Y} and the pointwise action π·(x, y) = (π·x, π·y).

It is routine to check that supp((x, y)) = supp(x)∪supp(y).

2.2.3. Full function space.

X→Y is a set with a permutation action with underlying set all functions from |X| to |Y|, and the conjugation permutation action

(π·f)(x) = π·(f(π-1·x)).

2.2.4. Finite-supported function space.

X⇒Y 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.

Definition 2.14

Suppose Z is a set with a permutation action. Give subsets Z ⊆ Z the pointwise permutation action

π·Z = {π·z | z ∈Z}.

Then pset(Z) (the full powerset of Z) is a set with a permutation action with

• underlying set {Z | Z ⊆ Z} (the set of all subsets of |Z|), and

• the pointwise action π·Z = {π·z | z ∈Z}.

A particularly useful instance of the pointwise action is for sets of atoms. As discussed in Subsection 2.2.1 above, if a ∈𝔸 then π·a = π(a). Thus if A ⊆𝔸 then

π·A means {π(a) | a ∈A}.
Lemma 2.15

Even if Z is a nominal set, pset(Z) need not be a nominal set.

Proof

Take Z = 𝔸 which we enumerate as {a0, a1, a2, . . . } and we take Z ∈ pset(Z) to be equal to comb defined by

comb = {a0, a2, a4, . . . }.

This does not have finite support (see also [Gab11, Remark 2.18]).End of proof

2.2.6. Finite powerset.

For this subsection, fix a nominal set X.

Definition 2.16

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.

Notation 2.17

We might write X ⊆fin X for X∈FinPow(X).

Lemma 2.18

If X ⊆fin X then:

(1) ⋃{supp(x) | x∈X} is finite.

(2) ⋃{supp(x) | x∈X} = supp(X).

(3) x ∈X implies supp(x) ⊆ supp(X).

Rewriting this using Notation 2.11: if X is finite and x∈X then a#X implies a#x.5

Proof

The first part is immediate since by assumption there is some finite A⊆𝔸 that bounds supp(x) for all x ∈X. 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.End of proof

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 i∈ℤ.

Definition 2.19

Let the atoms-abstraction set [𝔸i]X have

• Underlying set {[a]x | a∈𝔸i, x ∈ X} where [a]x = {(π(a), π·x) | π ∈ fix(supp(x)\{a})}.

• Permutation action π·[a]x = [π·a]π·x.

Lemma 2.20

If x∈X and a∈𝔸i then supp([a]x) = supp(x)\{a}. In particular a#[a]x (Notation 2.11).

Proof

See [Gab11, Theorem 3.11].End of proof

Lemma 2.21

Suppose x∈X and a, b∈𝔸i. Then if b#x then [a]x = [b](b a)·x.

Proof

See [Gab11, Lemma 3.12].End of proof

Definition 2.22

Suppose z∈[𝔸i]X and b∈𝔸i. Write z@b for the unique x ∈ X such that z = [b]x, if this exists.

Lemma 2.23

Suppose b∈𝔸i and z ∈ [𝔸i]X. Then b#z implies z@b ∈ X is well-defined.

Proof

See [Gab11, Theorem 3.19].End of proof

Lemma 2.24

Suppose a∈𝔸i and x∈X and z ∈ [𝔸i]X. Then:

(1) ([a]x)@a = x and if b#x then ([a]x)@b = (b a)·x.

(2) If a#z then [a](z@a) = z.

Proof

See [Gab11, Theorem 3.19].End of proof

2.3. The principle of equivariance.

Remark 2.25

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:

Theorem 2.26

Suppose x is a list x1, . . . , xn. Suppose π is a (not necessarily finite) permutation and write π·x for π·x1, . . . , π·xn. Suppose Φ(x) is a first-order logic predicate in the language of ZFA6 with free variables x. Suppose Υ(x) is a function specified using a first-order predicate in the language of ZFA with free variables x.

Then we have the following principles:

(1) Equivariance of predicates. Φ(x) ⇔ Φ(π·x).7

(2) Equivariance of functions. π·Υ(x) = Υ(π·x).

(3) Conservation of support. If x denotes elements with finite support then supp(Υ(x)) ⊆ supp(x1)∪· · · ∪supp(xn).

Proof

See Theorem 4.4, Corollary 4.6, and Theorem 4.7 from [Gab11].End of proof

Remark 2.27

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 φ(a, b, c), then

• taking π = (a c) we also know φ(c, b, a) and

• taking π = (a a′)(b b′)(c c′) we also know φ(a′, b′, c′), but

• we do not necessarily know that we can deduce φ(a, b, a) (depending on φ this may still hold, of course, but not by equivariance since no permutation takes (a, b, c) to (a, b, a)).

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

a ∈𝔸iatm(a) ∈Seti(κ)X ⊆fin Pred(κ) and(X) ∈Pred(κ+1)X∈Pred(κ) neg(X) ∈Pred(κ+1)X∈Pred(κ) a∈𝔸iall([a]X)∈Pred(κ+1)a∈𝔸i+1 x∈Seti(κ) elt(x, a) ∈Pred(κ+1)X∈Pred(κ) a∈𝔸i-1st([a]X)∈Seti(κ+1)
Figure 1: Syntax of internal predicates and terms
Proposition 2.28

(1) supp(π·x) = π·supp(x) (which means {π(a) | a ∈ supp(x)}).

(2) a#π·x (Notation 2.11) if and only if π-1(a)#x, and a#x if and only if π(a)#π·x.

Proof

Immediate consequence of part 2 of Theorem 2.26 (for the ‘not-free’ proof by concrete calculations see [Gab11, Theorem 2.19]).End of proof

3. Internal syntax

3.1. Basic definition.

Remark 3.1

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 a#X corresponds to “a is not free in X”.

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

Notation 3.2

Write ℤ for the integers, so ℤ = {0, 1, -1, 2, -2, . . . } and ℕ for the natural numbers, which we start at 0, so ℕ = {0, 1, 2, . . . }.

Definition 3.3

(1) Define datatypes

• Pred of internal predicates and

• Seti for i∈ℤ of internal (level i) sets inductively by the rules in Figure 1, where κ ranges over finite ordinals.

(2) Define

Pred = ⋃κ Pred(κ) and Seti = ⋃κ Seti(κ).

(3) Write age(X) for the least κ such that X∈Pred(κ).

(4) Write age(x) for the least κ such that x∈Seti(κ).

Notation 3.4

• If a∈𝔸 we may call atm(a) an internal atom.

• If X∈Pred we may call st([a]X) an internal comprehension.

• We may call atm(a) or st([a]X) an internal set.11

Remark 3.5

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:

x ∈Set ::= atm(a) | st([a]X) X ∈Pred ::= and(X) | neg(X) | all([a]X) | elt(x, a)

(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([a]X) as ‘for all a, X’ or in symbols: ‘∀a.φ’. In all([a]X), [a]X 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(x, a) as ‘x is an element of a’. Note here that a is an atom; it does not literally have any elements. elt(x, a) represents the predicate ‘we believe that x is an element of the variable a’, or in symbols: ‘x ∈a’.

(7) st([a]X) represents sets comprehension; read st([a]X) as ‘the set of a such that X’ or in symbols: ‘{a | X}’. Again, as standard in nominal techniques, nominal atoms-abstraction is used to represent the binding.

If a∈𝔸i then st([a]X)∈Seti+1.

(8) atm(a) is a copy of a∈𝔸 wrapped in some formal syntax atm.

Lemma 3.6

Suppose X∈Pred and i∈ℤ and a, a′∈𝔸i and a′#X. Then:

(1) st([a]X) = st([a′](a′ a)·X) and all([a]X) = all([a′](a′ a)·X).

(2) a#st([a]X) and a#all([a]X), and supp(st([a]X)), supp(all([a]X)) ⊆ supp(X)\{a}.

(3) For every finite S ⊆fin 𝔸i there exist b ∈𝔸i\S and Y ∈Pred such that st([a]X) = st([b]Y) and all([a]X) = all([b]Y).

Proof

Immediate from Lemma 2.21, and Lemma 2.20 with Theorem 2.26.End of proof

Lemma 3.7

Suppose i∈ℤ and a, b ∈𝔸i and X ∈ Pred and x ∈ Set. Then age(X) = age((a b)·X) and age(x) = age((a b)·x).

Proof

Direct from Theorem 2.26(2).End of proof

3.2. Some notation.

Notation 3.8

Suppose X, Y ∈Pred and X ⊆fin Pred. Define syntactic sugar or(X), imp(X, Y) and iff(X, Y) by

or(X) = neg((and({neg(X) | X ∈X}))) imp(X, Y ) = or({neg(X), Y }) iff(X, Y ) = and({imp(X, Y ), imp(Y, X)}).
Example 3.9

Define F ∈ Pred and T ∈ Pred by

F = or(∅) and T = and(∅).

Intuitively, F represents the empty disjunction, and T represents the empty conjunction.

Notation 3.10

Suppose that:

• i∈ℤ and

• x = st(x′)∈Seti is an internal comprehension where x′ ∈ [𝔸i-1]Pred and a′∈𝔸i-1 and

• a′#x (equivalently12 a′#x′).

Then write

x@a′ for x′@a′.

Lemma 3.11 checks that Notation 3.10 makes sense:

Lemma 3.11

Suppose i∈ℤ and a′∈𝔸i-1. Suppose x∈Seti is an internal comprehension and a′#x and X′ ∈ Pred. Then:

(1) x@a′ is well-defined and x@a′ ∈ Pred.

(2) x = st([a′](x@a′)).

(3) If age(x) = κ+1 then age(x@a′) = κ (meaning that in an inductive argument using age, taking x@a′ strictly decreases the inductive measure).

(4) (st([a′]X′))@a′ = X′.

Proof

(1) By construction and Lemma 2.23.

(2) By construction and Lemma 2.24(2).

(3) By construction and Lemma 3.7.

(4) By construction and Lemma 2.24(1).End of proof

Recall F=or(∅) from Example 3.9.

Definition 3.12

Suppose i∈ℤ and a∈𝔸i-1. Define empti and seti by

empti = st([a]F) = st([a]or(∅)) seti = st([a]T) = st([a]and(∅)).

We conclude with an easy lemma:

Lemma 3.13

Suppose i∈ℤ and a∈𝔸i-1. Then:

(1) empti@a = F and st([a]F) = empti, and similarly seti@a = T and st([a]T) = seti.

(2) a#F and a#T.

(3) Definition 3.12 does not depend on the choice of a∈𝔸i-1.

Proof

(1) From Definition 3.12 and Lemma 2.24(1).

(2) From part 1 of this result, since a#F and a#T by Theorem 2.26.

(3) From part 2 of this result, using Corollary 2.13.End of proof

(σand) (and(X))[a↦→x] = and({X[a↦→x] | X∈X})(σneg) (neg(X))[a↦→x] = neg((X[a↦→x]))(σall) b#x ⇒ (all([b]X))[a↦→x] = all([b](X[a↦→x]))(σeltatm) (elt(y, a))[a↦→atm(n)] = elt(y[a↦→atm(n)], n)(σelta) (elt(y, a))[a↦→st([a′]X′)] = X[a′↦→y[a↦→st([a′]X′)]](σeltb) (elt(y, b))[a↦→x] = elt(y[a↦→x], b)(σa) atm(a)[a↦→x] = x(σb) atm(b)[a↦→x] = atm(b)(σst) c#x ⇒ st([c]X)[a↦→x] = st([c](X[a↦→x]))
Figure 2: The sigma-action (Definition 4.1)

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.

Definition 4.1

Define a σ-action (sigma-action) to be a family of functions

σi : Pred × 𝔸i × Seti →Pred and σij : Setj × 𝔸i × Seti →Setj

where i, j∈ℤ, inductively by the rules in Figure 2. For readability we write

σi(Z, a, x) as Z[a↦→x] and σi(z, a, x) as z[a↦→x].

Furthermore in Figure 2:

• In rule (σand), X⊆finPred.

• In rule (σneg), X∈Pred.

• In rule (σall), X∈Pred and b∈𝔸j for some j∈ℤ.

• In rule (σelta), a′∈𝔸i-1.

• In rule (σeltatm), n ranges over all atoms in 𝔸i (not just those distinct from a).

• In rule (σeltb), b∈𝔸j for some j∈ℤ.

• In rule (σst), X∈Pred and c∈𝔸k for some k∈ℤ.

Remark 4.2

Figure 2 slips in no fewer than three abuses of the mathematics:

(1) We do not know that X ∈ Pred implies X[a↦→x] ∈ Pred, so we should not write and({X[a↦→x] | . . . }) on the right-hand side of (σand), or indeed X[a↦→x] 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 a′∈𝔸i-1 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 X (on the right-hand side) is smaller than elt(y, a) (on the left-hand side). The level of a′ is strictly lower than the level of a, however levels are taken from ℤ which is totally ordered but not well-ordered by ≤.

In fact:

• X ∈ Pred does indeed imply X[a↦→x] ∈ Pred.

• The choice of fresh a′ 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.

Remark 4.3 (Why ‘minimum level’).

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.

Definition 4.4

Define minlevel(Z) and minlevel(z) the minimum level of Z or z, inductively on Z∈Pred and z∈Seti for i∈ℤ as follows:

minlevel(atm(a)) = level(a)minlevel(and(X)) = min({0} ∪{minlevel(X) | X∈X})minlevel(neg(X)) = minlevel(X) minlevel(all([a]X)) = min({level(a), minlevel(X)}) minlevel(elt(x, a)) = min({minlevel(x), level(a)}) minlevel(st([a]X)) = min({level(a), minlevel(X)})

Above, min(I) is the least element of I ⊆fin ℤ. 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:

Notation 4.5

• Define minlevel(a) = level(a).

• If l = (l1, l2, . . . , ln) is a list of elements from Pred ∪⋃i∈ℤ Seti ∪𝔸 then we write minlevel(l) for the least element of {minlevel(l1), . . . , minlevel(ln)}.

Proposition 4.6

Suppose i∈ℤ and a∈𝔸i and x∈Seti.

(1) If Z∈Pred then

• Z[a↦→x] is well-defined,

• minlevel(Z[a↦→x])≥minlevel(Z, a, x), and

• Z[a↦→x]∈Pred.

(2) If k∈ℤ and z∈Setk then

• z[a↦→x] is well-defined,

• minlevel(z[a↦→x])≥minlevel(z, a, x), and

• z[a↦→x]∈Setk.

Proof

Fix some k∈ℤ. We prove the Proposition for all Z, a, x and z, a, x with minlevel(Z, a, x)≥k and minlevel(z, a, x)≥k, by induction on

(level(a), age(Z)) and (level(a), age(z))

lexicographically ordered. Since k was arbitrary, this suffices to prove it for all Z, a, x and z, a, x.

We consider the possibilities for Z∈Pred:

• The case of and(X) for X ⊆fin Pred.

By Figure 2 (σand) Z[a↦→x]=and({X′[a↦→x]|X′∈X}). We use the inductive hypothesis on each X′[a↦→x] and some easy arithmetic calculations.

• The case of neg(X′) for X′∈Pred. By Figure 2 (σneg) Z[a↦→x] = neg((X′[a↦→x])). We use the inductive hypothesis on X′[a↦→x].

• The case of all([b]X′) for X′∈Pred and b∈𝔸j for some j∈ℤ.

Using Lemma 3.6(1) we may assume without loss of generality that b#x. By Figure 2 (σall) (all([b]X′))[a↦→x] = all([b′](X[a↦→x])). We use the inductive hypothesis on X′[a↦→x].

• The case of elt(z, a) for z∈Seti-1. There are two sub-cases:

– Suppose x=atm(n) for some n∈𝔸i. By Figure 2 (σeltatm) (elt(z, a))[a↦→x] = elt(z[a↦→atm(n)], n). We use the inductive hypothesis on z[a↦→atm(n)].

– Suppose x=st([a′]X′) where X′ = x@a′ for some fresh a′∈𝔸i-1 (so a′#x, z). By Figure 2 (σelta) (elt(z, a))[a↦→x] = X′[a′↦→z[a↦→x]]. We have the inductive hypothesis on z[a↦→x]. We also have the inductive hypothesis (since k≤level(a′)=i-1 ⪇i=level(a))13 on X′[a′↦→z[a↦→x]], and this suffices.

• The case of elt(z, c) where c∈𝔸k and z∈Setk-1 and k∈ℤ. By Figure 2 (σeltb) and the inductive hypothesis.

We consider the possibilities for z∈Setk:

• The case that z is an internal atom. We use (σa) or (σb) of Figure 2.

• The case that z is an internal comprehension.End of proof

Choose fresh c∈𝔸k-1 (so c#x, z), so that by Lemma 3.11(2) z = st([c]z@c). We use the first part of this result and Figure 2 (σst).End of proof

4.2. Nominal algebraic properties of the sigma-action.

Remark 4.7

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 a is not free in t then t[a↦→s] = t”, 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.

(σα) b′#Z ⇒ Z[b↦→y] = ((b′ b)·Z)[b′↦→y](σ#) b#Z ⇒ Z[b↦→y] = Z(σσ) a#y ⇒Z[a↦→x][b↦→y] = Z[b↦→y][a↦→x[b↦→y]](σswp) a#y, b#x ⇒Z[a↦→x][b↦→y] = Z[b↦→y][a↦→x](σasc) a#y, b#Z ⇒Z[a↦→x[b↦→y]] = Z[a↦→x][b↦→y](σid) Z[a↦→atm(a)] = Z(σren) a′#Z ⇒Z[a↦→atm(a′)] = (a′ a)·Z(σ@) c#x ⇒ (z@c)[a↦→x] = z[a↦→x]@c
Figure 3: Further nominal algebra properties of the σ-action

4.2.1. Alpha-equivalence of the sigma-action.

Lemma 4.8 ((σα)).

Suppose i∈ℤ and a, a′∈𝔸i and x∈Seti. Suppose Z∈Pred and a′#Z and z∈Setk and a′#z. Then:

(1) Z[a↦→x] = ((a′ a)·Z)[a′↦→x] and z[a↦→x] = ((a′ a)·z)[a′↦→x].

(2) supp(Z[a↦→x]) ⊆ (supp(Z)\{a}) ∪ supp(x) and supp(z[a↦→x]) ⊆ (supp(z)\{a}) ∪ supp(x).

(3) If a#x then a#Z[a↦→x] and a#z[a↦→x].

Proof

By induction on

age(Z) and age(z).

We consider the possibilities for Z∈Pred:

• The case of and(X) for X ⊆fin Pred. By Lemma 2.18 a#X′ for every X′∈X, so by the inductive hypothesis X′[a↦→x] = ((a′ a)·X′)[a′↦→x]. We use Figure 2 (σand) and Theorem 2.26.

• The case of neg(X) for X∈Pred. By Figure 2 (σneg) and the inductive hypothesis for X.

• The case of all([b]X) for X∈Pred and b∈𝔸j for some j∈ℤ. Using Lemma 3.6(1) we may assume without loss of generality that b#x. We use Figure 2 (σall) and the inductive hypothesis.

• The case of elt(y, a) for some y∈Seti-1. There are two sub-cases:

– Suppose x=atm(n) for some n∈𝔸i. We reason as follows:

(elt(y, a))[a↦→atm(n)] = elt(y[a↦→atm(n)], n) Figure 2(σeltatm)= elt(((a′ a)·y)[a′↦→atm(n)], n) Ind hyp for y= (elt(((a′ a)·y), a′))[a′↦→atm(n)] Figure 2(σeltatm)= ((a′ a)·(elt(y, a)))[a′↦→atm(n)] Theorem 2.26

– Suppose x=st([b′]X′) where X′ = x@b′ for some fresh b′∈𝔸i-1 (so b′#x, y, z). We reason as follows:

(elt(y, a))[a↦→x] = X′[b′↦→y[a↦→x]] Figure 2(σelta)= X′[b′↦→((a′ a)·y)[a′↦→x]] Ind hyp for y= (elt((a′ a)·y, a′))[a′↦→x] Figure 2(σelta)

• The case elt(y, b) for j∈ℤ and b∈𝔸j and y∈Setj-1. We reason as follows:

(elt(y, b))[a↦→x] = elt(y[a↦→x], b) Figure 2(σeltb)= elt(((a′ a)·y)[a′↦→x], b) Ind hyp for y= (elt(((a′ a)·y), b))[a′↦→x] Figure 2(σeltb)= ((a′ a)·(elt(y, b)))[a′↦→x] Theorem 2.26

We consider the possibilities for z∈Setk:

• The case that z is an internal atom. We use (σa) or (σb) of Figure 2.

• The case that z is an internal comprehension. We use Lemma 3.11(2&3) for a fresh c∈𝔸k-1 (so c#z), (σst), and the inductive hypothesis.

For part 2, we note that by Theorem 2.26 and Proposition 2.28

supp(Z[a↦→x]) ⊆supp(Z) ∪{a} ∪supp(x) and supp(((a′ a)·Z)[a′↦→x]) ⊆(a′ a)·supp(Z) ∪{a′} ∪supp(x).

We take a sets intersection. The case of z is similar.

Part 3 follows, recalling from Notation 2.11 that a#x means a∉supp(x).End of proof

Remark 4.9

Note for experts: We could set Definition 4.1 up differently: we could have σi and σij input abstractions

σi : ([𝔸i]Pred) × Seti →Pred and σij : ([𝔸i]Setj) × Seti →Setj.

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

Lemma 4.10 ((σ#)).

Suppose i∈ℤ and a∈𝔸i and x∈Seti and Z∈Pred and z∈Setk for k∈ℤ. Then

a#Z ⇒Z[a↦→x] = Z a#z ⇒z[a↦→x] = z.
Proof

By induction on

age(Z) and age(z).

We consider the possibilities for Z∈Pred:

• The case of and(X) for X ⊆fin Pred.

By Figure 2 (σand) (and(X))[a↦→x] = and({X[a↦→x] | X∈X}). By Lemma 2.18(3) a#X for every X∈X. We use the inductive hypothesis on each X.

• The case of neg(X) for X∈Pred. By Figure 2 (σneg) neg(X)[a↦→x] = neg(X[a↦→x]). We use the inductive hypothesis on X.

• The case of all([b]X) for X∈Pred and b∈𝔸j for some j∈ℤ.

Using Lemma 3.6(1) we may assume without loss of generality that b#x. By Figure 2 (σall) (all([b]X))[a↦→x] = all([b](X[a↦→x])). We use the inductive hypothesis on X.

• The case of elt(y, a) for i∈ℤ and y∈Seti-1. This is impossible because we assumed a#Z.

• The case of elt(y, b) for j∈ℤ and b∈𝔸j and y∈Setj-1.

By Figure 2 (σeltb) (elt(y, b))[a↦→x] = elt(y[a↦→x], b). We use the inductive hypothesis on y.

We consider the possibilities for z∈Setk:

• If z is an internal atom then we reason using (σa) or (σb) of Figure 2.

• If z is an internal comprehension then we use Lemma 3.11(2&3) for a fresh c∈𝔸k-1 (so c#z), (σst), and the inductive hypothesis.End of proof

Recall F=or(∅) and T=and(∅) from Example 3.9. Corollary 4.11 is an easy consequence of Lemma 4.10 and will be useful later:

Corollary 4.11

Suppose i∈ℤ and a∈𝔸i and x∈Seti. Then

F[a↦→x] = F and T[a↦→x] = T.
Proof

By Theorem 2.26 supp(F)=∅ so that a#x. We use Lemma 4.10. Similarly for T.End of proof

4.2.3. σ commutes with atoms-concretion.

Lemma 4.12 will be useful later, starting with Proposition 4.13:

Lemma 4.12 ((σ@)).

Suppose i∈ℤ and a∈𝔸i and x∈Seti. Suppose k∈ℤ and z ∈ Setk is an internal comprehension and c∈𝔸k-1 and c#z, x. Then

(z@c)[a↦→x] = z[a↦→x]@c.

(z@c is from Notation 3.10.)

Proof

By Lemma 3.11(2) we may write z = st([c]Z) where Z = z@c. We reason as follows:

(z@c)[a↦→x] = Z[a↦→x] Z = z@c= st([c](Z[a↦→x]))@c Lemma 3.11(2)= (st([c]Z)[a↦→x])@c Figure 2(σst), c#x= (z[a↦→x])@c z = st([c]Z)End of proof

4.2.4. σ commutes with itself: the ‘substitution lemma’.

Proposition 4.13

Suppose Z∈Pred and k∈ℤ and z∈Setk. Suppose i∈ℤ and a∈𝔸i and x∈Seti and suppose j∈ℤ and b∈𝔸j and y∈Setj and a#y. Then

Z[a↦→x][b↦→y] = Z[b↦→y][a↦→x[b↦→y]] z[a↦→x][b↦→y] = z[b↦→y][a↦→x[b↦→y]].
Proof

For brevity we may write

σ for [a↦→x][b↦→y] and σ′ for [b↦→y][a↦→x[b↦→y]].

Fix some k∈ℤ. We prove the Lemma for all Z, a, x, b, y and z, a, x, b, y with minlevel(Z, a, x, b, y)≥k and minlevel(z, a, x, b, y)≥k (Definition 4.4), reasoning by induction on

(level(a)+level(b), age(Z)) and (level(a)+level(b), age(z))

lexicographically ordered. Since k was arbitrary, this suffices to prove it for all Z, a, x, b, y and z, a, x, b, y.

We consider the possibilities for Z∈Pred:

• The case of and(X) for X ⊆fin Pred. We use rule (σand) of Figure 2 and the inductive hypothesis.

• The case of neg(X) for X∈Pred. We use (σneg) of Figure 2 and the inductive hypothesis.

• The case of all([a′]X) for X∈Pred and a′∈𝔸i′ for some i′∈ℤ. We use Lemma 3.6(1) to assume without loss of generality that a′#x, y, and then we use (σall) of Figure 2 and the inductive hypothesis.

• The case of elt(z, b) for z∈Setj-1 where j∈ℤ. There are two sub-cases:

– Suppose y=atm(n) for some n∈𝔸i other than a (we assumed a#y so n=a is impossible). We reason as follows:

(elt(z, b)) [a↦→x][b↦→atm(n)] = (elt(z[a↦→x], b))[b↦→atm(n)] Figure 2(σeltb)= elt(zσ, n) Figure 2(σeltatm)= elt(zσ′, n) IH age(z)<age(elt(z, b)), a#y= (elt(z[b↦→atm(n)], n))[a↦→x[b↦→atm(n)]] Figure 2(σeltb)= (elt(z, b))[b↦→atm(n)][a↦→x[b↦→atm(n)]] Figure 2(σeltatm)

– Suppose y=st([b′]Y ′) where Y ′ = y@b′ for some fresh b′∈𝔸j-1 (so b′#z, x, y and k≤level(b′)). Note by Theorem 2.26 that a#Y ′ and b′#x[b↦→y]. We reason as follows:

(elt(z, b)) [a↦→x][b↦→y] = (elt(z[a↦→x], b))[b↦→y] Figure 2(σeltb)= Y ′[b′↦→zσ] Figure 2(σelta)= Y ′[b′↦→zσ′] IH age(z)<age(elt(z, b)), a#y= Y ′[a↦→x[b↦→y]][b′↦→zσ′] Lemma 4.10, a#Y ′= Y ′[b′↦→z[b↦→y]] [a↦→x[b↦→y]] IH level(b′)<level(b), b′#x[b↦→y]= (elt(z, b))[b↦→y][a↦→x[b↦→y]] Figure 2(σelta)

• The case of elt(z, a) for z∈Seti-1 where i∈ℤ. There are two sub-cases:

– Suppose x=atm(n) for some n∈𝔸i. If n≠b then we reason as follows:

(elt(z, a)) [a↦→atm(n)][b↦→y] = (elt(z[a↦→atm(n)], n))[b↦→y] Figure 2(σeltatm)= elt(zσ, n) Figure 2(σeltb)= elt(zσ′, n) IH age(z)<age(elt(z, a)), a#y= elt(z[b↦→y][a↦→atm(n)], n) (σb) n≠b= (elt(z[b↦→y], a))[a↦→atm(n)] Figure 2(σeltatm)= (elt(z[b↦→y], a))[a↦→atm(n)[b↦→y]] (σb) n≠b= (elt(z, a))[b↦→y][a↦→atm(n)[b↦→y]] Figure 2(σeltb)

If n=b so that x=atm(b), and y=atm(m) for some m∈𝔸j other than a, then we reason as follows:

(elt(z, a)) [a↦→atm(b)][b↦→atm(m)] = (elt(z[a↦→atm(b)], b))[b↦→atm(m)] Figure 2(σeltatm)= elt(z[a↦→atm(b)][b↦→atm(m)], m) Figure 2(σeltatm)= elt(z[b↦→atm(m)][a↦→atm(b)[b↦→atm(m)]], m) IH age(z)<age(elt(z, a)), a#m= (elt(z[b↦→atm(m)], m))[a↦→atm(b)[b↦→atm(m)]] Figure 2(σeltb)= (elt(z, b))[b↦→atm(m)][a↦→atm(b)[b↦→atm(m)]] Figure 2(σeltatm)

If n=b so that x=atm(b), and y=st([b′]Y ′) where Y ′ = y@b′ for some fresh b′∈𝔸j-1 (so b′#z, n, y and k≤level(b′)) then we reason as follows (note by Theorem 2.26 that a#Y ′ and b′#x[b↦→y]):

(elt(z, a)) [a↦→atm(b)][b↦→y] = (elt(z[a↦→atm(b)], b))[b↦→y] Figure 2(σeltatm)= Y ′[b′↦→zσ] Figure 2(σelta)= Y ′[b′↦→zσ′] IH age(z)<age(elt(z, a)), a#y= Y ′[a↦→atm(b)[b↦→y]][b′↦→zσ′] Lemma 4.10, a#Y ′= Y ′[b′↦→z[b↦→y]][a↦→atm(b)[b↦→y]] IH level(b′)<level(b), b′#x[b↦→y]= (elt(z, a))[b↦→y][a↦→atm(b)[b↦→y]] Figure 2(σeltb)

– Suppose x=st([a′]X′) where X′ = x@a′ for some fresh a′∈𝔸i-1 (so a′#z, x, y and k≤level(a′)). We reason as follows:

(elt(z, a))[a↦→x][b↦→y] = X′[a′↦→z[a↦→x]] [b↦→y] Figure 2(σelta)= X′[b↦→y][a′↦→zσ] IH k≤level(a′)=level(a)-1, a′#y= X′[b↦→y][a′↦→zσ′] IH age(z)<age(elt(z, a)), a#y= (x[b↦→y]@a′)[a′↦→zσ′] Lemma 4.12, a′#y= (elt(z[b↦→y], a))[a↦→x[b↦→y]] Figure 2(σelta)= (elt(z, a))[b↦→y][a↦→x[b↦→y]] Figure 2(σelta), a#y

• The case of elt(z, c) for k∈ℤ and c∈𝔸k and z∈Setk-1. We reason as follows:

(elt(z, c))[a↦→x][b↦→y] = elt(zσ, c) Figure 2 (σeltb), twice= elt(zσ′, c) IH age(z)<age(elt(z, a)), a#y= (elt(z, c))[b↦→y][a↦→x[b↦→y]] Figure 2 (σeltb), twice

We consider the possibilities for z∈Setk:

• If z is an internal atom then we reason using (σa) and (σb) of Figure 2.

• If z is an internal comprehension then we use Lemma 3.11(2&3) for a fresh c∈𝔸k-1 (so c#z), (σst), and the inductive hypothesis.End of proof

Remark 4.14

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

Corollary 4.15 ((σswp)).

Suppose Z∈Pred and k∈ℤ and z∈Setk. Suppose i∈ℤ and a∈𝔸i and x∈Seti and suppose j∈ℤ and b∈𝔸j and y∈Setj. Suppose a#y and b#x. Then

Z[a↦→x][b↦→y] = Z[b↦→y][a↦→x] z[a↦→x][b↦→y] = z[b↦→y][a↦→x].
Proof

From Proposition 4.13 and Lemma 4.10.End of proof

Corollary 4.16 ((σasc)).

Suppose Z∈Pred and k∈ℤ and z∈Setk. Suppose i∈ℤ and a∈𝔸i and x∈Seti and suppose j∈ℤ and b∈𝔸j and y∈Setj. Suppose a#y and b#Z, z.14 Then

Z[a↦→x[b↦→y]] = Z[a↦→x][b↦→y] z[a↦→x[b↦→y]] = z[a↦→x][b↦→y].
Proof

From Proposition 4.13 and Lemma 4.10.End of proof

4.2.5. (σid): substitution for atoms and its corollaries.

We called atm(a) in Definition 3.3 an internal atom. Atoms in nominal techniques interpet variables, so if we call atm(a) an internal atom this should suggest that atm(a) 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:

Lemma 4.17 ((σid)).

Suppose i∈ℤ and a∈𝔸i. Then:

(1) If Z∈Pred then Z[a↦→atm(a)] = Z.

(2) If k∈ℤ and z∈Setk then z[a↦→atm(a)] = z.

Proof

We reason by induction on

age(Z) and age(z).

We consider the possibilities for Z∈Pred:

• If Z = and(Z) for Z ⊆fin Pred or Z = neg(Z′) for Z′∈Pred then we use rules (σand) and (σneg) of Figure 2 and the inductive hypothesis.

• If Z = all([a′]Z′) for Z′∈Pred and a′∈𝔸i′ for some i′∈ℤ then we use (σall) of Figure 2 and the inductive hypothesis.

• If Z = (elt(z, b)) for j∈ℤ and b∈𝔸j and z∈Setj-1 then we use rule (σeltb) of Figure 2 and the inductive hypothesis.

• If Z = (elt(z, a)) for z∈Seti-1 then we use (σeltatm) of Figure 2 and the inductive hypothesis for z.

We consider the possibilities for z∈Setk:

• If z is an atom then we reason using (σa) or (σb) of Figure 2.

• If z is an internal comprehension then we use Lemma 3.11(2&3) for a fresh c∈𝔸k-1 (so c#z), (σst), and the inductive hypothesis.End of proof

Given what we have so far, Lemma 4.18 is not hard to prove.

Lemma 4.18 ((σren)).

Suppose i∈ℤ and a, a′∈𝔸i. Then:

• If Z∈Pred and a′#Z then Z[a↦→atm(a′)] = (a′ a)·Z.

• If k∈ℤ and z∈Setk and a′#z then z[a↦→atm(a′)] = (a′ a)·z.

Proof

Suppose Z∈Pred and a′#Z. We note by Lemma 4.8(1) (since a′#Z) that Z[a↦→atm(a′)] = ((a′ a)·Z)[a′↦→atm(a′)] and use Lemma 4.17(1). The case of z∈Setk is exactly similar.End of proof

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:

Theorem 4.19

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.

Proof

Immediate from the definitions and lemmas thus far, which were designed to verify these properties.End of proof

Remark 4.20

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]).

Remark 4.21

We do not demand that the sigma-action should distribute through elt but this is because this is syntactically impossible: elt(y, a)[a↦→x] cannot be equal to elt(y[a↦→x], x) because elt(y[a↦→x], x) 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.

Remark 4.22

Another way to approach the proofs in this paper would be to admit elt(y, x) 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 y∈x and its properties.

Figure 1 only permits the syntax elt(y, a), not the syntax elt(y, x). We can obtain the power of elt(y, x) via a more sophisticated operation which we construct out of components already available:

Notation 4.23

• Suppose i∈ℤ and x∈Seti is an internal comprehension15 and y∈Seti-1. Then define y∈x by

y∈x = (x@b)[b↦→y]

where we choose b∈𝔸i-1 fresh (so b#x, y).

• Suppose i∈ℤ and a∈𝔸i and y∈Seti-1. Then define y∈atm(a) and y∈a by

y∈atm(a) = elt(y, a) = y∈a.
Remark 4.24

Two natural sanity properties for Notation 4.23 are that

(1) it should interact well with sets comprehension on the right-hand side, and

(2) it should interact well with the sigma-action substituting variables for terms.

This is Lemmas 4.25 and 4.26.

Lemma 4.25

Suppose X∈Pred and i∈ℤ and a∈𝔸i and x∈Seti and a#x. Then (using Notation 4.23)

x∈st([a]X) = X[a↦→x].
Proof

Note by Lemma 2.20 that a#st([a]X). By Notation 4.23 (since a#x, st([a]X)) x∈st([a]X) is equal to ((st([a]X))@a)[a↦→x] and by Lemma 3.11(4) this is equal to X[a↦→x].End of proof

Lemma 4.26

Suppose i, j∈ℤ and x∈Seti+1 and y∈Seti and a∈𝔸j and u∈Setj. Then:

(1) (y∈x)[a↦→u] = y[a↦→u]∈x[a↦→u].

(2) (y∈a)[a↦→u] = y[a↦→u]∈u, where j = i+1.

(3) (y∈b)[a↦→u] = y[a↦→u]∈b, where b∈𝔸i+1.

Proof

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 x=atm(a′) for some a′∈𝔸i+1 not equal to a. We reason as follows:

(y∈atm(a′))[a↦→u] = (elt(y, a′))[a↦→u] Notation 4.23= elt(y[a↦→u], a′) Figure 2(σeltb)= y[a↦→u]∈atm(a′) Notation 4.23= y[a↦→u]∈(atm(a′)[a↦→u]) Figure 2(σb)

• Suppose x=atm(a) (so that j=i+1). There are two sub-cases:

– Suppose u=atm(n) for some n∈𝔸i. We reason as follows:

(y∈atm(a))[a↦→atm(n)] = (elt(y, a))[a↦→atm(n)] Notation 4.23= elt(y[a↦→atm(n)], n) Figure 2(σeltatm)= y[a↦→atm(n)]∈atm(n) Notation 4.23

– Suppose u=st([a′]U′) where U′ = u@a′ for some fresh a′∈𝔸i-1 (so a′#u, y). We reason as follows:

(y∈atm(a))[a↦→u] = (elt(y, a))[a↦→u] Notation 4.23= U′[a′↦→y[a↦→u]] Figure 2(σelta)= y[a↦→u]∈u Notation 4.23

• Suppose x is an internal comprehension (not an internal atom). Choose b∈𝔸i fresh (so b#x, y, u). We reason as follows:

(y∈x)[a↦→u] = (x@b)[b↦→y][a↦→u] Notation 4.23= (x@b)[a↦→u][b↦→y[a↦→u]] Proposition 4.13 b#u= (x[a↦→u]@b)[b↦→y[a↦→u]] Lemma 4.12 b#x, u= y[a↦→u]∈x[a↦→u] Notation 4.23End of proof
Corollary 4.27

Suppose k∈ℤ and c∈𝔸k and x∈Setk and y∈Setk-1 and c#y. Then

if z=st([c](y∈c))∈Setk+1 then x∈z = y∈x.
Proof

We reason as follows:

x∈z = x∈st([c]y∈c) Assumption= (y∈c)[c↦→x] Lemma 4.25= y[c↦→x]∈x Lemma 4.26(1)= y∈x Lemma 4.10 c#yEnd of proof
Remark 4.28

It is quite interesting to reflect on the inductive measures used in the proofs above. Collecting them a list, they are:

• age(Z) and age(z) in Lemmas 4.8, 4.10, and 4.17.

• (level(a), age(Z)) and (level(a), age(z)) in Proposition 4.6.

• (level(a)+level(b), age(Z)) and (level(a)+level(b), age(z)) 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.

φ, ψ ::= ⊥| ¬φ | φ∧φ | ∀a.φ | s∈s s, t, r ::= a | {a|φ}
Figure 4: The syntax of Stratified Sets

5.1. Syntax of Stratified Sets.

Definition 5.1

Let formulae and terms be inductively defined as in Figure 4. In that figure, a ranges over atoms (Definition 2.1) and ∀ is taken to bind a and we quotient by α-equivalence. We write φ[a:=s] and r[a:=s] for the usual capture-avoiding substitution on syntax.

Remark 5.2

Quotienting by α-equivalence means that a formula φ is actually an α-equivalence class of syntax-trees and similarly for a term r. 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:

Definition 5.3

Suppose t is a term (Definition 5.1). Then extend level(a) from Definition 2.1 from atoms to all terms by:

level({a|φ}) = level(a)+1

Call a formula φ or term t stratified when:

if s′∈s is a subterm of φ or t then level(s) = level(s′)+1.

Example 5.4

Suppose a∈𝔸2, b∈𝔸3, and c∈𝔸4. Then a∈b and b∈c are stratified, and a∈c, b∈a, and a∈a are not stratified.

Definition 5.5

The language of Stratified Sets consists of stratified formulae and terms.

Remark 5.6

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 i and i+1 to a formula for each i ∈ℤ, and

• sets comprehension {a|φ} takes an atom of type i ∈ℤ and a formula φ to a term of type i+1.

We further assume that levels are arranged to respect stratification where this is required, so for example when we write [a:=s] it is understood that we assume a∈𝔸level(s).

Remark 5.7

We could add equality s=t to our syntax in Figure 4, at some modest cost in extra cases in inductive arguments. The pertinent stratification condition would be that if s=t is a subterm then level(s) = level(t). Our results extend without issues to the syntax with equality.

⟨⊥⟩= F ⟨¬φ⟩= neg(⟨φ⟩) ⟨φ∧ψ⟩= and({⟨φ⟩, ⟨ψ⟩}) ⟨∀a.φ⟩= all([a]⟨φ⟩)⟨t∈s⟩= ⟨t⟩∈⟨s⟩ ⟨{a|φ}⟩= st([a]⟨φ⟩) ⟨a⟩= atm(a)
Figure 5: Interpretation of formulae and terms

5.2. Interpretation for formulae and terms.

Definition 5.8

Define an interpretation of stratified formulae φ and terms s as in Figure 5, mapping φ to ⟨φ⟩∈ Pred and s of level i∈ℤ to ⟨s⟩∈ Seti.

Remark 5.9

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.

• ⟨t⟩∈⟨s⟩ is from Notation 4.23.

• st([a]⟨φ⟩) 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 s from Figure 4 to the syntax of internal predicates and internal sets from Definition 3.3 is not entirely direct: t∈s is primitive in formulae but only primitive in internal predicates if s is an atom.

Definition 5.10

Define the size of a stratified formula φ and stratified term t inductively as follows:

size(a) = 1 size({a|φ}) = size(φ)+1size(⊥) = 1 size(φ∧ψ) = size(φ) + size(ψ) + 1size(¬φ) = size(φ)+1 size(∀a.φ) = size(φ)+1size(t∈s) = size(t)+size(s) + 1
Lemma 5.11

Suppose φ is a stratified formula and s is a stratified term with level(s) = i ∈ℤ. Then

⟨φ⟩∈Pred and ⟨s⟩∈Seti.
Proof

By induction on size(φ) and size(s):17

• The case of a. By Figure 5 ⟨a⟩=atm(a). By Definition 3.3 atm(a)∈Seti.

• The case of {b|φ} for j≥1 and b∈𝔸j. By Figure 5 ⟨{b|φ}⟩=st([b]⟨φ⟩). By Definition 5.3 level {b|φ} = j+1. By inductive hypothesis ⟨φ⟩∈Pred and by Definition 3.3 st([b]⟨φ⟩) ∈ Setj+1.

• 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 ∀a.φ. From Figure 5 and Definition 3.3 using the inductive hypothesis.

• The case of t∈s. We refer to Notation 4.23 and use Lemma 3.11 and Proposition 4.6.End of proof

5.3. Properties of the interpretation.

Proposition 5.12

Suppose φ is a stratified formula and t, and r are stratified terms and b∈𝔸level(t). Then:

⟨φ⟩[b↦→⟨t⟩] = ⟨φ[b:=t]⟩ ⟨r⟩[b↦→⟨t⟩] = ⟨r[b:=t]⟩

Note by Lemma 5.11 that ⟨t⟩∈Setlevel(t) so that the σ-action [b↦→⟨t⟩] above is well-defined (Definition 4.1).

Proof

By induction on size(φ) and size(r). We consider each case in turn; the interesting case is for ∈, where we use Lemma 4.26:

• The case of ⊥. We reason as follows:

⟨⊥⟩[b↦→⟨t⟩] = F[b↦→⟨t⟩] Figure 5= F Corollary 4.11⟨⊥[b:=t]⟩= ⟨⊥⟩ Fact of syntax= F Figure 5

• The case of ¬φ. We reason as follows:

⟨¬φ⟩[b↦→⟨t⟩] = (neg(⟨φ⟩))[b↦→⟨t⟩] Figure 5= neg(⟨φ⟩[b↦→⟨t⟩]) Figure 2= neg(⟨φ[b:=t]⟩) IH size(φ)<size(¬φ)= ⟨¬(φ[b:=t])⟩ Figure 2= ⟨(¬φ)[b:=t]⟩ Fact of syntax

• The case of φ∧ψ. We reason as follows:

⟨φ∧ψ⟩[b↦→⟨t⟩] = (and({⟨φ⟩, ⟨ψ⟩}))[b↦→⟨t⟩] Figure 5= and({(⟨φ⟩[b↦→⟨t⟩]), (⟨ψ⟩[b↦→⟨t⟩])}) Figure 2= and({⟨φ[b:=t]⟩, ⟨ψ[b:=t]⟩}) IH size(φ), size(ψ)<size(φ∧ψ)= ⟨φ[b:=t]∧(ψ[b:=t])⟩ Figure 2= ⟨(φ∧ψ)[b:=t]⟩ Fact of syntax

• The case of ∀a.φ. We reason as follows, where we α-rename if necessary to assume a#t (from which it follows by Theorem 2.26 that a#⟨t⟩):

⟨∀a.φ⟩[b↦→⟨t⟩] = all([a]⟨φ⟩)[b↦→⟨t⟩] Figure 5= all([a](⟨φ⟩[b↦→⟨t⟩])) Figure 2 a#⟨t⟩= all([a]⟨φ[b:=t]⟩) IH size(φ)<size(∀a.φ)= ⟨∀a.(φ[b:=t])⟩ Figure 5= ⟨(∀a.φ)[b:=t]⟩ Fact of syntax, a#t

• The case of b. By Figure 5 ⟨b⟩=atm(b). By assumption ⟨t⟩∈Setlevel(b) so by Figure 2 (σa)

atm(b)[b↦→⟨t⟩] = ⟨t⟩.

• The case of a (any atom other than b). By Figure 5 ⟨a⟩=atm(a). We use rule (σb) of Figure 2.

• The case of {a|φ}. α-converting if necessary assume a is fresh (so a#t, and by Theorem 2.26 also a#⟨t⟩). We reason as follows:

⟨{a|φ}⟩[b↦→⟨t⟩] = (st([a]⟨φ⟩))[b↦→⟨t⟩] Figure 5= st([a]⟨φ⟩[b↦→⟨t⟩]) Figure 2(σst), a#⟨t⟩= st([a]⟨φ[b:=t]⟩) IH size(φ)<size({a|φ})= ⟨{a|φ[b:=t]}⟩ Figure 5, a#t= ⟨{a|φ}[b:=t]⟩ Fact of syntax

• The case of t′∈s′. We reason as follows:

⟨t′∈s′⟩[b↦→⟨t⟩] = (⟨t′⟩∈⟨s′⟩)[b↦→⟨t⟩] Figure 5= (⟨t′⟩[b↦→⟨t⟩])∈(⟨s′⟩[b↦→⟨t⟩]) Lemma 4.26= (⟨t′[b:=t]⟩)∈(⟨s′[b:=t]⟩) IH size(t′), size(s′)<size(t′∈s′)= ⟨(t′[b:=t])∈(s′[b:=t])⟩ Figure 5End of proof
t∈{a|φ} →φ[a:=t]φ →φ′¬φ →¬φ′φ →φ′φ∧φ′′ →φ′∧φ′′φ →φ′φ′′∧φ →φ′′∧φ′φ →φ′ {a|φ} →{a|φ′}φ →φ′ ∀a.φ →∀a.φ′s →s′t∈s →t∈s′t →t′t∈s →t′∈s
Figure 6: Rewrite system on formulae and terms
Lemma 5.13

Suppose φ is a stratified formula and s is a stratified term. Suppose a ∈𝔸i+1 and level(s) = i. Then:

(1) ⟨s∈{a|φ}⟩= ⟨φ[a:=s]⟩.

(2) ⟨s∈{a|φ}⟩= ⟨φ⟩[a↦→⟨s⟩].

Proof

We reason as follows:

⟨s∈{a|φ}⟩= ⟨s⟩∈⟨{a|φ}⟩ Figure 5= ⟨s⟩∈st([a]⟨φ⟩) Figure 5= (st([a]⟨φ⟩)@a)[a↦→⟨s⟩] Notation 4.23= ⟨φ⟩[a↦→⟨s⟩] Lemma 3.11(4)= ⟨φ[a:=s]⟩ Proposition 5.12End of proof

5.4. Confluence.

Definition 5.14

(1) Let → be a rewrite relation on the language of Stratified Sets (Definition 5.5) defined by the rules in Figure 6.

(2) Write →∗ for the transitive reflexive closure of → (so the least transitive reflexive relation containing →).

Notation 5.15

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.

Notation 5.16

Call a formula of the form t∈{a|φ} a reduct.

Lemma 5.17

⟨φ⟩ considered as a formula, is a →-normal form, and similarly for ⟨s⟩.

Proof

Reducts are impossible because the internal syntax from Figure 1 only allows us to form y∈x (written elt(y, x) in that figure) when x is an atom and not a comprehension.End of proof

We can now state a kind of converse to Lemma 5.17:

Theorem 5.18

(1) φ →∗⟨φ⟩ and s →∗⟨s⟩.

Here we use Notation 5.15 to treat ⟨φ⟩ and ⟨s⟩ directly as stratified syntax.

(2) If φ →φ′ then ⟨φ⟩= ⟨φ′⟩. If s →s′ then ⟨s⟩= ⟨s′⟩.

(3) φ →∗φ′ then φ′ →∗⟨φ⟩, and if s →∗s′ then s′ →∗⟨s′⟩. As a corollary, the rewrite relation → from Figure 6 is confluent.

Proof

(1) By induction on syntax. The interesting case is for t∈{a|φ}. Suppose φ →∗⟨φ⟩. Then

t∈{a|φ} →∗⟨t⟩∈{a|φ} IH, Figure 6→⟨φ⟩[a↦→⟨t⟩] Figure 6= ⟨t∈{a|φ}⟩ Lemma 5.13

(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 t∈{a|φ} →φ[a:=t]. By Lemma 5.13 ⟨t∈{a|φ}⟩= ⟨φ[a:=t]⟩.

• Suppose t∈{a|φ} →t∈{a|φ′} because {a|φ} →{a|φ′} because φ →φ′. By induction hypothesis ⟨φ⟩= ⟨φ′⟩. Then using Lemma 5.13 we have

⟨t∈{a|φ}⟩L5.13= ⟨φ⟩[a↦→⟨t⟩] = ⟨φ′⟩[a↦→⟨t⟩] L5.13= ⟨t∈{a|φ}⟩.

• Suppose t∈{a|φ} →t′∈{a|φ} because t →t′. By induction hypothesis ⟨t⟩= ⟨t′⟩. We have

⟨t∈{a|φ}⟩L5.13= ⟨φ⟩[a↦→⟨t⟩] = ⟨φ⟩[a↦→⟨t′⟩] L5.13= ⟨t′∈{a|φ}⟩.

(3) We combine parts 1 and 2 of this result.End of proof

5.5. Strong normalisation.

Notation 5.19

• Call a comprehension {a|φ} ternary when a occurs in φ at least three times.18 If a occurs in φ zero, one, or two times then we call {a|φ} non-ternary.

• Call a formula φ ternary if every comprehension in it is ternary.

• Call a term t ternary if every comprehension in it is ternary.

Definition 5.20

Suppose φ is a formula and t is a term. Write na(φ) and na(t) for the predicate or term obtained by padding every non-ternary comprehension {a′|φ′} in φ or t to

{a′|φ′∧∃c.(a′∈c∧a′∈c∧a′∈c)}

where c ∈𝔸level(a′)+1.19

Lemma 5.21

Suppose φ is a formula and t is a term. Then:

(1) na(φ) and na(t) are ternary.

(2) If φ and s are ternary then φ[a:=s] is ternary. Similarly for t[a:=s].

(3) If φ is ternary and φ →φ′ then φ′ is ternary. Similarly for t →t′.

Proof

(1) By construction.

(2) By an easy calculation.

(3) By an easy calculation from Figure 6 and part 2 of this result.End of proof

Definition 5.22

Define the complexity of a stratified formula φ and stratified term t as follows:

cplx(a) = 1 cplx({a|φ}) = 1 + cplx(φ) cplx(⊥) = 3 cplx(φ∧ψ) = cplx(φ) + 1 + cplx(ψ) cplx(¬φ) = 1 + cplx(φ) cplx(∀a.φ) = 1 + cplx(φ) cplx(b∈{a|φ}) = cplx(φ) cplx(t∈s) = cplx(t) + 1 + cplx(s) t not an atom, or s not a comprehension

Define the number of atomic reducts of φ and t as follows:

atomic(a) = 0 atomic({a|φ}) = atomic(φ) atomic(⊥) = 0 atomic(φ∧ψ) = atomic(φ) + atomic(ψ) atomic(¬φ) = atomic(φ) atomic(∀a.φ) = atomic(φ) atomic(t∈b) = atomic(t) atomic(t∈{a|φ}) = atomic(φ) + 1 t an atomatomic(t∈s) = atomic(t) + atomic(s) t not an atom
Remark 5.23

(1) If we view {a|φ} as λa.φ and t∈s as s t then an atomic reduct is just a term of the form (λa.φ)b. Then atomic counts the number of atomic reducts in formulae φ and terms t, 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

size(φ) = cplx(φ) + 2 ∗atomic(φ),

and similarly for t.

(2) Intuitively, cplx(⊥) = 3 means “⊥ has the same complexity as b∈a”. Technically, cplx(⊥) = 3 makes Lemma 5.24(2) hold, and allows the arithmetic in Lemma 5.26 to go through.

Lemma 5.24

Suppose s is a term and φ is a predicate. Then:

(1) cplx(s) ≥ 1.

(2) cplx(φ) ≥ 3.

(3) If s is not an atom (so it is a comprehension) then cplx(s) ≥ 4.

Proof

By calculations and induction using Definition 5.22; the base cases are ⊥ and t∈s (in particular, b∈a).End of proof

Lemma 5.25

Suppose φ is a predicate and t is a term. Suppose a is an atom and s is a term and level(a) = level(s) (so the substitution [a:=s] is well-defined). Then:

(1) If s is an atom then

cplx(φ[a:=s]) = cplx(φ) and cplx(t[a:=s]) = cplx(t).

(2) If s is not an atom (so is a comprehension) then

cplx(φ[a:=s]) ≥cplx(φ) + n ∗(cplx(s)-1) andcplx(t[a:=s]) ≥cplx(t) + n ∗(cplx(s)-1)

where n is the number of instances of a in φ or t.

Proof

(1) By a routine induction on φ and t using Definition 5.22.

(2) Essentially this is clear because we replace n instances of a each with complexity 1, with n instances of s each with complexity cplx(s). The proof is by induction on syntax using Definition 5.22. Interesting cases of the induction are φ or t that do not mention a (so n = 0), t′∈a, a∈b, and a∈{a′|φ′}. We consider each in turn:

• If φ or t do not mention a then φ[a:=s] = φ and t[a:=s] = t and the result follows.

• It is a fact that cplx(t′∈a) = cplx(t′) + 2, and we calculate as follows:

cplx(t′[a:=s]∈s) = cplx(t′[a:=s]) + 1 + cplx(s) ≥cplx(t′) + (n-1) ∗(cplx(s)-1) + 1 + cplx(s) = cplx(t′) + (n-1) ∗(cplx(s)-1) + 2 + (cplx(s)-1) = cplx(t′) + 2 + n ∗(cplx(s)-1) = cplx(t′∈a) + n ∗(cplx(s)-1)

• It is a fact that cplx(a∈b) = 3, and we calculate as follows:

cplx(s∈b) = cplx(s) + 2 = 3 + 1 ∗(cplx(s)-1) = cplx(a∈b) + 1 ∗(cplx(s)-1)

• It is a fact that cplx(a∈{a′|φ′}) = cplx(φ′), and we calculate as follows:

cplx(s∈{a′|φ′[a:=s]}) = cplx(s) + 2 + cplx(φ′[a:=s]) ≥cplx(s) + 2 + cplx(φ′) + (n-1) ∗(cplx(s)-1) ⪈(cplx(s)-1) + cplx(φ′) + (n-1) ∗(cplx(s)-1) = cplx(φ′) + n ∗(cplx(s)-1)End of proof
Lemma 5.26

Suppose {a|φ} is ternary (so φ mentions a free at least three times) and s is a term and level(s) = level(a). Then:

(1) If s is an atom then

cplx(s∈{a|φ}) = cplx(φ[a:=s]) = cplx(φ).

(2) If s is not an atom then

cplx(s∈{a|φ}) ⪇cplx(φ[a:=s]).
Proof

(1) From Lemma 5.25(1).

(2) Using Definition 5.22 and Lemma 5.25(2) we have the following facts:

• cplx(s∈{a|φ}) = cplx(φ) + 3 + (cplx(s)-1).

• cplx(φ[a:=s]) ≥ cplx(φ) + n ∗ (cplx(s)-1). We can drop the cplx(φ) on both sides and do some arithmetic:

3 + (cplx(s)-1) ⪇n ∗(cplx(s)-1) ⇔3 ⪇(n-1) ∗(cplx(s)-1) ⇔3 ⪇(n-1) ∗3 Lemma 5.24(3)⇔2 ⪇n.

We assumed φ is ternary, which means precisely that n ≥ 3, so this is true.End of proof

Corollary 5.27

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 t →t′.

Proof

Consider a reduct s∈{a|φ′}.

• If s is not an atom then we use Lemma 5.26(2).

• If s is an atom then using Lemma 5.26(1) complexity is unchanged; however the number of atomic reducts decrements.End of proof

Proposition 5.28

The rewrite system from Figure 6 is terminating (no infinite chain of rewrites).

Proof

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)

cplx(φ) ≤cplx(φ′) ≤cplx(⟨φ⟩).

Thus the set {cplx(φ′) | φ →∗φ′} is bounded above by cplx(⟨φ⟩). It follows using Corollary 5.27(1&2) and considering the measure

(cplx(⟨φ⟩) −cplx(φ′), atomic(φ′)),

lexicographically ordered, that any chain of reductions from φ must terminate.End of proof

Remark 5.29

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 t ∈{a | φ} corresponds to a β-reduct and extensionality s = {b | b ∈s} 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]).

Theorem 5.30

Formulae and terms of Stratified Sets, with the rewrites from Figure 6, are confluent and strongly normalising.

Proof

Confluence and weak normalisation (every formula/term has some rewrite to a normal form) are from Theorem 5.18.

Strong normalisation follows from weak normalisation and termination (Proposition 5.28).End of proof

Remark 5.31

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 s are only legal if we could assign levels to their variables to stratify them. We obtain as an easy corollary:

Theorem 5.32

Formulae and terms of stratifiable syntax, with the rewrites from Figure 6, are confluent and strongly normalising.

Proof

The result follows from Theorem 5.30 by taking a stratifiable φ, and stratifying it so that we now have φ′ in the language of Typed Sets. Rewrites on φ′ clearly correspond 1-1 with rewrites on φ, since Figure 6 makes no reference to the levels of variables.End of proof

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 ∅= {a | ⊥} then ∅∈{a | a ∉a} is not stratifiable but it rewrites to ∅∉∅, which is stratifiable for instance as {a0 | ⊥} ∉{a1 | ⊥}, which we could also write just as ∅1 ∉∅2. 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 ‘i ∈ℤ’. ↩

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 X is infinite. For instance if we take X = 𝔸 = X then the reader can verify that a#X for every a, but a#a does not hold for any a ∈𝔸. 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 x must contain all the variables mentioned in the predicate. It is not the case that a = a if and only if a = b — but it is the case that a = b if and only if b = a (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 a = {a}. ↩

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 φ(π·x, π·y, π·z), given a deduction of φ(x, y, z), is 1. Without equivariance, the cost of deducing φ(π·x, π·y, π·z), given a deduction of φ(x, y, z), is roughly n where n is the cost of deducing φ(x, y, z). 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 n 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(a) an internal atom, st([a]X) an internal set, and atm(a) or st([a]X) internal elements. However, note that st([a]X) is not a set and neither is atm(a); they are both syntax and we can call them what we like. ↩

12By concrete calculations or by Theorem 2.26. ↩

13k was chosen no greater than the minimum level of Z, a, and x. Now x = st([a′]X′), and it follows from Definition 4.4 that k ≤ level(a′). ↩

14We expect a stronger version of Corollary 4.16 to be possible in which we do not assume a#y. However, the proof would require an induction resembling the proof of Proposition 4.13 — the proof assuming a#y 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 x has the form st([b]x@b) for some b∈𝔸i-1 with b#x, and x does not have the form atm(a) for any a∈𝔸i1. ↩

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 c 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 a′∈c∧a′∈c∧a′∈c for c a fresh constant-symbol or variable symbol (one for each level), instead of ∃c.(a′∈c∧a′∈c∧a′∈c). 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. ↩