Library Deduxit.Linear.IntuitionisticCheck
Two-sided proof terms, their checker and its soundness
From Stdlib Require Import Bool List Permutation Lia.
From Deduxit.Linear Require Export Intuitionistic.
Import ListNotations.
Section Formulas.
Context {atom : Type}.
Local Notation iformula := (iformula atom).
Section Equality.
A Boolean equality on atoms; the checker compares atoms with it.
Structural equality of intuitionistic formulas, comparing atoms
with atom_eqb.
Fixpoint iformula_eqb (A B : iformula) : bool :=
match A, B with
| ivar a, ivar b ⇒ atom_eqb a b
| ione, ione ⇒ true
| itop, itop ⇒ true
| izero, izero ⇒ true
| itens A1 A2, itens B1 B2 ⇒ iformula_eqb A1 B1 && iformula_eqb A2 B2
| ilmap A1 A2, ilmap B1 B2 ⇒ iformula_eqb A1 B1 && iformula_eqb A2 B2
| iwith A1 A2, iwith B1 B2 ⇒ iformula_eqb A1 B1 && iformula_eqb A2 B2
| iplus A1 A2, iplus B1 B2 ⇒ iformula_eqb A1 B1 && iformula_eqb A2 B2
| ioc A, ioc B ⇒ iformula_eqb A B
| _, _ ⇒ false
end.
match A, B with
| ivar a, ivar b ⇒ atom_eqb a b
| ione, ione ⇒ true
| itop, itop ⇒ true
| izero, izero ⇒ true
| itens A1 A2, itens B1 B2 ⇒ iformula_eqb A1 B1 && iformula_eqb A2 B2
| ilmap A1 A2, ilmap B1 B2 ⇒ iformula_eqb A1 B1 && iformula_eqb A2 B2
| iwith A1 A2, iwith B1 B2 ⇒ iformula_eqb A1 B1 && iformula_eqb A2 B2
| iplus A1 A2, iplus B1 B2 ⇒ iformula_eqb A1 B1 && iformula_eqb A2 B2
| ioc A, ioc B ⇒ iformula_eqb A B
| _, _ ⇒ false
end.
atom_eqb decides equality. The soundness theorem assumes this.
Hypothesis atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b).
Lemma iformula_eqb_spec : ∀ A B, reflect (A = B) (iformula_eqb A B).
Proof.
induction A; destruct B; cbn; try (constructor; congruence).
all: repeat match goal with
| |- reflect _ (atom_eqb ?a ?b) ⇒ destruct (atom_eqb_spec a b)
| |- reflect _ (iformula_eqb ?A ?B && _) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (iformula_eqb ?A ?B) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (true && _) ⇒ cbn
| |- reflect _ (false && _) ⇒ cbn
end.
all: constructor; congruence.
Qed.
Lemma iformula_eqb_spec : ∀ A B, reflect (A = B) (iformula_eqb A B).
Proof.
induction A; destruct B; cbn; try (constructor; congruence).
all: repeat match goal with
| |- reflect _ (atom_eqb ?a ?b) ⇒ destruct (atom_eqb_spec a b)
| |- reflect _ (iformula_eqb ?A ?B && _) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (iformula_eqb ?A ?B) ⇒
match goal with IH : ∀ B, reflect (A = B) _ |- _ ⇒ destruct (IH B) end
| |- reflect _ (true && _) ⇒ cbn
| |- reflect _ (false && _) ⇒ cbn
end.
all: constructor; congruence.
Qed.
Equality of intuitionistic formulas as a decision, used in proofs;
the checker computes with iformula_eqb.
Definition iformula_eq_dec (A B : iformula) : {A = B} + {A ≠ B} :=
reflect_dec _ _ (iformula_eqb_spec A B).
End Equality.
End Formulas.
Section Check.
Context {atom : Type} (atom_eqb : atom → atom → bool).
Local Notation iformula := (iformula atom).
Local Notation eqb := (iformula_eqb atom_eqb).
reflect_dec _ _ (iformula_eqb_spec A B).
End Equality.
End Formulas.
Section Check.
Context {atom : Type} (atom_eqb : atom → atom → bool).
Local Notation iformula := (iformula atom).
Local Notation eqb := (iformula_eqb atom_eqb).
A two-sided proof term. Below, Γ ⊢ C is the node's conclusion,
its hypotheses read as a multiset.
| IOneR
⊢ 1
Γ, 1 ⊢ C from Γ ⊢ C
Γ, Δ ⊢ A ⊗ B from Γ ⊢ A and Δ ⊢ B
Γ, A ⊗ B ⊢ C from Γ, A, B ⊢ C
Γ ⊢ A ⊸ B from Γ, A ⊢ B
Γ, Δ, A ⊸ B ⊢ C from Γ ⊢ A and Δ, B ⊢ C
Γ ⊢ ⊤, with Γ the context
Γ ⊢ A & B from Γ ⊢ A and Γ ⊢ B
Γ, A & B ⊢ C from Γ, A ⊢ C
Γ, A & B ⊢ C from Γ, B ⊢ C
Γ, 0 ⊢ C, with Γ the context and C the goal
Γ ⊢ A ⊕ B from Γ ⊢ A
Γ ⊢ A ⊕ B from Γ ⊢ B
Γ, A ⊕ B ⊢ C from Γ, A ⊢ C and Γ, B ⊢ C
promotion, !Γ ⊢ !A from !Γ ⊢ A
dereliction, Γ, !A ⊢ C from Γ, A ⊢ C
weakening of a ! hypothesis, Γ, !A ⊢ C from Γ ⊢ C
contraction, Γ, !A ⊢ C from Γ, !A, !A ⊢ C
Γ, Δ ⊢ C from Γ ⊢ A and Δ, A ⊢ C, with icut; the
premise that proves A may come first or second
Removes one occurrence of A from l, or fails when there is none.
Multisets, as lists compared through iformula_eqb
Fixpoint pick (A : iformula) (l : list iformula) : option (list iformula) :=
match l with
| [] ⇒ None
| B :: l' ⇒ if eqb A B then Some l' else option_map (cons B) (pick A l')
end.
match l with
| [] ⇒ None
| B :: l' ⇒ if eqb A B then Some l' else option_map (cons B) (pick A l')
end.
Whether l1 and l2 are the same multiset.
Fixpoint same (l1 l2 : list iformula) : bool :=
match l1 with
| [] ⇒ match l2 with [] ⇒ true | _ :: _ ⇒ false end
| A :: l1' ⇒ match pick A l2 with Some l2' ⇒ same l1' l2' | None ⇒ false end
end.
match l1 with
| [] ⇒ match l2 with [] ⇒ true | _ :: _ ⇒ false end
| A :: l1' ⇒ match pick A l2 with Some l2' ⇒ same l1' l2' | None ⇒ false end
end.
Fixpoint unoc (l : list iformula) : option (list iformula) :=
match l with
| [] ⇒ Some []
| ioc A :: l' ⇒ option_map (cons A) (unoc l')
| _ :: _ ⇒ None
end.
match l with
| [] ⇒ Some []
| ioc A :: l' ⇒ option_map (cons A) (unoc l')
| _ :: _ ⇒ None
end.
The conclusion Γ1, Γ2 ⊢ C2 of a cut on A when the first premise
Γ1 ⊢ C1 proves A and the second, Γ2 ⊢ C2, has A as a
hypothesis; None otherwise.
Definition cut_by (A : iformula) (l1 : list iformula) (C1 : iformula)
(l2 : list iformula) (C2 : iformula) : option (list iformula × iformula) :=
if eqb A C1 then
match pick A l2 with
| Some l2' ⇒ Some (l1 ++ l2', C2)
| None ⇒ None
end
else None.
(l2 : list iformula) (C2 : iformula) : option (list iformula × iformula) :=
if eqb A C1 then
match pick A l2 with
| Some l2' ⇒ Some (l1 ++ l2', C2)
| None ⇒ None
end
else None.
The conclusion of a cut on A from its premises Γ1 ⊢ C1 and
Γ2 ⊢ C2, whichever of them proves A. When both orders apply,
C1 and C2 are both A, and the two orders give the same
sequent.
Definition icut_conclusion (A : iformula) (l1 : list iformula) (C1 : iformula)
(l2 : list iformula) (C2 : iformula) : option (list iformula × iformula) :=
match cut_by A l1 C1 l2 C2 with
| Some s ⇒ Some s
| None ⇒ cut_by A l2 C2 l1 C1
end.
(l2 : list iformula) (C2 : iformula) : option (list iformula × iformula) :=
match cut_by A l1 C1 l2 C2 with
| Some s ⇒ Some s
| None ⇒ cut_by A l2 C2 l1 C1
end.
The pass
Fixpoint iderive (R : irules) (p : iproof) : option (list iformula × iformula) :=
match p with
| IAx a ⇒ Some ([ivar a], ivar a)
| IOneR ⇒ Some ([], ione)
| IOneL q ⇒
match iderive R q with
| Some (l, C) ⇒ Some (ione :: l, C)
| None ⇒ None
end
| ITensR A B q r ⇒
match iderive R q, iderive R r with
| Some (l1, A'), Some (l2, B') ⇒
if eqb A A' && eqb B B' then Some (l1 ++ l2, itens A B) else None
| _, _ ⇒ None
end
| ITensL A B q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick A l with
| Some l' ⇒
match pick B l' with
| Some l'' ⇒ Some (itens A B :: l'', C)
| None ⇒ None
end
| None ⇒ None
end
| None ⇒ None
end
| ILmapR A B q ⇒
match iderive R q with
| Some (l, B') ⇒
if eqb B B' then
match pick A l with
| Some l' ⇒ Some (l', ilmap A B)
| None ⇒ None
end
else None
| None ⇒ None
end
| ILmapL A B q r ⇒
match iderive R q, iderive R r with
| Some (l1, A'), Some (l2, C) ⇒
if eqb A A' then
match pick B l2 with
| Some l2' ⇒ Some (ilmap A B :: l1 ++ l2', C)
| None ⇒ None
end
else None
| _, _ ⇒ None
end
| ITopR l ⇒ Some (l, itop)
| IWithR A B q r ⇒
match iderive R q, iderive R r with
| Some (l1, A'), Some (l2, B') ⇒
if eqb A A' && eqb B B' && same l1 l2 then Some (l1, iwith A B) else None
| _, _ ⇒ None
end
| IWithL1 A B q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick A l with
| Some l' ⇒ Some (iwith A B :: l', C)
| None ⇒ None
end
| None ⇒ None
end
| IWithL2 A B q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick B l with
| Some l' ⇒ Some (iwith A B :: l', C)
| None ⇒ None
end
| None ⇒ None
end
| IZeroL l C ⇒ Some (izero :: l, C)
| IPlusR1 A B q ⇒
match iderive R q with
| Some (l, A') ⇒ if eqb A A' then Some (l, iplus A B) else None
| None ⇒ None
end
| IPlusR2 A B q ⇒
match iderive R q with
| Some (l, B') ⇒ if eqb B B' then Some (l, iplus A B) else None
| None ⇒ None
end
| IPlusL A B q r ⇒
match iderive R q, iderive R r with
| Some (l1, C1), Some (l2, C2) ⇒
match pick A l1, pick B l2 with
| Some l1', Some l2' ⇒
if eqb C1 C2 && same l1' l2' then Some (iplus A B :: l1', C1) else None
| _, _ ⇒ None
end
| _, _ ⇒ None
end
| IOcR A q ⇒
match iderive R q with
| Some (l, A') ⇒
match unoc l with
| Some _ ⇒ if eqb A A' then Some (l, ioc A) else None
| None ⇒ None
end
| None ⇒ None
end
| IDe A q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick A l with
| Some l' ⇒ Some (ioc A :: l', C)
| None ⇒ None
end
| None ⇒ None
end
| IWk A q ⇒
match iderive R q with
| Some (l, C) ⇒ Some (ioc A :: l, C)
| None ⇒ None
end
| ICo A q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick (ioc A) l with
| Some l' ⇒
match pick (ioc A) l' with
| Some l'' ⇒ Some (ioc A :: l'', C)
| None ⇒ None
end
| None ⇒ None
end
| None ⇒ None
end
| IWeaken A q ⇒
if iweakening R then
match iderive R q with
| Some (l, C) ⇒ Some (A :: l, C)
| None ⇒ None
end
else None
| ICut A q r ⇒
if icut R then
match iderive R q, iderive R r with
| Some (l1, C1), Some (l2, C2) ⇒ icut_conclusion A l1 C1 l2 C2
| _, _ ⇒ None
end
else None
end.
match p with
| IAx a ⇒ Some ([ivar a], ivar a)
| IOneR ⇒ Some ([], ione)
| IOneL q ⇒
match iderive R q with
| Some (l, C) ⇒ Some (ione :: l, C)
| None ⇒ None
end
| ITensR A B q r ⇒
match iderive R q, iderive R r with
| Some (l1, A'), Some (l2, B') ⇒
if eqb A A' && eqb B B' then Some (l1 ++ l2, itens A B) else None
| _, _ ⇒ None
end
| ITensL A B q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick A l with
| Some l' ⇒
match pick B l' with
| Some l'' ⇒ Some (itens A B :: l'', C)
| None ⇒ None
end
| None ⇒ None
end
| None ⇒ None
end
| ILmapR A B q ⇒
match iderive R q with
| Some (l, B') ⇒
if eqb B B' then
match pick A l with
| Some l' ⇒ Some (l', ilmap A B)
| None ⇒ None
end
else None
| None ⇒ None
end
| ILmapL A B q r ⇒
match iderive R q, iderive R r with
| Some (l1, A'), Some (l2, C) ⇒
if eqb A A' then
match pick B l2 with
| Some l2' ⇒ Some (ilmap A B :: l1 ++ l2', C)
| None ⇒ None
end
else None
| _, _ ⇒ None
end
| ITopR l ⇒ Some (l, itop)
| IWithR A B q r ⇒
match iderive R q, iderive R r with
| Some (l1, A'), Some (l2, B') ⇒
if eqb A A' && eqb B B' && same l1 l2 then Some (l1, iwith A B) else None
| _, _ ⇒ None
end
| IWithL1 A B q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick A l with
| Some l' ⇒ Some (iwith A B :: l', C)
| None ⇒ None
end
| None ⇒ None
end
| IWithL2 A B q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick B l with
| Some l' ⇒ Some (iwith A B :: l', C)
| None ⇒ None
end
| None ⇒ None
end
| IZeroL l C ⇒ Some (izero :: l, C)
| IPlusR1 A B q ⇒
match iderive R q with
| Some (l, A') ⇒ if eqb A A' then Some (l, iplus A B) else None
| None ⇒ None
end
| IPlusR2 A B q ⇒
match iderive R q with
| Some (l, B') ⇒ if eqb B B' then Some (l, iplus A B) else None
| None ⇒ None
end
| IPlusL A B q r ⇒
match iderive R q, iderive R r with
| Some (l1, C1), Some (l2, C2) ⇒
match pick A l1, pick B l2 with
| Some l1', Some l2' ⇒
if eqb C1 C2 && same l1' l2' then Some (iplus A B :: l1', C1) else None
| _, _ ⇒ None
end
| _, _ ⇒ None
end
| IOcR A q ⇒
match iderive R q with
| Some (l, A') ⇒
match unoc l with
| Some _ ⇒ if eqb A A' then Some (l, ioc A) else None
| None ⇒ None
end
| None ⇒ None
end
| IDe A q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick A l with
| Some l' ⇒ Some (ioc A :: l', C)
| None ⇒ None
end
| None ⇒ None
end
| IWk A q ⇒
match iderive R q with
| Some (l, C) ⇒ Some (ioc A :: l, C)
| None ⇒ None
end
| ICo A q ⇒
match iderive R q with
| Some (l, C) ⇒
match pick (ioc A) l with
| Some l' ⇒
match pick (ioc A) l' with
| Some l'' ⇒ Some (ioc A :: l'', C)
| None ⇒ None
end
| None ⇒ None
end
| None ⇒ None
end
| IWeaken A q ⇒
if iweakening R then
match iderive R q with
| Some (l, C) ⇒ Some (A :: l, C)
| None ⇒ None
end
else None
| ICut A q r ⇒
if icut R then
match iderive R q, iderive R r with
| Some (l1, C1), Some (l2, C2) ⇒ icut_conclusion A l1 C1 l2 C2
| _, _ ⇒ None
end
else None
end.
Whether p proves hypotheses ⊢ goal in R: its conclusion has
that goal and, as a multiset, those hypotheses.
Definition icheck (R : irules) (p : iproof) (hypotheses : list iformula) (goal : iformula)
: bool :=
match iderive R p with
| Some (l, C) ⇒ eqb C goal && same l hypotheses
| None ⇒ false
end.
End Check.
Arguments iproof atom : clear implicits.
Section Soundness.
Context {atom : Type} (atom_eqb : atom → atom → bool)
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)).
Local Notation iformula := (iformula atom).
Local Notation eqb_spec := (iformula_eqb_spec atom_eqb atom_eqb_spec).
Lemma pick_perm : ∀ (A : iformula) l l',
pick atom_eqb A l = Some l' → Permutation l (A :: l').
Proof.
induction l as [| B l IH]; cbn; intros l' H; [discriminate |].
destruct (eqb_spec A B) as [<- | _].
- injection H as <-. reflexivity.
- destruct (pick atom_eqb A l) as [l'' |] eqn:E; cbn in H; [| discriminate].
injection H as <-. rewrite (IH l'' eq_refl). apply perm_swap.
Qed.
Lemma same_perm : ∀ (l1 l2 : list iformula),
same atom_eqb l1 l2 = true → Permutation l1 l2.
Proof.
induction l1 as [| A l1 IH]; cbn; intros l2 H.
- destruct l2; [reflexivity | discriminate].
- destruct (pick atom_eqb A l2) as [l2' |] eqn:E; [| discriminate].
rewrite (pick_perm _ _ _ E). apply perm_skip, IH, H.
Qed.
Lemma unoc_map : ∀ (l l' : list iformula),
unoc l = Some l' → l = map ioc l'.
Proof.
induction l as [| A l IH]; cbn; intros l' H.
- injection H as <-. reflexivity.
- destruct A; try discriminate.
destruct (unoc l) as [l'' |]; cbn in H; [| discriminate].
injection H as <-. cbn. f_equal. apply IH. reflexivity.
Qed.
Local Notation eq_dec := (iformula_eq_dec atom_eqb atom_eqb_spec).
: bool :=
match iderive R p with
| Some (l, C) ⇒ eqb C goal && same l hypotheses
| None ⇒ false
end.
End Check.
Arguments iproof atom : clear implicits.
Section Soundness.
Context {atom : Type} (atom_eqb : atom → atom → bool)
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)).
Local Notation iformula := (iformula atom).
Local Notation eqb_spec := (iformula_eqb_spec atom_eqb atom_eqb_spec).
Lemma pick_perm : ∀ (A : iformula) l l',
pick atom_eqb A l = Some l' → Permutation l (A :: l').
Proof.
induction l as [| B l IH]; cbn; intros l' H; [discriminate |].
destruct (eqb_spec A B) as [<- | _].
- injection H as <-. reflexivity.
- destruct (pick atom_eqb A l) as [l'' |] eqn:E; cbn in H; [| discriminate].
injection H as <-. rewrite (IH l'' eq_refl). apply perm_swap.
Qed.
Lemma same_perm : ∀ (l1 l2 : list iformula),
same atom_eqb l1 l2 = true → Permutation l1 l2.
Proof.
induction l1 as [| A l1 IH]; cbn; intros l2 H.
- destruct l2; [reflexivity | discriminate].
- destruct (pick atom_eqb A l2) as [l2' |] eqn:E; [| discriminate].
rewrite (pick_perm _ _ _ E). apply perm_skip, IH, H.
Qed.
Lemma unoc_map : ∀ (l l' : list iformula),
unoc l = Some l' → l = map ioc l'.
Proof.
induction l as [| A l IH]; cbn; intros l' H.
- injection H as <-. reflexivity.
- destruct A; try discriminate.
destruct (unoc l) as [l'' |]; cbn in H; [| discriminate].
injection H as <-. cbn. f_equal. apply IH. reflexivity.
Qed.
Local Notation eq_dec := (iformula_eq_dec atom_eqb atom_eqb_spec).
Rewrites with the Boolean equalities of formulas a node compared.
Local Ltac equalities :=
repeat match goal with
| H : (_ && _) = true |- _ ⇒ apply andb_prop in H; destruct H
| H : iformula_eqb atom_eqb ?A ?B = true |- _ ⇒
destruct (eqb_spec A B); [subst | discriminate]
end.
repeat match goal with
| H : (_ && _) = true |- _ ⇒ apply andb_prop in H; destruct H
| H : iformula_eqb atom_eqb ?A ?B = true |- _ ⇒
destruct (eqb_spec A B); [subst | discriminate]
end.
Unfolds a node's matches on its subterms' conclusions and on the
multiset operations, and keeps what each one computed.
Local Ltac steps :=
repeat match goal with
| H : match ?e with _ ⇒ _ end = Some _ |- _ ⇒
let E := fresh "E" in destruct e eqn:E; try discriminate
| H : (if ?b then _ else _) = Some _ |- _ ⇒
let E := fresh "E" in destruct b eqn:E; try discriminate
end.
repeat match goal with
| H : match ?e with _ ⇒ _ end = Some _ |- _ ⇒
let E := fresh "E" in destruct e eqn:E; try discriminate
| H : (if ?b then _ else _) = Some _ |- _ ⇒
let E := fresh "E" in destruct b eqn:E; try discriminate
end.
Decides a permutation of lists of formulas from the permutations in
the context, by counting every formula's occurrences.
Local Ltac iperm :=
apply (Permutation_count_occ eq_dec); intros ?x;
repeat match goal with
| H : Permutation _ _ |- _ ⇒
rewrite (Permutation_count_occ eq_dec) in H; specialize (H x)
end;
repeat first [rewrite count_occ_app in × | progress cbn [count_occ] in *];
repeat match goal with
| |- context [eq_dec ?a ?b] ⇒ destruct (eq_dec a b)
| H : context [eq_dec ?a ?b] |- _ ⇒ destruct (eq_dec a b)
end;
lia.
Variable R : irules.
apply (Permutation_count_occ eq_dec); intros ?x;
repeat match goal with
| H : Permutation _ _ |- _ ⇒
rewrite (Permutation_count_occ eq_dec) in H; specialize (H x)
end;
repeat first [rewrite count_occ_app in × | progress cbn [count_occ] in *];
repeat match goal with
| |- context [eq_dec ?a ?b] ⇒ destruct (eq_dec a b)
| H : context [eq_dec ?a ?b] |- _ ⇒ destruct (eq_dec a b)
end;
lia.
Variable R : irules.
Proves a premise from the derivation of a subterm, up to a
permutation of its hypotheses.
Local Ltac premise :=
match goal with
| H : ill R ?l ?C |- ill R _ ?C ⇒ apply (ex_ir R l _ C H); iperm
end.
match goal with
| H : ill R ?l ?C |- ill R _ ?C ⇒ apply (ex_ir R l _ C H); iperm
end.
If a cut's premises are derivable, its conclusion is.
Lemma cut_by_sound : ∀ A l1 C1 l2 C2 l C,
icut R = true → ill R l1 C1 → ill R l2 C2 →
cut_by atom_eqb A l1 C1 l2 C2 = Some (l, C) → ill R l C.
Proof.
unfold cut_by; intros × K H1 H2 E.
destruct (eqb_spec A C1) as [-> | _]; [| discriminate].
destruct (pick atom_eqb C1 l2) as [l2' |] eqn:P; [| discriminate].
injection E as <- <-. apply pick_perm in P.
apply (cut_ir R K C1 l1 l2' C2); [exact H1 | exact (ex_ir R _ _ _ H2 P)].
Qed.
Lemma icut_conclusion_sound : ∀ A l1 C1 l2 C2 l C,
icut R = true → ill R l1 C1 → ill R l2 C2 →
icut_conclusion atom_eqb A l1 C1 l2 C2 = Some (l, C) → ill R l C.
Proof.
unfold icut_conclusion; intros × K H1 H2 E.
destruct (cut_by atom_eqb A l1 C1 l2 C2) as [[l' C'] |] eqn:B.
- injection E as <- <-. exact (cut_by_sound _ _ _ _ _ _ _ K H1 H2 B).
- exact (cut_by_sound _ _ _ _ _ _ _ K H2 H1 E).
Qed.
icut R = true → ill R l1 C1 → ill R l2 C2 →
cut_by atom_eqb A l1 C1 l2 C2 = Some (l, C) → ill R l C.
Proof.
unfold cut_by; intros × K H1 H2 E.
destruct (eqb_spec A C1) as [-> | _]; [| discriminate].
destruct (pick atom_eqb C1 l2) as [l2' |] eqn:P; [| discriminate].
injection E as <- <-. apply pick_perm in P.
apply (cut_ir R K C1 l1 l2' C2); [exact H1 | exact (ex_ir R _ _ _ H2 P)].
Qed.
Lemma icut_conclusion_sound : ∀ A l1 C1 l2 C2 l C,
icut R = true → ill R l1 C1 → ill R l2 C2 →
icut_conclusion atom_eqb A l1 C1 l2 C2 = Some (l, C) → ill R l C.
Proof.
unfold icut_conclusion; intros × K H1 H2 E.
destruct (cut_by atom_eqb A l1 C1 l2 C2) as [[l' C'] |] eqn:B.
- injection E as <- <-. exact (cut_by_sound _ _ _ _ _ _ _ K H1 H2 B).
- exact (cut_by_sound _ _ _ _ _ _ _ K H2 H1 E).
Qed.
Every conclusion iderive computes is derivable.
Lemma iderive_sound : ∀ p l C,
iderive atom_eqb R p = Some (l, C) → ill R l C.
Proof.
induction p; cbn; intros l C H; steps; equalities;
repeat match goal with
| H : Some _ = Some _ |- _ ⇒ injection H as <- <-
| IH : ∀ l C, Some (?l', ?C') = Some (l, C) → _ |- _ ⇒
specialize (IH l' C' eq_refl)
| H : pick _ _ _ = Some _ |- _ ⇒ apply pick_perm in H
| H : same _ _ _ = true |- _ ⇒ apply same_perm in H
| H : unoc ?l = Some _ |- _ ⇒ apply unoc_map in H; subst l
end.
- apply ax_ir.
- apply one_irr.
- apply one_ilr; premise.
- apply tens_irr; premise.
- apply tens_ilr; premise.
- apply lmap_irr; premise.
- apply lmap_ilr; premise.
- apply top_irr.
- apply with_irr; premise.
- apply with_ilr1; premise.
- apply with_ilr2; premise.
- apply zero_ilr.
- apply plus_irr1; premise.
- apply plus_irr2; premise.
- apply plus_ilr; premise.
- apply oc_irr; premise.
- apply de_ilr; premise.
- apply wk_ilr; premise.
- apply co_ilr; premise.
- apply weakening_ilr; [assumption | premise].
- eapply icut_conclusion_sound; [eassumption | | | eassumption]; eassumption.
Qed.
End Soundness.
iderive atom_eqb R p = Some (l, C) → ill R l C.
Proof.
induction p; cbn; intros l C H; steps; equalities;
repeat match goal with
| H : Some _ = Some _ |- _ ⇒ injection H as <- <-
| IH : ∀ l C, Some (?l', ?C') = Some (l, C) → _ |- _ ⇒
specialize (IH l' C' eq_refl)
| H : pick _ _ _ = Some _ |- _ ⇒ apply pick_perm in H
| H : same _ _ _ = true |- _ ⇒ apply same_perm in H
| H : unoc ?l = Some _ |- _ ⇒ apply unoc_map in H; subst l
end.
- apply ax_ir.
- apply one_irr.
- apply one_ilr; premise.
- apply tens_irr; premise.
- apply tens_ilr; premise.
- apply lmap_irr; premise.
- apply lmap_ilr; premise.
- apply top_irr.
- apply with_irr; premise.
- apply with_ilr1; premise.
- apply with_ilr2; premise.
- apply zero_ilr.
- apply plus_irr1; premise.
- apply plus_irr2; premise.
- apply plus_ilr; premise.
- apply oc_irr; premise.
- apply de_ilr; premise.
- apply wk_ilr; premise.
- apply co_ilr; premise.
- apply weakening_ilr; [assumption | premise].
- eapply icut_conclusion_sound; [eassumption | | | eassumption]; eassumption.
Qed.
End Soundness.
If the checker accepts a term for a sequent, the sequent is
derivable in the two-sided calculus R: intuitionistic linear
logic or its affine variant, with or without cut. A certificate of
a two-sided proof applies this theorem.
Theorem soundness_ill {atom : Type} (atom_eqb : atom → atom → bool)
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)) (R : irules) :
∀ (p : iproof atom) (hypotheses : list (iformula atom)) (goal : iformula atom),
icheck atom_eqb R p hypotheses goal = true → ill R hypotheses goal.
Proof.
unfold icheck; intros p Γ C H.
destruct (iderive atom_eqb R p) as [[l C'] |] eqn:E; [| discriminate].
apply andb_prop in H as [HC HΓ].
destruct (iformula_eqb_spec atom_eqb atom_eqb_spec C' C); [subst | discriminate].
eapply ex_ir; [apply (iderive_sound atom_eqb atom_eqb_spec R _ _ _ E) |].
apply (same_perm atom_eqb atom_eqb_spec). assumption.
Qed.
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)) (R : irules) :
∀ (p : iproof atom) (hypotheses : list (iformula atom)) (goal : iformula atom),
icheck atom_eqb R p hypotheses goal = true → ill R hypotheses goal.
Proof.
unfold icheck; intros p Γ C H.
destruct (iderive atom_eqb R p) as [[l C'] |] eqn:E; [| discriminate].
apply andb_prop in H as [HC HΓ].
destruct (iformula_eqb_spec atom_eqb atom_eqb_spec C' C); [subst | discriminate].
eapply ex_ir; [apply (iderive_sound atom_eqb atom_eqb_spec R _ _ _ E) |].
apply (same_perm atom_eqb atom_eqb_spec). assumption.
Qed.