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

Curry-Howard for incomplete first-order logic derivations using one-and-a-half level terms

Murdoch J. Gabbay1, Dominic P. Mulligan2

Abstract

The Curry-Howard correspondence connects derivations in natural deduction with the lambda-calculus. Predicates are types, derivations are terms. This supports reasoning from assumptions to conclusions, but we may want to reason backwards; from the desired conclusion towards the assumptions. At intermediate stages we may have a partial derivation, with holes.

This is natural in informal practice but it can be difficult to formalise. The informal act of filling holes in a partial derivation suggests a capturing substitution, since holes may occur in the scope of quantifier introduction rules. As other authors have observed, this is not immediately supported by the lambda-calculus. Also, universal quantification requires a ‘fresh name’ and it is not immediately obvious what formal meaning to assign to this notion if derivations are incomplete. Further issues arise with proof-normalisation; this corresponds with lambda-calculus reduction, which can require alpha-conversion to avoid capture when beta-reducing, and it is not immediately clear how to alpha-convert a name in an incomplete derivation.

We apply a one-and-a-half level technique based on nominal terms to construct a Curry-Howard correspondence for first-order logic. This features two levels of variable, but with no lambda-abstraction at the second level. Predicates are types, derivations are terms, proof-normalisation is reduction — and the two levels of variable are respectively the assumptions and the holes of an incomplete derivation.

We give notions of proof-term, typing, alpha-conversion and beta-reduction for our syntax. We prove confluence, we exhibit several admissible rules including a proof that instantiation of level two variables is type-safe — this corresponds with the act of filling holes in an incomplete derivation, and can be viewed as a form of Cut-rule — and we explore the connection with traditional Curry-Howard in the case that the derivation is in fact complete.

Our techniques are not specifically tailored to first-order logic and the same ideas should be applicable without any essential new difficulties to similar logical systems.

1. Introduction

The Curry-Howard correspondence [US06, PCW05] corresponds logic with typed λ-calculus as follows:

predicatescorrespond(s) withtypes
derivationsterms
dischargeλ-abstraction
modus-ponensapplication
β-reductionproof-normalisation

For example,3

[A]a A⇒B B[A]a A⇒B⇒C B⇒CCaA⇒Ccorresponds with λa.((pa)qa) (1)

where a has type A, p has type A ⇒ B ⇒ C, and q has type A ⇒ B.

The typed λ-calculus yields a model of the ‘forwards’ construction of derivations; we plug together derivations to form larger ones, and we plug together λ-terms to form larger ones. However, we may wish to reason starting from the desired conclusion and working backwards, filling in the derivation as we go. At intermediate stages the derivation will be incomplete, for example as below with a ‘hole’ called X:

··· X B[A]a A⇒B⇒C B⇒CCaA⇒CAn incomplete derivation.

Here the λ-calculus is less helpful; X corresponds with qa in the complete derivation, so (being straighforward about it) the incomplete derivation above corresponds with ‘λa.((pa)X)’. But X is under a λ-binder and should be instantiated; substituted for without avoiding capture, and the λ-calculus does not contain a single operation to represent capturing substitution.

The reader can find extensive discussion of motivations for considering capturing substitution — which include but are not limited to representation of incomplete derivations — in [Bog02, Subsection 2.1 onwards], [Muñ97, Subsection 1.4.1], and also in [GL08, GL09, Introduction].

Most interesting logics are undecidable, so theorem-proving is often interactive (AUTOMATH [dB80] and descendents like Isabelle [Pau89] and HOL [GM93]). This motivates us to study intermediate proof-states. In addition, a well-known field of proof-theory is devoted to reasoning from conclusions to assumptions; goal-directed proof theory [GO00]. To our knowledge no Curry-Howard correspondence has been developed for goal-directed proof-theory.

This leads us to study what formal syntaxes, logics, and calculi underlie incomplete derivations and their refinement to complete ones.

We propose an approach based on nominal terms [UPG04]. Nominal terms have two levels of variable: variables of level one a, b, c, . . . and variables of level two X, Y, Z, . . .. Substitution of variables of level two does not avoid capture by variables of level one, so capturing substitution is directly represented by substitution of variables of level two. The incomplete derivation above is represented by the nominal term λa.((pa)X), and substitution of X for qa returns λa.((pa)(qa)). Full definitions will follow.

Nominal terms can be the basis of expressive, mathematically well-behaved, and implementable systems. They were introduced in a unification algorithm (freshness conditions are constraints) [UPG04] which was implemented as the basis of a logic programming language [CU04]. The first author in collaboration has applied them to rewriting [FG07b], universal algebra [Mat07], schematic reasoning in first-order logic [GM08a], and most recently a two-level λ-calculus [GM09a]4.

In brief, nominal terms feature a two-level hierarchy of variables: variables of level one a, b, c, d, . . . and variables of level two X, Y, Z, . . .. Here is an example of our system in action:

(1)··· X ⊥⇒A(2)[⊥] ··· X ⊥⇒A(3)[⊥] ··· X′A(⇒I)⊥⇒A(4)[⊥](⊥E)A(⇒I)⊥⇒A(1) X:⊥⇒A ⊢X:⊥⇒A (2) X:⊥⇒A, a:⊥; a#X ⊢X:⊥⇒A (3) a:⊥, X′:A ⊢λa.X′:⊥⇒A (4) a:⊥⊢λa.xf(a):⊥⇒A

On the left is a refinement of an incomplete derivation of ⊥⇒ A to a complete derivation, represented by λa.xf(a). Here xf (for ex-falsum) is a constant representing ⊥-elimination. On the right is their representation as terms-in-context in one-and-a-half level Curry-Howard using nominal terms. Note that:

• Assumptions are represented by variables of level one. Types are predicates assumed.

• Incomplete parts of the derivation, or (terminology from theorem-proving) subgoals, are represented by variables of level two, and, informally, are instantiated to any term sharing their type, to obtain a well-typed term.5 Types are predicates to be proved.

• Freshness conditions a#X, read in the literature as ‘a is fresh for X’ [UPG04] mean here that ‘a must be discharged in whatever X is instantiated to’.

The refinement of the lambda-term, above, follows closely the development of a proof in natural deduction; only stage (2) is a ‘technical’ stage, representing the injection of a level one variable of type ⊥ into a typing and freshness context.

We are reasonably ambitious in our choice of the types for our nominal terms. Our types correspond with first-order predicate logic without equality (see Definition 2). Note that this logic is strictly less expressive than first-order logic with function-symbols or with equality, but because it includes a binder ∀ it suffices to raise the issues of interest to us in this paper. The extension to full first-order logic is future work.

This paper treats incomplete first-order logic derivations, but there seems no obvious obstacle to applying the same ideas to logics other that first-order logic. In particular, we believe that the techniques represented in this paper would extend smoothly to the application considered by Muñoz of a theory of incomplete terms-and-types in dependent type theory [Muñ97].

1.1. Overview of the paper

In Section 2 we introduce syntax in Definition 5 and typing rules for the syntax in Definition 14, with some discussion of the rules in Remark 16 and with example derivations in Subsection 2.4.

In Section 3 we describe some admissible rules, including in Subsection 3.3 a rule for instantiating variables of level two (i.e. filling in unknown parts of a derivation) which features as a form of Cut. The proof of admissibility of Cut (Lemma 35 and Theorem 36) is a proof of soundness for instantiating variables of level two, as we do when we transform a term representing an incomplete derivation to a term representing a complete one.6

In Section 4 we consider traditional natural deduction derivation and show that our Curry-Howard system is sound (Theorem 41) and complete (Theorem 42) for the case of terms without variables of level one (representing complete derivations). That is: once an incomplete term is instantiated to a complete term in our system, it really does represent a natural deduction derivation of the predicate represented by its type.

In Section 5 we develop a theory of β-reduction for our calculus, corresponding via the Curry-Howard paradigm to a notion of proof-normalisation. Important technical results are subject reduction (Theorem 48), the identification of canonical forms (Definition 57), and confluence (Theorem 62). β-reduction is non-trivial in our calculus, because terms containing variables of level two raise issues to do with α-equivalence and β-reduction. The reader can find discussions of this in the authors’ recent publications [GL08, GL09, GM09a], as well as in other authors’ work [Bog02, Subsection 2.1 onwards], [Muñ97, Subsection 1.4.1], and also in [GL08, GL09, Introduction]. The solutions used by the calculus of this paper build on ideas presented in previous work using nominal terms [GL08, GL09, GM08a, GM09a] but they are non-trivial extensions of that work, since the calculus of this paper represents derivations of first-order logic, and is therefore particularly rich.

Finally, in the Conclusions, we give a technical survey of the literature on incomplete derivations, and propose future work.

2. Syntax of types (predicates) and terms (derivations), with examples

2.1. Terms, types and typable terms

Types (Definition 2) are the syntax of predicates of first-order logic. Terms (Definition 5) are the syntax of a λ-calculus. As we shall see, it will be possible to assign types to terms such that terms represent (incomplete) first-order logic derivations; this is explored with some detailed examples in Subsection 2.4.

Fix disjoint countably infinite sets of level one and level two variables. We let a, b, c, d, . . . range over level one variables, and X, Y, Z, . . . range permutatively over level two variables. We use a permutative convention that a, b, c, . . . and X, Y, Z, . . . range over distinct elements. For example ‘a and b’ means ‘two distinct level one variables’, and . ‘X, Y , and Z’ means ‘three distinct level two variables’.

Remark 1

Level one variables are derived from nominal term atoms, and level two variables are derived from nominal term unknowns [UPG04]. In keeping with more recent work [GM09a, GL08, GL09] we prefer the ‘levels’ terminology. Note that the variables in this paper (also in keeping with [GM09a, GL08, GL09]) display λ-abstraction and β-reduction behaviour, which nominal terms atoms and unknowns do not display. The variables here are also typed, with types representing predicates of first-order logic as will be described below. Thus, the syntax here is not the same thing as the nominal terms of [UPG04], but if we remove β-conversion, typing, and the theorems we prove about them in this paper — then we are left with α-equivalence, and the α-equivalence used in this paper is indeed that introduced in [UPG04].

Definition 2

Fix type-formers P, Q, R and type term-formers f, g, h, to each of which is associated an arity ar(-) which is a nonnegative integer (0, 1, 2, ...).

Define type terms and types by:

g ::= a | f(g1, . . . , gar(f)) φ, ψ, ξ ::= ⊥| φ ⇒φ | P(g1, · · · , gar(P)) | ∀a.φ

g will range over type terms. φ, ψ, and ξ will range over types.

For example ∀a.(P(a, a) ⇒ P(a, b)) is a type if ar(P) = 2.

We write ≡ for syntactic identity and we equate types up to ∀-bound variables of level one (so for example ∀a.∀b.P(a, b) ≡∀b.∀a.P(b, a)).7 Implication associates to the right; for example φ ⇒ψ ⇒ξ ≡φ ⇒ (ψ ⇒ξ).

Intuitively, types are first-order logic predicates.

Definition 3

Define the free level one variables as standard by:

fa(a) = {a} fa(f(g1, . . . , gn)) = fa(g1) ∪· · · ∪fa(gn) fa(P(g1, . . . , gn)) = fa(g1) ∪· · · ∪fa(gn) fa(φ ⇒ψ) = fa(φ) ∪fa(ψ) fa(⊥) = ∅ fa(∀a.φ) = fa(φ)\{a}
Definition 4

Call a bijection π on level one variables a permutation when {a | π(a) ≠ a} is finite. π, π′, π′′, . . . will range over permutations.

Write id for the identity permutation, so id(a) = a for all variables of level one, a. Call π◦π′ the composititon of permutations π and π′, so (π◦π′)(a) = π(π′(a)). Write π-1 for the inverse of π, whereby π◦π-1 = id = π-1◦π.

Write (a b) for the swapping permutation, which sends a to b, b to a and all other c to themselves.

Definition 5

Let terms be:

r, s, t, . . . ::= g | π · X | λa.r | r′r | xf(r)

We write ≡ for syntactic equivalence.

(We do not quotient terms by α-equivalence; thus for example λa.a ≢λb.b.) We may write (λa.r)t as r[a↦ →t], for example (λa.b)a ≡b[a↦ →a]. We may write r′r as r′(r). Application associates to the left, so r′′r′r ≡ (r′′r′)r; sometimes we will bracket anyway.

In Definition 5, we say π in π · X is suspended on X, with intuition ‘π acts on whatever X is instantiated to’. Consistent with previous work [UPG04] we may write ‘X’ for ‘id · X’. Note that later, we define π · r (Definition 11); this is meta-level notation for an action of π on r, whereas π · X is directly syntax.

Definition 6

A type assignment is a pair of the form a : φ where a ∉ fa(φ), or X : φ, or a : ∗. A typing context Γ is a finite set of type assignments, which is functional in the sense that:

• If a : φ ∈ Γ then a : ∗∉ Γ. If a : ∗∈ Γ then a : φ ∉ Γ.

• If a : φ ∈ Γ and a : φ′ ∈ Γ then φ = φ′. Similarly for X.

As is standard we may drop set brackets, writing for example Γ, a : φ for Γ ∪{a : φ}. Intuitively, a : φ means ‘a has type φ’; a : ∗ means ‘a is a type variable’; X : φ means ‘X has type φ’.

Remark 7

We use the same syntactic class (variables of level one) to represent type variables and term variables. The typing context differentiates them; a : φ ∈ Γ means a behaves like a term variable; a : ∗∈ Γ means a behaves like a type variable.

We could make a syntactic separation between variables of level one that can have types (a : φ ∈ Γ), and variables of level one that can appear in types (a : ∗∈ Γ). However, we would duplicate the treatments of λ-abstraction, application, and freshness. Our approach keeps the machinery shorter, at the expense of raw syntax being less inherently ‘sorted’.

