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

WFLP 2008

Term sequent logic

Michael Gabbay1

http://www.kcl.ac.uk/kis/schools/hums/philosophy/staff/m_gabbay.html

Murdoch J. Gabbay

http://www.gabbay.org.uk

Abstract

We consider a term sequent logic for the lambda-calculus. Term sequents are a judgement form similar to the logical judgement form of entailment between sentences, but denoting equality or reducibility between terms. Using term sequents, it is possible to treat lambda-terms almost like logical sentences, and to use proof-theoretic methods to establish their properties. We prove a cut-elimination result for untyped lambda-calculus and describe how this generalises the usual confluence result. We give a notion of uniform proof for lambda-terms, and suggest how this can be viewed as a mixed logic-programming/functional programming framework with the ability to assume arbitrary reductions. Finally, we discuss related and future work.

Keywords: Cut Elimination, Lambda Calculus, Functional programming, Proof Theory

1 Introduction

Sequent calculi are a general framework for formalising logical consequence relations and proving their properties. Cut-elimination is key to proving properties such as consistency, non-triviality (a model exists with more than one element), non-derivability, completeness for derivation-search algorithms, decidability results for fragments, and so on. However, these properties do not follow in the presence of axioms. For example cut-elimination does not directly imply the consistency of an equality axiom like (λx.x)·y ≈y.

Term sequents generalise sequent calculus; the intuition is ‘sequents for terms, as well as sentences’. Logical consequence becomes a relation not just between sentences, but also between terms. An advantage of doing this is that a term sequent calculus represents, without axioms, logics with non-trivial equalities between terms — logics that would require axioms if formulated using the ‘ordinary’ sequent calculus, thus precluding an obvious proof-theoretic treatment of their properties.

Γ ⊢x :−x(Ax:−)Γ ⊢Θ :−s Γ ⊢⟨. . . s . . .⟩:−t Γ ⊢⟨. . . Θ . . .⟩:−t(Cutλ)Γ ⊢⟨. . . ⟨t1, t2⟩. . .⟩:−t Γ ⊢⟨. . . t1·t2 . . .⟩:−t(·L)Γ ⊢Θ1 :−t1Γ ⊢Θ2 :−t2Γ ⊢⟨Θ1, Θ2⟩:−t1·t2(·R)Γ ⊢Θ :−t1Γ ⊢⟨. . . t2 . . .⟩:−t Γ, t1⇝t2 ⊢⟨. . . Θ . . .⟩:−t(⇝L) Γ ⊢t1 :−t2Γ ⊢t1⇝t2, ∆(⇝R)Γ ⊢Θ :−t1Γ ⊢⟨. . . t2[x/t1] . . .⟩:−t Γ ⊢⟨. . . ⟨λx.t2, Θ⟩. . .⟩:−t(λL)Γ ⊢⟨Θ, x⟩:−t Γ ⊢Θ :−λx.t(λR)x not free in Θ or Γ
Fig. 1. Term sequent rules: λ-calculus
Γ, Ai ⊢∆ Γ, A1 ∧A2 ⊢∆(∧L)1 ≤i ≤2Γ ⊢A1, ∆ Γ ⊢A2, ∆ Γ ⊢A1 ∧A2, ∆(∧R)Γ ⊢C, ∆ Γ, C ⊢∆ Γ ⊢∆(Cut)Γ, A[x/t] ⊢∆ Γ, ∀x.A ⊢∆(∀L)Γ ⊢A, ∆ Γ ⊢∀x.A, ∆(∀R)x not free in Γ, ∆Γ, A ⊢∆ Γ ⊢¬A, ∆(¬R)Γ ⊢A, ∆ Γ, ¬A ⊢∆(¬L)Γ ⊢A, ∆ Γ, B ⊢∆ Γ, A ⇒B ⊢∆(⇒L)Γ, A ⊢B, ∆ Γ ⊢A ⇒B, ∆(⇒R)
Fig. 2. Sentence sequent rules

As a result, the basic technique of cut-elimination is extended to algebraic systems (those satisfying non-trivial equalities between terms).

The specific objective of this paper is to develop a term-sequent style logic and proof-theory of the (untyped) λ-calculus. We shall prove full cut-elimination and also exhibit a well-behaved notion of uniform proof. This reconciles, in a novel way, first-order logic with the λ-calculus, and the computational content of first-order logic with the computational content of the λ-calculus.

The idea of logics with term sequents is itself novel to this paper. We have applied it to the λ-calculus, but first author has developed term sequent systems for other systems, for example arithmetic and rational numbers. Further comment is in the Conclusions.

2 Syntax of the λ-calculus

Definition 2.1

− Define terms t and sentences A by:

t ::= x, y, z, . . . | (t1·t2) | (λx.t) A ::= t1⇝t2 | A1 ∧A2 | A1 ⇒A2 | ¬A | ∀x.A

− Free variables of t and A are defined as usual; for example x is free in x⇝y and in x·x, and x is not free in ∀x.A and λx.(x·x).

− Also as usual, we take predicates and terms up to α-conversion of bound variables. We use ≡ to express identity of syntax up to α-conversion.

(D1)⊢t[x/y] :−t[x/y]Thrm. 3.1⊢⟨λx.t, y⟩:−t[x/y](λL)⊢λx.t :−λy.(t[x/y])(λR)⊢λx.t⇝λy.(t[x/y])(⇝R)(D2)⊢t[x/y][y/x] :−tThrm. 3.1⊢⟨λy.(t[x/y]), x⟩:−t(λL)⊢λy.(t[x/y]) :−λx.t(λR)⊢λy.(t[x/y])⇝λx.t(⇝R)(D3)⊢t[x/t′] :−t[x/t′]Thrm. 3.1⊢⟨λx.t, t′⟩:−t[x/t′](λL)⊢(λx.t)·t′ :−t[x/t′](·L)⊢(λx.t)·t′⇝t[x/t′](⇝R)(D4)⊢t :−tThrm. 3.1⊢x :−x(Ax:−)⊢⟨t, x⟩:−t·x(·L)⊢t :−λx.(t·x)(λR)⊢t⇝λx.(t·x)(⇝R)
Fig. 3. Derivations of αβη-reduction
Definition 2.2

