Library Deduxit.Linear.Mix
Mix as a hypothesis ?(⊥ ⊗ ⊥)
From Stdlib Require Import List Permutation.
From Deduxit.Linear Require Export Calculus.
Import ListNotations.
Section Mix.
Context {atom : Type}.
Local Notation formula := (formula atom).
A rule with one premise, applied behind an extra first formula
X.
Lemma behind : ∀ R (X A B : formula) l,
(∀ m, ll R (A :: m) → ll R (B :: m)) → ll R (X :: A :: l) → ll R (X :: B :: l).
Proof.
intros R X A B l rule H.
eapply ex_r; [apply rule; eapply ex_r; [exact H | apply perm_swap] | apply perm_swap].
Qed.
(∀ m, ll R (A :: m) → ll R (B :: m)) → ll R (X :: A :: l) → ll R (X :: B :: l).
Proof.
intros R X A B l rule H.
eapply ex_r; [apply rule; eapply ex_r; [exact H | apply perm_swap] | apply perm_swap].
Qed.
A derivation of ⊢ Γ in any calculus gives a derivation of
⊢ ?(⊥ ⊗ ⊥), Γ in the same calculus without Mix, with the same
weakening and cut.
Theorem mix_to_ll : ∀ R (l : list formula),
ll R l →
ll {| mix := false; weakening := weakening R; cut := cut R |} (wn (tens bot bot) :: l).
Proof.
intros R l H. set (R' := {| mix := false; weakening := weakening R; cut := cut R |}).
induction H.
- apply wk_r, ax_r.
- eapply ex_r; [exact IHll | apply perm_skip, H0].
- apply wk_r, one_r.
- eapply ex_r; [apply bot_r, IHll | apply perm_swap].
- apply wk_r, top_r.
- apply co_r.
eapply ex_r.
+ apply (tens_r _ A B (wn (tens bot bot) :: l1) (wn (tens bot bot) :: l2)).
× eapply ex_r; [exact IHll1 | apply perm_swap].
× eapply ex_r; [exact IHll2 | apply perm_swap].
+ cbn. rewrite <- Permutation_middle.
apply perm_trans with (wn (tens bot bot) :: tens A B :: wn (tens bot bot) :: l1 ++ l2);
[apply perm_swap | apply perm_skip, perm_swap].
- eapply ex_r; [apply parr_r | apply perm_swap].
eapply ex_r; [exact IHll |].
apply perm_trans with (A :: wn (tens bot bot) :: B :: l);
[apply perm_swap | apply perm_skip, perm_swap].
- eapply ex_r; [apply with_r | apply perm_swap].
+ eapply ex_r; [exact IHll1 | apply perm_swap].
+ eapply ex_r; [exact IHll2 | apply perm_swap].
- revert IHll. apply behind. intro. apply plus_r1.
- revert IHll. apply behind. intro. apply plus_r2.
- eapply ex_r; [| apply perm_swap].
apply (oc_r R' A (tens bot bot :: l)).
eapply ex_r; [exact IHll | apply perm_swap].
- revert IHll. apply behind. intro. apply de_r.
- eapply ex_r; [apply wk_r, IHll | apply perm_swap].
- eapply ex_r; [apply co_r | apply perm_swap].
eapply ex_r; [exact IHll |].
apply perm_trans with (wn A :: wn (tens bot bot) :: wn A :: l);
[apply perm_swap | apply perm_skip, perm_swap].
-
apply co_r, co_r.
eapply ex_r.
+ apply de_r.
apply (tens_r _ bot bot (wn (tens bot bot) :: l1) (wn (tens bot bot) :: l2));
apply bot_r; [exact IHll1 | exact IHll2].
+ cbn. apply perm_skip, perm_skip, Permutation_sym, Permutation_middle.
- eapply ex_r; [apply weakening_r, IHll | apply perm_swap]. assumption.
-
apply co_r.
eapply ex_r.
+ refine (cut_r R' _ A (wn (tens bot bot) :: l1) (wn (tens bot bot) :: l2) _ _).
× assumption.
× eapply ex_r; [exact IHll1 | apply perm_swap].
× eapply ex_r; [exact IHll2 | apply perm_swap].
+ cbn. apply perm_skip. symmetry. apply Permutation_middle.
Qed.
ll R l →
ll {| mix := false; weakening := weakening R; cut := cut R |} (wn (tens bot bot) :: l).
Proof.
intros R l H. set (R' := {| mix := false; weakening := weakening R; cut := cut R |}).
induction H.
- apply wk_r, ax_r.
- eapply ex_r; [exact IHll | apply perm_skip, H0].
- apply wk_r, one_r.
- eapply ex_r; [apply bot_r, IHll | apply perm_swap].
- apply wk_r, top_r.
- apply co_r.
eapply ex_r.
+ apply (tens_r _ A B (wn (tens bot bot) :: l1) (wn (tens bot bot) :: l2)).
× eapply ex_r; [exact IHll1 | apply perm_swap].
× eapply ex_r; [exact IHll2 | apply perm_swap].
+ cbn. rewrite <- Permutation_middle.
apply perm_trans with (wn (tens bot bot) :: tens A B :: wn (tens bot bot) :: l1 ++ l2);
[apply perm_swap | apply perm_skip, perm_swap].
- eapply ex_r; [apply parr_r | apply perm_swap].
eapply ex_r; [exact IHll |].
apply perm_trans with (A :: wn (tens bot bot) :: B :: l);
[apply perm_swap | apply perm_skip, perm_swap].
- eapply ex_r; [apply with_r | apply perm_swap].
+ eapply ex_r; [exact IHll1 | apply perm_swap].
+ eapply ex_r; [exact IHll2 | apply perm_swap].
- revert IHll. apply behind. intro. apply plus_r1.
- revert IHll. apply behind. intro. apply plus_r2.
- eapply ex_r; [| apply perm_swap].
apply (oc_r R' A (tens bot bot :: l)).
eapply ex_r; [exact IHll | apply perm_swap].
- revert IHll. apply behind. intro. apply de_r.
- eapply ex_r; [apply wk_r, IHll | apply perm_swap].
- eapply ex_r; [apply co_r | apply perm_swap].
eapply ex_r; [exact IHll |].
apply perm_trans with (wn A :: wn (tens bot bot) :: wn A :: l);
[apply perm_swap | apply perm_skip, perm_swap].
-
apply co_r, co_r.
eapply ex_r.
+ apply de_r.
apply (tens_r _ bot bot (wn (tens bot bot) :: l1) (wn (tens bot bot) :: l2));
apply bot_r; [exact IHll1 | exact IHll2].
+ cbn. apply perm_skip, perm_skip, Permutation_sym, Permutation_middle.
- eapply ex_r; [apply weakening_r, IHll | apply perm_swap]. assumption.
-
apply co_r.
eapply ex_r.
+ refine (cut_r R' _ A (wn (tens bot bot) :: l1) (wn (tens bot bot) :: l2) _ _).
× assumption.
× eapply ex_r; [exact IHll1 | apply perm_swap].
× eapply ex_r; [exact IHll2 | apply perm_swap].
+ cbn. apply perm_skip. symmetry. apply Permutation_middle.
Qed.
From Mix to classical linear logic: a derivation of ⊢ Γ with Mix
gives one of ⊢ ?(⊥ ⊗ ⊥), Γ in classical linear logic.