WFLP 2007
-logic with arrows
Abstract
We present an extension of first-order predicate logic with a novel predicate ‘at ’ meaning intuitively “this term is a variable symbol”. We give simple sequent proof-rules for it, we demonstrate cut-elimination for the resulting logic, and we give a semantics for which the logic is sound and complete. Because we can now make assertions about what would normally be considered an intensional property of a term (being a variable symbol) we can now express inside the logic, properties of its terms and predicates which would normally be external to the logic. We give axiomatisations in -logic, including of the lambda-calculs, and discuss what relevance this might have to logic programming.
1 Introduction
-logic extends classical First-Order Logic (FOL) with a predicate at such that if is not a variable symbol then at is contradictory. We read at as ‘ is a variable symbol’.
Let , , , and so on, be variable symbols. A simple inductive definition of substitution on abstract syntax without binding is:
Here is a term-former and we write for ‘ and are identical terms’, and for ‘ and are syntactically different terms’. For the first two clauses it is necessary to identify and as variable symbols. Of course substitution is at the heart of many major systems in computer science, including logic and functional- and logic programming.
We find that at gives just enough power to axiomatise the -calculus. We investigate the -calculus example in detail but by the end of the paper it should seem plausible that -logic has broader applications.
So what is new? Plenty of other systems can express the syntax and reductions of the -terms. To our knowledge -logic is unique in that it has this expressivity while still being a first-order (that is, -reduction is not primitive) logic such that: variables of the object theory are variables of the logic and and application are just binary term-formers taking pairs of terms and giving terms.
We would like to say that again, but we need some (informal) terminology. Say a map is a shallow embedding from one system (logic or calculus, say) to another, when variables map to variables (with a deep embedding variables map to constants) [2,29]; a map is compositional when the interpretation of an expression can be obtained directly by composing the interpretation of its parts in a syntax-directed manner. Say a system is first-order when its language of terms does not already contain -reduction.
Our application of -logic is unique in that it is to our knowledge the only compositional shallow embedding of the -calculus into a first-order logic.
The reader need not care about logic or about the -calculus. However, these are paradigmatic and they are the basis of logic and functional programming respectively. It has not previously been possible to directly (in the sense just given) map one to the other. We discuss potential applications and related work in the Conclusions.
Outline of the paper. -logic is a straightforward classical first-order logic with a Boolean semantics. We define syntax in Subsection 2.1 and sequent rules in Subsection 2.2. We axiomatise substitution in Subsection 3.1, then the untyped -calculus in Subsection 3.2, and finally we briefly consider other examples. Section 4 proves cut-elimination. Section 5 constructs a class of models and proves soundness and completeness. In the Conclusions we recap on related work, summarise, and mention possible future work. In Appendix A we build a concrete semantics for the axioms of the -calculus, incidentally proving consistency of the main axiomatisations in this paper.
The ‘’ in ‘-logic’ refers to the fact that the logic is for making statements about its variable symbols . Any resemblance to an indefinite article is coincidental.
2 -logic
2.1 Terms, directions, predicates
Assume a countably infinite set of variable symbols and some untyped language of abstract syntax trees. Write , , for arbitrary terms, built inductively from variable symbols and some countable set of term-formers of fixed arity applied to terms. Write [] for the usual substitution on terms. We may write if occurs in and otherwise. 2
We assume three directions up, down, and up and down. Where necessary, will vary over directions. Assume some countable set of predicate constant symbols , each with an arity ) which is a sentence in (thus, a possibly empty list of directions). We write : for ‘ has arity ’. When has length and some list of terms also has length , we say that list has length appropriate to . We assume distinguished predicate constants:
(i) We call : () ayquality.
(ii) We call at : () atom (‘is an atom’).
(iii) We call : () false or contradiction.
We may write as shorthand for a list of terms . Write () for a predicate constant applied to a list of terms of length appropriate to its arity.
Consider : () and a list of terms (). When for all such that , it is the case that , we say occurs up in () and we write (). Similarly when for all such that we have , write (). When for all such that we have , write ().
The intuition of is a formalisation of a reduction relation (like -reduction, for example). The intuition of () is a ‘subject reduction’ property, that if then ()[] implies ()[]. If () and then ()[] implies ()[]. Finally, if () and then ()[] if and only if ()[]. More on this in Subsection 2.3.
Intuitively, at is true when is a variable symbol. The arity () of is consistent with its intuition. at must have arity () both to avoid inconsistencies (we see this later) and to remain true to the intuition. 3
There is no interaction (yet) between directions and the terms, so () is always well-formed so long as has the right length. Predicates are generated by the grammar
is binding, nothing else is. As is usual we write as shorthand for . We equate predicates up to -equivalence; we will not talk about ‘occurring free’ or ‘occurring bound’. Consistent with our convention for terms we write for ‘ and are identical predicates up to -equivalence’.
Write for the variables occurring in , defined by: ( , (, and (. We may write for , we read it ‘ occurs in ’. Then means ‘ does not occur in ’.
Write [] for with every instance of the variable replaced by the term in the usual, capture-avoiding, manner.
2.2 Contexts and judgements
A (logical) context Γ ∆is a finite set of predicates. We write Γ when for some Γ, and Γ otherwise.
A judgement is a pair of contexts which we write Γ ∆. When a context is on the right-hand side of a judgement we call it a cocontext. The valid or derivable judgements are inductively defined by the rules in Figure 1.
In Figure 1 and are distinct variable symbols; bound by , free otherwise (note that the in (at L) must be a variable symbol). Formulae in square brackets are side-conditions whose satisfaction can be decided just by examining syntax. (at L) is not mis-typed. It eliminates a variable.
Call Γ theorem when a derivation exists concluding in Γ write Γ write Γ .
A subset of the logic is classical predicate logic, so we use standard sugar such as writing for , for () , for (), for ( ()), and in general we shall use other well-known shorthands for classical equivalences.
2.3 Comments on atoms
(at L) states that atoms exist, and (at R) states that we cannot indirectly describe them.
As can be seen from this derivation, assuming is not a variable,
(at R) is like (L); ‘if is a term then it is not a variable’. at is a theorem and can be derived by (Ax) followed by (at R). (We assume a pair term-former - -.) There is no rule Γ at ∆. It would break Lemma 4.1 (the substitution lemma) which underlies the essential case of and which formalises the intuition ‘variable symbols represent unknown terms’.
We cannot conclude at just because is a variable symbol! at in Γ represents a promise that will never be instantiated to a (non-variable) term. This explains (at R) since there the promise has manifestly been broken, and also (at L) since there is fresh from Γ and thus immune to any nasty things Γ may do to it (such as contain = 0). We may call a variable symbol of which we know at an atom.
Define , , and by:
is transitive and reflexive; and are derivable.
The latter is simply an instance of (R), the former follows by this derivation (noting that ()):
2
behaves like the transitive reflexive closure of a reduction/rewrite relation. By Theorem 2.2 below if then satisfies ‘subject reduction’; if [] then []. But then in (where does not mention ) the direction of the ‘subject reduction’ is reversed, thus we need (). Similar issues arise with itself. For example if ()[] and then ()[]. This is why has arity ().
The following two rules are derivable:
It is not hard to check, by induction on , that directions propagate pointwise but get flipped if they are in negative position (the left-hand side of an implication) and that precisely when and .
We now work by induction on . The atomic case follows immediately from (L) (L) and the definition of in the case where is atomic (see page 3). The induction cases are routine. For example suppose is (). We must show that
(i) if () and Γ ()[]∆then Γ ()[
(ii) if () and Γ ()[] ∆then Γ ()[] The antecedent of case (i) can be only if we have and , and the antecedent for case (i) can occur only if and .
For case (i) we sketch a derivation as follows:
We can now derive Γ[] ∆from the assumption that Γ ( )[] ∆and (Cut).
The relevant derivation for case (ii) is easily obtained from the derivation above by swapping with and by swapping (L) with (L).2
The standard derivation rules for equality are: 4
If we make sure that , then behaves just like an equality — at least for that . Also, -logic predicates can express a notion of equality:
Write in -logic as shorthand for .
R) and L) are derivable in -logic.
If neither () nor () we view () in terms of two variables fresh atoms and , one occurring exclusively up in (), the other occurring exclusively down. That is, we view () as ()[] where () and (), and where (). It is then easy to verify that with one use each of ( L) and ( L) we can obtain the effect of (=LR) is easy. 2
So -logic combines elements of computation, given by , of logic, given by the evident logical apparatus, and of something quite unusual, given by at .
3 Expressivity
We are now ready to write down some axioms:
3.1 Substitution
Suppose a ternary term-former . We usually write () as . Assume a binary predicate # : () freshness. Then an -logic theory of substitution is given by the axioms in Figure 2.
We intend # to express a notion of ‘not free in’. This notation and intuition is inherited from nominal techniques [18], though the properties of # are here expressed as axioms in -logic, whereas they are built in as primitive to the nominal framework. We intend to express a notion of ‘capture-avoiding substitution for atoms’; a related nominal treatment is also available [17].
Note, in Figure 3 that # implies at . We use this for example when we omit an assumption at in a number of axioms, e.g. (comm), but we still give the name ‘’.
A remark on syntax is particularly important:
is valid syntax whether or not is a variable symbol. is just a ternary term-former. is distinct from substitution on terms []. For example [] but and furthermore is not derivable.
[] is not well-defined unless for some variable symbol . is a valid term always, but only if we have assumed at can we prove anything useful about from the axioms in Figure 2. However, assuming at of that is not a variable symbol leads to immediate contradiction by (at R). Therefore in practise we only have occasion to usefully write down terms such as .
We can now give an answer to the question “why not =?”. Assume the axioms of Figure 2, except replacing with = from Definition 2.3, which we proved in Theorem 2.4 has the properties we expect of equality. For example axiom (at) becomes (at ). Call this set of axioms . Then:
is derivable. In words: “ is inconsistent in -logic”.
Note that all the axioms of are closed and that at is derivable using the replaced version of (aa). Using (Cut) and (=L) also at at () is derivable and using (at R) we obtain at . Finally by (at L) we derive . 2
So at in -logic interacts with equality, and it seems to require it t be directed. In Appendix A we build a nontrivial model for all the axioms of Figures 2, 3 and 4. By a soundness result which we prove later in Theorem A.7, this demonstrates that any subset or weakening of these axioms is neither inconsistent nor trivial.
The axioms of Figure 3 interact to yield some further theorems of of substitution and freshness. For example, using ( R) it follows that
and then using (#aa) and we can derive that #(). Then using (# ) we can derive
so freshness is a symmetric relation when between atoms.
Axiomatisations of substitution exist though we are aware of no authoritative source. Two examples are Crabbé [10, p.2] and Salibra [23, p.6]. Crabbé assumes a function symbol which we can identify with #; Salibra gives a more algebraic axiomatisation but the domain must be a model of the -calculus so he expresses # ( is not free in ) by writing as (). Salibra’s and Crabbé’s axiomatisations are almost equivalent; the authors do not cite one another but the interested reader can note that () in Salibra corresponds to [] in Crabbé [10, Proposition 3.1]. We must remove Salibra’s axiom , which is -reduction. The first author with Mathijssen has recently investigated an axiomatisation of substitution using nominal algebra [16,17]. Nominal algebra makes more structure, such as freshness, primitive to the logic; making a formal connection with -logic is future work.
3.2 -calculus
Note (as observed of in Remark 3.3) that application and are merely term formers; is a valid term for any , but the axioms permit nothing of interest to be derived about it, unless at is also derivable.
We can add an axiom for extensionality to those of Figure 4:
There are other interesting properties we might consider investigating in future work. For example:
A unary predicate symbol □ with axiom □at #. The intuition is ‘ is closed’.
A predicate ‘the free atoms of are precisely ’ axiomatised by (#)at #.
A predicate ‘the free atoms of are at most ’ axiomatised by at #.
These are in the spirit of suggestions already make for nominal rewriting in [11, Subsection 9.2] though the technical details are very different.
The first author was instrumental in developing so-called Nominal techniques, including Nominal Logic [22,14]. These have similar applications to -logic and they have a freshness predicate #. However they are inconsistent with the axiom of choice; for example Nominal Logic is inconsistent with a unary term-former such that ()# always. It seems that we can axiomatise such an in -logic, as #. The use of helps to avoid contradictions and this might be useful in some applications of nominal techniques.
4 Cut-elimination
In this section we prove that -logic (without additional axioms and term formers for substitution) satisfies Cut-Elimination. If Γ = write Γ[] for [][]. Similarly for ∆[].
(Substitution Lemma) If Γ has a derivation Π, then Γ[] ] has a derivation Π[] that is no deeper than Π.
By induction on the depth of derivations. 5
We consider some cases:
The case of (at R). If is not a variable in Γ at ∆then [] is not a variable in Γ[] at []] so substitution instances of instances of (at R) are still instances of (at R).
The case of (at L). Suppose the sequent Γ ∆is derived from the sequent Γ at at L). Then is a variable symbol such that Γ ∆. We need to show that Γ[] ] is derivable.
By the inductive hypothesis, we have that Γ[] at [] ] is derivable, for any other variable . Choosing so that Γ it follows that the sequent Γ at ∆is derivable, and the derivation is no deeper.
By the inductive hypothesis again
is derivable. Now, was chosen so that (at )[] at . So we can use (at L) to derive Γ[] ] as required.
The rules for are non-standard but it is not hard to verify that substitution in a valid instance of a rule is still a valid instance, just as we would do for the usual equality rules. For example in the case of (L) if we have
. . . then by induction hypothesis we have:
Other cases are routine.
2
(Weakening) If Γ then Γ .
By induction on the derivation of Γ ∆. We may need to rename variables generated by (at L), or (R) to avoid clashes with variables in . For example if the derivation ends with (Ax) then the weakened conclusion is itself derivable by (Ax), if the derivation ends with (R):
where Π[] is obtained using Lemma 4.1 by replacing in Π by some atom that does not occur in Γ . We know that Π[] really is a derivation because is not free in Γ or ∆. From this we can derive Γ by an application of (R) (recall from Subsection 2.1 that we equate predicates up to -equivalence). The remaining cases follow by familiar application of the induction hypothesis. 2
(Cut) is an admissible rule in the system without it.
By induction on the rank and degree of the earliest cut, counting from the leaves of the proof down to the conclusion. The proof is standard for first-order logic with equality and uses weakening, and the substitution lemma for the essential cases. (at L) and (at R) have no essential case. Cuts are commuted in the usual way with the rules, including (at L) and (at R), to lower their rank forming essential cases where they are reduced to cuts of lower degree.
Here we use Weakening (proved above) to extend to by adding at to the premise of every sequent in . Since Γ we can rename all terms in so that does not occur at all in it, and then we can add at without invalidating any rule applications in Π. The essential (and commutation) cases for the remaining connectives are familiar, and with one exception the essential cases for are also easy.
It is worth stating explicitly the problematic commutation case for aequality. This is the case where an aequality rule applies to the cut formula itself. Suppose () and we have
then (by the other commutation cases) we can assume that the right premise of such a (Cut) where the Cut formula is atomic, is actually the conclusion of (Ax), (L), ( R) or (at R) (that is, we can assume Π is empty).
If the right premise of the (Cut) is derived by (L) or ( R), or if the predicate relevant to its derivation is in Γ or ∆(and is not ()[]). Then the conclusion of the (Cut) can be derived directly by the rule that derived Γ()[]
If the right premise of the (Cut) is derived from (Ax) so that ∆is ∆()[] then we may permute the derivation to
The twins to these, where (), is similar. 2
If Γ , where Γ and do not contain at or and where the final rule application is (at L) or (at R) to the formula at , then a (shorter) derivation can be found without this application.
By induction on the length of a cut-free derivation that Γ ∆. Suppose (at L) or (at R) follows to a derivation of length 1. Since Γ and ∆do not contain the derivation must be a single application of (Ax) or (L). In the first case the derivation must be of one of these forms:
where Γ = and ∆= ∆. This can be replaced by a single application of (Ax). The case for (L) is similar.
Now suppose the derivation is of length 1. Then the rule preceding the final application of (at L) cannot be any rule (for then Γ would contain ). Therefore the preceeding rule must be a rule. Then we permute the application of (at L) or (at R) with the FOL rule (so the at rule applies to the premises of the FOL rule). We can then apply the induction hypothesis. For example:
and the induction hypothesis applies to the derivation up to the application of (at L). 2
-logic is a conservative extension of FOL without identity.
Suppose Γ ∆, in the language of FOL without identity, is derivable in -logic. We shall argue it is also derivable in FOL. We know that Γ ∆can be derived in a cut-free derivation. If this derivation makes no use of the rules for at and then there is nothing to prove, otherwise the our argument proceeds by induction on the length of the derivation. If the final rule is a FOL rule then the result follows by induction hypothesis on its premises. Given the conditions on Γ and ∆, the only other possibility for the final rule is that it is (at L) or (at R) , in this case the result follows by Lemma 4.4. 2
5 Models of -logic
5.1 Semantic definitions and soundness
An -domain is a tuple () — we may write () if is understood
— such that:
is a poset on That is, is a transitive reflexive asymmetric binary relation on
is down-closed with respect to . That is, for any , if and then A valuation to is a function from to such that
We need some notation. Write for the set of -tuples () of elements for 1 . 0 contains just the 0-tuple (). Call a function from to continuous when
A model ⟦-⟧ extends an -domain with the following information:
For each term-former of arity a continuous function ⟦⟧ from to such that ⟦⟧() for all .
Intuitively, the result of applying the interpretation of a term-former to some arguments must never be the interpretation of a variable symbol. This reflects the intuition that at is false if is not a variable symbol.
For each predicate constant symbol of arity () other than at and , a set ⟦⟧ such that if then:
Comparing these conditions with (L) and (L) from Figure 1 we see that models , and we make this intuition precise below. We extend the model ⟦-⟧ to an interpretation of terms inductively by
as is standard.
Given a valuation and a ⟦-⟧ we define a notion of validity in the model (for the valuation) as follows:
⟦ is invalid.
⟦ is valid when ⟦⟧ is invalid or ⟦ is valid.
⟦⟧ is valid when ⟦⟧ is valid for all .
For at , ⟦()⟧ is valid when (⟦⟧ ⟦⟧)
⟦⟧ is valid when ⟦⟧
⟦at is valid when ⟦.
We write that ⟦Γ⟧ is valid when ⟦ is valid for all Γ, and we extend validity to judgements Γ is valid when either
Finally we write
⟦Γ ∆⟧ is valid when ⟦Γ for all valuations .
Lemmas 5.1 and 5.2 are technical results which are useful later:
⟦at is valid if and only if is a variable symbol and
By definition, ⟦at is valid when ⟦ and by the conditions on ⟦-⟧ and , ⟦ cannot be in if is a constant or a complex term (as no function symbol is interpreted to have values in ). 2
(i) ⟦[.
(ii) ⟦[ is valid if and only if
The first part is by an easy induction on syntax. The second part is also by an easy induction, we consider only one case:
⟦at ([ is valid if and only if ⟦[, and by part (i) this is the case if and only if ⟦.
Other cases are similar. 2
((L)) (i) If ⟦⟧ is valid then ⟦[.
(ii) If ⟦Γ[] is valid then ⟦Γ .
The first part is direct from Lemma 5.2 and the definition of ⟦⟧ . The second part is routine from the definition, using the first part. 2
Suppose that , and ( for all other . Then
(ii) ⟦ is valid iff
As an easy corollary, if Γ and ( for all other then ⟦Γ if and only if ⟦Γ .
We work by induction on for (i) and then on for (ii). We consider only two cases:
The case at . Suppose ⟦at is valid. By Lemma 5.1 is a variable symbol and
valid. The result follows.
The reverse implication is similar.
The case . We can assume is distinct from because we quotient syntax by -conversion. ⟦⟧ is valid when ⟦⟧ for all . The result follows by inductive hypothesis.2
((R)) If ⟦Γ and Γ then ⟦Γ .
Fix . We now reason by cases:
Fix some Γ. By Lemma 5.4
Fix some is valid then by Lemma 5.4 also ⟦Γ is valid.
Suppose ⟦ is valid for all Γ and suppose ⟦ is not valid for all Then ⟦⟧ is valid. By Lemma 5.4
((at R),(at L)) (i) If ⟦Γ at is valid and is not a variable symbol then ⟦Γ is valid.
(ii) If ⟦Γ at is valid and
(i) By Lemma 5.1 ⟦at is not valid on any valuation . The result then follows from the definition of validity.
(ii) Since ⟦ it follows that ⟦at is valid. By definition, either ⟦ is invalid for some Γ or ⟦ is valid for some ∆. Again by definition, ⟦Γ .
2
(Soundness) Suppose ⟦-⟧ is a model. Then if Γ is derivable then ⟦Γ is valid.
We work by induction on the depth of derivations.
Most cases are immediate from the definitions (we have sketched the reasoning in what we consider the more complex cases in lemmas above). Only rule (at L) is not straightforward.
The case of (L). By part (ii) of Lemma 5.3.
The case of (R). By Lemma 5.5.
The case of (at R). By part (i) of Lemma 5.1.
The case of (at L). Suppose Γ at ∆is derivable where Γ ∆. Let be such that ⟦⟧. By Lemma 4.1 for [] it follows that Γ at derivable, and the derivation is no deeper. By inductive hypothesis ⟦Γ at is valid. The result now follows by part (ii) of Lemma 5.6.2
5.2 Prime theories and completeness
Let range over (possibly infinite) sets of formulae; call a theory. Call inconsistent when there exists some (finite) Γ such that Γ is derivable. Otherwise call consistent. Call maximal when:
is consistent.
If Γ and Γ then . We call deductively closed.
For all , or .
If [] for all then .
at for at least one .
If is maximal then if and only if [] for all . Also if and only if [] for some .
By easy calculations using the definition of maximal set. 2
If Γ is a consistent and Γ then Γ at is consistent.
We suppose Γ at and we prove a contradiction. By assumption Γ; it is not hard to extend the derivation of Γ at to a derivation of Γ at . We combine this using (Cut) with the following derivation
to produce a derivation of Γ . This contradicts our assumption that Γ is consistent. 2
If Γ is finite and consistent then there exists a maximal theory such that Γ .
Since Γ is finite there are infinitely many variable symbols that do not appear in Γ. The language is countable so we enumerate its predicates We now construct a sequence , , . . . as follows:
at for some such that Γ.
Suppose is inconsistent. Then .
Suppose is consistent and is not of the form for any . Then .
Suppose is consistent and is of the form for some . Then [] for some .
Note that if . Write . By construction Γ . If we can prove that is maximal then we are done:
is consistent: is consistent by Lemma 5.9. By construction is consistent if is, so is consistent for all 0.
If is inconsistent then it has a finite inconsistent subset. This must be contained in some and this is impossible. The result follows.
is deductively closed: Suppose that . for some and by construction .
For every , either or : for some . By construction or .
If [] for all then . Suppose that . Then . Now for some . Therefore [] for some and so [] .
at for at least one : By construction of .2
For a given set of sentences , define
If is maximal then if and only .
Suppose that . Since it follows that and so if we have that and so . Conversely suppose . Now if then and so by the maximality of and the transitivity of (see Theorem 2.1), and so . Thus, . 2
If Γ is consistent then there exists some model ⟦-⟧ and some valuation on ⟦-⟧ such that ⟦Γ⟧ is valid.
Suppose Γ is consistent. Extend it using the construction in the proof of Lemma 5.10 to a maximal set such that Γ .
Define an -domain by:
at
The arity at : () and the rules for ayquality entail that if at and are derivable then so is at . It follows that is down-closed. Therefore is an -domain.
We specify a model ⟦-⟧ and valuation by stipulating that:
(i) If has arity and . Then ⟦⟧(
(ii) ⟦(
(iii) (.
We must verify the properties required of a model.
If ⟦⟧(
() we have that
and so () () . Therefore
which entails that ()(). Thus if then ⟦⟧(
By construction maps atoms to elements of . By construction there exists an such that at . Also by construction at . Therefore there exists an such that
Suppose the arity of is () and suppose . By definition and by Lemma 5.11 . There are now three cases: The case that : If (
We prove by induction that ⟦
The case .
The case (). Then
We prove by induction that ⟦⟧ is valid if and only if :
The case that at . ⟦at is valid when ⟦, which happens when , and this happens when at .
The case that . ⟦⟧ is valid when ⟦⟧
The case that () for some at . ⟦()⟧ is valid when (⟦⟧
Other cases are straightforward. For example:
We conclude that ⟦⟧ is valid for every , and it follows that ⟦Γ⟧ is valid.2
(Completeness) If ⟦Γ is valid in all models then Γ
-logic is classical. Therefore Γ ∆when Γ : . It suffices to show that if Γ : is consistent then there is a model ⟦-⟧ and valuation such that ⟦⟧ is valid for all Γ : . This follows by Lemma 5.12. 2
6 Conclusions
-logic is a classical first-order logic with a two-valued model theory, one of many [5,13]. The twist to the story is that at can identify variables, and accordingly truth-values are given also to open predicates.
In the semantics, predicates are sets of (tuples of) elements of the domain. at is a unary predicate. Atoms are simply a subset of the underlying domain; those in ⟦ at ⟧ which is the interpretation of at in the domain. Elements of ⟦ at ⟧ are special; they cannot be in the image of the interpretation of any term-formers.
We believe that -logic could provide a logical semantics for isvar in PROLOG, as used for example in practical programming in CIAO PROLOG [9]. isvar is a non-logical predicate which is true when its argument has not yet been unified with a concrete value — that is, when it is a variable. This is used exactly as we have used it in this paper, to master shallow embeddings into CIAO of languages with variables. at and isvar appear to be compatible but problems arise interpreting PROLOG conjunction, which ceases to be commutative in the presence of isvar. This is a known issue which we are attempting to solve by using a modified translation of CIAO conjunction which is will be the topic of a future paper.
A previous paper considered a variant of -logic with equality [15]. There, in order to axiomatise substitution we had to introduce a (in the authors’ opinion) ad hoc notion which we called ‘essentially a term’. In this paper we take a different path and introduce a directed equality — the arrow in the title of this paper. This solves the issues we encountered in [15], arguably in more elegant way which seems to benefit the resulting theory and axioms. In particular, our principal axiomatisations (of the -calculus and of substitution) are improved.
It is relevant how conveniently -logic can be implemented in a theorem-prover such as Isabelle [21]. We do not know.
gives -logic a flavour of a ‘logical theory of rewriting’. 6 Rewriting itself is traditionally intensional on the syntax of terms (we look at a term’s syntax to decide whether to rewrite), or completely abstract (we just take any relation on a set, but the only properties of its elements are the relation so elements are closed, in the sense that instantiation is absent) [3,28]. In some sense at provides just enough to give a point of contact between these two worlds and it may be possible to make this idea useful for the theory of rewriting.
How else can the -calculus (and friends) be modelled in a formal system and how does -logic relate to them?
We can use a higher-order system to begin with (build the system as an extension of a -calculus). The -calculus cannot recognise a variable symbol as such, so to use it to model the -calculus requires deep embedding which model variables by closed terms (in essence, you have to write a Turing machine).
First-order logic also cannot recognise a variable symbol. We can take a two-level hierarchy with object-level variables modelled by constants. We cannot quantify over constants so a hallmark of such approaches is an infinity of axioms, one for each constant (the -logic axiomatisations look similar, but are finite). This approach is followed for example by Cylindric Algebras [8] (which assume only finitely many variable symbols so as to obtain a finite theory), by Salibra’s Lambda Abstraction Algebras [24], and by some treatments of Structural Operational Semantics (SOS) [1], see for example Bernstein’s SOS axiomatisations of the -calculus, the lazy -calculus, and CHOCS [6].
We can do away with variables entirely, for example using Boehm trees, Scott domains, or combinators [4]. The translations are only for closed terms (hence, not compositional) and combinators may suffer exponential blow-up [7]. This is a bit off-topic for us, because we are interested not just in a ‘naked denotation’ but also in the formal system it is constructed in.
We can suppose a two-level hierarchy of variables and meta-variables and assume -reduction for the former; computation/reasoning is by instantiation of meta-variables following by reduction. One of several examples of this style is Combinatory Reduction Systems (CRS). Note that in CRS meta-variables vary over closed elements — the higher-order elements are used to feed arguments to where they are used. In -logic unknowns may be substituted for open terms. So for example # states that (whatever is) it should not depend on . This is not expressible in a CRS. Being a variable or meta-variable is an intensional property in CRS, whereas in -logic the difference is expressed by at and can be mixed with implication and the rest of the logic. Finally, in CRS -reduction is built-in. Although we certainly concentrate on substitutions and the -calculus in this paper, other theories are possible so -logic is probably more flexible.
Nominal logic [22] has a notion of atom but keeps this separate from the notion of variable; this is because nominal logic was designed for reasoning on syntax — in our terminology, reasoning on a deep embedding where there is a clear distinction between variable symbols of the object-level language, called atoms because they behave like atomic entities, and variables of the meta-level language which range over unknown elements of the domain. A shallow embedding of (for example) the -calculus in nominal logic is not possible. We also believe, but have not proved, that -logic is consistent with arbitrary choice. Nominal logic is not [22], so -logic may have some interesting technical advantages.
-logic may be closer to Miller and Tiu’s logic of Generic Judgements (GJ) [20], where ‘being a variable symbol’ is managed by scoping for a dedicated quantifier instead of a dedicated predicate at . GJ is significantly different in being higher-order and having a ‘definitional’ equality [25] suited more to logic-programming than model theory; we suspect it is unsuited for our applications.
Kit Fine’s ‘Reasoning with arbitrary objects’ [12] axiomatises dependence between elements. Perhaps our semantics, which contain variables, may be related.
References
[1] L. Aceto, W. Fokkink, and C. Verhoef. Structural operational semantics. In Handbook of Process Algebra. Elsevier, 1999.
[2] A. Azurat and I.S.W.B. Prasetya. A survey on embedding programming logics in a theorem prover. Technical Report 7, Institute of information and computing sciences, Utrecht University, 2002.
[3] Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.
[4] H.P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, 1984.
[5] John Bell and Moshé Machover. A course in mathematical logic. North-Holland, 1977.
[6] Karen L. Bernstein. A congruence theorem for structured operational semantics of higher-order languages. In Logic in Computer Science, pages 153–164, 1998.
[7] Martin W. Bunder. Some improvements to turner’s algorithm for bracket abstraction. J. Symb. Log., 55(2):656–669, 1990.
[8] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Springer, 1981.
[9] CIAO. CIAO Prolog. www.clip.dia.fi.upm.es/Software/Ciao//.html.
[10] Marcel Crabbé. On the notion of substitution. Logic Journal of the IGPL, 12(2):111–124, 2004.
[11] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205:917–965, 2007.
[12] Kit Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.
[13] Dov Gabbay and Franz Günthner, editors. Handbook of philosophical logic. Number 166 in Synthese Library. D.Reidel Publishing company, 1986.
[14] Murdoch J. Gabbay and J. Cheney. A sequent calculus for nominal logic. In Proc. 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 139–148. IEEE Computer Society, 2004.
[15] Murdoch J. Gabbay and Michael J. Gabbay. a-logic. In We Will Show Them: Essays in Honour of Dov Gabbay, volume 1. College Publications, 2005.
[16] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding substitution as a nominal algebra. In ICTAC’2006: 3rd International Colloquium on Theoretical Aspects of Computing, volume 4281 of LNCS, pages 198–212, 2006.
[17] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding substitution as a nominal algebra. Formal Aspects of Computing, 2007. To appear.
[18] Murdoch J. Gabbay and Andrew M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2002.
[19] Narciso Martí-Oliet and José Meseguer. Rewriting logic: roadmap and bibliography. Theor. Comput. Sci., 285(2):121–154, 2002.
[20] Dale Miller and Alwen Tiu. A proof theory for generic judgments: An extended abstract. In Proc. of LICS 2003, pages 118–127. IEEE, 2003.
[21] Larry Paulson. The Isabelle reference manual. Cambridge University Computer Laboratory, 2001.
[22] Andrew M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186(2):165–193, 2003.
[23] Antonino Salibra. On the algebraic models of lambda calculus. Theoretical Computer Science, 249(1):197–240, 2000.
[24] Antonino Salibra. Lambda calculus: models and theories. In AMiLP-2003, number 21 in TWLT Proceedings, pages 39–54, 2003.
[25] Peter Schroeder-Heister. Definitional reflection and the completion. In Extensions of Logic Programming, volume 798 of Springer Lecture Notes in Artificial Intelligence, pages 333–347, 1993.
[26] Mark R. Shinwell and Andrew M. Pitts. On a monadic semantics for freshness. Theoretical Computer Science, 342(1):28–55, 2005.
[27] Joseph E. Stoy. Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. MIT Press, Cambridge, MA, USA, 1977.
[28] Vincent van Oostrom. Confluence for Abstract and Higher-Order Rewriting. PhD thesis, Vrije Universiteit, Amsterdam, 1994.
[29] Martin Wildmoser and Tobias Nipkow. Certifying machine code safety: Shallow versus deep embedding. In TPHOLs, volume 3223 of LNCS, pages 305–320. Springer, 2004.
A Consistency and nontriviality of the axiomatisation of the -calculus
We build a model of the theory for the untyped -calculus from Subsection 3.2. This illustrates an easy but non-trivial example of an -logic model and it suffices to prove consistency of the axioms in Figures 2, 3 and 4.
Let Λ be the set of untyped -terms, generated by the grammar
Here ranges over variables of -logic; it is convenient to identify these with variables of the -calculus. We define -conversion and -reduction on -terms set as usual [4]. Write fv() for the free variables of . For example fv().
Write [] for the capture-avoiding substitution of for in , making some fixed but arbitrary choice about how to rename variable symbols to avoid capture. For example ()[ for some fixed but arbitrary choice of .
Note that our use of [] for capture-avoiding substitution in -terms is distinct from the (syntactic) substitution action [] of Subsection 2.1: [] is an operation on the -terms which we are about to use to construct a concrete model for the theory of Figures 2 and 4; [] is an operation on -logic terms.
Write for the relation generated by an -conversion followed by a -reduction followed by -conversion, and call this -reduction. 7
Write for the transitive reflexive closure of . That is, when either or there exists some chain such that
Write for the relational image of under . That is,
All of these definitions are standard [4].
Let ¿ be some symbol not in Λ and read it as error. We define an -domain by:
when or
We define a valuation by (
⟦⟧() if
⟦⟧ ) if and .
⟦⟧([]) if ,
() ⟦#⟧ when
, , and in the language of are term-formers with arities 2, 2, and 3 respectively. -logic permits ‘silly terms’ such as (). Standard methods are available to exclude them; for instance a sorting system for -logic could be developed. On the other hand, we could even ‘embrace the silliness’, allow such terms, and investigate their properties. All of this is future work; for our purposes we need only include ¿ an error value, and in Definition A.2 we let the denotation of a silly term such as () be ¿. For more future work, it may be possible to identify ¿ with the of Scott domain models of the -calculus [27]. However, this requires a more sophisticated construction, perhaps involving nominal domain theory [26].
We now sketch a proof that we have indeed constructed a model of . Lemmas A.3 and A.4 are technical lemmas needed for Corollary A.5.
Suppose and suppose . Then:
If for some then for some (that is, for some such that ).
If
Suppose and suppose . Note that ¿ . By definition of we know . It follows that ¿ and so for some . It follows that and therefore that .
Suppose
If then precisely one of the following holds:
We work by cases on possible forms for :
The case . It is a fact of -calculus reduction that if for some then for any other .
The case ¿. Immediate.2
⟦⟧ , ⟦⟧ , and ⟦⟧ are continuous.
It suffices to verify that:
If and then ⟦⟧() ⟦⟧().
If and then ⟦⟧() ⟦⟧().
If , , and then ⟦⟧() ⟦⟧().
We will consider only the first of these calculations, for ; the calculations for and are similar. Suppose that and .
By Lemma A.4 either or
The case that ¿. Then ⟦⟧(¿. We assumed . By construction of it follows that ¿. Therefore ⟦⟧(¿ and the result follows.
The case that . Then ⟦⟧(¿. We assumed and so (since the definition of unpacks to ) . Therefore ⟦⟧(¿ and the result follows.
The case that
is an -domain. is a valuation. ⟦-⟧ is a model.
We verify all the required properties in turn. is an -domain:
is a partial order on : This is also a fact.
is down-closed: Suppose and . By definition of we know that
is a valuation: By construction maps to . Also,
⟦-⟧ is a model:
is a term-former with arity 2. By construction ⟦⟧ is a function from 2 to . It is a fact of -calculus reduction that if then is not a variable symbol. It follows that ⟦⟧() always. We proved in Corollary A.5 that ⟦⟧ is continuous.
The cases of application and substitution are similar.
Recall that # : (). Suppose that , , and () ⟦#⟧. We must show that () ⟦#⟧.
By construction
The construction above yields a model of .
We verify that the axioms given in in turn. We consider only two cases.
We must show that if () ⟦#⟧ then
for all such that it is the case that ⟦⟧(
Suppose that () ⟦#⟧. By definition
follows. (comm)
Suppose that , () ⟦#⟧ and () ⟦#⟧. We must show that
We may suppose that , and . It follows that and that fv() . It also follows that fv() and, since is just a variable, this entails that .
But it is a fact of the -calculus that if and fv() that
The other axioms in Figures 2, 3 and 4 can be verified similarly. 2
Notes
1 We acknowledge the support of British Academy grant PDF/2006/509 and grant RYC-2006-002131 at the Polytechnic University of Madrid.
2 If the language of terms admits binding then when occurs free in .
3 For example, if models a literal reduction relation then we can interpret as expressing that some complex term reduces to an atom . In that case we had better not allow the substitution of for in a (true) sentence such as at , for that would yield the (potentially false) sentence at .
4 A familiar alternative to (=L) is this:
5 Where the depth of a derivation is defined inductively as follows: the empty derivation has depth 0; if a derivation has depth up to the premise of any rule application, then the derivation up to the conclusion of that rule application has depth
6 To our surprise, we could find no reference in the literature for a logic-based-on a transitive reflexive not-necessarily-symmetric congruence — that is, for a logic of rewriting. We would be happy to hear of such a reference. Rewriting Logic [19] seems different, informally treating terms as formulae.
7 The first author has studied different ways these definitions can be expressed. This is not the issue for constructing the model; for our purposes it suffices to know that the relation exists.