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

A Simple and Complete Model Theory for Intensional and Extensional Untyped λ-Equality

Michael Gabbay

Department of Philosophy, Kings College London

Murdoch Gabbay

Department of Computer Science, Heriott-Watt University, Edinburgh

Abstract

We present a sound and complete model theory for theories of β-reduction with or without η-expansion. The models of this paper derive from structures of modal logic: we use ternary accessibility relations on ‘possible worlds’ to model the action of intensional and extensional lambda-abstraction in much the same way binary accessibility relations are used to model the box operators of a normal multi-modal logic.

Keywords: Lambda Calculus, Reduction, Intensional Equality, Extensional Equality, Model Theory, Completeness, Kripke Frames, Possible World Semantics, Modal Logic.

1 Introduction

We extend the method of [6] by which we interpret λ-terms compositionally on ‘possible world’ structures. The simplicity of the structures is striking, moreover, they provide a surprising richness of interpretations of function abstraction and application.

Our primary goal is to show how the models can differentiate between extensional and intensional λ-equality, and provide semantic characterisation (i.e. completeness) theorems for both. We shall then hint at how richer λ-languages can be interpreted.

We are very grateful to the input and suggestions of the referees of this journal paper and of its previous incarnation as a conference paper at CiE 2012.

Vol. 1 No. 2 2014 IFCoLog Journal of Logic and its Applications

The key idea in this paper is a class of models, presented in Section 2.2, although an important syntactic consideration is required first in Section 2.1. These ideas bear some similarity to the reduction models of [18] in that they get us as far as λ-reduction only. Then, in Section 4 we use the results of the earlier sections to provide a characterisation theorem for λ-equality (both with and without η-equality, i.e. extensional and intensional).

2 The models, computation, logic

2.1 The language and logic

Definition 2.1

Fix a countably infinite set of variables.

Define a language Lλ of λ-terms by: t ∶∶= x ∣λx.t ∣ t⋅t λx binds in λx.t. For example, x is bound (not free) in λx.x⋅y.

We write t[x/s] for the usual capture-avoiding substitution. For example, (λz.y)[y/x] = λz.x, and (λx.y)[y/x] = λz.x where z is an arbitrary fresh variable. If x1... xn is a sequence of variables and t1... tn is an equally long sequence of terms then we write t[xi/ti] for the simultaneous substitution in t of each xi by its corresponding ti.

We write t[x∶−s] for the (unusual) non-capture avoiding substitution. For example, (λx.x)[x∶−y] = λx.y, and (λx.y)[y∶−x] = λx.x

We now turn to λ-reduction. It is important for us to consider not merely the relation of λ-reduction, but a relation of λ-reduction with assumptions. We therefore need to define some basic, and familiar, rules of λ-reduction but allow for a set of assumed additional reductions.

Remark 2.2

We shall define a basic relation on terms that follows the familiar reduction rule of β-contraction (Definition 2.3). To help with the completeness theorem of Section 3 we will need to consider a conservative extension of the familiar λ-calculus (Definition 2.5). To facilitate the proof that this extension really is conservative (Theorem 2.8), we present the λ-calculus in the non-axiomatic style of [12, Def. 1.24].

Definition 2.3

Let Γ be a set of pairs of terms of Lλ. We define a reduction relation →Γ on terms of Lλ using Figure 1. A derivation is a sequence of terms t1,... , tn such that ti →Γ ti+1 for each 1 ≤i < n.

Remark 2.4

If Γ = ∅ then →Γ is the familiar relation of untyped β-reduction.

Definition 2.5

Define L∗ λ by: t ∶∶= x ∣λx.t ∣ t⋅t ∣ t ∗ t

Let x occur free only once in t. Let x1 ... xn be any sequence of variables and t1 ... tnbe any (equally long) sequence of terms. (β) t[x∶−(λx.s)⋅r] →Γ t[x∶−s[x/r]](ass) t[x∶−s[xi/ti]] →Γ t[x∶−r[xi/ti]] (⟨s,r⟩∈Γ)(α) t[x∶−λy.s] →Γ t[x∶−λz.s[y/z]] The rule (ass) says that any (capture avoiding) substitution instance of s may be replaced in any t, without worrying about variable capture, by its matching substi- tution instance of r.1
Figure 1: λ-reduction for Lλ
Let x occur free only once in t. Let x1 ... xn be any sequence of variables and t1 ... tnbe any (equally long) sequence of terms. (β) t[x∶−(λx.s)⋅r] ⇒Γ t[x∶−s[x/r]](ass) t[x∶−s[xi/ti]] ⇒Γ t[x∶−r[xi/ti]] ⟨s,r⟩∈Γ(α) t[x∶−λy.s] ⇒Γ t[x∶−λz.s[y/z]](β∗) t[x∶−(λx.s) ∗r] ⇒Γ t[x∶−s[x/r]](sub) t[x∶−s⋅r] ⇒Γ t[x∶−s ∗r](η∗) t[x∶−s] ⇒Γ t[x∶−λy.(s ∗y)] (y not free in t)
Figure 2: λ-reduction for L∗ λ
Definition 2.6

Let Γ be a set of pairs of terms of Lλ (not L∗ λ). Define a reduction relation ⇒Γ on terms of L∗ λ using Figure 2. Again, a derivation is a sequence of terms t1,... , tn such that ti ⇒Γ ti+1 for each 1 ≤i < n.

Remark 2.7

Notice that we do not allow terms unique to L∗ λ to be assumptions in derivations. This is because the paper is concerned with characterising reduction and equality only in the more familiar language Lλ, and L∗ λ is merely a means to that end. Allowing assumed reductions for L∗ λ causes problems for the Theorem 2.8.

Theorem 2.8

If t1 and t2 are terms of Lλ then t1 ⇒Γ t2 implies t1 →Γ t1. In other words ⇒Γ is conservative over →Γ.

Proof

Suppose that t1 ⇒Γ t2, where t1, t2 ∈Lλ. We argue that any such derivation can be converted into a derivation that t1 →Γ t2.

We first argue that any application of (η) or (sub) can be pushed after an application of any other rule or eliminated entirely.

• Suppose we have the following derivation segment:

t[x∶−s](η∗)⇒Γ t[x∶−λy.(s ∗y)] ⇒Γ t[x∶−λy.(s′ ∗y)]

where s′ is derived from s by an application of any rule, then we may easily swap the rule applications:

t[x∶−s] ⇒Γ t[x∶−s′](η∗)⇒Γ t[x∶−λy.(s′ ∗y)]

• The cases where t′[x∶−s] is derived from t[x∶−s] is similar. For example:

t[z∶−r[x∶−s]](η∗)⇒Γ t[z∶−r[x∶−λy.(s ∗y)]](ass)⇒Γ t[z∶−r′[x∶−λy.(s ∗y)]]

may be replaced, given that Γ contains only terms from Lλ,2 by:

t[z∶−r[x∶−s]](ass)⇒Γ t[z∶−r′[x∶−s]](η∗)⇒Γ t[z∶−r′[x∶−λy.(s ∗y)]]

