A simple class of Kripke-style models in which logic and computation have equal standing
1 http://www.kcl.ac.uk/philosophy/people/fellows/mgabbay.html
Abstract. We present a sound and complete model of lambda-calculus reductions based on structures inspired by modal logic (closely related to Kripke structures). Accordingly we can construct a logic which is sound and complete for the same models, and we identify lambda-terms with certain simple sentences (predicates) in this logic, by direct compositional translation. Reduction then becomes identified with logical entailment. Thus, the models suggest a new way to identify logic and computation. Both have elementary and concrete representations in our models; where these representations overlap, they coincide. In a concluding speculation, we note a certain subclass of the models which seems to play a role analogous to that played by the cumulative hierarchy models in axiomatic set theory and the natural numbers in formal arithmetic — there are many models of the respective theories, but only some, characterised by a fully second order interpretation, are the ‘intended’ ones.
1 Introduction
We try to unify logic and computation by using a class of structures which are (very nearly) Kripke structures. It turns out that these structures allow sound and complete interpretations of both a logic (an extension of second-order propositional logic), and computation (the untyped -calculus). Furthermore, we are able to compositionally translate -terms and formulae into our logic, and when we do so, the ‘computational’ reduction maps to logical entailment, and maps to a kind of logical quantifier.
Combining logic and computation is of course not a new idea. The two notions are clearly related and intertwined, and there are good theoretical and practical reasons to be interested in these questions.
A naive combination of logic and computation can lead to some famous contradictions. Consider untyped -calculus quotiented by computational equivalence, e.g. -equivalence. Suppose also the naive addition of some basic logical operations, e.g. negation . Then we can form a term encoding the Liar paradox .().(). Then and from this a contradiction quickly follows. This is, in a nutshell, the argument in [15].3
We can persist with adding logic to -terms. This motivated the development of types, as in higher-order logic [21], where the paradox is avoided by restricting which terms can receive an interpretation. Also, with the same intuitions but different design decisions, illative combinatory logics [3,2] can admit an untyped system but restrict which -terms count as ‘logical’.
Conversely, we can view, e.g. the negation of a -term as a category error, and think of computation as an object or vehicle of logical systems. So for example rewriting logic has a logic with an oriented equality representing reduction; whereas deduction modulo [4,7] has a background ‘computational engine’ which may be triggered to efficiently compute equalities between terms, but the logic is modulo this and reasons up to computational equivalence. In both cases the interpretations of the logical and computational parts of the languages are separated, like sentences are separated from terms in first-order languages and semantics.
The model of logic and computation of this paper is like rewriting logic in that we explicitly represent computations (reductions) by an arrow, . However, in line with the original intuition equivocating logic and computation, is the same arrow as is used to represent logical implication.
In our models, -terms are interpreted as sets on a domain and is interpreted as ‘complement union’. Entailment and reduction are both therefore represented in the models as subset inclusion (see Definition 2.13). That is, this arrow really is standard implication, just as the reader is used to. We discuss in Section 5.1 how this relates to the paradox above.
The kernel of the ideas in this paper is a class of models, presented in Section 2.1; the rest of the paper can be considered to arise just by considering their structure. It turns out that it is possible to consider -abstraction as a kind of quantifier and to consider reduction as subset inclusion (Section 2.2). The models are sets-based: The usual logical connectives such as conjunction, negation, and quantification are interpreted in the models as operations on sets; and logical entailment is interpreted as subset inclusion. We obtain an extension of classical second-order propositional logic with quantifiers (Section 2.3). We make our logic rich enough that it captures the structure we used to interpret -abstraction and reduction; because reduction is interpreted as subset inclusion, it maps directly to logical entailment.
The idea of modelling -reduction is not new. Models of reduction where terms are interpreted as points in an ordering are discussed by Selinger in [19]; and models, based on graph models, where terms are interpreted as sets on a domain of functions, are given in [16]. The models in Section 2 have similarities with these. One significant difference is that our models have a Boolean structure, in particular every denotation has a complement and a universal quantification. So the denotational domains for -terms also display the structure of denotational domains of propositions of classical logic.
So: logic and computation are not identical in this story (we do not claim that logic is computation, or vice versa) — but the two notions overlap in the models, and in this overlap, they coincide.
One possible use for our models is that they might provide a relatively elementary and systematic framework for extensions of the pure -calculus with ‘logical’ constructs, and indeed the design of other logics. We do not consider that there is anything sacred about the particular languages we use in this paper. However, they do have the virtues of being simple and well-behaved. In particular we can give tight soundness and completeness results for both the logic and the -calculus (Theorems 2.27 and 4.13).
The structure and main results of this paper are as follows: We develop a simple model theory and the syntax it motivates in Section 2; in Section 3 we verify that we can faithfully translate a system of -reduction into this syntax (and thus obtain a new model theory for -reduction); in Section 4 we prove completeness for an axiomatisation of the model theory. We conclude with some comments on the significance of the models presented here both for current and further research.
2 The models, computation, logic
2.1 Frames
If is a set, write () for the set of subsets of .
A frame is a 3-tuple (, , ) of
a set of worlds,
an application function from to (), and
Frames are not monoids or any other form of applicative structure — an applicative structure would map to and not, as we do here, to (). One reasonable way to think of is as a non-deterministic ‘application’ operation, although we suggest a better way in the concluding section 5.2 (where we also discuss in more detail the differences between frames and other known structures that ‘look’ like frames).
Subsets of will serve as denotations of sentences (Definitions 2.7 and 2.13). We can interpret both computational and logical connectives as elementary operations on sets of worlds (e.g. we interpret logical conjunction as sets intersection).
() (‘H’ for ‘Henkin’) plays a similar role to the structure of Henkin models for higher-order logic [1,12,20]. This makes our completeness results possible and is a famous issue for second- and higher-order logics. Powersets are too large; for completeness results to be possible we must cut them down — at least when we quantify. This is why in Definitions 2.7 and 2.13, the binders restrict quantification from () down to . More on this in the concluding section 5.2.
The reader familiar with modal logic can think of as a ternary ‘accessibility relation’ such that if and only if . We can also think of is as a non-deterministic ‘application’ operation, but note that frames are not applicative structures — an applicative structure would map to , whereas in the case of frames, maps to (). However, does induce an applicative structure on
Suppose , , ) is a frame. Suppose , and .
The function induces functions from () and
2.2 -terms
Fix a countably infinite set of variables. , , will range over distinct variables (we call this a permutative convention)
Define a language of -terms by:
binds in .t. For example, is bound (not free) in .. We identify terms up to -equivalence.
We write t[s] for the usual capture-avoiding substitution. For example, (.)[., and (.)[. where is a fixed but arbitrary choice of fresh variable.
Suppose , , ) is a frame. A valuation (to ) is a map from variables to sets of worlds (elements of ()). will range over valuations.
If is a variable, , and is a valuation, then write [] for the valuation mapping to () and mapping to .
Define an denotation of t inductively by:
Reduction on terms is defined in Figure 1 on page 9.
We will be particularly interested in models where the denotation of every -term is a member of . This is because Definition 2.7 interprets as a kind of quantifier over all members of . -reduction then becomes a form of universal instantiation and so requires that all possible instantiations (i.e. the denotation of any term) is a member of . More on this in Section 5.2.
-reduction and -expansion are sound, if we interpret reduction as subset inclusion:
By routine calculations from the definitions. We prove a more general result in Theorem 2.23.
It may help to give some indication of what the canonical frame used in the completeness proof for (Definition 3.5) looks like: worlds are -reduction--expansion closures of -terms t, and for each there exists some t such that is the set of worlds that contain t.
As we emphasised in Remark 2.2, our frames are not applicative structures, and the denotations of -terms are not worlds, but sets of worlds. Thus, in the canonical frame, the denotation of a -term t is not the set of its reducts (i.e. not some world in the canonical frame). Rather, the denotation of t is the set of all worlds that reduce to t.
We can identify a world with its ‘top’ term, so roughly speaking, in the canonical model a world is a term t, and an (or any denotation) is a set of all terms which reduce to some particular term s.
We suggest an intuition why our models ‘have to’ satisfy -reduction and -expansion. Both -reduction and -expansion lose information: in the case of we perform the substitution as is usual; in the case of -expansion .(t) has lost any intensional information that might reside in t. So we consider validating -expansion as an interesting feature, and not necessarily a bug.
Others have also noted good properties and justification in models for -expansion [14]. It is possible to refine the models to eliminate -expansion, at some cost in complexity; see the Conclusions.
We will fill in more details of the semantics of -terms in Section 2.4, including the role of , once we have built the logic in Section 2.3.
2.3 The logic
Define a language with sentences by:
binds in . . For example, is bound in . (). We identify sentences up to -equivalence.
We now give notions of logical entailment and denotation for . In Section 2.4 we discuss expressive power and in Sections 3 and 4 we sketch proofs of soundness and completeness.
Suppose , , ) is a frame and is a valuation to . Define ⟦⟧ the denotation of by:
Intuitions are as follows:
, , , are variables ranging over subsets of .
is classical implication.
. is a quantification over elements of . Think of . as ‘the intersection of the denotation of for all of a pre-selection of possible denotations of ’. The possible denotation of are subsets of and not elements of the ; pre-selection is done by , which identifies those denotations that ‘exist’ in the sense of being in the ranges of the quantifiers. More on this later.
□ is a notion of necessity. □ is either or depending on whether is itself or not.
□ is the modality of S5 [11].
is a notion of application; the construction in Definition 2.4 ensures that the interpretation of it is monotonic with respect to subset inclusion.4
The maps - and - behave like the box operator of the modal logic .
is the right adjoint to with respect to . It is easily verified from Definition 2.13 that ⟦⟧
is a second-order classical propositional logic enriched with the necessity modality □ from 5, and notions of application and its right adjoint (with respect to logical implication ).
When we mix all these ingredients, interesting things become expressible, as we now explore.
2.4 Expressivity
We can express truth, negation, conjunction, disjunction, if-and-only-if and existential quantification as below. We also unpack Definition 2.13 to see this denotationally:
Note that . quantifies over elements of . This is all standard, which is the point.
We can express that two predicates are equal by: □().
We unpack the denotation of and for comparison also that of (() ()):
Intuitively, holds at the worlds where and are either both true or both false, whereas represents the statement ‘ and are true of the same worlds’.
We can express that a predicate is in by E. (), read ‘ exists’. This is usually called an existence predicate [13, Ch.16].
It is not hard to verify that E has the following denotation:
We are now ready to interpret -abstraction in our logic. We also mention a notion of matching, because it comes very naturally out of the logic as a ‘dual’ to the construction for :
. . () match . . ().
Intuitively, . reads as: ‘for any , if is an argument (of the function instantiated at this world), then we get ’. As a kind of inverse to this, match . reads as: ‘for any , if is an argument, then we get ’. So match . is a kind of pattern-matching or inverse-.
is a logical quantifier, so we name it reversed by analogy with the reversed A and E of universal and existential quantification.
⟦. )⟧
The case for match . is similar.
If is not free in , then for any , ⟧.
An easy induction on .
(Substitution Lemma) For any , ⟦[]⟧ ⟧.
By induction on , we present the cases for and :
The following hold in any frame:
(-expansion) ⟦. ()⟧ (for not free in ) (matching) ⟦(match . )([])⟧
(matching) follows by a similarly routine calculation.
If is not free in and ⟦⟧ then ⟦(match . )⟧ .
If then ⟦(match . )((. ))⟧
The first two parts follow easily from Theorem 2.23. The third part follows unpacking definitions, since both are equal to . ().
Read (match . ) as returning the intersection of all such that is equivalent to []. If there are many such , e.g. when is not free in , then (match . ) for all such and so (match . ) is included in their intersection.
Write t s if t s is derivable using the axioms of Figure 1.
Our implementation of is sound in the following sense:
t s only if ⟦t s⟧ for all and , , ) such that ⟦u⟧ for all u.5
This follows (mostly) by Theorem 2.23.
3 Completeness for -reduction
In this section we show that the axiomatisation of -reduction of Figure 1 is complete for our interpretation of -terms in terms of . We do this by proving the converse of Theorem 2.27.
To complete Theorem 2.27 we must show that if t s then there is a frame and valuation where ⟦u⟧ for all u and ⟦t s⟧ (where is the translation of Definition 2.25).
Say a -term is complex if it contains term formers, i.e. is not simply a variable. The size of a -term is the number of term formers within it.
Now we can begin the construction of the desired frame. First we add infinitely many new variables , to the language . Since the language is countable we can enumerate its complex terms , and these new variables , . We describe a one-one function from terms to variables.
( where is the least number such that and is not free in nor is the value under of any for .
Thus is a one-one function that assigns a distinct ‘fresh’ variable to each complex term of the language. Thus (t) is a variable that ‘names’ t. These play the role of witness constants in the construction of the canonical frame in Theorem 3.7. The (t) also help us carry out inductions on the size of -terms, as t[(s)] is smaller than .t even if t[s] might not be.
Next we add two new axioms of reduction, denote them by :
Write t s when t s is derivable using the rules in addition to the rules of Figure 1.
If t s and neither s or t contain any of the new variables , , then t s.
By simultaneously substituting each instance of () with each instance of becomes an instance of () without affecting the rest of the derivation.
If t is a term let s t s. Thus is the closure of t under .
Define the canonical -frame , , as follows:
t is a term
For any , ,
t t is a term
Given , , and a term t. Let t t .
By induction on the size of t we show that t (i.e. t ) if and only if ⟦t⟧. t is a variable . Then (⟧ by the definition of .
t is . Then () tt. 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, ⟦t⟧. Similarly ⟦t⟧. Hence ⟦tt⟧ by Definition 2.13.
Conversely, suppose that ⟦tt⟧. Then there are , such that ⟦t⟧ and ⟦t⟧ and . By the induction hypothesis and . Then and . Furthermore, by the construction of , and hence by () . t is .s. Then ⟦(.s)⟧ . s⟧ . ⟦s⟧. Suppose .s . Suppose that , and that for some , then u for some term u. By we have that u and u for some . So and . By the construction of , .s and so s[] , i.e. s[]. By the induction hypothesis s[] ⟦s []⟧. Furthermore by Lemma 2.22 ⟦s []⟧ s⟧. But by the definition of , ⟦⟧ , and so ⟦s⟧. But so ⟦s⟧. Thus . ⟦s⟧.s)⟧. Hence, .s ⟦(.s)⟧
Conversely, suppose that .s for some u. Let be a variable not free in u or s and consider the worlds and . If s[] then u s[], so .(u) (s[]) by . But by our choice of , entails that u .(u). So u .s[], which contradicts our initial supposition that .s , therefore s[] . In other words s[]. Therefore, by the induction hypothesis, ⟦s []⟧. Since ⟦⟧ , it follows by Lemma 2.22 that ⟦s⟧. But clearly , so it follows that . ⟦s⟧. By the semantics of (.s) (i.e. . s), this means that ⟦(.s)⟧. Hence, since every is for some u, ⟦(.s)⟧.s.
We can now prove the converse of Theorem 2.27:
t s if and only if ⟦t s⟧ for all and all frames , , ) such that ⟦u⟧ for all u.6
4 The axioms, Soundness and Completeness
We can axiomatise the interpretation of given by Definition 2.13. Axioms are given in Figure 2.
Let , denote sets of sentences. Write if is derivable using the rules of Figure 2. Write when there are such that (associating to the right).
4.1 Theorems and admissible rules
The converses of (),(),(), and () are all derivable. Also derivable are:
Notice that the second sentence of the leftmost column is the Barcan formula [13, Ch.13].
If = 0 then becomes a simple necessitation rule stating that implies □. From this we get the following group of inference rules, ():
4.2 Soundness
Suppose , , ) is a frame. Then implies for any .
By induction on derivations. Assume . We consider each axiom and inference rule in turn.
To show that an axiom of the form is sound it is enough to show that
Instances of ().
The other case for () and the cases for () are similar. Instances of () and ().
The other cases are similar.
Instances of (). ⟦⟧ ⟧ ⟧ ⟦⟧ etc. Instances of (□)˙. We must show that ⟦□()⟧ ⟦⟧ ⟦⟧. This is trivial if ⟦⟧ , so we may assume that ⟦⟧
4.3 Completeness
Say that a set of sentences is consistent if .
We will show that given a consistent set of sentences we can construct a frame and a valuation such that .
A maximal set is a consistent set such that
(1) or for any ,
(2) for every sentence there is some variable such that (see Definition 2.17), and
(3) if . then [], E for some variable symbol .
The second requirement on maximality ensures that every sentence is ‘named’ by some atomic variable. The third requirement is the more familiar condition that every existential quantifier have a ‘Henkin witness’.
If consistent then there exists a maximal set such that .
Add two infinite collections of new propositional variable symbols , , , to , then enumerate all sentences , and describe two one-one functions , from predicates to variables:
( where is the least number such that and is not free in nor in nor is the value under of any .
(. where is the least number such that and is not free in nor in nor is the value under of any . . . We also write (. ) as .
We now construct , ,. . . as follows (using the enumeration , above, or a new one):
If is inconsistent then , otherwise .
Note that if . Let . By construction . We must prove is maximal: is consistent: Suppose is inconsistent, then there are such that . Suppose the that do not occur in are:
and
First simultaneously substitute () with . We get that where each is either in or is or is . [] (where [(]). Let be . [] E() where is latest in the enumeration of all sentences. We may assume that . Since we have by () that
and
but by our choice of it follows by the quantifier axioms that . . So . We may conclude from this that is derivable where each () is either of the form or is in . But this is impossible by the consistency of .
For every , either or : By the construction, either or is added to some . By the consistency of , it is also deductively closed.
By the construction of , for every sentence , there is some variable such that .
If . then for some , . ([] E) and so [], E.
Thus is indeed maximal.
If is a maximal set then is maximal and □ implies .
Define the canonical frame , , :
For any , , & implies .
It follows by that .
Given , , ) and a sentence . Let .
Let be the canonical frame, and let ( for any (sentential) variable . Then for any sentence , .
By induction on . is for some variable . Then (⟧ by the definition of . is . Suppose that . If
Conversely, suppose that . Then by () and . By the induction hypothesis, and the maximality of , we may conclude that
For the converse case suppose that for all . Then since contains all maximal consistent sets containing □ it follows that □. So by
Conversely, suppose that . . Then by the maximality of , . and so [] E for some . By the induction hypothesis and Lemma 2.22 we have that
For the converse case suppose that , we must show that there are , such that
The case where is is similar to that for and uses a lemma similar to Lemma 4.12.
If and , then there are two maximal sets , such that
(1) ,
(2) for every ,
(3) □ implies for any .
Enumerate all sentences , and construct two sequences , , and , , :
If is not of the form . then:
If is of the form . then:
Note that and if . Let and .
By induction on . If = 0 then since it follows by () and () that . Assume that ()() but ()() . First we must show that
By (), () and the consistency of if ()() and ()() then
So by () and () (())(). But this entails that ()() which is contrary to our assumption. So the lemma holds if is not of the form . . Suppose is of the form . . We must show that:
implies that
Given , we need only show that
implies that
If (. )() then by (), . (. )() .8 But since is maximal and every negated universal quantification has a witness:
But then (. [] E)() (for some ). So we can conclude that ()() implies that ()() . Analogous reasoning shows that this in turn implies that ()()
, are consistent:
Suppose is inconsistent, then there are such that . The must all be in some , but as ()() this implies by () that . This is impossible since is consistent. We may conclude analogously that is not inconsistent.
For any , either or :
This follows from the fact that every is a , and so either it or its negation is added to . Similarly, or for any .
. implies [], E for some :
. is a and so is added to , but . , [], E for some .9 Similarly for . So and are maximal, now we verify that they satisfy the conditions of the lemma.
(1) and : By choice of , we have that and , so by () and the maximality of and it follows that and .
(2) for every , . Choosing some suitable large , we have that and and the result follows by (), () and the fact that
(3) If □ then □□ and so, since , □. Now, if □ or □ then, by (1) and (2), (□) or (□) .
But □, so by Theorem 4.2 this implies that (□□) or (□□) . This is impossible since and are consistent. So □ and by
If is consistent then for some frame and valuation .
We have shown that can be extended to a maximal set which is in the canonical frame . Then by Theorem 4.11, implies that
If for all frames , then .
If then is consistent, so there is a frame such that ⟦⟧. By the semantics of negation it follows that ⟦⟧ .
We can use this result together with Definition 4.1 to simplify Theorem 3.8.
t s if and only if Eu u is a -term t s
It is a further issue whether Corollory 4.15 holds if Et t is a -term is replaced with E is a sentence, or even E is a closed sentence. A result equivalent to the fact that the corollory does not hold for the assumptions Eu u is a closed -term was shown by Plotkin in [18].
5 Conclusion
5.1 Negation and the Liar
How does our logic resolve the paradoxes that affected Church’s original system? We can extend (Definition 2.25) to translate (t) to either (t) or (. )t . The first case corresponds to negation as a term-former in -term syntax; the second case corresponds to treating negation as a constant-symbol.
In the first case, let be short for . (). (). Then we may use Theorem 2.27 and Corollary 4.14 to conclude that E(u) u is a -term . So just as with Church’s system we get a sentence that implies its own negation. Since ⟦⟧ ⟦⟧ there is only one possible interpretation of : the empty set.
In the second case similar reasoning applies, but more interpretations of are available. This is because (. )t may receive a different interpretation from t , even if we assume E(u) for all terms u. The reason for this is that ⟦. ⟧ and so contains only those that relate, by , members of to their complements. So although has a complement in (), there may be no to serve in the extension of ⟦. ⟧.
For example, if is a frame where ⟦⟧ then ⟦. ⟧ implies and so for any (as is monotonic with respect to ). So ⟦. ⟧ implies for all . So for such a frame , ⟦(. )⟧ ⟧ for any !
What moral can we draw from this? The negations of -terms can be interpreted perfectly naturally in our models. Paradoxes are averted because they may translate to impossible structural properties on the frames. Our models might help design other extensions of the -calculus, by considering how these extensions behave when interpreted in the models.
5.2 Related work
Multiplicative conjunction. with its connective (Definition 2.12) looks like a (classical) logic with a multiplicative conjunction , as in linear logic or bunched implications [8,17]. Multiplicative conjunction does not have contraction, so that for example is not equivalent to .
However is not a species of multiplicative conjunction. This is because multiplicative conjunction is usually taken to be associative and commutative, whereas is neither; it models application, and we do not usually want () to equal (), or (()) to equal (())().10
Phase spaces. On a related point, a frame based on a set with its function from Definition 2.1 looks like a phase space [9]. Indeed the denotation for in Definition 2.7 uses the same idea as the denotation of multiplicative implication (see for example [9, Section 2.1.1]).
However is unlike a phase space in one very important respect: does not make into a commutative monoid because it maps to (), and not to . This is also, as we have mentioned, why is not an applicative structure.
An interesting interpretation of our models. The ‘application operation’ returns not worlds but sets of worlds. In Section 2.1 we have already suggested that we can read as a ternary Kripke accessability relation, or as a non-deterministic application operation. We would now like to suggest another reading, which we have found useful.
Think of worlds as objects, programs, and/or data. What happens when we apply one object to another (e.g. a rock to a nut; a puncher to some tape; a program to an input; a predicate to a datum)? On the one hand, we obtain an output (a nut that is broken; strip of perforated tape; a return value; a truth-value). Yet, on its own, an output is meaningless. What makes the execution of some action a computation is not the raw output, but the concept that this output signifies. That is, we apply to not to obtain some , but to obtain some meaning that signifies. A raw output like ‘42’ tells us nothing; it is only significant relative to the meaning we give it.
The output of a computation, rather than a mere action, is a concept.
As is standard, we can interpret concepts extensionally as sets of data. So, when maps to () we can read this as follows: takes two objects and applies one to the other to obtain a concept.
By this reading, when we write .t or . , quantifies over concepts — not over data. Data is certainly there, and resides in , but when we compute on this returns us to the world of concepts. It is certainly possible to envisage frames in which is always a singleton — but this is just a very special case (and our completeness proofs do not generate such frames).
The fact that maps to () is a key point of the semantics in this paper. It turns out that this is sufficient to unify logic and computation, as we have seen.
Relevance logic. The notion of a function from to () does appear in the form of a ternary relation on , when giving denotations to relevant implication in relevance logic [5], and to implication in other provability and substructural logics such as independence logic [22]. For example, the clause for in Definition 2.13 is just like the clause for relevant implication in [5, 3.7, p.69].
However, these logics impose extra structure on ; see for example conditions (1) to (4) in [5, 3.7, p.68]. In the notation of this paper, for relevance logic and other substructural logics models a form of logical conjunction and has structural properties like associativity and commutativity. In our frames models function application, which does not have these structural properties.
and Henkin models for higher-order logic. Another feature of frames is the set (). We mentioned in Remark 2.3 that we use to restrict quantification and ‘cut down the size’ of powersets so as to obtain completeness. This idea is standard from Henkin semantics for higher-order logics.
Here, two classes of frame are particularly interesting: full frames in which () (which we return to below), and faithful frames in which the denotation of every possible sentence is in (see [20, Section 4.3]). Full frames are simple, and may be represented as a pair full , ), but they inherit an overwhelming richness of structure from the full powerset. Henkin models are simpler ‘first order’ [20, Corollary 3.6] — and therefore completely axiomatisable — approximations to the full models.
Henkin semantics for higher-order logic are actually unsound without the assumption of faithfulness. We do not impose a general condition that models must be faithful because we built the models in the general case without committing to one specific logic. Once we fix a logic, conditions analogous to faithfulness begin to appear. See for example Theorems 2.27 and 3.8, and Corollary 4.15.
Investigating the properties of full models is possible further work.
5.3 Summary, and further work
We have presented models in which logic and computation have equal standing. They combine, among other things, the expressive power of untyped -calculus and quantificational logic, in a single package. This has allowed us to give interesting answers to two specific questions:
Q. What is the negation of a -term? A. Its sets complement.
Q. What logical connective corresponds to functional () abstraction? A. from Definition 2.19.
There are many questions to which we do not have answers.
The logic is very expressive; interesting things can be expressed other than the -calculus, including encodings of first-order logic and simple types, and also less standard constructs. We note in particular matching (Definition 2.19) as a ‘dual’ to . What other programming constructs do the semantics and the logic invite?
We can take inspiration from modal logic, and note how different conditions on accessibility in Kripke models match up with different systems of model logic [13]. It is very interesting to imagine that conditions on and might match up with systems of -reduction and equality.
Can we tweak the frames so that Theorem 2.27 becomes provable for a reduction relation that does not include , or perhaps does include its converse (yes, but there is no space here for details). -calculus embeds in , so can a sequent system be given for extending the sequent system for -reduction of [6]?
Note that logic-programming and the Curry-Howard correspondence both combine logic and computation, where computation resides in proof-search and proof-normalisation respectively.
Where does our combination of logic and computation fit into this picture, if at all?
We can only speculate on applications of all this.
Models can be computationally very useful. For instance, we may falsify a predicate by building a model that does not satisfy it. Our models might have something specific to offer here, because they are fairly elementary to construct and the tie-in to the languages and is very tight, with completeness results for arbitrary theories (see Definition 4.1 and Corollary 4.14).
We have already touched on possible applications to language design; we might use the models and the logic to design new language constructs. We note in passing that the models have a built-in notion of location, given by reading as a ‘world’. It is not entirely implausible that this might be useful to give semantics to languages with subtle constructs reflecting that not all computation takes place on a single thread. To illustrate what we have in mind, consider a simple ‘if. . . then. . . else’ -term which is such that reduces to [s] if , and to [s] otherwise. But ‘where’ should be checked? Should it be checked at the world where the function resides, where the argument resides, or where the result resides? Translations into our logic reflect these possibilities:
Note that may be free in .
We conclude the paper with a hypothesis. Consider the full frames where () and using the translation of Definition 2.25 consider the relation defined such that t s when ⟦t s⟧ for any valuation on any full frame. Our hypothesis is this: there are t and s such that t s but ts; furthermore, t s is ‘true’ in the sense that t intuitively does compute to s. In other words, we hypothesise that the intuitive concept of computation is captured by the full, just like our intuitive concept of natural number is captured by the standard model . We suggest that -calculi and axiomatisations of computation are actually first order implementations of .
References
1. Christoph Benzmüller, Chad E. Brown, and Michael Kohlhase. Higher-order semantics and extensionality. Journal of Symbolic Logic, 69:1027–1088, 2004.
2. Wil Dekkers, Martin Bunder, and Henk Barendregt. Completeness of the propositions-as-types interpretation of intuitionistic logic into illative combinatory logic. Journal of Symbolic Logic, 3:869–890, 1998.
3. Wil Dekkers, Martin Bunder, and Henk Barendregt. Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus. Archive für Mathematische Logik, 37:327–341, 1998.
4. Gilles Dowek, Thrse Hardin, and Claude Kirchner. Theorem proving modulo. Journal of Automated Reasoning, 31(1):33–72, September 2003.
5. J. Michael Dunn and Greg Restall. Relevance logic. In Dov M. Gabbay, editor, Handbook of Philosophical Logic, volume 6, pages 1–136. Kluwer Academic Publishers, second edition, 2002.
6. Michael Gabbay and Murdoch J. Gabbay. Term sequent logic. In Proceedings of the 17th International Workshop on Functional and (Constraint) Logic Programming (WFLP 2008), volume 246 of Electronic Notes in Theoretical Computer Science, pages 87–106, August 2009.
7. Benjamin Werner and Gilles Dowek. Arithmetic as a theory modulo. In Proceedings of RTA, pages 423–437, 2005.
8. Jean-Yves Girard. Linear logic. Theoretical Computer Science, 50:1–102, 1987.
9. Jean-Yves Girard. Linear logic: its syntax and semantics. In Proceedings of the workshop on Advances in linear logic, pages 1–42, New York, 1995. Cambridge University Press.
10. Jean-Yves Girard, Paul Taylor, and Yves Lafont. Proofs and types. Cambridge University Press, 1989.
11. Robert Goldblatt. Logics of Time and Computation. Number 7 in CSLI Lecture Notes. Center for the Study of Language and Information, 2. edition, 1992.
12. Leon Henkin. Completeness in the theory of types. Journal of Symbolic Logic, 15:81–91, 1950.
13. George E. Hughes and Maxwell J. Cresswell. A New Introduction to Modal Logic. Routledge, 1996.
14. C. Barry Jay and Neil Ghani. The virtues of eta-expansion. Journal of Functional Programming, 5(2):135–154, April 1995.
15. S. C. Kleene and J. B. Rosser. The inconsistency of certain formal logics. Annals of Mathematics, 36(3), 1935.
16. Robert K. Meyer, Martin W. Bunder, and Lawrence Powers. Implementing the ‘fool’s model’ of combinatory logic. Journal of Automated Reasoning, 7(4):597–630, 1991.
17. Peter O’Hearn and David Pym. The logic of bunched implications. Bulletin of Symbolic Logic, 5(2):215–244, 1999.
18. Gordon D. Plotkin. The lambda-calculus is omega-incomplete. Journal of Symbolic Logic, 39(2):313–317, 1974.
19. Peter Selinger. Order-incompleteness and finite lambda reduction models. Theoretical Computer Science, 309(1):43–63, 2003.
20. Stewart Shapiro. Foundations without foundationalism: a case for second-order logic. Number 17 in Oxford logic guides. Oxford University Press, 2000.
21. Johan van Benthem. Higher-order logic. In Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 189–244. Kluwer, 2001.
22. Albert Visser. An overview of interpretability logic. In Mathematical Logic, Proceedings of the 1988 Heyting Conference, pages 307–359. Plenum Press, 1997.
Notes
The authors are grateful to the anonymous referees for their comments ↩
Supported by British Academy grant PDF/2006/509, IFCoLog Hilbert-Bernays Project, and grant RYC-2006-002131 at the Polytechnic University of Madrid. ↩
3 Historically, Church wanted to base maths on the notion of function as opposed to a notion of set. The -calculus was invented as a foundation for logic, not a foundation for computation. [15] proved that this foundation was logically inconsistent. ↩
4 That is, ⟦⟧
5 In other words, if ⟦E(u )⟧ for all terms u. ↩
6 In other words, if ⟦E(u )⟧ for all terms u. ↩
7 E is short for . □(). The axioms for 5 (),( ) and (5) entail that . □( ) □. □(). So, by the case for □, E iff E for any , . ↩
8 As we may assume that is not free in . ↩
9 We chose and to be and , to guarantee the that the construction did not begin with a sentence of the form . . ↩
10 There is some interest in non-commutative multiplicative conjunction, but this does not change the basic point. ↩