a-logic

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

a-logic

Murdoch J. Gabbay and Michael J. Gabbay

1 Introduction

Mathematics and computer science pervasively use logics formal languages for reasoning in. One of the most common is classical First-Order Logic with equality (FOL) [Bell and Machover, 1977, Gabbay and Günthner, 1986].

For example FOL is routinely used as a foundational tool to express Zermelo-Fraenkel set theory (ZF sets) [Johnstone, 1987, Machover, 1996] and thus as a (language to express) a foundation for classical mathematics. The implication is that first-order logic is a minimal and convenient logical framework for doing, well, triangles and numbers and other mathematical objects.

But is it so good for the mathematics of computation, i.e. for computer science? Perhaps not, since it cannot express substitution as an object-level operation on its own terms. The λ-calculus [Barendregt, 1984] can and does, in the sense that we can write (λa.s)t, which β-reduces [Barendregt, 1984]:

(λa.s)t →s[a↦→t].

This is a pervasive phenomenon and theories of computation are frequently based on notions of substitution. (For this reason, some researchers refer informally to a general notion of ‘movement’, which in the examples here is implemented by substitution.)

Another example is channel communication as appears for example in the π-calculus [Milner et al., 1992]:

ab | a⟨c⟩.P →P[c↦→b].

Now note that first-order logic cannot express this directly; consider a ternary explicit substitution term-former which we write s[t↦→u]. The intuition is that if t is a variable symbol, then s[t↦→u] denotes the term obtained by replacing every instance of t in s by u.

This is ridiculous because even if t were a variable symbol, there is no way we could guarantee it would still be a variable symbol if that variable symbol is instantiated, as arises from the following consideration:

We want our logic to satisfy cut-elimination and thus we want to simplify a proof of the form

Γ ⊢P, ∆ Γ ⊢∀x. P, ∆ Γ, P[x↦→s] ⊢∆ Γ, ∀x. P ⊢∆ (Cut) Γ ⊢∆

to one without the cut. It suffices to demonstrate the Substitution Lemma:

Lemma. If Γ ⊢∆ is derivable in our logic without cut, then Γ[x↦→s] ⊢ ∆[x↦→s] is also derivable in our logic without cut, and with a no larger proof.

(— ‘no larger’ according to whatever measure is useful for making an inductive argument work given the other transformations we make on the proof while eliminating cuts. The substitution action on Γ and ∆is element-wise. See Lemma 5.)

Likewise it is not possible to hypothesise binary term-formers λ and ◦ with axioms in first-order logic such that if a is a variable symbol then (λa.s) ◦u = s[a↦→u].

Yet there is a need to express the λ-calculus in logic, for any of several reasons:

• The untyped λ-calculus is a foundational system to rival ZF sets. Why should we be able to write down axioms for one in FOL, but not for the other?

• FOL has a well-developed and tractable meta-theory.

• Functions are useful.

Theoretical computer science as a field has reacted to these issues by working in higher-order frameworks, but this commits to certain very particular choices, e.g. committing to β-reduction as the only notion of substitution (‘movement’), a particular discipline of types (which may prevent us from quantifying over all elements of the universe), and it may be expensive for the meta-theory (models are more complex, Interpolation need not hold, compactness fails, and so on).

So a first-order logic which can express explicit substitution as a term-former as described above, offers the prospect of combining the power of a functional theory, with the simplicity and flexibility of a first-order system.

In this paper we define a-logic, investigate its relation to First-Order Logic, prove some meta-theory for the logic as a formal system, and then axiomatise the λ-calculus as a finite first-order theory. Finally, we consider axiomatisations of other theories.

The ‘a’ in ‘a-logic’ refers to the fact that the logic is for making statements about its variable symbols a, b, c. Any resemblance to a pronoun is coincidental.

2 a-logic

2.1 Terms, directions, predicates

We assume a countably infinite set x, y, z, a, b, n of (term) variable symbols, and a finite set of term-formers f to each of which is associated an arity ar(f) which is a nonnegative number which may be 0.1 If ar(f) = 0 we may call f a constant.

Terms are inductively generated as follows:

s, t ::= x | f(s, . . . , s)

where f has ar(f) arguments. If f is a constant we may write f() as just f.

For reasons which will become clear later, we arbitrarily call some of the f inevitably term-formers. (For future reference, λ and application will be inevitably term-formers, but explicit substitution is not. We come back to this later.)

We write s ≡t for ‘s and t are syntactically identical terms’. We write s ≢t for ‘s and t are syntactically different terms’.

Assume some set of predicate constant symbols p, q, r . . . ∈P, each with its arity ar(p), ar(q), ar(r),. . . which is a nonnegative number which may be 0.

We assume distinguished predicate constants:

1. We call at the predicate is an atom (or atom for short), of arity 1.

2. We call ⊥ false or contradiction of arity 0.

3. We call = equality.

Write p(t1, . . . , tn) for a predicate constant applied to a list of terms of length n where we shall always assume n = ar(p). Call this a primitive proposition.

Propositions are generated by the grammar

P ::= p(ts) | P ⊃P | ∀x. P.

∀x. P is binding, nothing else is. Consistent with our convention for terms we write P ≡Q for ‘P and Q are identical predicates’ (up to α-equivalence).

Write V P for the variables occurring in P, defined by: Vp(t1, . . . , tn) = ⋃ V ti, V(P ⊃Q) = V P ∪V Q, and V(∀n. P) = V P\{n}.

Here, if S and T are sets then S \ T is set of elements of S which are not elements of T. In particular V P\{n} denotes the set of elements of V P not equal to n. We use this notation without comment henceforth.

We may write x ∈P for x ∈V P, we read it ‘x occurs in P’. Then x ∉P means ‘x does not occur in P’. (We strictly equate predicates up to α-equivalence, we will not talk about ‘occurring free’ or ‘occurring bound’.) Write P[x↦→s] for P with every instance of the variable x replaced by s in the usual, capture-avoiding, manner.

Later, when we develop our notions of derivability and model, if we happen to know that at holds of a term, then we may choose a name like a, b, or n to represent it.

2.2 Contexts and judgements

A (logical) context Γ, ∆is a set of propositions. We way write V {P, Q} for V P ∪V Q, and V Γ for the natural meaning as a union; we may even mix, as in V (Γ, P, Γ′). We shall write x ∉ Γ, P, Γ′ for x ∉V (Γ, P, Γ′), and so on.

A judgment 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 judgments are inductively defined by the following derivation rules (notation is defined below):

(Ax) Γ, P ⊢P, ∆ (⊥L) Γ, ⊥⊢∆ Γ, P ⊢Q, ∆ (⊃R) Γ ⊢P ⊃Q, ∆ Γ ⊢P, ∆ Γ, Q ⊢∆ (⊃L) Γ, P ⊃Q ⊢∆ Γ ⊢P, ∆ (∀R)(∗) Γ ⊢∀x. P, ∆ Γ, P[x↦→s] ⊢∆ (∀L) Γ, ∀x. P ⊢∆ Γ ⊢P, ∆ Γ, P ⊢Q, ∆ (Cut) Γ ⊢Q, ∆ (s inevitably a term) (at L) Γ, at s ⊢∆ Γ, at a ⊢∆ (Fresh)(∗) Γ ⊢∆ (=R) Γ ⊢t = t, ∆ Γ, P[x↦→s′] ⊢∆ (=L) Γ, s′= s, P[x↦→s] ⊢∆

Here x and a are variables; bound by ∀, free otherwise. Conditions in brackets are side-conditions whose validity can be decided just by examining syntax.

In particular the bracketed asterisks annotating (∀R) and (Fresh) indicate that the rules are subject to the side-condition x ∉ Γ, ∆or a ∉ Γ, ∆. (Fresh) is not mis-typed. It eliminates a variable. Comma, as in ‘Γ, P’, indicates set union. Note that this means that for example in (⊃ R), it may still be that P ∈ Γ or indeed that P ⊃Q ∈∆.

We say that s is inevitably a term when it is of the form f(t1, . . . , tn) and f is an inevitable term-former. An example of a term which is not inevitably a term, is a term without any top-level term-former at all, namely y a variable symbol.

(Later on, we will encounter explicit substitution s⟨t↦→u⟩ which is not inevitably a term, and λ-abstraction and application which are.)

Say a judgement Γ ⊢∆is a theorem when a derivation exists concluding in Γ ⊢ ∆. Note that ∆may be empty in which case we write Γ ⊢; we may call Γ inconsistent when Γ ⊢ is derivable.