There are also the following three special cases:

t[x∶−s⋅r](η∗)⇒Γ t[x∶−λy.(s ∗y)⋅r](β)⇒Γ t[x∶−s⋅r]

becomes

t[x∶−s⋅r]t[x∶−s ∗r](η∗)⇒Γ t[x∶−λy.(s ∗y) ∗r](β∗)⇒Γ t[x∶−s ∗r]

becomes

t[x∶−s ∗r]t[x∶−s](η∗)⇒Γ t[x∶−λy.(s ∗y)](α)⇒Γ t[x∶−λz.(s ∗z)]

becomes

t[x∶−s](η∗)⇒Γ t[x∶−λz.(s ∗z)]

• By a similar reasoning it follows that (sub) can be pushed in front of any other rule, with the exception of the special case of the derivation segment

t[x∶−λy.s⋅r](sub)⇒Γ t[x∶−λy.s ∗r](β∗)⇒Γ t[x∶−s[y/r]]

which may be replaced by:

t[x∶−λy.s⋅r](β)⇒Γ t[x∶−s[y/r]]

It follows that any derivation may be replaced by a derivation where the last application is an instance of (η) or (sub), if either appears in the derivation at all. Since (η) and (sub) introduce an instance of ∗, if t2 ∈Lλ then no instances of (η) or (sub) occur in the derivation. Furthermore, since t1 ∈Lλ it follows that the derivation contains no instances of (β∗) or occurrences of ∗. This implies that t1 →Γ t2.End of proof

2.2 Frames and interpreting λ-terms

Given Theorem 2.8 we will work with L∗ λ.

Definition 2.9

If W is a set, write P(W) for the set of subsets of W.

An intensional frame F is a 4-tuple (W,●,○,H) where: −W a set of worlds, −● and ○ are functions from W × W to P(W) such that ●⊆○.

−H ⊆P(W).
Remark 2.10

Subsets of W will serve as denotations of λ-terms (Definition 2.13) and H ⊆P(W) (‘H’ for ‘Henkin’) plays a similar role to the structure of Henkin models for higher-order logic [2, 11, 19]. This makes our completeness results possible and is a famous issue for second- and higher-order logics: powersets are too large and for completeness results to be possible we must cut them down — at least when we quantify. This is why in Definition 2.13, the binders restrict quantification from P(W) down to H.

The reader familiar with modal logic can think of ● and ○ as ternary ‘accessibility relations’ R● and R○ such that R●w1w2w3 if and only if w3 ∈w1 ●w2 (and similarly for R○). We can also think of ● and ○ as non-deterministic ‘application’ operations, but note that intensional frames are not applicative structures — an applicative structure would map W ×W to W, whereas in the case of intensional frames, W ×W maps to P(W).

Definition 2.11

Let F = (W,●,○,H) be an intensional frame and S1,S2 ⊆W and w ∈W. Then the functions ● and ○ induce functions from W × P(W) and P(W) × P(W) to P(W) by: w ●S = ⋃{w ●w′ ∣w′ ∈S} and S1 ●S2 = ⋃{w1 ●w2 ∣ w1 ∈S1, w2 ∈S2} (and similarly for ○).

Definition 2.12

Suppose F = (W,●,○,H) is a frame. A valuation (to F) is a map from variables to sets of worlds (elements of P(W)) that are in H. v will range over valuations.

If x is a variable, h ∈H, and v is a valuation, then write v[x ↦h] for the valuation mapping x to h and mapping y to v(y) for any other y.

Definition 2.13

Define an denotation of t inductively by:

[[x]]v = v(x) [[t⋅s]]v = [[t]]v ●[[s]]v[[t ∗s]]v = [[t]]v ○[[s]]v[[λx.t]]v = {w ∣w ○h ⊆[[t]]v[x↦h] for all h ∈H}
Remark 2.14

By elementary set theory: [[λx.t]]v = ⋂h∈H{w ∣w ○h ⊆[[t]]v[x↦h]} We are particularly interested in frames where the denotation of every λ-term is a member of H. This is because Definition 2.13 interprets λ as a kind of quantifier over all members of H. β-reduction is then valid analogously to universal instantiation in first order logic (∀x.Fx ⊧Ft),3 and so requires that every possible instantiation (i.e. every term denotation) is a member of H.

Remark 2.15

Consider the definition of application and abstraction in a graph model with carrier set P(A) (Scott semantics), where ↦∶Pfin(A) × A ↦A is an arbitrary injective map and v ∶V ar ↦P(A) is an arbitrary environment:

X ●Y ={α ∣(∃a ⊆fin A) s.t. a ↦α ∈X and a ⊆Y } (X,Y ⊆A)[[λx.t]]v ={a ↦α ∣α ∈[[t]]v[x↦a]} (t a lambda term)={a ↦α ∣(∀h ∈P(A)){a ↦α} ●h ⊆[[t]]v[x↦h]}

Very roughly speaking (our construction is more general), the above definitions of application and abstraction in graph models are abstracted in this paper as follows, where H is a fixed subset of P(A):

●∶H × H ↦H =any linear map in both arguments [[λx.t]]v ={α ∣(∀h ∈H){α} ●h ⊆[[t]]v[x↦h]}

where v ∶V ar ↦H is an H-environment. This semantics is of perhaps of additional interest because it does not codify the step functions of continuous semantics.

Lemma 2.16

1. If x is not free in t, then for any h ∈H, [[t]]v = [[t]]v[x↦h].

2. [[t[x/s]]]v = [[t]]v[x↦[[s]]v]

Proof

Both parts follow by easy inductions on t.End of proof

Definition 2.17

A frame is faithful when for every v and every t ∈Lλ, [[t]]v ∈H. That is, a frame is faithful when H contains the interpretation of every λ term in Lλ independently of v.

Remark 2.18

Definition 2.17 is not ideal. A semantic characterisation of faithfulness — as a condition on H, ● and ○ — is desirable. We cannot present such a charactersiation in this paper except in the special cases of theories of β-equality which we defer until 5.1 of Section 5. In spite of this, the structures characterised by 2.17 are informative because they allow us to break down λ-abstraction into a quantification over worlds with a ternary accessibility relation; the denotations of λ-terms then become simply sets of worlds. On this analysis the domain of quantification for λ-abstraction — the actual set of denotations of λ-terms — is H, a subset of the set of all possible denotations P(W). This is a common pattern, for example in topological semantics for modal logics and for intuitionistic logic the set of denotations, the analogue of H, is the set of all open subsets of the domain rather than the powerset itself. It is then no accident that H will reveal further significance: it will be useful later in characterising the difference between extensional and intensional λ-calculus (see Remark 3.18). Unlike in the modal case, we offer no general way in this paper of characterising H beyond simply saying that it must contain [[t]]v for each valuation v and term t. For a considerably more complex characterisation of H in topological terms see [8].

Lemma 2.19

If we interpret ⇒Γ as subset inclusion then all the rules of Figure 2 are sound for faithful intensional frames.

