A Simple and Complete Model Theory for Intensional and Extensional Untyped -Equality
Murdoch Gabbay
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
Fix a countably infinite set of variables.
Define a language of -terms by: t x xt tt x binds in xt. For example, x is bound (not free) in xxy.
We write txs for the usual capture-avoiding substitution. For example, zyyxzx, and xyyxzx where z is an arbitrary fresh variable. If is a sequence of variables and is an equally long sequence of terms then we write t for the simultaneous substitution in t of each by its corresponding .
We write txs for the (unusual) non-capture avoiding substitution. For example, xxxyxy, and xyyxxx
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.
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].
Let Γ be a set of pairs of terms of . We define a reduction relation on terms of using Figure 1. A derivation is a sequence of terms such that for each 1 .
If Γ then is the familiar relation of untyped -reduction.
Define by: t x xt tt t t
Let Γ be a set of pairs of terms of (not ). Define a reduction relation on terms of using Figure 2. Again, a derivation is a sequence of terms such that for each 1 .
Notice that we do not allow terms unique to to be assumptions in derivations. This is because the paper is concerned with characterising reduction and equality only in the more familiar language , and is merely a means to that end. Allowing assumed reductions for causes problems for the Theorem 2.8.
If and are terms of then implies . In other words is conservative over .
Suppose that , where . We argue that any such derivation can be converted into a derivation that .
We first argue that any application of or can be pushed after an application of any other rule or eliminated entirely.
• Suppose we have the following derivation segment:
where is derived from s by an application of any rule, then we may easily swap the rule applications:
• The cases where xs is derived from txs is similar. For example:
may be replaced, given that Γ contains only terms from ,2 by:
There are also the following three special cases:
becomes
becomes
becomes
• By a similar reasoning it follows that can be pushed in front of any other rule, with the exception of the special case of the derivation segment
which may be replaced by:
It follows that any derivation may be replaced by a derivation where the last application is an instance of or , if either appears in the derivation at all. Since and introduce an instance of , if then no instances of or occur in the derivation. Furthermore, since it follows that the derivation contains no instances of or occurrences of . This implies that .
2.2 Frames and interpreting -terms
Given Theorem 2.8 we will work with .
If is a set, write for the set of subsets of .
An intensional frame is a 4-tuple where: a set of worlds, and are functions from to such that .
Subsets of will serve as denotations of -terms (Definition 2.13) and (‘’ 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 down to .
The reader familiar with modal logic can think of and as ternary ‘accessibility relations’ and such that if and only if (and similarly for ). 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 to , whereas in the case of intensional frames, maps to .
Let be an intensional frame and and . Then the functions and induce functions from and to by: and (and similarly for ).
Suppose is a frame. A valuation (to ) is a map from variables to sets of worlds (elements of ) that are in . will range over valuations.
If x is a variable, , and is a valuation, then write x for the valuation mapping x to and mapping y to y for any other y.
Define an denotation of t inductively by:
By elementary set theory: xtt We are particularly interested in frames where the denotation of every -term is a member of . This is because Definition 2.13 interprets as a kind of quantifier over all members of . -reduction is then valid analogously to universal instantiation in first order logic (),3 and so requires that every possible instantiation (i.e. every term denotation) is a member of .
Consider the definition of application and abstraction in a graph model with carrier set (Scott semantics), where is an arbitrary injective map and is an arbitrary environment:
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 is a fixed subset of :
where is an -environment. This semantics is of perhaps of additional interest because it does not codify the step functions of continuous semantics.
1. If x is not free in t, then for any , tt.
2.
Both parts follow by easy inductions on t.
A frame is faithful when for every and every t , t. That is, a frame is faithful when contains the interpretation of every term in independently of .
Definition 2.17 is not ideal. A semantic characterisation of faithfulness — as a condition on , 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 , a subset of the set of all possible denotations . This is a common pattern, for example in topological semantics for modal logics and for intuitionistic logic the set of denotations, the analogue of , is the set of all open subsets of the domain rather than the powerset itself. It is then no accident that 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 beyond simply saying that it must contain t for each valuation and term t. For a considerably more complex characterisation of in topological terms see [8].
If we interpret as subset inclusion then all the rules of Figure 2 are sound for faithful intensional frames.
By routine calculations from the definitions. We show only and here, the others are equally straightforward.
2.3 Soundness
A model is a pair where is a faithful intensional frame and is a valuation on such that t for every t.
A frame is Γ-sensitive if ts for every and every t s Γ.
A model is Γ-sensitive if is Γ-sensitive.
We could have defined a model as a pair where is a (possibly not faithful) frame and is a valuation on such that t 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.
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]).
and are monotone. That is, implies and for any , and similarly for .
By the pointwise definitions of and . For example:
If sr for all on some faithful , then for any on txstxr
By induction on t. If t is a variable the result is easy. If t is or then the result follows from the induction hypothesis and the monotonicity of and (Lemma 2.23).
If t is , then txs is xxs. And so:
And the argument is similar if t is y for y x
t s implies ts in all Γ-sensitive (faithful) models .
3 Completeness for -reduction
Ultimately, we wish to show that if t s then there is a Γ-sensitive model (Def. 2.20) where ts. We first show that t s implies such an exists if t s , and then we appeal to Theorem 2.8.
First we form the languages by adding infinitely many new constant symbols to and . Since the language is countable we can enumerate its terms , which may contain the new constants, and the new constants alone . We describe a one-one function from terms to constants.
where is the least number such that and does not occur in nor is the value under of any for .
Thus is a one-one function that assigns a distinct ‘fresh’ constant to each term of the language, so 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 t also help us carry out inductions on the size of -terms, as txs is smaller than xt even if txs might not be.
Define a reduction relation on terms of of by setting t s if t s and using the rule:
In other words, extends with the rule , which makes t and its corresponding t inter-reducible.
Simply extending by insisting that ttt t Γ for every t is not equivalent to defining as we have done above. For example, consider the individual variable x: if x is c and x c Γ then by , t c for any t.
If t s and neither s nor t contain any of the new constants , then t s.
is defined in terms of an enumeration such that r always precedes r. Thus if we repeatedly substituting each instance of r with r in a derivation, eventually all will be eliminated. But then instances of depending on become trivial reductions r 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 r in the first place.
If t is a term let s t s. Thus is the closure of t under .
Define the canonical -frame :
Given , and a term t of , let t t . Note that t t
Given it is easy to see that . Frames where the converse does not hold are easy to construct (for example, Figure 3).
Let be the canonical intensional -frame (Definition 3.5), let xx for any variable x, and extend so that c c for any constant c. Then for any term t , tt.
By induction on t we show that t (i.e. t ) iff t. t is a variable x. Then xxx by the definition of . t is . Then . Suppose , and consider the worlds and in . If and then by Definition 3.4, and . Thus and . Then by the definition of we have that . Furthermore, and so by the induction hypothesis, . Similarly . Hence by Definition 2.13.
Conversely, suppose that . Then there are such that and and . By the induction hypothesis and . Then and . Furthermore, by the construction of , and hence by . t is xs. s . Suppose xs . Suppose that , and that for some , then r for some term r. By we have that r c and c r for some c . So c and c . By the construction of , xs r and so sxc by , i.e. sxc. Since sxc, it follows by the induction hypothesis that sxcsxc. Furthermore by Lemma 2.16 sxc s. But by the definition of , cc, and so s. But c so s. Thus sxs. Hence, xsxs
Conversely, suppose that xs for some r. Let y be a variable not free in r or s and consider the worlds and . If sxy then r y sxy, so yr yysxy by . But by our choice of y, entails that r yr y. So r ysxy, which contradicts our initial supposition that xs , therefore sxy. In other words sxy. But sxy, so by the induction hypothesis sxy. Since yy, it follows by Lemma 2.16 that s. But clearly , so it follows that s. By the semantics of ys this means that ys. Hence, since every is for some r, xsxs.
If are any valuations on a frame that such that
1. xx for any variable x that occurs free in t,
2. are extended so that cc for any constant c that occurs in t,
then tt.
By an easy induction on t.
If there is a valuation on a frame such that t t , then is faithful. Hence the canonical frame is faithful.
Suppose there is such a , then we must show that for any valuation and any term t that t. By the definition of a valuation, x for any variable x. So if t then by Lemma 3.9
where are the free variables of t. Now, by assumption, is such that every is s for some s. It follows then that we can choose such that , and so:
This entails, by Theorem 2.16 that t. But this contradicts the assumption that t t .
is Γ-sensitive.
We must argue that for Γ and any , . Let be the free variables of and . Then is some .
Let be a valuation extended such that rr for for any variable or constant r (i.e. meets the condition of Theorem 3.8). Then:
and similarly for . But by , and so and so .
t s if and only if ts for all Γ-sensitive models.4
If t and s are terms of then t s if and only if ts for all Γ-sensitive models.
Using Theorem 2.8 and the assumption that t and s are terms of we get that t s if and only if t s
An extensional frame is an intensional frame where , we may define them simply as a triple . Similarly an extensional model is a pair where is an extensional frame.
Let Γ xyxy. Then t s if and only if ts for any faithful extensional model.
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].
Given 3.15, we can say that -reduction with -expansion is complete for extensional frames.
Notice also a crucial purpose served by in the completeness proof. Any subset of a frame is a potential denotation of a -term, and 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 ) 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 the denotations depending explicitly on . We obtained a frame which is sensitive to all the reductions of Γ, in the original language , 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 xt is something that maps objects in the domain to t; intensional xt is something maps objects in the domain and also some in a hidden domain to t. Furthermore, the ‘hidden’ objects are the denotations of terms in that require .
3.1 -reduction
As already noted, if x is not free in t, then txt x 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 yxyx (and since , also yxy x).
We can characterise -reduction syntactically easily enough:
Let xyx 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:
A frame is -reductive when for any .
t s iff t s in all -reductive models.
It is straightforward to verify that t s implies that ts in all -reductive models. Conversely, if t s then ts in the canonical model for :
since each is t for some t.
4 Equality
Let txtx t .
When restricted to , is the familiar relation of (intensional) -equality, and by Theorem 3.12 is complete for -sensitive models.
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 Kz will stand in for xyxz. 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 xt, 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 txsxts. It then turns out that xtxt and we thereby obtain models of -expansion.
Define the following shorthands:
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 ’ to describe an induction on the pair , lexicographically ordered, where is the number of occurrences of in t and is the number of occurrences of in t that are free.6
For any t , define xt by induction on :
1. xx is SKK
2. xr is Kr if x is not free in r.
3. xsr is Sxsxr
4. xzs is Czxs
Without loss of generality we assume that x and z are distinct in (4).
If t then xt and (1) is well defined, (2) contains no free instances of , and (3) contains no free occurrences of x.
By induction on .
If t is atomic or of the form sr or s r then the result is easily proved.
If t is zs then by the induction hypothesis xs is well defined and contains no free occurrences of . So the induction hypothesis applies again and the same may be said of zxs. It then follows easily that the properties (1), (2) and (3) hold for xzs.
Suppose t and let variable v not occur in t, then xtyv xtyv
By induction on . If t is x then xyv x and so
If t is y then yyv v and xy Ky. So:
The case where t is K, C, S or some variable other than x or y is similar. If t is sr or s r then the result follows easily by the induction hypothesis. If t is zs, then we may assume that z is not x, then
If t , then for any , xt stxs
By induction on .
We appeal to known facts about -reduction and Theorem 3.12 (completeness). t x. Then xt s is SKKs, and it is easy to show that that
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:
t . Then
and the result follows as above. The argument is similar for the case where t If t is yr, then choose a variable z that does not occur in r or s. Now, s and xs contain fewer free instances of than t (Lemma 4.7), so given Theorem 3.12 we may apply the induction hypothesis as follows:
A frame is -complete when for any
1.
2.
3.
A model is -complete if is.
Notice that no can be empty if is a non-trivial -complete frame. For if then for any , K, so then and ts for any t s and .
We could have equivalently defined -complete frames by requiring that, for any xKxy, xzyzSxyz, zxzyCxy 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, S and C with purely semantic expressions using Definition 2.13.
For any -complete , if t then txsxts.
Again, we proceed by induction on . t x. Then xxs s and it is not hard to see that the definition of lambda completeness (4.10) implies that sSKKs. The argument is similar for the case where t y x or t is K, C, S. t . Then:
and the result follows as above. Suppose t is yr. Let z be chosen so that it does not occur in t or s. Then using Lemma 2.24:
If t then txsxts for any -complete model .
We now have a means of characterising -equality semantically.
If t s then, t s iff ts for all -complete models .
By 4.13 if t s then ts in all -complete frames. Furthermore if t s then ts in the canonical model for . It is not hard to verify that the canonical frame is -complete.
A frame is -complete iff it is -sensitive
A frame is fully extensional when for all . A model is fully extensional when is.
Let xyx yyxyx and let .
If t s then, t s iff ts for all fully extensional -complete models .
It is straightforward to verify (see Remark 4.17) that t s implies that ts in all fully extensional, -complete models. Conversely, if t s then ts in the canonical model for , it is not hard to show that it is -complete and fully extensional.
Say that a frame is combinatorially complete when for any
1.
2.
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.
A fully extensional frame (model) is -complete if it is combinatorially complete.
Again, given Theorem 3.12 we argue partially syntactically. First note that the first two conditions of Definition 4.10 are met if is combinatorially complete.
Now we argue that if a frame is combinatorially complete, then for any ,
Given soundness (Theorem 2.25) and known facts about combinators (e.g. [12, p.25]), if is combinatorially complete then xzyxyz for some particular complex expression given in terms of S and K.7 Moreover, since is fully extensional, i.e. xtxt for any t , then
and so xzyxyzCxyz.
So if is combinatorially complete then:
and so the third condition of 4.10 is met.
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 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 and , of structural properties a frame must have in order that there is an to be the denotation of each -term? The difficulty lies in the denotation of -terms of the form xs. We might know what must hold of for it to include the denotation of s, but what of xs? x acts like a kind of quantifier which binds in s. So the denotation of xs 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
If an intensional frame is -complete and also for any :
1. KSC (for some/any ),
2. if then .
3. if then (i.e. yx y),
then is faithful.
First notice that condition (1) is independent of 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 for every term of (i.e. terms not containing ). Condition (2) states that is closed under . Condition (3) says that if x then so is yx y. Given closure under this condition (3) could be replaced by the condition that xyx y.
We must argue that for any valuation , t for all t . We do so by induction on t.
t is a variable x. Then t by the definition of valuations 2.12.
t is sr.Then the result follows by condition (2) and the induction hypothesis.
t is xs. Then by the induction hypothesis r for every subterm r of s. Now xs 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) xs. But then by condition (3) and Lemma 2.16.2, xxs x.
Finally, given -completeness we may conclude from Theorems 4.9 and 4.12.1 that xs xs and so xs
If an extensional frame is -complete and the three conditions of 5.1 hold, then is faithful.
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 , and . Both and 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 in graph models is that denotations are drawn from the powerset of the domain (the analogue of ). The fact that in the models and frames of this paper can be something other than 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 by specifying that, for any , , but it would also be interesting to look for conditions on and alone that correspond to this, independently of .
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 xyxy Γ then is a reduction relation allowing -expansion: s may be rewritten, inside any term t, to ysy 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 cannot depend on the preceding application of . ↩
3Perhaps a better analogy would be , where conjunctions corresponds to and the quantified expression corresponds to a -term. ↩
4Equivalently: t s if and only if ts for any valuation 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 [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 would be the number of occurrences of in t. ↩
7 is SBBSKK where B is short for SKSK. ↩
8The mathematical designs of this paper, combined with those of [5, 7], give rise to a more general solution for -reduction in [8]. ↩