Library Deduxit.Linear.Calculus


The one-sided sequent calculus of classical linear logic

This file is part of what a certificate's statement rests on: read it to know what a certificate claims. ll R Γ says that the sequent ⊢ Γ has a derivation in the calculus whose optional rules are R; without cut when cut R = false. A sequent is a list of formulas read as a multiset: the exchange rule ex_r allows any permutation. The rules are the textbook ones. Every rule except exchange, Mix and cut acts on the first formula of its conclusion and its premises. The file derives nothing and assumes nothing. ll R Γ is a Prop: it says that a derivation exists.

From Stdlib Require Import List Permutation.
From Deduxit.Linear Require Export Formulas.
Import ListNotations.

The optional rules of a calculus. Classical linear logic has none; Mix adds mix, affine logic adds weakening, and a calculus with cut adds cut. mix is the binary rule only, never the nullary one (the empty sequent ⊢). weakening is the rule weakening_r below; the weakening of ? formulas, wk_r, is in every calculus. cut is the rule cut_r.
Record rules : Type := Rules {
  mix : bool;
binary Mix: ⊢ Γ, Δ from ⊢ Γ and ⊢ Δ
  weakening : bool;
weakening of any formula, not only of ? ones
  cut : bool;
cut: ⊢ Γ, Δ from ⊢ A, Γ and ⊢ A⊥, Δ
}.

Classical linear logic: no Mix, no weakening, no cut.
Definition classical : rules := {| mix := false; weakening := false; cut := false |}.

Section Calculus.

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

The derivable sequents, where R gives the optional rules.
Inductive ll (R : rules) : list formula → Prop :=
| ax_r : ∀ a,
    ll R [covar a; var a]
| ex_r : ∀ l1 l2,
    ll R l1 → Permutation l1 l2 → ll R l2
| one_r :
    ll R [one]
| bot_r : ∀ l,
    ll R l → ll R (bot :: l)
| top_r : ∀ l,
    ll R (top :: l)
| tens_r : ∀ A B l1 l2,
    ll R (A :: l1) → ll R (B :: l2) → ll R (tens A B :: l1 ++ l2)
| parr_r : ∀ A B l,
    ll R (A :: B :: l) → ll R (parr A B :: l)
| with_r : ∀ A B l,
    ll R (A :: l) → ll R (B :: l) → ll R (awith A B :: l)
| plus_r1 : ∀ A B l,
    ll R (A :: l) → ll R (aplus A B :: l)
| plus_r2 : ∀ A B l,
    ll R (B :: l) → ll R (aplus A B :: l)
| oc_r : ∀ A l,
    ll R (A :: map wn l) → ll R (oc A :: map wn l)
| de_r : ∀ A l,
    ll R (A :: l) → ll R (wn A :: l)
| wk_r : ∀ A l,
    ll R l → ll R (wn A :: l)
| co_r : ∀ A l,
    ll R (wn A :: wn A :: l) → ll R (wn A :: l)
| mix_r : mix R = true → ∀ l1 l2,
    ll R l1 → ll R l2 → ll R (l1 ++ l2)
| weakening_r : weakening R = true → ∀ A l,
    ll R l → ll R (A :: l)
| cut_r : cut R = true → ∀ A l1 l2,
    ll R (A :: l1) → ll R (dual A :: l2) → ll R (l1 ++ l2).

End Calculus.