− Define trees by: Θ ::= t | ⟨Θ1, Θ2⟩.

− If Θ′ is a subtree of Θ then we write Θ as ⟨. . . Θ′. . .⟩.

Definition 2.3

A term sequent is a tuple Γ ⊢ Θ :− t where Θ is a tree and t is a term. A sentence sequent is a pair Γ ⊢ ∆. The derivable sequents of a term sequent logic are inductively defined by the rules in Figures 1 and 2.

For some example derivations, see Figure 3.

Remark 2.4

As a piece of design of a logic, issues lie in the choice of structure for a term sequent Γ ⊢ Θ :− t, and of term sequent derivation rules. The challenge is to find a term sequent structure and rules such that terms and their term-formers can be decomposed in a syntax-directed manner.

This design issue is familiar from other sequent systems: for example bunched implications [12] requires a logical context with ‘bunches’; intuitionistic logic typically has a single sentence on the right whereas classical logic has many sentences; and so on.

Remark 2.5

An intuition for the rules of Figure 1 is perhaps best obtained by examining how they contribute to Theorem 3.6, which makes a correspondence between derivability in our term sequent logic, and αβη-reductions in familiar formulations of the λ-calculus; it is a kind of soundness and completeness result.

In a term sequent Γ ⊢ Θ :− t, we may see Γ as a set of assumptions, t as a λ-term and Θ as a rough normal form of a λ-term that reduces to t. Intuitively, (λL) corresponds to β-reduction; (λR) corresponds to η-expansion; (·L) fixes · as a symbol for application and (·R) corresponds to a form of congruence.

Remark 2.6

A special case of (λL) is Γ ⊢t1 :−t1Γ ⊢⟨. . . t2[x/t1] . . .⟩:−t Γ ⊢⟨. . . ⟨λx.t2, t1⟩. . .⟩:−t. We can write this as Γ ⊢⟨. . . t2[x/t1] . . .⟩:−t Γ ⊢⟨. . . ⟨λx.t2, t1⟩. . .⟩:−t in the light of Theorem 3.1.

Similarly, a special case of (⇝L) may be written

Γ ⊢⟨. . . t2 . . .⟩:−t Γ, t1⇝t2 ⊢⟨. . . t1 . . .⟩:−t.

These special cases are insufficient for term sequent logic; they fail to yield cut-elimination in the same way that this special case of (⇒L) Γ, B ⊢∆ Γ, A ⇒B, A ⊢∆ fails to yield cut-elimination in propositional logic. For example (A1 ∧ A2) ⇒ B, A1, A2 ⊢ C is not derivable without (Cut) if only the special case of (⇒L) is used. Similarly, ⊢⟨λy.y, ⟨s, t⟩⟩ :− s·t requires (Cutλ) if we use only the special case of (λL).

We read Θ = ⟨Θ1, Θ2⟩ as ‘Θ1 applied to Θ2’. We read Γ ⊢ Θ :− t as: “Γ implies that the term corresponding to Θ is equal/reduces to t.” So we read Γ ⊢⟨λx.(y·x), z⟩ :−λy.z as “Γ implies that λx.(y·x) applied to z reduces to λy.z”.

Remark 2.7

Our notation uses three different sorts of bracket, but we promise that this is harmless.

• Square brackets [ ] express capture avoiding substitution on terms, this is standard.

• Round brackets ( ) parse terms, as is standard.

• Angle brackets ⟨⟩ parse trees (Definition 2.2), which are part of our term-sequent form.

Because term sequent derivation rules break apart terms, it can happen that round brackets ‘become’ angle brackets (e.g. the last three lines of derivation D3 of Figure 3). This has essentially the same status as conjunctions ‘becoming’ commas in traditional sequent systems.

Remark 2.8

Manipulation of term sequents and sentence sequents are kept separate. Only (⇝R) moves between them. The two cut rules (Cutλ) and (Cut) apply either to terms in term sequents, or to sentences in sentence sequents. For example we cannot use our cut rules to make an inference like

A ∧t1⇝t2 ⊢t1⇝t2t1⇝t2 ⊢t1 :−t2A ∧t1⇝t2 ⊢t1 :−t2

This separation is necessary and slightly restricts deductive power, for example we cannot derive that A ∧ t1⇝t2 ⊢ t1:− t2, but it simplifies matters.

Remark 2.9

A notion similar to ⇝ has been investigated under the name aequality, using the same symbol, and representing a directed equality in a first-order logic [4]. The intuition of ⇝ here is similar — ‘directed equality’ is much the same thing as ‘reduction’. Further intuition for ⇝ is provided by in Theorem 3.6.

3 Derivability

Theorem 3.1

− Γ ⊢ t :− t is derivable, without using (Cutλ), for any t.

− Γ, A ⊢ A, ∆ is always derivable.

Proof

The first part is by induction on t. For example, if t ≡λx.s then by induction hypothesis Γ ⊢ s :− s, and so:

Π Γ ⊢s :−s Γ ⊢⟨λx.s, x⟩:−s(λL)Γ ⊢λ.xs :−λx.s(λR)

The second part follows by (⇝L), (⇝R) and induction on A. 2