Proof

By routine calculations from the definitions. We show only (β) and (η∗) here, the others are equally straightforward.

[[λx.t⋅s]]v= [[λx.t]]v ●[[s]]vDefinition 2.13= ⋂h∈H{w ∣w ○h ⊆[[t]]v[x↦h]} ●[[s]]vDefinition 2.13⊆{w ∣w ○[[s]]v ⊆[[t]]v[x↦[[s]]v]} ●[[t]]v[[s]]v ∈H⊆{w ∣w ●[[s]]v ⊆[[t]]v[x↦[[s]]v]} ●[[t]]v●⊆○⊆[[t]]v[x↦[[s]]v]Definition 2.11= [[t[x/s]]]vLemma 2.16[[t]]v ⊆⋂h∈H{w ∣w ○h ⊆[[t]]v ○h} Definition 2.11= ⋂h∈H{w ∣w ○h ⊆[[t ∗x]]v[x↦h]} x not free in [[t]]v= [[λx.(t ∗x)]]vDefinition 2.13End of proof

2.3 Soundness

Definition 2.20

− A model M is a pair ⟨F,v⟩ where F is a faithful intensional frame and v is a valuation on F such that v(t) ∈H ∈F for every t.

− A frame F is Γ-sensitive if [[t]]v ⊆[[s]]v for every v and every ⟨t, s⟩∈ Γ.

− A model ⟨F,v⟩ is Γ-sensitive if F is Γ-sensitive.

Remark 2.21

We could have defined a model as a pair ⟨F,v⟩ where F is a (possibly not faithful) frame and v is a valuation on F such that [[t]]v ∈H ∈F for every t. But since the completeness theorem 3.12 holds for the stronger notion of a model we shall use that. Intuitively a Γ-sensitive frame or model can be thought of as giving ⟨t, s⟩∈ Γ the meaning that however the variables of t and s are interpreted, t’s denotation is a subset of s’s.

Remark 2.22

