Some Formal Considerations on Gabbay’s Restart Rule in Natural Deduction and Goal-Directed Reasoning
Michael Gabbay and Murdoch Gabbay
1 Introduction
In this paper we make some observations about Natural Deduction derivations [Prawitz, 1965, van Dalen, 1986, Bell and Machover, 1977]. We assume the reader is familiar with it and with proof-theory in general. Our development will be simple, even simple-minded, and concrete. However, it will also be evident that general ideas motivate our examples, and we think both our specific examples and the ideas behind them are interesting and may be useful to some readers.
In a sentence, the bare technical content of this paper is: Extending natural deduction with global well-formedness conditions can neatly and cheaply capture classical and intermediate logics.
The interest here is in the ‘neatly’ and ‘cheaply’. By ‘neatly’ we mean ‘preserving proof-normalisation’,1 and ‘maintaining the subformula property’, and by ‘cheaply’ we mean ‘preserving the formal structure of deductions’ (so that a deduction in the original system is still, formally, a deduction in the extended system, and in particular it requires no extra effort to write just because it is in the extended system).
To illustrate what we have in mind consider intuitionistic first-order logic (FOL) [van Dalen, 1986] as a paradigmatic example of a formal notion of deduction. A natural deduction derivation (or deduction) is an inductively defined tree structure where each node contains an instance of a formula. A deduction is valid when each successive node follows from its predecessors in accordance with some predetermined inference rules.
A particular attraction of Natural Deduction is its clean and economical presentation. Here for example are deduction (fragments) proving from and , and (
Of interest is also the Curry-Howard correspondence [M. H. B. Sorensen, 1998, Barendregt, 2000]: these deductions have a natural notion of proof-normalisation. As is well-known, studying proof-normalisation is an important first step for giving deductions semantics, for example arrows in Cartesian-Closed Categories [Taylor, 1999], sets-and-functions-between-them, or normal forms in functional programs [M. H. B. Sorensen, 1998].
Now consider classical FOL. We can express it in Natural Deduction style by adding the law of excluded middle or double-negation elimination to intuitionistic FOL:
However, these rules compromise proof-normalisation and are in that sense unsatisfactory (computational semantics of deductions in classical logic are a research area in their own right, see [Coquand, 1996] for a solid survey; we do not discuss this huge field here).
So how to recover normal forms? Gentzen’s elegant solution [Gentzen, 1934] was a multiple-conclusioned logic. We are so familiar with this idea nowadays, we may forget that this is an expensive option in the sense that we have to add explicit context and co-context everywhere. For example, the deduction-fragments above become:
(In practice we might prefer left- and right-introduction rules, but that is not important here.) So to do classical FOL we have to pay at every stage of the deduction by threading Γ and Δ through every part of the deduction, even the purely intuitionistic parts inherited from the intuitionistic core of the logic. (This is analagous to emulating global state in a purely functional programming language by threading it through function calls [Peyton-Jones, 2001].)
Now for our proposal. We extend intuitionistic FOL with classical restart, which is the following Natural Deduction rule:
This is not a misprint. From we may proceed to .
The side-condition, of course there is one, is that below every occurrence of restart from to , there is (at least) one occurrence of . For example is not a valid deduction, but the following deduction is valid:
The restart at is justified at . The conclusion of this deduction is Peirce’s Law, a famous classical tautology, and we have just proved one half of the next theorem.
Natural deduction has a notion of state given by the undischarged assumptions. Although Restart insists we return to , on our return we may find ourselves in a more clement state with respect to the undischarged assumptions. This turns out to give precisely the extra deductive power of classical logic:
Propositional Intuitionistic Logic plus () has the same entailment relation as Classical Logic.
The proof is elementary; one half follows from the derivation of Peirce’s Law above. We give the other half in the next section (see also Theorem 2 on page 24).
So if we impose global well-formedness conditions on Natural Deduction derivations, then we have a way of strengthening a logic ‘cheaply’. There is a bit more: it is ‘neat’ too and proof-normalisation is inherited in a natural way, and we shall explore that briefly in the next section.
In conclusion: There are (at least) two techniques to imposing side-conditions on the form of a deduction. One is to build them in as sequents at every stage, another is to impose them globally on a (natural) deduction. Sometimes these side-conditions are easy to express in both techniques. For example:
Natural Deduction: In -introduction may not occur in assumptions on which depends.
Sequents: In -left-introduction may not occur in Γ.
Natural Deduction: In -introduction must occur precisely once (to obtain a ‘linearity’ condition on logical implication).
Sequent Calculus: In -right-introduction , Γ is a multiset and comma denotes multiset union.
An interesting historical example where Natural Deduction seemed to do better than sequent systems was Prawitz’s natural deduction system for the modal logic S5 [Prawitz, 1965] for which the obvious sequent system does not have cut-elimination (an issue addressed later by [Braüner, 2000]). Conversely Natural Deduction could not neatly (in the sense we define) capture classical logic, until now:
Sequent Calculus: Sequents are multiple-conclusion Γ Δ (for classical logic).
Natural Deduction: We propose: Restart.2
A little history: A rule corresponding to Classical Restart was invented by Dov Gabbay [Gabbay and Reyle, 1984, Gabbay, 1998, Gabbay and Olivetti, 2000b] in the framework of goal directed deductions; these are for proof-search and the rules are read bottom up (we discuss this further below). As a bottom-up goal-directed rule, restart is: at a goal we can ‘restart’ at any previous goal we have considered. The second author then re-presented the same rule top-down in Prawitz natural deduction [Gabbay, 2004].
2 Classical Restart
We begin by studying in detail Intuitionistic Logic (IL) augmented with our restart natural deduction rule. We show it has the same derivability relation as Classical Logic (CL); We prove that the standard proof-normalisation procedure for Natural Deduction is preserved; We then consider consider restart in other deduction formats than natural deduction.
2.1 Proof that IL+(Restart)=CL
For simplicity we consider just the propositional case. Fix a set of atomic formulae . Formulae are defined by the grammar3
The Natural Deduction rules of IL are standard:
Other connectives such as and are possible.
A deduction of IL is formed from (), (), (). Call a proto-deduction a deduction formed as just described, but also with (). A proto-deduction is
valid when it satisfies the condition that under every restart there is a later instance of . We represent this in the following diagram:
Let Classical Logic (CL) be IL augmented with Peirce’s Law (() ) for all and . We have already seen how to use () to prove Peirce’s Law, now we consider the converse.
Any application of () as above may be replaced by
This proves Theorem 1, and in view of this we may call () Classical Restart.
2.2 Proof-normalisation
Unlike adding Peirce’s Law, adding () to IL does not compromise proof-normalisation. The essential cases are as before, for example:
The only possible problem is when above justifies one or more instances of () in the deduction above; then restructure them as follows:
Now each of the problematic instances of () is justified one line further down, by B rather than , and we can proceed with elimination of the essential case. Note how Π is teleported deep inside the deduction.
More generally, in the presence of conjunction and disjunction, we can always restructure a deduction so that no formula both completes a restart rule and is the major premise of an elimination rule. Schematically, we can replace
with this
and now the premise of the restart is and its side condition is met by a formula one step closer to the conclusion (so we may conclude that ultimately, we can restructure the deduction so that no formula both is the major premise of an elimination rule and validates a previous application of restart).
Notice also that we can always restructure a deduction so that the conclusion of an application of (or if we extend the results to the quantified case) is also not the major premise of any elimination rule.4
We can now complete a normalisation argument using familiar methods, we sketch the argument here. Say a segment is a sequence of occurrences of a formulae , where each is an instance of the same formula , and is a minor premise of a rule the conclusion of which is . Say a segment is maximal when is the conclusion of an introduction rule, and is the major premise of an elimination rule. Notice that since we can always restructure a deduction so that no major premise of an elimination rule is also the conclusion of (or ) then we can assume that any maximal segment is a sequence of only two formulae. But then since we may always restructure a deduction so that no major premise of an elimination rule is necessary to validate a previous application of restart, we may remove the maximal segment altogether (as shown by the essential cases above).
Additionally, we may neaten up a deduction by thinking of () as an introduction rule and simplify () followed by an elimination rule as we would any essential case:
We do not simplify restart in the minor premise ( above); this destroys confluence of the reductions, we discuss this later.
Disjunction. Our syntax in (2.1) does not have disjunction but later in this paper it will be convenient to suppose we do. The natural reduction is as follows:
Again, a similar simplification is possible if a restart terminates either of the two minor premises to , but adding it would destroy confluence.
2.3 From restart to multiple conclusions
Suppose we have a deduction where the side conditions of some restarts, say from members of Δ, above have not (yet) been met. We can write this as a sequent Γ ; Δ (the predicate is ‘active’; a minor tweak of standard sequents, see below). We apply the restart rule from to to obtain this deduction tree
Now we describe this new deduction tree as Γ or just Γ . We can construct a new sequent system (with the semicolon as an additional structural entity) with rules
The second of these two rules captures the side condition ‘provided is deduced again later on’. If we add rules for the other connectives we obtain a sequent system for classical logic. For example:
Here is a (well-known) deduction of Peirce’s law:
In the usual multiple conclusion sequent calculus the conclusion is not split as above into an ‘active formula’ and a set of ‘outstanding formulae’. This extra structure imposes no restrictions since we can easily change the active formula:
Thus we may interpret the sequent Γ ; Δ semantically just as we would an ordinary multiple conclusion logic:
If the Γ are true and the Δ are false then is true.
or even
If the Γ are true then so is at least one of
Similarly we may understand a deduction tree as a deduction of from the assumptions of Γ and further assumptions of the negations of the premises of restarts that do not have their side conditions met.5
The reader may recognise that the observations of this subsection and the last correspond, via the Curry-Howard correspondence, to the -calculus [Parigot, 1992]. In fact (using the terminology we have developed) the -calculus only allows restarts from any to . Also our proof-normalisation procedure is not restricted at all to following that specified by ; a restart from to need not necessarily be tied to a particular later instance of , and we can choose arbitrarily from which to teleport; so the system here is a little more general.
Of course, all this is not limited to first-order logic. Indeed restart as described is valid in the presence of any abstract machine with state, and perhaps investigating ‘stateful automata with restart’ belongs to interesting future work. We return to this in the Conclusion.
3 Restart in frameworks other than Natural Deduction
3.1 Restart in linear natural deduction
We have formulated () for a Prawitz style natural deduction system. Its tree structure makes dependency between two formulae easy to track, being a matter of whether there is a path in the tree between them. () as discussed so far exploits this. For example in this deduction
formulae occurring between and may be said to depend on that particular application of restart. We do not have a full deduction until this dependency is discharged (until occurs again).
In a linear natural deduction system, dependency is harder to track. When we extend with restart we must extend whatever mechanism we have for handling dependencies to take the new rule into account.
Consider adding restart to a Lemmon style natural deduction system. Each formula in the deduction has three sets of labels (this is standard): a line number; the line numbers of the premises if it is the conclusion of a rule; and the line numbers of the assumptions it depends on. Here is a deduction of ():
The ‘deduction rule’ () is the following schema:
We say ‘schema’ because the premises (lines and ) can occur at some distance above the conclusion (line ). The assumption is discharged by removing its line number from the set of dependency labels at line , and this is how dependencies are tracked.
We say that at line depends on at line when the sets of dependency labels are at line and at line (i.e. occurs as an assumption and has ’s line number in its dependency column). So now we have Γ when there is a deduction in which there is a line containing that depends only on elements of Γ.
To add restart, extend labels with a dependency label () where is for ‘restart’ and is the line number of the premise. We then add two rules, one for the restart:
. . . and one for the side condition that the premise of the restart reoccur:
So for example we can now deduce Peirce’s law:
The restart rule looks less magical now, since these rules are so like a rule for indirect proof; () resembles a label for , (1) resembles a rule for deducing B from A and , and (2) resembles a rule for deducing that if follows from then we can conclude without a dependency on . It is not hard to translate between deductions using the two rules above, and deductions using Indirect Proof or Peirce’s Law.
In Prawitz form, restart is interesting because we get a normalising deduction system for classical logic from an intuitionistic one with no structural changes (labels, multiple conclusions). In linear natural deduction systems, where dependency is tracked by labelling anyway, this advantage is, if not exactly lost, certainly less apparent.
3.2 Goal-directed deduction with restart
A striking formulation of the restart rule is the original one from [Gabbay, 1990]. This is in terms of Goal-Directed reasoning which we can understand here as a Fitch style natural deduction system such that all subdeductions have a goal which must be met. That is, a subdeduction is not open-ended, but can be closed only when the goal is reached. For example, here is a Goal-Directed deduction that [ ()] [() ()]:
Notice that an individual subdeduction is completed only when its goal is reached, at which point we can terminate the subdeduction and introduce an implication. The restart rule then becomes an additional rule on when a subdeduction is completed.
A subdeduction with a hypothesis and goal ? may be terminated (introducing an implication ) by the deduction of not only its goal, but by the deduction of any previous goal.
For example here is a Goal-Directed deduction of Peirce’s Law:
We get line 5 by restarting the goal ? to a goal ? (and declaring ourselves satisfied since that is what we have at line 4); instead of terminating the subdeduction with , we terminate it with the previous goal .
It is not hard to see that this restart is sound: we observe that we can obtain a valid deduction in a system with an indirect proof rule by replacing any goal ? with an additional assumption and then using the principle of indirect proof. Any previous ’goal’ is really an assumption that the goal is false. So note in the example above, reading ? as , that the introduction of is valid, as we can deduce from and the previous assumption that . Because ? was a previous goal, when is deduced again later in the deduction (line 6), we may consider the assumption of (i.e. ?) as being discharged by the Principle of Indirect Proof:
The system of Goal-Directed logic [Gabbay, 1990, Gabbay and Olivetti, 2000a] is mainly for implication- and quantifier-fragments of various logics.
4 -depth restart
Say a Kripke model has height bounded by when for all series of worlds , if for 1 then an exists with (“the model has depth at most ”). Here denotes the Kripke accessibility relation.
A characteristic axiom scheme for models of depth 1 is 1() (() ) . A characteristic axiom scheme for models of depth + 1 is taken from [Gabbay, 1981] and given as follows:
For example 2((() ) ) ) .
4.1 A natural deduction restart for bounded height
An appealing intuition (we do not make it formal) behind -depth restart is that each is proved at world , where is the final world. Whence the condition on discharge after handles, which corresponds to a restriction not to descend below until we have justified the restart at that world. The restart at the final world is an ordinary 1-depth restart, jumping from to an arbitrary is reasonable because there is no future world and so any holds in any future world.
There is an extra side-condition on -depth restart. Say that the restart is handled by each re-deduction of (so each application of an -depth restart rule gets handled times). The side condition is this
In -depth restart no assumption or application of restart in the deduction of may be discharged or handled under before has been handled
We can prove ( ()) using 2-depth restart, as illustrated. The ‘deduction’ on the right of using the 2-depth restart rule is invalid because it discharges at 2 before at .
Proof-normalisation is fairly evident and similar to the 1-depth case (ordinary restart); an elimination rule following in the lower part of the deduction is teleported to the in the upper part of the deduction. Normal forms are unique. We omit the proof of this, which is not hard.
5 Soundness of -depth restart
We shall argue that any deduction containing applications of -depth restart may be replaced by a deduction, of the same conclusion, using the -depth axiom instead. We shall do this by showing how to replace any application of -depth restart with a use of the -depth restart rule.
The construction, although simple to the mind, is unfortunately not so simple to the eye. Take any application of -depth restart:
and we can begin to rewrite it as follows:
We can routinely replace all applications of -depth restart with this ‘rule’:
If there is no (i.e. if = 1) then and are empty and we have replaced the -depth restart with an appeal to Peirce’s Law.
However, if 1 then we must make further replacements. To save space, let be short for ()
We may replace any application of
so that we use instead an application of
in a similar way:
Notice that the side condition ensures that no assumption in is discharged in so we can bring out and across from underneath without affecting the deduction.
Ultimately, after repeated applications of this we will have replaced all applications of -depth restart by this:
and since there is no this is simply
which is just an appeal to the -depth Kripke model axiom.
6 Completeness of -depth restart
Notice that within an application of an + 1-depth restart rule we can find an -depth restart rule (considering only and ignoring ). We have already shown that any instance of Peirce’s law 1 can be derived using 1-depth restart. We can now argue that can be derived using the -depth restart rule.
The argument is by induction on . Suppose for the induction hypothesis that the -depth restart rule can be used to derive the -depth axiom, where 1 and 1.
where is (). Now we can edit it in the following way, first we add an extra premise:
and now we continue on from as follows
and since is () then (() ) is really () which is the -depth axiom. Furthermore we have converted the -depth restart into an instance of + 1-depth restart. This completes the induction.
6.1 Goal-directed -depth restart
-depth restart can be formulated in Goal Directed reasoning as well. Say that a goal ? is embedded in another goal ? when ? is a goal previous to ?,6 and occurs, not as a goal, somewhere between ? and ?.
Schematically, ? is embedded in ? when this happens:
The -depth goal directed restart rule is this:
A subdeduction with a hypothesis and goal ? may be terminated (introducing an implication ) by the deduction of not only its goal, but of a previous goal ? provided that there are goals ?? such that ? is embedded in 1 and each is embedded in .
So for example, here is a deduction using 2-depth restart of (( ())
The application of restart was to complete the Goal ? by completing instead the previous goal ?. Notice that above the goal ? is an occurrence of and above that is a goal ?. So ? is embedded in at least one other goal. This legitimises they use of 2-depth restart.
6.2 Soundness of goal-directed -depth restart
It is a somewhat tedious matter to show how to convert a deduction using the goal-directed -depth restart rule into a deduction using the -depth axioms. We shall not describe the construction in detail here, mainly because it is similar to the construction proving soundness of the natural deduction -depth restart rule.
But a sketch-proof of why the rule is sound may be found by observing that the goal-directed -depth restart rule meets the conditions of the natural deduction -depth restart rule.
To apply the goal directed restart rule, we act as if we have achieved a goal ? when in fact we have deduced only . Effectively we do this:
But was not just any formula, it was a previous goal, which means it will have to be met at a later point for the deduction to be complete:
But is embedded in a goal ?, which means that we have to complete the goal ? after we have achieved goal ?:
and also we have already deduced when deduced :
but discharge in goal-directed reasoning is done only by completing goals, it follows (since was deduced in between the goal ? and the prior goal ?) that no assumption on which depends is discharged (has its goal met) before is deduced again (that is, before the goal ? is achieved). The same holds if ? must be embedded in further goals:
This is precisely the side condition on the +1-depth natural deduction restart rule.
7 Hash logic
7.1 Natural deduction for hash logic
We can internalise the restart rule and use it as an elimination rule for a connective. Here are the rules for a unary connective #.
Say an application of (#) is completed when is deduced again below it. Until is deduced again the application of (#) is incomplete.
The side condition on the rule (#) is this:
() no (occurrence of an) assumption on which # depends may be discharged until is re-deduced and
() no (#) rule on which # depends is completed until is re-deduced. So the rule is this
where nothing on which # depends may be discharged until the (#) rule is completed and no (#) rule that is incomplete at # is completed until re-occurs.
We should be liberal with our interpretation of these rules. We should not regard the rules as requiring that an application of the (#) rule is completed by the first re-occurrence of its minor premise that is deduced again. The rule demands only that the minor premise is deduced at some later point, it may appear many times before we can regard the rule as being completed.7
To see what the Hash rules do, note the following deduction of ():8
Furthermore, we can replace instances of (#) with instances of this # (( )):
may be replaced by
And the side condition ensures that moving Π out from underneath does not invalidate the deduction.
We have shown that for every deduction using (#) there is a deduction, of the same conclusion, using an appeal to an axiom schema # ( ()) instead. Furthermore, it is not hard to see that we can replace the (#) rule throughout a deduction by an appeal to the axiom schema # and (). Finally, we can remove all occurrences of the # rule and replace them with appeals to this axiom #() (# #).9
It is shown in [Gabbay, 1981] that adding the axioms
to intuitionistic logic gives (the new connective) # the following truth conditions:
# is true at world (in a Kripke model) when is true in all s.t.
Given this, # means that the Kripke model has a depth of at most worlds.10
I shall not discuss the hash logic much here. We shall note that the additional rules for # preserve normalisation.
7.2 Normalisation for hash logic
The essential case for # is only slightly more complex than for the other connectives. Suppose # is introduced, subjected to a number of applications of #, and then eliminated. First note that two (and hence any number) of successive applications of (#)
may be reduced to just one:
and now an introduction, permutation ((#) rule) and subsequent elimination of #
may be reduced to:
and if any of the # are introduced by (#) then they may be dispatched similarly.
The normalisation argument then proceeds in almost identical fashion to the argument for restart. We must argue that we can always restructure the deduction so that the major premise of an elimination rule never be required to complete an application of restart. In such a case we must teleport the elimination rule away, so this
gets replaced by this:
and we must treat any incomplete restarts in the minor premises of Π as being completed only after (even if the appropriate formulae happen, by chance, to re-occur in ).11
7.3 Goal directed Hash logic
The Goal-directed reasoning of [Gabbay and Reyle, 1984, Gabbay, 1998, Gabbay and Olivetti, 2000b] does not have rules for disjunction. However, we can formulate the axioms for # in terms of implication. It is not hard to show that we obtain equivalent logics when using the axiom # [(() ) ] instead of # ( ()). For example, here is an argument that there is a deduction of ( ()) if we add (() ) as an axiom, for brevity let be shorthand for [ ()].
Here are the rules for the # operator in goal directed logic. Firstly is the obvious introduction rule:
We may infer # if we have previously inferred .
and now the less obvious elimination rule:
We may infer from an instance of if we have a goal ? prior to that instance of and we have deduced # prior to that goal ?.
Schematically this rule looks like this
Line is inferred from by the rule for #, prior to is a goal ? and prior that is
To see the rule is sound observe that we can convert it into a deduction that uses an instance of the axiom # [(() ) ].
Looking within this construction we can see an alternative proof that the simple goal-directed restart rule is sound that proceeds by replacing applications of restart to an appeal to Peirce’s law rather than the principle of indirect proof.
To ensure that the goal-directed hash calculus is complete we need only add the following rule (the equivalent of the # rule) which we represent here schematically:
To show completeness we must use the new rules to derive the three axioms # [(() ) , # and #() # #, this is left for the reader.
8 Restart in first order logic
8.1 Quantifier rules
We have concentrated on restart for propositional logic, but there is no reason not to do exactly the same with predicate logic.
In first order logic, the restart rule remains unchanged (to extend intuitionistic to classical logic), but the side conditions on and rules must be modified a little.12
A formula is required to handle a restart at (a node containing an instance of) in a deduction when there is a (prior) application of restart that requires to be deduced again but (an appropriate instance of) has not yet been deduced again.
We obtain these side conditions systematically as follows: in the soundness proof of restart (page 4) we convert the instances of restart into an appeal to Peirce’s law. That is, we show that for every deduction using the restart rule there is a direct way of replacing the appeal to restart with an appeal to Peirce’s law. Actually, it is not hard to see that we can replace the applications of restart with appeals to a particular instance of Peirce’s law: (() ) .
The deduction (segment) with which we replace the application of restart contains the assumption, and subsequent discharge, of () . This assumption of () (which formerly did not appear in the deduction at all) may interfere with the side conditions of any applications of () or () below it. Schematically, if we replace an application of restart
by this
then any applications of () or () in Π may become invalidated if or is free in . The new side condition ensures that this does not happen as the application of restart in question is incomplete throughout Π and so no application of () or () makes critical use of any or that is free in .
It is now not hard to derive the following theorem:
Intuitionistic FOL plus () has the same entailment relation as Classical FOL.
We have just shown the left right direction of this theorem, and the right left direction is shown in the same way as with Theorem 1
Normalisation follows by an easy extension of the arguments of Section 2.2. For example here is the reduction case for the existential quantifier (given the familiar side condition on we may suppose that no variable in is bound in
Where is obtained from by making the following replacements:
1. First replace any constant or variable symbol in that is not free in any assumption of but is free in assumptions of by some other variable or constant symbol that is not free in any assumptions of .
2. Finally, replace by throughout
It is left to the reader to verify, bearing in mind the rules for the quantifiers, that may be appended to the end of to yield a valid deduction.
There is much interesting research to be done in the relation between more complex restart rules, hash logic and first order intermediate logics. Restart seems quite robust and suggests in a natural way the side-conditions and reduction rules necessary to make things work. We now continue with another example.
8.2 Endpoint Restart
Consider this restart rule, call it endpoint restart:
which allows us to infer from provided we infer again later and then still later. In relation to the side conditions on the universal quantifier, if is free in , then we cannot introduce by until after is deduced again (but we can do so before is deduced again as is not free in ).
This more complex restart rule allows us to deduce the following formula
and the application of is legitimate because the requirement to re-deduce has been met (although the application of restart is not fully complete as must be deduced). Furthermore observe that for any deduction using the new restart there is a deduction of the same conclusion using the axiom ((() ) ). We can convert any application of endpoint restart thusly
But it is a fact of intuisionistic logic that
and so we can convert any applications of endpoint restart into an appeals to .
Adding as an axiom to intuitionistic logic yields an intermediate logic complete for Kripke frames where each world has an endpoint accessible to it (see [van Dalen, 1986, Gabbay, 1981]), that is:
Notice that we can already express such a condition using the hash operator #. And indeed, we can deduce from # (see 8.3).
Interestingly however, we cannot deduce # if we add as an axiom. To see this, consider a Kripke frame with a set of worlds and an accessibility relation such that for every , i.e. the accessibility relation is an equivalence class on . In such a frame is clearly true at all worlds, but # is not true at any world.
What has happened is that does not force a Kripke frame to have endpoints, but it does force a frame into something indistinguishable from one with endpoints (a frame where there are always worlds where all propositions are determined). But with the additional expressive power of the # operator we can make such distinctions and so, in the presence of #, the intermediate logic with as an axiom (named in [Gabbay, 1981]) is not complete for frames where every world has an accessible endpoint. It follows that and endpoint restart are complete for Kripke frames where every world has an accessible endpoint only if the language does not contain #.
Normalisation of endpoint restart follows almost exactly as with ordinary restart: because has no introduction rule, the extra condition that be deduced after has no effect on the normalisation argument.
The goal-directed formulation of endpoint restart is this
We may replace a goal ? with a previous goal ? (i.e. act as if we have deduced when we have really deduced ) provided that there is a goal ? previous to the goal ?.
To see this work it is convenient to have the following introduction rule for the universal quantifier:
That is, we assume nothing and set [] as our goal where is new to the deduction, then when we reach that goal we may conclude . Now, here is a deduction of using goal-directed endpoint restart:
What is interesting about this particular restart rule is that it does not mention quantifiers at all. Looking carefully at the rule we can see that it has no effect on the propositional fragment of intuitionistic logic. Without quantifiers it corresponds to an appeal to the double negation of Peirce’s law which is an intuitionistic theorem.14 With quantifiers endpoint restart corresponds to an appeal to the double negation of a universal generalisation of Peirce’s law (and that is not an intuitionistic theorem).
8.3 More fun with hash
Endpoint restart was not discovered by accident, it was noticed by externalising the effect of adding # as an axiom. That is, # internalises into intuitionistic logic the deduction structure of restart. And so more complex formulae involving hash internalise more complex deduction structures. It is interesting to see what restarts we get if we attempt to put these structures back into the external structure of natural deduction (in the form of more complex restart rules). It is not hard to see how the axiom # justifies endpoint restart:15
and we obtained endpoint restart from considering that deduction. We suspect many more restart rules can be obtained in this manner.
9 Conclusions and future work
It is always nice when we can extend a system without having to reengineer our existing material (say it is inherited). For example it is nice to be able to extend a logic in such a way that deductions of the unextended logic are still deductions of the extended logic, and valid proof-reductions of the unextended logic are still valid proof-reductions of the extended logic.
Examples of this principle in action are not hard to find wherever people have invested effort in a particular system, and then find they want to extend it. Besides saved effort, the chances are that if formal structure is preserved, so may the good properties (e.g. proof-normalisation!).
This paper presents a robust and elementary method by which logical derivability may be extended, without affecting the structure of deductions or their normalisation. We have applied it here both to intuitionistic Natural Deduction and to Gabbay’s Goal-Directed Deduction. We consider consider restart-like methods of obtaining interesting and sometimes exotic logics. This also gives some new perspectives on their computational content.
On a philosophical note we are following work of Gentzen, Prawitz and Dummett (to name a few) that a deduction theoretic account of the meaning of a logical connective can be found in its introduction and elimination rules (intro/elim pair). In this view, the intro/elim pair of, say implication, define its meaning. A useful definition of meaning is an intro/elim pair which normalises in the context of the rest of the logic. As we have seen, natural deduction plus restart is convenient for defining classical logics in a way that, for example, natural deduction plus double negation elimination is not.
We made it obvious that Classical Restart corresponds to multiple conclusions, but it is not identical to multiple conclusions, any more than Natural Deduction is identical to sequent systems. Indeed, we can argue that Restart is the true meaning of multiple conclusions!
There is a much work on ‘exotic’ deduction systems for logics a little off the beaten track. We have dabbled in this in the paper with the hash logic and with -depth restart. Hypersequents, introduced by Arnon Avron [Avron, 1996], are another example in the literature. Amusingly hypersequents go in entirely the opposite direction to this paper; instead of doing away with sequent structure, they enrich it. And yet they seem to arrive at similar applications to us:
Ciabattoni and Ferrari [Ciabattoni and Ferrari, 2000] present deduction-systems for logics complete for Kripke models with restrictions on their geometry, including bounded depth like our -depth restart but also bounded cardinality, bounded width, and so on — this is much more general than what we managed.
The connection between our determinedly Natural Deduction restart rules, and the superficially quite different determinedly Sequent Calculus hypersequent systems, is in the connection between the proof-teleportation which we have seen in this paper, which arises naturally from restart proof-normalisation, in which fragments of deduction are copied (teleported) deep inside intermediate parts of other deductions; on the other hand hypersequents on the other hand derive their power by allowing us to rearrange and copy assumptions inside intermediate steps in the sequent deduction. In the first, we move a fragment of deduction to a new context, and in the second we move the new context to be around a fragment of deduction — in the end, it seems to come to almost the same thing.
Hypersequents seem to be more general and expressive than restart rules in that they express a wider range of intermediate logics. Yet Restart rules are nice when they work, they retain the simple Natural Deduction presentation and so are ‘cheap’ in the sense of the Introduction. This can be seen in the ease by which we can internalise the restart rule into the hash logic which is a conservative extension of classical logic (this follows from the normal form theorem on hash logic). The hash logic itself is interesting and further work into the extra expressive power and computational content of #, and connectives axiomatisable using #, seems promising. Indeed, as far as we are aware, the intermediate logic (see section 8.2) has not been formulated in terms of hypersequents.
Viewed computationally, Classical Restart leads immediately to a -calculus very similar to Parigot’s -calculus (restarts-yet-to-be-justified, and the current goal, correspond to multiple conclusions). Parigot’s great accomplishment was to ‘pull out of the air’ the -calculus in 1992, and in retrospect we now see that Dov Gabbay had pulled it out of the air too, in 1984 and in a different field as goal-directed restart. This should serve as a taster to interesting calculi that can be produced for the predicate case, for hash logic, and for any other restart rule.
Perhaps the most striking presentation of restart rules is still in the original presentation in goal directed formulations. The restart rule is somewhat obvious in the rigorous and highly annotated structure of (Lemmon style) linear natural deduction systems. The effects of restart and hash rules in their natural deduction formulations are unexpected at first, but then intelligible. But in their goal-directed formulations the restart and hash rules seem, at least to the authors of this article, almost magical. The discoverer of the restart rule, who spotted it directly in its goal directed formulation, is surely to be commended on such a leap of the imagination.
Acknowledgements
We are grateful to Agata Ciabattoni, Alexis Saurin, and David Richter, for useful comments, and to two anonymous referees.
BIBLIOGRAPHY
[Avron, 1996] A. Avron. The method of hypersequents in the proof theory of propositional non-classical logics. In W. Hodges, M. Hyland, C. Steinhorn, and J. Truss, editors, Logic: from foundations to applications. Proc. Logic Colloquium, Keele, UK, 1993, pp. 1–32. oup, New York, 1996.
[Barendregt, 2000] H. P. Barendregt. Lambda calculi with types. In S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, Volume 2, pp. 117–309. OUP, 2000.
[Bell and Machover, 1977] J. Bell and M. Machover. A course in mathematical logic. North-Holland, 1977.
[Braüner, 2000] T. Braüner. A cut-free gentzen formulation of the modal logic s5. Logic Journal of IGPL, 8(5):629–643, 2000.
[Ciabattoni and Ferrari, 2000] A. Ciabattoni and M. Ferrari. Hypertableau and path-hypertableau calculi for some families of intermediate logics. In Automated Reasoning with Tableaux and Related Methods (Tableaux’2000), volume 1847 of LNAI, pp. 160–175, 2000.
[Coquand, 1996] T. Coquand. Computational content of classical logic. In P. Dybjer and A. Pitts, editors, CLICS Cambridge Summer School., 1996.
[de Groote, 1995] P. de Groote. A simple calculus of exception handling. In LNCS, volume 902, pp. 201–215. Springer, 1995. TLCA’95.
[Gabbay and Olivetti, 2000a] D. Gabbay and N. Olivetti. Goal Directed Algorithmic Proof Theory. Kluwer Academic, 2000.
[Gabbay and Olivetti, 2000b] D. Gabbay and N. Olivetti. Goal-directed Proof Theory. Kluwer Academic Publishers, 2000.
[Gabbay and Reyle, 1984] D. Gabbay and U. Reyle. N-prolog: An extension of prolog with hypothetical implications i. Journal of Logic Programming, (1):391–355, 1984.
[Gabbay, 1981] D. Gabbay. Semantical investigations in Heyting’s Intuitionistic Logic, volume 148 of Synthèse. D. Reidel, 1981.
[Gabbay, 1990] D. Gabbay. Algorithmic proof with diminishing resources part i. In CSL’90, volume 533 of LNCS, pp. 156–173. Springer, 1990.
[Gabbay, 1998] D. Gabbay. Elementary Logic: A Procedural Perspective. Prentice Hall, 1998.
[Gabbay, 2004] Michael Gabbay. Proof-Normalisation and Truth by Definition. PhD thesis, King’s College, London, 2004.
[Gentzen, 1934] G. Gentzen. Untersuchungen über das logische Schliessen. Mathematische Zeitschrift, 39:176–210 and 405–431, 1934.
[M. H. B. Sorensen, 1998] P. Urzyczyn M. H. B. Sorensen. Lectures on the curry-howard isomorphism. Technical Report 98/14, DIKU, 1998.
[Parigot, 1992] M. Parigot. Lambda-mu-calculus: An algorithmic interpretation of classical natural deduction. In LPAR’92, pp. 190–201, 1992.
[Peyton-Jones, 2001] S. Peyton-Jones. Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in haskell. In Engineering theories of software construction, Marktoberdorf Summer School, NATO ASI, pp. 47–96. 105 Press, 2001.
[Prawitz, 1965] D. Prawitz. Natural Deduction - A proof theoretical study. Almquist and Wiksell, 1965.
[Stalmarck, 1991] G. Stalmarck. Normalization theorems for full first order classical natural deduction. Journal of Symbolic Logic, 56:129–149, 1991.
[Taylor, 1999] P. Taylor. Practical Foundations of Mathematics. Number 59 in Cambridge Studies in Advanced Mathematics. 1999.
[van Dalen, 1986] 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, 1986.
Notes
1Perhaps in this paper we should call it ‘deduction-normalisation’ or ‘derivation-normalisation’ but, as the phrase is a common one, we shall use the term ‘proof-normalsation’ to refer to a property of deductions (the property of reducing to normal forms). ↩
2Methods of obtaining a calculus for classical logic that satisfies a normal form theorem are known. For example in [Stalmarck, 1991, Prawitz, 1965] the rule ....
is used. This rule may be considered as an elimination rule for , it is also known as the principle of indirect proof (). We confine discussion of this rule to a footnote because it is not purely structural, it cannot be formulated unless at least one of or is in the language. So for example we cannot use it to formulate the implication-only fragment of classical propositional logic which should have (() ) as a theorem independently of whether we have negation or in the language as well. We are interested here in the properties of Restart as a purely structural rule that makes the difference between intuitionistic, classical and intermediate logics. ↩
3Our results easily generalise to and . ↩
4So for example in the case of the existential quantifier ( is the formula obtained by simultaneously replacing all free occurrences of the variable in by the term ):
In such a reduction it may be necessary to replace (in the deduction of from ) by some other constant if occurs in . This is because of the side condition on (), see section 8.1. ↩
5Perhaps this subsection is too humbly titled. ‘No’, we can say: ‘a multiple conclusion sequent Γ Δ expresses the existence of a/any deduction from assumptions Γ with a conclusion Δ and incomplete applications of restart to formulae ’. This is philosophically more satisfying than an interpretation of multiple conclusions which assumes the logic has an explicit disjunction . ↩
6i.e. the subdeduction for which ? is a goal is a subdeduction (of a subdeduction of. . . ) the subdeduction for which ? is a goal. ↩
7So suppose we encounter something like this in the deduction
and the first application of (#) cannot be completed by the re-occurrence of (suppose it is the first) unless has already re-occurred. If the completed the second application of (#) then, even though has been deduced again, both application of (#) remain incomplete. ↩
8Here we use disjunction to harmonise our results with [Gabbay, 1981], but from the next section it can be seen disjunction is not essential to make the point made here. ↩
9The minor premise of (#) gives us that and so we have #() using the axiom # and then the # operator may be distributed across all implications using the axiom above. ↩
10Actually this is not true. The axioms for # considered in [Gabbay, 1981] are these:
and the semantics for # is that # is true at world (in a Kripke model) when either
(ii) is an endpoint and is true in .
But it is not hard to convert Gabbay’s proof into one that the axioms we present are complete for our simpler semantics. We find our simpler semantics much more convenient. For one thing we can express the hash operator of [Gabbay, 1981] using conjunction: #. Furthermore it is useful not to have # as necessarily false, for we can use it (on our semantics for #) to express the property of being an endpoint (according to our semantics, # is true at iff has no worlds accessible to it other than itself). ↩
11Note that for a hash logic normalisation theorem we must work with a slightly different notion of a segment: a segment is either () a sequence in a deduction where each is an occurrence of or () a sequence # # where each # is deduced from by the # rule. ↩
is the formula obtained by simultaneously replacing all free occurrences of the variable in by the term ↩
13(() ) is a propositional classical theorem and so ((() ) ) is an intuitionistic theorem, and therefore so is its universal generalisation etc.
14Also, propositional intuitionistic logic is complete for finite Kripke models. So the condition that every world has an accessible endpoint is trivially met in the propositional case. ↩
15And since endpoint restart can be used to deduce it follows that # deduces . ↩