Theorem 3.2
x⇝y, y⇝z ⊢x⇝z λx.t :−λy.(t[x/y]) (if y is not free in t)⊢x⇝x λy.(t[x/y]) :−λx.t (if y is not free in t)⊬x :−y (λx.t)·t′ :−t[x/t′]⊬x⇝y t :−λx.(t·x) (if x is not free in t)
Proof

Some derivations can be found within Figures 3 and 4. For D1 and D2 assume y is not free in t, for D4 assume x is not free in t.

⊬ x :− y and ⊬ x⇝y follows from the syntax directedness of the derivation sequent rules. 2 2

We now prove a theorem relating the term sequent treatment of λ-calculus to familiar treatments of the λ-calculus in terms of αβη-conversion. First we need to associate a λ-term to every tree.

Definition 3.3

If Θ is a tree then trm(Θ) is a term defined inductively by trm(t)≡t and trm(⟨Θ1, Θ2⟩) ≡ trm(Θ1)·trm(Θ2).

Lemma 3.4

Γ ⊢ Θ :− trm(Θ)

Proof

The proof is by an easy induction on Θ. 2

Definition 3.5

If t1 and t2 are λ-terms then let t1 ↠αβη t2 mean that t1 can be rewritten to t2 by means of α-conversion, β-reduction and η-expansion.

Theorem 3.6

⊢ Θ :− t if and only if trm(Θ) ↠αβη t.

Proof

The ‘if’ direction follows by Theorem 3.2 (right column), (Cutλ) and Lemma 3.4.

The ‘only if’ direction follows by induction on derivations. For example, suppose the derivation ends with (λR): Π Γ ⊢⟨Θ, x⟩:−t Γ ⊢Θ :−λx.t(λR). Then by the induction hypothesis on Π and Definition 3.3 trm(Θ)·x ↠αβη t, but then by congruence λx.(trm(Θ)·x) ↠αβη λx.t. Thus by η-expansion (and the transitivity of ↠αβη) we have that trm(Θ)↠αβη λx.t. 2

In Figure 4 we present some complex derivations. We do not necessarily decompose λ-terms to normal forms (the λ-calculus is untyped; there may not be a normal form). Derivation D5 exemplifies how term sequents can handle a λ-terms that does not reduce to a normal form. Derivation D8 exemplifies that term sequents are no rewrite system for the λ-calculus in disguise; we derive that a reduction holds if y is reducible to z. As discussed in the Introduction, a rewrite system cannot hypothesise rewrites.

4 Interreducivity and intersubstitutivity

Definition 4.1

Write t ↭ t′ for t⇝t′ ∧ t′⇝t.

(D5).... Theorem 3.1⊢y·ˆ λx.`y·(x·x)´·λx.` y·(x·x)´˜:−y·ˆ λx.` y·(x·x)´ ·λx.` y·(x·x)´˜⊢⟨λx.`y·(x·x)´, λx.` y·(x·x)´ ⟩:−y·ˆ λx.` y·(x·x)´ ·λx.`y·(x·x)´˜(λL)(D6)⊢y :−y(Ax:−)x⇝y ⊢x :−y(⇝L)x⇝y, y⇝z ⊢x :−z(⇝L)x⇝y, y⇝z ⊢x⇝z(⇝R)(D7)⊢z :−z(Ax:−)⊢⟨λx.x, z⟩:−z(λL)y⇝λx.x ⊢⟨y, z⟩:−z(⇝L)y⇝λx.x ⊢y·z :−z(·R)y⇝λx.x ⊢(y·z)⇝z(⇝R)(D8)y⇝z ⊢y :−y(Ax:−)⊢y :−y(Ax:−)⊢z :−z(Ax:−)⊢y :−y(Ax:−)⊢⟨z, y⟩:−z·y(·R)y⇝z ⊢⟨y, y⟩:−z·y(⇝L)y⇝z ⊢y·y :−z·y(·L)y⇝z ⊢⟨λx.(x·x), y⟩:−z·y(λL)y⇝z ⊢λx.(x·x)·y :−z·y(·L)
Fig. 4. Example derivations in term sequent λ-calculus

In the light of Definition 4.1 and the rules in Figure 1 we might look at Theorem 3.6 and jump to the conclusion that ↭ is just α-equivalence — but this conclusion is false. In Γ ⊢ Θ :− t and Γ ⊢ ∆we can assume reductions in Γ; so ↭ holds or fails to hold in the context of some assumptions, which can assert reductions that are not α-equivalences.

We will show that Γ ⊢A[x/t], ∆ Γ, t ↭t′ ⊢A[x/t′], ∆ is admissible (Theorem 4.3).

Lemma 4.2

− Γ⊢t2:−t1 and Γ⊢⟨. . . s[x/t1] . . .⟩:−s′ imply Γ⊢⟨. . . s[x/t2] . . .⟩:−s′.

− Γ ⊢ t1:− t2 and Γ ⊢ Θ :− s[x/t1] imply Γ ⊢ Θ :− s[x/t2].

Proof

The first part is by induction on the derivation of Γ ⊢⟨. . . s[x/t1] . . .⟩ :− s′. There are a number of cases for the final rule of the derivation. We consider some of them here:

• The case (Ax:−). Then s ≡ x or, for some y ≢ x, s ≡ y. In the the first case the result follows from the assumption that Γ ⊢ t2 :− t1 and (Cutλ), otherwise s[x/t1] ≡ y[x/t1] ≡ y[x/t2] ≡ s.

We may now assume that s is not atomic. For otherwise, regardless of the final rule application, s ≡ x or s ≡ y for some y ≢ x and the result follows as above.

