LJT (G4ip) proof search

Originally invented by Roy Dyckhoff in Contraction-free sequent calculi for intuitionistic logic. G4ip is the sequent calculus derived from G3ip.

Also see an implementation by Michel Levy: http://teachinglogic.liglab.fr/
I traced down the code from the file preuve.ml ("proof" in French) in the DN1 variant.

---

Let context

$\mathrm{\Gamma }={\mathrm{\Gamma }}_0\cup {\mathrm{\Gamma }}_1\cup {\mathrm{\Gamma }}_2\cup {\mathrm{\Gamma }}_3$, where

• ${\mathrm{\Gamma }}_1$ is a set of atoms,
• ${\mathrm{\Gamma }}_2$ is a set of clauses of the form
  $b\to c$ where
  $b$ is an atom,
• ${\mathrm{\Gamma }}_3$ is a set of clauses of the form
  $(b\to d)\to c$,
• ${\mathrm{\Gamma }}_0$ is a set of formula of no restrictions.

Given a w.f.f.

$a$, decide whether

$\mathrm{\Gamma }{⊢}_{\mathrm{NJ}}a$. Usually initially

$\mathrm{\Gamma }=\mathrm{\varnothing }$.
Also give a witness if it is derivable.

Algorithm

• If
  $a\in \mathrm{\Gamma }$: Conclude "derivable" (
  $\mathrm{assum}$).
• If one of below conditions holds:
  1. $\mathrm{\perp }\in {\mathrm{\Gamma }}_0$ (
     $L_{\mathrm{\perp }}$), or
  2. there is some
     $x\in \mathrm{\Gamma }$ such that
     $x\to a\in \mathrm{\Gamma }$, or
  3. ${\mathrm{\Gamma }}_0$ contains either
     $\mathrm{\_}\wedge a$ or
     $a\wedge \mathrm{\_}$ (
     $L_{\wedge };\mathrm{assum}$),
  Conclude "derivable".

  Remark: modus ponens always holds by structural induction on

  $x$.

• Else, Try to pattern match
  $({\mathrm{\Gamma }}_0,a)$:
  • If
    $a$ is of the form
    $x\to y$, apply
    $R_{\to }$.
  • If
    $a$ is of the form
    $x\wedge y$, apply
    $R_{\wedge }$.

    Remark: after this stage,

    $a$ can only be

    $\mathrm{\perp }$, an atom, or a disjunction.

  • If
    ${\mathrm{\Gamma }}_0$ is non-empty, pick an element and pattern match:
    • an atom: Move it to
      ${\mathrm{\Gamma }}_1$ and recurse.
    • a conjunction: Apply
      $L_{\wedge }$.
    • a disjunction: Apply
      $L_{\vee }$.
    • an implication
      $y=g\to b$:
      Let
      ${\mathrm{\Gamma }}_0^{\prime }=({\mathrm{\Gamma }}_0\setminus \{y\})$, prove
      $g\to b⊢a$ as follows:
      1. Prove
         ${\mathrm{\Gamma }}_0^{\prime }\cup {\mathrm{\Gamma }}_{1..3}⊢g$, and then
      2. Prove (
         ${\mathrm{\Gamma }}_0^{\prime }\cup \{b\})\cup {\mathrm{\Gamma }}_{1..3}⊢a$.

      Why? It resembles MP, but I cannot find a term to describe this process.

      If either step is not derivable, pattern match
      $g$ and rewrite accordingly,
      • an atom: move
        $y$ to
        ${\mathrm{\Gamma }}_2$ and recurse.
      • a conjunction: apply
        $L_{\wedge \to }$. _{Lemma p10}
      • a disjunction: apply
        $L_{\vee \to }$. _{Lemma p11}
      • an implication: move it to
        ${\mathrm{\Gamma }}_3$ and recurse.
      • $\mathrm{\perp }$: remove
        $y$ and recurse. (why?)
  • Else
    ${\mathrm{\Gamma }}_0$ is empty. Try proceeding with the following steps in order.
    • Collect
      $\{p:p\in {\mathrm{\Gamma }}_1,p\to b\in {\mathrm{\Gamma }}_2\}$. If it is non-empty, apply
      $L_{0\to }$ on an element. If a proof fails, repeat this step on the remaining of them.
    • If
      ${\mathrm{\Gamma }}_3$ is non-empty, pick an element in
      ${\mathrm{\Gamma }}_3$ and apply
      $L_{\to \to }$. _{Lemma p13}
    • If
      $a$ is a disjunction, apply
      $R_{\vee }$ on either side.

      Remark: By the disjunction property, a disjunction is derivable if and only if either branch is derivable.

    • None of the above applies (
      $a$ is
      $\mathrm{\perp }$ or an atom).
      Conclude "not derivable".

      Remark: it is already not the case that

      $a\in \mathrm{\Gamma }$.

To apply a rule, to prove a statement, or to move/remove an element to a set means that to re-enter the procedure with the resulting context

${\mathrm{\Gamma }}^{\prime }={\cup }_{i=0..3}{\mathrm{\Gamma }}_i$ and formula.

The original algorithm describes everything as multisets for proving total correctness, but it seems that ordinary sets or lists suffices in practice.

Appendix

There are 8 proof rules in LJ. They are

$\mathrm{assum}$,

$L_{\mathrm{\perp }}$,

$L_{\wedge }$,

$R_{\wedge }$,

$L_{\vee }$,

$R_{\vee }$,

$L_{\to }$,

$R_{\to }$.

The 4 rules replacing the problematic

$L_{\to }$ are as follows:

$$\frac{\mathrm{\Gamma },P,B⊢E}{\mathrm{\Gamma },P,P\to B⊢E}(L_{0\to })\text{with }P\text{ atomic}$$

$$\frac{\mathrm{\Gamma },D,B⊢C\to D\mathrm{\Gamma },B⊢E}{\mathrm{\Gamma },(C\to D)\to B⊢E}(L_{\to \to })$$

$$\frac{\mathrm{\Gamma },C\to D\to B⊢E}{\mathrm{\Gamma },(C\wedge D)\to B⊢E}(L_{\wedge \to })$$

$$\frac{\mathrm{\Gamma },C\to B,D\to B⊢E}{\mathrm{\Gamma },(C\vee D)\to B⊢E}(L_{\vee \to })$$

The witness can be collected from the path an input has undergone recursively.

Some lemmas are used to convert the sequent calculus back to natural deduction proofs. They are listed below, naming after variables found in the original code:

• p10:
  $(c\wedge d)\to b⊢c\to (d\to b)$
• p11:
  $(c\vee d)\to b⊢d\to b$ (only the second branch)
• p13:
  $(c\to d)\to b⊢d\to b$ (only the second branch)

---

Questions:

1. Roy's paper did not give an explicit deciding procedure. Why this order of backtracking?
2. Will it always terminate?
3. When it rejects, how to prove that it has tried all paths?