({a : ∗a ∈f(g)} Γ| a⊆)(T∗)gΓ⊢g : ∗(a : φ ∈Γ, {b : ∗b ∈f(φ)} Γ; | a⊆)∆(Tφ)aΓ⊢a : φ (X : φ ∈Γ, Γ ⊢π{b : ∗b ∈f(φ)} Γ, {b#X | b ∈f(φ)} ∆∅); , | a⊆a∩= ∆(T)XΓ⊢π · X : π · φΓ⊢r : ⊥; ; ∆∆(T⊥E)Γ⊢x(r) φΓ⊢r′ : φ ⇒ψ Γ⊢r : φ; f: ; ; ∆∆∆(T⇒E)Γ⊢r′r : ψΓ⊢r : ∀aΓ⊢g : ∗; ; .; ∆∆φ ∆(T∀E)Γ⊢r: φ[a :g], : φ; ⊢r : ψ; g = Γa ∆∆(T⇒I)Γ, : φ; ⊢λ: φ ⇒ψΓ, : ∗; ⊢r : φ f(i(, : ∗; ⊢r)a ∆aa ∆a ∉amΓa ∆).pr ortant(T∀I)Γ, : ∗; ⊢λ: ∀aΓ, ; , #X r : φ Γ, ; , #X b#r (A ∈b : ψ: ∗, ∆a ∆a.A∆b⊢A∆b⊢{, }b ∉).φ b r (T)frΓ⊢r : φ; ∆(a#b)Γ, : φ: φ; ⊢a#b(a f(g)a , ∆∉a)b (a#g)Γ⊢a#g; ∆(a#λa)Γ⊢a#λΓ⊢a#r Γ⊢a#b; a; ; ∆.∆∆r(a#λb)Γ⊢a#λ-1(a)X ∈∆; b#∆.rπ(a#X)Γ⊢a#π · X(a f(φ); ∉a)∆(a#b′)Γ, : ∗, : φ; ⊢a#bΓ⊢a#r′Γ⊢a#ra b ∆; ; ∆∆(a#a)ppΓ⊢a#r′rΓ⊢a#r; ; ∆∆(a#x)fΓ⊢a#x(r); f∆
Figure 1: Typing and freshness derivation rules
⊥(⊥E)φ[φ] ·ψ·· (⇒I)φ ⇒ψ⇒ψ φ φ(⇒E)ψΦ·φ (a f(·∉aΦ· ))(∀I)∀a∀b..φφ(∀E)φ[b :g]=
Figure 2: Natural deduction style derivation rules
Definition 8

Call a pair a#r of a variable of level one and a term a freshness. Call a freshness of the form a#X primitive. Call a finite set of primitive freshnesses a freshness context. ∆ will range over freshness contexts.

Definition 9

Call Γ; ∆⊢r a term-in-context. Call Γ; ∆⊢r : φ a typing sequent. Call Γ; ∆⊢a#r a freshness sequent.

Definition 10

We define some useful notions for working with types and freshnesses:

• If Φ is a set of types, write fa(Φ) for ⋃{fa(φ) | φ ∈ Φ}.

• If X is a set of variables of level two, write a#X for the freshness context {a#X | X ∈X}.

• Write b ∉∆ when b#X ∉∆ for all X.

Definition 11

Define permutation actions on type terms, types, and terms by:

π · a ≡π(a) π · f(g1, . . . , gn) ≡f(π · g1, . . . , π · gn)π · ⊥≡⊥ π · (φ ⇒ψ) ≡(π · φ) ⇒(π · ψ)π · ∀a.φ ≡∀π(a).π · φ π · P(g1, . . . , gn) ≡P(π · g1, . . . , π · gn)π · (π′ · X) ≡(π◦π′) · X π · (r′r) ≡(π · r′)(π · r)π · λa.r ≡λπ(a).(π · r) π · xf(r) ≡xf(π · r)
Definition 12

Define a substitution action φ[a := b] on types by the usual capture-avoiding substitution on predicates.

For example, if f is a type term former with arity 2 and ∼ is a type former of arity 2, then (∀b.(f(a, b) ∼c))[a := f(b, c)] = ∀b′.(f(f(b, c), b′) ∼c.

Definition 13

Write Γ ⊢π when for every a such that π(a) ≠ a, precisely one of the following holds:

• a : ∗∈ Γ and π(a) : ∗∈ Γ,

• a : φ ∈ Γ and π(a) : π · φ ∈ Γ, for some φ.

Definition 14

Let the derivable typing and freshness sequents be inductively defined by the rules in Figure 1. We use the following notation here and later:

• Side-conditions are written in brackets.

• A ranges over typings or freshnesses, so A ∈{r : φ, a : ∗, a#r}.

• If a sequent - ⊢ - is not derivable we write - ⊬ -.

• We write important(Γ; ∆⊢r) for {φ | a : φ ∈ Γ, Γ; ∆⊬a#r}.

If φ exists such that Γ; ∆⊢r : φ is derivable, call Γ; ∆⊢r typable.

We may write ‘Γ; ∆⊢r : φ’ for ‘Γ; ∆⊢r : φ is a derivable typing sequent’, and similarly for ‘Γ; ∆⊢a#r’.

Remark 15

A few brief comments on these rules:

• The side-condition b ∉∆ in (Tfr) ensures that (Tfr) removes all mention of b from the freshness context.

• (TX) is syntax-directed on the term being typed (π·X). Note that π·φ has the same top-level type term-former as φ; we merely permute the level one variables.

• A way to read important(Γ; ∆⊢r), recalling that r represents an incomplete natural deduction derivation, is: “the possible assumptions of instantiations of r to complete natural deduction derivations”. 8

• The condition Γ; ∆⊢a#b in (a#λb) is not redundant. For example, it fails if a : ∗∈ Γ, b : ψ ∈ Γ, and a ∈ fa(ψ).

Remark 16

We compare the rules in Figure 1, for typing nominal terms, with the rules in Figure 2, which describe standard natural deduction:

• Compare (T⊥E) with (⊥E). ‘xf’ stands for ex falsum. (T⊥E) corresponds with (⊥E) in a standard way. No surprises here.

• Compare (T⇒I) with (⇒I). (T⇒I) does not discharge a : φ because r may contain a variable of level two X. We intend X to be instantiated to t which (because instantiation need not avoid capture) may mention a; see Definition 26. We remember a : φ in the typing context so that we can use it to build t, if we like. This is not a problem: we can mimic (⇒I) using (T⇒I) and (Tfr). An effect of this design choice is that the names of ‘bound’ variables in terms really do matter. For example, using (T⇒I) and (Tfr):

– ∅; ∅⊢λa.λa.a : φ ⇒φ ⇒φ is derivable. – ∅; ∅⊢λa.λa.a : ψ ⇒φ ⇒φ is not derivable.

– ∅; ∅⊢λb.λa.a : ψ ⇒φ ⇒φ is derivable.

We could ‘solve’ this problem by introducing α-equivalence into the typing rules. We choose not to; it makes no difference for the theorems of interest to us.

• Compare (T∀I) with (∀I). a ∉ fa(Φ) is intuitively ‘a is not free in any of the assumptions Φ used to prove φ’. a ∉ fa(important(Γ, a:∗; ∆⊢r)) generalises this to take account of variables of level two and freshness assumptions on them.

• Compare (a#b) and (a#b′). (a#b) is as in [UPG04]; distinct variables of level one are fresh. In (a#b′) we account for the type of b. For example:

a : P(c), X : P(c), c : ∗; a#X ⊢a#X a:P(c), X:P(c), c:∗; a#X ⊬c#X a:P(c), X:P(c), c:∗; a#X ⊬c#a

2.2. Properties of the permutation action

Here, we collect properties of the permutation action which will be useful later.

Lemma 17

If Γ ⊢π (Definition 13) and Γ ⊢π′ then Γ ⊢π◦π′.

Proof

Routine from the definitions.End of proof

Lemma 18

π′ · (π · r) ≡ (π′◦π) · r

Proof

By induction on r.

• The case a. As permutations are a bijection on variables of level one.

• The case π · X. From the definition of the permutation action.

• The case r′r. We have (π◦π′)·r′r ≡ ((π◦π′)·r′)((π◦π′)·r). By hypothesis, this is equivalent to (π · (π′ · r′))(π · (π′ · r)). The result follows from the permutation action.

• The case λa.r. We have

π′ · (π · λa.r) ≡π′ · (λπ(a).(π · r)) ≡λ((π′◦π) · a).((π′◦π) · r)

and the result follows.

• The case xf(r). We have (π◦π′) · xf(r) ≡ xf((π◦π′) · r). By hypothesis, this is equivalent to xf(π · (π′ · r)). The result follows from the permutation action definition.End of proof

Lemma 19

If Γ; ∆⊢a#r and Γ ⊢π then Γ; ∆⊢π(a)#π · r.

Proof

By induction on the derivation of Γ; ∆⊢a#r.

• The case (a#b). Suppose a : φ ∈ Γ and b : φ ∈ Γ. Since Γ ⊢π also π(a) : φ ∈ Γ and π(b) : φ ∈ Γ. By (a#b), also Γ ⊢π(a)#π(b).

• The case (a#g) is similar.

• The case (a#b′). Suppose a : ∗∈ Γ and b : φ ∈ Γ and a ∉ fa(φ). Since Γ ⊢π also π(a) : ∗∈ Γ and π(b) : π · φ ∈ Γ. By (a#b′), also Γ ⊢π(a)#π(b).

• The case (a#λa). Γ; ∆⊢π(a)#λπ(a).(π · r) always, using (a#λa).

• The case (a#λb). By inductive hypothesis, Γ; ∆⊢π(a)#π · r and Γ; ∆⊢π(a)#π · b. By (a#λb) also Γ; ∆⊢π(a)#λπ(b).(π · r). The result follows.

• The case (a#X). Suppose a#π′ · X is derived using (a#X), so that π′-1(a)#X ∈∆. It is a fact that π′-1(a) = π ◦π′-1(π(a)). The result follows.

• The cases of (a#app) and (a#xf) are no harder.End of proof

Lemma 20

Suppose Γ ⊢π. Then φ ∈ important(Γ; ∆⊢r) if and only if π·φ ∈ important(Γ; ∆⊢π·r).

Proof

Suppose Γ ⊢π. Suppose φ ∈ important(Γ; ∆⊢r). By definition a : φ ∈ Γ. Since Γ ⊢π, also π(a) : π · φ ∈ Γ. Also by definition, Γ; ∆⊬a#r. By Lemma 19 Γ; ∆⊬π(a)#π · r.

The argument for π · φ ∈ important(Γ; ∆⊢r) is similar. The result follows.End of proof

Lemma 21

fa(π · φ) = {π(a) | a ∈ fa(φ)}.

Proof

By a routine induction on φ.End of proof

Lemma 22

If a ∉ fa(φ) and b ∉ fa(φ) then (a b) · φ = φ.

Proof

By a routine induction on φ.End of proof

Lemma 23

If Γ; ∆⊢r : φ and Γ ⊢π then Γ; ∆⊢π · r : π · φ.

Proof

By induction on the derivation of Γ; ∆⊢r : φ.

• The case (Ta∗). Suppose a : ∗∈ Γ. Since Γ ⊢π also π(a) : ∗∈ Γ. The result follows.

• The case (Taφ). Suppose a : φ ∈ Γ. Since Γ ⊢π also π(a) : π · φ ∈ Γ. The result follows.

• The case (TX). By a routine calculation on permutations.

• The cases (T⊥E), (T⇒E), and (T⇒I) are routine.

• The case (T∀E). Suppose Γ; ∆⊢r : ∀a.φ and Γ; ∆⊢g : ∗. By inductive hypothesis Γ; ∆⊢π · r : ∀π(a).π · φ. Since Γ; ∆⊢g : ∗, x : ∗∈ Γ for every x ∈ fa(g). Since Γ ⊢π also π(x) : ∗∈ Γ for every x ∈ fa(g). It is a fact that π · (φ[a := g]) = (π · φ)[π(a) := π · g]. Using (T∀E) it follows that Γ; ∆⊢ (π · r)(π · g) : (π · φ)[π · a := π · g].

• The case (T∀I). Suppose Γ, a : ∗; ∆⊢r : φ and a ∉ important(Γ, a : ∗; ∆⊢r). By inductive hypothesis Γ, a : ∗; ∆⊢π · r : π · φ. By Lemma 20 π · a ∉ important(Γ, a : ∗; ∆⊢π · r). By assumption since Γ, a : ∗⊢π also π(a) : ∗∈ Γ, a : ∗. The result follows. 10

• The case (Tfr). Similar to the previous case, using Lemma 19.End of proof

Lemma 24

Suppose Γ; ∆⊢r : φ. Then if Γ; ∆⊢a#r then a ∉ fa(φ).

Proof

By induction on the derivation of Γ; ∆⊢r : φ.

• The case (Taφ). There are two cases:

– Γ; ∆⊢a#b is derived using (a#b). So a : φ, b : φ ∈ Γ. By assumption, a ∉ fa(φ), as required.

– Γ; ∆⊢a#b is derived using (a#b′). So a : ∗, b : φ ∈ Γ and a ∉ fa(φ).

• The case (TX). Γ; ∆⊢a#π · X must be derived using (a#X). It follows that π-1(a)#X ∈ ∆. By the side-condition in (TX), π-1(a) ∉ fa(φ). Therefore, a ∉ fa(π · φ).

• The cases of (T⊥E) and (T⇒E) are routine.

• The case (T∀E). Γ; ∆⊢a#rg : φ[b := g] must be derived using (a#app). Then Γ; ∆⊢ a#r and Γ; ∆⊢a#g. By inductive hypothesis a ∉ fa(∀b.φ), and by the structure of (a#g) also a ∉ fa(g). It is then a fact that a ∉ fa(φ[b := g]).

• The case (T∀I). There are two cases.

– The case of Γ, a : ∗; ∆⊢λa.r : ∀a.φ. a ∉ fa(∀a.φ) is immediate.

– The case of Γ, b : ∗; ∆⊢λb.r : ∀b.φ. Since a ∈ fa(φ) if and only if a ∈ fa(∀b.φ).

• The case (Tfr). Immediate, since φ is not changed above and below the line.End of proof

We use Lemma 25 much later, in the proof of Theorem 48. We place it here because it fits naturally into the results in this subsection.

Lemma 25

Suppose Γ; ∆⊢r : φ, Γ ⊢ (a b), Γ; ∆⊢a#r, and Γ; ∆⊢b#r. Then Γ; ∆⊢ (a b) · r : φ.

Proof

Suppose Γ; ∆⊢r : φ, Γ ⊢ (a b), Γ; ∆⊢a#r, and Γ; ∆⊢b#r. By Lemma 23 Γ; ∆⊢ (a b) · r : (a b) · φ. By Lemma 24 a ∉ fa(φ) and b ∉ fa(φ). By Lemma 22 Γ; ∆⊢ (a b) · r : φ.End of proof

2.3. Level two substitution

The purpose of level two variables X is to be instantiated; they represent ‘unknown parts of the proof’. We now formally define this instantiation action:

Definition 26

Define a substitution action r[X := t] by:

a[X := t] ≡a (π · X)[X := t] ≡π · t (π · Y )[X := t] ≡π · Y (λa.r)[X := t] ≡λa.(r[X := t]) (r′r)[X := t] ≡(r′[X := t])(r[X := t]) xf(r)[X := t] ≡xf(r[X := t])
Lemma 27

π · (r[X := t]) ≡ (π · r)[X := t]

Proof

By induction on r.

• The case π · (a[X := t]). Since a[X := t] ≡a and π(a)[X := t] ≡ π(a).

• The case π′ · ((π′ · X)[X := t]). π · (π′ · X)[X := t] ≡π · π′ · t. The result follows from Lemma 18. 11

• The case π′ · ((π′ · X)[Y := t]). (π′ · X)[Y := u] ≡π′ · X and similarly for (π ◦π′) · X. The result follows.

• The case r′r. We have π · ((r′r)[X := t]) ≡ (π · (r[X := t]))(π · (r[X := t])). By inductive hypothesis, (π · (r[X := t]))(π · (r[X := t])) ≡ ((π · r)[X := t])((π · r)[X := t]). The result follows.

• The case λa.r. We have π · ((λa.r)[X := t]) ≡λπ(a).(π · (r[X := t])). By inductive hypothesis, λπ(a).(π · (r[X := t])) ≡λπ(a).((π · r)[X := t]). The result follows.

• The case xf(r). We have π · (xf(r)[X := t]) ≡ xf(π · (r[X := t])). By inductive hypothesis, xf(π · (r[X := t])) ≡ xf((π · r)[X := t]). The result follows.End of proof

2.4. Examples

The derivations below type terms representing derivations from the Introduction; one is complete, the other incomplete. At each stage the term being typed represents a (possibly incomplete) natural deduction derivation. Write ‘Γ; ∅⊢r’ as ‘Γ ⊢r’. Write Γ for a : A, p : A ⇒ B ⇒ C, q : A ⇒ B:

(Taφ)Γ ⊢a : A(Taφ)Γ ⊢q : A ⇒B(T⇒E)Γ ⊢qa : B(Taφ)Γ ⊢a : A(Taφ)Γ ⊢p : A ⇒B ⇒C(T⇒E)Γ ⊢pa : B ⇒C(Ty⇒E)Γ ⊢(pa)qa : C(T⇒I)Γ ⊢λa.((pa)qa) : A ⇒C(Tfr)p : A ⇒B ⇒C, q : A ⇒B ⊢λa.((pa)qa) : A ⇒C(Taφ)Γ, X : B ⊢X : B(Taφ)Γ, X : B ⊢a : A(Taφ)Γ, X : B ⊢p : A ⇒B ⇒C(T⇒E)Γ, X : B ⊢pa : B ⇒C(T⇒E)Γ, X : B ⊢(pa)X : C(T⇒I)Γ, X : B ⊢λa.((pa)X) : A ⇒C(Tfr)p : A ⇒B ⇒C, q : A ⇒B, X : B ⊢λa.((pa)X) : A ⇒C

Derivations of Γ ⊢a#λa.((pa)qa) and Γ, X : B ⊢a#λa.((pa)X) are elided.

Another example illustrates the side-condition on (T∀I). The two derivations

A∀c(A ⇒P(c).)(∀E)A ⇒P(c)(⇒E)P(c)(∀I)∀cP(c) ∀cP(c)⇒B.(.) (⇒E)B·X ∀cP(c) ∀cP(c)⇒B·.(.) · (⇒E)B(2)

are represented, writing Γ for a : A, p : ∀c.(A ⇒ P(c)), q : (∀c.P(c)) ⇒ B, c : ∗, by:

(Tφ)aΓ ⊢a:A(Tφ)aΓ ⊢p : ∀c(A⇒P(c).)(T∀E)Γ ⊢p: A⇒P(c)c (T⇒E)Γ ⊢p: P(c)(cf(A), f(∀c(A⇒P(c))c∉ac∉a.)a (T∀I)Γ ⊢λ(p) ∀cP(c)cc: ..a(Tφ)aΓ ⊢q : ∀cP(c)⇒B(.)(T⇒E)Γ ⊢q(λ(p)Bcc) .a: (T)fra : A, : ∀c(A ⇒P(c), : ∀cP(c)⇒B ⊢q(λ(p)Bp .)q (.) cc) .a:
(T)XΓ, : P(c) ⊢X : P(c)cf(c(AP(c)c f(∀cP(c)⇒B))(c f(A)∀⇒X a.)∉a(.))∉a∉) (T∀I)Γ, : P(c) ⊢λ: ∀cP(c)X c..X (Tφ)aΓ, : P(c) ⊢q : ∀cP(c)⇒BX (.)(T⇒E)Γ, : P(c) ⊢q(λ) BX c: .X(T)fra : A, : ∀c(A ⇒P(c), : ∀cP(c)⇒B, : P(c) ⊢q(λ) Bp .)q (.) X c: .X
Γ; ∆⊢r : φ (Y ∉Γ)(WeakX)Γ, Y : ψ; ∆⊢r : φ Γ; ∆⊢r : φ (B ∈{b : ψ, b : ∗}, b ∉Γ)(Weaka)Γ, B; ∆, b#unkn(Γ) ⊢r : φ Γ, Y :ψ; ∆, a1#Y, . . . , an#Y ⊢r : φ Γ; ∆⊢u:ψΓ; ∆⊢ai#u (1≤i≤n) (Y ∉∆)(Cut)Γ; ∆⊢r[Y := u] : φ
Figure 3: Admissible rules

Derivations of freshnesses are elided.

3. Admissible rules

Definition 28

Say that a derivation rule:

A1. . . AnB

is admissible if A1. . . An is derivable implies that B is derivable.

Definition 29

Write unkn(Γ) for the variables of level two mentioned in Γ.

Definition 30

Figure 3 presents three admissible rules: two kinds of weakening, (WeakX) and (Weaka), and a form of Cut.

We briefly outline the meaning of these rules, notation and definitions follow:

• Weakening for variables of level two (WeakX) is the technically easiest result (Theorem 32). This is the usual weakening result for natural deduction. Intuitively, we introduce a new unknown derivation, represented by a variable of level two (but never use it).

• Weakening for variables of level one (Weaka) is technically harder (Theorem 33); what is it to weaken a derivation with an extra assumption (represented by a variable of level one) that is never used — if we do not yet know all parts of that derivation? We use freshness conditions.

• Cut is technically the most challenging, and intuitively the most significant result (Theorem 36). Here, Cut means intuitively that instantiating unknown parts of a derivation results in another derivation; in other words, it is sound to instantiate variables of level two.

3.1. Weaken with a variable of level two (WeakX)

Lemma 31

Suppose Γ′ satisfies Definition 6. Suppose also that Γ ⊆ Γ′ and ∆⊆∆′.

If Γ; ∆⊢a#r then Γ′; ∆′ ⊢a#r.

Proof

By induction on the derivation of Γ; ∆⊢a#r.

• The case (a#b). Suppose a : φ ∈ Γ and b : φ ∈ Γ. Then a : φ ∈ Γ′ and b : φ ∈ Γ′. Applying (a#b), we obtain Γ′; ∆′ ⊢a#b. The result follows. 13

• The case (a#b′). Suppose a : ∗∈ Γ and b : φ ∈ Γ, with a ∉ fa(φ). Then a : ∗∈ Γ′ and b : φ ∈ Γ′. Applying (a#b′), we obtain Γ′; ∆′ ⊢a#b. The result follows.

• The case (a#g) is immediate.

• The case (a#X). Suppose π-1(a)#X ∈∆, therefore π-1(a)#X ∈∆′. Applying (a#X), we obtain Γ′; ∆′ ⊢a#π · X. The result follows.

• The case (a#λa). Since Γ′; ∆′ ⊢a#λa.r always, by (a#λa).

• The case (a#λb). By inductive hypothesis, Γ′; ∆′ ⊢a#r and Γ′; ∆′ ⊢a#b. Applying (a#λb), we obtain Γ′; ∆′ ⊢a#λb.r. The result follows.

• The case (a#app). By inductive hypothesis, Γ′; ∆′ ⊢a#r′ and Γ′; ∆′ ⊢a#r. Applying (a#app), we obtain Γ′; ∆′ ⊢a#r′r. The result follows.

• The case (a#xf). By inductive hypothesis, Γ′; ∆′ ⊢a#r. Applying (a#xf), we obtain Γ′; ∆′ ⊢a#xf(r). The result follows.End of proof

Theorem 32

(WeakX) is admissible (Figure 3).

Proof

By induction on derivations.

• The case (Ta∗). There is nothing to prove.

• The case (Taφ). By assumption, Γ; ∆⊢a : φ therefore a : φ ∈ Γ, hence a : φ ∈ Γ, Y : ψ. The result follows.

• The case (TX). By assumption, Γ; ∆⊢X : φ therefore X : φ ∈ Γ, hence X : φ ∈ Γ, Y : ψ. Note that Γ ⊢π by assumption. The result follows.

• The case (T⊥E). By inductive hypothesis, Γ, Y : ψ; ∆⊢r : ⊥ where Y ∉ Γ. Applying (T⊥E), we have Γ, Y : ψ; ∆⊢ xf(r) : φ. The result follows.

• The case (T⇒I). By inductive hypothesis, Γ, a : φ, Z : ξ; ∆⊢r : ψ. Applying (T⇒I), we obtain Γ, Z : ξ; ∆⊢λa.r : φ ⇒ψ. The result follows.

• The case (T⇒E). By inductive hypothesis, Γ, Z : ξ; ∆⊢r′ : φ ⇒ψ and Γ, Z : ξ; ∆⊢r : φ with Z ∉ Γ. Applying (T⇒E), we obtain Γ, Z : ξ; ∆⊢r′r : ψ. The result follows.

• The case (T∀I). By inductive hypothesis, Γ, a : ∗, Y : ψ; ∆⊢r : φ with Y ∉ Γ where it is easy to see a ∉ fa(important(Γ , a : ∗, Y : ψ; ∆⊢ r)) when a ∉ fa(important(Γ , a : ∗; ∆⊢ r)) and Y ∉ Γ. Applying (T∀I), we obtain Γ, a : ∗, Y : ψ; ∆⊢ λa.r : ∀a.φ. The result follows.

• The case (T∀E). By inductive hypothesis, Γ, Y : ψ; ∆⊢r : ∀a.φ with Y ∉ Γ. Applying (T∀E), we obtain Γ, Y : ψ; ∆⊢rg : φ[a := g]. The result follows.

• The case (Tfr). By inductive hypothesis, Γ, b : τ, Z : ξ; ∆, b#X ⊢r : φ where Z ∉ Γ, τ ∈{ψ, ∗} and b ∉∆. By Lemma 31, we have Γ, b : τ, Z : ξ; ∆, b#X ⊢b#r. Applying (Tfr), we obtain Γ, Z : ξ; ∆⊢r : φ. The result follows.End of proof

3.2. Weaken with a variable of level one (Weaka)

(Weaka) states that the variable of level one is fresh for the incomplete parts in the derivation:

Theorem 33

(Weaka) is an admissible rule (Figure 3).

Proof

By induction on derivations.

• The case (Ta∗). There is nothing to prove.

• The case (Taφ). Suppose Γ; ∆⊢a : φ then a : φ ∈ Γ. Further, suppose b ∉ Γ and b : τ for τ ∈{ψ, ∗}. Then Γ, b : τ; ∆, b#unkn(Γ) ⊢a : φ is derivable. The result follows.

• The case (TX). Suppose Γ; ∆⊢X : φ then X : φ ∈ Γ. Further, suppose b ∉ Γ and b : τ for τ ∈{ψ, ∗}. Then Γ, b : τ; ∆, b#unkn(Γ) ⊢X : φ is derivable, and by assumption Γ ⊢π. The result follows.

• The case (T⊥E). By inductive hypothesis, Γ, b : τ; ∆, b#unkn(Γ) ⊢r : ⊥ for τ ∈{φ, ∗} and b ∉ Γ. Applying (T⊥E), we obtain Γ, b : τ; ∆, b#unkn(Γ) ⊢ xf(r) : φ. The result follows.

• The case (T⇒I). By inductive hypothesis, Γ, a : φ, b : τ; ∆, unkn(Γ) ⊢r : φ for τ ∈{ψ, ∗} and b ∉ Γ. Applying (T⇒I), we obtain Γ, a : φ, b : τ; ∆, b#unkn(Γ) ⊢λa.r : φ ⇒ψ. The result follows.

• The case (T⇒E). By inductive hypothesis, Γ, b : τ; ∆, b#unkn(Γ) ⊢r′ : φ ⇒ψ and Γ, b : τ; ∆, b#unkn(Γ) ⊢r : φ for τ ∈{φ, ∗} and b ∉ Γ. Applying (T⇒E), we obtain Γ, b : τ; ∆, b#unkn(Γ) ⊢r′r : ψ and the result follows.

• The case (T∀I). By inductive hypothesis Γ, a : ∗, b : τ; ∆, b#unkn(Γ) ⊢r : φ where b ∉ Γ, a : ∗ and τ ∈{ψ, ∗}. It is not hard to calculate that Γ, a : ∗, b : τ; ∆, b#unkn(Γ) ⊢b#r and so a ∉ fa(important(Γ, a : ∗, b : τ; ∆, b#unkn(Γ) ⊢r)). The result follows.

• The case (T∀E). By inductive hypothesis, Γ, b : ∗; ∆, b#unkn(Γ) ⊢r : ∀a.φ where b ∉ Γ. Applying (T∀E), we obtain Γ; ∆, b#unkn(Γ) ⊢rg : φ[a := g]. The result follows.

• The case (Tfr). By inductive hypothesis, Γ, a : τ, b : τ ′; ∆, a#X, b#unkn(Γ, a : τ) ⊢r : φ where τ, τ ′ ∈{φ, ∗} and b ∉ Γ. By Lemmas 31, Γ, a : τ, b : τ ′; ∆, a#X, b#unkn(Γ, a : τ) ⊢ b#r. Applying (Tfr) it is easy to see that unkn(Γ) = unkn(Γ, a : τ) and we therefore obtain Γ, b : τ ′; ∆, b#unkn(Γ) ⊢r : φ. The result follows.End of proof

3.3. Cut

The main result of this subsection is Theorem 36, that (Cut) from Figure 3 is admissible. The proof is non-trivial, and as discussed at the start of this Section, it is significant: it states that level two variables may be instantiated, in other words, that the ‘holes’ in our incomplete derivations really can be filled with derivations.

The proof of Theorem 36 depends on two lemmas: Lemma 34 and Lemma 35. Recall that important(Γ; ∆⊢r : φ) (Definition 14) represents “the possible assumptions of instantiations of r”. Lemma 34 captures this, by proving that the instantiations of r do have assumptions contained in important(Γ; ∆⊢r : φ); this is important to make sure that it is sound to instantiate level two variables in (T∀I). Lemma 35 is the meat of the proof of Theorem 36. It states a precise sense in which instantiating level two variables is sound.

Lemma 34

Suppose that:

• Γ, Y : ψ; ∆⊢r : φ and Γ; ∆⊢u : ψ.

• Γ; ∆′ ⊢a#u for every a#Y ∈∆.

(Here, ∆′ is any freshness context satisfying the above condition.)

Then

important(Γ; ∆′ ⊢r[Y := u]) ⊆important(Γ, Y : ψ; ∆⊢r).
Proof

By a routine induction on r. We consider cases:

• The case a. Note a[Y := u] ≡a. Then important(Γ; ∆′ ⊢a) ⊆ important(Γ, Y : ψ; ∆⊢a). The result follows.

• The case π · Y . We have important(Γ; ∆′ ⊢π · u) = {φ | a : φ ∈ Γ, Γ; ∆′ ⊬a#π · u}. This is equivalent to {φ | a : φ ∈ Γ, Γ; ∆′ ⊬π-1(a)#u}. Further, we have important(Γ, Y : ψ; ∆⊢π · Y ) = {φ | a : φ ∈ Γ, Γ, Y : ψ; ∆⊬a#π · Y }. This, in turn, is equivalent to {φ | a : φ ∈ Γ, π-1(a)#Y ∉∆}. Now, we must show {φ | a : φ ∈ Γ, Γ; ∆′ ⊬π-1(a)#u} ⊆{φ | a : φ ∈ Γ, π-1(a)#Y ∉∆}. So, suppose φ ∈{φ | a : φ ∈ Γ, Γ; ∆′ ⊬π-1(a)#u}, and therefore φ is the type of some variable of level one in Γ such that Γ; ∆′ ⊬π-1(a)#u. By assumption, π-1(a)#Y ∈∆ implies Γ; ∆′ ⊢π-1(a)#u, therefore Γ; ∆′ ⊬π-1(a)#u implies π-1(a)#Y ∉∆. The result follows.

• The case π · X. Note that (π · X)[Y := s] ≡π · X. Further, note π-1(a)#X ∈∆′. It is then easy to see that important(Γ; ∆′ ⊢π · X) ⊆ important(Γ, Y : ψ; ∆⊢π · X). The result follows.

• The case λb.r. By inductive hypothesis, important(Γ; ∆′ ⊢r[Y := u]) ⊆ important(Γ, Y : ψ; ∆⊢r). Note that (λb.r)[Y := u] ≡λb.(r[Y := u]). The result follows.

• The case r′r. Note that (r′r)[Y := u] ≡r′[Y := u](r[Y := u]). The result follows from the inductive hypothesis.

• The case xf(r). Note that xf(r)[Y := u] ≡ xf(r[Y := u]). The result follows from the inductive hypothesis.End of proof

Lemma 35

Suppose that:

• Γ, Y : ψ; ∆⊢r : φ and Γ; ∆⊢u : ψ.

• Γ; ∆′ ⊢a#u for every a#Y ∈∆.

Then:

• Γ, Y : ψ; ∆⊢a#r implies Γ; ∆′ ⊢a#r[Y := u], for every a.

• Γ; ∆′ ⊢r[Y := u] : φ.

Proof

The first claim is shown by induction on the derivation of Γ; ∆′ ⊢a#t.

• The case (a#b). Suppose Γ, a : φ, b : φ, Y : ψ; ∆⊢a#b is derived using (a#b). Then Γ, a : φ, b : φ; ∆′ ⊢a#b and b[Y := u] ≡b. The result follows.

• The case (a#b′). Suppose Γ, a : ∗, b : φ, Y : ψ; ∆⊢a#b is derived by (a#b′). Then a ∉ fa(φ) and it follows that Γ, a : ∗, b : φ; ∆′ ⊢a#b and b[Y := u] ≡b. The result follows.

• The case (a#g). Suppose Γ, Y : ψ; ∆⊢a#g is derived using (a#g). Then Γ; ∆′ ⊢a#g and g[Y := u] ≡g. The result follows.

• The case (a#X). There are two cases:

– The case π · Y . Suppose Γ, Y : ψ; ∆⊢a#π · Y is derived using (a#X). This implies π-1(a)#Y ∈∆ by inversion. By assumption, Γ; ∆′ ⊢π-1(a)#u. From Lemma 19 and Lemma 18 we have Γ; ∆′ ⊢a#π · u. The result follows.

– The case π · X. Suppose Γ, X : φ; ∆⊢a#π · X is derived using (a#X). This implies π-1(a)#X ∈∆. By assumption, Γ; ∆′ ⊢π-1(a)#u. By Lemma 19, Lemma 18, and the fact that (π · X)[Y := u] ≡π · X, the result follows.

• The case (a#λa). Note Γ; ∆′ ⊢a#λa.(r[Y := u]) always, using (a#λa). Since λa.(r[Y := u]) ≡ (λa.r)[Y := u], the result follows.

• The case (a#λb). Suppose Γ, Y : ψ; ∆⊢a#r and Γ, Y : ψ; ∆⊢a#b and Γ, Y : ψ; ∆⊢ a#λb.r is derived by (a#λb). By inductive hypothesis Γ; ∆′ ⊢a#r[Y := u] and Γ; ∆′ ⊢a#b and so Γ; ∆′ ⊢a#λb.(r[X := t]). Since λb.(r[Y := u]) ≡ (λb.r)[Y := u], the result follows.

• The case (a#app). By inductive hypothesis, Γ; ∆′ ⊢a#r′[Y := u] and Γ; ∆′ ⊢a#r[Y := u]. Applying (a#app), we obtain Γ; ∆′ ⊢a#r′[Y := u](r[Y := u]). Note that r′[Y := u](r[Y := u]) ≡ (r′r)[Y := u]. The result follows.

• The case (a#xf). By inductive hypothesis, Γ; ∆′ ⊢a#r[Y := u]. Applying (a#xf), we obtain Γ; ∆′ ⊢a#xf(r[Y := u]). Note that xf(r[Y := u]) ≡ xf(r)[Y := u]. The result follows.

The second claim is shown by induction on the derivation of Γ, Y : ψ; ∆⊢r : φ.

• The case (Ta∗). There is nothing to prove.

• The case (Taφ). Suppose a : φ ∈ Γ and Γ, Y : ψ; ∆⊢a : φ is derived by (Taφ). Then Γ; ∆′ ⊢a : φ. Since a ≡a[Y := u], the result follows..

• The case (TX). Suppose X : φ ∈ Γ and Γ, Y : ψ; ∆⊢X : φ is derived by (TX). Then Γ; ∆′ ⊢X : φ. Since X ≡X[Y := u], the result follows. Further, suppose Γ, Y : ψ; ∆⊢Y : ψ is derived by (TX). By assumption Γ; ∆′ ⊢u : ψ. Since u ≡Y[Y := u], the result follows.

• The case (T⊥E). By inductive hypothesis, Γ; ∆′ ⊢r[X := t] : ⊥. Applying (T⊥E), we obtain Γ; ∆′ ⊢ xf(r[X := t]) : φ. The result follows.

• The case (T⇒I). By inductive hypothesis, Γ, a : φ; ∆′ ⊢r[X := t] : ψ. Applying (T⇒I), we obtain Γ, a : φ; ∆′ ⊢λa.(r[X := t]) : φ ⇒ψ. As λa.(r[X := t]) ≡ (λa.r)[X := t], the result follows.

• The case (T⇒E). By inductive hypothesis, Γ; ∆′ ⊢r′[X := t] : φ ⇒ψ and Γ; ∆′ ⊢r[X := t] : φ. Applying (T⇒E), we obtain Γ; ∆′ ⊢ (r′[X := t])(r[X := t]) : ψ. As (r′[X := t])(r[X := t]) ≡ (r′r)[X := t], the result follows.

• The case (T∀E). By inductive hypothesis, Γ; ∆′ ⊢r[X := t] : ∀a.φ. Applying (T∀E), we obtain Γ; ∆′ ⊢r[X := t]g : φ[a := g]. As r[X := t]g ≡ (rg)[X := t], the result follows.

• The case (T∀I). By inductive hypothesis, Γ, a : ∗; ∆′ ⊢r[X := t] : φ. Using Lemma 34, a ∉ fa(important(Γ, a : ∗; ∆′ ⊢r[X := t])). Applying (T∀I), we have Γ, a : ∗; ∆′ ⊢λa.(r[X := t]) : ∀a.φ. As λa.(r[X := t]) ≡ (λa.r)[X := t], the result follows.

• The case (Tfr). Suppose Γ, Z : ξ; ∆⊢r : φ because Γ, b : τ, Z : ξ; ∆, b#X ⊢r : φ and Γ; ∆⊢v : ξ and suppose that Γ, b : τ, Z : ξ; ∆, b#X ⊢b#r where b ∉∆ and τ ∈{ξ, ∗}. By inductive hypothesis and some calculations, using the first claim, Γ, b : τ; ∆′, b#X ′ ⊢ r[Z := v] : φ and Γ, b : τ; ∆′, b#X ′ ⊢b#r[Z := v] for a suitable X ′ and ∆′ where b ∉∆′. The result follows.End of proof

Cut in natural deduction is the operation of ‘plugging the conclusion of one derivation into the assumption(s) of another’. Yet, for us now, these derivations may be incomplete and substitution capture-avoiding. The rule (Cut) specifies precisely what operation this now is, and we have:

Theorem 36

(Cut) is an admissible rule.

Proof

Suppose, given Y ∉∆, that Γ, Y : ψ; ∆, a1#Y . . . an#Y ⊢r : φ, Γ; ∆⊢u : ψ and Γ; ∆⊢ ai#u for 1 ≤i ≤n. Then clearly Γ; ∆⊢ai#u for every ai#Y ∈∆, a1#Y, . . . an#Y . The result now follows immediately from Lemma 35.End of proof

4. Natural deduction

The intended semantics of a term r is ‘an incomplete natural deduction derivation’. In this section, we recap the standard theory of natural deduction derivations and prove forms of soundness (Theorem 41) and completeness (Theorem 42).

Definition 37

Call a finite set of types a (natural deduction) context. Let Φ, Φ′ range over contexts.

Write Φ ⊢φ when φ may be derived using the rules in Figure 2 allowing elements of Φ as assumptions.8 In accordance with our convention, side-conditions are in brackets. As is standard, square brackets in (⇒I) denote discharge of assumptions; note that we may choose to discharge φ zero times (empty discharge).

Lemma 38

If Φ ⊢ψ and Φ ⊆ Φ′ then Φ′ ⊢ψ.

Proof

By induction on derivations. The special case where Φ, φ ⊢φ follows immediately. See Footnote 8 for details.

• The case (⊥E). By inductive hypothesis, Φ′ ⊢⊥. Applying (⊥E), we obtain Φ′ ⊢φ and the result follows.

• The case (⇒I). By inductive hypothesis, Φ′, φ ⊢ψ. Applying (⇒I), we obtain Φ′ ⊢φ ⇒ψ when we discharge, and the result follows. Alternatively, we obtain Φ′, φ ⊢φ ⇒ψ where we discharge zero times, and the result follows.

• The case (⇒E). By inductive hypothesis, Φ′ ⊢φ ⇒ψ and Φ′ ⊢φ. Applying (⇒E), we obtain Φ′ ⊢ψ and the result follows.

• The case (∀I). By inductive hypothesis, Φ′ ⊢φ. Picking suitable a we extend with (∀I), to obtain Φ′ ⊢∀a.φ and the result follows.

• The case (∀E). By inductive hypothesis, Φ′ ⊢∀b.φ. Applying (∀E), we obtain Φ′ ⊢φ and the result follows.End of proof

Definition 39

Call Γ; ∆⊢r closed when ∆= ∅ and Γ mentions no variables of level two. Recall that we write ‘Γ; ∅⊢r’ as ‘Γ ⊢r’.

We will use the following fact without comment:

Lemma 40

If Γ ⊢r is closed (so Γ mentions no variables of level two and the freshness context is empty) and Γ ⊢r is typable, then r mentions no variables of level two.

Proof

By induction on derivations.

• The case (Ta∗). r ≡a : ∗. There is nothing to prove since ∗ is not a type.

• The case (Taφ). r ≡a : φ. The result is immediate.

• The case (TX). Clearly r ≡X : φ, hence Γ ⊢r cannot be closed. There is nothing to prove.

• The case (T⊥E). By inductive hypothesis, Γ ⊢r : ⊥ where Γ is closed and r contains no variables of level two. Applying (T⊥E), we have Γ ⊢ xf(r) : φ. The result follows.

• The case (T⇒I). By inductive hypothesis, Γ, a : φ ⊢r : ψ with Γ closed and r containing no variables of level two. Applying (T⇒I), we obtain Γ ⊢λa.r : φ ⇒ψ. The result follows.

• The case (T⇒E). By inductive hypothesis, Γ ⊢r′: φ ⇒ψ and Γ ⊢r : φ with Γ closed and r′ and r containing no variables of level two. Applying (T⇒E), we obtain Γ ⊢r′r : ψ. The result follows.

• The case (T∀I). By inductive hypothesis, Γ, a : ∗⊢r : φ with Γ closed and r containing no variables of level two, where a satisfies the side condition. Applying (T∀I), we obtain Γ ⊢λa.r : ∀a.φ. The result follows.

• The case (T∀E). By inductive hypothesis, we have Γ ⊢r : ∀a.φ with Γ closed and r containing no level two variables. Applying (T∀E), we obtain Γ ⊢rg : φ[a := g] and the result follows.

• The case (Tfr). By inductive hypothesis, Γ, b : τ ⊢r : φ and Γ, b : τ ⊢b#r with r containing no variables of level two and Γ closed, where τ ∈{φ, ∗}. Applying (Tfr), we obtain Γ ⊢r : φ. The result follows.End of proof

Theorem 41

Suppose Γ ⊢r is closed and suppose Γ ⊢r : φ is derivable. Then important(Γ ⊢r) ⊢φ (Definition 14) is derivable in natural deduction.

Proof

By induction on the derivation of Γ ⊢r : φ.

• The case (Taφ). Suppose Γ, a : φ ⊢a : φ. It is then easy to calculate that important(Γ, a : φ ⊢a) = {φ} and φ ⊢φ is a fact.

• The case (TX). As Γ ⊢r is not closed, there is nothing to prove.

• The case (T⊥E). Suppose Γ; ∆⊢r : ⊥. By inductive hypothesis, important(Γ; ∆⊢ r) ⊢⊥. Note important(Γ; ∆⊢r) = important(Γ; ∆⊢ xf(r)). Applying (⊥E), we have important(Γ; ∆⊢ xf(r)) ⊢φ. The result follows.

• The case (T⇒I). Suppose Γ, a : φ ⊢λa.r : φ ⇒ψ and Γ, a : φ ⊢r : ψ. By inductive hypothesis, important(Γ, a : φ ⊢r) ⊢ψ. We now apply (⇒I). If important(Γ, a : φ ⊢λa.r) = important(Γ, a : φ ⊢r) \ {φ} then we discharge φ. Otherwise important(Γ, a : φ ⊢λa.r) = important(Γ, a : φ ⊢r) and we discharge φ zero times. The result follows.

• The case of (T⇒E). Suppose Γ ⊢r′r : ψ and Γ ⊢r′ : φ ⇒ψ and Γ ⊢r : φ. By inductive hypothesis important(Γ ⊢r′) ⊢φ ⇒ψ and important(Γ ⊢r) ⊢φ. By Lemma 38 and (T⇒E), important(Γ ⊢r′) ∪ important(Γ ⊢r) ⊢ψ. By the syntax-directed nature of the freshness rules in Figure 1, Γ ⊢a#r′r if and only if both of Γ ⊢a#r′ and Γ ⊢a#r hold. Therefore, important(Γ ⊢r′r) = important(Γ ⊢r′) ∪ important(Γ ⊢r). The result follows.

• The case (T∀I). Suppose Γ, a : ∗⊢λa.r : ∀a.φ where Γ, a : ∗⊢r : φ and a ∉ fa(important(Γ, a : ∗⊢r)). By inductive hypothesis important(Γ, a : ∗⊢r) ⊢φ. Applying (∀I), important(Γ, a : ∗⊢r) ⊢∀a.φ. The result follows.

• The case (T∀E). Suppose Γ ⊢rg : φ[b := g] and Γ ⊢r : ∀b.φ. By inductive hypothesis important(Γ ⊢r) ⊢∀b.φ. Applying (∀E), important(Γ ⊢r) ⊢φ[b := g]. By reasoning similar to the case of (T⇒E) we can calculate that important(Γ ⊢rg) = important(Γ ⊢r). The result follows.

• The case (Tfr). Suppose Γ ⊢r : φ and Γ, b : τ ⊢r : φ and Γ, b : τ ⊢b#r where τ ∈{φ, ∗}. By inductive hypothesis important(Γ, b : τ ⊢r) ⊢φ. If τ = ∗ then important(Γ, b : ∗⊢r) = important(Γ ⊢r) and the result follows immediately. If τ = φ then, since Γ, b : φ ⊢b#r again important(Γ, b : φ ⊢r) = important(Γ ⊢r). The result follows.End of proof

Theorem 42

If Φ ⊢φ is derivable in natural deduction then there exists some closed Γ ⊢r such that important(Γ ⊢r) ⊆ Φ and Γ ⊢r : φ.

Proof

We prove by induction on the derivation of Φ ⊢φ that there exists some closed typable Γ ⊢r such that:

• important(Γ ⊢r) ⊆ Φ and Γ ⊢r : φ.

• Γ satisfies a uniqueness property: if a : φ ∈ Γ and x : φ ∈ Γ then x = a (so there is at most one variable of level one of each type in Γ).9

We consider each possible rule in turn:

• The case of no rule; Φ ⊢φ because φ ∈ Φ. Suppose fa(φ) = {b1, . . . , bn}. We take Γ = a : φ, b1: ∗, . . . , bn: ∗ and r ≡a. The result follows.

• The case (⊥E). Suppose Φ ⊢⊥. By inductive hypothesis, there exists Γ ⊢r such that important(Γ ⊢r) ⊆ Φ and Γ ⊢r : ⊥. Applying (T⊥E), we have Γ ⊢ xf(r) : φ for arbitrary φ. The result follows.

• The case (⇒I). Suppose Φ ⊢φ ⇒ψ and Φ, φ ⊢ψ. By inductive hypothesis there exists Γ ⊢r such that important(Γ ⊢r) ⊆ Φ ∪{φ} and Γ ⊢r : ψ. If a : φ ∈ Γ for some a then let Γ′ = Γ. If no a exists such that a : φ ∈ Γ then let Γ′ = Γ, a : φ for some a not appearing in Γ. By Theorem 33 Γ′ ⊢r : ψ. It is also a fact that important(Γ ⊢r) = important(Γ′ ⊢r). Applying (T⇒I) we have Γ′ ⊢λa.r : φ ⇒ψ. It is a fact that Γ′ ⊢a#λa.r. Therefore by uniqueness, important(Γ′ ⊢λa.r) = important(Γ′ ⊢r) \ {φ}. The result follows.

• The case (⇒E). Suppose Φ ⊢φ ⇒ψ, and Φ ⊢φ. By inductive hypothesis there exist Γ′ ⊢r′ such that important(Γ′ ⊢r′) ⊆ Φ and Γ′ ⊢r′ : φ ⇒ψ and Γ ⊢r such that important(Γ ⊢r) ⊆ Φ and Γ ⊢r : φ. Without loss of generality we may assume that Γ ∪ Γ′ satisfies our uniqueness condition; we rename variables of level one to make this true if necessary. Applying (T⇒E) and using the fact that important(Γ ∪ Γ′ ⊢r′r) ⊆ Φ, the result follows.

• The case (∀I). Suppose Φ ⊢∀a.φ where a ∉ fa(Φ) and Φ ⊢φ. By inductive hypothesis there exists Γ ⊢r such that important(Γ ⊢r) ⊆ Φ and Γ ⊢r : φ. Since a ∉ fa(Φ) we know that a ∉ fa(important(Γ ⊢r)). If a : ∗∈ Γ then let Γ′ = Γ. If a : ∗∉ Γ then let Γ′ = Γ, a : ∗. If a : ξ ∈ Γ for some type ξ then we are in the pathological situation that a ∉ fa(φ) and a : ξ ∈ Γ ‘by mistake’; we rename a. By Theorem 33 Γ′ ⊢r : φ. It is also a fact that important(Γ ⊢r) = important(Γ′ ⊢r). Applying (T∀I) and using the fact that important(Γ′ ⊢r) = important(Γ′ ⊢λa.r), tshe result follows.

• The case (∀E). Suppose Φ ⊢φ and Φ ⊢∀b.φ. By inductive hypothesis there are Γ and r such that important(Γ ⊢r) ⊆ Φ and Γ ⊢r : ∀b.φ. If Γ ⊢g : ∗ then let Γ′ = Γ. If Γ ⊬g : ∗ then let Γ′ = Γ ∪{a : ∗| a ∈ fa(g)}; we permute atoms in r and Γ to avoid ‘accidental clash’ with atoms in g; by ZFA equivariance (Appendix Appendix A) we retain the inductive hypothesis. By Theorem 33 Γ′ ⊢r : ∀b.φ. It is also a fact that important(Γ ⊢ r) = important(Γ′ ⊢r). Applying (T∀E) and using the fact that important(Γ′ ⊢r) = important(Γ′ ⊢rg), the result follows.End of proof

Γ; ∆⊢r →s(congλa)Γ; ∆⊢λa.r →λa.sΓ; ∆⊢r →s(congapp1)Γ; ∆⊢rt →stΓ; ∆⊢t →u(congapp2)Γ; ∆⊢rt →ruΓ; ∆⊢r →s(congxf)Γ; ∆⊢xf(r) →xf(s)Γ; ∆⊢r →s Γ; ∆⊢a#s Γ; ∆⊢b#s Γ ⊢(a b)(congα)Γ; ∆⊢r →(a b) · s (→1a)Γ; ∆⊢a[a↦ →t] →t(→g)Γ; ∆⊢g′[a↦ →g] →g′[a := g]Γ; ∆⊢a#r(→#)Γ; ∆⊢r[a↦ →t] →r(→xf)Γ; ∆⊢xf(r)[a↦ →t] →xf(r[a↦ →t])Γ; ∆⊢b#t Γ; ∆⊢a#b Γ; ∆⊢b#a(→λa)Γ; ∆⊢(λb.r)[a↦ →t] →λb.(r[a↦ →t])(→app)Γ; ∆⊢(r′r)[a↦ →t] →(r′[a↦ →t])(r[a↦ →t])
Figure 4: Congruence and reduction rules

5. Reductions/proof-normalisation

Part of the Curry-Howard correspondence is that reductions correspond with proof-normalisation. Accordingly, we provide a theory of reductions, hence proof-normaliation, for our syntax:

Definition 43

Let the derivable reductions Γ; ∆⊢r →s be inductively defined by the rules in

Figure 4.

Remark 44

Some comments on the the rules in Figure 4:

• (congα) gives us α-equivalence. It is expressed in the style of nominal terms [UPG04] and more specifically in the style of the permutation rule of nominal algebra [GM07]. It is not syntax-directed, but this will not be a problem for our proofs.

• If Γ; ∆⊢a#π · X holds, then (π · X)[a↦ →t] can reduce in context Γ; ∆ — otherwise, (π · X)[a↦ →t] is simply stuck. In practice we will freshly extend the context (Definition 51) and use (congα) to guarantee the side-condition.

• The freshness conditions in (→λa) avoid ‘accidental capture’. Because both a and b could have types, we must avoid capture not only with respect to t, but also with respect to these 21

types. This is the reason for the a#b and b#a conditions. This retains subject reduction (Theorem 48) by excluding the possibility that for example a : ∗∈ Γ and b : ψ ∈ Γ and a ∈ fa(ψ).

• We prefer a small-step semantics r →s over a big-step semantics r ⇓s, because the proof-theorist can view our small step semantics as directly describing a proof-normalisation algorithm. Note also that terms need not have any normal form (the ‘canonical form’ of Definition 57 is not a normal form, but it serves a similar function), so it is not the case that there is a natural fixed normal form to ‘go to’ in the big step semantics. It is possible to identify a normal form up to rearranging substitutions in a suitable sense, but we leave this to future work, and we do not need it for our proofs.

5.1. Commuting properties of (Tfr)

Given a typing derivation, we may commute all instances of (Tfr) down through the tree, until they reach the root, in a sense made formal by Theorem 46. We will use this in Subsection 5.2 to work with typing derivations such that the non-syntax directed rule (Tfr) is convenienty isolated at the end of a derivation.

Lemma 45

(Tfr) may be commuted down through all other typing rules (Figure 1). The transformations involved do not increase the depth of a derivation.

Proof

By analysing all possibilities.

• The cases (Ta∗), (Taφ) and (TX). There is nothing to show.

• Suppose (Tfr) is followed by (T⊥E). That is, we have:

Γ, A; ∆, b#X ⊢r : ⊥ Γ, A; ∆, b#X ⊢b#r(Tfr)Γ; ∆⊢r : ⊥(T⊥E)Γ; ∆⊢xf(r) : φ

Where A ∈{b : ψ, b : ∗} and b ∉∆. We commute (Tfr) with (T⊥E) to obtain:

Γ, A; ∆, b#X ⊢r : ⊥(T⊥E)Γ, A; ∆, b#X ⊢xf(r) : φ Γ, A; ∆, b#X ⊢b#xf(r)(Tfr)Γ; ∆⊢xf(r) : φ

Where A ∈{b : ψ, b : ∗} and b ∉∆. As we have Γ, A; ∆, b#X ⊢b#r by assumption, we can derive Γ, A; ∆, b#X ⊢b#xf(r) by (a#xf). The result follows by Lemma 31.

• Suppose (Tfr) is followed by (T⇒E). There are two cases:

– The left case. Assume Γ, A; ∆, b#X ⊢b#r′, which can be guaranteed by ZFA equivariance (Appendix Appendix A).

Γ, A; ∆, b#X ⊢r′ : φ ⇒ψ Γ, A; ∆, b#X ⊢b#r′(Tfr)Γ; ∆⊢r′ : φ ⇒ψ Γ; ∆⊢r : φ(T⇒E)Γ; ∆⊢r′r : ψ

Where A ∈{b : ψ, b : ∗} and b ∉∆. We commute (Tfr) with (T⇒E) to obtain:

Γ, A; ∆, b#X ⊢r′ : φ ⇒ψ Γ, A; ∆, b#X ⊢r : φ(Tfr)Γ, A; ∆, b#X ⊢r′r : ψ Γ, A; ∆, b#X ⊢b#r′r(T⇒E)Γ; ∆⊢r′r : ψ

Where A ∈{b : ψ, b : ∗} and b ∉∆. The result follows.

– The right case. Assume Γ, A; ∆, b#X ⊢b#r, which can be guaranteed by ZFA equivariance (Appendix Appendix A).

Γ; ∆⊢r′ : φ ⇒ψΓ, A; ∆, b#X ⊢r : φ Γ, A; ∆, b#X ⊢b#r(Tfr)Γ; ∆⊢r : φ(T⇒E)Γ; ∆⊢r′r : ψ

Where A ∈{b : ψ, b : ∗} and b ∉∆. We commute (Tfr) with (T⇒E) to obtain:

Γ, A; ∆, b#X ⊢r′ : φ ⇒ψ Γ, A; ∆, b#X ⊢r : φ(T⇒E)Γ, A; ∆, b#X ⊢r′r : ψ Γ, A; ∆, b#X ⊢b#r′r(Tfr)Γ; ∆⊢r′r : ψ

Where A ∈{b : ψ, b : ∗} and b ∉∆. The result follows.

• Suppose (Tfr) is followed by (T⇒I). That is we have:

Γ, a : φ, A; ∆, b#X ⊢r : ψ Γ, a : φ, A; ∆, b#X ⊢b#r(Tfr)Γ, a : φ; ∆⊢r : ψ(T⇒I)Γ, a : φ; ∆⊢λa.r : φ ⇒ψ

Where A ∈{b : ψ, b : ∗} and b ∉∆. Renaming using ZFA equivariance (Appendix Appendix A) if necessary, we assume that b ∉ fa(φ). We may commute (Tfr) with (T⇒I) to obtain:

Γ, a : φ, A; ∆, b#X ⊢r : ψ(T⇒I)Γ, a : φ, A; ∆, b#X ⊢λa.r : φ ⇒ψ Γ, a : φ, A; ∆, b#X ⊢b#λa.r(Tfr)Γ, a : φ; ∆⊢λa.r : φ ⇒ψ

Where A ∈{b : ψ, b : ∗} and for some b ∉∆. Then, by assumption, Γ, a : φ, A; ∆, b#X ⊢

b#r therefore Γ, a : φ, A; ∆, b#X ⊢b#λa.r by (a#λb). The result now follows from Lemma 31. The case for

Γ, a : φ, A; ∆, a#X ⊢r : ψ Γ, a : φ, A; ∆, a#X ⊢a#r(Tfr)Γ, a : φ; ∆⊢r : ψ(T⇒I)Γ, a : φ; ∆⊢λa.r : φ ⇒ψ

where A ∈{a : φ, a : ∗} and for some a ∉∆, follows immediately, using Lemma 31, as a#λa.r always, by (a#λa).

• Suppose (Tfr) is followed by (T∀I). That is we have:

Γ, a : ∗, A; ∆, b#X ⊢r : φ Γ, a : ∗, A; ∆, b#X ⊢b#r(Tfr)Γ, a : ∗; ∆⊢r : φ(T∀I)Γ, a : ∗; ∆⊢λa.r : ∀a.φ

Where A ∈{b : ψ, b : ∗}, b ∉∆ and a ∉ fa(important(Γ, a : ∗; ∆⊢r)). We may commute

(Tfr) with (T∀I) to obtain:

Γ, a : ∗, A; ∆, b#X ⊢r : φ(T∀I)Γ, a : ∗, A; ∆, b#X ⊢λa.r : ∀a.φ Γ, a : ∗, A; ∆, b#X ⊢b#λa.r(Tfr)Γ, a : ∗; ∆⊢λa.r : ∀a.φ

Where A ∈{b : ψ, b : ∗}, b ∉∆ and by assumption, a ∉ fa(important(Γ, a : ∗; ∆⊢r)). The result follows.

• Suppose (Tfr) is followed by (T∀E). That is, we have:

Γ, A; ∆, b#X ⊢r : ∀a.φ Γ, A; ∆, b#X ⊢b#r(Tfr)Γ; ∆⊢r : ∀a.φ(T∀E)Γ; ∆⊢rg : φ[a := g]

Where A ∈{b : ξ, b : ∗} and b ∉∆. Renaming if necessary, we suppose that a and b are distinct. Also permuting if necessary, we suppose that b ∉ fa(g); we use ZFA equivariance (Appendix Appendix A) to retain the inductive hypothesis. We commute (Tfr) with (T∀E) to obtain:

Γ, A; ∆, b#X ⊢r : ∀a.φ(T∀E)Γ, A; ∆, b#X ⊢rg : φ[a := g] Γ, A; ∆, b#X ⊢b#rg(Tfr)Γ; ∆⊢rg : r[a := g]

Where A ∈{b : ξ, b : ∗} and b ∉∆. As Γ, A; ∆, b#X ⊢b#r, we can derive Γ, A; ∆, b#X ⊢ b#rg using (a#app). The result follows by Lemma 31.End of proof

Theorem 46

Suppose Π is a derivation of Γ; ∆⊢r : φ. Then there exists a derivation Π′, also of Γ; ∆⊢r : φ, such that Π′ ends in some (possibly zero many) instances of (Tfr), and contains no other instances of (Tfr).

In words: “all instances of (Tfr) may be pushed to the conclusion of the typing derivation”.

Proof

By Lemma 45.End of proof

5.2. Subject reduction

In this subsection we investigate three forms of consistency under reduction. Lemma 47 states that ‘no variables are created’ by reductions; in the terminology of [FG07b, Section 6] we can say that reduction is uniform. Theorem 48 is a subject-reduction property; if we reduce a derivation of a proposition, then it remains a derivation of that same proposition. In the proof of Theorem 48, we induct on the derivation of a reduction r →s and perform case analysis on the way in which r : φ can have been derived; the results of Subsection 5.1 are needed here, to control the non-syntax-directed rule (Tfr).

Lemma 49 is an object-level equivariance property; reduction is preserved under permuting variables of level one (compare this with [FG07b, Theorem 50, part 3]). Lemma 49 is technically important in Subsection 5.3 for Lemma 61, which is the key result for confluence (Theorem 62).

Lemma 47

If Γ; ∆⊢a#r and Γ; ∆⊢r →s then Γ; ∆⊢a#s.

Proof

By induction on the derivation of Γ; ∆⊢r →s.

• The case (→1a). There are two cases:

– The case a[a↦ →t]. We have Γ; ∆⊢a[a↦ →t] →t and Γ; ∆⊢a#(λa.a)t. This implies that Γ; ∆⊢a#λa.a and Γ; ∆⊢a#t. The result follows.

– The case b[b↦ →u]. We have Γ; ∆⊢b[b↦ →u] →u and Γ; ∆⊢a#(λb.b)u. This implies that Γ; ∆⊢a#λb.b and Γ; ∆⊢a#u. The result follows.

• The case (→g). We have Γ; ∆⊢g′[a↦ →g] →g′[a := g]. It is a fact that fa(g′[a↦ →g]) ⊆ fa(g′[a := g]). The result follows.

• The case (→#) where Γ; ∆⊢a#r. There are two cases:

– The case a#r[a↦ →t]. The result follows by assumption. 24

– The case b#r[a↦ →t]. We have Γ; ∆⊢b#(λa.r)t hence Γ; ∆⊢b#r and Γ; ∆⊢b#t. The result follows from the fact that Γ; ∆⊢r[a↦ →t] →r.

• The case (→app). There are two cases:

– The case (r′r)[a↦ →t]. We have Γ; ∆⊢ (r′r)[a↦ →t] →r′[a↦ →t](r[a↦ →t]) and by assumption, Γ; ∆⊢a#t. Note that Γ; ∆⊢a#λa.r′ Γ; ∆⊢a#λa.r and Γ; ∆⊢a#t. The result follows.

– The case Γ; ∆⊢ (r′r)[b↦ →u]. We have Γ; ∆⊢ (r′r)[b↦ →u] →r′[b↦ →u](r[b↦ →u]) and Γ; ∆⊢a#(r′r)[b↦ →u]. This implies that Γ; ∆⊢a#λb.(r′r) therefore Γ; ∆⊢a#r′ and Γ; ∆⊢a#r and also that Γ; ∆⊢a#u. With these facts, we may derive Γ; ∆⊢ a#((λb.r′)u)((λb.r)u). The result follows.

• The case (→λa). There are several cases:

– The case (λb.r)[a↦ →t] where Γ; ∆⊢b#t, Γ; ∆⊢b#a, and Γ; ∆⊢a#b. We have Γ; ∆⊢ (λb.r)[a↦ →t] →λb.(r[a↦ →t]) and Γ; ∆⊢a#(λa.(λb.r))t. This implies that Γ; ∆⊢a#λa.(λb.r) and Γ; ∆⊢a#t. With this, Γ; ∆⊢a#λb.((λa.r)t). The result follows.

– The case (λb.r)[c↦ →v] where Γ; ∆⊢b#v, Γ; ∆⊢b#c, and Γ; ∆⊢c#b. We have Γ; ∆⊢ (λb.r)[c↦ →v] →λb.(r[c↦ →v]) and Γ; ∆⊢a#(λc.(λb.r))v. This implies that Γ; ∆⊢a#λc.(λb.r) therefore Γ; ∆⊢a#r and also Γ; ∆⊢a#v. With these facts, we may derive Γ; ∆⊢a#λb.((λc.r)v). The result follows.

– The case (λa.r)[b↦ →u] where Γ; ∆⊢a#u, Γ; ∆⊢b#a, and Γ; ∆⊢a#b. We have Γ; ∆⊢ (λa.r)[b↦ →u] →λa.(r[b↦ →u]). It is a fact that Γ; ∆⊢a#λa.(r[b↦ →u]) always. The result follows.

• The case (→xf). There are two cases:

– The case xf(r)[a↦ →t]. We have Γ; ∆⊢ xf(r)[a↦ →t] → xf(r[a↦ →t]) and Γ; ∆⊢ a#λa.(xf(r))t. This implies that Γ; ∆⊢a#λa.(xf(r)) and Γ; ∆⊢a#t. With this, we may derive Γ; ∆⊢a#xf((λa.r)t). The result follows.

– The case xf(r)[b↦ →u]. We have Γ; ∆⊢ xf(r)[b↦ →u] → xf(r[b↦ →u]) and Γ; ∆⊢ a#λb.(xf(r))u. This implies that Γ; ∆⊢a#λb.(xf(r)) therefore Γ; ∆⊢a#r and Γ; ∆⊢ a#u. With these facts, we may derive Γ; ∆⊢a#xf((λb.r)u). The result follows.

• The case (congλa). There is only a one case, as Γ; ∆⊢a#λa.s always. Therefore, consider Γ; ∆⊢a#λb.r. This implies Γ; ∆⊢a#r. By inductive hypothesis Γ; ∆⊢a#r implies Γ; ∆⊢a#s. Therefore Γ; ∆⊢a#λb.s. The result follows.

• The case (congapp1). By assumption, Γ; ∆⊢a#rt. This implies that Γ; ∆⊢a#r and Γ; ∆⊢a#t. By inductive hypothesis, Γ; ∆⊢a#r implies Γ; ∆⊢a#s. Therefore, Γ; ∆⊢ a#st. The result follows.

• The case (congapp2) is similar to the previous case.

• The case (congxf). By assumption, Γ; ∆⊢a#xf(r) therefore Γ; ∆⊢a#r. By inductive hypothesis, Γ; ∆⊢a#r implies Γ; ∆⊢a#s. Therefore, Γ; ∆⊢a#xf(s). The result follows.

• The case (congα). By assumption, Γ; ∆⊢b#s, Γ; ∆⊢c#s and Γ; ∆⊢a#r. By inductive hypothesis, Γ; ∆⊢a#s. By Lemma 19, we have Γ; ∆⊢a#(b c) · s. The result follows.End of proof

Theorem 48 (Subject Reduction).

If Γ; ∆⊢r : φ and Γ; ∆⊢r →s then Γ; ∆⊢s : φ.

Proof

By induction on the derivation of Γ; ∆⊢r →s. In a sense illustrated in the case of (→1a), we may conveniently ignore (Tfr).

• The case (→1a). Suppose Γ; ∆⊢a[a↦ →t] →t. By definition a[a↦ →t] ≡ (λa.a)t. Suppose Γ; ∆⊢ (λa.a)t : φ. By Theorem 46 there is a derivation of Γ; ∆⊢ (λa.a)t : φ such that all instances of (Tfr) occur at the end of the derivation. Therefore, for some Γ′ and ∆′ extending Γ and ∆, Γ′; ∆′ ⊢λa.a : φ ⇒φ and Γ′; ∆′ ⊢t : φ. Using Lemma 47 (or by concrete calculations) we can now extend the derivation of Γ′; ∆′ ⊢ t : φ to a derivation of Γ; ∆⊢t : φ, as required. From now on, we will elide the treatment of (Tfr), which is identical in all the following cases.

• The case (→g). Suppose Γ; ∆⊢g′[a↦ →g] →g[a := g]. It is a fact that fa(g′[a := g]) ⊆ fa(g′[a↦ →g]). It follows that if Γ; ∆⊢g′[a↦ →g] : ∗ then Γ; ∆⊢g′[a := g] : ∗.

• The case (→#) where Γ; ∆⊢a#r. Suppose Γ; ∆⊢r[a↦ →t] →r. By definition r[a↦ →t] ≡ (λa.r)t. Suppose Γ; ∆⊢ (λa.r)t : φ. There are now two cases:

– a : φ′ ∈ Γ and Γ; ∆⊢r : φ and Γ; ∆⊢t : φ′.

– a : ∗∈ Γ and Γ; ∆⊢r : φ and Γ; ∆⊢t : ∗.

In either case, Γ; ∆⊢r : φ.

• The case (→app). Suppose Γ; ∆⊢ (r′r)[a↦ →t] → (r′[a↦ →t])(r[a↦ →t]). By definition (r′r)[a↦ →t] ≡ (λa.(r′r))t and (r′[a↦ →t])(r[a↦ →t]) ≡ ((λa.r′)t)((λa.r)t). There are now four cases:

– Γ; ∆⊢ (λa.(r′r))t : φ because a : ψ ∈ Γ, Γ; ∆⊢t : ψ, Γ; ∆⊢r′ : φ′ ⇒φ, and Γ; ∆⊢r : φ′ ∈ Γ.

– Γ; ∆⊢ (λa.(r′r))t : φ[a := t] because a : ∗∈ Γ, Γ; ∆⊢t : ∗, Γ; ∆⊢r′ : φ′ ⇒φ, and Γ; ∆⊢r : φ′ ∈ Γ.

– (λa.(r′r))t : φ[b := r] because a : ψ, Γ; ∆⊢t : ψ, Γ; ∆⊢r′: ∀b.φ, and Γ; ∆⊢r : ∗.

– (λa.(r′r))t : φ[b := r][a := t] because a : ∗∈ Γ, Γ; ∆⊢t : ∗, Γ; ∆⊢r′ : ∀b.φ, and Γ; ∆⊢r : ∗.

In each case, it is routine to verify the result. For example in the final case, it is routine to verify that Γ; ∆⊢ ((λa.r′)t)((λa.r)t) : φ[b := r][a := t] as required.

• The case (→λa). Suppose Γ; ∆⊢ (λb.r)[a↦ →t] →λb.(r[a↦ →t]) where Γ; ∆⊢b#t, Γ; ∆⊢ b#a, and Γ; ∆⊢a#b. By definitinion (λb.r)[a↦ →t] ≡ (λa.(λb.r))t and λb.(r[a↦ →t]) ≡ λb.((λa.r)t). There are now two cases:

– Γ; ∆⊢ (λa.(λb.r))t : φ′ ⇒φ because a : ψ, b : φ′ ∈ Γ, Γ; ∆⊢t : ψ, and Γ; ∆⊢r : φ.

– Γ; ∆⊢ (λa.(λb.r))t : (φ′ ⇒φ)[a := t] because a : ∗, b : φ′ ∈ Γ, Γ; ∆⊢t : ∗, and Γ; ∆⊢r : φ.

– Γ; ∆⊢ (λa.(λb.r))t : ∀b.φ because a : ψ, b : ∗∈ Γ, Γ; ∆⊢t : ψ, and Γ; ∆⊢r : φ.

– Γ; ∆⊢ (λa.(λb.r))t : (∀b.φ)[a := t] because a : ∗, b : ∗∈ Γ, Γ; ∆⊢t : ∗, and Γ; ∆⊢r : φ.

In each case, it is routine to verify the result. For example in the final case, that Γ; ∆⊢ λb.((λa.r)t) : ∀b.(φ[a := t]).

• The case (→xf). Suppose Γ; ∆⊢ xf(r)[a↦ →t] : φ. By definition xf(r)[a↦ →t] ≡ (λa.(xf(r)))t. There are now two cases:

– Γ; ∆⊢ (λa.(xf(r)))t : ⊥ because a : ψ ∈ Γ and Γ; ∆⊢r : φ.

– Γ; ∆⊢ (λa.(xf(r)))t : ⊥ because a : ∗∈ Γ and Γ; ∆⊢r : φ.

In each case, it is routine to verify the result. For example in the first case, that Γ; ∆⊢ xf(r) :

⊥.

• The case (congα). Suppose Γ; ∆⊢r : φ, Suppose Γ; ∆⊢ (a b) and Γ; ∆⊢a#r and Γ; ∆⊢b#r. Since Γ; ∆⊢r →s, by inductive hypothesis Γ; ∆⊢s : φ. By Lemma 47, Γ; ∆⊢a#s and Γ; ∆⊢b#s. It follows by Lemma 25 that Γ; ∆⊢ (a b) · s : φ, as required.

• The case (congλa). Suppose Γ; ∆⊢r →s and Γ; ∆⊢λa.r →λa.s. There are now two cases:

– Γ; ∆⊢λa.r : φ′ ⇒φ and a : φ′ ∈ Γ. By inductive hypothesis Γ; ∆⊢s : φ. By (T⇒I) Γ; ∆⊢s : φ′ ⇒φ.

– Γ; ∆⊢λa.r : ∀a.φ and a : ∗∈ Γ. By inductive hypothesis Γ; ∆⊢s : φ. Using Lemma 47 we see that important(Γ ⊢s) ⊆ important(Γ ⊢r). It follows using (T∀I) that Γ; ∆⊢λa.s : ∀a.φ.

• The cases of (congapp1), (congapp2), and (congxf) are no harder.End of proof

Lemma 49

If Γ; ∆⊢r →s then Γ; ∆⊢π · r →π · s.

Proof

By induction on derivations.

• The case (→1a). We have π · (a[a↦ →t]) ≡π(a)[π(a) ↦→π · t]. The result follows from (→1a).

• The case (→g) is similar.

• The case (→#) where Γ; ∆⊢a#r. We have π · (r[a↦ →t]) ≡ (π · r)[π(a) ↦→π · t]. By Lemma 19, we have Γ; ∆⊢π(a)#π · r. Applying (→#), we derive Γ; ∆⊢ (π · r)[π(a) ↦→ π · t] →π · r. The result follows.

• The case (→app). We have π · ((r′r)[a↦ →t]) ≡ ((π · r′)(π · r))[π(a) ↦→π · t]. Applying (→app), we obtain ((π · r′)[π(a) ↦→π · t])((π · r)[π(a) ↦→π · t]). The result follows from the definition of the permutation action.

• The case (→λa) where Γ; ∆⊢b#t, Γ; ∆⊢b#a, and Γ; ∆⊢a#b. We have π · ((λb.r)[a↦ → t]) ≡ (λπ(b).(π ·r))[π(a) ↦→π ·t]. By Lemma 19, we have Γ; ∆⊢π(b)#π ·t. Applying (→λa), we have Γ; ∆⊢ (λπ(b).(π · r))[π(a) ↦→π · t] →λπ(b).((π · r)[π(a) ↦→π · t]). The result follows by the definition of the permutation action.

• The case (→xf). We have π · (xf(r)[a↦ →t]) ≡ xf(π · r)[π(a) ↦→π · t]. Applying (→xf), we have Γ; ∆⊢ xf(π · r)[π(a) ↦→π · t] → xf((π · r)[π(a) ↦→π · r]). The result follows.

• The case (congapp1). By inductive hypothesis, we have Γ; ∆⊢π · r →π · s. Applying (congapp1), we have Γ; ∆⊢ (π · r)(π · t) → (π · s)(π · t). The result follows.

• The case (congapp2) is similar to the previous case.

• The case (congλa). By inductive hypothesis, we have Γ; ∆⊢π · r →π · s. Applying (congλa), we have Γ; ∆⊢λπ(a).(π · r) →λπ(a).(π · s). The result follows.

• The case (congxf). By inductive hypothesis, we have Γ; ∆⊢π · r →π · s. Applying (congxf), we have Γ; ∆⊢ xf(π · r) → xf(π · s). The result follows.

• The case (congα). By inductive hypothesis, we have Γ; ∆⊢π · r →π · s. Further, by Lemma 19, we have Γ; ∆⊢π(a)#π · s and Γ; ∆⊢π(b)#π · s. Applying (congα), we obtain Γ; ∆⊢π · r → (π(a) π(b)) · (π · s). The result follows from elementary properties of permutations.End of proof

5.3. Confluence

The next notion of correctness, following subject reduction discussed in Theorem 48 in Subsection 5.2, is confluence and the identification of a canonical reduced version of any derivation. This is Definition 57 and Theorem 62.

Choose some fixed but arbitrary order on variables of level one. If S is a finite set of variables of level one say ‘for the first variable of level one not in S’ to mean ‘for the least variable of level one, in our fixed but arbitrary order, that is not an element of S’. This is convenient, though not necessary, for expressing the proofs to follow. We will never make infinitely many choices of fresh variable of level one, and nowhere will the truth of a result depend on our choice of order.

Definition 50

Define a substitution action on terms, with respect to a typing and freshness context, Γ; ∆ by the rules below. Earlier rules take priority.

• r[a := t] ≡r if Γ; ∆⊢a#r.

• a[a := t] ≡t.

• (π · X)[a := t] ≡(π · X)[a↦ →t].

• (λb.r)[a := t] ≡λb.(r[a := t]) if Γ; ∆⊢b#t, Γ; ∆⊢a#b, and Γ; ∆⊢b#a.

• (λb.r)[a := t] ≡λc.(((b c) · r)[a := t]) if Γ; ∆⊬b#t. Here c is the first fresh variable of level one of the same type as b in Γ if such a variable exists. That is, c is the first variable of level one, with the same type as b, according to our order, that is not mentioned in r, t, a, or b (so Γ; ∆⊢c#r and Γ; ∆⊢c#t), if such a c exists.

• (r′r)[a := t] ≡r′[a := t](r[a := t])

• xf(r)[a := t] ≡ xf(r[a := t])

Note in Definition 50 that r[a := t] depends on Γ; ∆ and that r[a := t] need not necessarily exist. This is a partial definition; however, we may guarantee that r[a := t] exists for suitably extended versions of Γ and ∆.

Definition 51

Suppose that Γ; ∆ and Γ+; ∆+ are pairs of typing and freshness contexts. Say Γ+; ∆+ freshly extends Γ; ∆ when there exist Γ′ and ∆′ such that:

• Γ′ gives types to the variables of level one appearing in ∆′, and to no other variables of level one (and to no variables of level two).

• If a#X ∈∆′ then X is given a type in Γ.

• If a#X ∈∆′ then a does not appear in Γ or ∆.

• ∆+ = ∆∪∆′

• Γ+ = Γ ∪Γ′

Intuitively, Γ+; ∆+ ‘extends Γ; ∆ with some fresh variables of level one’.

Definition 52

Define →∗ as the reflexive, transitive closure of →.

Lemma 53

Suppose that Γ ⊆ Γ′ and ∆⊆∆′.

If Γ; ∆⊢r →s then Γ′; ∆′ ⊢r →s.

Proof

By induction on the derivation of Γ; ∆⊢r →s.

• The case (→1a). Since Γ′; ∆′ ⊢a[a↦ →t] →t always, by (→1a).

• The case (→g) is similar.

• The case (→#). Suppose Γ; ∆⊢a#r. By Lemma 31, Γ′; ∆′ ⊢a#r. Then Γ′; ∆′ ⊢r[a↦ → t] →r. The result follows.

• The case (→xf). Since Γ′; ∆′ ⊢ xf(r)[a↦ →t] → xf(r[a↦ →t]) always, by (→xf).

• The case (→λa). Suppose Γ; ∆⊢b#t, Γ; ∆⊢b#a, and Γ; ∆⊢a#b. By Lemma 31, Γ′; ∆′ ⊢ b#t, and similarly for b#a and a#b. Then Γ′; ∆′ ⊢ (λb.r)[a↦ →t] →λb.(r[a↦ →t]) always, by (→λa). The result follows.

• The case (→app). Since Γ′; ∆′ ⊢ (r′r)[a↦ →t] →r′[a↦ →t](r[a↦ →t]) always, by (→app).

• The case (congλa). By inductive hypothesis, Γ′; ∆′ ⊢r →s. Applying (congλa), we obtain Γ′; ∆′ ⊢λa.r →λa.s. The result follows.

• The case (congapp1). By inductive hypothesis, Γ′; ∆′ ⊢r →s. Applying (congapp1), we obtain Γ′; ∆′ ⊢rt →st. The result follows.

• The case (congapp2). By inductive hypothesis, Γ′; ∆′ ⊢t →u. Applying (congapp1), we obtain Γ′; ∆′ ⊢rt →ru. The result follows.

• The case (congxf). By inductive hypothesis, Γ′; ∆′ ⊢r →s. Applying (congxf), we obtain Γ′; ∆′ ⊢ xf(r) → xf(s). The result follows.

• The case (congα). Suppose Γ; ∆⊢r →s, with Γ; ∆⊢a#s, Γ; ∆⊢b#s and Γ ⊢ (a b). By inductive hypothesis, Γ′; ∆′ ⊢r →s. By Lemma 31, Γ′; ∆′ ⊢a#s and Γ′; ∆′ ⊢b#s. As Γ′ satisfies Definition 6, we have Γ′ ⊢ (a b). Applying (congα), we obtain Γ′; ∆′ ⊢r → (a b)·s. The result follows.End of proof

The following definition and lemma are used in the proof of Lemma 56.

Definition 54

Define the depth of a term by:

depth(a) = 1 depth(π · X) = 1 depth(λa.r) = 1 + depth(r)depth(r′r) = depth(r′) + depth(r) depth(xf(r)) = 1 + depth(r)
Lemma 55

depth(π · r) = depth(r)

Proof

By induction on r.

• The case a. Since π is a bijection on variables of level one.

• The case π′ · X. By Lemma 18, π · (π′ · X) ≡ (π◦π′) · X. Further, depth((π◦π′) · X) = depth(π′ · X). The result follows.

• The case λa.r. We have π · λa.r ≡λπ(a).(π · r). By inductive hypothesis, depth(π · r) = depth(r). The result follows.

• The case r′r. By inductive hypothesis, depth(π·r′) = depth(r′) and depth(π·r) = depth(r). The result follows.

• The case xf(r). By inductive hypothesis, depth(π · r) = depth(r). The result follows.End of proof

Lemma 56

For every Γ; ∆, r, a, s and t there exist Γ+ freshly extending Γ and ∆+ freshly extending ∆ such that

Γ+; ∆+ ⊢r[a↦ →t] →∗r[a := t].

(r[a := t] calculated for Γ+; ∆+.)

Proof

By induction on the depth of r.

• The case a. We have a[a := t] ≡t and also Γ; ∆⊢a[a↦ →t] →∗t.

• The case b. We have b[a := t] ≡b and also Γ; ∆⊢b[a↦ →t] →∗b.

• The case π · X. If Γ; ∆⊢a#π · X then we have (π · X)[a := t] ≡π · X and Γ; ∆⊢ (π · X)[a↦ →t] →∗ (π · X) also. Otherwise, we have Γ; ∆⊢ (π · X)[a↦ →t] →∗ (π · X)[a↦ →t] and (π · X)[a := t] ≡ (π · X)[a↦ →t]. The result follows.

• The case λa.r. We have (λa.r)[a := t] ≡λa.r and Γ; ∆⊢ (λa.r)[a↦ →t] →∗λa.r.

• The case λb.r. If Γ; ∆⊢a#λb.r, then (λb.r)[a := t] ≡λb.r and Γ; ∆⊢ (λb.r)[a↦ →t] →λb.r. Otherwise, there are two cases:

– The case Γ; ∆⊢b#t, Γ; ∆⊢b#a, and Γ; ∆⊢a#b. We have (λb.r)[a := t] ≡λb.(r[a := t]). Applying (→λa) Γ; ∆⊢ (λb.r)[a↦ →t] →λb.(r[a↦ →t]). By inductive hypothesis Γ+; ∆+ ⊢r[a↦ →t] →∗r[a := t] for some Γ+ and ∆+ freshly extending Γ and ∆. The result follows using Lemma 53.

– Otherwise, we have (λb.r)[a := t] ≡ (λc.((b c) · r))[a := t] where c is a suitably fresh variable of level one of suitable type, obtained from the freshly extended contexts Γ+ and ∆+. Applying (congα) and (→λa)

Γ+; ∆+ ⊢(λb.r)[a↦ →t] →∗(λc.((b c) · r))[a↦ →t].

By inductive hypothesis and Lemma 55, we have

Γ+; ∆+ ⊢((b c) · r)[a↦ →t] →∗((b c) · r)[a := t].

The result follows.

• The case r′r. If Γ; ∆⊢a#r′r then the result follows immediately. Otherwise, (r′r)[a := t] ≡r′[a := t](r[a := t]) and Γ; ∆⊢ (r′r)[a↦ →t] →∗r′[a↦ →t](r[a↦ →t]) by (→app). The result follows by the inductive hypothesis for r and r′.

• The case xf(r). We have xf(r)[a := t] ≡ xf(r[a := t]). The result follows by the inductive hypothesis for r.End of proof

Definition 57

Let the canonical form r⋆ of r in the context Γ; ∆ be inductively defined by the following rules, where earlier rules take priority:10

g⋆≡g (π · X)⋆≡(π · X) (λa.r)⋆≡λa.r⋆(r[a↦ →t])⋆≡r⋆[a := t⋆] (r′r)⋆≡(r′⋆)(r⋆) where r’ is not an abstractionxf(r)⋆≡xf(r⋆)

Note that r⋆ depends on the context Γ; ∆. It need not be defined, because [a := t⋆] need not always be defined (see the comment following Definition 50). However, in a sense made formal by Lemma 58 this does not matter because we can freshly extend the context.

Note also that (r⋆)⋆≢r⋆ in general, so taking the canonical form is not idempotent. This will not be a problem. r⋆ is a choice of representative of the terms that r rewrites to; a choice which happens to be very useful for proving confluence (Theorem 62). Intuitively, r⋆ is a rewrite of r such that

“all substitutions have been pushed down, and through each other, at least once”.

Lemma 58

For every Γ; ∆ and r there exist Γ+ and ∆+ such that Γ+; ∆+ ⊢r →∗r⋆. (r⋆ calculated for Γ+; ∆+.)

Proof

By induction on r.

• The case a. Since a⋆≡a.

• The case π · X. Since (π · X)⋆≡π · X.

• The case λa.r. By inductive hypothesis, Γ+; ∆+ ⊢r →∗r⋆. The result follows from λa.(r⋆) ≡ (λa.r)⋆.

• The case r′r. The special case r[a↦ →t], by definition syntactically identical to (λa.r)t, follows from Lemma 56. Otherwise, by inductive hypothesis, Γ+; ∆+ ⊢r′ →∗r′⋆ and Γ+; ∆+ ⊢r →∗r⋆. The result follows from r′⋆(r⋆) ≡ (r′r)⋆.

• The case xf(r). By inductive hypothesis, Γ+; ∆+ ⊢r →∗r⋆. The result follows from xf(r⋆) ≡ xf(r)⋆.End of proof

For the rest of this subsection, Γ+; ∆+ will be a context freshly extending Γ; ∆ with sufficient freshness such that all the canonical forms we require exist. We will always be clear about what these canonical forms are.

Lemma 59

Fix Γ; ∆. Then Γ; ∆⊢a#s implies Γ; ∆⊢a#s⋆. (s⋆ calculated for Γ; ∆.)

Proof

By induction on derivations.

• The case (a#b). Since b⋆≡b.

• The case (a#g). Since g⋆≡g.

• The case (a#λa). We have (λa.r)⋆≡λa.r⋆ and Γ; ∆⊢a#λa.r⋆ always.

• The case (a#λb). By inductive hypothesis, Γ; ∆⊢a#r⋆. Applying (a#λb), we have Γ; ∆⊢a#λb.r⋆. The result follows.

• The case (a#X). As (π · X)⋆≡π · X.

• The case (a#b′). Since b⋆≡b.

• The case (a#app). By inductive hypothesis, Γ; ∆⊢a#r′⋆ and Γ; ∆⊢a#r⋆. Applying (a#app) and simple manipulation, we have Γ; ∆⊢a#(r′r)⋆. The result follows.

• The case (a#xf). By inductive hypothesis, Γ; ∆⊢a#r⋆. Applying (a#xf) and simple manipulation, we obtain Γ; ∆⊢a#xf(r)⋆. The result follows.End of proof

Lemma 60

(π · r)⋆≡π · r⋆

Proof

By induction on r.

• The case a. Since a⋆≡a for all variables of level one.

• The case π′ · X. We have (π′ · X)⋆≡π′ · X. The result follows from Lemma 18.

• The case r′r. We have π·((r′r)⋆) ≡ (π·(r′⋆))(π·(r⋆)). The result follows from the inductive hypothesis.

• The case λa.r. Since (π·λa.r)⋆≡ (λπ(a).(π·r))⋆≡λπ(a).((π·r)⋆). Applying the inductive hypothesis, we have λπ(a).((π · r)⋆) ≡λπ(a).(π · r⋆). The result follows from the definition of the permutation action.

• The case xf(r). Since (π · xf(r))⋆≡ xf(π · r)⋆≡ xf((π · r)⋆). By application of the inductive hypothesis, xf((π · r)⋆) ≡ xf(π · r⋆). The result follows.End of proof

Lemma 61

Γ; ∆⊢r →s implies Γ+; ∆+ ⊢s⋆→∗r⋆.

Proof

By induction on derivations. Note the reversal from r →s to s⋆→∗r⋆.

• The case (→1a). We have:

Γ; ∆⊢a[a↦ →t] →t Γ+; ∆+ ⊢t⋆→∗(a[a↦ →t])⋆

as (a[a↦ →t])⋆≡t⋆ and the result follows.

• The case (→g). We have:

Γ; ∆⊢g′[a↦ →g] →g′[a := g] Γ+; ∆+ ⊢(g′[a := g])⋆→∗(g′[a↦ →g])⋆

as (g′[a↦ →g])⋆≡g′[a := g] ≡ (g′[a := g])⋆ and the result follows.

• The case (→#) when Γ; ∆⊢a#r. We have:

Γ; ∆⊢r[a↦ →t] →r Γ+; ∆+ ⊢r⋆→∗(r[a↦ →t])⋆as (r[a↦ →t])⋆≡r⋆when Γ; ∆⊢a#r.

• The case (→λa) when Γ; ∆⊢b#t, Γ; ∆⊢a#b, and Γ; ∆⊢b#a. We have:

Γ; ∆⊢(λb.r)[a↦ →t] →λb.(r[a↦ →t]) Γ+; ∆+ ⊢(λb.(r[a↦ →t]))⋆→∗((λb.r)[a↦ →t])⋆as (λb.(r[a↦ →t]))⋆≡λb.(r⋆[a := t⋆]) ≡((λb.r)[a↦ →t])⋆.

• The case (→xf). We have:

Γ; ∆⊢(xf(r))[a↦ →t] →xf(r[a↦ →t]) Γ+; ∆+ ⊢(xf(r[a↦ →t]))⋆→∗((xf(r))[a↦ →t])⋆as (xf(r[a↦ →t]))⋆≡(xf(r⋆[a := t⋆])) ≡((xf(r))[a↦ →t])⋆.

• The case (congλa). By inductive hypothesis, Γ+; ∆+ ⊢s⋆→∗r⋆. We now argue by induction on the path length of Γ+; ∆+ ⊢s⋆→∗r⋆. If the path is empty, then s⋆≡r⋆ and the result follows. Otherwise, we have the case Γ+; ∆+ ⊢s⋆→∗r′⋆→r⋆. By inductive hypothesis, it follows that Γ+; ∆+ ⊢λa.s⋆→∗λa.r′⋆. Applying (congλa), it follows that Γ+; ∆+ ⊢λa.r′⋆→λa.r⋆. It now follows, by the definition of the reflexive transitive closure, that Γ+; ∆+ ⊢λa.s⋆→∗λa.r⋆. The result follows.

• The case (congapp1). By inductive hypothesis, Γ+; ∆+ ⊢s⋆→∗r⋆. Applying (congapp1) and an inductive argument similar to the previous case we derive Γ+; ∆+ ⊢s⋆(t⋆) →∗ r⋆(t⋆). The result follows.

• The case (congapp2) is similar to the previous case.

• The case (congxf). By inductive hypothesis, Γ+; ∆+ ⊢s⋆→∗r⋆. By induction on the path length of Γ+; ∆+ ⊢s⋆→∗r⋆ and applying (congxf), the result follows.

• The case (congα). Suppose s ≡ (a b) · s′. Suppose Γ; ∆⊢r →s′ and Γ; ∆⊢a#s′ and Γ; ∆⊢b#s′. By inductive hypothesis, Γ+; ∆+ ⊢s′⋆→∗r⋆. By Lemma 59 Γ+; ∆+ ⊢a#s′⋆ and Γ+; ∆+ ⊢b#s′⋆. By Lemma 47 it follows that Γ+; ∆+ ⊢a#r⋆ and Γ+; ∆+ ⊢b#r⋆. Applying (congα) it follows that Γ+; ∆+ ⊢s′⋆→∗ (a b) · (r⋆). By Lemmas 49 and 18 it follows that Γ; ∆+ ⊢ (a b) · (s′⋆) →∗r⋆. By Lemma 60 Γ+; ∆+ ⊢s⋆→∗r⋆. The result follows.End of proof

Theorem 62

If Γ; ∆⊢s ∗←r →∗t then Γ+; ∆+ ⊢s →∗u ∗←t. That is, → is Church–Rosser.

Proof

Suppose Γ; ∆⊢r →∗s and Γ; ∆⊢r →∗t. By Lemma 58 fresh extensions Γ1; ∆1 of Γ; ∆ exist such that Γ1; ∆1 ⊢r →∗r⋆. Again by Lemma 58, fresh extensions Γ2; ∆2 and Γ3; ∆3 of Γ; ∆, exist such that Γ2; ∆2 ⊢s →∗s⋆ and Γ3; ∆3 ⊢t →∗t⋆. By Lemma 61 a fresh extension Γ4; ∆4 of Γ2; ∆2, and a fresh extension Γ5; ∆5 of Γ3; ∆3, exist such that Γ4; ∆4 ⊢s⋆→∗r⋆ and Γ5; ∆5 ⊢t⋆→∗r⋆. Taking Γ+ = ⋃1≤i≤5 Γi and ∆+ = ⋃1≤i≤5 ∆i, the result follows.

For the reader’s convenience we rewrite this argument as a diagram:

rs◀∗t∗-s⋆∗?∗- r⋆∗? ◀∗t⋆∗?End of proof

We illustrate this for X[a↦→t][b↦→u], where Γ; ∆⊢a#u:

X[a↦→t][b↦→u]X[a↦→t][b↦→u]◀∗X[b↦→u][a↦→t[b↦→u]]∗-X[b↦→u][a↦→t[b↦→u]]∗?∗- X[b↦→u][a↦→t[b↦→u]]∗?◀∗X[a↦→t[b↦→u]][b↦→u[a↦→t[b↦→u]]]∗?

6. Conclusions

We have shown how nominal terms, endowed with a non-trivial typing system, model incomplete derivations in first-order logic.

We use a one-and-a-half level syntax building on ideas from one-and-a-halfth order logic [GM08a]: variables of level one model variable symbols and can be quantified (we use variables of level one to model both type and term variables); variables of level two model ‘holes’. This 33

reflects informal practice in which instantiation of meta-variables (modelled here by variables of level two) captures object-level abstraction (modelled by variables of level one and their abstraction).

This paper is part of a larger project to develop nominal techniques in general, and in particular to study a multi-level syntax, in which capturing-substitution is explicitly represented, and using permutations to manage α-conversion in the presence of multiple levels of variable.

6.1. Related work

This paper builds on a conference version [GM08b]. This journal paper gives full proofs, and it also extends results as follows:

• The type language is now full first-order logic, rather than first-order logic without term-formers.11

• We have added to the syntax of our Curry-Howard system a theory of α-equivalence, following nominal terms and based on permutations in the style of [GP01, UPG04]. This is (congα), and more specifically, it is based on the permutation rule (perm) from nominal algebra [GM07].

• We have given notions of β-reduction/proof-normalisation.

This paper ‘just’ studies a type system for nominal terms. Has this not been done before? Not in a way that helps us for constructing Curry-Howard for first-order logic. A sorting system for nominal terms from [UPG04] is not suitable; it is designed to construct abstract syntax and atoms (variables of level one in our terminology) have sort ‘the sort of atoms’, thus they do not populate other types as do the variables of level one in this paper. A typing system [FG07a] is not suitable, for two reasons:

• Types corresponded with propositional logic with quantifiers whereas here, we want first-order logic.

• Here, we want to represent (∀I) and (∀E) (Figure 2) so terms may λ-abstract over and be applied to type variables, and we require freshness for type variables. In [FG07a] type-variables do not inhabit terms in any way.

A body of research exists, aimed at providing formalisms for representing incomplete derivations:

Muñoz, Asperti. Of all the work we have seen in the literature, that by Muñoz [Muñ96] seems closest in spirit to ours. Muñoz works towards representing incomplete derivations in dependent types — a goal more ambitious than ours, of representing incomplete derivations of first-order logic, but not one which creates any essential difficulties aside from problems of scale and presentation. We believe that what Muñoz tries to do, and what we try to do, are essentially the same thing. The major difference, which we believe is an advantage of our approach, is our use of nominal terms — Muñoz uses de Bruijn indexes. The first sixty pages of [Muñ96] are devoted to discussing the problems, and solutions, of representing reduction in a λ-calculus with explicit substitutions based on de Bruijn indexes. Then ‘meta-variables’ (level two variables in our terminology) are introduced. These are essentially identical to our level two variables and admit a capturing substitution (see Definition 3.1.7 in [Muñ96]) — but they exist in the de Bruijn framework.

The Matita [ACTZ07] proof assistant, based on the Curry-Howard isomorphism, employs Muñoz’s approach for representing unspecified proofs. It would be interesting future work to create a similar proof assistant based on our approach. We hope this could permit a higher-level style of programming in the same way that for example FreshOCaml or α-Prolog (also based on the nominal model of names and binding) are intended to allow a higher-level style of programming on datatypes with names [SP05, CU03]. This is future research.

Jojgov and Geuvers. Jojgov and Geuvers [GJ02] study incomplete derivations in higher-order logic (a popular logic for proof assistants). Their work may be seen as a generalisation of that of Muñoz, wherein they generalise the approach and re-establish the Curry-Howard isomorphism, but may also be viewed as a systemization of the techniques used in the Coq and Matita proof assistants.

They create o-HOL, which conservatively extends HOL with ‘open’ terms and ‘open’ (incomplete) proofs. ‘Metavariables’ (level two variables in our terminology) are represented in o-HOL syntax. Their treatment of α-conversion is not nominal, but neither is it quite ‘traditional’. In particular it does capture a kind of capturing substitution which they, like us, call instantiation. See the definition of metavariable instantiation on page 546 (page 10 of the paper, just after Definition

11), which in simplified form reads like this:

n[q]{n[y] := t} = t[q/y]

Here n is a metavariable symbol, q and t are terms, and y is a(n ordinary, level one) variable. n[q] seems to correspond with what we might write as ‘X[- ↦→q]’ and the metavariable instantiation {n[y] := t} seems to correspond with what we might write as ‘[y↦ → -][X := t]’. By this (rather ingenious) device Jojgov and Geuvers avoid many of the pitfalls described in [Bog02, Subsection 2.1 onwards], [Muñ97, Subsection 1.4.1], and [GL08, Introduction] of combining (in our terminology) variables of different levels.

The precise technical relationship between our term language and that of Jojgov and Geuvers is currently unclear and might be the topic of future work.

Miller and McBride. McBride’s Oleg system [McB99] is a theorem proving environment, based on Luo’s ECC, augmented with what McBride calls ‘holes’, which a Prolog programmer might recognise as ‘logical variables’ or ‘existential variables’. Intuitively, an existential variable has operational or logical content ‘please find a suitable value for me’.12 McBride’s syntax for a existential variable is ?x.p where p is a term. See Section 2.3 of [McB99] where rules are presented for searching for values for, and instantiating values for, existential variables.

If the existential variables represent a datatype of derivation-trees, then terms with existential variables represent incomplete derivations. There is no a priori proof-theory or reduction system for such a datatype built in to McBride’s system (it is just a datatype).

McBride’s system comes closer to our goals if we consider that a term containing a existential variable in McBride’s system does in a suitable sense represent an ‘incomplete inhabitant’ of the type it populates. If that type is a type of truth-values then the term represents an ‘incomplete inhabitant’ of a type of truth-values, thus, an ‘incomplete proof’. In fact our level two variables X are neither overtly existential nor universal. We have given no operational semantics for instantiating them (note that we have studied instantiation of X — see Definition 50 and the subsequent results — we just have not internalised this to, for example, a derivation-instantiating strategy). However, level two variables X exist at top level and we, looking at the system from the outside, typically want to ‘find some complete derivation’, i.e. we want to instantiate X with some term of the right type. Thus for us, the X do intuitively possess an existential flavour. Then the difference between our work and McBride’s is our ‘nominal style’ term language; McBride’s treatment of existential variables and instantiation is based on ‘traditional’ α-equivalence and capture-avoiding substitution. Essentially, our work and McBride’s are two complementary systems; we do not study existential variables for their own sake (though they do appear in our system to represent ‘unknown derivations’!) — and McBride does not study instantiation. In that light, our argument is that for Curry-Howard for incomplete derivations we need logical variables and instantiation. Thus, it might be interesting to take the ideas about treating logical variables from McBride’s research and combine them with our nominal treatment of level two variables in order to build a system in which our meta-level consideration of instantiating X can be internalised in, say, the tactics language of a theorem-prover. This is future work.

Miller’s work [Mil92] also considers existential variables, by considering unification with a mixed (i.e. ∀/∃) prefix. Normally, a unification problem takes the form ∃x1. . . xn.s1 = t1. . . sm = tm. Miller is interested in finding solutions to problems of the form Qx1. . . Qxn.s1 = t1. . . sm = tm, where Q may represent either a universal or an existential quantifier, and the terms, si, ti are simply typed λ-terms. A universally quantified variable behaves like a constant within its scope, whereas an existentially quantified variable is available for substitution. Differing sequences of quantifiers modify the behaviour of substitutions applied to the equations. For example, ∀ι ⇒ιf.∃ιx.∀ιw.[(fw) = x] does not have a solution, as the naming apart of bound variables and substitutions requires that any substitution for x will fail to obtain equality. The quantifier prefix constrains the behaviour of substitutions similarly to ‘nominal style’ freshness conditions. The existence of existential variables can be used to express ‘incomplete derivations’. Again, the treatment of all variables is ‘traditional’, based on α-equivalence and capture-avoiding substitution.

Magnusson. ALF is a proof assistant based on Martin-Löf type theory [Mag93]. As far as we know this was the first to explicitly represent incomplete derivations. This is done using proof terms containing meta-variables (‘place-holders’ in ALF parlance). Each meta-variable is annotated with a ‘local context’, which is a list of variables upon which an expression to which the place-holder is refined, may depend. In addition, typing constraints on substituted expressions limit which expressions may be used to refine a meta-variable [Nor93].

The ALF approach has much in common with the Oleg approach of McBride [McB99], and with the approaches of Muñoz and Jojgov [Joj02].

Stoughton, Gunter and Rémy. Stoughton [Sto98] used a system capable of representing incomplete derivations for a programming language semantics animator, DOPS (Deterministic OPerational Semantics). DOPS uses a typed lambda calculus as a metalanguage, and neither non-determinism nor non-termination of the object language are possible. Stoughton’s representation of incomplete derivations uses this fact—an incomplete derivation tree is represented as a tree with branches missing coupled with a ‘resumption’. The action of the resumption is uniquely determined by the evaluation relation of the object language in question, and extends the coupled tree with new branches, if possible, when executed.

Gunter and Rémy [GR93] appear to have first proposed using representations of incomplete derivations for animating programming language semantics. They provided a brief informal overview of their idea, but did not expand on it, nor did they implement a system [Sto98].

Other, distantly related work. We also briefly note contributions by Bognar [Bog02] and Hashimoto and Ohori [HO01]. Bognar’s calculi treat terms with holes but their approach is essentially based on ‘traditional’ α-equivalence and λ-lifting, as can be seen for example in [Bog02, Definition 4.2.11]. Hashimoto and Ohori [HO01] admit capturing substitution and use a sophisticated type system to control it (and its interaction with capture-avoiding substitution which we referred to in the Introduction). There is no discussion of how suited these systems would be to a Curry-Howard correspondence.

6.2. Future work

This paper is part of a mathematical project to explore how multi-level systems — with capturing as well as capture-avoiding substitution — serve as a mathematical foundation for informal practice. In this paper we have seen how the ideas of two levels of variable, with freshness conditions, and permutations, can be used to as a formal syntax and operational semantics for a Curry-Howard for incomplete derivations.

We see four broad avenues for building on the system in this paper:

Types for multi-level calculi. The Lambda-Context Calculus [GL08, GL09] has levels of variables and an operational semantics, but it does not feature a nominal terms style α-equivalence based on permutations — in [GL08], the first author wrote about possible applications to modelling incomplete derivations. Two level λ-calculus has two levels of variable [GM09a]. This has λa and also a λX, substitution for X does not avoid capture by λa, and nominal terms style α-equivalence.

This paper would then be a rather powerful type system (more than Hindley-Milner for example) for the λX-free fragment of two level λ-calculus; we are reasonably confident this would extend to λX. That is for future work.

Implementation. We ask whether the ideas in this paper can be useful for the theory or practice of writing theorem provers. Can these ideas be refined and extended and applied to represent and program on intermediate proof-states in the kernel of a theorem-prover?

Nominal unification is known to be decidable [UPG04], and Fernández and Calvès have shown that nominal unification can be performed in polynomial time [CF07]. Further, Fernández and Gabbay [FG07b] provided sufficient conditions on terms for efficient, polynomial time, nominal rewriting. Thus, nominal terms have some good computational properties which we may be able to exploit. This need not be too large a job, since the kernel of a theorem-prover can be quite small (a few thousand lines of code).

Note that we have not developed the mathematics of our representation with efficiency in mind (for example, our term-reduction/derivation-normalisation system is small-step, and non-terminating). Improving the computational properties of our representation is future work. Note that this is not necessarily very difficult. For example the non-termination could be dealt with by introducing an explicit substitution. As is often the case, we trade mathematical simplicity for computational efficiency: this would add an extra term-former and lengthen some proofs, which is why we did not do it here (some further comment on this issue, follows below).

In principle, nominal terms may be useful for implementing tactics within a theorem prover. For instance, many tactics lift subterms of λ-terms into a new context. This operation is complex due to the possibility of inadvertently capturing variables. Employing similar techniques to those presented in this paper may allow a more straightforward and less error-prone implementation of complex tactics. It may also be interesting to consider one-and-a-halfth level terms as a language for communicating incomplete derivations between systems.

Extensions of the system. It should not be hard to change the types and/or the terms of our calculus to suit other logical systems. For example we can follow Muñoz and try to enrich types in the direction of a dependent type theory, attempting to develop the typing rules from Figure 1 into a dependent type theory similar to that of Martin-Löf [BN90]. This would be distinct from a dependent type theory with elements of nominal techniques [SS04], which treats atoms (variables of level one) as variable symbols.

Likewise, we can try to extend the system to other logics, with λ-abstraction for level two variables (following the two level λ-calculus of [GM09a] or the lambda context calculus of [GL08, GL09]), or we can extend with explicit rules for instantiating level two variables and with constructs internalising other aspects of proof-search like instantiation and backtracking, following the example of McBride [McB99].

Finally, we mentioned goal-directed proof theory in the Introduction [GO00]. This field of research is devoted to the study of reasoning from conclusions towards assumptions, and to our knowledge no Curry-Howard correspondence has been developed for it.13 Thus, it seems a good avenue for future work to apply the techniques used in this paper for a sequent system, to the goal-directed one.

Improving the system. Our calculus has no strong normalisation result; (λb.((λa.c)a))b (which we also write c[a↦ →a][b↦ →b], using the notation of Definition 5) can reduce indefinitely in the empty freshness context, because the β-redexes can ‘skip over’ one another, and the term is typable. For the same reason, strong normalisation is not preserved for the natural translation of the untyped λ-calculus to the (level 1) fragment of our language; consider the λ-term (λy.((λx.z)x))y.

There is a current of research devoted to creating calculi for computation which are computationally efficient and also are amenable to mathematical treatment; according to those criteria, it is clear that our calculus could be improved. Note however that even if computational efficiency is not a concern, we can be interested in elegant proofs (see below) and we can consider efficiency a separate concern, much as one might program in the λ-calculus but execute on an abstract machine. In particular, one can imagine a version of this calculus in which level 2 variables are annotated with parallel substitutions so that we can outlaw the ‘skipping’ behaviour mentioned above. This is future work.

So we should now take a critical look at the proofs in this paper, and this brings us to the main issue with this paper. The proofs are quite long, and rather complex: why?

1. We do not apply the familiar parallel reduction proof-method to prove confluence (attributed to Tait and Martin-Löf and documented, for example, in Barendregt’s book [Bar84]). Instead, we use a proof-method based on a canonical form (Definition 57) and a diagram (Theorem 62). We developed this method for the λ-context calculus [GL08, GL09]. At the time we thought it was original but in fact it is close to one discovered by Takahashi [Tak95].14 This proof-method has much to commend it; to quote Takahashi commenting on her application of it to prove the theorem of confluence of the untyped λ-calculus, it is “rigorous, direct, and perhaps the shortest among all the known proofs of the theorem”. Our proof is longer, but this is just because it is applied to the more complex syntax of this paper. We consider the proof-method used in this paper to be a feature, not a bug. We now come to what we consider the main issue with our calculus:

2. The notion of α-equivalence, which is inherited from nominal terms [UPG04], is a source of complexity. First, α-equivalence depends on a freshness context and is not inherent to terms. This means that we cannot ‘just quotient by α-equivalence’, because the relation over which we would like to quotient is dependent on the freshness context. The obvious solution is to fix one the freshness context, but this is not possible because for confluence we may specifically wish to ‘freshly extend it’ (Definition 51) with extra fresh atoms. For similar reasons, in the typing rules we introduce a ‘freshly extending’ rule (Tfr) (Figure 1). This combination of factors puts two non-syntax-directed rules in the theory of this paper, (Tfr) and (congα), and we must argue up to fresh extensions of the freshness context. We trace most of the complexity of this paper to these factors (for example, the results in Subsection 5.1 are all devoted to controlling (Tfr)).

Since this paper was written, and as a response to these issues, we have investigated permissive nominal terms and also semantic nominal terms [DGM09, GM09c, GM09b]. These do away with freshness contexts and are based on the idea of infinite and coinfinite sets of atoms (a set is coinfinite when its sets complement is infinite). Because sets are coinfinite, it is always guaranteed that there is a fresh atom, so that we can ‘just quotient’ by α-equivalence and there is no need for freshly extended contexts, nor for rules to handle these things. Developing this further is future research.

References

[ACTZ07] Andrea Asperti, Claudo Sacerdoti Coen, Enrico Tassi, and Stefano Zacchiroli. Crafting a Proof Assistant, pages 18–32. Lecture Notes in Computer Science. Springer, 2007.

[Bar84] Henk P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, 1984.

[BN90] Jan M. Smith Bengt Nordstrom, Kent Petersson. Programming in Martin-Löf’s Type Theory, volume 7 of International Series of Monographs on Computer Science. Clarendon Press, Oxford, 1990. Also online at http://www.cs.chalmers.se/Cs/Research/Logic/book/.

[Bog02] Mirna Bognar. Contexts in Lambda Calculus. PhD thesis, Vrije Universiteit Amsterdam, 2002.

[Bru96] Norbert Brunner. 75 years of independence proofs by Fraenkel-Mostowski permutation models. Mathematica Japonica, 43:177–199, 1996.

[CF07] Christophe Calvès and Maribel Fernández. Implementing nominal unification. Electronic Notes in Theoretical Computer Science, 176(1):25–37, 2007.

[CU03] J. Cheney and C. Urban. System description: Alpha-Prolog, a fresh approach to logic programming modulo alpha-equivalence. In UNIF’03, pages 15–19. Universidad Politecnica de Valencia, 2003.

[CU04] James Cheney and Christian Urban. Alpha-prolog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proc. of the 20th Int’l Conf. on Logic Programming (ICLP 2004), number 3132 in Lecture Notes in Computer Science, pages 269–283. Springer, 2004.

[dB80] N.G. de Bruijn. A survey of the project AUTOMATH. In Hindley and Seldin, editors, To H.B.Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism. Academic Press, 1980.

[DGM09] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. In CILC, 24th Italian Conference on Computational Logic, 2009.

[FG07a] Maribel Fernández and Murdoch J. Gabbay. Curry-style types for nominal terms. In Types for Proofs and Programs (proceedings of TYPES’06), volume 4502 of Lecture Notes in Computer Science, pages 125–139. Springer, 2007.

[FG07b] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, 2007.

[Gab07] Murdoch J. Gabbay. Fresh Logic. Journal of Applied Logic, 5(2):356–387, June 2007.

[GJ02] Herman Geuvers and Gueorgui I. Jojgov. Open proofs and open terms: A basis for interactive logic. In Computer Science Logic: 16th International Workshop, pages 537–552, 2002.

[GL08] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. Electronic Notes in Theoretical Computer Science, 196:19–35, 2008.

[GL09] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus (extended version). Information and computation, 2009.

[GM93] Michael J. C. Gordon and Thomas F. Melham. Introduction to HOL: A Theorem Proving Environment for Higher Order Logic. Cambridge University Press, 1993.

[GM07] Murdoch J. Gabbay and Aad Mathijssen. A Formal Calculus for Informal Equality with Binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162–176. Springer, 2007.

[GM08a] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic. Journal of Logic and Computation, 18(4):521–562, August 2008.

[GM08b] Murdoch J. Gabbay and Dominic P. Mulligan. One-and-a-halfth Order Terms: Curry-Howard for Incomplete Derivations. In Proceedings of 15th Workshop on Logic, Language and Information in Computation (WoLLIC 2008), volume 5110 of Lecture Notes in Artificial Intelligence, pages 180–194, 2008.

[GM09a] Murdoch J. Gabbay and Dominic P. Mulligan. Two-and-a-halfth Order Lambda-calculus. Electronic Notes in Theoretical Computer Science, 2009. To appear.

[GM09b] Murdoch J. Gabbay and Dominic P. Mulligan. Semantic nominal terms. In TAASN, 2009.

[GM09c] Murdoch J. Gabbay and Dominic P. Mulligan. Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables. LFMTP’09: Proceedings of the Fourth International Workshop on Logical Frameworks and Meta-Languages, 64–73, 2009.

[GO00] Dov Gabbay and Nicola Olivetti. Goal Directed Algorithmic Proof Theory, volume 21 of Applied Logic Series. Kluwer Academic, 2000.

[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, 2001.

[GR93] Carl A. Gunter and Didier Rémy. A proof theoretic assessment of runtime type errors. Technical Report 11261-921230-43TM, AT&T Bell Laboratories, 1993.

[HO01] Masatomo Hashimoto and Atsushi Ohori. A typed context calculus. Theoretical Computer Science, 266(1-2):249– 272, 2001.

[Joj02] Gueorgui I. Jojgov. Holes with binding power. In TYPES, volume 2646 of Lecture Notes in Computer Science, pages 162–181. Springer, 2002.

[Mag93] Lena Magnusson. Refinement and local undo in the interactive proof assistant ALF. In Informal Proceedings of the 1993 Workshop on Types for Proofs and Programs, pages 237–253, 1993.

[Mat07] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.

[McB99] Conor McBride. Dependently Typed Functional Programs and their Proofs. PhD thesis, University of Edinburgh, 1999.

[Mil92] Dale Miller. Unification under a mixed prefix. Journal of Symbolic Computation, 14(4):321–358, 1992.

[MP93] James McKinna and Randy Pollack. Pure Type Systems formalized. In Proceedings of the International Conference 39

on Typed Lambda Calculi and Applications (TLCA’93), number 664 in LNCS, pages 289–305. Springer-Verlag,

March 1993. [Muñ96] César Muñoz. Proof representation in type theory: State of the art. In Proceedings of the 22nd Latin American

Conference on Informatics (CLEI Panel 96), 1996. [Muñ97] César Muñoz. A Calculus of Explicit Substitutions for Incomplete Proof Representation in Type Theory. PhD thesis, INRIA Rocqencourt, Projet Coq, 1997.

[Nor93] Bengt Nordström. The ALF proof editor. In Proceedings of the Workshop on Types for Proofs and Programs (TYPES 1993), pages 253–266, 1993.

[Pau89] Lawrence C. Paulson. The foundation of a generic theorem prover. Journal of Automated Reasoning, 5(3):363– 397, 1989.

[PCW05] Iman Hafiz Poernomo, John Newsome Crossley, and Martin Wirsing. Adapting Proofs-as-Programs: The Curry– Howard Protocol. Number XII in Monographs in Computer Science. Springer, 2005.

[SP05] Mark R. Shinwell and Andrew M. Pitts. Fresh objective Caml user manual. Technical Report UCAM-CL-TR- 621, University of Cambridge, 2005.

[SS04] Ulrich Schöpp and Ian Stark. A Dependent Type Theory with Names and Binding. In CSL, volume 3210 of Lecture Notes in Computer Science, pages 235–249, 2004.

[Sto98] Alley Stoughton. An operational semantics framework supporting the incremental construction of derivation trees. In Second Workshop on Higher-Order Operational Techniques in Semantics (HOOTS II), volume 10 of Electronic Notes in Theoretical Computer Science. Elsevier Science B. V., 1998.

[Tak95] Makato Takahashi. Parallel reductions in lambda-calculus. Information and Computation, 1(118):120–127, 1995.

[Tru94] John Truss. Permutations and the axiom of choice. In H.D.Macpherson R.Kaye, editor, Automorphisms of first order structures, pages 131–152. OUP, 1994.

[UPG04] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, 2004.

[US06] Pawel Urzyczyn and Morten Sørensen. Lectures on the Curry-Howard isomorphism, volume 149 of Studies in Logic. Elsevier, 2006.

Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.

Appendix A. ZFA equivariance

Equivariance is well-studied in model theory [Tru94, Bru96]; in a sentence, equivariance states that truth is invariant under permuting atoms, where an ‘atom’ is an element with no structure, aside from being equal to itself. Variable symbols are an example of something ‘in nature’ which can naturally be viewed as atomic.

Permutations were used in computer science already in [MP93]. In [GP01] equivariance was noted as a meta-mathematical fact of Fraenkel-Mostowski set theory and used to deduce the some/any property of the ‘NEW’-quantifier and thus derive new inductive reasoning principles for syntax-with-binding. In [Gab07] equivariance was used in a discursive proof (that is, in the informal but rigorous mathematical argument of a published paper) to ‘rename variable symbols’ without losing the inductive hypothesis. In [GM08a, Appendix A], equivariance was explicitly stated and proved as a meta-mathematical principle of Zermelo-Fraenkel set theory with atoms (a more general, and more standard, foundational system than Fraenkel-Mostowski set theory, which does not have its ‘finite support’ property; see [GP01] for details).

We will now briefly recap on [GM08a, Appendix A], but instead of axiomatic set theory we will use a ‘lighter’ argument based on von Neumann cumulative hierarchies.

Fix a collection of atoms (recall the sets of level one variables from Subsection 2.1). Write this set A. Define a cumulative hierarchy by:

U0 = A Uα =⋃β<αP(Uβ) ∪UβU =⋃αUα

Here P denotes the powerset and α and β range over ordinals. Intuitively U is a collection of well-founded (possibly infinitely-branching) trees, which is constructed by transfinite induction starting from trees consisting of a single node labelled with an element of A. This is the standard model of Zermelo-Fraenkel set theory with atoms. It is a sufficently rich structure to build all of usual mathematics, and it has been argued that this is the foundational mathematical universe most commonly used in ‘practical mathematics’ (rather than Zermelo-Fraenkel set theory, without atoms).

A permutation Π is a bijection on A (we do not care if {a | Π(a) ≠ a} is finite or not). We define a permutation action on U by:

Π · a = Π(a) Π · U = {Π · u | u ∈U}

Here U ∈U \ A and a ∈A.

Now let terms T and predicates Φ be inductively defined by:

T ::= X | A Φ ::= Φ ⇒Φ | ⊥| ∀X.Φ | T = T | T ∈T

Here X are variable symbols. This is the language of first-order logic. This happens to be very similar to the language of types investigated in this paper (because we wanted to model an interesting logic), but Φ here is intended to be a model of the informal but rigorous mathematical arguments written in English in this paper. In other words, the Φ model the statements of lemmas and theorems in this paper, and the theory of truth for Φ over U is sufficiently rich to soundly capture the mathematics in those lemmas and theorems.

It then suffices to observe the following:

Theorem 63

Φ(X1, . . . , Xn) is true of U, if and only if Φ(Π · X1, . . . , Π · Xn) is true.

Proof

By induction on Φ. It suffices to observe that:

• u ∈u′ if and only if Π · u ∈ Π · u′

• u = u′ if and only if Π · u = Π · u′.

• Π · A = A.End of proof

When in the body of this paper we permute variable symbols, we use Theorem 63 to retain the inductive hypothesis.

Notes

1http://www.gabbay.org.uk ↩

2http://www.macs.hw.ac.uk/˜dpm8 ↩

3We are grateful to Jojgov for the examples in his paper [Joj02]. ↩

4Within the context of nominal terms, we use the following naming convention: ‘one-level’ refers to calculi without nominal unknowns; ‘one-and-a-halfth level’ refers to calculi possessing unknowns but with no quantification or abstraction over them, and ‘two-level’ refers to calculi with nominal unknowns and the ability to quantify or abstract over them. See [GM09a] for a detailed discussion. ↩

5See Figure 3 for more details. ↩

6This paper does not internalise proof-search. We prove that instantiation of level two variables is admissible, but we have no explicit instantiation rule, no backtracking rule, and so on. How to get from incomplete derivations to complete derivations is a separate issue, for us, from how to represent the incomplete derivations — but an interesting one which could be the topic of future work. See the discussion of McBride’s system in the Conclusions. ↩

7The first author is known for studying the problem of reasoning on datatypes up to α-equivalence. We do not study that problem in this paper. ↩

8 Note that in natural deduction, Φ, φ ⊢φ is automatic — ‘if we allow Φ, φ as assumptions, then we assume φ, and so we have φ’. There is no need for a derivation rule. ↩ ↩

9Here x ranges over all variables of level one, not necessarily permutatively, so perhaps x = a. ↩

10It has been pointed out to us that the technique we use to prove confluence resembles a proof by Makato Takahashi [Tak95]. This ‘convergent evolution’ is interesting and suggests to us the existence of some deeper mathematics, which we have not fully understood. At the very least, there should be a general method here which could be brought out. ↩

11Thanks to an anonymous reviewer for pointing this out. ↩

12The operational behaviour of a language with existential variables is typically to return an instantiation satisfying constraints on those variables, as in Prolog. Contrast this with functional or ‘universal’ variables λx.p with operational or logical content ‘you can replace me with anything you like’, as in function application in functional languages. ↩

13Dov Gabbay, private communication. ↩

14Takahashi’s proof still defines a parallel reduction relation, whereas the proof we give uses just multiple β-reduction, but the underlying ideas of the two proofs are very similar. ↩