• The cases where last rule applies to some term other than s[x/t1]. Then the result follows easily by the induction hypothesis on the shorter derivation of the premise.

• The cases where the last rule applies to s[x/t1]. Then the result follows again by the induction hypothesis. For example suppose s ≡λy.r and is derived by (λL):

Π1Γ ⊢Θ :−r′Π2Γ ⊢⟨. . . r[x/t1][y/r′] . . .⟩:−t Γ ⊢⟨. . . ⟨λy.r[x/t1], Θ⟩. . .⟩:−t(λL)

We may suppose that x is not free in r′ and y is not free in t1 and so r[x/t1][y/r′] ≡ r[y/r′][x/t1]. Thus Γ ⊢⟨. . . r[y/r′][x/t1] . . .⟩ :− t is the conclusion of Π2. So there is a derivation Π′ 2 of Γ ⊢⟨. . . r[y/r′][x/t2] . . .⟩ :− t by induction hypothesis. So we have that:

Π1Γ ⊢Θ :−r′Π′ 2Γ ⊢⟨. . . r[y/r′][x/t2] . . .⟩:−t Γ ⊢⟨. . . ⟨λy.r[x/t2], Θ⟩. . .⟩:−t(λL)

since r[y/r′][x/t1] ≡ r[x/t1][y/r′]. The remaining possibilities involve little more complexity.

The second part is proved similarly to the first part, by induction on the derivation of Γ ⊢ Θ :− s[x/t1].

• The base case, as with the first part, is when Γ ⊢ Θ :− s[x/t1] is derived by (Ax:−) or when s is atomic. In each subcase the result follows easily by (Cutλ).

For example, if s ≢x then we have: Γ ⊢Θ :−s[x/t1] Γ ⊢t1 :−t2Γ ⊢Θ :−t2(Cutλ).

• The remaining cases are uncomplicated.2

Theorem 4.3

− Γ⊢t1:−t2, Γ⊢t2:−t1 and Γ ⊢ A[x/t1], ∆ imply Γ ⊢ A[x/t2], ∆.

− Γ ⊢ A[x/t1], ∆ implies Γ, t1 ↭ t2 ⊢ A[x/t2], ∆.

Proof

The first part follows by induction on the derivation of Γ ⊢ A[x/t1], ∆. The base case is where A = s1⇝s2 and the derivation ends with (⇝R) applied to the premise Γ ⊢ t1[x/t1] :− t2[x/t1]. The result then follows by Lemma 4.2. The inductive cases are straightforward.

The second part follows from the first part, (Cutλ) and from the fact that Γ, t1⇝t2, t2⇝t1 ⊢ t1:− t2 and Γ, t1⇝t2, t2⇝t1 ⊢ t2:− t1. 2

So t1 ↭ t2 functions like a substitutional equality on sentences. See Section 7 for a (weaker) notion of equality corresponding with αβη-equality in a suitable formal sense.

5 Cut elimination

Cut elimination is proved in two stages: eliminate the term sequent rule (Cutλ), then eliminate the sentence sequent rule (Cut).

Eliminating (Cutλ) is somewhat simplified compared to the propositional case, because term sequents lack structural rules like contraction and weakening. First, some definitions.

5.1 Height and grade of term sequents

Definition 5.1

Define the height of a term sequent in a derivation by:

− A term sequent of the form Γ ⊢ t :− t has height 0.

− The height of any other term sequent (in a derivation) is the sum of the heights of its premises plus 1.

Call the height of a derivation the height of its final sequent.

The height of a term sequent, therefore, is the size of the derivation tree extending back as far as the last instances of Γ ⊢ t :− t. We can define something equivalent for sentence sequents.

Definition 5.2

The grade of a term is the number of occurrences in it of the symbols · and λ. For example, (λx.(λy.x·y))·z has grade 4.

Definition 5.3

For an instance of (Cutλ) Γ ⊢Θ :−s Γ ⊢⟨. . . s . . .⟩:−t Γ ⊢⟨. . . Θ . . .⟩:−t call s the cut term, call the grade of the instance the grade of the cut sentence. Call the height of the instance the height of its conclusion.

5.2 Rank and degree of sentence sequents

Definition 5.4

Define the rank of a sentence sequent in a derivation by:

− The conclusion of (T⊥) or (⇝R) has rank 0.

− The rank of any other term sequent (in a derivation) is the sum of the ranks of its premises plus 1.

The rank of a derivation is the rank of its conclusion.

Definition 5.5

The degree of a sentence is the number of occurrences in it of the symbols ∧, ¬, ∀. For example, ∀x.¬∀y.∃z.(x⇝y ∧ x⇝z) has degree 5.

Definition 5.6

For an instance of (Cut) Γ ⊢C, ∆ Γ, C ⊢∆ Γ ⊢∆ call C the cut sentence, call the degree of the instance the degree of the cut sentence. Call the rank of the instance the rank of its conclusion.

5.3 Cutλ-elimination

We must first prove a lemma on the uniform substitution of variables for terms.

Lemma 5.7

− Γ⊢Θ:−t implies Γ[x/t′]⊢Θ[x/t′]:−t[x/t′] with no greater height.

− If Γ ⊢∆ then Γ[x/t] ⊢∆[x/t], ∆′[x/t] with the same rank.

Proof

Both parts follow by induction on the derivation. 2

Lemma 5.8

If Γ ⊢ Θ :− t then Γ, A ⊢ Θ :− t with no more instances of (Cutλ).

Proof

By a simple induction on the derivation. 2

Theorem 5.9

− If Γ ⊢ Θ :− t is derivable using exactly one instance of (Cutλ) then it is derivable, with no greater height, using none.

− If Γ ⊢ Θ :− t is derivable then it is derivable without (Cutλ).

