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

One-and-a-halfth order terms: Curry-Howard and incomplete derivations

Murdoch J. Gabbay1 and Dominic P. Mulligan2

1 http://www.gabbay.org.uk 2 http://www.macs.hw.ac.uk/~dpm8/

Abstract. The Curry-Howard correspondence connects Natural Deduction derivation 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 an ‘incomplete derivation’, with ‘holes’.

This is natural in informal practice; the challenge is to formalise it. To this end we use a one-and-a-halfth order technique based on nominal terms, with two levels of variable. Predicates are types, derivations are terms — and the two levels of variable are respectively the assumptions and the ‘holes’ of an incomplete derivation.

1 Introduction

The Curry-Howard correspondence [US06,PCW05] connects logic with typed λ-calculus: predicates are types; derivations are terms; discharge is λ-abstraction; modus ponens is application; β-reduction is proof-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 λ-calculus supports ‘forwards’ reasoning, where we plug together complete derivations to form larger ones. However, we may wish to reason ‘backwards’: We start from an incomplete derivation of the desired conclusion and we work backwards to construct a derivation. Then we may have ‘half a derivation’, like as below left with a ‘hole’ called X:

··· X B[A]a A⇒B⇒C B⇒CCaA⇒C[A]a··· X A ⇒B B[A]a A⇒B⇒C B⇒CCaA⇒C[A]a··· X A ⇒B B[A]a A⇒B⇒C B⇒CCaA⇒C

Here, λ-calculus syntax is less helpful. X corresponds with qa in the complete derivation, so (being straighforward about it) the incomplete derivation corresponds with ‘λa.((pa)X)’. But X is under a λ-binder and should be instantiated; substituted for without avoiding capture. This is impossible within the λ-calculus. Most interesting logics are undecidable so theorem-proving is often interactive (like AUTOMATH [dB80] and its many descendents). This leads us to study calculi tailored to represent incomplete derivations.

In this paper we build on previous work by the first author and others on nominal techniques [GP01] and specifically nominal terms [UPG04] and one-and-a-halfth order logic [GM07]. These were designed specifically to study binding (in unification up to α-equivalence, and derivation-schema in first-order logic respectively). They feature two levels of variables, freshness conditions, and permutations; details are in this paper, and in the work cited above. In this paper we extend this pallette of ideas to represent binding in incomplete derivations. We are reasonably ambitious in our choice of logic for which to represent incomplete derivations: we will consider first-order predicate logic; this is a significantly more complex target than propositional logic, and it leads to quite a rich syntax.

In the style of Miller [Mil92], McBride’s OLEG system [McB99], and a collection of λ-calculi by Bognar [Bog02], we can represent X by fa where f is a ‘normal’ variable, perhaps recording in a context f should be instantiated; f ⊢λa.((pa)fa). A problem from our point of view is, for example, that the representation of the incomplete derivation above left is identical to that of distinct incomplete derivations above centre and above right, in which X is refined.

Another approach is to extend the λ-calculus with hereditarily parameterised meta-variables (hereditarily, since the parameters may themselves have ‘holes’). This path is taken by Jojgov [Joj02], and for a non-hereditary notion of parameters, by Severi and Poll [SP94], and Bloo et al [BKLN02].