This paper approaches lambda calculus from the angle of modal logic and so we retain the ‘normal’ practice of describing the model theory in terms of frames and models: a frame is sufficient to fix the interpretation of the closed terms, and a model interprets the open terms (e.g. as in [10]. This also matches the ‘normal’ practice in the model theory of first order logic of distinguishing a structure from a model – a structure together with a variable assignment – as in [3]. This differs from the ‘normal’ terminology for lambda calculus which would use the term ‘model’ to refer to our frames (e.g. in [1]).

Lemma 2.23

● and ○ are monotone. That is, h1 ⊆h2 implies h ●h1 ⊆h ●h2 and h1 ●h ⊆h2 ●h for any h, and similarly for ○.

Proof

By the pointwise definitions of ● and ○. For example:

h ●h1= ⋃{w ●w1 ∣w ∈h and w1 ∈h1} Def. 2.11⊆ ⋃{w ●w1 ∣w ∈h and w1 ∈h2} if h1 ⊆h2End of proof
Lemma 2.24

If [[s]]v ⊆[[r]]v for all v on some faithful F, then for any v on F [[t[x∶−s]]]v ⊆[[t[x∶−r]]]v

Proof

By induction on t. − If t is a variable the result is easy. − If t is t1⋅t2 or t1 ∗ t2 then the result follows from the induction hypothesis and the monotonicity of ● and ○ (Lemma 2.23).

− If t is λxt′, then t[x∶−s] is λx.t′[x∶−s]. And so:

[[λx.t′[x∶−s]]]v= ⋂h∈H{w ∣w ○h ⊆[[t′[x∶−s]]]v[x↦h]} Def. 2.13⊆ ⋂h∈H{w ∣w ○h ⊆[[t′[x∶−r]]]v[x↦h]} Ind. Hyp= [[λx.t′[x∶−r]]]vDef. 2.13

And the argument is similar if t is λy.t′ for y ≠ xEnd of proof

Theorem 2.25

t ⇒Γ s implies [[t]]v ⊆[[s]]v in all Γ-sensitive (faithful) models M.

Proof

Theorem 2.19 entails that each rule of Figure 2 holds in all models, and by definition, if ⟨t, s⟩∈ Γ then [[t]]v ⊆[[s]]v for all v in any Γ-sensitive model. The result then follows by Lemma 2.24.End of proof

3 Completeness for λ-reduction

Ultimately, we wish to show that if t /→Γ s then there is a Γ-sensitive model M (Def. 2.20) where [[t]]v /⊆[[s]]v. We first show that t /⇒Γ s implies such an M exists if t, s ∈Lλ, and then we appeal to Theorem 2.8.

First we form the languages Lλc,L∗ λc by adding infinitely many new constant symbols c1, c2... to Lλ and L∗ λc. Since the language is countable we can enumerate its terms t1, t2... , which may contain the new constants, and the new constants alone c1, c2... . We describe a one-one function f from terms to constants.

f(ti) = cj where j is the least number such that j > i and cj does not occur in ti nor is the value under f of any tk for k < i.

Thus f is a one-one function that assigns a distinct ‘fresh’ constant to each term of the language, so f(t) is a constant that ‘names’ t. These play the role of witness constants in the construction of the canonical frame in Theorem 3.8. The f(t) also help us carry out inductions on the size of λ-terms, as t[x/f(s)] is smaller than λx.t even if t[x/s] might not be.

Definition 3.1

Define a reduction relation ⇒f Γ on terms of of L∗ λc by setting t ⇒f Γ s if t ⇒Γ s and using the rule:

(con)t[x/s] ⇒f Γ t[x/f(s)] t[x/f(s)] ⇒f Γ t[x/s]

In other words, ⇒f Γ extends ⇒Γ with the rule (con), which makes t and its corresponding f(t) inter-reducible.

Remark 3.2

Simply extending ⇒Γ by insisting that {⟨t,f(t)⟩,⟨f(t), t⟩} ⊆ Γ for every t is not equivalent to defining ⇒f Γ as we have done above. For example, consider the individual variable x: if f(x) is c and ⟨x, c⟩∈ Γ then by (ass), t ⇒Γ c for any t.

Lemma 3.3

If t ⇒f Γ s and neither s nor t contain any of the new constants c1, c2... , then t ⇒Γ s.

Proof

f is defined in terms of an enumeration such that r always precedes f(r). Thus if we repeatedly substituting each instance of f(r) with r in a derivation, eventually all will be eliminated. But then instances of (con) depending on become trivial reductions r ⇒f Γ r which can be removed without affecting the rest of the derivation. Certainly the first and final terms t and s are unaffected as they never contained any f(r) in the first place.End of proof

Definition 3.4

If t is a term let wt = {s ∣ t ⇒f Γ s}. Thus wt is the closure of t under ⇒f Γ.

Definition 3.5

Define the canonical λ-frame Fλ = ⟨Wλ,●λ,○λ,Hλ⟩:

Wλ = {wt ∣t ∈L∗ λc} Hλ = {{w ∣t ∈w} ∣w ∈Wλ and t ∈Lλc} wt ●λ ws = {w ∈Wλ ∣t⋅s ∈w} wt ○λ ws = {w ∈Wλ ∣t ∗s ∈w}
Definition 3.6

Given Fλ = ⟨Wλ,●λ,○λ,Hλ⟩, and a term t of L∗ λ, let ∥t∥= {w ∈ Wλ ∣ t ∈w}. Note that Hλ = {∥t∥∣ t ∈Lλc}

Remark 3.7

Given (sub) it is easy to see that ●λ ⊆○λ. Frames where the converse does not hold are easy to construct (for example, Figure 3).

Theorem 3.8

Let Fλ be the canonical intensional λ-frame (Definition 3.5), let v(x) = ∥x∥ for any variable x, and extend v so that v(c) = c for any constant c. Then for any term t ∈Lλc, [[t]]v = ∥t∥.

Proof

By induction on t we show that w ∈∥t∥ (i.e. t ∈w) iff w ∈[[t]]v. − t is a variable x. Then ∥x∥= v(x) = [[x]]v by the definition of v. − t is t1⋅t2. Then t1, t2 ∈Lλc. Suppose t1⋅t2 ∈w, and consider the worlds wt1 and wt2 in Wλ. If s1 ∈wt1 and s2 ∈wt2 then by Definition 3.4, t1 ⇒f Γ s1 and t2 ⇒f Γ s2. Thus t1⋅t2 ⇒f Γ s1⋅s2 and s1⋅s2 ∈w. Then by the definition of ●λ we have that w ∈wt1●λwt2. Furthermore, wt1 ∈∥t1∥ and so by the induction hypothesis, wt1 ∈[[t1]]v. Similarly wt2 ∈[[t2]]v. Hence w ∈[[t1⋅t2]]v by Definition 2.13.

Conversely, suppose that w ∈[[t1⋅t2]]v. Then there are ws1,ws2 such that ws1 ∈ [[t1]]v and ws2 ∈[[t2]]v and w ∈ws1 ●λ ws2. By the induction hypothesis ws1 ∈∥t1∥ and ws2 ∈∥t2∥. Then s1 ⇒f Γ t1 and s2 ⇒f Γ t2. Furthermore, by the construction of ●λ, s1⋅s2 ∈w and hence by (cong) t1⋅t2 ∈w. − t is λx.s. s ∈Lλc. Suppose λx.s ∈w1. Suppose that w3 ∈w1 ○λ w2, and that w2 ∈h for some h ∈Hλ, then h = ∥r∥ for some term r. By (ζf) we have that r ⇒f Γ c and c ⇒f Γ r for some c ∈Lλc. So h = ∥c∥ and c ∈w2. By the construction of ○λ, λx.s ∗ r ∈w3 and so s[x/c] ∈w3 by (β∗), i.e. w3 ∈∥s[x/c]∥. Since s[x/c] ∈Lλc, it follows by the induction hypothesis that ∥s[x/c]∥= [[s[x/c]]]v. Furthermore by Lemma 2.16 [[s[x/c]]]v = [[s]]v[x↦[[c]]v]. But by the definition of v, [[c]]v = ∥c∥, and so w3 ∈[[s]]v[x↦∥c∥]. But h = ∥c∥ so w3 ∈[[s]]v[x↦h]. Thus w1 ∈{w ∣∀h ∈Hλ.w ○λ h ⊆[[s]]v[x↦h]} = [[(λx.s)]]v. Hence, ∥λx.s∥⊆[[(λx.s)]]v

Conversely, suppose that λx.s ∉wr for some r. Let y be a variable not free in r or s and consider the worlds wy and wr∗y. If s[x/y] ∈wr∗y then r ∗ y ⇒f Γ s[x/y], so λy.(r ∗ y) ⇒f Γ λy(s[x/y]) by (ξ). But by our choice of y, (η) entails that r ⇒f Γ λy.(r ∗ y). So r ⇒f Γ λy.s[x/y], which contradicts our initial supposition that λx.s ∉wr, therefore s[x/y] ∉wr∗y. In other words wr∗y ∉∥s[x/y]∥. But s[x/y] ∈Lλc, so by the induction hypothesis wr⋅y ∉[[s[x/y]]]v. Since [[y]]v = ∥y∥, it follows by Lemma 2.16 that wr⋅y ∉[[s]]v[x↦∥y∥]. But clearly wr∗y ∈wr ○λ wy, so it follows that wr ∉{w ∣∀h ∈Hλ.w ○λ h ⊆[[s]]v[x↦h]}. By the semantics of λy.s this means that wr ∉[[(λy.s)]]v. Hence, since every w ∈Wλ is wr for some r, [[(λx.s)]]v ⊆∥λx.s∥.End of proof

Lemma 3.9

If v1,v2 are any valuations on a frame F that such that

1. v1(x) = v2(x) for any variable x that occurs free in t,

2. v1,v2 are extended so that v1(c) = v2(c) for any constant c that occurs in t,

then [[t]]v1 = [[t]]v2.

Proof

By an easy induction on t.End of proof

Lemma 3.10

If there is a valuation v on a frame F such that {[[t]]v ∣ t ∈Lλ} = H, then F is faithful. Hence the canonical frame Fλ is faithful.

Proof

Suppose there is such a v, then we must show that for any valuation v′ and any term t ∈Lλ that [[t]]v′ ∈H. By the definition of a valuation, [[x]]v′ ∈H for any variable x. So if [[t]]v′ ∉H then by Lemma 3.9

[[t]]v[x1↦[[x1]]v′...xn↦[[xn]]v′] ∉H

where x1... xn are the free variables of t. Now, by assumption, v is such that every h ∈H is [[s]]v for some s. It follows then that we can choose s1... sn such that [[si]]v = v[xi ↦[[xi]]v′], and so:

[[t]]v[x1↦[[s1]]v...xn↦[[sn]]v] ∉H

This entails, by Theorem 2.16 that [[t[xi/si]]]v ∉H. But this contradicts the assumption that {[[t]]v ∣ t ∈Lλ} = H.End of proof

Lemma 3.11

Fλ is Γ-sensitive.

Proof

We must argue that for ⟨t1, t2⟩∈ Γ and any v, [[t1]]v ⊆[[t2]]v. Let x1... xn be the free variables of t1 and t2. Then v(xi) is some ∥si∥∈Hλ.

Let v′ be a valuation extended such that v′(r) = ∥r∥ for for any variable or constant r (i.e. v′ meets the condition of Theorem 3.8). Then:

[[t1]]v = [[t1]]v′[x1↦[[x1]]v...xn↦[[xn]]v]Lemma 3.9= [[t1]]v′[x1↦∥s1∥...xn↦∥sn∥]= [[t1]]v′[x1↦[[s1]]v′...xn↦[[sn]]v′]Theorem 3.8= [[t1[xi/si]]]v′Lemma 2.16= ∥t1[xi/si]∥ Theorem 3.8

and similarly for t2. But t1[xi/si] ⇒Γ t2[xi/si] by (ass), and so ∥t1[xi/si]∥⊆ ∥t2[xi/si]∥ and so [[t1]]v ⊆[[t2]]v.End of proof

Theorem 3.12

t ⇒Γ s if and only if [[t]]v ⊆[[s]]v for all Γ-sensitive models.4

Proof

The left-right direction is Theorem 2.25.

If t /⇒Γ s then s ∉wt in Fλ. Therefore ∥t∥/⊆∥s∥ and so by Theorem 3.8 there is a valuation v such that [[t]]v /⊆[[s]]v on the canonical frame Fλ. Furthermore, by Lemmas 3.10 and 3.11, Fλ is faithful and Γ-sensitive.End of proof

Corollary 3.13

If t and s are terms of Lλ then t →Γ s if and only if [[t]]v ⊆[[s]]v for all Γ-sensitive models.

Proof

Using Theorem 2.8 and the assumption that t and s are terms of Lλ we get that t →Γ s if and only if t ⇒Γ sEnd of proof

Definition 3.14

An extensional frame is an intensional frame where ●= ○, we may define them simply as a triple ⟨W,●,H⟩. Similarly an extensional model is a pair ⟨F,v⟩ where F is an extensional frame.

Corollary 3.15

Let Γ = {⟨x,λy.(x⋅y)⟩}. Then t ⇒Γ s if and only if [[t]]v ⊆[[s]]v for any faithful extensional model.

Proof

For the left-right direction it is a simple matter to apply the reasoning of Theorem 2.25. For the right-left direction it is enough to note that:

t[x∶−s ∗r](ass)⇒Γ t[x∶−λy(s⋅y) ∗r](β∗)⇒Γ t[x∶−s⋅r]

so in the construction of the canonical frame Fλ of Theorem 3.8, ●λ = ○λ.End of proof

Remark 3.16

An extensional frame satisfies η-expansion. An intensional frame is like an extensional frame except with an additional ‘outer’ application function ○. We interpret λ in terms of the outer function and application in terms of the inner function ● to block η-expansion (Definition 2.13). η-expansion will prove useful in constructing models of λ-equality in Section 4. Other authors have also noted reasons to include η-expansion in models [13].

Remark 3.17

Given 3.15, we can say that λ-reduction with η-expansion is complete for extensional frames.

Remark 3.18

Notice also a crucial purpose served by H in the completeness proof. Any subset of a frame is a potential denotation of a λ-term, and H may be seen as listing the subsets that actually are denotations of λ-terms. We have used this distinction to characterise intensional λ-reduction.

We took an (intensional) set of λ-reductions Γ (in Lλ) and we extended it using ∗ to help us interpret λ (Definition 2.5 and Theorem 2.8). Then, when we constructed the frame (Definition 3.5) for Γ we left out of H the denotations depending explicitly on ∗. We obtained a frame which is sensitive to all the reductions of Γ, in the original language Lλ, but where the interpretation of λ still depends on ∗ which is not mentioned in Γ (Theorem 3.8).

As we shall see, this provides a simple characterisation of intensional and extensional λ-abstraction. Abusing notation somewhat: extensional λx.t is something that maps objects h in the domain to t(h); intensional λx.t is something maps objects h in the domain and also some in a hidden domain to t(h). Furthermore, the ‘hidden’ objects are the denotations of terms in L∗ λ that require ∗.

y A solid arrow passing from w1 through w2 to w3 represents that w3 ∈w1 ●w2, and a dotted arrow represents that w3 ∈w1 ○w2. H can be set as P(W) and v(y) is as indicated. Then the two worlds on the left (unfilled) both are in [[λx.(y⋅x)]]v and [[λx.(y ∗x)]]v, but only one is in [[y]]v.
Figure 3: A counterexample to η-reduction in an intensional model where W contains 4 worlds.

3.1 η-reduction

As already noted, if x is not free in t, then [[t]]v ⊆[[λx.(t ∗ x)]]v in any intensional frame. That is, η-expansion is satisfied by any frame, but what about η-reduction? Figure 3 gives an example of a simple frame where [[y]]v /⊆[[λx.(y⋅x)]]v (and since ●⊆○, also [[y]]v /⊆[[λx.(y ∗ x)]]v).

We can characterise η-reduction syntactically easily enough:

Definition 3.19

Let η−= {⟨λx.(y⋅x), y⟩}.

Then t ⇒η−− s is the relation we want. Furthermore, we can use the completeness theorem 3.12 to describe a class of models for which this relation is complete:

Definition 3.20

A frame is η-reductive when ⋂h′∈H{w ∣w ○h′ ⊆h●h′}⊆h for any h.

Theorem 3.21

t ⇒η− s iff t ⊆ s in all η-reductive models.

Proof

It is straightforward to verify that t ⇒η−− s implies that [[t]]v ⊆[[s]]v in all η-reductive models. Conversely, if t /⇒η−− s then [[t]]v /⊆[[s]]v in the canonical model for η−:

⋂h′∈Hλ{w ∣w ○h′ ⊆∥t∥●h′} = ∥λx.(t⋅x)∥⊆∥t∥

since each h ∈H is ∥t∥ for some t.End of proof

4 Equality

Definition 4.1

Let β = {⟨t,λx.t⋅x]⟩∣ t ∈Lλ}.

