(* File: NSound.v  (last edited on 27/10/2000) (c) Klaus Weich  *)

Require Export Le_Ks.
Require Export Derivable_Tools.

Definition nsound (work : nf_list) (ds : disjs) (ni : nested_imps)
  (ai : atomic_imps) (a : atoms) (context : flist) :=
  forall c : normal_form,
  in_ngamma work ds ni ai a c -> Derivable context (nf2form c).


Lemma nsound_eqv :
 forall (work : nf_list) (ds : disjs) (ni1 ni2 : nested_imps)
   (ai : atomic_imps) (a : atoms) (context : flist),
 eqv_ni ni1 ni2 ->
 nsound work ds ni1 ai a context -> nsound work ds ni2 ai a context.
(* Goal: forall (work : nf_list) (ds : disjs) (ni1 ni2 : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : eqv_ni ni1 ni2) (_ : nsound work ds ni1 ai a context), nsound work ds ni2 ai a context *)
intros work ds ni1 ni2 ai a context eq12 sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni1 ai a c *)
apply in_ngamma_eqv with ni2. 
(* Goal: eqv_ni ni2 ni1 *)
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply eqv_sym; assumption.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
assumption.
Qed.


Lemma nsound_le :
 forall (work : nf_list) (ds : disjs) (ni1 ni2 : nested_imps)
   (ai : atomic_imps) (a : atoms) (context : flist),
 le_ni ni1 ni2 ->
 nsound work ds ni1 ai a context -> nsound work ds ni2 ai a context.
(* Goal: forall (work : nf_list) (ds : disjs) (ni1 ni2 : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : le_ni ni2 ni1) (_ : nsound work ds ni1 ai a context), nsound work ds ni2 ai a context *)
intros work ds ni1 ni2 ai a context le sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_ge with ni2; assumption.
Qed.


Lemma nsound_ge :
 forall (work : nf_list) (ds : disjs) (ni1 ni2 : nested_imps)
   (ai : atomic_imps) (a : atoms) (context : flist),
 le_ni ni2 ni1 ->
 nsound work ds ni1 ai a context -> nsound work ds ni2 ai a context.
(* Goal: forall (work : nf_list) (ds : disjs) (ni1 ni2 : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : le_ni ni2 ni1) (_ : nsound work ds ni1 ai a context), nsound work ds ni2 ai a context *)
intros work ds ni1 ni2 ai a context le sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_le with ni2; assumption.
Qed.


(***********************************************************************)



Lemma nsound_shift_work_ds :
 forall (i j : Int) (work : nf_list) (ds : disjs) (ni : nested_imps)
   (ai : atomic_imps) (a : atoms) (context : flist),
 nsound (NDisj i j :: work) ds ni ai a context ->
 nsound work ((i, j) :: ds) ni ai a context.
(* Goal: forall (i j : Int) (work : nf_list) (ds : disjs) (ni : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : nsound (@cons normal_form (NDisj i j) work) ds ni ai a context), nsound work (@cons (prod Int Int) (@pair Int Int i j) ds) ni ai a context *)
intros i j work ds ni ai a context sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_shift_ds_work; assumption.
Qed.




Lemma nsound_shift_work_ni :
 forall (x : nested_imp) (work : nf_list) (ds : disjs) 
   (ni : nested_imps) (ai : atomic_imps) (a : atoms) 
   (context : flist),
 nsound (NImp_NF (nested_imp2nimp x) :: work) ds ni ai a context ->
 nsound work ds (x :: ni) ai a context.
(* Goal: forall (x : nested_imp) (work : nf_list) (ds : disjs) (ni : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : nsound (@cons normal_form (NImp_NF (nested_imp2nimp x)) work) ds ni ai a context), nsound work ds (@cons nested_imp x ni) ai a context *)
intros x work ds ni ai a context sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_shift_ni_work; assumption.
Qed.