Proof

− The first part is proved by induction on the pair (g, h), lexicographically ordered, where g is the height and h is the grade of the (Cutλ). As with familiar cut elimination theorems, we permute cuts and eliminate essential cases. The essential cases and examples of permutation rules are given in Figures 5 and 6, the base case is given by Lemma 3.1.

In all cases we replace an instance of (Cutλ) with a number of new instances with lesser heights or degrees, these may be eliminated by the induction hypothesis. The result as a whole is made easier by the fact the the derivation system contains no ‘exponential’ structural rules such as weakening or contraction (exponential with regard to their effect on derivation complexity).

− The second part follows from the first by induction on the structure of the derivation.

2

Γ ⊢t1 :−t1(Ax:−)Π Γ ⊢⟨. . . t1 . . .⟩:−t2Γ ⊢⟨. . . t1 . . .⟩:−t2(Cutλ)↦−→Π Γ ⊢⟨. . . t1 . . .⟩:−t2Π Γ ⊢⟨. . . Θ . . .⟩:−t Γ ⊢t :−t(Ax:−)Γ ⊢⟨. . . Θ . . .⟩:−t(Cutλ)↦−→Π Γ ⊢⟨. . . Θ . . .⟩:−tΠ1Γ ⊢⟨Θ1, x⟩:−t1Γ ⊢Θ1 :−λx.t1(λR)Π2Γ ⊢Θ2 :−t2Π3Γ ⊢⟨. . . t1[x/t] . . .⟩:−t2Γ ⊢⟨. . . ⟨λx.t1, Θ2⟩. . .⟩:−t(λL)Γ ⊢⟨. . . ⟨Θ1, Θ2⟩. . .⟩:−t2(Cutλ)↦−→Π2Γ ⊢Θ2 :−t2Π1[x/t] Γ ⊢⟨Θ1, t⟩:−t1[x/t]Π3Γ ⊢⟨. . . t1[x/t] . . .⟩:−t2Γ ⊢⟨. . . ⟨Θ1, t⟩. . .⟩:−t(Cutλ)Γ ⊢⟨. . . ⟨Θ1, Θ2⟩. . .⟩:−t2(Cutλ)where Π1[x/t] results from Π1 by replacing x uniformly in it by t (see Lemma 5.7). Π1Γ ⊢Θ1 :−t1Π2Γ ⊢Θ2 :−t2Γ ⊢⟨Θ1, Θ2⟩:−t1·t2(·R)Π3Γ ⊢⟨. . . ⟨t1, t2⟩. . .⟩:−t Γ ⊢⟨. . . ⟨t1·t2⟩. . .⟩:−t(·L)Γ ⊢⟨. . . ⟨Θ1, Θ2⟩. . .⟩:−t(Cutλ)↦−→Π1Γ ⊢Θ1 :−t1Π2Γ ⊢Θ2 :−t2Π3Γ ⊢⟨. . . ⟨t1, t2⟩. . .⟩:−t Γ ⊢⟨. . . ⟨t1, Θ2⟩. . .⟩:−t(Cutλ)Γ ⊢⟨. . . ⟨Θ1, Θ2⟩. . .⟩:−tt(Cutλ)
Fig. 5. Some essential cases for Cutλ-elimination

We must prove that term sequents interact well with sentence sequents.

Theorem 5.10

Γ ⊢ t1:− t2 and Γ, t1⇝t2 ⊢ Θ :− t imply Γ ⊢ Θ :− t

Proof

By induction on the height of the derivation that Γ, t1⇝t2 ⊢ Θ :− t. If the final rule application is (⇝L) introducing t1⇝t2 then the result follows by (Cutλ) and then Theorem 5.9. 3 2

Full cut elimination now follows:

Theorem 5.11

− If Γ ⊢∆ is derivable using exactly one instance of (Cut) then it is derivable using none.

− If Γ ⊢∆ is derivable then it is derivable without using (Cut).

Π1Γ ⊢Θ1 :−t1Π2Γ ⊢⟨. . . t2 . . .⟩:−t Γ′ ⊢⟨. . . Θ1 . . .⟩:−t(⇝L)Π3Γ′ ⊢⟨. . . t . . .⟩:−t3Γ, t1⇝t2 ⊢⟨. . . ⟨. . . Θ1 . . .⟩. . .⟩:−t3(Cutλ)↦−→Π′ 1Γ′ ⊢Θ1 :−t1Π′ 2Γ′ ⊢⟨. . . t2 . . .⟩:−tΠ3Γ, t1⇝t2 ⊢⟨. . . t . . .⟩:−t3Γ′ ⊢⟨. . . ⟨. . . t2 . . .⟩. . .⟩:−t3(Cutλ)Γ′ ⊢⟨. . . ⟨. . . Θ1 . . .⟩. . .⟩:−t3(⇝L)where Γ′ is Γ, t1⇝t2, and Π′ 1, Π′ 2 are obtained from Π1, Π2 by weakening with t1 ≈t2 (see Lemma 5.8)Π1Γ ⊢Θ :−tΠ2Γ ⊢⟨. . . t . . .⟩:−t1Π3Γ ⊢⟨. . . t2[x/t1] . . .⟩:−t3Γ ⊢⟨. . . ⟨λx.t2, ⟨. . . t . . .⟩⟩. . .⟩:−t3(λL)Γ ⊢⟨. . . ⟨λx.t2, ⟨. . . Θ . . .⟩⟩. . .⟩:−t3(Cutλ)↦−→Π Γ ⊢Θ :−tΠ2Γ ⊢⟨. . . t . . .⟩:−t1Γ ⊢⟨. . . Θ1 . . .⟩:−t1(Cutλ)Π3Γ ⊢⟨. . . t2[x/t1] . . .⟩:−t3Γ ⊢⟨. . . ⟨λx.t2, ⟨. . . Θ . . .⟩⟩. . .⟩:−t3(λL)
Fig. 6. Some permutation cases for Cutλ-elimination
Proof