Corollary 4.2

When restricted to Lλ, ⇒β is the familiar relation of (intensional) λ-equality, and by Theorem 3.12 is complete for β-sensitive models.

Remark 4.3

Corollary 4.2 is itself not so significant as it only tells us half the story about what these models look like, and does not tell us if there are any non-trivial ones. Of course, given independent nontriviality proofs for λ-equality,5 we can use Theorem 3.12 to conclude that there are nontrivial β-sensitive models. This section is concerned with producing a purely semantic characterisation of β-sensitivity. In fact, in characterising β-sensitivity, we can complete Definition 2.17 and provide a semantic characterisation of faithfulness.

The strategy we shall employ is as follows. First we introduce some shorthands to stand in for constructions involving λ-expressions, so for example K⋅z will stand in for (λxλy.x)⋅z. This will allow us to work with certain complex λ-expressions as if they are free of the symbol λ. Then, for each t we describe a new term [x]t, constructible only out of application and the new shorthands (effectively the familiar combinator abstraction of [12, p.26], but extended to a language that includes the λ-operator). Then, with the help of the completeness theorem 3.12, we describe conditions in which a model (or frame) entails that [[t[x/s]]]v = [[[x]t⋅s]]v. It then turns out that [[[x]t]]v ⊆[[λx.t]]v and we thereby obtain models of β-expansion.

Definition 4.4

Define the following shorthands:

K= λxy.x C =λxyz.((x⋅z)⋅y)) S =λxyz.((x⋅z)⋅(y⋅z))
Definition 4.5

− Say that an instance of λ in a term t is free if it is not part of an occurrence of K, C, S in t. − When defining or proving a property of a term t, we write ‘by induction on (l,d)’ to describe an induction on the pair (l,d), lexicographically ordered, where d is the number of occurrences of ⋅ in t and l is the number of occurrences of λ in t that are free.6