Lemma nsound_shift_work_ai :
 forall (i : Int) (b : normal_form) (work : nf_list) 
   (ds : disjs) (ni : nested_imps) (ai ai' : atomic_imps) 
   (a : atoms) (context : flist),
 EQUIV_INS nf_list i (cons b) nf_nil ai ai' ->
 nsound (AImp i b :: work) ds ni ai a context ->
 nsound work ds ni ai' a context.
(* Goal: forall (i : Int) (b : normal_form) (work : nf_list) (ds : disjs) (ni : nested_imps) (ai ai' : atomic_imps) (a : atoms) (context : flist) (_ : EQUIV_INS nf_list i (@cons normal_form b) nf_nil ai ai') (_ : nsound (@cons normal_form (AImp i b) work) ds ni ai a context), nsound work ds ni ai' a context *)
intros i b work ds ni ai ai' a context equiv_ins sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_shift_ai_work with ai'; assumption.
Qed.






Lemma nsound_shift_work_a :
 forall (i : Int) (work : nf_list) (ds : disjs) (ni : nested_imps)
   (ai : atomic_imps) (a a' : atoms) (context : flist),
 EQUIV_INS unit i (fun _ : unit => tt) tt a a' ->
 nsound (NAtom i :: work) ds ni ai a context ->
 nsound work ds ni ai a' context.
(* Goal: forall (i : Int) (work : nf_list) (ds : disjs) (ni : nested_imps) (ai : atomic_imps) (a a' : atoms) (context : flist) (_ : EQUIV_INS unit i (fun _ : unit => tt) tt a a') (_ : nsound (@cons normal_form (NAtom i) work) ds ni ai a context), nsound work ds ni ai a' context *)
intros i work ds ni ai a a' context equiv_ins sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_shift_a_work with a'; assumption.
Qed.


Lemma nsound_shift_work_ni_x_ni :
 forall (x : nested_imp) (work : nf_list) (ds : disjs)
   (ni1 ni2 : nested_imps) (ai : atomic_imps) (a : atoms) 
   (context : flist),
 nsound (NImp_NF (nested_imp2nimp x) :: work) ds (ni1 ++ ni2) ai a context ->
 nsound work ds (ni1 ++ x :: ni2) ai a context.
(* Goal: forall (x : nested_imp) (work : nf_list) (ds : disjs) (ni1 ni2 : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : nsound work ds (@app nested_imp ni1 (@cons nested_imp x ni2)) ai a context), nsound (@cons normal_form (NImp_NF (nested_imp2nimp x)) work) ds (@app nested_imp ni1 ni2) ai a context *)
intros x work ds ni1 ni2 ai a context sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_shift_ni_x_ni_work; assumption.
Qed.


Lemma nsound_shift_ni_x_ni_work :
 forall (x : nested_imp) (work : nf_list) (ds : disjs)
   (ni1 ni2 : nested_imps) (ai : atomic_imps) (a : atoms) 
   (context : flist),
 nsound work ds (ni1 ++ x :: ni2) ai a context ->
 nsound (NImp_NF (nested_imp2nimp x) :: work) ds (ni1 ++ ni2) ai a context.
(* Goal: forall (x : nested_imp) (work : nf_list) (ds : disjs) (ni1 ni2 : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : nsound work ds (@app nested_imp ni1 (@cons nested_imp x ni2)) ai a context), nsound (@cons normal_form (NImp_NF (nested_imp2nimp x)) work) ds (@app nested_imp ni1 ni2) ai a context *)
intros x work ds ni1 ni2 ai a context sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_shift_work_ni_x_ni; assumption.
Qed.



(***********************************************************************)


Remark nsound_app_work :
 forall (bs work : nf_list) (ds : disjs) (ni : nested_imps)
   (ai : atomic_imps) (a : atoms) (context : flist),
 (forall (n : nat) (b : normal_form),
  my_nth normal_form n bs b -> Derivable context (nf2form b)) ->
 nsound work ds ni ai a context -> nsound (bs ++ work) ds ni ai a context.
(* Goal: forall (bs work : nf_list) (ds : disjs) (ni : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : forall (n : nat) (b : normal_form) (_ : my_nth normal_form n bs b), Derivable context (nf2form b)) (_ : nsound work ds ni ai a context), nsound (@app normal_form bs work) ds ni ai a context *)
intros bs work ds ni ai a context der_bs sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form c) *)
elim (in_ngamma_work_app_rev bs work ds ni ai a c in_ngamma); clear in_ngamma.
(* Goal: forall _ : in_ngamma work ds ni ai a c0, Derivable context (nf2form c0) *)
(* Goal: forall _ : @eq normal_form c0 c, Derivable context (nf2form c0) *)
intros in_ngamma.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply sound; assumption.
(* Goal: forall _ : @sig nat (fun n : nat => my_nth normal_form n bs c), Derivable context (nf2form c) *)
intros nth; elim nth; clear nth.
(* Goal: forall (x : nat) (_ : my_nth normal_form x bs c), Derivable context (nf2form c) *)
intros n nth.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply der_bs with n; assumption.
Qed.



Lemma nsound_cons_ds_tail :
 forall (work : nf_list) (i j : Int) (ds : disjs) (ni : nested_imps)
   (ai : atomic_imps) (a : atoms) (context : flist),
 nsound work ((i, j) :: ds) ni ai a context -> nsound work ds ni ai a context.
(* Goal: forall (work : nf_list) (i j : Int) (ds : disjs) (ni : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : nsound work (@cons (prod Int Int) (@pair Int Int i j) ds) ni ai a context), nsound work ds ni ai a context *)
intros work i j ds ni ai a context sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_cons_ds_tail; assumption.
Qed.


Remark nsound_del_ai :
 forall (i : Int) (work : nf_list) (ds : disjs) (ni : nested_imps)
   (ai ai' : atomic_imps) (a : atoms) (context : flist),
 EQUIV_DEL nf_list i ai ai' ->
 nsound work ds ni ai a context -> nsound work ds ni ai' a context.
(* Goal: forall (i : Int) (work : nf_list) (ds : disjs) (ni : nested_imps) (ai ai' : atomic_imps) (a : atoms) (context : flist) (_ : EQUIV_DEL nf_list i ai ai') (_ : nsound work ds ni ai a context), nsound work ds ni ai' a context *)
intros i work ds ni ai ai' a context equiv_del sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c : normal_form) (_ : in_ngamma work ds ni ai' a c), Derivable context (nf2form c) *)
intros c in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_del_ai_tail with i ai'; assumption.
Qed.





(***********************************************************************)


Lemma nsound_cons_work_cons_context :
 forall (c : normal_form) (work : nf_list) (ds : disjs) 
   (ni : nested_imps) (ai : atomic_imps) (a : atoms) 
   (context : flist),
 nsound work ds ni ai a context ->
 nsound (c :: work) ds ni ai a (nf2form c :: context).
(* Goal: forall (c : normal_form) (work : nf_list) (ds : disjs) (ni : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : nsound work ds ni ai a context), nsound (@cons normal_form c work) ds ni ai a (@cons form (nf2form c) context) *)
intros c work ds ni ai a context sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c0 : normal_form) (_ : in_ngamma (@cons normal_form c work) ds ni ai a c0), Derivable (@cons form (nf2form c) context) (nf2form c0) *)
intros c0 in_gamma.
(* Goal: Derivable (@cons form (nf2form c) context) (nf2form c0) *)
elim (in_ngamma_cons_work_rev c work ds ni ai a c0 in_gamma); clear in_gamma.
(* Goal: forall _ : in_ngamma work ds ni ai a c0, Derivable (@cons form (nf2form c) context) (nf2form c0) *)
(* Goal: forall _ : @eq normal_form c0 c, Derivable (@cons form (nf2form c) context) (nf2form c0) *)
intros in_gamma.
(* Goal: Derivable (@cons form (nf2form c) context) (nf2form c0) *)
(* Goal: forall _ : @eq normal_form c0 c, Derivable (@cons form (nf2form c) context) (nf2form c0) *)
apply derivable_weak.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply sound; assumption.
intros eq;  rewrite eq; clear eq.
(* Goal: Derivable (@cons form (nf2form c) context) (nf2form c) *)
apply Derivable_Intro with (Var 0).
(* Goal: derives (@cons form (nf2form c) context) (Var O) (nf2form c) *)
apply ByAssumption.
(* Goal: my_nth form O (@cons form (nf2form c) context) (nf2form c) *)
apply My_NthO.
Qed.

