Library Deduxit.Linear.Intuitionistic


The two-sided sequent calculus of intuitionistic linear logic

This file is what a certificate's intuitionistic statement rests on: read it to know what such a certificate claims. ill R Γ C says that the sequent Γ ⊢ C, with the hypotheses Γ and exactly one conclusion C, has a derivation in intuitionistic linear logic, or in its affine variant when R adds weakening; without cut when icut R = false.
The formulas and the rules are those of Yalla's standalone kernel nanoill.v and of the textbook calculus over 1, ⊗, ⊸, ⊤, &, 0, ⊕ and !, without ⊥. Every sequent has exactly one conclusion, so no rule weakens on the right. The axiom is on atoms; the identity on any formula is derivable. nanoill.v has no cut; R adds one here.
The hypotheses are a list read as a multiset: the exchange rule ex_ir allows any permutation. Every left rule acts on the first hypothesis, and the cut on the first hypothesis of its second premise. 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.
Import ListNotations.

Section Formulas.

Context {atom : Type}.

An intuitionistic formula.
Inductive iformula : Type :=
| ivar : atom → iformula
an atom a
1
A ⊗ B
A ⊸ B
⊤
A & B
0
A ⊕ B
!A

End Formulas.

Arguments iformula atom : clear implicits.

The optional rules of a two-sided calculus. Intuitionistic linear logic has none. Affine logic adds the weakening of any hypothesis (weakening_ilr below), never of the conclusion; the weakening of a ! hypothesis, wk_ilr, is in both. A calculus with cut adds cut_ir.
Record irules : Type := IRules {
  iweakening : bool;
weakening of any hypothesis, not only of ! ones
  icut : bool;
cut: Γ, Δ ⊢ C from Γ ⊢ A and Δ, A ⊢ C
}.

Intuitionistic linear logic: weakening of ! hypotheses only, no cut.
Definition intuitionistic : irules := {| iweakening := false; icut := false |}.

Affine intuitionistic logic: weakening of any hypothesis, no cut.
Definition affine : irules := {| iweakening := true; icut := false |}.

Section Calculus.

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

The derivable sequents Γ ⊢ C, where R gives the optional rules.
Inductive ill (R : irules) : list iformula → iformula → Prop :=
| ax_ir : ∀ a,
    ill R [ivar a] (ivar a)
| 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 : iweakening R = true → ∀ A l C,
    ill R l C → ill R (A :: l) C
| cut_ir : icut R = true → ∀ A l1 l2 C,
    ill R l1 A → ill R (A :: l2) C → ill R (l1 ++ l2) C.

End Calculus.