− The first part is by induction on the pair (d, r), lexicographically ordered, where d is the degree and r is the rank of the (Cut). The base case is where the cut formula is of the form t1⇝t2:

Π1Γ ⊢t1 :−t2Γ ⊢t1⇝t2, ∆(⇝R)Π2Γ, t1⇝t2 ⊢t :−t′Γ, t1⇝t2 ⊢t⇝t′, ∆(⇝R)Γ ⊢∆(Cut)↦−→Π1Π2.... Theorem 5.10 Γ ⊢t :−t′Γ ⊢t⇝t′, ∆(⇝R)

The remaining cases are as for cut elimination on first order logic.

− The second part follows by induction on the derivation.

2

6 Uniform derivations

Definition 6.1

A derivation of a term sequent is uniform if it is (Cutλ) free and for every term sequent Γ ⊢ Θ :− t in it, if t is not atomic then that sequent is the conclusion of an instance of a rule applying to t (i.e. (λR) or (·R)).

It is of interest to determine which term sequents are derivable by uniform derivations. To guarantee that derivations are uniform we need to modify the term sequent rules, in particular the left rules, and we must tweak our definition of a tree:

Definition 6.2

− Redefine trees by: Θ ::= t | ⟨Θ1, Θ2⟩| ⟨Θ1; Θ2⟩.

The difference between ⟨Θ1, Θ2⟩ and ⟨Θ1; Θ2⟩ is purely for bookkeeping, see Remark 6.5.

Definition 6.3

− The modified rule (⇝L−) is rule (⇝L)

Γ ⊢Θ :−t1Γ ⊢⟨. . . t2 . . .⟩:−t Γ, t1⇝t2 ⊢⟨. . . Θ . . .⟩:−t

with an additional restriction that the free variables of (terms appearing in) Θ be free also in t2 (intuitively, fv(Θ) ⊆ fv(t2)).

− The modified rule (λL−) is

Γ ⊢Θ :−t1Γ ⊢⟨. . . t2[x/t1] . . .⟩:−t Γ ⊢⟨. . . ⟨λx.t2; Θ⟩. . .⟩:−t(λL−)

(note the semicolon in the conclusion) with the restriction that the free variables of Θ be free also in t2[x/t1].

− The modified rule (·L−) is

Γ ⊢⟨. . . ⟨t1; t2⟩. . .⟩:−t Γ ⊢⟨. . . t1·t2 . . .⟩:−t(·L−)

(note the semicolon in the premise).

− We add an extra (λR) rule for the case of a semicolon:

Γ ⊢⟨Θ; x⟩:−t Γ ⊢Θ :−λx.t(λR)

(with the restriction that x is not free in Θ or Γ).

− The other rules are unchanged. In particular (·R) is not modified so as to introduce ⟨Θ1; Θ2⟩ on the left, it introduces only ⟨Θ1, Θ2⟩.

Theorem 6.4

If Γ ⊢ Θ :− t is derivable using the modified term sequent rules of Definition 6.3, then it is derivable by a uniform derivation.

Proof

By Theorem 5.9 (it remains valid for the modified rules and tweaked tree structure) we may assume that any derivation of Γ ⊢ Θ :− t is free of (Cutλ). The proof that such a derivation is uniform is by induction on its height.

Suppose t is not atomic and Γ ⊢ Θ :− t is the conclusion of any rule (?L−) other than (λR) or (·R). We may assume, by the induction hypothesis, that the derivations of the premises of (?L−) are uniform. The result follows by the induction hypothesis and the fact that (λR) or (·R) may be permuted with (?L−).

There are six permutations to consider, the three featuring (λR) are given in Figure 7. The remaining three cases featuring (·R) are straightforward. 2

Remark 6.5

It is worth noting how the modified left rules are required for Theorem 6.4. In the cases of (⇝L−) and (λL−), the restrictions ensure that they may be permuted with (λR) as shown in Figure 7. For example, looking at the third permutation of Figure 7 we see that after (λR) is swapped with (⇝L−), we must be sure that x is not free in Θ (otherwise the instance of (λR) is illegitimate). In the case of (·L−) the restriction is so that it can always be permuted with (·R).

To see the importance of the modified tree structure (the semicolons) note that (·R) generates new tree structure on the left of the term sequent. So if any subsequent instance of (·L) depends on this structure then it cannot be pushed behind (·R). The semicolons keep track of the tree structures on the left that depend only on (λL−), the restriction on (·L−) thus ensures that no instance of (·L−) depends on a prior instance of (·R).

The restrictions on (⇝L−), (λL−) and (·L−) and the modifications to the tree structure are sufficient but not necessary for Theorem 6.4. Refinements are for future research.

Restrictions arise in the notion of uniform derivation because — if we imagine a logic programming system based on these ideas — we must prevent the user from running programs which contain certain ‘silly’ reductions. This is not visible in the proof of cut-elimination, which considers the logic as a whole.

Definition 6.1 extends the existing notion of uniform derivation [8] to term sequent derivations. A term sequent derivation is uniform if (reading bottom up) we can always decompose the right part of a term sequent before decomposing the left parts: i.e. we can decompose the t of Γ ⊢ Θ :− t before we decompose Θ. Compare with the more familiar notion of uniform derivation for sentence sequents ‘a sentence sequent derivation is uniform when we can decompose the ∆of Γ ⊢∆ before we decompose Γ’.