A subset of the logic is classical propositional logic, so we use standard sugar such as writing ¬P for P⊃⊥, P∨Q for (¬P)⊃Q, ∃x. P for ¬(∀x. ¬P), P∧Q for ¬(P⊃(¬Q)), and in general we shall use other well-known shorthands for classical equivalences. We may also use ‘derivation rules’ such as (∃L) and (¬L), to represent several rules of the core system appropriately pasted together.

2.3 The first-order theory corresponding to a-logic

We now set up some notation. Uses of this notation will be scattered throughout the text; all definitions relevant to theories are here.

Let FOL be classical first-order logic with equality. Say a triple of

• a finite set of theory term-formers, which may already be in the base logic (write a typical term-former f),

• a finite set of theory atomic predicate symbols, which may already be in the base logic (write a typical atomic predicate symbol φ),

• a possibly infinite set of theory sentences or axioms, which are predicates in the language of the base logic extended with any of the new term-formers and atomic predicate symbols,

is a theory. If the set of sentences is finite, call it a finite theory, otherwise call it an infinite theory.

When a theory has no, or a trivial, signature, we may equate it with the set of its axioms and name it using calligraphic letters, for example T . Otherwise, we tend to give theories names in sans-serif font, for example Q or lambda. Theories named in sans-serif font will always be finite.

As a matter of notation we may write Unc+Cle for the theory obtained by taking the unions of the theories’ term-formers, predicate symbols, and sentences. We write ¬Unc for the theory obtained by negating all the theory sentences. Finally, if both Unc and Cle are finite, we may identify them with the predicate which is the logical conjunction of their senteces, and write things like Unc ⊃ Cle or Unc ⊃¬Cle.

The rest of this subsection proves that a-logic corresponds to the following FOL theory alogic in a formal sense we make precise in a moment:

• There are some term-formers (e.g. f with arity n).

• There is one unary predicate symbol at .

• There is an axiom

∃a. at a (folfresh)

• For each inevitable term-former f of arity n, there is an axiom:

∀x1, . . . , xn. ¬at (f(x1, . . . , xn)) (folat Lf)

Here is the characteristic property of inevitable term-formers:

Lemma 1

alogic, at a, f(s1, . . . , sn) = a is inconsistent.

(Formally: alogic, at a, f(s1, . . . , sn)=a ⊢ .)

Proof

We use (folat Lf). ■

That is, ‘in a-logic, terms which are inevitably terms, cannot be atoms’.

The intuition of an atom is a term which the logic identifies as being a variable symbol; the only way this can happen is if at t is derivable. A term is inevitably a term when the logic always identifies it as not being a variable symbol (and this happens when ¬at t is derivable).

Lemma 2

Γ ⊢∆ in a-logic if and only if alogic, Γ ⊢∆ in FOL (with its signature extended with at and so on; we shall not mention this again).

Proof

We can translate from a derivation in a-logic to one in FOL with alogic by transforming instances of (Fresh) and (at L) as shown (where for simplicity we suppose f is unary):

at a, ∃a. at a, Γ ⊢∆(∃L) (a ∉Γ, ∆)∃a. at a, Γ ⊢∆
(Ax)at f(s), ∀x. ¬at f(x), Γ ⊢∆, at f(s)(¬L)¬at f(s), at f(s), ∀x. ¬at f(x), Γ ⊢∆(∀L)at f(s), ∀x. ¬at f(x), Γ ⊢∆

■

So roughly speaking: (Fresh) just says that

an atom exists,

and (at L) says that

they cannot be directly described by (some) term-formers.

alogic is parametarised over the choice of which f are inevitable terms-formers, and we will always make that choice explicit.

Corollary 3

a-logic is consistent (⊢ is not derivable).

Proof

FOL is sound and complete with respect to a standard notion of model [van Dalen, 1985, Machover, 1996], so Γ ⊢ ∆in a FOL theory it suffices to show that the FOL theory has a model.

This is given by a two-element set {anatom, aterm} (here anatom and aterm are merely suggestive names for two distinct elements, though in view of their uniqueness we might also call them theatom and theterm). Write [[ - ]] for the interpretation of a term or predicate.

[[ f]] is the constant map to aterm no matter what the arity of f. [[ at ]] is {anatom}. [[ = ]] = {⟨anatom, anatom⟩, ⟨aterm, aterm⟩}. Predicate constants can be interpreted arbitrarily. ■

Recall from the Introduction that we may call a variable symbol a of which we know at a an atom.

So is a-logic trivial, if it has such a simple model? Of course a model of pure FOL is the one-element set. The interest comes in provability and its properties, and in models of more complex predicates than ‘⊤’. The same holds for a-logic. What we have demonstrated is that an a-logic theory is a special case of a first-order theory, so we can be optimistic that a-logic should behave meta-theoretically very much like FOL (since that is what it is).

2.4 Comments on the rules

This is a simple logic consisting of First-Order Logic with equality, augmented with a unary predicate at with two rules (Fresh) and (at L) as usual, though instead of left- and right-introduction rules we have a left -introduction and -elimination rule.

Recall from the last section that the distinguishing feature of an ‘inevitable’ term-former f is that (at L) may be used for a term of which it is the top-level term-former, or equivalently one for which the corresponding alogic has an axiom (folat Lf). The need for this becomes clear in §4.1. But why do we say ‘inevitably a term’?

One of the important basic lemmas of First-Order Logic is the Substitution Lemma (see Lemma 5 for the a-logic version):

If Γ ⊢ ∆is derivable, then so is Γ[a↦→s] ⊢∆[a↦→s].

This makes formal the idea that ‘variables stand for unknown terms’ and gives them a slightly dynamic character in the logic. Suppose at f(t1, . . . , tn) gives rise to contradiction for certain f. Then we may also obtain a contradiction from at f(t1[a↦→s], . . . , tn[a↦→s]). The property of ‘having top-level term-former f’ is invariant under substitution. Therefore, (at L) is not incompatible with the Substitution Lemma after all.

We say ‘inevitably’ because substitutions do not affect the top-level term-former. We say ‘a term’ because the property of being a variable symbol is the canonical example of a property which is not inevitable (i.e. variables get substituted; that is what they are there for!).

Accordingly, there is no (at R) rule such as

Γ ⊢ at a, ∆

if a is a variable symbol.

at ⟨a, a⟩⊢ is a theorem with a trivial proof by (at L). (We assume a pair term-former ⟨-, -⟩.)

In summary, at a in Γ represents a promise that a will never be instantiated, or at least, not to the wrong kind of term. We may call a variable symbol a of which we know at a an atom.

3 Meta-properties of a-logic

3.1 Cut-elimination

The proof-theory of a-logic is hardly more complex than that of FOL itself.

Lemma 4 (Weakening).

If Γ ⊢∆ then Γ, Γ′ ⊢∆′, ∆.

Proof

It suffices to consider the derivation rules one-by-one and check that if we weaken the conclusion of an instance with Γ′ and ∆′, then we may weaken the hypotheses in the same way, and still have an instance of the derivation rule. We shall see that we also have to remember a systematic ‘freshening’ of the variables, but this is no problem.

This is quite obvious for (Ax), (⊃ R), (⊃ L), and (⊥L), because these rules make no comment on Γ and ∆so they ‘might as well be as big as we like’.

(∀R) has a side-condition that x ∉ Γ, ∆(we say a is fresh). If we weaken context and cocontext to Γ, Γ′ and ∆, ∆′ the instance of the rule will be invalid precisely when x ∈ Γ′ or x ∈∆′.

However, we can use any fresh x in (∀R), and we simply choose some x′ not in Γ, Γ′, ∆, or ∆′ and rename x to x′ systematically from then on as we move upwards, before weakening.2

The rest of the rules are just as easy: (Fresh) has a condition similar to (∀R), which can be dealt with similarly. ■

Call a derivation cut-free when it does not use (Cut). Say it has depth n when the greatest number of deduction steps from the conclusion to an assumption is n. If S is a set of predicates write S[y↦→t] for the set obtained by applying the substitution [y↦→t] pointwise to S. We now prove the substitution lemma:

Lemma 5

If Γ ⊢∆ has a cut-free derivation of length n then Γ[y↦→t] ⊢ ∆[y↦→t] has a cut-free derivation of length at most n.

Proof

It suffices to consider the derivation rules one-by-one and check that if we apply [y↦→t] to the conclusion, we may do the same to the hypotheses, and still have an instance of the derivation rule. As for Weakening above we may need to systematically accumulate some other transformations, but they are not a problem.

Rules (Ax), (⊃ R), (⊃ L), and (⊥L) are not a problem because they are propositional and do not care what terms the predicates mention.