(**********************************************************************)


Lemma nsound_cons_work_weak :
 forall (b c : normal_form) (work : nf_list) (ds : disjs) 
   (ni : nested_imps) (ai : atomic_imps) (a : atoms) 
   (context : flist),
 (Derivable context (nf2form b) -> Derivable context (nf2form c)) ->
 nsound (b :: work) ds ni ai a context ->
 nsound (c :: work) ds ni ai a context.
(* Goal: forall (b c : normal_form) (work : nf_list) (ds : disjs) (ni : nested_imps) (ai : atomic_imps) (a : atoms) (context : flist) (_ : forall _ : Derivable context (nf2form b), Derivable context (nf2form c)) (_ : nsound (@cons normal_form b work) ds ni ai a context), nsound (@cons normal_form c work) ds ni ai a context *)
intros b c work ds ni ai a context der_ab sound.
(* Goal: nsound (@cons normal_form c work) ds ni ai a context *)
unfold nsound in |- *.
(* Goal: forall (c0 : normal_form) (_ : in_ngamma (@cons normal_form c work) ds ni ai a c0), Derivable context (nf2form c0) *)
intros c0 in_ngamma.
elim (in_ngamma_cons_work_rev c work ds ni ai a c0 in_ngamma);
 clear in_ngamma.