Following one-and-a-halfth order logic [GM07] we propose an approach based on nominal terms [UPG04]. Nominal terms have atoms a, b, c, . . . and unknowns X, Y, Z, . . .. Crucially, substitution of unknowns does not avoid capture by atoms, and we reason on what unknowns do not depend on, rather than using parameters to record what they might depend on (a#X versus fa; see ‘freshness’ below). The first author, Urban, Pitts, and Cheney amongst others have argued in favour this approach [UPG04,FG07,Mat07,Pit02,Che05].4

We further this argument and show that atoms, unknowns and freshness model assumptions, holes, and discharge in incomplete derivations.

Consider an example; definitions are in the body of the paper:

(1)··· X ⊥⇒A(2)[⊥]a··· X ⊥⇒A(3)[⊥]a··· X′A(⇒I)a⊥⇒A(4)[⊥]a(⊥E)A(⇒I)a⊥⇒A(1) X:⊥⇒φ ⊢X:⊥⇒φ (2) X:⊥⇒φ, a:⊥; a#X ⊢X:⊥⇒φ (3) a:⊥, X′:φ ⊢λa.X′:⊥⇒φ (4) a:⊥⊢λa.xf(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-halfth order Curry-Howard. Note that:

− Assumptions are represented by atoms. Types are predicates assumed.

− Incomplete parts of the derivation, or (using terminology from the theorem-proving community) subgoals, are represented by unknowns. 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’.

This paper is ‘just’ about 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 have sort ‘the sort of atoms’. A typing system [FG06] is not suitable; types corresponded to propositional logic with quantifiers whereas here, we want first-order logic and; we also 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.

Some words on what this paper is not: it is not proof-search [PR05,MS06]. We study binding in incomplete derivations, but not the act of stepping from one derivation to another. We also give no semantics to our syntax: There is no denotational semantics (Scott domains spring to mind; we would require an extended version, perhaps like FM (nominal) domain theory [SP05]). There is not even an operational semantics (reduction of derivations), though we do plan this for a later paper; see the Conclusions.

2 Terms, types, and Natural Deduction

2.1 Terms and types

We give definitions, then discuss examples in Remark 10 and Subsection 2.2.

Fix disjoint countably infinite sets of atoms A and unknowns. We let a, b, c, d, . . . range over atoms. We use a permutative convention; they range permutatively over atoms, so for example ‘a and b’ means ‘a pair of two distinct atoms’. Similarly we let X, Y, Z, . . . range permutatively over unknowns.5

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

Definition 1

Let types be:

φ, ψ, ξ ::= ⊥| φ ⇒φ | P(ar(P) var’bles a, . . . ) | ∀a.φ.

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

We equate types up to ∀-bound atoms. We write ≡ for syntactic identity of types. We write φ[a := b] for the usual capture-avoiding substitution action of b for a. Implication associates to the right; for example φ ⇒ψ ⇒ξ ≡φ ⇒ (ψ ⇒ξ).

Intuitively, types are first-order logic with the trivial term-language (a logic whose terms are just variable symbols).

Definition 2

Define the free atoms of φ as standard by:

fa(P(a, . . .))={a, . . .} fa(φ⇒ψ)=fa(φ)∪fa(ψ) fa(⊥)=∅ fa(∀a.φ) = fa(φ)\{a}
Definition 3

Let terms be: r, s, t, . . . ::= a | X | λa.r | r′r | xf(r).

Following [GL08] we identify terms up to α-equivalence of a in λa.r provided that r mentions no unknowns.6 We write ≡ for syntactic equivalence of terms.

For example λa.a ≡λb.b and λa.X ≢λb.X. 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.

Definition 4

A type assignment is a pair of the form a : φ, 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 : φ}. We use this convention later without comment. Intuitively, a : φ means ‘a has type φ’; a : ∗ means ‘a is a type variable’; X : φ means ‘X has type φ’.

Remark 5

We use the same syntactic class (atoms) 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 atoms that can have types (a : φ ∈Γ), and atoms that can appear in types (a : ∗∈Γ). However, we would duplicate the treatments of λ-abstraction, application, and freshness. Our approach keeps the machinery significantly shorter.

Definition 6

Call a pair a#r of an atom 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 7

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

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

Definition 8

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

− If X is a set of unknowns, write a#X for the freshness context {a#X | X ∈X}.

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

Definition 9

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.

Remark 10

We compare the rules in Figures 1 and 2:

− 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 an unknown X. We intend X to be instantiated to t which (because instantiation need not avoid capture) may mention a; see Definition 16. We remember a : φ in the typing context so that we can use it to build t, if we like.

We can mimic (⇒I) using (T⇒I) and (Tfr).

− (Tfr) is an explicit discharge rule. It connects b#r, which we can read as ‘b will discharged in the (possibly incomplete) derivation represented by r’ with actual discharge of b; after discharge, we cannot use b to construct any further derivations. As we just argued above, in the presence of unknowns it is convenient to separate these two notions.

− 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 unknowns and freshness assumptions on them.