Π Γ ⊢⟨⟨. . . ⟨t1, t2⟩. . .⟩, x⟩:−t Γ ⊢⟨. . . ⟨t1, t2⟩. . .⟩:−λx.t(λR)Γ ⊢⟨. . . t1·t2 . . .⟩:−λx.t(·L)↦−→Π Γ ⊢⟨⟨. . . ⟨t1, t2⟩. . .⟩, x⟩:−t Γ ⊢⟨. . . t1·t2 . . ., x⟩:−t(·L)Γ ⊢⟨. . . t1·t2 . . .⟩:−λx.t(λR)Π1Γ ⊢Θ :−t1Π2Γ ⊢⟨⟨. . . t2[x/t1] . . .⟩, x⟩:−t Γ ⊢⟨. . . t2[x/t1] . . .⟩:−λx.t(λR)Γ ⊢⟨. . . ⟨λx.t2; Θ⟩. . .⟩:−λx.t(λL−)↦−→Π1Γ ⊢Θ :−t1Π2Γ ⊢⟨⟨. . . t2[x/t1] . . .⟩, x⟩:−t Γ ⊢⟨⟨. . . ⟨λx.t2; Θ⟩. . .⟩, x⟩:−t(λL−)Γ ⊢⟨. . . t2[x/t1] . . .⟩:−λx.t(λR)Π1Γ ⊢Θ :−t1Π2Γ ⊢⟨⟨. . . t2 . . .⟩, x⟩:−t Γ ⊢⟨. . . t2 . . .⟩:−λx.t(λR)Γ, t1⇝t2 ⊢⟨. . . Θ . . .⟩:−λx.t(⇝L−)↦−→Π1Γ ⊢Θ :−t1Π2Γ ⊢⟨⟨. . . t2 . . .⟩, x⟩:−t Γ, t1⇝t2 ⊢⟨⟨. . . Θ . . .⟩, x⟩:−t(⇝L−)Γ ⊢⟨. . . t2 . . .⟩:−λx.t(λR)Π1Γ ⊢⟨. . . ⟨t1; t2⟩. . .⟩:−s1Π2Γ ⊢Θ :−s2Γ ⊢⟨⟨. . . ⟨t1; t2⟩. . .⟩, Θ⟩:−s1·s2(·R)Γ ⊢⟨⟨. . . ⟨t1·t2⟩. . .⟩, Θ⟩:−s1·s2(·L)↦−→Π1Γ ⊢⟨. . . ⟨t1; t2⟩. . .⟩:−s1Γ ⊢⟨. . . ⟨t1·t2⟩. . .⟩:−s1(·L)Π2Γ ⊢Θ :−s2Γ ⊢⟨⟨. . . ⟨t1·t2⟩. . .⟩, Θ⟩:−s1·s2(·R)
Fig. 7. Permutations of left and right rules

Term sequent logic combines term sequents with sentence sequents, thus we consider a derivation uniform when its sentence sequent parts are uniform in the familiar sense, and its term sequent parts are uniform in the sense of Definition 6.1:

Γ ⊢t1 :−t2Γ ⊢ti :: tj(E)i=1, j=2 or i=2, j=1Γ ⊢s1 :: t1Γ ⊢t2 :: s2Γ, t1 ≈t2 ⊢s1 :: s2(≈L)Γ ⊢t1 :: t2. . . Γ ⊢tn−1 :: tnΓ ⊢t1 ≈tn, ∆(≈R)
Fig. 8. Rules for λ-equality
Definition 6.6

A cut-free derivation of a sentence sequent is uniform if it is

(i) for every sentence sequent Γ ⊢A in it, if A is not atomic the sequent is an instance of the conclusion of rule applying to A (a right rule).

(ii) every subderivation of a term sequent is uniform in the sense of Definition 6.1.

Theorem 6.7

If Γ ⊢ A is derivable in the single conclusion fragment of the term sequent calculus (i.e. where ∆ is empty in any sentence sequent), then it is derivable by a uniform derivation.

Proof

That the first condition on a uniform derivation is met is a well known result on intuitionistic logic, e.g. see [8]. That the second condition on a uniform derivation is met is proved by Theorem 6.4. 2

7 λ-Equality

The equality offered by ↭ is strong (it relates relatively few terms). We often want two λ-terms equal when there is a chain of reductions linking them. To capture this we extend of term sequents with a new judgement form:

Definition 7.1

An equality-term sequent is a tuple Γ ⊢ t1 :: t2 where t1 and t2 are terms.

We extend the syntax to include a binary atomic predicate ≈ and extend the term sequent rules by the rules of Figure 8.

Theorem 7.2

If x does not occur in either argument position of ⇝ in (any part of) the sentence A then Γ ⊢ A[x/t1], ∆ implies Γ, t1 ≈ t2 ⊢ A[x/t2], ∆.

Theorem 7.3

⊢ t1 :: t2 if and only if t1=t2, where = is the reflexive-transitive-symmetric closure of ↠αβη.

Theorem 7.4

Theorem 6.7 extends to a term sequent calculus extended to include ≈ and equality-term sequents.

8 Conclusions

Related work.

Beeson’s λ-logic [2] has the sentences of first-order logic with equality, and as term-language the λ-calculus. Our paper is in this spirit. In λ-logic there is no proof-theory for the term language. This paper gives a proof-theory for the λ-calculus with the advantage that consistency follows by purely proof-theoretic means.