(* Goal: forall _ : in_ngamma work ds ni ai a c0, Derivable context (nf2form c0) *)
(* Goal: forall _ : @eq normal_form c0 c, Derivable context (nf2form c0) *)
intros in_ngamma.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_cons_work_tail; assumption.
intros eq;  rewrite eq; clear eq c0.
(* Goal: Derivable context (nf2form c) *)
apply der_ab.
(* Goal: Derivable context (nf2form b) *)
apply sound.
(* Goal: in_ngamma (@cons normal_form b work) ds ni ai a b *)
apply in_ngamma_cons_work_head.
Qed.




Lemma nsound_shift_work_ai_strength :
 forall (i : Int) (bs work : nf_list) (ds : disjs) 
   (ni : nested_imps) (ai ai' : atomic_imps) (a a' : atoms) 
   (context : flist),
 EQUIV_INS unit i (fun _ : unit => tt) tt a a' ->
 LOOKUP nf_list i ai bs ->
 EQUIV_DEL nf_list i ai ai' ->
 nsound work ds ni ai a' context -> nsound (bs ++ work) ds ni ai' a' context.
(* Goal: forall (i : Int) (bs work : nf_list) (ds : disjs) (ni : nested_imps) (ai ai' : atomic_imps) (a a' : atoms) (context : flist) (_ : EQUIV_INS unit i (fun _ : unit => tt) tt a a') (_ : LOOKUP nf_list i ai bs) (_ : EQUIV_DEL nf_list i ai ai') (_ : nsound work ds ni ai a' context), nsound (@app normal_form bs work) ds ni ai' a' context *)
intros i bs work ds ni ai ai' a a' context equiv_ins lookup equiv_del sound.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply nsound_app_work; try assumption.
(* Goal: forall (n : nat) (b : normal_form) (_ : my_nth normal_form n bs b), Derivable context (nf2form b) *)
(* Goal: nsound work ds ni ai' a' context *)
intros n b nth.
(* Goal: Derivable context (nf2form b) *)
(* Goal: nsound work ds ni ai' a' context *)
apply derivable_a_a_imp_b__derivable_b with (Atom i).
(* Goal: Derivable context (Atom i) *)
(* Goal: Derivable context (Imp (Atom i) (nf2form b)) *)
(* Goal: nsound work ds ni ai' a' context *)
apply sound with (c := NAtom i).
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply in_ngamma_ins_a_head with a; assumption.
(* Goal: Derivable context (Imp (Atom i) (nf2form b)) *)
(* Goal: nsound work ds ni ai' a' context *)
apply sound with (c := AImp i b).
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply In_Atomic_Imps with (i := i) (b := b) (n := n) (bs := bs); assumption.
(* Goal: In_NGamma.in_ngamma work ds ni2 ai a c *)
apply nsound_del_ai with i ai; assumption.
Qed.