(∀R) is problematic — what if x ≡y so that [y↦→t] affects P in the hypotheses, and what if x ∈s and y ∈ Γ, ∆so that x ∈ Γ[y↦→t], ∆[y↦→t] (violating the side-condition)? As for weakening, these problems are solved simply by choosing a fresher x′.

In (∀L) it suffices to observe that by α-equivalence on formulae we may assume x ≢y and x ∉t so that

(∀x. P)[y↦→t] ≡∀x. (P[y↦→t]) P[x↦→s][y↦→t] ≡P[y↦→t][x↦→s[y↦→t]]

and after the substitution we still have a valid instance of (∀L) where s is replaced by s[y↦→t].

In (at L) it suffices to observe that if s is not a variable, neither is s[y↦→t]. (Fresh) is not a problem unless (‘by accident’) a ≡y; if we apply [y↦→t] naïvely then after the substitution we no longer have an instance of the rule. The answer is, as for (∀R), to rename a to some fresher a′ and then apply the substitution. ■

Lemma 6

(Fresh) followed by any other rule (∗), may be commuted to (∗) followed by (Fresh).

As a corollary, all instances of (Fresh) in a derivation may be commuted downwards to the head of the proof.

Proof

We verify that derivations may be transformed as follows:

Γ ⊢P, ∆ Γ, P, at a ⊢∆ (Fresh) Γ, P ⊢∆ (Cut) Γ ⊢∆ =⇒ Γ, at a ⊢P, ∆ Γ, at a, P ⊢∆ (Cut) Γ, at a ⊢∆ (Fresh) Γ ⊢∆

This is easy, we just need Weakening to add at a to the derivation in the top left. Similarly:

Γ, P[x↦→s], at b ⊢∆(Fresh)Γ, P[x↦→s] ⊢∆(∀L)Γ, ∀x. s ⊢∆=⇒Γ, at b, P[x↦→s] ⊢∆(∀L)Γ, at b, ∀x. P ⊢∆(Fresh)Γ ⊢∆

This is easy, since if b ∉ Γ, P[x↦→s], ∆then certainly b ∉ Γ, ∀x. P, ∆.

Γ, at a ⊢P, ∆ (Fresh) Γ ⊢P, ∆ (∀R) Γ ⊢∀y. P, ∆ =⇒ Γ, at a ⊢P, ∆ (∀R) Γ, at a ⊢∀y. P, ∆ (Fresh) Γ ⊢∀y. P, ∆

By the side-condition on (Fresh) we can assume a ≢y and a ∉ Γ, ∆, P. By the side-condition on (∀R) we also know y ∉ Γ, ∆. Therefore, y ∉ Γ, ∆, at a, P and a ∉ Γ, ∆, ∀y. P. Therefore in the transformed derivation above, the instances of (Fresh) and (∀R) are still valid.

We consider only one more case:

Γ, at a, P[x↦→s′] ⊢∆ (Fresh) Γ, P[x↦→s′] ⊢∆ (=L) Γ, P[x↦→s], s′= s ⊢∆ =⇒ Γ, at a, P[x↦→s′] ⊢∆ (=L) Γ, at a, s′= s, P[x↦→s] ⊢∆ (Fresh) Γ, s′= s, P[x↦→s] ⊢∆

We need only verify that a ∉s. If this is not the case, we rename a in the derivation of Γ, at a, P[x↦→s′] ⊢ ∆first. ■

Theorem 7 (Cut elimination).

If Γ ⊢∆ has a derivation then it has a cut-free derivation.

Proof

We work by induction on the pair of numbers (cuts, depth) where cuts is the number of instances of (Cut) in the derivation, and depth is its depth — lexicographically ordered. The essential cases are just as for first-order logic (since at has no right rule, there can be no essential case for it); we use the previous lemmas in standard ways [van Dalen, 1985, Machover, 1996].

The commutation cases are also as for first-order logic except we worry about commuting (Fresh) from between a left- and a right-introduction. It suffices to verify that (Fresh) may be commuted down through all the other rules. This follows by the previous lemma. ■

3.2 Interpolation

The following result is known as Craig’s Interpolation Theorem for First-Order Logic ([D.M.Gabbay, 2005, Theorem 5.65, page 169], [G.Boolos, 1989, Section 23]):

Theorem 8

In classical first-order logic with equality, if P ⊃Q is provable then there is some I mentioning only predicate symbols and term-formers mentioned in both P and Q, and possibly also =, such that P ⊃I and I ⊃Q are provable.

We call I the the interpolant and say it is in the common sublanguage of P and Q. Because = may appear in the interpolant even if it does not occur in P and Q, we call such an atomic predicate a logical symbol.

An easy corollary is:

Theorem 9

In classical a-logic with equality, if P ⊃Q then there is an interpolant I, such that P ⊃I and I ⊃Q are provable; = and at are logical symbols.

More specifically, if P or Q mention at (but not necessarily both) it may still be that I mentions at , but if neither P nor Q mention at then the interpolant will not.

Proof

In §2.3 we characterised a-logic as a theory alogic in FOL. Therefore P ⊃Q is equivalent to P ∧ alogic ⊃Q and P ⊃ (alogic ⊃Q). By Interpolation, interpolants exist.

We now observe that alogic mentions at and an unspecified collection of term-formers. By partitioning these axioms judiciously between the left- and right-hand sides of the implication to minimise the term-formers which appear on both sides, we can obtain the result of the theorem. ■

3.3 Models

Since alogic is a FOL theory and FOL has Soundness and Completeness, to give a theory of models it suffices to recall the theory of models for FOL, which is first-order classical logic with equality.

Here we give a very brief recap: A model Q of a theory Q is:

• An underlying set |Q|, which we just write Q.

• For each n-ary function-symbol f, a function [[ f]] : Qn → Q.

• For each atomic predicate symbol φ, a function [[ φ]] : Qn →Bool, where Bool = {True, False} is a two-element set representing truth values. We may treat [[ φ]] as a set, writing [[ φ]] ⊆ Qn.

(Recall that we are working, for simplicity, with an unsorted logic, so there is only one underlying set to consider.)

We can either insist that equality be identity in the model, or treat it as just another one of the atomic predicate symbols, in which case the model should also satisfy

If (p, q) ∈[[ = ]] and ⟨p1, . . . , p, . . . , pn⟩∈[[ φ ]] , then ⟨p1, . . . , q, . . . , pn⟩∈ [[ φ ]] .

We use this latter approach in this paper.

The interpretation of atomic predicates can be extended to predicates in a standard way. Write σ for functions from variable symbols to elements of Q, and call these valuations.

• [[ ⊥]] σ is false.

• [[ P ⊃Q]] σ is true when if [[ Q]] σ is true, then [[ P]] σ is true.

• [[ ∀x. P]] σ is true when [[ P]] ([x↦→p]σ) is true, for every p ∈ Q. Here [x↦→p]σ represents the valuation which acts like σ, only x maps to p.

Say [[ Q ]] ⊨P when for all valuations, [[ P]] σ is true. Say Γ ⊨[[ Q ]] ∆when [[ Q ]] ⊨⋀i Gi ⊃⋁j Dj, where Γ = {G1, . . .} and ∆= {D1, . . .} and we interpret empty conjunction as ⊤≡⊥⊃⊥ and empty disjunction as ⊥.

Then a standard theorem is Soundness and Completeness for FOL:

Theorem 10

Γ ⊢∆ if and only if Γ ⊨[[ Q ]] ∆ for all models [[ Q ]] .

4 Substitution

We now give a theory of substitution.

4.1 Explicit substitution

Let sub have a ternary term-former sub which we sugar to s⟨u↦→t⟩. Being a ternary term-former, s⟨u↦→t⟩ is valid syntax whether or not u is a variable symbol — however, our axioms allow us to prove nothing about s⟨u↦→t⟩ unless at u is known.

There are no new predicate symbols. As a matter of notation, write

a#u is sugar for at a ∧∀x. u⟨a↦→x⟩= u.

Intuitively we can read a#u as ‘a is fresh for u’ or ‘a does not occur (free) in u’. Note that this is not a syntactic judgement; for example a does not occur in the syntax of x, but if we know nothing about x, intuitively a#x may or may not hold.

Then, sentences are:

at a ⊃u⟨a↦→a⟩= u at a ⊃a⟨a↦→x⟩= x at a ∧at b ⊃(a≠ b ⇔a#b) at a ∧b#u ⊃u⟨a↦→b⟩⟨b↦→y⟩= u⟨a↦→y⟩ at a ∧a#x ⊃a#u⟨a↦→x⟩ at b ∧a#b ∧a#y ⊃u⟨a↦→x⟩⟨b↦→y⟩= u⟨b↦→y⟩⟨a↦→x⟨b↦→y⟩⟩

(Note that a#u implies at a.) Here a, b, x, y, z, and u are all variable symbols which are universally quantified. For example, the first axiom is in fact ∀a, u. at a ⊃u⟨a↦→a⟩= u.

We do not introduce a sentence

∀x, y, z. ¬at (x⟨y↦→z⟩) (folat L)

nor the corresponding deduction rule (at L) for sub. This is to avoid the following derivation being valid:

(at L) at a⟨a↦→a⟩⊢ (the first axiom) at a ⊢ (Fresh) ⊢
Lemma 11

sub+alogic is consistent.

Proof

As in Lemma 2 it suffices to give a FOL model, call it N. We recall the model from Lemma 2, but here N is (intuitively) all atoms with no terms.

The underlying set is N where N is the natural numbers 0, 1, . . .. [[ = ]] = ⋃n∈N{⟨n, n⟩} is the usual graph of equality on the underlying set. [[ at ]] = N.

Clearly [[ ∃a. at a]] is ‘true’; choose [[ a ]] = 1.

Write p, q, r for arbitrary elements of our model (we tend to do the same later when we consider other models). By abuse of notation, henceforth we write p⟨q↦→r⟩ instead of [[ sub]] (p, q, r), and at p instead of p ∈ [[ at ]] , and so on, without comment. We also use this kind of shorthand later.

[[ sub]] is defined by:

n⟨n↦→m⟩= m n⟨n′↦→m⟩= n (n′ ≠ n)

It remains to verify that the derivation rules are valid of these interpretations and that they make the interpretations of the axioms valid. This is easy:

• We check in the definition above that p⟨n↦→n⟩= p for all p and all n (at p holds always).

• We similarly check that n⟨n↦→p⟩= p always.

• We check that n#m holds precisely when n ≠ m.

• The other equalities follow by checking of cases.

■

We can easily extend the model N with ‘terms’; for example, introduce an element aterm such that aterm ∉ at , aterm⟨n↦→p⟩= aterm, and p⟨aterm↦→q⟩= p. It is not hard to check that the axioms are still satisfied.

To see more complex models, the reader can either verify that ‘ordinary syntax’ with ‘ordinary substitution’ (e.g. the syntax of first-order logic with capture-avoiding substitution of terms for variables) is also a model, or they can wait for later when we use models of ECA to construct models of lambda (see below for terminology).

We conclude with some simple lemmas:

Lemma 12

1. a#u if and only if for some b#u, u⟨a↦→b⟩= u. (So to test freshness, it suffices to try freshening the variable and checking for equality.)

2. If at a and b#x and b#y, then b#x⟨a↦→y⟩. (A useful case.)

Proof

1. Suppose a#u. Then u⟨a↦→b⟩= u by definition. Conversely suppose u⟨a↦→b⟩ for some b#u. Then by an axiom, u⟨a↦→b⟩⟨b↦→y⟩= u⟨a↦→y⟩ for any y.

2. By an axiom x⟨a↦→y⟩= x⟨a↦→b⟩⟨b↦→y⟩. Then b#x⟨a↦→b⟩⟨b↦→y⟩ follows by another axiom.

■

Lemma 13

sub + alogic, at a, at b ⊬a ≠ b. (Two atoms with different names are not necessarily distinct.)

Proof

Consider a valuation on a and b in the model above, making them equal. The result follows by soundness and completeness of FOL. ■

Lemma 14

Any model of sub must have at least two elements.

Proof

By (Fresh), the underlying set is non-empty, since it contains an element a such that at a. Now suppose this is the only element. It is easy to check that a#a, which contradicts the right-to-left direction of the third axiom of sub (at a ∧ at b ∧a#b ⊃a ≠ b). ■

∃x, y. x ≠ y alone is sufficient, in the presence of the other axioms, to give the right-to-left direction of the third axiom of sub.

The reader familiar with Nominal Techniques [Gabbay and Pitts, 2001] might expect an axiom along the lines of

(Fresh#) ∀x. ∃a. a#x

(‘no x can mention all atoms’), or even something with the meaning of ‘no x can mention more than finitely many atoms’ [Gabbay and Pitts, 2001, (Fresh), page 8] (call this finite support). This would certainly be useful.

The problem is, (Fresh#) only allows us to choose a fresh for x, not necessarily x1, . . . , xn for arbitrarily large n. Unless the language of terms has something like pairing — e.g. a binary term-former of which we can deduce a#(x, y) ⇔a#x ∧a#y — then the only option is to introduce an axiom scheme over all n. Rather than do that (and make our theories infinite), we wait for a more specific theory (lambda for example) and then add made-to-measure axioms with the effect of (Fresh#). As for insisting on finite support, we do not bother; it would make some things easier, but for our purposes we have enough.

4.2 ‘Provably closed’

Meta-level substitution and explicit substitution are quite different. For example x[y↦→z] ≡x but x⟨y↦→z⟩= x is not derivable in general. This fact is clearly brought out by the following definition, which will be useful in a moment:

In sub, write

•s for ∀a. at a ⊃a#s

where a ∉s. Read •s as ‘s is (provably) closed’. By abuse of terminology, we may use ‘s is open’ to mean ‘s is not provably closed’.

It is important to note that •s does not at all imply that the term s is actually closed (viewed as syntax). For example, •x ⊢•x but x is a variable. Similarly, if •x then ∀a. at a ⊃•(a⟨a↦→x⟩), but a⟨a↦→x⟩ clearly has free variables a and x.

However, in an underlying model •p indicates precisely the notion of closure given by ‘is invariant under the explicit substitution’. For example recalling N the model of sub used in the proof of Lemma 11, it is easy to prove

Lemma 15

N has no closed elements. Recalling also the extension of N with aterm, the element aterm is closed.

Proof

By routine concrete calculations which we omit. ■

Note also that there are no binders in terms, in the sense of a term-former which quotients the syntax of terms by α-equivalence. The only binder anywhere in this paper, is ∀ which is inherited from FOL and exists at the level of predicates (and the few times we mention ‘real’ λ-abstraction if we want to build a ‘real’ function).

(Recall from the end of §2.2 that when Γ entails the empty set we write Γ ⊢ and say Γ is inconsistent.)

So if a term can contain variable symbols and still be ‘closed’, what does ‘closed’ mean? Here are two examples of things we can derive:

Lemma 16

In sub. . .

• at a, •a ⊢ is derivable (atoms cannot be closed).

• at a, •x ⊢•a⟨a↦→x⟩ is derivable (if x is closed then, well, x is closed).

Proof

In the following derivation, we omit sub.

at a, a#a ⊢ at a ⊢at a(∀L), (⊃L)∀b. at b ⊃b#a, at a ⊢

at a, a#a ⊢⊥ follows easily from sub.

For the second part, we can use either

at a ⊃a⟨a↦→x⟩= x or at a ∧a#x ⊃a#u⟨a↦→x⟩

— we omit the derivations. ■

Note that atermi from the model used in Lemma 11 are closed, and they the only closed element of the model (all the other elements are atoms).

Say a model of sub is non-trivial when there exist p and q such that •p and •q and p ≠ q. The model used in Lemma 11 demonstrates that sub has at least one nontrivial model. Using Soundness and Completeness of FOL we have:

Lemma 17

sub + alogic, •x, •y ⊬x = y.

So let us take stock. We have constructed a logic with a theory sub which ‘internalises the meta-level’ enough to express substitution as an explicit term-former. We can now exploit this to directly and finitely axiomatise the untyped λ-calculus as a first-order theory, and explore in what sense that axiomatisation is correct.

5 λ-calculus

5.1 The theory lambda

Assume sub, the theory of explicit substitution above.

We now construct lambda, an axiomatisation of the extensional λ-calculus. The signature has binary term-formers application and lambda, write them st and λs.t, and axioms:

(α) ∀a, b, x, y. at a ∧b#x ⊃λa.x = λb.x⟨a↦→b⟩(β) ∀a, x, y. at a ∧•y ⊃(λa.x)y = x⟨a↦→y⟩(ξ) ∀x, y. •x ∧•y ⊃(∀z. •z ⊃xz = yz) ⊃x = y(σλ) ∀a, b, x, y. at b ∧a#y ⊃(λa.x)⟨b↦→y⟩= λa.(x⟨b↦→y⟩)(σapp) ∀a, x, y, z. at a ⊃(xy)⟨a↦→z⟩= (x⟨a↦→z⟩)(y⟨a↦→z⟩)(#app) ∀x, y. ∃a. a#x ∧a#y ∧∀b. (b#axy ⇔(b#a ∧b#x ∧b#y))

We explore in what precise sense this can be said to be an ‘axiomatisation of the extensional λ-calculus’ in the rest of this section.

Note that lambda is built on top of sub. So let us suppose that sub is ‘substitution’ and that a#x is ‘a does not occur (free) in x’ — whatever those sentences mean. In that case we can say:

• (α) is α-conversion.

• (β) is β-conversion. The condition that it be applied to a provably closed term means that a term like (λa.a)b (for a and b atoms) will not reduce; as if it were waiting for b to ‘become’ something, which it can do if an explicit substitution arrives from a surrounding term. Compare this with [Fernández et al., 2005], where a reduction strategy is considered which only allows reductions for closed terms; in their case the motivation is efficient reduction.

• (ξ) is a form of extensionality, restricted to the world of provably closed terms.

• (σλ) and (σapp) are the usual rules for moving a substitution inside a term (the action of substitution on atoms is specified in sub).

• (#app) says ‘there are infinitely many atoms and no x can mention them all’. See Lemma 18.

Interesting points about this axiomatisation are:

• λ is a binary term-former — just like application. The special status of the first argument is mediated through at .

• This is a finitely axiomatised FOL theory; quantification over all elements is ∀x.blah; quantification over all atoms (i.e. object-level unknowns) is ∀x.at x ⊃blah.

• The underlying domain need not be an inductive type. It is some set with interpretations for the signature, that is, λ, explicit substitution, and at .

• The theory includes an explicit term-former for substitution, substitution is not emulated by applying a λ-abstraction to a term.

• The condition •y in (β), and similar conditions in (ξ), give terms a two-level structure: provably closed terms are the ‘real’ λ-terms, because we can β-reduce on them.

This gives open terms something of a flavour of an internal meta-language for talking about terms.

• Accordingly, we can think intuitively as follows:

1. Unknown λ-terms are variables.

2. Unknown λ-term variables are atoms (terms of which we can prove at ).

3. Known λ-terms (the ‘real’ λ-terms) are provably closed (terms of which we can prove •).

• Explicit substitution acts on u whether or not u is provably closed (and so is part of the internal meta-language).

• The axioms of lambda represent just one choice, out of many possible systems.

For example, rules

(β′) ∀a, x, y. at a ∧¬at y ⊃(λa.x)y = x⟨a↦→y⟩(ξ′) ∀x, y. ¬at x ∧¬at y ⊃(∀z. •z ⊃xz = yz) ⊃x = y

are quite reasonable; they just equate more terms of the internal meta-language.

• The following axiom is wrong and inconsistent:

(βFALSE) ∀a, x, y. at a ⊃(λa.x)y = x⟨a↦→y⟩

Using it, it is not hard to show that at a ⊢a = (λa.a)a. However, ¬at ((λa.a)a) (because the top-level term-former is application), so at a ⊢⊥. Using (Fresh) it is easy to derive ⊢, i.e. the system becomes inconsistent and has no models.

Write lambda as shorthand for lambda + sub + alogic. We conclude this subsection with a question, whose answer also throws light on the significance of (#app):

How many atoms are there, and how fresh can they be?

Lemma 18

• lambda ⊢∃a, b. at a ∧ at b ∧a#b. (‘There exist two distinct atoms’.)

• lambda ⊢∃a, b, c. at a ∧ at b ∧ at c ∧a#b ∧b#c ∧a#c. (‘There exist three distinct atoms’.)

• ‘There exist n distinct atoms’ (we do not write out the predicate in full).

• lambda ⊢∃a. a#x1 ∧· · · ∧a#xn. (‘for any x1 to xn, there is an a fresh for them all’.)

Proof

• By (Fresh) there exists some atom a. We then use (#app), taking x = a = y. (We cannot use (#app) directly, since without (Fresh) the empty model is a model of lambda.)

• We use (#app) again, taking x = ba = y and using the previous part.

• We just consider the case n = 4. We use (#app), taking x = cba = y.

• For the case n = 1 we use (#app) with x = x1 = y, to obtain a#x1. For n = 2 we use (#app) again with x = ax1 and y = x2 to obtain b#a, x1, x2. For n = 3 we use (#app) with x = bx1x2 and y = x3 to obtain some c#b, x1, x2, x3, and so on.

■

5.2 Moving from theories of lambda to λ-models

We now show how provably closed terms in lambda correspond to elements of models of the extensional λ-calculus in a more traditional sense (thus giving our axioms some justification).

Let ECA (Extensional Combinatory Algebras) be the FOL theory with signature:

• A binary term-former application (we write it infix and invisible, as the name suggests).

• Constants (0-ary term-formers) s and k. Write i for sk.

— and axioms:

∀x, y. kxy = x sxyz = (xy)(xz) ∀x, y. (∀z. xz = yz) ⊃x = y.

(We do not need extensionality, but the extensional theory is marginally easier to work with.)

An extensional λ-model is a FOL model of ECA. This is a traditional notion of model for the λ-calculus [Salibra, 2003b, Selinger, 1997].

We now show how to build a λ-model out of a theory in lambda+sub+alogic. Take any model Q of lambda+sub+alogic.

Let Λ be the set of all provably closed elements of (the underlying set of) Q. That is, Λ = {p ∈ Q | •p}.

Theorem 19

Λ is an extensional λ-model.

Proof

We know by Lemma 18 that infinitely many atoms exist in Q, so pick three different ones a, b, c (different here means that a#b, b#c, and a#c are all derivable). Set s ≡λabc.(ab)(ac) and k ≡λab.a. Here we abuse notation and use the same notation for elements which are atoms in the model, as for terms of which we can prove at — we do this without comment henceforth.

We check that:

• •λabc.(ab)(ac) and •λab.a are derivable.

• λabc.(ab)(ac) = λa′b′c′.(a′b′)(a′c′) is derivable, for any other choice of three different atoms.

• Likewise λab.a = λa′b′.a′ is derivable.

The first part is from Lemma 20 which follows. The second two parts are by using (α), and the other axioms.

We must verify that spqr = (pq)(pr). We verify this using (β) and the rules of sub. Similarly, we can verify kpq = p.

Finally we must verify that with these definitions,

∀p, q. (∀r. pr = qr) ⊃p = q.

This follows directly from (ξ). ■

Lemma 20

Assume lambda + sub + alogic is in the context. Then:

at a ⊢a#λa.x and b#x, at a ⊢b#λa.x.
Proof

• Fix some u and use Lemma 18 to choose b#a, x, u. By axioms, λa.x = λb.(x⟨a↦→b⟩) and

(λa.x)⟨a↦→u⟩= λb.(x⟨a↦→b⟩⟨a↦→u⟩) = λb.(x⟨a↦→b⟩) = λa.x.

• Suppose at a and b#x. If b = a we use the previous part. Otherwise, b#a by an axiom, we use the last part of Lemma 18 to obtain a fresh c and reason as follows:

(λa.x)⟨b↦→u⟩= (λc.(x⟨a↦→c⟩))⟨b↦→u⟩= λc.(x⟨a↦→c⟩⟨b↦→u⟩) = λc.(x⟨a↦→c⟩) = λa.x

For the last step, we use the second part of Lemma 12.

■

So informally described, we have observed that elements corresponding to s and k live inside a model of lambda and are provably closed. Application is already in lambda, so we can just take the provably closed elements and quotient by provable equality to get an extensional λ-model.

5.3 Moving back

In the previous subsection we showed how to obtain a model of ECA from a model of lambda. Now we consider going back.

Given a model Q of ECA there are two issues with obtaining a model of lambda:

• How to add atoms and explicit substitution.

• How to interpret λ.

These problems can be handled in a relatively standard way using a suitable quotient of a free term model over the elements of Q. Extend Q formally with a disjoint countably infinite set a, b ∈A and close formally under application. We obtain a language L generated by the grammar

l ::= (a ∈A) | (q ∈Q) | l · l.

We may drop · and the bracket; · associates to the left.

Quotient L by

(s)l1l2l3 = (l1l3)(l2l3), (k)l1l3 = l1, and (p)(q) = (pq)

provided that l3 does not mention any atoms.

(The final rule says that if p and q are from Q then (p) applied to (q) in L is related to the result of applying p to q in Q, injected into L.)

Call this quotiented set Q′. We shall be lax about the difference between l, an element of L, and its equivalence class, an element of Q′.

Here is a simple result:

Lemma 21

1. If l does not mention atoms, then l = (p) for some p ∈ Q.

2. p ≠ q in Q if and only if (p) ≠ (q) in Q′.

3. As a corollary of the last part, (s) ≠ (k) in Q′.

Proof

For the first part, we notice that in the absence of atoms we may use the final rule above to concatenate the elements of l.

For the second part, we notice that the rules for deducing l = l′ simulate the equalities satisfied in Q anyway. ■

Consider A as a subset of Q′ by mapping a to (a). We may be lax and write a when we mean (a), and more generally we may write p for (p). So for example s in the equation below should be (s).

Let [[ at ]] = A ⊆ Q′. Define an interpretation of explicit substitution as follows:

• l⟨a↦→u⟩ is (the equivalence class of) the string obtained by formally replacing every a in l by u.

It is not hard to show that this is well-defined, i.e. that:

(sl1l2l3)⟨a↦→u⟩= ((l1l2)(l1l3))⟨a↦→u⟩ (kl1l2)⟨a↦→u⟩= l1⟨a↦→u⟩ ((p)(q))⟨a↦→u⟩= (pq)⟨a↦→u⟩.

For example, for the last part we simply observe that both sides are equal to (pq).

• p⟨q↦→u⟩= p for q ∉A (this is just a convenient default value).

Lemma 22

• a#ll′ if and only if a#l and a#l′.

• a#(b) if a ≠ b.

• a#(a) is not the case.

Therefore, a#l if and only if a occurs in l,

As a corollary, •l if and only if l does not mention atoms, and •l if and only if l = (p) for some p ∈ Q.

Proof

• Direct from the definition of explicit substitution, observing that

(ll′)⟨a↦→l′′⟩= (l⟨a↦→l′′⟩)(l′⟨a↦→l′′⟩).

• Direct from the definition.

• Direct from the observation that a⟨a↦→(s)⟩= (s) and a⟨a↦→(k)⟩= (k), and (s) ≠ (k) by a previous part of this result.

For the last part, observe that elements of Q′ have a strict inductive structure as lists, and by induction on structure we conclude that a#l if and only if a occurs in l.

For the corollary, we use the results just proved and the first part of Lemma 21. ■

Lemma 23

Using the interpretations above, Q′ is a model of sub.

Proof

We just verify that the axioms of sub are valid for the interpretations given. This is quite long and uses the previous parts of this lemma and Lemma 21, but it is also routine, since the interpretation of substition really is substitution. ■

We now interpret λ in a standard way for combinatory algebra:

• λa.a = skk.

• λa.l = kl if a#l.

• Otherwise, λa.(ll′) = s(λa.l)(λa.l′).

See [Barendregt, 1984, Definition 7.1.5] or [Selinger, 1997, Subsection 2.2.2] for a futher treatment.

Lemma 24

a#λa.l, and a#λb.l if a#l.

Proof

By a simple induction on the structure of l. For example, a#skk so a#λa.a. ■

We must now verify that this interpretation satisfies the axioms of lambda:

Theorem 25

With the interpretations above, Q′ is a model of alogic + sub + lambda. That is:

1. λa.l = λb.(l⟨a↦→b⟩) if b#l.

2. (λa.l)l′ = l⟨a↦→l′⟩ if •l′.

3. If •l and •l′ then if for all l′′ such that •l′′, ll′′ = l′l′′, then l = l′.

4. (λa.l)⟨b↦→m⟩= λa.(l⟨b↦→m⟩) if a#m.

5. (ll′)⟨b↦→m⟩= (l⟨b↦→m⟩)(l′⟨b↦→m⟩).

6. For any l and l′, there exists some a#l, l′ such that for all b, b#all′ if and only if b#a, l, l′.

Here we use a#l, l′ as shorthand for a#l and a#l′, and similarly for b#a, l, l′.

Proof

1. If a#l then a does not occur in l so l⟨a↦→b⟩ is l with b replaced by a. The result follows by induction on l.

2. Suppose l′ mentions no atoms. We work by induction on l.

• (λa.a)l′ = skkl′ = (kl′)(kl′) = l′ (since l′ mentions no atoms; we do not mention this again).

• If a#l then (λa.l)l′ = kll′ = l′.

• (λa.l1l2)l′ = ((λa.l1)l′)((λa.l2)l′). We now use the inductive hypothesis.

■

Recall that we may write lambda when we mean alogic+sub+lambda. So, lambda really does axiomatise the λ-calculus. We conclude with two more simple observations:

Say a model of lambda is non-trivial when there exist two distinct provably closed elements.

Theorem 26

lambda has a non-trivial model.

Proof

ECA has non-trivial models by standard results of the λ-calculus [Barendregt, 1984]. We use the theorem above and Lemma 21. ■

Theorem 27

If we travel from Q an extensional λ-model to Q′ a model of lambda and back again as described above, we return to Q.

Proof

By construction Q maps into the model of lambda, with p↦→(p). By Lemma 22 this map surjects onto the provably closed elements, and by Lemma 21 the map is an injection. The result follows, since mapping back from Q′ to Q is just taking closed elements. ■

The converse does not hold: if we travel from Q′ to Q and back to obtain Q′′, it need not be the case that Q′′ is identical to Q′; fewer equalities may hold in Q′′. For example, consider Q′ equal to terms up to provable equality with

lambda, ∀a, b. at a ∧at b ⊃(λa.a)b = b

(and the rest of lambda). This identity does not hold in Q′′.

We can say that “the map from Q′ to Q throws away the internal meta-language” (mentioned in §5).

So models of lambda are, in a suitably formal sense, models of the λ-calculus, of perhaps a slightly new kind, since open terms are given a direct semantics too.

6 Other theories

We now return to our example theories.

6.1 Meta-level substitution

Until now we have dealt with two notions of substitution: the meta-level substitution [b↦→t] and the object-level (explicit) substitution ⟨a↦→s⟩.

How do they interact? As follows:3

u⟨a↦→s⟩[b↦→t] ≡u[b↦→t]⟨a↦→s[b↦→t]⟩.

Note that meta-level substitution is an operation on terms, whereas the explicit substitution is a term-former with a theory of equality. This is why [b↦→t] can distribute down under ⟨a↦→s⟩, without avoiding capture. (The first author builds a λ-calculus of meta-variables based on this idea in [Gabbay, 2005].)

We can internalise this. Extend sub with a binary predicate ≤ and axioms:

at a ∧at b ∧a≤b ∧b≤a ⊃a=b at a ∧at b ∧at c ∧a≤b ∧b≤c ⊃a≤c at a ⊃a≤a.

Write a < b for a ≤b ∧a ≠ b. Modify (σλ) as follows:

(σλ)at b ∧a#b ∧a#y ∧b ≤a ⊃ u⟨a↦→x⟩⟨b↦→y⟩= s⟨b↦→y⟩⟨a↦→x⟨b↦→y⟩⟩(σλ′)at b ∧at b ∧a < b ⊃ u⟨a↦→x⟩⟨b↦→y⟩= s⟨b↦→y⟩⟨a↦→x⟨b↦→y⟩⟩

This endows a < b with the intuition ‘b is a meta-variable with respect to a’, in the sense that the characteristic of a meta-variable is that it may be replaced by any term, possibly capturing names in the term under surrounding bindings.

6.2 ‘Substitution instance of’

Return to sub as originally presented. Substitution ⟨t↦→u⟩ is not a term, only substitution applied to a term, that is s⟨t↦→u⟩, is a term (and even then, only meaningfully so if at t.

Assume term-formers for pairs and lists and use standard notations (s, t), Nil, and hd :: tl. Introduce a binary term-former · and axioms such that:

s · [] = s s · (a, u) :: tl = s⟨a↦→u⟩· tl

(here a must be an atom).

Then a list of pairs whose first elements are atoms behaves like an internal notion of substitution. It is easy to detect when a term is a substitution; let σ, σ′,. . . vary over them.

We can then write predicates such as:

1. ‘σ and σ′ are extensionally equal’:

Eq(σ, σ′) = ∀x. x · σ = x · σ′

(since a-logic is untyped, we may wish in practice to restrict equality to some subset of all terms, e.g. those not of the form σ′′).

We can then write ‘s is a substitution instance of t’ as ∃σ. s = t · σ. Similarly we can write σ ≤σ′ when ∃σ′′. Eq(σ, σ′σ′′) (where σ′σ′′ denotes list concatenation), and thus ‘σ is a (most general) unifier of s and t’, and so on.

2. The discussion above extends to predicates in a weaker sense. We can write a#P to mean ∀u. P⟨a↦→u⟩⇔P where here P⟨a↦→u⟩ is that predicate obtained by replacing every term s in P by s⟨a↦→u⟩. We can express •P as ∀a. at a ⊃a#P, and so on.

6.3 Logic Programming.

As a-logic gives at proof-rules, and can express properties of unification using explicit substitutions, it is interesting to consider logic programming in it. We give a sketch of how this might proceed. Define a-hereditarily harrop formulae by

G ::= ⊤| p(ts) | G∧G | at t | ∃x.G | ∀x.G | G∨G | D⊃G D ::= ⊤| p(ts) | D∧D | G⊃D | at t | ∀x.D

Write G and D for the sets of all G and D respectively. Say a derivation is uniform when every subderivation concluding a non-atomic goal ends in a right rule or (FreshL). Say (G, D) is a logic programming language when for any G ∈G and ∆ ⊆D, if ∆⊢G is derivable then a uniform derivation exists.

Theorem 28

a-hereditarily harrop formulae are an abstract logic programming language.

Proof

We establish commutation rules for those right rules down through those left rules, which can appear in a proof of ∆ ⊢G. Most of the proof is as for FOL [Miller et al., 1991]; then by Lemma 6 (Fresh) commutes down through any left rule, and it is easily verified that (at L) commutes up through any right rule. ■

7 Conclusions and related work

Think of an atom as a ‘generic element’; certainly, it is distinguished from other kinds of elements (just like the reader can distinguish an ‘arbitrary triangle’ from other kinds of triangles) — but only if we use at . This brings out a motivation for this work, from Kit Fine’s book ‘reasoning with arbitrary elements’ [Fine, 1985]. Fine’s ‘generic elements’ are not quite the atoms in a-logic; for a start he does not insist that generic elements exist ‘naked’ in the semantics, only that there be some notions of dependence and specialisation. However, we were inspired by the idea of a semantics in which generic elements are first-class members of the denotation. To us, ‘generic element’ suggests ‘variable’, and ‘denotation’ suggests ‘underlying set’.

We were influenced by the logic of generic judgements by Dale Miller and Alwen Tiu [Miller and Tiu, 2003]. This uses higher-order techniques in logic-programming (with a ‘definitional’ equality [Schroeder-Heister, 1993]) suited to logic-programming but not as readily to model theory; we suspect it is unsuited for our applications. Their system exhibits a quantifier ∇x.Px which, roughly, reads ‘generate a new variable symbol and assert P applied to x, where P has higher type’. While Miller and Tiu seem to insist on there being no semantic content to this (being logic-programmers, they treat the logic as a computational system and it is perfectly reasonable to request it supply a fresh variable symbol; the meaning of this operation is given by the resulting notions of derivability and proof-search, semantics in the sense of maps to sets is irrelevant). The first author was curious to know what ∇ actually means. This paper does not study the mathematical relation of a-logic with the logic of generic judgements (but we will come back to ∇ in more detail in a later paper) — however, the underlying idea suggested by what a semantics for ∇ could be, is clearly visible in the intuition we suggest for at that it identifies an element as being a variable symbol.

We have explored the semantics of a-logic, but not treated them in this paper (except via the FOL theory alogic and standard FOL model theory). We would like to point out that a nice way of obtaining a semantics is via FOL model theory, by doing to a-logic itself what we did to the λ-calculus with lambda: build a signature for the syntax of a-logic in a suitable extension of sub, so that the syntax of a-logic can be interpreted in that theory. Write down axioms for implication and universal quantification (which we can do because we have explicit substitution); much as we did for lambda. Prove that formal derivability in a-logic, coincides with the entailment between interpretations in the theory. Then a model of the theory in a-logic, is a model of a-logic. The peculiarity of this notion of model is that variable symbols exist in the underlying set and are represented in the underlying model by atoms.

This paper has considered the λ-calculus as a finitely-axiomatised object-level theory in first-order logic with a finite signature. We were aware of Salibra’s work on Lambda Abstraction Algebras,4 [Lusin and Salibra, 2004, Salibra, 2003a] which are an axiomatisation of the λ-calculus as an algebraic theory (our axiomatisation is not algebraic because of all the hypotheses such as at a, •x, and b#x), albeit with a infinite signature (roughly, Salibra assumes a unary term-former λa, one for each of a countably infinite set of names a) and infinitely many algebraic equalities (indexed over the a). The parallel with our binary term-former λ (using at in axioms to make sure that the first element is an atom) is obvious. However, Salibra can state that names are infinite as a fact of the model, he uses the infinite signature and an appropriate infinite axiom scheme, whereas we have internalised names into the object level and so must introduce a single but non-algebraic axiom (#app) to do the same job. In addition, we must introduce conditions •y to avoid inconsistencies (see wrong and inconsistent on page 19), giving, as we commented there, our open λ-terms the flavour of an internal meta-language.

Work by van Benthem and others on Dynamic Logic [van Benthem, 1997] is related to ours. The idea is to treat valuations σ (§3.3) as possible worlds, with an accessibility relation for each variable corresponding to changing the value of σ at x. Substitution of terms for variables becomes movement in a Kripke structure, and universal and existential quantifiers become modalities.

Similar ideas appear in work by Venema [Venema, 1996] and others. Kripke structures are a very general and powerful framework, and a-logic slots nicely into this picture as a logic with a predicate at which internalises whether the current world assigns a term to a variable (this is to our knowledge a new idea).

Taking the broader view, there are roughly two ways of enriching FOL with structure — add a new predicate with deduction rules directly, or view the structure as a Kripke frame and add modalities and suitable axioms. In this view, a-logic and Dynamic logic pursue similar goals by different means. This does raise the question of what other aspects of syntax can be internalised in a-logic style.

Michael Beeson created Otter2 [Beeson, 2004, Beeson, 2001] a first-order theorem-prover which extends the term-language of Otter (a first-order theorem-prover [Kalman, 2001]) with λ-terms. He calls the underlying logic ‘Lambda-Logic’; which we can think of as a single-sorted FOL with λ-abstraction in the language of terms. His motivation was good proof-search principles (from first-order logic) combined with expressivity (from the stronger term-language). Variables cannot be positively identified as such within the logic (which is what at does), but a scheme of infinitely many axioms asserts equalities such as Ap(λx.t, s) = t[x↦→s] where here Ap is a distinguished binary term-former for application and t[x↦→s] is the result of actually performing a capture-avoiding substitution of x for s in t.

We can think of the term-language of Lambda-Logic as being λ-terms up to α-equivalence, but not up to β-equivalence. This treatment of higher-orders brings many advantages. The argument (as we interpret it) is that β-reduction is just too powerful to put into the language of terms (it is Turing-complete, after all, so unification and matching are undecidable), but still we want functions to practice computer science, so we put in functions but leave β-reduction as an equality to be asserted, rather than being a literal quotient on terms. (Compare this with, say, Isabelle/HOL [Paulson, 2001], which practices higher-order unification.)

In this terminology the theory lambda (§5.1) does the same as Lambda-Logic, only we do not even quotient by α-equivalence. Consequently, λ can be treated as a binary term-former and the whole affair becomes just one theory in FOL enriched with at . It may or may not be the case that lambda is well-suited to theorem-proving (it does not delegate α-equivalence to the meta-level, and this might well be a great nuisance), but it would be possible to express the axioms of lambda in any theorem-prover with first-order logic, as we have demonstrated.

a-logic draws on Nominal Logic [Pitts, 2003, Gabbay and Cheney, 2004] and to some extent FreshML [FreshML, , Shinwell et al., 2003]. The terminology ‘atom’ is directly drawn from that work, as is the notion of ‘fresh’ #. However, in Nominal Logic atoms populate a distinct type, and # is defined in terms of permutations using the NEW quantifier И [Gabbay and Pitts, 2001], rather than substitutions using ∀. The ‘nominal way’ gives atoms the character of a collection of atomic constants representing precisely themselves up to identity, rather than a subset of the universe which are atoms representing generic elements. Consistently with the ‘atomic’ nature of atoms, Nominal Logic and FreshML are designed for deep embeddings of syntax in an ambient logic, so that the syntax is an inductive datatype [Azurat and Prasetya, 2002, Wildmoser and Nipkow, 2004]. Thus, terms like (1 + 1) are equal in the logic when they are provably equal as syntax, and not when they are equal in some denotational sense (so 1+1 is not equal to 2). Any other notions of equality, such as arithmetic equality or β-convertibility, are expressed (probably inductively) as relations. In our implementation, equality is a mix of the two; denotational on closed elements, and syntactic (except for the action of the explicit substitution) on open ones.

It is important to realise that Nominal Unification [Urban et al., 2004] and Nominal Rewriting [Maribel Fernández, 2004] introduces a two-level hierarchy of variables, ‘unknowns’ X and ‘atoms’ a, which is not present in Nominal Logic [Pitts, 2003]. This corresponds to the ‘meta-level substitution’ we considered in this paper in §6.1, though there are technical differences (only substitution, no permutations) and the axiomatisation corresponds more closely to the New Calculus of Contexts [Gabbay, 2005].

We have shown how the λ-calculus can be expressed in first-order logic. Compare this with logic expressed in the λ-calculus. For example Beeson (having extended terms of FOL with λ-abstraction to obtain Lambda Logic) uses the λ-terms to express an object-level logic [Beeson, 1998] (we could do the same here, starting from lambda). Barendregt and others have pursued the idea of taking λ-calculus as the foundation, and expressing logic in it (and avoiding inconsistency while doing so, which turns out to be hard) [H. Barendregt, 1998b, H. Barendregt, 1998a] and [Barendregt, 1984, p.560]. Finally, many systems are based directly on higher-order logic [Leivant, 1994, Paulson, 1989, Prawitz, 1964], which simply quotients terms by β-reduction and gains much power as a result (we cannot discuss the trade-offs here [Leivant, 1994, Beeson, 2004]).

To avoid inconsistency in lambda, we restrict β-reduction to st where t is provably closed. We note that this idea is similar to work by Fernández et el [Fernández et al., 2005] (they use a similar condition for a different purpose, to develop efficient reduction strategies and eliminate the need for α-conversion).

This paper is one of very many which try to bring the advantages of the λ-calculus to FOL, and more generally to reconcile them (in new and interesting ways!). We do this in a general way, which we demonstrate would be applicable also to other systems with binders, and we do this working directly in FOL using standard tools.

BIBLIOGRAPHY

[Azurat and Prasetya, 2002] 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.

[Barendregt, 1984] H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.), volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1984.

[Beeson, 1998] M. Beeson. Unification in lambda-calculi with if-then-else. In CADE- 15: Proceedings of the 15th International Conference on Automated Deduction, pages 103–118, 1998.

[Beeson, 2001] M. Beeson. A second-order theorem prover applied to circumscription. IJCAR, pages 318–324, 2001.

[Beeson, 2004] M. Beeson. Lambda logic. IJCAR, pages 460–474, 2004.

[Bell and Machover, 1977] J. Bell and M. Machover. A course in mathematical logic. North-Holland, 1977.

[Burris and Sankappanavar, 1981] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Springer, 1981. Also available online.

[D.M.Gabbay, 2005] L.Maksimova D.M.Gabbay. Interpolation and Definability: Modal and Intuitionistic Logics. Clarendon Press, 2005.

[Fernández et al., 2005] Fernández, Mackie, and Sinot. Closed reductions: Explicit substitutions without α-conversion. Mathematical Structures in Computer Science, 15(2):343–381, 2005.

[Fine, 1985] K. Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.

[FreshML, ] FreshML. FreshML homepage, . http://www.freshml.org.

[Gabbay and Cheney, 2004] M. 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, 2004.

[Gabbay and Günthner, 1986] D. Gabbay and F. Günthner, editors. Handbook of philosophical logic. Number 166 in Synthese Library. D.Reidel Publishing company, 1986.

[Gabbay and Pitts, 2001] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13:341–363, 2001.

[Gabbay, 2005] M. J. Gabbay. A new calculus of contexts. In PPDP, 2005.

[G.Boolos, 1989] R. Jeffrey G. Boolos. Computability and Logic. Cambridge University Press, 1989.

[H. Barendregt, 1998a] M. Bunder H. Barendregt, W. Dekkers. Completeness of the propositions-as-types interpretation of intuitionistic logic into illative combinatory logic. J. Symbolic Logic, 3:869–890, 1998.

[H. Barendregt, 1998b] M. Bunder H. Barendregt, W. Dekkers. Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus. Archive für Mathematische Logik, 37:327–341, 1998.

[Johnstone, 1987] P. T. Johnstone. Notes on logic and set theory. Cambridge University Press, 1987.

[Kalman, 2001] J. A. Kalman. Automated Reasoning with Otter. Rinton Press, 2001.

[L. Henkin, ] A. Tarski L. Henkin, J. D. Monk. Cylindric algebras. North Holland. Part I (1971), Part II (1985).

[Leivant, 1994] D. Leivant. Higher order logic. In Handbook of Logic in Artificial Intelligence and Logic Programming, volume 2, pages 229–322. 1994.

[Lusin and Salibra, 2004] S. Lusin and A. Salibra. The lattice of lambda theories. Journal of Logic and Computation, 14 n.3:373–394, 2004.

[Machover, 1996] M. Machover. Set Theory, Logic and their Limitations. Cambridge University Press, 1996.

[Maribel Fernández, 2004] I. Mackie M. Fernández, Murdoch J. Gabbay. Nominal rewriting. Submitted, January 2004.

[Miller and Tiu, 2003] D. Miller and A. Tiu. A proof theory for generic judgments: An extended abstract. In Proceedings of LICS 2003, pages 118–127. IEEE, June 2003.

[Miller et al., 1991] D. Miller, G. Nadathur, F. Pfenning, and A. Scedrov. Uniform proofs as a foundation for logic programming. Annals of Pure and Applied Logic, 51:125–157, 1991.

[Milner et al., 1992] R. Milner, J. Parrow, and D. Walker. A calculus of mobile processes, II. Information and Computation, 100(1):41–77, September 1992.

[Paulson, 1989] L. C. Paulson. The foundation of a generic theorem prover. Journal of Automated Reasoning, 5(3):363–397, 1989.

[Paulson, 2001] L. Paulson. The Isabelle reference manual. Cambridge University Computer Laboratory, February 2001.

[Pitts, 2003] A. M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186:165–193, 2003.

[Prawitz, 1964] D. Prawitz. Completeness and hauptsatz for second-order logic. Theoria, 33:246–258, 1964.

[Salibra, 2003a] A. Salibra. Lambda calculus: models and theories. In G. Scollo F. Spoto and A. Nijhol, editors, Proceedings of the Third AMAST Workshop on Algebraic Methods in Language Processing (AMiLP-2003), number 21 in TWLT Proceedings, pages 39–54, University of Twente, 2003. Invited Lecture.

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

[Schroeder-Heister, 1993] P. 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.

[Selinger, 1997] P. Selinger. Functionality, polymorphism, and concurrency: a mathematical investigation of programming paradigms. PhD thesis, University of Pennsylvania, June 1997.

[Shinwell et al., 2003] M. R. Shinwell, A. M. Pitts, and M. J. Gabbay. FreshML: Programming with binders made simple. In Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden, pages 263–274. ACM Press, August 2003.

[Urban et al., 2004] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. Theoretical Computer Science, 323:473–497, 2004.

[van Benthem, 1997] J. van Benthem. Modal foundations for predicate logic. Logic Journal of the IGPL, 5(2):259–286, 1997.

[van Dalen, 1985] D. van Dalen. Intuitionistic logic. In Gabbay and Günthner, editors, Handbook of Philosophical Logic vol III, volume 166 of Synthèse, chapter 4. D. Reidel.

[Venema, 1996] Y. Venema. A modal logic of substitution and quantification. Logic Colloquium ’92, pages 293–309, 1996.

[Wildmoser and Nipkow, 2004] M. Wildmoser and T. Nipkow. Certifying machine code safety: Shallow versus deep embedding. In TPHOLs, volume 3223 of LNCS, pages 305–320. Springer, 2004.

Notes

1Our reasons for using a as a variable symbol, not a constant, will become clear. ↩

2What if we choose an x′ which is introduced by some other (∀R) further up in the proof? Valid answers are: you have the proof in your hand; check, and make sure you don’t or don’t look ahead, but freshen them up if and when you come to them. This is a form of α-equivalence at the level of proofs which is common to the theory of proofs of any logic with binding. ↩

3In the equation we slipped in a simplification: a[b↦→t] ≡a. ↩

4If the reader has not heard of these, but knows about Cylindric Algebras [L. Henkin, , Burris and Sankappanavar, 1981], then they can think of Lambda Abstraction Algebras as infinite-dimensional cylindric algebras for the λ-calculus, and not be too far off the mark. ↩