Definition 4.6

For any t ∈Lλ, define [x]t by induction on (l,d):

1. [x]x is (S⋅K)⋅K

2. [x]r is K⋅r if x is not free in r.

3. [x](s⋅r) is (S⋅[x]s)⋅[x]r

4. [x]λz.s is C⋅[z][x]s

Without loss of generality we assume that x and z are distinct in (4).

Lemma 4.7

If t ∈Lλ then [x]t ∈L∗ λ and (1) is well defined, (2) contains no free instances of λ, and (3) contains no free occurrences of x.

Proof

By induction on (l,d).

− If t is atomic or of the form s⋅r or s ∗ r then the result is easily proved.

− If t is λz.s then by the induction hypothesis [x]s is well defined and contains no free occurrences of λ. So the induction hypothesis applies again and the same may be said of [z][x]s. It then follows easily that the properties (1), (2) and (3) hold for [x]λz.s.End of proof

Lemma 4.8

Suppose t ∈Lλ and let variable v not occur in t, then [x](t[y/v]) = ([x]t)[y/v]

Proof

By induction on (l,d). − If t is x then x[y/v] = x and so

[x]x = (S⋅K⋅)K Def. 4.6= ([x]x)[y/v] y ∉(S⋅K⋅)K

− If t is y then y[y/v] = v and [x]y = K⋅y. So:

[x]v = K⋅v Def. 4.6= (K⋅y)[y/v] y ∉K= ([x]y)[y/v]

− The case where t is K, C, S or some variable other than x or y is similar. − If t is s⋅r or s ∗ r then the result follows easily by the induction hypothesis. − If t is λz.s, then we may assume that z is not x, then

[x](t[y/v]) = C⋅[z][x](s[y/v]) Def. 4.6= C⋅([z][x]s)[y/v] ind. hyp, Lemma 4.7= (C⋅[z][x]s)[y/v] y ∉C= ([x]t)[y/v]

End of proof

Theorem 4.9

If t ∈Lλ, then for any M = ⟨F,v⟩, [[[x]t ∗ s]]v ⊆[[t[x/s]]]v

Proof

By induction on (l,d).

We appeal to known facts about β-reduction and Theorem 3.12 (completeness). − t = x. Then [x]t ∗ s is ((S⋅K⋅)K)⋅s, and it is easy to show that that

((S⋅K⋅)K) ∗s ⇒∅s

So the result follows by Theorem 3.12. − The argument is similar for the case where t is a variable y ≠ x or K, C, S. We appeal to the easily shown fact that:

(K⋅t) ∗s ⇒∅t

− t = t1⋅t2. Then

((S⋅[x]t1) ∗[x]t2)⋅s ⇒∅t1[x/s]⋅t2[x/s]= (t1⋅t2)[x/s]

and the result follows as above. − The argument is similar for the case where t = t1 ∗ t2 − If t is λy.r, then choose a variable z that does not occur in r or s. Now, s and [x]s contain fewer free instances of λ than t (Lemma 4.7), so given Theorem 3.12 we may apply the induction hypothesis as follows:

[[(C⋅[y][x]r)⋅s]]v⊆ [[λz.(((C⋅[y][x]r)⋅s) ∗z)]]vThrm 2.25⊆ [[λz.(([y][x]r⋅z)⋅s)]]vThrm 3.12⊆ [[λz.([x]r[y/z]⋅s)]]vInd. Hyp.⊆ [[λz.(t[y/z,x/s])]]vInd. Hyp.= [[λy.(t[x/s])]]vEnd of proof
Definition 4.10

A frame is λ-complete when for any h1,h2,h3 ∈H

1. h1 = ([[K]]v ●h1) ●h2

2. (h1 ●h3) ●(h2 ●h3) = (([[S]]v ●h1) ●h2) ●h3

3. ⋂h∈H{w ∣(h1 ●h) ●h2} = ([[C]]v ●h1) ●h2

A model ⟨F,v⟩ is λ-complete if F is.

Remark 4.11

Notice that no h ∈H can be empty if F is a non-trivial λ-complete frame. For if ∅∈H then for any h ∈H, h = ([[K]]v ●h) ●∅= ∅, so then H = {∅} and [[t]]v = [[s]]v = ∅ for any t, s and v.

We could have equivalently defined λ-complete frames by requiring that, for any v [[x]]v = [[(K⋅x)⋅y]]v, [[(x⋅z)⋅(y⋅z)]]v = [[((S⋅x)⋅y)⋅z]]v, [[λz.((x⋅z)⋅y)]]v = [[(C⋅x)⋅y]]v and so on. But 4.10 is preferable as its form is less dependent on the syntax. Since K, S and C are closed terms, we could even go further and replace [[K]]v, [[S]]v and [[C]]v with purely semantic expressions using Definition 2.13.

Theorem 4.12

For any λ-complete ⟨F,v⟩, if t ∈Lλ then [[t[x/s]]]v ⊆[[[x]t⋅s]]v.

Proof

Again, we proceed by induction on (l,d). − t = x. Then x[x/s] = s and it is not hard to see that the definition of lambda completeness (4.10) implies that [[s]]v = [[((S⋅K)⋅K)⋅s]]v. − The argument is similar for the case where t = y ≠ x or t is K, C, S. − t = t1⋅t2. Then:

[[(t1⋅t2)[x/s]]]v= [[t1[x/s]]]v ●[[t2[x/s]]]v⊆ [[([x]t1⋅s)]]v ●[[([x]t2⋅s)]]vInd. Hyp.= ([[[x]t1]]v ●[[s]]v) ●([[[x]t2]]v ●[[s]]v)= (([[S]]v ●[[[x]t1]]v) ●[[[x]t2]]v) ●[[s]]vDef 4.10= [[((S⋅[x]t1)⋅[x]t2)⋅[[s]]v]]vDef. 2.13= [[([x]t1⋅t2)⋅s]]vDef. 4.6

and the result follows as above. − Suppose t is λy.r. Let z be chosen so that it does not occur in t or s. Then using Lemma 2.24:

[[λy.(r[x/s])]]v= [[λz.(r[y/z,x/s])]]v⊆ [[λz.([x](r[y/z])⋅s)]]vInd. Hyp.= [[λz.(([x]r)[y/z]⋅s)]]vLemma 4.8⊆ [[λz.(([y][x]r⋅z)⋅s)]]vInd. Hyp.⊆ [[(C⋅[y][x]r)⋅s]]vDef. 4.10= [[([x]λy.r)⋅s]]vDef. 4.6End of proof
Corollary 4.13

If t ∈Lλ then [[t[x/s]]]v = [[λx.t⋅s]]v for any λ-complete model ⟨F,v⟩.

Proof

Since ●⊆○ we have that [[λx.t⋅s]]v ⊆[[λx.t∗s]]v, and so Theorem 4.9 entails that [[λx.t⋅s]]v ⊆[[t[x/s]]]v.

And conversely:

[[t[x/s]]]v⊆ [[[x]t⋅s]]vThrm 4.12⊆ [[λx.([x]t ∗x)⋅s]]vThrm 3.12, Lemma 2.24, Lemma 4.7⊆ [[λx.t⋅s]]vThrm 4.9End of proof

We now have a means of characterising β-equality semantically.

Corollary 4.14

If t, s ∈Lλ then, t ⇒β s iff [[t]]v ⊆[[s]]v for all λ-complete models ⟨F,v⟩.

Proof

By 4.13 if ⟨t, s⟩∈β then [[t]]v ⊆[[s]]v in all λ-complete frames. Furthermore if t /⇒β s then [[t]]v /⊆[[s]]v in the canonical model for β. It is not hard to verify that the canonical frame is λ-complete.End of proof

Corollary 4.15

A frame is λ-complete iff it is β-sensitive

Definition 4.16

A frame is fully extensional when h = ⋂h′∈H{w ∣w ○h′ ⊆h ●h′} for all h ∈H. A model ⟨F,v⟩ is fully extensional when F is.

Remark 4.17

Looking at Definition 2.13 h = [[t]]v implies ⋂h′∈H{w ∣w ○h′ ⊆ h ●h′} = [[λx.(t⋅x)]]v for x ∉ t. So if a frame is fully extensional then, for any t and any v, [[t]]v = [[λx(t⋅x)]]v for x not free in t. This implies, by reasoning similar to Corollary 3.15, that ●= ○.

Definition 4.18

Let η = {⟨λx.(y⋅x), y⟩,⟨y,λx.(y⋅x)⟩} and let βη = β ∪η.

Theorem 4.19

If t, s ∈Lλ then, t ⇒βη s iff [[t]]v ⊆[[s]]v for all fully extensional λ-complete models ⟨F,v⟩.

Proof

It is straightforward to verify (see Remark 4.17) that t ⇒βη s implies that [[t]]v ⊆[[s]]v in all fully extensional, λ-complete models. Conversely, if t /⇒βη s then [[t]]v /⊆[[s]]v in the canonical model for βη, it is not hard to show that it is λ-complete and fully extensional.End of proof

Definition 4.20

Say that a frame is combinatorially complete when for any h1,h2,h3 ∈H

1. h1 = ([[K]]v ●h1) ●h2

2. (h1 ●h3) ●(h2 ●h3) = (([[S]]v ●h1) ●h2) ●h3

This is the familiar notion of combinatory completeness as used in characterisations of lambda models in terms of combinatory algebras (e.g. see [12, p.228]). We now get the following result.

Theorem 4.21

A fully extensional frame (model) is λ-complete if it is combinatorially complete.

Proof

Again, given Theorem 3.12 we argue partially syntactically. First note that the first two conditions of Definition 4.10 are met if F is combinatorially complete.

Now we argue that if a frame F is combinatorially complete, then for any v,

[[(x⋅z)⋅y]]v = [[((C⋅x)⋅y)⋅z]]v

Given soundness (Theorem 2.25) and known facts about combinators (e.g. [12, p.25]), if F is combinatorially complete then [[(x⋅z)⋅y]]v = [[((C′⋅x)⋅y)⋅z]]v for some particular complex expression C′ given in terms of S and K.7 Moreover, since F is fully extensional, i.e. [[λx(t⋅x)]]v = [[t]]v for any t ∈Lλ, then

[[C′]]v = [[λxyz.((C′⋅x)⋅y)⋅z]]v = [[λxyz.((x⋅r)⋅y)]]v = [[C]]v

and so [[(x⋅z)⋅y]]v = [[((C′⋅x)⋅y)⋅z]]v = [[((C⋅x)⋅y)⋅z]]v.

So if F is combinatorially complete then:

[[λz.((x⋅z)⋅y)]]v⊆ [[λz.(((C⋅x)⋅y)⋅z)]]vby the above⊆ [[(C⋅x)⋅y]]vas F is fully extensional

and so the third condition of 4.10 is met.End of proof

5 Faithfulness

The completeness result 4.15 relates λ theories to faithful λ-complete frames. Faithfulness was defined in 2.17 partially syntactically: a faithful frame is one that has a denotation h ∈H for every λ-term t.

It is natural to seek a characterisation of faithfulness that does not require explicit reference to the syntax, i.e. a purely semantic one. Can we provide a description, only in terms of H and R, of structural properties a frame must have in order that there is an h ∈H to be the denotation of each λ-term? The difficulty lies in the denotation of λ-terms of the form λx.s. We might know what must hold of H for it to include the denotation of s, but what of λx.s? λx acts like a kind of quantifier which binds in s. So the denotation of λx.s depends not just on s but on the denotations of s for all possible interpretations of x (assuming it is free in s).

What we have just described is an instance of the more general problem of syntax-free interpretations of quantification and binding (and substitution). We can solve the problem here for the the special case of a syntactic theory of λ-equality (i.e. a β-sensitive, or λ-complete, theory):8

Theorem 5.1

If an intensional frame F is λ-complete and also for any S1,S2 ⊆ P(W):

1. [[K]]v,[[S]]v,[[C]]v ∈H (for some/any v),

2. if S1,S2 ∈H then S1 ●S2 ∈H.

3. if S1 ∈H then ⋂h∈H{w ∣S ○h ⊆S1 ○h} ∈H (i.e. [[λy(x ∗ y)]]v[x↦S1] ∈H),

then F is faithful.

Proof

First notice that condition (1) is independent of v as K, S and C are all closed terms. Also note that by Definition 2.17, a frame is faithful when it guarantees an interpretation in H for every term of Lλ (i.e. terms not containing ∗). Condition (2) states that H is closed under ●. Condition (3) says that if [[x]]v ∈H then so is [[λy(x ∗ y)]]v. Given closure under ● this condition (3) could be replaced by the condition that [[λxy(x ∗ y)]]v ∈H.

We must argue that for any valuation v, [[t]]v ∈H for all t ∈Lλ. We do so by induction on t.

− t is a variable x. Then [[t]]v ∈H by the definition of valuations 2.12.

− t is s⋅r.Then the result follows by condition (2) and the induction hypothesis.

− t is λx.s. Then by the induction hypothesis [[r]]v ∈H for every subterm r of s. Now [x]s contains no free occurrences of x and is a concatenation, by the ⋅ symbol, only of instances of K, S, C and subterms of s. So by conditions (1), (2) [[[x]s]]v ∈H. But then by condition (3) and Lemma 2.16.2, [[λx.([x]s ∗ x)]]v ∈H.

Finally, given λ-completeness we may conclude from Theorems 4.9 and 4.12.1 that [[[x]s ∗ x]]v = [[s]]v and so [[λx.s]]v ∈HEnd of proof

Corollary 5.2

If an extensional frame F is λ-complete and the three conditions of 5.1 hold, then F is faithful.

Remark 5.3

