Library Deduxit.Linear.Soundness
Soundness of the checker
From Stdlib Require Import Bool List Permutation Lia.
From Deduxit.Linear Require Export Check.
Import ListNotations.
Section Soundness.
Context {atom : Type} (atom_eqb : atom → atom → bool)
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)).
Local Notation formula := (formula atom).
Local Notation eqb_spec := (formula_eqb_spec atom_eqb atom_eqb_spec).
Local Notation eq_dec := (formula_eq_dec atom_eqb atom_eqb_spec).
Local Notation count := (count_occ eq_dec).
Lemma remove_one_perm : ∀ (A : formula) l l',
remove_one 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 (remove_one 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 remove_one_absent : ∀ (A : formula) l,
remove_one atom_eqb A l = None → ¬ In A l.
Proof.
induction l as [| B l IH]; cbn; intros H HI; [exact HI |].
destruct (eqb_spec A B) as [_ | ne]; [discriminate |].
destruct HI as [-> | HI]; [exact (ne eq_refl) |].
destruct (remove_one atom_eqb A l); [discriminate | exact (IH eq_refl HI)].
Qed.
Lemma take_all_perm : ∀ (l1 l2 l : list formula),
take_all atom_eqb l1 l2 = Some l → Permutation l2 (l1 ++ l).
Proof.
induction l1 as [| A l1 IH]; cbn; intros l2 l H.
- injection H as <-. reflexivity.
- destruct (remove_one atom_eqb A l2) as [l2' |] eqn:E; [| discriminate].
rewrite (remove_one_perm _ _ _ E). apply perm_skip, IH, H.
Qed.
Lemma remove_all_perm : ∀ (A : formula) l,
Permutation l (repeat A (count l A) ++ remove_all atom_eqb A l).
Proof.
unfold remove_all. induction l as [| B l IH]; cbn; [reflexivity |].
destruct (eq_dec B A) as [e | ne]; destruct (eqb_spec A B) as [e' | ne'];
try congruence; cbn.
- subst. apply perm_skip, IH.
- apply (Permutation_trans (perm_skip B IH)), Permutation_middle.
Qed.
Lemma diff_count : ∀ (l1 l2 : list formula) x,
count (diff atom_eqb l2 l1) x = count l2 x - count l1 x.
Proof.
induction l1 as [| A l1 IH]; cbn; intros l2 x; [lia |].
destruct (remove_one atom_eqb A l2) as [l2' |] eqn:E; rewrite IH.
- apply remove_one_perm in E.
rewrite (Permutation_count_occ eq_dec) in E. rewrite (E x). cbn.
destruct (eq_dec A x); lia.
- apply remove_one_absent, (count_occ_not_In eq_dec) in E.
destruct (eq_dec A x); subst; lia.
Qed.
Permutations of lists of formulas, decided by counting every
formula's occurrences on both sides.
Ltac perm :=
apply (Permutation_count_occ eq_dec); intros ?x;
repeat rewrite map_app; repeat rewrite app_nil_r; cbn [map];
repeat first [rewrite count_occ_app | progress cbn [count_occ]];
repeat rewrite diff_count;
repeat match goal with
| |- context [eq_dec ?a ?b] ⇒ destruct (eq_dec a b); try subst
end;
lia.
apply (Permutation_count_occ eq_dec); intros ?x;
repeat rewrite map_app; repeat rewrite app_nil_r; cbn [map];
repeat first [rewrite count_occ_app | progress cbn [count_occ]];
repeat rewrite diff_count;
repeat match goal with
| |- context [eq_dec ?a ?b] ⇒ destruct (eq_dec a b); try subst
end;
lia.
Weakening of a list of ? formulas.
Lemma wk_list : ∀ (Θ l : list formula), ll R l → ll R (map wn Θ ++ l).
Proof. induction Θ; cbn; intros; [assumption | apply wk_r; auto]. Qed.
Lemma wn_contract_cons : ∀ (A : formula) n (l : list formula),
ll R (wn A :: map wn (repeat A n) ++ l) → ll R (wn A :: l).
Proof. induction n; cbn; intros l H; [exact H | apply IHn, co_r, H]. Qed.
Proof. induction Θ; cbn; intros; [assumption | apply wk_r; auto]. Qed.
Lemma wn_contract_cons : ∀ (A : formula) n (l : list formula),
ll R (wn A :: map wn (repeat A n) ++ l) → ll R (wn A :: l).
Proof. induction n; cbn; intros l H; [exact H | apply IHn, co_r, H]. Qed.
Any number of copies of ?A, zero included, contract into one.
Lemma wn_contract : ∀ (A : formula) n (l : list formula),
ll R (map wn (repeat A n) ++ l) → ll R (wn A :: l).
Proof.
intros A [| n] l H; cbn in H; [apply wk_r, H | apply (wn_contract_cons A n), H].
Qed.
ll R (map wn (repeat A n) ++ l) → ll R (wn A :: l).
Proof.
intros A [| n] l H; cbn in H; [apply wk_r, H | apply (wn_contract_cons A n), H].
Qed.
What a state stands for
Definition sat (theta gamma : list formula) (any : bool) : Prop :=
∀ Δ, (any = false → Δ = []) → ll R (gamma ++ map wn theta ++ Δ).
Lemma sat_perm : ∀ theta gamma gamma' any,
Permutation gamma gamma' → sat theta gamma any → sat theta gamma' any.
Proof.
intros × HP H Δ HΔ. eapply ex_r; [apply H, HΔ | apply Permutation_app_tail, HP].
Qed.
Lemma take_spec : ∀ A gamma any gamma',
take atom_eqb A gamma any = Some gamma' →
Permutation gamma (A :: gamma') ∨ (any = true ∧ gamma' = gamma).
Proof.
unfold take; intros × H.
destruct (remove_one atom_eqb A gamma) eqn:E.
- injection H as <-. left. apply remove_one_perm, E.
- destruct any; [| discriminate]. injection H as <-. auto.
Qed.
∀ Δ, (any = false → Δ = []) → ll R (gamma ++ map wn theta ++ Δ).
Lemma sat_perm : ∀ theta gamma gamma' any,
Permutation gamma gamma' → sat theta gamma any → sat theta gamma' any.
Proof.
intros × HP H Δ HΔ. eapply ex_r; [apply H, HΔ | apply Permutation_app_tail, HP].
Qed.
Lemma take_spec : ∀ A gamma any gamma',
take atom_eqb A gamma any = Some gamma' →
Permutation gamma (A :: gamma') ∨ (any = true ∧ gamma' = gamma).
Proof.
unfold take; intros × H.
destruct (remove_one atom_eqb A gamma) eqn:E.
- injection H as <-. left. apply remove_one_perm, E.
- destruct any; [| discriminate]. injection H as <-. auto.
Qed.
Consuming A from a satisfied zone leaves a satisfied zone with
A in front, behind whatever prefix pre the rule puts first.
Lemma take_sat : ∀ pre A theta gamma any gamma',
take atom_eqb A gamma any = Some gamma' →
sat theta (pre ++ gamma) any → sat theta (pre ++ A :: gamma') any.
Proof.
intros × T H. destruct (take_spec _ _ _ _ T) as [HP | [-> ->]].
- apply (sat_perm _ (pre ++ gamma)); [apply Permutation_app_head, HP | exact H].
- intros Δ _. eapply ex_r; [apply (H (A :: Δ)); easy | perm].
Qed.
take atom_eqb A gamma any = Some gamma' →
sat theta (pre ++ gamma) any → sat theta (pre ++ A :: gamma') any.
Proof.
intros × T H. destruct (take_spec _ _ _ _ T) as [HP | [-> ->]].
- apply (sat_perm _ (pre ++ gamma)); [apply Permutation_app_head, HP | exact H].
- intros Δ _. eapply ex_r; [apply (H (A :: Δ)); easy | perm].
Qed.
Theorem derive_sound : ∀ p s,
derive atom_eqb R p = Some s → sat (theta s) (gamma s) (any s).
Proof.
induction p as [a | A B l IHl r IHr | A B q IHq | | q IHq | A B l IHl r IHr
| A B side q IHq | | A q IHq | A q IHq | A q IHq | A q IHq | l IHl r IHr
| A l IHl r IHr];
cbn; intros s H.
-
injection H as <-; cbn. intros Δ HΔ. rewrite (HΔ eq_refl). cbn. apply ax_r.
-
destruct (derive atom_eqb R l) as [[θl γl al] |] eqn:El; [| discriminate].
destruct (derive atom_eqb R r) as [[θr γr ar] |] eqn:Er; [| discriminate].
cbn in H.
destruct (take atom_eqb A γl al) as [gl |] eqn:Tl; [| discriminate].
destruct (take atom_eqb B γr ar) as [gr |] eqn:Tr; [| discriminate].
injection H as <-; cbn.
specialize (IHl _ eq_refl); specialize (IHr _ eq_refl); cbn in IHl, IHr.
pose proof (take_sat [] _ _ _ _ _ Tl IHl) as Hl; cbn in Hl.
pose proof (take_sat [] _ _ _ _ _ Tr IHr) as Hr; cbn in Hr.
intros Δ HΔ. destruct al.
+ eapply ex_r; [apply tens_r; [apply (Hl Δ); easy | apply (Hr []); easy] | perm].
+ destruct ar.
× eapply ex_r; [apply tens_r; [apply (Hl []); easy | apply (Hr Δ); easy] | perm].
× rewrite (HΔ eq_refl).
eapply ex_r; [apply tens_r; [apply (Hl []); easy | apply (Hr []); easy] | perm].
-
destruct (derive atom_eqb R q) as [[θ γ a] |] eqn:E; [| discriminate]. cbn in H.
destruct (take atom_eqb A γ a) as [g1 |] eqn:T1; [| discriminate].
destruct (take atom_eqb B g1 a) as [g2 |] eqn:T2; [| discriminate].
injection H as <-; cbn.
specialize (IHq _ eq_refl); cbn in IHq.
pose proof (take_sat [] _ _ _ _ _ T1 IHq) as H1; cbn in H1.
pose proof (take_sat [A] _ _ _ _ _ T2 H1) as H2; cbn in H2.
intros Δ HΔ. apply parr_r, H2, HΔ.
-
injection H as <-; cbn. intros Δ HΔ. rewrite (HΔ eq_refl). cbn. apply one_r.
-
destruct (derive atom_eqb R q) as [[θ γ a] |] eqn:E; [| discriminate].
injection H as <-; cbn.
specialize (IHq _ eq_refl); cbn in IHq.
intros Δ HΔ. apply bot_r, IHq, HΔ.
-
destruct (derive atom_eqb R l) as [[θl γl al] |] eqn:El; [| discriminate].
destruct (derive atom_eqb R r) as [[θr γr ar] |] eqn:Er; [| discriminate].
cbn in H.
destruct (take atom_eqb A γl al) as [gl |] eqn:Tl; [| discriminate].
destruct (take atom_eqb B γr ar) as [gr |] eqn:Tr; [| discriminate].
specialize (IHl _ eq_refl); specialize (IHr _ eq_refl); cbn in IHl, IHr.
pose proof (take_sat [] _ _ _ _ _ Tl IHl) as Hl; cbn in Hl.
pose proof (take_sat [] _ _ _ _ _ Tr IHr) as Hr; cbn in Hr.
unfold join_with in H; cbn in H.
destruct al, ar; cbn in H.
+
injection H as <-; cbn. intros Δ _. apply with_r.
× eapply ex_r; [apply (Hl (diff atom_eqb gr gl ++ map wn θr ++ Δ)); easy | perm].
× eapply ex_r; [apply (Hr (diff atom_eqb gl gr ++ map wn θl ++ Δ)); easy | perm].
+
destruct (take_all atom_eqb gl gr) as [rest |] eqn:T; [| discriminate].
injection H as <-; cbn. apply take_all_perm in T.
intros Δ HΔ. rewrite (HΔ eq_refl). apply with_r.
× eapply ex_r; [apply (Hl (rest ++ map wn θr)); easy | rewrite T; perm].
× eapply ex_r; [apply (wk_list θl), (Hr []); easy | perm].
+
destruct (take_all atom_eqb gr gl) as [rest |] eqn:T; [| discriminate].
injection H as <-; cbn. apply take_all_perm in T.
intros Δ HΔ. rewrite (HΔ eq_refl). apply with_r.
× eapply ex_r; [apply (wk_list θr), (Hl []); easy | perm].
× eapply ex_r; [apply (Hr (rest ++ map wn θl)); easy | rewrite T; perm].
+
destruct (take_all atom_eqb gl gr) as [[| r' rest] |] eqn:T;
[| discriminate | discriminate].
injection H as <-; cbn. apply take_all_perm in T. rewrite app_nil_r in T.
intros Δ HΔ. rewrite (HΔ eq_refl). apply with_r.
× eapply ex_r; [apply (wk_list θr), (Hl []); easy | perm].
× eapply ex_r; [apply (wk_list θl), (Hr []); easy | rewrite T; perm].
-
destruct (derive atom_eqb R q) as [[θ γ a] |] eqn:E; [| discriminate]. cbn in H.
specialize (IHq _ eq_refl); cbn in IHq.
destruct side; cbn in H.
+ destruct (take atom_eqb A γ a) as [g |] eqn:T; [| discriminate].
injection H as <-; cbn.
pose proof (take_sat [] _ _ _ _ _ T IHq) as H1; cbn in H1.
intros Δ HΔ. apply plus_r1, H1, HΔ.
+ destruct (take atom_eqb B γ a) as [g |] eqn:T; [| discriminate].
injection H as <-; cbn.
pose proof (take_sat [] _ _ _ _ _ T IHq) as H1; cbn in H1.
intros Δ HΔ. apply plus_r2, H1, HΔ.
-
injection H as <-; cbn. intros Δ _. apply top_r.
-
destruct (derive atom_eqb R q) as [[θ γ a] |] eqn:E; [| discriminate]. cbn in H.
destruct (take atom_eqb A γ a) as [[| g1 g'] |] eqn:T; [| discriminate | discriminate].
cbn in H. injection H as <-; cbn.
specialize (IHq _ eq_refl); cbn in IHq.
pose proof (take_sat [] _ _ _ _ _ T IHq) as H1; cbn in H1.
intros Δ HΔ. rewrite (HΔ eq_refl).
eapply ex_r; [apply (oc_r R A θ); eapply ex_r; [apply (H1 []); easy | perm] | perm].
-
destruct (derive atom_eqb R q) as [[θ γ a] |] eqn:E; [| discriminate].
injection H as <-; cbn.
specialize (IHq _ eq_refl); cbn in IHq.
intros Δ HΔ. apply (wn_contract A (count θ A)).
eapply ex_r; [apply IHq, HΔ |].
transitivity (γ ++ map wn (repeat A (count θ A) ++ remove_all atom_eqb A θ) ++ Δ).
+ apply Permutation_app_head, Permutation_app_tail, Permutation_map, remove_all_perm.
+ perm.
-
destruct (derive atom_eqb R q) as [[θ γ a] |] eqn:E; [| discriminate]. cbn in H.
destruct (take atom_eqb A γ a) as [g |] eqn:T; [| discriminate].
injection H as <-; cbn.
specialize (IHq _ eq_refl); cbn in IHq.
pose proof (take_sat [] _ _ _ _ _ T IHq) as H1; cbn in H1.
intros Δ HΔ. eapply ex_r; [apply de_r, (H1 Δ), HΔ | perm].
-
destruct (weakening R || is_wn A) eqn:W; [| discriminate].
destruct (derive atom_eqb R q) as [[θ γ a] |] eqn:E; [| discriminate].
injection H as <-; cbn.
specialize (IHq _ eq_refl); cbn in IHq.
intros Δ HΔ. apply orb_true_iff in W as [W | W].
+ apply (weakening_r R W), IHq, HΔ.
+ destruct A; cbn in W; try discriminate. apply wk_r, IHq, HΔ.
-
destruct (mix R) eqn:M; [| discriminate].
destruct (derive atom_eqb R l) as [[θl γl al] |] eqn:El; [| discriminate].
destruct (derive atom_eqb R r) as [[θr γr ar] |] eqn:Er; [| discriminate].
injection H as <-; cbn.
specialize (IHl _ eq_refl); specialize (IHr _ eq_refl); cbn in IHl, IHr.
intros Δ HΔ. destruct al.
+ eapply ex_r; [apply (mix_r R M); [apply (IHl Δ); easy | apply (IHr []); easy] | perm].
+ destruct ar.
× eapply ex_r; [apply (mix_r R M); [apply (IHl []); easy | apply (IHr Δ); easy] | perm].
× rewrite (HΔ eq_refl).
eapply ex_r; [apply (mix_r R M); [apply (IHl []); easy | apply (IHr []); easy] | perm].
-
destruct (cut R) eqn:C; [| discriminate].
destruct (derive atom_eqb R l) as [[θl γl al] |] eqn:El; [| discriminate].
destruct (derive atom_eqb R r) as [[θr γr ar] |] eqn:Er; [| discriminate].
cbn in H.
destruct (take atom_eqb A γl al) as [gl |] eqn:Tl; [| discriminate].
destruct (take atom_eqb (dual A) γr ar) as [gr |] eqn:Tr; [| discriminate].
injection H as <-; cbn.
specialize (IHl _ eq_refl); specialize (IHr _ eq_refl); cbn in IHl, IHr.
pose proof (take_sat [] _ _ _ _ _ Tl IHl) as Hl; cbn in Hl.
pose proof (take_sat [] _ _ _ _ _ Tr IHr) as Hr; cbn in Hr.
intros Δ HΔ. destruct al.
+ eapply ex_r; [apply (cut_r R C A); [apply (Hl Δ); easy | apply (Hr []); easy] | perm].
+ destruct ar.
× eapply ex_r; [apply (cut_r R C A); [apply (Hl []); easy | apply (Hr Δ); easy] | perm].
× rewrite (HΔ eq_refl).
eapply ex_r; [apply (cut_r R C A); [apply (Hl []); easy | apply (Hr []); easy] | perm].
Qed.
Theorem soundness : ∀ p sequent,
check atom_eqb R p sequent = true → ll R sequent.
Proof.
unfold check; intros p Γ H.
destruct (derive atom_eqb R p) as [[θ γ a] |] eqn:E; [| discriminate].
destruct θ; cbn in H; [| discriminate].
pose proof (derive_sound _ _ E) as S; cbn in S.
destruct (take_all atom_eqb γ Γ) as [[| r rest] |] eqn:T; [| | discriminate];
apply take_all_perm in T.
- eapply ex_r; [apply (S []); easy | rewrite T; perm].
- subst a. eapply ex_r; [apply (S (r :: rest)); easy | rewrite T; perm].
Qed.
End Soundness.
check atom_eqb R p sequent = true → ll R sequent.
Proof.
unfold check; intros p Γ H.
destruct (derive atom_eqb R p) as [[θ γ a] |] eqn:E; [| discriminate].
destruct θ; cbn in H; [| discriminate].
pose proof (derive_sound _ _ E) as S; cbn in S.
destruct (take_all atom_eqb γ Γ) as [[| r rest] |] eqn:T; [| | discriminate];
apply take_all_perm in T.
- eapply ex_r; [apply (S []); easy | rewrite T; perm].
- subst a. eapply ex_r; [apply (S (r :: rest)); easy | rewrite T; perm].
Qed.
End Soundness.
The theorem for classical linear logic: no Mix, no weakening, no
cut.
Theorem soundness_classical {atom : Type} (atom_eqb : atom → atom → bool)
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)) :
∀ (p : proof atom) (sequent : list (formula atom)),
check atom_eqb classical p sequent = true → ll classical sequent.
Proof. exact (soundness atom_eqb atom_eqb_spec classical). Qed.
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)) :
∀ (p : proof atom) (sequent : list (formula atom)),
check atom_eqb classical p sequent = true → ll classical sequent.
Proof. exact (soundness atom_eqb atom_eqb_spec classical). Qed.
The theorem for linear logic with Mix: binary Mix, no weakening, no
cut.
Theorem soundness_mix {atom : Type} (atom_eqb : atom → atom → bool)
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)) :
∀ (p : proof atom) (sequent : list (formula atom)),
check atom_eqb {| mix := true; weakening := false; cut := false |} p sequent = true →
ll {| mix := true; weakening := false; cut := false |} sequent.
Proof. exact (soundness atom_eqb atom_eqb_spec _). Qed.
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)) :
∀ (p : proof atom) (sequent : list (formula atom)),
check atom_eqb {| mix := true; weakening := false; cut := false |} p sequent = true →
ll {| mix := true; weakening := false; cut := false |} sequent.
Proof. exact (soundness atom_eqb atom_eqb_spec _). Qed.
The theorem for affine linear logic: weakening of any formula, no
Mix, no cut.
Theorem soundness_affine {atom : Type} (atom_eqb : atom → atom → bool)
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)) :
∀ (p : proof atom) (sequent : list (formula atom)),
check atom_eqb {| mix := false; weakening := true; cut := false |} p sequent = true →
ll {| mix := false; weakening := true; cut := false |} sequent.
Proof. exact (soundness atom_eqb atom_eqb_spec _). Qed.
(atom_eqb_spec : ∀ a b, reflect (a = b) (atom_eqb a b)) :
∀ (p : proof atom) (sequent : list (formula atom)),
check atom_eqb {| mix := false; weakening := true; cut := false |} p sequent = true →
ll {| mix := false; weakening := true; cut := false |} sequent.
Proof. exact (soundness atom_eqb atom_eqb_spec _). Qed.