ONE-AND-A-HALFTH-ORDER LOGIC
Abstract. The practice of first-order logic is replete with meta-level concepts. Most notably there are meta-variables ranging over formulae, variables, and terms, and properties of syntax such as alpha-equivalence, capture-avoiding substitution and assumptions about freshness of variables with respect to meta-variables. We present one-and-a-halfth-order logic, in which these concepts are made explicit. We exhibit both sequent and algebraic specifications of one-and-a-halfth-order logic derivability, show them equivalent, show that the derivations satisfy cut-elimination, and prove correctness of an interpretation of first-order logic within it.
We discuss the technicalities in a wider context as a case-study for nominal algebra, as a logic in its own right, as an algebraisation of logic, as an example of how other systems might be treated, and also as a theoretical foundation for future implementation.
Partially supported by EPSRC grant number EP/C013573/1.
Contents
1. Introduction 2
2. Nominal terms 4
2.1. Sorts and terms 4
2.2. Freshnesses 6
3. Derivations of one-and-a-halfth-order logic 7
4. Nominal algebra 9
4.1. Permutations and substitutions 9
4.2. Assertions, axioms and derivations 11
4.3. The theories CORE and SUB 13
5. Proof-theoretical results 14
5.1. Equivariance and substitution 16
5.2. Cut-elimination 18
6. An equational axiomatisation of one-and-a-halfth-order logic 21
6.1. Theory FOL 21
6.2. Sequent derivability implies FOL derivability 22
6.3. FOL derivability implies sequent derivability 26
7. First-order logic with equality 28
7.1. Ground terms 28
7.2. Derivability in First-Order Logic 30
8. Conclusions 32
References 35
Appendix A. Equivariance 36
1. Introduction
Consider the following valid sequents in first-order predicate logic with equality (FOL) [3, 5], written in standard notation:
(),
if fn() then ,
if fn() then (),
if fn() then ,
if fn() then ,
if fn() then () ,
().
These sequents cannot be derived in FOL, since derivations involve FOL syntax only, while the syntax of the sequents just given contains meta-variables , , , and . These are not FOL syntax, they vary over it. Also we refer to properties of syntax when we write ‘ fn()’ and ‘’, but FOL syntax cannot represent these explicitly.
Of course to us humans this is all obvious. One reason is that the derivations fall into a limited number of schema. For example the ‘derivation’ below on the left
is not a derivation, but it obviously represents a schema of derivations of which the (real) derivation on the right is an instance setting and to . But is there a logic in which the beast on the left is a derivation too?
It is not a new observation that meta-variables varying over syntax are not syntax, and that schematic derivations are not derivations [27, page 7] (Hodges calls them ‘argument schema’). Many authors do leave meta-variables at the meta-level. Some suggest that this is where they belong.
Yet logic teaches us that reasoning can and should be formalised, not only its conclusions. So if we use meta-variables in reasoning, we can and should ask ‘what is the mathematics of this reasoning’?
This paper presents one-and-a-halfth-order logic. This logic generalises first-order logic by adding explicit meta-variables (unknowns) and which in the logic represent the and of the derivations above.
If we think about how we might do this we immediately encounter serious technical barriers, due to the interaction of unknowns with quantifiers.
and need not be -convertible if mentions and free. So if we permit terms with unknowns such as and , what is the suitable generalisation of -equivalence? It is not acceptable to write ‘ does not occur in the syntax of and ’ (even though this is quite true)
— because and are syntax representing unknown predicates and should also represent the intuition of and that they might be instantiated to predicates mentioning . Yet we do need to generalise -equivalence, for example so that we can represent the right quantifier introduction rule (R):
Here as is well-known we expect to be able to -rename to guarantee the side-condition. We would still like to be able to do so in a derivation with unknowns, but it is absolutely not clear how to do so if we are just given a sequent , because and are just variable symbols (representing unknown predicates) and it is quite unclear how to rename in to avoid capture in .
In the presence of meta-variables, substitution becomes nontrivial. For example where means ‘replace by ’ has some meaning if we can rely on and being meta-variables which are bound to ‘real’ syntax. What is a correct representation of substitution which permits us to write and thus represent the left introduction rule:
So in this paper we are seeking to construct a logic that enriches the syntax of first-order logic with explicit meta-variables, and which still permits generalised forms of -equivalence, substitution, capture-avoidance, and quantifier introduction rules which are only (a very small distance) away from the ‘schematic derivations’ which we see all the time in informal practice, such as:
We shall demonstrate not only that such a logic exists, but that it satisfies many of the good properties of first-order logic including cut-elimination. Even though one-and-a-halfth-order logic is a completely formal logic with clearly-specified derivation rules, we shall see that reasoning in one-and-a-halfth-order logic is remarkably close to reasoning in informal practice using schematic derivations. One of the obvious future applications of this logic is as a basis for a theorem-prover with some of the generality of second-order logic, but with the flavour of familiar pencil-and-paper schematic derivations in first-order logic.
Map of the paper. In Section 2 we introduce the syntax of one-and-a-halfth-order logic. In Sections 3 to 5 we develop a sequent calculus and establish proof-theoretical properties including cut-elimination. In Section 6 we give an equational axiomatisation of one-and-a-halfth-order logic and show it equivalent to the sequent calculus. In Section 7 we show that a subset of one-and-a-halfth-order logic is equivalent to first-order logic. We discuss related and future work in the Conclusions.
2. Nominal terms
We need a syntax in which expressions with meta-variables may be represented. Examples we have already mentioned include , fn(), and .
We use Nominal Terms [42] because they offer built-in support for meta-variables, abstraction, and freshness in a way that is close to informal practice.
2.1. Sorts and terms.
Our sorts will be very tailored to the needs of this paper; see elsewhere for a more general exposition [18, 19].
Fix base sorts:
of formulae,
of terms.
Fix a countably infinite collection of atoms. Then sorts are inductively defined by:
The intuition of [] is ‘elements of with an atom abstracted’.
has no intuitive functional denotation; we should not think of [] as a space of functions (in a standard notation: as ). So for example [] is not a valid sort. We should think of [] as the set of -equivalence classes of elements of with a distinguished bound atom.
So much for the sorts. Now we construct the terms.
Let atoms be the elements of . For each sort fix a countably infinite collection of unknowns of sort . Atoms and sets of unknowns are all distinct.
Atoms represent object-level variable symbols, for examples see in the Introduction. Unknowns represent meta-level variables, for examples see in the Introduction. We may drop the sorting subscript and write as . We may also write : as shorthand for ‘, which has sort ’. We tend to give unknowns of sort names and unknowns of sort names .
A permutation of atoms is a total bijection with finite support, meaning that for some finite set of atoms (which may be empty) () , but for all atoms not in that set, (.
This is a mathematical notion of ‘most’: is a bijection on atoms such that ( for most .
As usual, we write Id for the identity permutation, for the inverse of , and for the composition of and , i.e. ()((()). Id is also the identity of composition, i.e. Id and Id .
Terms are inductively defined by:
Call a moderated unknown. We may abbreviate Id to .
We call the symbols
term-formers. We shall usually let f vary over term-formers.
Amongst the the reader should understand symbols such as 0, S issocrates and greek, but also , Σ, fixpoint, ! (standard notation for the ‘there exists exactly one’ quantifier), and so on.
We define sorting assertions : ( has sort ) inductively by:
There may be additional sorting rules for other term formers, such as:
We write : as a shorthand for ‘ of sort ’. We may call terms : formulae. Let be any atom, : be any terms, and be any formulae. We discuss some intuitions and introduce some sugar:
represents false.
is a logical implication.
We write ([]) as ; this represents a universal quantification (which takes an abstraction of a formula and yields a formula).
We write sub([]) and sub([]) as [] and [], representing capture-avoiding substitution in the object-language. We may also refer to these terms as substitutions.
is equality in the object-language.
is a term of sort , representing an object-level variable symbol of sort .
We may use some other standard notation for term-formers with suggestive names; e.g. we may write as shorthand for +().
We use standard classical logic sugar:
Note that these are abbreviations, not term-formers.
To save on (unnecessary) parentheses, take [] , ], , , , , as the descending order of precedence. So for example is () () and is () . Also let , , and associate to the right; for example is ().
If a term-former forms terms of sort call it an object-level term-former. If a term-former forms terms of sort call it a predicate term-former. 0, S, , Σ and fixpoint are object-level term-formers and issocrates, greek and ! are predicate term-formers. These extra term-formers would cause no difficulties for the results which follow — aside from some extra cases.
We will not want any term-former to make terms of sort [] or [] directly; the correct way to form an abstraction is to use [].
Write syntactic identity of terms as . This emphasises the difference from provable equality , which is a logical assertion defined later in Section 4.2, and object-level equality , which is a term.
Note that the sorting system is such that a well-sorted term of the form must be of the form (so
We write (or ) for ‘ (or ) occurs in (the syntax of) ’. Occurrence is literal, e.g.
Call closed when mentions no unknowns — may still mention atoms, e.g. the terms and [] are closed and the terms and [] are not.
2.2. Freshnesses.
A freshness (assertion) is a pair # of an atom and a term. Intuitively we should read # as meaning ‘ fn()’ or in words ‘ is fresh for ’.
Call the assertion # (so ) primitive. Write ∆for a (possibly infinite) set of primitive freshnesses and call it a freshness context. We may drop set brackets in freshnesses, e.g. writing ## for ##. Also, we may write # for ##.
A reason this notion is quite subtle in nominal techniques is the unknowns ; # is not necessarily true even though is a fact of the syntax. represents an unknown term in the syntax; # has the quality of a promise or assertion about what term that can be, or put another way, about what we can instantiate to.
Freshness enjoys a notion of derivation which will be very useful:
Write # when a derivation of a freshness assertion # exists using the elements of as assumptions, according to the rules in Figure 1. Say that entails # or # is derivable from .
In Figure 1. . .
and permutatively range over atoms, i.e. and represent any two distinct atoms;
ranges over permutations.1
ranges over unknowns;
and range over terms;
f ranges over term-formers.
We use similar conventions henceforth.
Examples of derivable freshness assertions are:
Examples of non-derivable freshness assertions are:
Note that freshness is decidable; we obtain an algorithm by reading the rules in Figure 1 bottom-up.
3. Derivations of one-and-a-halfth-order logic
Recall that by our terminology a formula is a term of sort .
Let (formula) contexts Φ Ψ be finite (possibly empty) sets of formulae. A sequent is a triple Φ Ψ where ∆is a freshness context and Φ and Ψ are formula contexts; when a context appears to the right of we may call it a co-context.
We may write for
Extend the notions of occurrence, closedness, permutation actions and substitution action to formula contexts elementwise; for example Φ if for some Φ.
Let the valid sequents of one-and-a-halfth-order logic be inductively specified by the rules in Figure 2.
We may call the set of valid sequents an entailment relation.
Our rules resemble those of Gentzen’s sequent calculus for classical first-order logic with equality [8, 23, 39], but with the following distinctive features:
Unknown formulae and unknown terms are represented explicitly as unknowns of sort and respectively.
We can make freshness assumptions about unknowns (using (Fr)), and these affect derivability, for example in (R).
A theory of equality of terms up to -equivalence and capture-avoiding substitution is represented by an equality ∆ in a theory SUB (formally defined in the next section).
Side-conditions on substitution, freshness and atoms not occurring in terms, are all decidable.
Call (StructL) and (StructR) structural rules. (Cut) can emulate them, but we would lose cut-elimination. Note that the side-conditions of these rules refer to equational derivability in SUB. (StructL) and (StructR) exist to help us manage substitutions, see the example derivations below.
(Fr) helps us to introduce new atoms into a derivation. The difficulty is that one-and-a-halfth-order logic has explicit meta-variables, so we need (Fr) so that we can enrich the freshness context with information that the atom is fresh for those meta-variables.
Example derivations in one-and-a-halfth-order logic are in Figure 3. We give some intuitions:
() represents a family of tautologies of propositional logic (). The only difference is that here we are using the provision of explicit meta-variables to represent this family directly as a single sequent.
[] represents a family of tautologies of predicate logic. The condition # intuitively guarantees that whatever formula represents, it is not one that mentions free in its syntax. It corresponds to writing fn
A side-condition verifies formally that if fn() then and [] are the same. Since unknowns represent meta-variables ranging over formulae and terms, such an equality is not a syntactic fact; it becomes something worthy of proof. We develop the theory of this equality next.
[]([]) is -equivalence in the presence of unknowns! The derivation exploits the power to prove equalities in SUB.
expresses that if does not appear free in and holds, then so does .
expresses the same as the previous example, except that we have an additional assumption . The derivation becomes significantly more complex: we cannot use (R) on because we do not know #.
The solution is to use (Fr) to generate #, use structural rules to -rename, and then use (R). This use of (Fr) is essential: we need this mechanism to introduce a fresh atom into the derivation.
[]() represents another family of tautologies of predicate logic [12, page 4, axiom (2a)]. For the instance of (R) to be valid we must show #[](). We have made no assumptions about what is fresh for , but the abstraction by guarantees this property anyway.
[]([]) is a relatively non-trivial tautology which might be written in semi-formal notation as ‘() implies ()’.
4. Nominal algebra
We now develop the theory of equality of nominal terms up to substitution and formally construct the judgement ∆ which we used in Figure 2. This framework is called nominal algebra [18, 19]. In this section we omit proofs of most lemmas and theorems. Full proofs are available elsewhere [19].
4.1. Permutations and substitutions.
We write for the action of a permutation on a term, defined inductively on syntax by:
() () and Id .
A substitution is a finitely supported sort-respecting function from unknowns to terms. Here, finitely supported means that for some finite set of unknowns () Id , but for all other unknowns
Write if there exists an such that (), and similarly write if there is no such . For example [] and [].
A substitution has a natural action on terms , inductively defined by:
Give substitution and permutation actions higher precedence than abstraction and any of the sugared term-formers, and put substitution before permutation.
Note how substitution interacts with permutation in the case of an unknown, for example (() )[] () . So in is ‘waiting for a substitution to arrive’, as also made formal in the following property:
().
Another permutation action will be useful. Write for the meta-level action of on , which is defined by:
Fix and , and let map to , and map to . Then and ().
So the two permutation actions are interdefinable in the presence of substitution ; however, sometimes one is more natural than the other, we shall point out how, later.
We extend notation for , and to freshness contexts ∆as follows:
Note that ∆ is a freshness context, but ∆and ∆ need not be.
4.2. Assertions, axioms and derivations.
An equality assertion is a pair of terms of the same sort. Call a pair ∆ of a finite freshness context ∆ and an equality assertion an axiom, we may write just .
Call a (possibly infinite) set of axioms T a theory.
Write when a derivation of exists using the rules in Figure 4, such that every assumption used is a freshnesses from , and for every use of () for some , that is an element of T. Say that entails or is derivable from .
For example,
In the theory with axioms and []] , the derivations
are valid. We take ) and any , and ) and ], respectively.
We cannot use axiom ( to derive that ( , because no permutation can identify with (assuming term-formers and ).
Taking to be #
the left one is valid, but the right one is not, because # is not derivable. In (ax), unknowns get arbitrarily instantiated and atoms get arbitrarily permuted. Thus in an axiom two distinct unknowns represent any two terms but two distinct atoms represent any two distinct atoms.
In (fr) square brackets denote discharge in the sense of natural deduction (as in implication introduction [27]); ∆denotes the other assumptions of the derivation of .
In a sequent style presentation of nominal algebra, (fr) would be
To see how (fr) increases the power of the system consider a theory with just one axiom #, which we call . With (fr) we can derive . Without (fr) we can derive but we cannot derive (proof omitted).
In the left derivation, the superscript number one 1 is an annotation associating the instance of the rule (fr) with the assumption it discharges in the derivation. This is standard natural deduction notation.
Useful properties of nominal algebra include:
For any :
(1) if # then ()#;
(2) if then .
If then [[].
By an easy induction on the structure of .
For any , , if then:
(1) if # then #;
(2) if then .
This has as an easy corollary:
If then:
(1) if # then #;
(2) if then .
The reader may wonder why we do not use the following alternative axiom rule:
This is just a matter of taste. Using (), atoms in the substitution are renamed according to permutation . This we personally find rather mind-bending. For example, from the axiom []] it is immediate that
4.3. The theories CORE and SUB.
We have seen examples of one-and-a-halfth-order logic derivations. We have seen that structural rules and freshnesses play an important rôle in the control of the explicit meta-variables.
In the rest of this section we formally define the valid judgements of the form . In [17], we have shown that SUB really is capture-avoiding substitutition, and that this theory is decidable. In this section, we will only show some examples. In Section 7, we will show that equality in SUB coincides with the usual notion of capture-avoiding substitution, such as the one used in first-order logic with equality (FOL).
Write CORE for the theory with no axioms. This is a theory of -equivalence on nominal terms.
Write SUB for the theory with the axioms in Figure 5. Here are distinct atoms, are distinct unknowns of sort , are distinct unknowns of sort , and is an unknown of the appropriate sort.
There may also be axioms, which we shall not dwell on, to distribute substitutions through any other term-formers such as , +, and so on. These cause no extra issues; if the term-former takes terms of abstraction sort the equality should include a freshness side-condition in the same style as ().
The following two lemmas are useful:
#[) )[]
De-sugaring, we must derive sub([] sub([]() ) from #.
[ is derivable.
##[][[][] is derivable.
By (tran), it suffices to derive [][[][[]] and [][[[][] from assumptions # and #. The former follows from axiom (sub) and assumption #. By (congf), the latter follows from [, which follows from the assumption # by axiom (#).
For a dedicated investigation of SUB see elsewhere [17]. Now we recall Figure 3.
The side-condition #)[] in the derivation of []() is an instance of Lemma 4.10.
The side-condition ##[]() in the derivation of is an instance of Lemma 4.9.
In Figure 6 we show derivations of a few of the more interesting side-conditions used in Figure 3. The final derivation is given in two parts, one of which we call Π, for typographic reasons.
5. Proof-theoretical results
This section shows two important properties of the sequent calculus for one-and-a-halfth order logic:
In derivations, atoms may be permuted and unknowns may be instantiated. We will call these properties equivariance and substitution.
The cut-elimination property of first-order predicate logic is preserved by the extension to one-and-a-halfth-order logic.
5.1. Equivariance and substitution.
Fix a freshness context ∆, a context and cocontext Φ and Ψ, and a derivation Π.
We extend notation for permutation and substitution actions , and to contexts Φ and cocontexts Ψ, writing Φ, Φ and Φ, and Ψ, Ψ and Ψ for the result of applying the actions to the terms in the syntax of Φ and Ψ.
Write Π and Π for the derivation obtained from Π by translating each part according to the following table:
So Π renames every part of Π, while Π renames everything except for freshness contexts and the side-condition of the (Fr) rule.
If Π is a valid derivation of Φ Ψ then Π is a valid derivation of Φ Ψ.
Call this property meta-level equivariance.
The statement
‘Π is a valid derivation of Φ Ψ’ has four parameters and so by ZFA equivariance (Appendix A) is invariant under permuting atoms (in the values of) those parameters. The result follows.2
If Π is a valid derivation of Φ Ψ then Π is a valid derivation of Φ Ψ.
Call this property object-level equivariance.
By induction on Π. Base cases (Ax) and (L) are direct. We consider the inductive cases in turn:
(1) The case of (R): Suppose Φ Ψ is derived using (R). Then there exists a derivation of Φ Ψ, and by the inductive hypothesis is a derivation of Φ Ψ. Then
is the required derivation Π of Φ Ψ.
The cases (L), (L), (L) and (R) are similar.
(2) The case of (R): Suppose Φ Ψ is derived using (R). Then #Φ Ψ holds and is a derivation of Φ Ψ. By Lemma 4.5 # Φ Ψ, and by inductive hypothesis is a derivation of Φ Ψ. We conclude that Φ Ψ is derivable by extending with (R), as required.
The cases (StructL), (StructR) and (Cut) are similar.
(3) The case of (Fr): Suppose Φ Ψ is derived using (Fr). Then is a derivation of Φ Ψ where Φ Ψ ∆. By meta-level equivariance (Theorem 5.1) also is a derivation of Φ Ψ, where is chosen fresh (i.e. Φ Ψ).3 By ZFA equivariance (Appendix A) validity of the property ‘ has the inductive hypothesis’ is itself invariant under permuting atoms. So ‘ has the inductive hypothesis’ is also valid.
By inductive hypothesis is a derivation of Φ Ψ. Since Φ Ψ we may deduce Φ Ψ using (Fr), as required.
Write Π() for the substitution action on derivations. We inductively define it on the structure of Π as follows:
If Π concludes with a rule (R) different from (Fr), it is of the form
where # or empty, respectively.
Otherwise, the derivation concludes in
Let be all unknowns mentioned in (), for 1 , choose the atom to be fresh (i.e. Φ Ψ), and let ∆ ##. Then:
– If 1, then Π() is
– If = 0, then Π() is just (); no extra freshness assumptions need to be introduced. Note that ∆ in this case.
So is consistently applied throughout the formula contexts occurring in Π, ∆ replaces ∆, and (Fr) may generate slightly different freshness assumptions.
Suppose that , and suppose that Π is a valid derivation of Φ Ψ. Then Π() is a valid derivation of Φ Ψ.
Call this property meta-level substitution.
By induction on Π, similar to the proof of Theorem 5.2.
The cases (R), (StructL), (StructR) and (Cut) use meta-level substitution on freshness and equality (Theorem 4.7).
We treat the case of (Fr) in more detail. Suppose Φ Ψ is derived using (Fr). Then is a derivation of Φ Ψ where Φ Ψ
Let be all the unknowns mentioned in (), 1 , choose is fresh (i.e. Φ Ψ), and let ∆ ##.
By meta-level equivariance (Theorem 5.1) is a derivation of Φ Ψ, and by ZFA equivariance (Appendix A) we retain the inductive hypothesis for this derivation. We can easily verify that ∆##), so by the inductive hypothesis () is a valid derivation of Φ Ψ.
We proceed by case distinction on :
Suppose 1. Since Φ Ψ we may extend () with (Fr) to obtain our required derivation Π() of Φ Ψ.
Suppose = 0. By definition Π() is (). Since ∆ , it is a derivation of Φ Ψ, as required.
A useful corollary of Theorem 5.3 is the following:
If Φ Ψ is derivable for closed Φ and Ψ, then there is a derivation of Φ Ψ that does not mention unknowns.
Suppose Π is a derivation of Φ Ψ, which possibly mentions unknowns. Let be the substitution that maps all unknowns in the derivation to closed terms as follows:
each unknown of sort is mapped to ;
each unknown of sort is mapped to , where is an atom that does not occur anywhere in the derivation.
By meta-level substitution (Theorem 5.3), Π() is a valid derivation of Φ Ψ. This derivation does not mention unknowns, as can be verified by an easy induction on the structure of the definition of meta-level substitution.
5.2. Cut-elimination.
Call the depth of a derivation the greatest number of derivation steps not counting rules (Fr), (StructL) and (StructR) between its conclusion and its leaves, over all paths. We do not count nominal algebra derivations of freshnesses and equalities that occur as side-conditions. For example, the last two derivations of Figure 3 both have depth 4.
The following results are not normally problematic but we have internalised both -equivalence and being fresh — so renaming and freshening must be represented in the derivation.
If Φ Ψ and then Φ Ψ. The derivation has the same depth as the original one, and no more instances of cut.
Call this property freshness weakening.
By straightforward induction on the structure of the derivation. The cases (R), (StructL), (StructR) and (Cut) use Corollary 4.8 to weaken the freshness context of the side-conditions. The case of (Fr) uses ZFA equivariance.
It is also easy to see that Π, Π and Π() preserve the depth and number of instances of Π.
Write (Stuff) for the unknowns mentioned in the Stuff .
If and #
If Φ Ψ and Φ and Ψ then . The new derivation has the same depth as the original one, and no more instances of cut.
Call this property formula weakening.
We work by strong induction on the pair of the depth of the derivation and its structure, lexicographically ordered. The conditions on preserving depth and number of cuts can easily be verified from the structure of the reasoning which follows, and we do not mention them further.
(1) The case of (StructL): Suppose Φ Ψ is derived using (StructL), and assume the inductive hypothesis on all strictly lesser derivations. So Φ Ψ and ∆ are derivable for some . This derivation has the same depth as, and a lesser structure than that of Φ Ψ, so we may use the inductive hypothesis to derive . By (StructL) we obtain as required.
(2) The case of (R): Suppose Φ Ψ is derived using (R) and suppose the inductive hypothesis of all strictly lesser derivations.
By assumption Φ Ψ has a derivation of strictly lesser depth, and also ∆ #Φ Ψ holds.
Then ∆#Φ Ψ by Corollary 4.8, and Φ Ψ by freshness weakening (Lemma 5.5).4 Then by object-level equivariance (Theorem 5.2) also () Φ () Ψ () . Using (perm), by means of (StructL) and (StructR), we obtain Φ Ψ () . By inductive hypothesis (the derivation still has strictly lesser depth) there exists a derivation Π of () . By Lemma 5.6 also ∆# , and by simple calculations we observe ∆[]() (we use (perm), and the freshness information we have assumed of ).
Now we can conclude as follows:
(3) The case of (Fr): Suppose Φ Ψ where Φ Ψ use ZFA equivariance (Appendix A) to rename to some the whole derivation to obtain one of Φ Ψ. We can now apply the inductive hypothesis (which, as discussed above, by equivariance is preserved by the permutative renaming) to weaken to and , and finish off with (Fr).
The other cases are easy or similar.
Recall the sugar from Subsection 2.1.
The rules of Figure 7 are all admissible.
We consider just the case of (R). Suppose we have derived Φ Ψ. Then by Lemma 5.7 there also exists a derivation of Φ Ψ. Extending that derivation with (R) we obtain a derivation of Φ Ψ as required.
The cases (R), (L), (L), (R) and (L), are similar. Remaining cases are by directly extending derivations. In the case of (R), we use (StructL) to replace the ()[] by ([]).
Some of the above admissible rules will turn out useful later (Subsection 6.3). Write Φ[] for the elementwise application of the substitution to the elements of formula context Φ.
If Φ Ψ then Φ[] Ψ[]. The depth of the derivation does not increase, and neither does the number of cuts it contains.
Call this property object-level substitution.
Analogous to the proof of Lemma 5.7.
(Fr) may be commuted down through all other rules. The transformations involved do not increase the depth of a derivation or its number of cuts.
We consider the various possibilities in turn:
Suppose (Fr) is followed by (L) as follows:
Suppose we are unlucky and is mentioned in . Choose a fresh atom (i.e. Φ Ψ). By meta-level equivariance (Theorem 5.1), Π( is a valid derivation of Φ Ψ. Also, by freshness weakening (Lemma 5.5), there is a derivation of Φ Ψ.
We can now put our derivation together:
The new derivation preserves the depth and number of cuts of the original derivation, since Π1 does so by definition and does so by Lemma 5.5.
All other cases are similar or simpler. For example if (Fr) is followed by (L) it is not immediate that we may swap the derivation rules round, since perhaps in (L) mentions and does not. As in the previous case we may rename atoms in the derivation and then commute.
If Φ Ψ is derivable in the sequent calculus for one-and-a-halfth-order logic, then there exists a derivation of Φ Ψ which does not mention (Cut).
The commutation cases and essential cases are standard [23, 39]; we use Lemma 5.7 for the essential case for ; the non-standard case of (Fr) is handled by Lemma 5.10. The essential case for is handled by Lemma 5.9.
The sequent calculus of one-and-a-halfth-order logic is consistent, i.e. can never be derived.
By contradiction. Suppose is derivable, then by Theorem 5.11 a cut-free derivation exists. Let Π be the shortest derivation of for all possible ∆. We check through all possible derivation rules and see by their syntax-directed nature that the derivation must conclude in (Fr). But then we have a shorter derivation of some , which is a contradiction.
6. An equational axiomatisation of one-and-a-halfth-order logic
6.1. Theory FOL.
We now give an axiomatic presentation of one-and-a-halfth-order logic in nominal algebra from Section 4.
We now discuss the axioms in Figure 8:
We read (MP) as ‘Modus Ponens’ and it expresses the principle ‘if is true and implies is true, then is true’. In the literature this principle is also called detachment.
In (M) recall that is sugar for . This axiom from [32], along with Modus Ponens, is sufficient to derive all rules of classical propositional logic — otherwise known as boolean logic [7]. (M) stands for Meredith, the author of this axiom for classical predicate logic, which he discovered in the 1940s. Machine-checked verification of this fact is online [33]. Succinct axioms for propositional logic continue to provide innocent fun in some circles [31]; a good survey is here [22].
Axioms (Q1) (Q3) add quantifiers, we call them quantifier axioms; (Q3) exploits freshness conditions.
These axioms appear in the literature [12, page 5 (2)]. What is new here is that our axioms are not axiom-schemes; they are individual axioms (three, to be precise). We do this using the unknowns of nominal terms, and abstractions and freshness conditions to express capture-avoidance conditions which usually must be expressed — at the meta-level — for every instance. Note how these axioms are faithful to the usual syntactic form of the axiom-schemes found in the literature.
Axioms (E1) and (E2) add object-level equality, we call them equational axioms.
Again, we are able to represent by two axioms what might otherwise be two infinite axiom-schemes.
We now make the connection between the axioms in Figure 8 in the context of nominal algebra, and the sequent rules in Figure 2.
6.2. Sequent derivability implies FOL derivability.
Let classical propositional logic be the entailment relation obtained by considering rules (Ax), (L), (L), and (R) from Figure 2 and removing ∆.
If is derivable in classical propositional logic, then in the nominal algebra theory FOL.
By machine-checked proofs online [33], (MP) and (M) suffice to derive all the logical identities of classical propositional logic.
The following equalities are all derivable in FOL:
The reader will recognise these as the equalities of boolean algebra. It is known that equality in boolean algebra characterises precisely logical equivalence in classical propositional logic [7]. By Theorem 6.2 the equality of FOL includes equalities between all formulae that are provably logically equivalent in classical propositional logic (it suffices to use (MP) and (M)). The result follows.
We shall say we work by elementary calculations (in propositional logic) when we use Corollary 6.3 to transform formulae according to standard identities in classical propositional logic.
is derivable.
We derive as follows:
It follows that and so by elementary calculations in propositional logic the result follows.
An informal reading of Lemma 6.4 is that any semantics for in FOL should be non-empty, for if were empty then (intuitively) , so should not be derivable.
is non-empty because it is populated by atoms (in the derivation above, we use the fact that it is populated by ). Thanks to the substitution action, atoms behave like ‘object-level variable symbols’. Normally sorts of terms are populated by variable symbols, but this feature of the syntax does not show in the semantics, and that affects the notion of derivability: () may be derivable. We see that in one-and-a-halfth-order logic terms are populated by unknowns and atoms. Although atoms represent variable symbols, the derivation above suggests that any semantics for one-and-a-halfth-order logic must differ from a ‘standard’ semantics, and give atoms denotational reality. One such semantics is given by a standard semantics for nominal algebra [18] in nominal sets [21]; developing other denotations-containing-variables is very much of current research interest.
We need some meta-level properties.
For any formulae :
if and only if and .
if and only if .
By elementary calculations in propositional logic.
We also need some scope extrusion properties.
The following are derivable:
(1)
(2)
(3)
(4)
(5)
We are now in a position to derive the following ‘sequent-like’ properties of our Hilbert-style FOL:
For all formulae , atoms , terms : , and unknowns :
(3) if and
(4) if
(5) if []
(6) if and #
(7) if []
(9) if and
(10) if and
(11) if ## and
(12) if ,
The first four parts follow by elementary calculations in propositional logic.
For part 5, suppose that ∆ [] . By axiom (Q1) we know [. By Lemma 6.5 we obtain
Using further elementary calculations we conclude ∆ as required.
For part 6, suppose that ∆ # and ∆ . Using (cong[]) and (congf) we obtain ∆ [](. We use Lemma 6.6 and (tran) to conclude ∆ .
Parts 7 and 8 use axioms (E1) and (E2), respectively. Parts 9 and 10 follow by (tran) and (congf), since ∆ implies ∆ . Part 11 is immediate using (fr).
Part 12: Since ∆ implies ∆ , we may suppose
By Lemma 6.5 we obtain ∆ () (. By elementary calculations in propositional logic ∆ , so we conclude () (. By further calculations we reduce this to .
For any one-and-a-halfth-order logic context Φ = , define its conjunctive form Φ to be
when = 0, and
when 0.
Analogously define the disjunctive form Φ to be
when = 0, and
when 0.
The order of the is irrelevant; we promise never to do anything such that it matters.
If Φ Ψ is derivable in one-and-a-halfth-order logic then Φ Ψ in the nominal algebra theory FOL.
We inductively transform a one-and-a-halfth-order logic derivation of Φ Ψ into a nominal algebra derivation of Φ Ψ from ∆in theory FOL.
For every rule (R), the derivation has the following format:
Here 0 1 2, are derivations of , 1 , and cond is a (possibly trivial) side-condition (the non-trivial cases are (Fr), (Cut), (StructL), (StructR), and (R)).
So are derivable, then by inductive hypothesis ∆ holds. We use this together with cond to prove ∆ Φ Ψ. For each inference rule (R), this is an instance of a part of Lemma 6.7.
For example, if (R) is (Cut) then ∆ Φ Ψ should follow from
Φ Ψ Φ Ψ and ∆
This is an instance of part 12 of Lemma 6.7, using Φ and Ψ.
And if (R) is (R) then ∆ Φ Ψ should follow from
This is an instance of part 6, again using Φ and Ψ.
6.3. FOL derivability implies sequent derivability.
We now show that the sequent presentation of one-and-a-halfth-order logic (Figure 2) can mimic the axioms of nominal algebra theory FOL (Figures 4 and 8). In the proofs in this subsection we will use the admissible sequent rules from Corollary 5.8 (Figure 7) without comment.
For all formulae , terms : and atoms , the following are derivable in one-and-a-halfth-order logic:
(1)
(2) (((() ()) ) ) (() ())
(3) []
(4)
(5) if # then []()
(6) [] []
(7)
We give details of parts 5 and 6. The derivation of part 6 is completely syntax directed:
For part 5, we assume ∆ #. By (R), it suffices to derive
(a) []() , and
(b) []().
We show that (a) is derivable, showing derivability of (b) follows similar lines:
The side-condition on (StructL) is an instance of Lemma 4.10. The freshness side-conditions are straightforward from the definition of freshness derivability.
In the sequent calculus of one-and-a-halfth-order logic:
bi-implication is an equivalence relation (a reflexive symmetric transitive relation), i.e. the following rules are admissible:
bi-implication is a congruence:
is the left and right identity of bi-implication:
For all sorts , terms : , unknowns : , formulae , and freshness contexts :
By induction on the structure of FOL derivations of from ∆.
(refl): [] [] follows by reflexivity of .
(symm): [] [] follows from [] [] by symmetry of . By inductive hypothesis this follows from the assumption.
(tran): [] [] follows from [] [] and [] [] by transitivity of . By the inductive hypothesis these follow from the assumptions.
(cong[]): By the inductive hypothesis [] [] for any and . We must show [[]] [[]], which is syntactically equivalent to
where is an unknown (of appropriate sort) that does not occur in . This follows directly from the inductive hypothesis, taking [[]] and .
(congf): Analogous to the previous case.
(perm): we show [() ] [] as follows:
where ∆ [() ] [() [() ] [] is the side-condition of (StructR). By (congf) and congruence Lemma 4.6, this follows from the assumption ∆ () .
(fr is derived from ∆##, where We must show [] []. We cannot apply (Fr) directly, since might mention . Using ZFA equivariance we rename to ∆ while preserving the inductive hypothesis, to obtain [] []. We conclude [] [] by (Fr), since [] []
(): We work by cases:
If is an axiom of SUB (from Figure 5) then it is of the form ∆ . By congruence Lemma 4.6 we know ∆ [[]. We must show [] []. By (R), this follows from [] [] and [] []. The former can be derived:
The latter derivation is analogous, using (StructL).
If is an axiom from Figure 8 then the derivation is of the form
where Π is a derivation of ∆. We must show [] []. By congruence of (Lemma 6.10) this follows from . In case , this follows from by right identity of . For each axiom the remaining proof obligation is an instance of part of Lemma 6.9, using the assumption ∆ .
If Φ Ψ then Φ Ψ.
By (Cut) Φ Ψ follows from Φ Ψ Φ Ψ and Φ Ψ Φ Ψ. The former follows from the assumption using weakening (Lemma 5.7). The latter follows by (L) and a simple induction on the size of Φ and Ψ.
Sequent derivability is equivalent to FOL derivability:
Φ Ψ if and only if Φ Ψ.
The left-to-right part is Theorem 6.8.
For the right-to-left part, assume ∆ Φ Ψ. Then by Lemma 6.11 Φ Ψ is derivable. By right identity of , also Φ Ψ. By Lemma 6.12 we obtain Φ Ψ, as required.
This theorem has some nice corollaries.
For any :
By Theorem 6.13 and are equivalent to ∆ and ∆ . They are equivalent to ∆ , by part 1 of Lemma 6.5. Finally, by part 2 of that lemma, this is equivalent to ∆ .
FOL is consistent, i.e. does not hold for any .
By contradiction. Suppose ∆ . Using elementary calculations in propositional logic, also ∆ . Note that and , so by Theorem 6.13 is derivable, which contradicts consistency of one-and-a-halfth-order logic (Corollary 5.12).
7. First-order logic with equality
In this section we show how first-order logic can be considered as the fragment of one-and-a-halfth-order logic without unknowns or explicit substitutions.
7.1. Ground terms.
Call a nominal term ground if it does not mention unknowns (it is closed) and it does not mention sub (the substitution term-former). Ground terms of sort and are inductively characterised by
Here , , . . . are the indexes of the object-level term-formers and , , . . . are the indexes of the predicate term-formers other than , , , and , as mentioned in Subsection 2.1. We will not mention these term-formers again; they merely give rise to a few more cases in proofs.
For example, and []() are ground; and [] are not.
We may write the term where is ground just as (consistent with standard notation). Recall that in may not be renamed in general, e.g. to . Intuitively represents an unknown formula which might mention (if we know # we can at least rename to []()). To emphasise this we retained the notation [] until now. In where is ground, we know all atoms in and this issue does not arise.
Write fn() and fn() for the free names of ground terms : and : respectively, inductively defined by:
For ground terms : and : :
(1) # if and only if fn
(2) # if and only if fn
By simple induction on freshness derivations of on the one hand, and by induction on the definition of fn on the other.
Define -equivalence as the least congruence on formulae such that
The reader might have expected the clause for to read something like
where here is informal notation for with every replaced throughout by a freshly chosen , and similarly for . The two notions of -equivalence are identical [13]. The definition we adopt gives a closer match to how equality is defined in nominal algebra (specifically to (perm)).
CORE is a theory of -equivalence:
For ground terms : and : :
(1) if and only if .
(2) if and only if .
By known arguments of nominal results [18, 21].
For ground terms : and : , write and for and with replaced by , inductively defined by:
Here we make some arbitrary choice of for each , , and , and fix it for the rest of this paper.
On closed terms we can interpret all occurrences of term-former sub by capture-avoiding substitution.
Define the translation of closed terms to ground terms inductively on closed terms by:
The following nontrivial results are proved elsewhere [16] (the tools are also provided in [17]).
For closed terms , if # then fn().
For closed terms , .
For closed terms , if and only if .
7.2. Derivability in First-Order Logic.
A Gentzen sequent is a pair Φ Ψ of finite sets of ground formulae Φ and Ψ. The valid judgements of Gentzen’s sequent calculus for first-order logic are the Gentzen sequents inductively specified by the rules in Figure 9.
Here fn(Φ Ψ) stands for the union of all fn
If Φ Ψ is derivable in Gentzen’s sequent calculus then Φ Ψ is derivable in the sequent calculus for one-and-a-halfth-order logic.
The statement of this lemma is a little bit vague, since we take formulae up to -equivalence when we define Gentzen style derivability, but we do not take formulae up to -equivalence in one-and-a-halfth-order logic (but we have structural rules (StructL) and (StructR) instead). We ignore this issue, and suppose that some arbitrary choice of representative closed nominal terms is made for us.
Suppose Φ Ψ is derivable in Genzten’s sequent calculus. By induction on derivations of Φ Ψ we construct a derivation of Φ Ψ. Each rule translates to its one-and-a-halfth-order counterpart, where we note the following:
If at the meta-level in the Gentzen system we used -conversion, or just if we wish to change representatives, then we can ‘patch’ the derivation in one-and-a-halfth-order logic with structural rules (StructL) and (StructR). The side-conditions follow by Theorem 7.2.
For the case of (L) we need an extra use of (StructL) to manage the substitution. The side-condition [ follows by Lemma 7.5. The case of (L) is similar.
For the case of (R) the side-conditions #Φ Ψ follow from the assumption fn(Φ Ψ) by Lemma 7.1.
If Φ is a closed formula context, write Φ for the ground context Φ.
For closed Φ Ψ, Φ Ψ is derivable in one-and-a-halfth-order logic, if and only if Φ Ψ is derivable in Gentzen’s sequent calculus.
For the right-to-left direction, suppose Φ Ψ is derivable in Gentzen’s sequent calculus. By Lemma 7.8, Φ Ψ is derivable in one-and-a-halfth-order logic. We also know that for each Φ Ψ, by Lemma 7.5 and equational rule (symm). We use this to extend the derivation of Φ Ψ with applications of (StructL) or (StructR) for each Φ Ψ to obtain one of Φ Ψ, as required.
The left-to-right direction is by induction on derivations of Φ Ψ. By Corollary 5.4 we assume that these derivations do not mention unknowns, and by Theorem 5.11 we assume that they do not mention (Cut).
We consider the rules in turn:
(StructL) and (StructR) are facts, by Theorem 7.6.
(Fr) is impossible since the derivation does not mention unknowns.
The other rules translate directly to their first-order counterparts. For the case of (R) we use Lemma 7.4.
For ground Φ Ψ, Φ Ψ is derivable in one-and-a-halfth-order logic, if and only if Φ Ψ is derivable in Gentzen’s sequent calculus.
This is a direct instance of Theorem 7.9, since Φ Φ and Ψ Ψ when Φ and Ψ are ground.
For ground , in nominal algebra if and only if and are derivable in Gentzen’s sequent calculus.
By Corollaries 6.14 and 7.10.
8. Conclusions
Explicitly representing meta-variables has a long pedigree.
Monadic second-order logic [6] enriches first-order logic with variables ranging over predicates of arity one representing unknown unary predicates, or if we prefer ‘unknown sets’; the stronger second-order and higher-order logics [44, 40] represent unknowns as variables of function type. Representing unknowns as function variables has some distinctive features inherited from their intended functional semantics.
First, you have to choose the arity of your unknown in advance, e.g. function variable : can be interpreted as an unknown -ary predicate — but which ? Thus these logics distribute ‘unknown predicates’ across many types.
Second and perhaps more importantly, instantiation of these variables avoids capture. This has a side-effect that it is not possible to represent an unknown predicate uniformly across contexts. For example to represent the unknown in the context we can intuitively express as , it suffices to write where : ; but to represent the unknown in the context we must write — must take a higher type. Since for any given we must choose a type for it, it is not possible to directly represent the context we might write as Qs, where Qs represents an unknown context (of quantifiers).
Instantation of unknowns in nominal algebra does not avoid capture so that accurately reflects our intention when we write where may be instantiated in a capturing manner. Furthermore still represents in .
This suggests an application to the problem of incomplete proofs. Incomplete proofs arise naturally in proof-search in a human-assisted theorem-prover such as Isabelle [36] or COQ [28]. Here the theorem-prover acts as a program to manipulate proofs which are incomplete both in the sense of having holes, and in the sense of occurring in an unknown context, and the human assistant guides the system to fill in these holes until a complete proof emerges. A quantifier introduction rule binds the quantified variable in the derivation above it (this is usually expressed by a freshness condition). In the presence of incomplete proofs it is necessary to somehow represent this binding over an as yet unknown derivation. We believe that nominal terms with their unknowns and abstractions are a good match for the incomplete proofs and quantifiers binding in it. As the incomplete proof is ‘filled in’ by the human assistant and the system, a capturing substitution should be made for the unknown. An exciting application of our technology would be an investigation of how well (if at all) a system related to one-and-a-halfth-order logic but with proof-terms can represent this process. A step in this direction would be to investigate a Curry-Howard correspondence [43] for one-and-a-halfth-order logic.
For this it might be convenient to use an intuitionistic flavour of one-and-a-halfth-order logic. Note that there is no technical barrier to this. An intuitionistic one-and-a-halfth-order logic can be defined in the usual way by restricting the sequents in Figure 2 to have a single conclusion.
Unknowns also lend a very distinctive style to our nominal algebra theory FOL (see Figures 5 and 8), and to the sequent rules of one-and-a-halfth-order logic (see Figure 2). These rules accurately reflect common practice in the handling of meta-variables, see [12, 27] and the examples of the Introduction, and as a result we have been able to import first-order proof theory quite directly into our augmented setting.
It is not possible to make a direct comparison between one-and-a-halfth-order logic and second-order logic. The second-order theorem (() ) cannot be expressed in one-and-a-halfth-order logic, because one-and-a-halfth-order logic has no quantification over predicates; this gives it a first-order flavour. On the other hand the one-and-a-halfth-order logic theorem cannot be expressed in second-order logic, because that logic cannot directly express freshness conditions. To the authors’ knowledge no-one has been able to give a truly satisfactory account of the precise relation of nominal-style unknowns, and higher-order variables.
Our work is one (more) element in a very long line of investigations into algebraic logic [1]; for example cylindric [26], polyadic [25], and quantifier [38] algebra. There too, unknowns are syntax representing unknown elements quantified universally at top level, and abstraction []- (our notation) is clearly visible, e.g. as the of cylindric algebra. However, these systems do not have as a goal to reflect the proof-theory of first-order logic. One-and-a-halfth-order logic does this. The connection with the algebraic method is then via Nominal Algebra and our axiomatisation of derivability in one-and-a-halfth-order logic.
It is possible to represent the syntax of first-order logic in a so-called framework logical system, at ‘object-level’, i.e. as an inductive datatype — the so-called deep embedding. Then meta-variables are easily representable as meta-variables of the framework. This path is taken by Higher-Order Abstract Syntax [37], Fraenkel-Mostowski syntax [21], the Theory of Contexts [34] and much other research. This enterprise is quite different from that undertaken in this paper; one-and-a-halfth-order logic is about extending the syntax of the logic itself so it contains something which behaves very much like a meta-variable ranging over unknown formulae, without losing logical properties such as cut-elimination.
It is also possible to represent the semantics of first-order logic as theory in a framework, for example as a pair of types and along with functions between them like : () or : () . This is called a shallow embedding.
In [36] the case is made for Isabelle and for its higher-order logic framework as an efficient basis for shallow embeddings, and for conducting mathematics in these embeddings. For example, a shallow embedding of first-order logic called Isabelle/FOL exists in Isabelle’s higher-order logic framework Isabelle/Pure. A shallow embedding requires only a logic with a sufficiently powerful judgement form. Our axiomatisation of one-and-a-halfth-order logic in nominal algebra, is a shallow embedding.
The technical content of this paper is therefore in two halves with equal status: a case study of a shallow embedding of first-order logic using nominal algebra as a logical framework, and a study of logic proof-theory in the presence of nominal-style unknowns.
Logic proof-theory with nominal-style unknowns is new, and seems to work quite well; the rules of Figure 2 are clean and close to informal practice. We can now try to extend this system with abstraction over meta-variables; we come back to this idea in a moment.
What of nominal algebra as a logical framework; how does it size up for example compared to higher-order approaches? Time and further research will decide just where nominal algebra fits in but we can make some preliminary observations.
Nominal algebra is not higher-order — this means that it is not based on terms up to -equivalence; it is based on nominal terms. Unification on nominal terms is decidable [42] and this is not the case of unification up to -equivalence. Thus, using nominal algebra avoids some of the complexity of higher-order unification. This paper and others [17, 10] show how nominal terms can express fully-functional logics, and in a very direct manner ‘ away from informal practice’.
The authors see no difficulties in principle with axiomatising substructural logics such as linear logic [24], bunched implications [35], relevance logics [9], and so on; if the logic is susceptible to a (nominal) algebraic treatment then it can be axiomatised in nominal algebra. This is not always the case of a shallow embedding in a higher-order logical framework, because the structural rules of the connectives and quantifiers of that logic may ‘infect’ those of the object-logic.
There is also a more subtle foundational issue. Formal proofs of basic theoretical properties such as Church-Rosser in systems such as Isabelle are important and technically informative, however there is some legitimate concern about their foundational status, seeing as the correctness of the basic framework is a higher-order logic and so depends amongst other things on Church-Rosser. Nominal algebra is not higher-order and the correctness of meta-level properties does not appear to depend directly on Church-Rosser and other properties of -calculus syntax.
The technical tools used in this paper were developed based on work on Nominal Unification by the first author with Urban and Pitts [42], which introduced the theory of nominal terms up to CORE (our terminology). This was extended with Fernández [10] to Nominal Rewriting, a theory of rewriting on nominal terms, again up to CORE, and recently investigated with the second author, as a general framework of nominal algebra [18, 17].
For future work we are particularly interested in the following topics:
We can return to theory and be inspired by higher-order logic to ask whether we could permit abstraction over meta-variables, introducing an infinite hierarchy of stronger meta-variables such that at each level a meta-variable of higher level behaves to the lower level as an unknown behaves to an atom . This idea is explored in the arena of operational semantics by a -calculus called NEW calculus of contexts [14], and a rewriting framework called hierarchical nominal rewriting [15]. This might recover some or all of the power which one-and-a-halfth-order logic lacks compared to higher-order logic, but in a different way. In short, we envisage two- three- four- and -and-a-halfth-order logic. This would involve interesting extensions to the ‘nominal theme’. Another direction is to allow unknowns ranging over derivations of sequents, which may have interesting interactions with (R), which would abstract in such an unknown.
The semantics of one-and-a-halfth-order logic are interesting and raise the questions ‘what is an appropriate semantics for ’, and ‘what is an appropriate semantics for ’? Note that it is not possible to directly evaluate to an element of a set underlying domain, because intuitively ‘can mention ’. Thus we can use domains in which atoms can appear (à la Fraenkel-Mostowski sets [18, 21] or other approaches [4, 11]). The simplest solution, and perhaps the best one, is to evaluate to terms (a ‘substitutional semantics’ [30, Section 2] faithful to its intuition as an ‘unknown term’) and then evaluate atoms to elements of a set underlying domain.
References
[1] H. Andréka, I. Németi, and I. Sain. Algebraic logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 2, pages 133–249. Kluwer, 2001.
[2] J. Barwise. Admissible Sets and Structures: an approach to definability theory. Perspectives in mathematical logic. Springer, 1975.
[3] J. Barwise. An introduction to first-order logic. In J. Barwise, editor, Handbook of Mathematical Logic, pages 5–46. North Holland, 1977.
[4] M. Beeson. Lambda logic. In 2nd Int’l Joint Conf. on Automated Reasoning (IJCAR 2004), volume 3097 of LNCS, pages 460–474. Springer, 2004.
[5] J. Bell and M. Machover. A course in mathematical logic. North-Holland, 1977.
[6] C. Bruno. The expression of graph properties in some fragments of monadic second-order logic. DIMACS Series in Discrete Mathematics, 31, 1997.
[7] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Springer, 1981.
[8] A. Degtyarev and A. Voronkov. Equality reasoning in sequent-based calculi. In J. A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, pages 611–706. Elsevier and MIT Press, 2001.
[9] M. Dunn and G. Restall. Relevance logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 6, pages 1–128. Kluwer, 2002.
[10] M. Fernández and M. J. Gabbay. Nominal rewriting. Information and Computation, 2005. In press.
[11] K. Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.
[12] D. M. Gabbay and G. Malod. Naming worlds in modal and temporal logic. Journal of Logic, Language and Information, 11(1):29–65, 2002.
[13] M. J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
[14] M. J. Gabbay. A new calculus of contexts. In PPDP ’05: Proc. of the 7th ACM SIGPLAN int’l conf. on Principles and Practice of Declarative Programming, pages 94–105. ACM Press, 2005.
[15] M. J. Gabbay. Hierarchical nominal rewriting. In LFMTP’06: Logical Frameworks and Meta-Languages: Theory and Practice, pages 32–47, 2006.
[16] M. J. Gabbay and A. Mathijssen. Capture-avoiding substitution as a nominal algebra (journal version). Submitted Formal Aspects of Computing.
[17] M. J. Gabbay and A. Mathijssen. Capture-avoiding substitution as a nominal algebra. In ICTAC’2006: 3rd Int’l Colloquium on Theoretical Aspects of Computing, volume 4281 of LNCS, pages 198–212, 2006.
[18] M. J. Gabbay and A. Mathijssen. A formal calculus for informal equality with binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of LNCS, pages 162–176, 2007. To appear.
[19] M. J. Gabbay and A. Mathijssen. Nominal algebra. Technical report, Heriott-Watt, 2007.
[20] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, 1999.
[21] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.
[22] A. Gareau and R. Padmanabhan. Two axioms for implication algebras. Notre Dame Journal of Formal Logic, 2006.
[23] G. Gentzen. Untersuchungen über das logische schließen [Investigations into logical deduction]. Mathematische Zeitschrift 39, pages 176–210,405–431, 1935. Translated in [41], pages 68–131.
[24] J.-Y. Girard. Linear logic. Theoretical Computer Science, 50:1–102, 1987.
[25] P. Halmos. Algebraic logic, ii. homogeneous locally finite polyadic boolean algebras of infinite degree. Fundamenta Mathematicae, 43:255–325, 1956.
[26] L. Henkin, J. D. Monk, and A. Tarski. Cylindric Algebras. North Holland, 1971 and 1985. Parts I and II.
[27] W. Hodges. Elementary predicate logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer, 2001.
[28] G. Huet, G. Kahn, and C. Paulin-Mohring. The Coq proof assistent, a tutorial. http://pauillac.inria.fr/coq/doc/tutorial.html. LogiCal Project.
[29] P. T. Johnstone. Notes on logic and set theory. Cambridge University Press, 1987.
[30] H. Leblanc. Alternatives to standard first-order semantics. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 2, pages 53–132. Kluwer, 2001.
[31] W. McCune, R. Veroff, B. Fitelson, K. Harris, A. Feist, and L. Wos. Short single axioms for boolean algebra. Journal of Automated Reasoning, 1(29):1–16, 2002.
[32] C. A. Meredith. Single axioms for the systems (c,n), (c,o) and (a,n) of the two-valued propositional calculus. The Journal of Computing Systems, 3:155–164, 1953.
[33] Metamath.Org. Derivation of classical propositional logic from meredith’s axiom. us.metamath.org/mpegif/meredith.html.
[34] M. Miculan. Developing (meta)theory of lambda-calculus in the theory of contexts. ENTCS, 1(58), 2001.
[35] P. W. O’Hearn and D. J. Pym. The logic of bunched implications. Bulletin of Symbolic Logic, 2(5):215–244, 1999.
[36] L. C. Paulson. Isabelle: the next 700 theorem provers. In P. Odifreddi, editor, Logic and Computer Science, pages 361–386. Academic Press, 1990.
[37] F. Pfenning and C. Elliot. Higher-order abstract syntax. In PLDI ’88: Proc. of the ACM SIGPLAN 1988 conf. on Programming Language design and Implementation, pages 199– 208. ACM Press, 1988.
[38] C. Pinter. A simple algebra of first-order logic. Notre Dame Journal of Formal Logic, 14(3):361–366, 1973.
[39] D. Prawitz. Natural Deduction: A Proof Theoretical Study. Almqvist and Wiksell, Stockholm, 1965.
[40] S. Shapiro. Systems between first-order and second-order logics. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 131–188. Kluwer, 2001.
[41] M. Szabo, editor. Collected Papers of Gerhard Gentzen. North Holland, 1969.
[42] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
[43] P. Urzyczyn and M. Sørensen. Lectures on the Curry-Howard isomorphism, volume 149 of Studies in Logic. Elsevier, 2006.
[44] J. van Benthem. Higher-order logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 189–244. Kluwer, 2001.
Appendix A. Equivariance
We use atoms in this paper — we introduce them when we write ‘Fix a countably infinite collection of atoms ’ in Section 2.
We can represent atoms as, say, numbers 0 1 2 3, or as sets . In principle we might ‘accidentally’ use some property of atoms specific to their implementation, such as or . However, we know we do not do this, because we consider atoms to be . . . atomic.
By explicitly bearing this in mind, we can rename atoms. This is equivariance, proved below, which we use freely in this paper to give structural inductive proofs (renaming atoms in inductive hypotheses where convenient) while remaining fully formal.
Without equivariance, to be fully formal proofs by induction on measures such as term length or derivation depth would be necessary. These are longer, harder to read, and are rarely given in full detail outside of a theorem-prover.
To give a precise statement and formal proof of equivariance and how it can be used to rename atoms in proofs by structural induction on the syntax of terms and derivation-trees, it is well-worth a brief look at foundations so that we can prove a few simple theorems about a foundation in which atoms really are atomic.
ZFA stands for ‘Zermelo-Fraenkel set theory with atoms’. ZFA is a set theory, and set theories are just axioms in first-order logic with equality (similar to the one we defined in Section 7). Equivariance was introduced in [20]. It is a meta-mathematical property, meaning that it refers to the assertions proved in this paper.
We do not mean that equivariance refers to the terms of sort , nor the formulae of first-order logic, nor sequents of one-and-a-halfth-order logic. We mean that it refers to the assertions written in english in this paper — about one-and-a-halfth-order logic, nominal algebra, and so on.
ZFA features a set of atoms . The original motivation of atoms was to address the question ‘what set is equal to Plato?’. Obviously Plato is not any of the ‘normal’ sets of set theory, such as the empty set or the set containing just the empty set , and so on. The answer was to accommodate ‘the real world’ by introducing it en masse into the set model, as atoms.
As far as the set theory is concerned atoms are atomic objects with no internal (set-)structure, so it is quite natural to use these to model variable symbols. This idea appears already in [2]. As discussed, the advantage of this over an atom-less foundation such as ZF, is that equivariance is guaranteed, as we shall see.
For the language of ZFA set theory, in addition to the basic language of first-order logic with equality, we assume:
A binary predicate symbol called set inclusion.
A constant term-former called the set of atoms.
We use standard sugar of classical logic (similar to the sugar mentioned in Subsection 2.1).
ZFA set theory has the axioms in Figure 10.
Here, ranges over all predicates, [] denotes the predicate obtained by capture-avoiding substitution of by , and represents a function on the sets universe (strictly speaking, this is itself sugar, which is briefly described in Corollary A.4). Furthermore, we use the following sugar:
| is sugar for | (() ) | |
| is sugar for | ( ()) | |
| is sugar for | ((()) | |
| is sugar for | ( ()) | |
| () | is sugar for | (()) |
| is sugar for | (()) | |
| is sugar for | () | |
| is sugar for | (()) |
The syntactic sugar used in set theory is very rich; further details can be found elsewhere [29].
Note that atoms are extensionally equal to the empty set. This means that the same elements are related to them by : , but (and is not an atom). is not an atom, and is distinguished from atoms in that it is the unique empty set which is not in the set of atoms.
We can define a permutation action on ZFA sets by:
This definition is by -induction. Definition by -induction is a standard method in set theory [29]; if it is true that a property holds of , and if it holds of all then it holds of all , then that property holds of all . Written informally: sets are well-founded trees with daughter-of given by set inclusion .
We read ()() as
() acting on a set is equal to the set of () acting on the elements of that set
or even more succinctly
The permutation action is pointwise.
Write for functional composition. So maps to (()).
().
The proof is by -induction.
By definition if then ().
Suppose . Then by definition of the permutation action and by the inductive hypothesis
Recall that ranges over predicates of ZFA. Write () to range over predicates which mention at most , . . . , as free variable symbols.
If () is a predicate of ZFA set theory then
is always provable.
As a corollary, () and () are interchangeable in proof and in validity on models.
We work by induction on the syntax of .
implies follows directly from the fact that by definition. The reverse implication is easy using , the inverse of .
Similarly, if and only if .
If () is of the form then we may easily use the inductive hypothesis.
Likewise if () is , or is of the form , we may easily use the inductive hypothesis.
is provable, so if and only if , and if and only if , and similarly if and only if and if and only if .
The result follows.
As a corollary we have:
If () is function (not a function-set) from the set universe to itself then
is always provable.
In set theory, we specify using a predicate () such that (() (() () ))
Dept. of Computer Science, Heriot-Watt University, Riccarton, Edinburgh EH14 4AS, UK
E-mail address: murdoch.gabbay@gmail.com
Dept. of Mathematics and Computer Science, Eindhoven University of Technology (TU/e), P.O. Box 513, 5600 MB Eindhoven, The Netherlands
E-mail address: aad.mathijssen@gmail.com
Notes
1The (#X) rule excludes the empty permutation Id. While there is no mathematical reason for this, there is a nice computational one: the algorithm obtained by reading rules bottom-up, must terminate. ↩
2A proof by induction on derivations is possible, but longer. ↩
3If already Φ Ψ ∆then renaming to in Π is not strictly necessary. ↩
4It appears convenient to prove freshness weakening first separately; we do not want to weaken Φ and Ψ to and until we have renamed to , in a moment. ↩