Rewriting combines computation with logic: computation is expressed by rewrites; the logical judgement form is simply ‘s rewrites to t’. A literature of rewriting exists to prove confluence [1] which is comparable in richness and variety to that on cut-elimination. Also properties comparable to those following cut-elimination can be deduced from confluence. There are echoes of rewriting in our term logic for the λ-calculus — ⇝ asserts a rewrite — yet the judgement form ‘s rewrites to t’ is weaker than that of a typical logic. Notably, rewrites cannot be made conditional. Thus, cut-elimination for our system is a different and stronger result than a confluence proof. Conditional rewriting strengthens the judgement form [9], but ‘if y reduces to λx.x then y·z reduces to z’ still cannot be expressed or derived; see Derivation D7.

Deduction Modulo combines logical derivation with rewriting [6]. However, rewrites are imposed globally (we fix the rewrites, then do deduction ‘modulo’ those rewrites). Rewrites cannot be hypothesised by a sequent or made conditional. In term sequent logic, term sequents may be made conditional on complex predicates in the logic, as illustrated by our example derivations.

Deduction modulo is concerned with this issue and has a vocabulary to express the distinction: deduction modulo rewrite rules are computations, and term sequent equality is deduction. Enriching deduction modulo with deduction-style rewrites has been investigated [3]. This is known to be a non-trivial problem not yet fully resolved. Thus, this research is more general than deduction modulo and should be of interest to that community. However, term sequents apply to terms whereas deduction modulo rewrites can rewrite terms to terms, and also rewrite predicates to predicates. In that sense deduction modulo is more general than this research.

λ-prolog has λ-terms [11], which are typed. Terms are syntactically identified up to αβη-equivalence and there is an equality up to αβη at every type. This is different from our system, which distinguishes sentences and terms, uses untyped terms, and does not syntactically identify terms up to αβη. Still, it may be possible to make some connections.

The second author is known for studying variables and conditions on variables [5]. We note that the conditions on uniform proof (Definition 6.3) have to do with free variables. It is interesting to see conditions on free variables arise in this context.

Future work.

The idea of term sequents is novel. There seems no obstacle to taking the idea further. ‘Ordinary’ sentence sequents have been used in great variety to study different logics; a benefit of term sequents may be that they can also be used in great variety to study different kinds of equality on terms.

For example: Term sequent systems for integer and rational arithmetic will be studied in future publications. Furthermore, a much more general enquiry is possible to establish syntactic or semantic criteria on term sequent systems that guarantee cut-elimination.

The prospect of applying logical techniques to a variety of term systems is an interesting test of logical techniques: terms are not sentences; how far can we push logical techniques before they break? Ultimately, this may inform our understanding of ‘what is a logic?’ [7].

In this paper we have applied term sequents to build and study a model of functional programming within first order logic. First order logic itself has a well-known notion of computation given by uniform proof. The combination of the two in term sequent logic for the λ-calculus described in our notion of uniform proof, can be viewed as some kind of rewrite strategy — but currently we do not fully understand it. Matters are complicated because, as we have mentioned before in this paper, in term-sequents we can impose assumptions and thus, in effect, dynamically permit ‘extra rewrites’. It seems plausible that this could be the outline of a new and powerful programming environment. We detect shades of rewriting logic in this [10] but we cannot comment further on any connections. Careful further study of the system presented in this paper is justified.

References

[1] Franz Baader and Tobias Nipkow, Term rewriting and all that, Cambridge University Press, Great Britain, 1998.

[2] Michael Beeson, Lambda logic, 2nd Int’l Joint Conf. on Automated Reasoning (IJCAR 2004), LNCS, vol. 3097, Springer, 2004, pp. 460–474.

[3] Eric Deplagne and Claude Kirchner, Deduction versus computation: the case of induction, AISC and Calculemus Joint International Conferences, Lecture Notes in Artificial Intelligence, vol. 2385, Springer, July 2002, pp. 4–6.

[4] Murdoch J. Gabbay and Michael J. Gabbay, a-logic with arrows, Proceedings of WFLP, 2007, pp. 47–63.

[5] Murdoch J. Gabbay and A. M. Pitts, A New Approach to Abstract Syntax with Variable Binding (journal version), Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.

[6] Benjamin Werner Gilles Dowek, Arithmetic as a theory modulo, RTA, 2005, pp. 423–437.

[7] Ian Hacking, What is logic?, The Journal of Philosophy 76 (1979), 285–319.

[8] Joshua S. Hodas and Dale Miller, Logic programming in a fragment of intuitionistic linear logic, Proceedings 6th IEEE Annual Symp. on Logic in Computer Science, Amsterdam, The Netherlands, 15–18 July 1991, IEEE Computer Society Press, New York, 1991, pp. 32–42.

[9] Stephane Kaplan and Jean-Pierre Jouannaud (eds.), Conditional term rewriting systems, LNCS, vol. 308, Springer, July 1988.

[10] N. Marti-Oliet and J. Meseguer, Rewriting logic as a logical and semantic framework, ENTCS (J. Meseguer, ed.), vol. 4, Elsevier Science Publishers, 2000.

[11] Dale Miller, A logic programming language with lambda-abstraction, function variables, and simple unification, Extensions of Logic Programming 475 (1991), 253–281.

[12] Peter W. O’Hearn and David J. Pym, The logic of bunched implications, Bulletin of Symbolic Logic 2 (1999), no. 5, 215–244.

Notes

1 Michael Gabbay gratefully acknowledges the support of the British Academy under the grant PDF/2006/509. ↩

2 Actually, the rules are not absolutely syntax directed as Derivation D5 shows. It would be surprising if they were for there is no general normal form for untyped λ-terms. However, it is clear that no derivation rules can reduce the overall complexity of a term sequent to containing only atomic terms. ↩

3 Since (Cut) is a rule applying only to sentence sequents it cannot feature in the derivations of Γ ⊢ t1 :− t2 and Γ, t1⇝t2 ⊢ Θ :− t. ↩