It is easy to verify that the converses of 5.1 and 5.2 hold. Moreover, for the case of a fully extensional frame, we know from 4.21 that combinator completeness implies λ-completeness. It is then not hard to see that the conditions of 5.1 become instances of the definition of a syntax-free model of the λ-calculus. For example [12, p.237], condition (3) corresponds to the so-called (although not by [12]) Meyer-Scott axiom.

6 Further work

The methods used here resemble those behind the models of λ-calculus constructed by Engeler, Meyer, Plotkin and Scott (e.g. in [4, 14] and in [1, §18-19]) which are the basis of graph models.

The frames presented here have the components W, ● and H. Both ● and W have an analogue in graph models, and the differences between them and their analogues are not of great significance: it is not hard to associate each graph model with an equivalent extensional frame (see Remark 2.15). The analogue of H in graph models is that denotations are drawn from the powerset of the domain (the analogue of W). The fact that in the models and frames of this paper H can be something other than P(W) is significant. The completeness theorem 3.12 shows this, for it implies that every consistent λ-theory can be associated with a frame, and yet as shown by Salibra [17] there are λ-theories for which there are no graph models.

The models of this paper separate expansion and reduction for both β− and η− as distinct semantic properties of a model. Interestingly, β-reduction and η-expansion are natural features of the models (there is independent evidence that this is natural [13]). η-expansion arises from λ-abstraction and application being defined over the same underlying function ●. If we use two underlying functions ● and ○ instead, where ●⊆○, so that λ abstracts over ○ and application applies ●, then we obtain models free from η-expansion.

We could also reverse this ‘trick’ so that λ abstracts over the ● and application applies ○, and thus obtain models free from β-reduction. This may sound perverse but recall that meta-programming languages — languages that can suspend their own evaluation and/or quote their own syntax — are devoted to switching off β-reduction in a controlled manner, and the connections to modal logic have already been noted, where possible worlds correspond to deeper or shallower levels of suspension or quoting (see MetaML [15] and CMTT [16, 9]). This suggests the possibility of models for a variety of interacting λ-operators over a hierarchy of underlying application relations.

Finally, further work is needed in improving the semantic characterisations, in terms of ● and ○, of frames that are Γ-sensitive for interesting Γ. For example, can we provide a helpful semantic characterisation of theories that contain the schema of η-reduction? We can do it in terms of H by specifying that, for any S ∈H, ⋂h∈H{w ∣w ○h ⊆S ●h} ⊆S, but it would also be interesting to look for conditions on ● and ○ alone that correspond to this, independently of H.

References

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

[2] Christoph Benzmüller, Chad E. Brown, and Michael Kohlhase. Higher-order semantics and extensionality. Journal of Symbolic Logic, 69:1027–1088, 2004.

[3] H.B. Enderton. A Mathematical Introduction to Logic. Academic Press, 1972.

[4] Erwin Engeler. Algebras and combinators. Algebra Universalis, 13:389–392, 1981.

[5] Michael Gabbay. A proof-theoretic treatment of λ-reduction with cut-elimination: λ-calculus as a logic programming language. Journal of Symbolic Logic, 76(2):673–699, 2011.

[6] Michael Gabbay and Murdoch James Gabbay. A simple class of kripke-style models in which logic and computation have equal standing. In Edmund M. Clarke and Andrei Voronkov, editors, LPAR (Dakar), volume 6355 of Lecture Notes in Computer Science, pages 231–254. Springer, 2010.

[7] Murdoch J. Gabbay. Semantics out of context: nominal absolute denotations for first-order logic and computation. 2012. Submitted; available as arXiv preprint arxiv.org/abs/1305.6291.

[8] Murdoch J. Gabbay and Michael J. Gabbay. Representation and duality of the untyped lambda-calculus in nominal lattice and topological semantics, with a proof of topological completeness. 2012. Submitted; available as arXiv preprint arxiv.org/abs/1305.5968.

[9] Murdoch J. Gabbay and Aleksandar Nanevski. Denotation of contextual modal type theory (CMTT): syntax and metaprogramming. Journal of Applied Logic, 11:1–29, March 2013.

[10] Robert Goldblatt. Logics of Time and Computation. Number 7 in CSLI Lecture Notes. Center for the Study of Language and Information, 2. edition, 1992.

[11] Leon Henkin. Completeness in the theory of types. Journal of Symbolic Logic, 15:81–91, 1950.

[12] J. Roger Hindley and Jonathan P. Seldin. Lambda-Calculus and Combinators, An Introduction. Cambridge University Press, 2nd edition, 2008.

[13] C. Barry Jay and Neil Ghani. The virtues of eta-expansion. Journal of Functional Programming, 5(2):135–154, April 1995.

[14] Albert R. Meyer. What is a model of the lambda calculus? Information and Control, 1(52):87–122, 1982.

[15] Eugenio Moggi, Walid Taha, Zine-El-Abidine Benaissa, and Tim Sheard. An idealized metaml: Simpler, and more expressive. In ESOP ’99: Proc. of the 8th European Symposium on Programming Languages and Systems, volume 1576 of Lecture Notes in Computer Science, pages 193–207. Springer, 1999.

[16] Aleksandar Nanevski, Frank Pfenning, and Brigitte Pientka. Contextual modal type theory. ACM Transactions on Computational Logic (TOCL), 9(3):1–49, 2008.

[17] Antonino Salibra. Topological incompleteness and order incompleteness of the lambda calculus. ACM Trans. Comput. Logic, 4(3):379–401, 2003.

[18] Peter Selinger. Order-incompleteness and finite lambda reduction models. Theoretical Computer Science, 309(1):43–63, 2003.

[19] Stewart Shapiro. Foundations without foundationalism: a case for second-order logic. Number 17 in Oxford logic guides. Oxford University Press, 2000.

Received February 2014

Notes

1So for example if ⟨x,λy.(x⋅y)⟩∈ Γ then →Γ is a reduction relation allowing η-expansion: s may be rewritten, inside any term t, to λy.(s⋅y) provided the lambda-operator λy does not bind in s (although variables in s may be bound by abstractions in the wider context t. ↩

2And so the application of (ass) cannot depend on the preceding application of (η∗). ↩

3Perhaps a better analogy would be ∀x.(Fx →Gx) ∧Ft ⊧Gt, where conjunctions corresponds to ⋅ and the quantified expression corresponds to a λ-term. ↩

4Equivalently: t ⇒Γ s if and only if [[t]]v ⊆[[s]]v for any valuation v on any Γ-sensitive frame. ↩

5Nontriviality follows syntactically from the Church-Rosser property [12, Ch. A2], the cut-elimination theorem of [5]; and it follows semantically from Scott’s famous model Dω [12, Ch. 16], among others. ↩

6More loosely, if we were to treat K, C, S as constants in t (i.e. not containing λ at all), then l would be the number of occurrences of λ in t. ↩

7C′ is (S⋅((B⋅B)⋅S))⋅(K⋅K)) where B is short for (S⋅(K⋅S))⋅K. ↩

8The mathematical designs of this paper, combined with those of [5, 7], give rise to a more general solution for λ-reduction in [8]. ↩