Library Deduxit.Linear.FirstOrderIntuitionistic


The two-sided sequent calculus of first-order intuitionistic linear logic

This file is what a certificate's first-order intuitionistic statement rests on: read it to know what such a certificate claims. ill R Γ C says that the sequent Γ ⊢ C has a derivation in first-order intuitionistic linear logic, or in its affine variant when R adds weakening; without cut when Intuitionistic.icut R = false. R is the record Intuitionistic.irules of the propositional calculus.
The formulas and the rules are those of Intuitionistic, with predicates applied to terms (Terms) and the quantifiers ∀ and ∃, each with two rules:
  • ∀R and ∃L, with an eigenvariable that occurs nowhere in their conclusion;
  • ∃R and ∀L, with any closed term as the witness, eigenvariables included (they are constants outside the signature).
A quantifier binds the bound variable 0 of its body. Every left rule acts on the first hypothesis, and the cut on the first hypothesis of its second premise; the exchange rule ex_ir allows any permutation. The file derives nothing and assumes nothing. ill R Γ C is a Prop: it says that a derivation exists.

From Stdlib Require Import List Permutation.
From Deduxit.Linear Require Intuitionistic.
From Deduxit.Linear Require Export Terms.
Import ListNotations.

Section Formulas.

Context {symbol : Type}.
Local Notation term := (term symbol).

A first-order intuitionistic formula.
Inductive iformula : Type :=
| ivar : symbol → list term → iformula
a predicate p(t₁, …, tₙ)
1
A ⊗ B
A ⊸ B
⊤
A & B
0
A ⊕ B
!A
∀x. A, x the bound variable 0 of A
∃x. A
Substitutes the closed term u for the bound variable k of A; that variable is k at the top and one more under each quantifier. isubst 0 u A is the instance at u of the body A of ∀x. A or ∃x. A.
Fixpoint isubst (k : nat) (u : term) (A : iformula) : iformula :=
  match A with
  | ivar p l ⇒ ivar p (map (tsubst k u) l)
  | ione ⇒ ione
  | itens A B ⇒ itens (isubst k u A) (isubst k u B)
  | ilmap A B ⇒ ilmap (isubst k u A) (isubst k u B)
  | itop ⇒ itop
  | iwith A B ⇒ iwith (isubst k u A) (isubst k u B)
  | izero ⇒ izero
  | iplus A B ⇒ iplus (isubst k u A) (isubst k u B)
  | ioc A ⇒ ioc (isubst k u A)
  | iall A ⇒ iall (isubst (S k) u A)
  | iex A ⇒ iex (isubst (S k) u A)
  end.

Whether the eigenvariable a occurs in A.
Fixpoint ioccurs (a : nat) (A : iformula) : bool :=
  match A with
  | ivar _ l ⇒ existsb (toccurs a) l
  | ione | itop | izero ⇒ false
  | itens A B | ilmap A B | iwith A B | iplus A B ⇒ ioccurs a A || ioccurs a B
  | ioc A | iall A | iex A ⇒ ioccurs a A
  end.

The eigenvariable a occurs in no formula of l.
Definition ifresh (a : nat) (l : list iformula) : Prop :=
  ∀ A, In A l → ioccurs a A = false.

End Formulas.

Arguments iformula symbol : clear implicits.

Section Calculus.

Context {symbol : Type}.
Local Notation iformula := (iformula symbol).

The derivable sequents Γ ⊢ C, where R gives the optional rules.
Inductive ill (R : Intuitionistic.irules) : list iformula → iformula → Prop :=
| ax_ir : ∀ p l,
    ill R [ivar p l] (ivar p l)
| ex_ir : ∀ l1 l2 C,
    ill R l1 C → Permutation l1 l2 → ill R l2 C
| one_irr :
    ill R [] ione
| one_ilr : ∀ l C,
    ill R l C → ill R (ione :: l) C
| tens_irr : ∀ A B l1 l2,
    ill R l1 A → ill R l2 B → ill R (l1 ++ l2) (itens A B)
| tens_ilr : ∀ A B l C,
    ill R (A :: B :: l) C → ill R (itens A B :: l) C
| lmap_irr : ∀ A B l,
    ill R (A :: l) B → ill R l (ilmap A B)
| lmap_ilr : ∀ A B l1 l2 C,
    ill R l1 A → ill R (B :: l2) C → ill R (ilmap A B :: l1 ++ l2) C
| top_irr : ∀ l,
    ill R l itop
| with_irr : ∀ A B l,
    ill R l A → ill R l B → ill R l (iwith A B)
| with_ilr1 : ∀ A B l C,
    ill R (A :: l) C → ill R (iwith A B :: l) C
| with_ilr2 : ∀ A B l C,
    ill R (B :: l) C → ill R (iwith A B :: l) C
| zero_ilr : ∀ l C,
    ill R (izero :: l) C
| plus_irr1 : ∀ A B l,
    ill R l A → ill R l (iplus A B)
| plus_irr2 : ∀ A B l,
    ill R l B → ill R l (iplus A B)
| plus_ilr : ∀ A B l C,
    ill R (A :: l) C → ill R (B :: l) C → ill R (iplus A B :: l) C
| oc_irr : ∀ A l,
    ill R (map ioc l) A → ill R (map ioc l) (ioc A)
| de_ilr : ∀ A l C,
    ill R (A :: l) C → ill R (ioc A :: l) C
| wk_ilr : ∀ A l C,
    ill R l C → ill R (ioc A :: l) C
| co_ilr : ∀ A l C,
    ill R (ioc A :: ioc A :: l) C → ill R (ioc A :: l) C
| weakening_ilr : Intuitionistic.iweakening R = true → ∀ A l C,
    ill R l C → ill R (A :: l) C
| cut_ir : Intuitionistic.icut R = true → ∀ A l1 l2 C,
    ill R l1 A → ill R (A :: l2) C → ill R (l1 ++ l2) C
| all_irr : ∀ A a l,
    ifresh a (iall A :: l) → ill R l (isubst 0 (eigen a) A) → ill R l (iall A)
| all_ilr : ∀ A t l C,
    tclosed t = true → ill R (isubst 0 t A :: l) C → ill R (iall A :: l) C
| ex_irr : ∀ A t l,
    tclosed t = true → ill R l (isubst 0 t A) → ill R l (iex A)
| ex_ilr : ∀ A a l C,
    ifresh a (iex A :: C :: l) → ill R (isubst 0 (eigen a) A :: l) C → ill R (iex A :: l) C.

End Calculus.