− Compare (a#b), (a#b′), and (a#b′′). (a#b) and (a#b′′) are as in [UPG04]; distinct atoms 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 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:

(Tax)Γ ⊢a : A(Tax) Γ ⊢q : A ⇒B (Ty⇒E) Γ ⊢qa : B(Tax)Γ ⊢a : A(Tax) Γ ⊢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
(Tax)Γ, X : B ⊢X : B(Tax)Γ, X : B ⊢a : A(Tax) Γ, X : B ⊢p : A ⇒B ⇒C (T⇒E) Γ, X : B ⊢pa : B ⇒C (Ty⇒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.7

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)∀c.P(c) (∀c.P(c)) ⇒B (⇒E)B··· X ∀c.P(c) (∀c.P(c)) ⇒B (⇒E) B(2)

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

(Tax)Γ ⊢a:A(Tax) Γ ⊢p : ∀c.(A⇒P(c)) (T∀E) Γ ⊢pc : A⇒P(c) (T⇒E) Γ ⊢pca : P(c)(c∉fa(A), c∉fa(∀c.(A⇒P(c)))(T∀I)Γ ⊢λc.(pca) : ∀c.P(c)(Tax) Γ ⊢q : (∀c.P(c))⇒B (T⇒E)Γ ⊢q(λc.(pca)) : B(Tfr)a : A, p : ∀c.(A ⇒P(c)), q : (∀c.P(c)) ⇒B ⊢q(λc.(pca)) : B
(Tax)Γ, X : P(c) ⊢X : P(c)(c ∉fa(A) c ∉fa(∀c.(A⇒P(c))) c ∉fa((∀c.P(c))⇒B)))(T∀I)Γ, X : P(c) ⊢λc.X : ∀c.P(c)(Tax) Γ, X : P(c) ⊢q : (∀c.P(c))⇒B (T⇒E) Γ, X : P(c) ⊢q(λc.X) : B(Tfr)a : A, p : ∀c.(A ⇒P(c)), q : (∀c.P(c)) ⇒B, X : P(c) ⊢q(λc.X) : B

Derivations of freshnesses are elided.

2.3 Natural Deduction

We outline Natural Deduction and prove forms of soundness and completeness.

Definition 11

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 12

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

Definition 13

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

Theorem 14

Suppose Γ ⊢r is closed and suppose Γ ⊢r : φ is derivable. Then important(Γ ⊢r) ⊢φ (Definition 9) is derivable in Natural Deduction. (Proof in the Appendix.)

Theorem 15

If Φ ⊢φ is derivable in Natural Deduction then there exists some closed Γ ⊢r such that important(Γ ⊢r) ⊆Φ and Γ ⊢r : φ. (Proof in the Appendix.)

2.4 Admissible rules

Definition 16

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

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

Write unkn(Γ) for the unknowns mentioned in Γ. Figure 3 presents two kinds of weakening and a form of Cut.

Theorem 17

(WeakX) is admissible (if the sequents above the line are derivable, so are those below).

Proof

By a routine induction on derivations.

(Weaka) states that the atom is fresh for the incomplete parts in the derivation:

Theorem 18

(Weaka) is an admissible rule. (Proof in the Appendix.)

Lemma 19 states how instantiating unknowns is sound:

Lemma 19

Suppose that:

−Γ, X : ψ; ∆⊢r : φ and Γ; ∆⊢t : ψ.

−Γ; ∆′ ⊢a#t for every a#X ∈∆.

Then:

−Γ; ∆′ ⊢r[X := t] : φ.

−Γ, X : ψ; ∆⊢a#r implies Γ; ∆′ ⊢a#r[X := t], for every a.

(Proof in the Appendix.)

Cut in natural deduction is no more than ‘plugging the conclusion of one derivation into the assumption(s) of another’. However, now assumptions may be holes in incomplete derivations and we can ‘plug’ in a capturing manner. The rule (Cut) specifies that operation, and from Lemma 19 we have:

Theorem 20

(Cut) is an admissible rule.

3 Derivation-search (sketch)

If by ‘backwards’ reasoning we mean ‘reasoning from conclusion towards assumptions’ then the machinery so far is sufficient. To mix ‘forwards’ with ‘backwards’ reasoning we may need a little more; consider an incomplete derivation of A, ∀c.(A ⇒ P(c)), (∀c.P(c)) ⇒ B ⊢ B (cf. (2) in Subsection 2.2):

A∀c.(A ⇒P(c)) A ⇒P(c) P(c) ···(∀c.P(c)) ⇒B ···B(3)

Our syntax does not represent this as a single term-in-context because the ‘hole’ is not at the leaf of the derivation. We can represent this incomplete derivation as a set of sequents, all sharing the same typing and freshness context. Following theorem-provers and unification algorithms we present this as a set of goals, in rewriting style; the rewrites below can easily be converted into derivation trees:

Definition 21

Let Ξ range over finite sets of typings r : φ, a : ∗, and freshnesses a#r. We may call A ∈Ξ a goal and we may call Ξ a goal set.

A ∈Ξ has intuition ‘we know A’ — not ‘we want to prove A’ — but if A mentions an unknown X then what we know is incomplete and we would like to complete it, i.e. prove it. To derive φ from Γ; ∆ we start rewriting from X : φ, Γ, ∆ for X not appearing in Γ or ∆, and we try to instantiate X. We can declare success when we arrive at a goal state of the form Ξ, r : φ such that Γ; ∆⊢r : φ.

For example to prove B from A, ∀a.(A ⇒ P(a)), (∀a.P(a)) ⇒ B we can start with X : B, a : A, p : ∀a.(A ⇒ P(a)), q : (∀a.P(a)) ⇒ B and rewrite as follows (we may drop types to save space):

X : B, a : A, p : ∀c.(A ⇒P(c)), q : (∀c.P(c)) ⇒B(Weaka)−→ X : B, a, p, q, c : ∗(T∀E)−→ X : B, a, p, q, c, pc : A ⇒P(c)(T⇒E)−→ X : B, a, p, q, c, pc, pca : P(c)(T∀I)−→ X : B, a, p, q, c, pc, pca, λc.(pca) : ∀c.P(c)(T⇒E)−→ X : B, a, p, q, c, pc, pca, λc.(pca), q(λc.(pca)) : B(Cut)−→ q(λc.(pca)) : B, a, p, q, c, pc, pca, λc.(pca)

We read off q(λc.(pca)) as our result. (3) is represented by the third line above:

X : B, a, p, q, pc, pca : P(c).

The following series of rewrites generates the derivation in (1) from the Introduction, also discussed in Subsection 2.2 (→∗ is multiple rewrites):

X : A ⇒C, p : A ⇒B, q : A ⇒B ⇒C(Weaka)−→ X : A ⇒C, p, q, a : A, a#X(WeakX)−→ X : A ⇒C, p, q, a, a#X, X′ : C(T⇒I)−→ X : A ⇒C, p, q, a, a#X, X′, λa.X′ : A ⇒C(Cut)−→ λa.X′ : A ⇒C, p, q, a, X′(T⇒E)−→∗λa.X′ : A ⇒C, p, q, X′, pa : B, qa : B ⇒C, (pa)qa : C(Cut)−→ λa.((pa)qa) : A ⇒C, p, q, a, pa, qa, (pa)qa

4 Conclusions

We have seen how nominal terms, with a typing system, can model ‘incomplete derivations’ in first-order logic. We use a ‘one-and-a-halfth order’ syntax, building on ideas from nominal terms and one-and-a-halfth order logic: atoms model variable symbols and can be quantified (we use atoms to model both type and term variables); unknowns model ‘holes’ in the derivation. This directly reflects informal practice, in which holes in incomplete derivations are instantiated (substituted with capture).

We have tested our system on examples. We have shown the fragment without unknowns is sound and complete with respect to ‘normal’ derivations (Subsection 2.3). We have shown instantiating unknowns is sound, and explored what weakening means in the presence of the two levels of variable (Subsection 2.4).

This paper is part of a larger project which we expect to be a fruitful source of research. In roughly decreasing order of certainty, we envisage the following:

Curry-Howard supposes normalisation of derivations — this translates to an operational semantics for terms (Definition 3). This has to be more than ‘remove all β-reducts’ because, for example, the β-reduct in (λa.X)Y cannot be reduced. To address this, an investigation into two-and-a-halfth order λ-calculus is ongoing. 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-and-a-halfth order λ-calculus; we are reasonably confident this would extend to λX.

The rewrite system alluded to in Section 3 can be viewed as an independent system and studied. On that topic, we can ask whether the ideas in this paper can be useful for the theory or practice of writing theorem provers. Perhaps the representation itself will be useful, but nominal unification is known to be decidable [UPG04]; thus, nominal terms have some good computational properties which we may be able to exploit. Given the scale and complexity of modern theorem-provers, answers to such questions may take some time to emerge — but the situation is also far from hopeless, since in the first instance only the prover’s ‘kernel’ is involved.

Indeed, we can simplify the types to propositional logic (simple types; we drop the predicate part) and attempt to develop the rewrite system into a unification algorithm à la Huet [Hue02]. We can also try to enrich types in the direction of a dependent type theory and attempt to develop the typing rules from Figure 1 into a dependent type theory på samma Martin-Löf [NPS90]. This would be distinct from a dependent type theory with elements of nominal techniques [SS04], which treats atoms as variable symbols.

References

BKLN02. Roel Bloo, Fairouz Kamareddine, Twan Laan, and Rob Nederpelt. Parameters in pure type systems. In LATIN, pages 371–385. Springer, 2002.

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

Che05. James Cheney. Nominal logic and abstract syntax. SIGACT News (logic column 14), 36(4):47–69, 2005.

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.

FG06. Maribel Fernández and Murdoch J. Gabbay. Curry-style types for nominal rewriting. TYPES’06, 2006.

FG07. M. Fernández and M. J. Gabbay. Nominal rewriting. Information and Computation, 205:917–965, 2007.

GL08. Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. ENTCS, 196:19–35, 2008.

GM07. Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order logic. Journal of Logic and Computation, November 2007. Available online.

GP01. Murdoch J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.

Hue02. Gérard Huet. Higher order unification 30 years later. In TPHOL 2002, number 2410 in LNCS, pages 3–12, 2002.

Joj02. Gueorgui I. Jojgov. Holes with binding power. In TYPES, volume 2646 of LNCS, pages 162–181. Springer, 2002.

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.

MS06. Dale Miller and Alexis Saurin. A game semantics for proof search: preliminary results. In MFPS XXI, volume 155 of ENTCS, pages 543–563, 2006.

NPS90. B. Nordstrom, K. Petersson, and J. M. Smith. Programming in Martin-Lof’s Type Theory, volume 7 of Int’l Series of Monographs on Computer Science. Clarendon Press, Oxford, 1990. Also online.

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

Pit02. Andrew M. Pitts. Equivariant syntax and semantics. In ICALP, pages 32–36. Springer-Verlag, 2002.

PR05. David J. Pym and Eike Ritter. A games semantics for reductive logic and proof-search. In GALOP (Games for Logic and Programming Languages), pages 107–123, 2005.

SP94. Paula Severi and Erik Poll. Pure type systems with definitions. In LFCS, pages 316–328. Springer, 1994.

SP05. Mark R. Shinwell and Andrew M. Pitts. On a monadic semantics for freshness. Theoretical Computer Science, 342(1):28–55, 2005.

SS04. U. Schöpp and I. Stark. A Dependent Type Theory with Names and Binding. In CSL, volume 3210 of LNCS, pages 235–249, 2004.

UPG04. C. Urban, A. 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.

A Technical appendix

We will use the following fact without comment:

Lemma 22

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

Proof (of Theorem 14).

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

− The case of (Tax). Suppose Γ, a : φ ⊢a : φ. It is easy to calculate that important(Γ, a : φ ⊢a) = {φ}; then φ ⊢φ is a fact (see Footnote 8).

− The case of (T⇒I). Suppose Γ, a : φ ⊢λa.s : φ ⇒ψ and Γ, a : φ ⊢s : ψ. By inductive hypothesis important(Γ, a : φ ⊢s) ⊢ψ. We use (⇒I). If important(Γ, a : φ ⊢λa.s) = important(Γ, a : φ ⊢s) \ {φ} then we discharge φ. If important(Γ, a : φ ⊢λa.s) = important(Γ, a : φ ⊢s) then we discharge φ zero times. There are no other possibilities.

− The case of (T⇒E). Suppose Γ ⊢r′r : ψ and Γ ⊢r′: φ ⇒ψ and Γ ⊢r : φ. By inductive hypothesis important(Γ ⊢r′) ⊢φ ⇒ψ and important(Γ ⊢r) ⊢φ. By Lemma 12 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 of (T∀I). Suppose Γ, a : ∗⊢λa.r : ∀a.φ, where

Γ, a : ∗⊢r : φ and a ∉fa(important(Γ, a : ∗⊢r)).

By inductive hypothesis important(Γ, a : ∗⊢r) ⊢φ. By (∀I),

important(Γ, a : ∗⊢r) ⊢∀a.φ.

− The case of (T∀E). Suppose Γ, b : ∗⊢rb : φ[a := b] and Γ, b : ∗⊢r : ∀a.φ. By inductive hypothesis important(Γ, b : ∗⊢r) ⊢∀a.φ. By (∀E),

important(Γ, b : ∗⊢r) ⊢φ[a := b].

By reasoning similar to the case of (T⇒E) we can calculate that

important(Γ, b : ∗⊢rb) = important(Γ, b : ∗⊢r) ∪important(Γ, b : ∗⊢b : ∗).

Now it is a fact that important(Γ, b : ∗⊢b : ∗) = ∅. The result follows.

− The case of (Tfr). Suppose Γ ⊢r : φ, and

Γ, A ⊢r : φ and Γ, A ⊢b#r where A ∈{b : φ, b : ∗}.

By inductive hypothesis important(Γ, A ⊢r) ⊢φ. If A = b : ∗ then

important(Γ, A ⊢r) = important(Γ ⊢r)

and the result follows immediately. If A = b : ψ then since Γ, A ⊢b#r again

important(Γ, A ⊢r) = important(Γ ⊢r).

The result follows.

By abuse of appendices, we place the proof of Theorem 18 before that of Theorem 15. There is no circularity in the proofs and it is convenient for brevity; the special case of Theorem 18 when Γ mentions no unknowns, is needed to prove Theorem 15.

Proof (of Theorem 18).

By induction on derivations. Only the case of (T∀I) is of interest.

− Suppose Γ, a : ∗; ∆⊢r : φ and a ∉ fa(important(Γ, a : ∗; ∆⊢r)). By inductive hypothesis Γ, a : ∗, B; ∆, b#X ⊢r : φ where X = unkn(Γ) and b ∉Γ, a : ∗. It is not hard to calculate that Γ, a : ∗, B; ∆, b#X ⊢b#r and so

a ∉fa(important(Γ, a : ∗, B; ∆, b#X ⊢r)).

The result follows.

Proof (of Theorem 15).

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 atom 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 case (⇒I). Suppose Φ ⊢φ ⇒ψ and Φ, φ ⊢ψ.

By inductive hypothesis there exists Γ ⊢r such that important(Γ ⊢r) ⊆Φ ∪{φ} and Γ ⊢r : ψ. If a : φ ∈Γ for some a then let Γ ′ = Γ. If a : φ ∈Γ for no a then let Γ ′ = Γ, a : φ for some a not appearing in Γ. By Theorem 18 (see the comment preceding this proof) Γ ′ ⊢r : φ. It is also a fact that important(Γ ⊢r) = important(Γ ′ ⊢r). By (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 Φ ⊢φ ⇒ψ and Φ ⊢φ. By inductive hypothesis there exist:

• Γ ′ ⊢r′ such that important(Γ ′ ⊢r′) ⊆Φ and Γ ′ ⊢r′: φ ⇒ψ.

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

Without loss of generality we may assume that Γ ∪Γ ′ satisfies our uniqueness condition; we rename atoms to make this true if necessary. We use (T⇒E) and the fact that important(Γ ∪Γ ′ ⊢r′r) ⊆Φ.

− 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 : ξ ∈Γ for some type ξ then we are in the pathological situation that a ∉ fa(φ) and a : ξ ∈Γ ‘by mistake’; we rename a. If a : ∗∉Γ then let Γ ′ = Γ, a : ∗. By Theorem 18 Γ ′ ⊢r : φ. It is also a fact that important(Γ ⊢r) = important(Γ ′ ⊢r). We use (T∀I) and the fact that important(Γ ′ ⊢r) = important(Γ ′ ⊢λa.r).

− The case (∀E). Suppose Φ ⊢φ[a := b] and Φ ⊢∀a.φ. By inductive hypothesis there are Γ and r such that important(Γ ⊢r) ⊆Φ and Γ ⊢r : ∀a.φ. If b : ∗∈Γ then let Γ ′ = Γ. If b : ∗∉Γ then let Γ ′ = Γ, b : ∗. By Theorem 18 Γ ′ ⊢r : ∀a.φ. It is also a fact that important(Γ ⊢r) = important(Γ ′ ⊢r).

We use (T∀E) and the fact that

important(Γ ′ ⊢r) = important(Γ ′ ⊢rb).
Lemma 23

Suppose that:

−Γ, X : ψ; ∆⊢r : φ and Γ; ∆⊢t : ψ.

−Γ; ∆′ ⊢a#t for every a#X ∈∆.

Then important(Γ; ∆′ ⊢r[X := t]) ⊆ important(Γ, X : ψ; ∆⊢r).

Proof

By a routine induction on r. We consider cases:

− The case of a. Easy.

− The case of X. We calculate:

important(Γ, X : ψ; ∆⊢X) = {φ | a : φ ∈Γ, a#X ∉∆}

By assumption important(Γ; ∆′ ⊢t) ⊆{φ | a : φ ∈Γ, a#X ∉∆}.

Other cases are easier.

Proof (of Lemma 19).

By induction on the derivation of Γ, X : ψ; ∆⊢r : φ. The first part is routine, we consider only two cases:

− The case (a#b′). Suppose Γ, a : ∗, b : φ′, X : ψ; ∆⊢a#b is derived by (a#b′).

Then a ∉ fa(φ′) and it follows that

Γ, a : ∗, b : φ′; ∆′ ⊢a#b.

Since b[X := t] ≡b, we are done.

− The case (a#λb). Suppose Γ, X : ψ; ∆⊢a#r and Γ, X : ψ; ∆⊢a#λb.r is derived by (a#λb). By inductive hypothesis Γ; ∆′ ⊢a#r[X := t] and so

Γ; ∆⊢a#λb.(r[X := t]).

Since λb.(r[X := t]) ≡ (λb.r)[X := t], we are done.

For the second part we consider some cases:

− The case (Tax). Suppose Y : ξ ∈Γ and Γ, X : ψ; ∆⊢Y : ξ is derived by (Tax). Then Γ; ∆′ ⊢Y : ξ. Since Y ≡Y[X := t], we are done. Similarly for Γ, X : ψ; ∆⊢a : ξ.

Suppose Γ, X : ψ; ∆⊢X : ψ is derived by (Tax). By assumption Γ; ∆′ ⊢t : ψ. Since t ≡X[X := t], we are done.

− The case (T⇒I). Since (λa.r)[X := t] ≡λa.(r[X := t]). The cases of (T⇒E) and (T∀E) are similar.

− The case (T∀I). Since (λa.r)[X := t] ≡λa.(r[X := t]) and from Lemma 23.

− The case (Tfr). Suppose Γ, A, X:ψ; ∆⊢r : φ because Γ, A, X:ψ; ∆, b#X ⊢r : φ and suppose Γ, A, X:ψ; ∆, b#X ⊢b#r, where b ∉∆ and A is b : ∗ or b : ξ for some ξ. By inductive hypothesis and some calculations, Γ, A; ∆′, b#X ′ ⊢r[X := t] : φ and Γ, A; ∆′, b#X ′ ⊢b#r[X := t], for a suitable X ′ and ∆′ where b ∉∆′. The result follows.

(A ∈{a : φ, a : ∗, X : φ})(Tax)Γ, A; ∆⊢AΓ; ∆⊢r : ⊥(T⊥E)Γ; ∆⊢xf(r) : φΓ, a : φ; ∆⊢r : ψ(T⇒I)Γ, a : φ; ∆⊢λa.r : φ ⇒ψΓ; ∆⊢r′ : φ ⇒ψ Γ; ∆⊢r : φ(T⇒E)Γ; ∆⊢r′r : ψΓ, a : ∗; ∆⊢r : φ a ∉fa(important(Γ, a : ∗; ∆⊢r))(T∀I)Γ, a : ∗; ∆⊢λa.r : ∀a.φ Γ, b : ∗; ∆⊢r : ∀a.φ(T∀E)Γ, b : ∗; ∆⊢rb : φ[a := b]Γ, A; ∆, b#X ⊢r : φ Γ, A; ∆, b#X ⊢b#r (A ∈{b : ψ, b : ∗}, b ∉∆)(Tfr)Γ; ∆⊢r : φ (a#b)Γ, a : φ, b : φ; ∆⊢a#b(a#b′′)Γ, a : ∗, b : ∗; ∆⊢a#b(a#λa)Γ; ∆⊢a#λa.rΓ; ∆⊢a#r(a#λb)Γ; ∆⊢a#λb.r(a#X)Γ; ∆, a#X ⊢a#X(a ∉fa(φ))(a#b′)Γ, a : ∗, b : φ; ∆⊢a#bΓ; ∆⊢a#r′Γ; ∆⊢a#r(a#app)Γ; ∆⊢a#r′rΓ; ∆⊢a#r(a#xf)Γ; ∆⊢a#xf(r)
Fig. 1. Typing and freshness derivation rules
⊥(⊥E)φ[φ] ··· ψ(⇒I)φ ⇒ψφ ⇒ψ φ(⇒E)ψΦ··· φ (a ∉fa(Φ))(∀I)∀a.φ∀a.φ(∀E)φ[a := b]
Fig. 2. Natural Deduction style derivation rules
Γ; ∆⊢r : φ (X ∉Γ)(WeakX)Γ, X : ψ; ∆⊢r : φΓ; ∆⊢r : φ (B ∈{b : ψ, b : ∗}, a ∉Γ)(Weaka)Γ, B; ∆, b#unkn(Γ) ⊢r : φΓ, X:ψ; ∆, a1#X, . . . , an#X ⊢r : φ Γ; ∆⊢t:ψ Γ; ∆⊢ai#t (1≤i≤n) (X∉∆)(Cut)Γ; ∆⊢r[X := t] : φ
Fig. 3. Admissible rules

Notes

3 We are grateful to Jojgov for the examples in his paper [Joj02]. We thank Iman Poernomo and two anonymous referees for helpful comments. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid. ↩

4 In one-and-a-halfth order logic, unknowns populate predicates, and model predicate meta-variables in derivation schemas. Here, unknowns are used differently, to model holes in terms representing derivations. The common ‘one-and-a-halfth order’ idea — also present, implicitly, in Curry-style types for nominal terms [FG06] — is that atoms can be variables. This is different from [UPG04] where atoms populate a sort of atoms and are variable symbols. ↩

5 When we write ‘x’ and ‘y’ we intend them to be distinct symbols; for example ‘λx.y’ is always taken to be different from ‘λx.x’; likewise ‘x = y’ is different syntax than ‘x = x’. This is distinct from the denotation of x being equal to that of y. ↩

6 This allows us to rename bound atoms in ‘normal’ syntax — the part without unknowns — but it stops short of a nominal terms style α-equivalence with unknowns based on permutations. For our purposes in this paper, what we give ourselves is enough. See the Conclusions. ↩

7 The (Tfr) in the second derivation is ill-advised, in the sense that intuitively we cannot then instantiate X to qa; we might prefer to conclude the derivation with (T⇒I). We leave this kind of choice to a derivation search algorithm, or we might favour a ‘safe’ variant of (Tfr) which insists r be closed (that r mention no unknowns). ↩

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

9 Here x ranges over all atoms, not necessarily permutatively, so perhaps x = a. ↩