drop_refl_atom_O2 drop_drop_lt drop_skip_lt
*)
inductive drops (b:bool): pr_map → relation lenv ≝
-| drops_atom: â\88\80f. (b = â\93\89 â\86\92 ð\9d\90\88â\9dªfâ\9d«) → drops b (f) (⋆) (⋆)
+| drops_atom: â\88\80f. (b = â\93\89 â\86\92 ð\9d\90\88â\9d¨fâ\9d©) → drops b (f) (⋆) (⋆)
| drops_drop: ∀f,I,L1,L2. drops b f L1 L2 → drops b (↑f) (L1.ⓘ[I]) L2
| drops_skip: ∀f,I1,I2,L1,L2.
drops b f L1 L2 → ⇧*[f] I2 ≘ I1 →
∀U. ⇧*[f] T ≘ U → R L U.
definition d_liftable1_isuni: predicate (relation2 lenv term) ≝
- λR. â\88\80K,T. R K T â\86\92 â\88\80b,f,L. â\87©*[b,f] L â\89\98 K â\86\92 ð\9d\90\94â\9dªfâ\9d« →
+ λR. â\88\80K,T. R K T â\86\92 â\88\80b,f,L. â\87©*[b,f] L â\89\98 K â\86\92 ð\9d\90\94â\9d¨fâ\9d© →
∀U. ⇧*[f] T ≘ U → R L U.
definition d_deliftable1: predicate (relation2 lenv term) ≝
∀T. ⇧*[f] T ≘ U → R K T.
definition d_deliftable1_isuni: predicate (relation2 lenv term) ≝
- λR. â\88\80L,U. R L U â\86\92 â\88\80b,f,K. â\87©*[b,f] L â\89\98 K â\86\92 ð\9d\90\94â\9dªfâ\9d« →
+ λR. â\88\80L,U. R L U â\86\92 â\88\80b,f,K. â\87©*[b,f] L â\89\98 K â\86\92 ð\9d\90\94â\9d¨fâ\9d© →
∀T. ⇧*[f] T ≘ U → R K T.
definition d_liftable2_sn: ∀C:Type[0]. ∀S:?→relation C.
∀T2. S f T2 U2 → R K T1 T2.
definition co_dropable_sn: predicate (?→relation lenv) ≝
- λR. â\88\80b,f,L1,K1. â\87©*[b,f] L1 â\89\98 K1 â\86\92 ð\9d\90\94â\9dªfâ\9d« →
+ λR. â\88\80b,f,L1,K1. â\87©*[b,f] L1 â\89\98 K1 â\86\92 ð\9d\90\94â\9d¨fâ\9d© →
∀f2,L2. R f2 L1 L2 → ∀f1. f ~⊚ f1 ≘ f2 →
∃∃K2. R f1 K1 K2 & ⇩*[b,f] L2 ≘ K2.
definition co_dropable_dx: predicate (?→relation lenv) ≝
λR. ∀f2,L1,L2. R f2 L1 L2 →
- â\88\80b,f,K2. â\87©*[b,f] L2 â\89\98 K2 â\86\92 ð\9d\90\94â\9dªfâ\9d« →
+ â\88\80b,f,K2. â\87©*[b,f] L2 â\89\98 K2 â\86\92 ð\9d\90\94â\9d¨fâ\9d© →
∀f1. f ~⊚ f1 ≘ f2 →
∃∃K1. ⇩*[b,f] L1 ≘ K1 & R f1 K1 K2.
(* Basic inversion lemmas ***************************************************)
fact drops_inv_atom1_aux: ∀b,f,X,Y. ⇩*[b,f] X ≘ Y → X = ⋆ →
- Y = â\8b\86 â\88§ (b = â\93\89 â\86\92 ð\9d\90\88â\9dªfâ\9d«).
+ Y = â\8b\86 â\88§ (b = â\93\89 â\86\92 ð\9d\90\88â\9d¨fâ\9d©).
#b #f #X #Y * -f -X -Y
[ /3 width=1 by conj/
| #f #I #L1 #L2 #_ #H destruct
(* Basic_1: includes: drop_gen_sort *)
(* Basic_2A1: includes: drop_inv_atom1 *)
-lemma drops_inv_atom1: â\88\80b,f,Y. â\87©*[b,f] â\8b\86 â\89\98 Y â\86\92 Y = â\8b\86 â\88§ (b = â\93\89 â\86\92 ð\9d\90\88â\9dªfâ\9d«).
+lemma drops_inv_atom1: â\88\80b,f,Y. â\87©*[b,f] â\8b\86 â\89\98 Y â\86\92 Y = â\8b\86 â\88§ (b = â\93\89 â\86\92 ð\9d\90\88â\9d¨fâ\9d©).
/2 width=3 by drops_inv_atom1_aux/ qed-.
fact drops_inv_drop1_aux: ∀b,f,X,Y. ⇩*[b,f] X ≘ Y → ∀g,I,K. X = K.ⓘ[I] → f = ↑g →
(* Basic forward lemmas *****************************************************)
fact drops_fwd_drop2_aux: ∀b,f2,X,Y. ⇩*[b,f2] X ≘ Y → ∀I,K. Y = K.ⓘ[I] →
- â\88\83â\88\83f1,f. ð\9d\90\88â\9dªf1â\9d« & f2 ⊚ ↑f1 ≘ f & ⇩*[b,f] X ≘ K.
+ â\88\83â\88\83f1,f. ð\9d\90\88â\9d¨f1â\9d© & f2 ⊚ ↑f1 ≘ f & ⇩*[b,f] X ≘ K.
#b #f2 #X #Y #H elim H -f2 -X -Y
[ #f2 #Hf2 #J #K #H destruct
| #f2 #I #L1 #L2 #_ #IHL #J #K #H elim (IHL … H) -IHL
qed-.
lemma drops_fwd_drop2: ∀b,f2,I,X,K. ⇩*[b,f2] X ≘ K.ⓘ[I] →
- â\88\83â\88\83f1,f. ð\9d\90\88â\9dªf1â\9d« & f2 ⊚ ↑f1 ≘ f & ⇩*[b,f] X ≘ K.
+ â\88\83â\88\83f1,f. ð\9d\90\88â\9d¨f1â\9d© & f2 ⊚ ↑f1 ≘ f & ⇩*[b,f] X ≘ K.
/2 width=4 by drops_fwd_drop2_aux/ qed-.
(* Properties with test for identity ****************************************)
(* Basic_2A1: includes: drop_refl *)
-lemma drops_refl: â\88\80b,L,f. ð\9d\90\88â\9dªfâ\9d« → ⇩*[b,f] L ≘ L.
+lemma drops_refl: â\88\80b,L,f. ð\9d\90\88â\9d¨fâ\9d© → ⇩*[b,f] L ≘ L.
#b #L elim L -L /2 width=1 by drops_atom/
#L #I #IHL #f #Hf elim (pr_isi_inv_gen … Hf) -Hf
/3 width=1 by drops_skip, liftsb_refl/
(* Basic_1: includes: drop_gen_refl *)
(* Basic_2A1: includes: drop_inv_O2 *)
-lemma drops_fwd_isid: â\88\80b,f,L1,L2. â\87©*[b,f] L1 â\89\98 L2 â\86\92 ð\9d\90\88â\9dªfâ\9d« → L1 = L2.
+lemma drops_fwd_isid: â\88\80b,f,L1,L2. â\87©*[b,f] L1 â\89\98 L2 â\86\92 ð\9d\90\88â\9d¨fâ\9d© → L1 = L2.
#b #f #L1 #L2 #H elim H -f -L1 -L2 //
[ #f #I #L1 #L2 #_ #_ #H elim (pr_isi_inv_next … H) //
| /5 width=5 by pr_isi_inv_push, liftsb_fwd_isid, eq_f2, sym_eq/
qed-.
lemma drops_after_fwd_drop2: ∀b,f2,I,X,K. ⇩*[b,f2] X ≘ K.ⓘ[I] →
- â\88\80f1,f. ð\9d\90\88â\9dªf1â\9d« → f2 ⊚ ↑f1 ≘ f → ⇩*[b,f] X ≘ K.
+ â\88\80f1,f. ð\9d\90\88â\9d¨f1â\9d© → f2 ⊚ ↑f1 ≘ f → ⇩*[b,f] X ≘ K.
#b #f2 #I #X #K #H #f1 #f #Hf1 #Hf elim (drops_fwd_drop2 … H) -H
#g1 #g #Hg1 #Hg #HK lapply (pr_after_mono_eq … Hg … Hf ??) -Hg -Hf
/3 width=5 by drops_eq_repl_back, pr_isi_inv_eq_repl, pr_eq_next/
(* Forward lemmas with test for finite colength *****************************)
-lemma drops_fwd_isfin: â\88\80f,L1,L2. â\87©*[â\93\89,f] L1 â\89\98 L2 â\86\92 ð\9d\90\85â\9dªfâ\9d«.
+lemma drops_fwd_isfin: â\88\80f,L1,L2. â\87©*[â\93\89,f] L1 â\89\98 L2 â\86\92 ð\9d\90\85â\9d¨fâ\9d©.
#f #L1 #L2 #H elim H -f -L1 -L2
/3 width=1 by pr_isf_next, pr_isf_push, pr_isf_isi/
qed-.
(* Properties with test for uniformity **************************************)
-lemma drops_isuni_ex: â\88\80f. ð\9d\90\94â\9dªfâ\9d« → ∀L. ∃K. ⇩*[Ⓕ,f] L ≘ K.
+lemma drops_isuni_ex: â\88\80f. ð\9d\90\94â\9d¨fâ\9d© → ∀L. ∃K. ⇩*[Ⓕ,f] L ≘ K.
#f #H elim H -f /4 width=2 by drops_refl, drops_TF, ex_intro/
#f #_ #g #H #IH destruct * /2 width=2 by ex_intro/
#L #I elim (IH L) -IH /3 width=2 by drops_drop, ex_intro/
(* Inversion lemmas with test for uniformity ********************************)
-lemma drops_inv_isuni: â\88\80f,L1,L2. â\87©*[â\93\89,f] L1 â\89\98 L2 â\86\92 ð\9d\90\94â\9dªfâ\9d« →
- (ð\9d\90\88â\9dªfâ\9d« ∧ L1 = L2) ∨
- â\88\83â\88\83g,I,K. â\87©*[â\93\89,g] K â\89\98 L2 & ð\9d\90\94â\9dªgâ\9d« & L1 = K.ⓘ[I] & f = ↑g.
+lemma drops_inv_isuni: â\88\80f,L1,L2. â\87©*[â\93\89,f] L1 â\89\98 L2 â\86\92 ð\9d\90\94â\9d¨fâ\9d© →
+ (ð\9d\90\88â\9d¨fâ\9d© ∧ L1 = L2) ∨
+ â\88\83â\88\83g,I,K. â\87©*[â\93\89,g] K â\89\98 L2 & ð\9d\90\94â\9d¨gâ\9d© & L1 = K.ⓘ[I] & f = ↑g.
#f #L1 #L2 * -f -L1 -L2
[ /4 width=1 by or_introl, conj/
| /4 width=7 by pr_isu_inv_next, ex4_3_intro, or_intror/
qed-.
(* Basic_2A1: was: drop_inv_O1_pair1 *)
-lemma drops_inv_bind1_isuni: â\88\80b,f,I,K,L2. ð\9d\90\94â\9dªfâ\9d« → ⇩*[b,f] K.ⓘ[I] ≘ L2 →
- (ð\9d\90\88â\9dªfâ\9d« ∧ L2 = K.ⓘ[I]) ∨
- â\88\83â\88\83g. ð\9d\90\94â\9dªgâ\9d« & ⇩*[b,g] K ≘ L2 & f = ↑g.
+lemma drops_inv_bind1_isuni: â\88\80b,f,I,K,L2. ð\9d\90\94â\9d¨fâ\9d© → ⇩*[b,f] K.ⓘ[I] ≘ L2 →
+ (ð\9d\90\88â\9d¨fâ\9d© ∧ L2 = K.ⓘ[I]) ∨
+ â\88\83â\88\83g. ð\9d\90\94â\9d¨gâ\9d© & ⇩*[b,g] K ≘ L2 & f = ↑g.
#b #f #I #K #L2 #Hf #H elim (pr_isu_split … Hf) -Hf * #g #Hg #H0 destruct
[ lapply (drops_inv_skip1 … H) -H * #Z #Y #HY #HZ #H destruct
<(drops_fwd_isid … HY Hg) -Y >(liftsb_fwd_isid … HZ Hg) -Z
qed-.
(* Basic_2A1: was: drop_inv_O1_pair2 *)
-lemma drops_inv_bind2_isuni: â\88\80b,f,I,K,L1. ð\9d\90\94â\9dªfâ\9d« → ⇩*[b,f] L1 ≘ K.ⓘ[I] →
- (ð\9d\90\88â\9dªfâ\9d« ∧ L1 = K.ⓘ[I]) ∨
- â\88\83â\88\83g,I1,K1. ð\9d\90\94â\9dªgâ\9d« & ⇩*[b,g] K1 ≘ K.ⓘ[I] & L1 = K1.ⓘ[I1] & f = ↑g.
+lemma drops_inv_bind2_isuni: â\88\80b,f,I,K,L1. ð\9d\90\94â\9d¨fâ\9d© → ⇩*[b,f] L1 ≘ K.ⓘ[I] →
+ (ð\9d\90\88â\9d¨fâ\9d© ∧ L1 = K.ⓘ[I]) ∨
+ â\88\83â\88\83g,I1,K1. ð\9d\90\94â\9d¨gâ\9d© & ⇩*[b,g] K1 ≘ K.ⓘ[I] & L1 = K1.ⓘ[I1] & f = ↑g.
#b #f #I #K *
[ #Hf #H elim (drops_inv_atom1 … H) -H #H destruct
| #L1 #I1 #Hf #H elim (drops_inv_bind1_isuni … Hf H) -Hf -H *
]
qed-.
-lemma drops_inv_bind2_isuni_next: â\88\80b,f,I,K,L1. ð\9d\90\94â\9dªfâ\9d« → ⇩*[b,↑f] L1 ≘ K.ⓘ[I] →
+lemma drops_inv_bind2_isuni_next: â\88\80b,f,I,K,L1. ð\9d\90\94â\9d¨fâ\9d© → ⇩*[b,↑f] L1 ≘ K.ⓘ[I] →
∃∃I1,K1. ⇩*[b,f] K1 ≘ K.ⓘ[I] & L1 = K1.ⓘ[I1].
#b #f #I #K #L1 #Hf #H elim (drops_inv_bind2_isuni … H) -H /2 width=3 by pr_isu_next/ -Hf *
[ #H elim (pr_isi_inv_next … H) -H //
]
qed-.
-fact drops_inv_TF_aux: â\88\80f,L1,L2. â\87©*[â\92»,f] L1 â\89\98 L2 â\86\92 ð\9d\90\94â\9dªfâ\9d« →
+fact drops_inv_TF_aux: â\88\80f,L1,L2. â\87©*[â\92»,f] L1 â\89\98 L2 â\86\92 ð\9d\90\94â\9d¨fâ\9d© →
∀I,K. L2 = K.ⓘ[I] → ⇩*[Ⓣ,f] L1 ≘ K.ⓘ[I].
#f #L1 #L2 #H elim H -f -L1 -L2
[ #f #_ #_ #J #K #H destruct
qed-.
(* Basic_2A1: includes: drop_inv_FT *)
-lemma drops_inv_TF: â\88\80f,I,L,K. â\87©*[â\92»,f] L â\89\98 K.â\93\98[I] â\86\92 ð\9d\90\94â\9dªfâ\9d« → ⇩*[Ⓣ,f] L ≘ K.ⓘ[I].
+lemma drops_inv_TF: â\88\80f,I,L,K. â\87©*[â\92»,f] L â\89\98 K.â\93\98[I] â\86\92 ð\9d\90\94â\9d¨fâ\9d© → ⇩*[Ⓣ,f] L ≘ K.ⓘ[I].
/2 width=3 by drops_inv_TF_aux/ qed-.
(* Basic_2A1: includes: drop_inv_gen *)
-lemma drops_inv_gen: â\88\80b,f,I,L,K. â\87©*[b,f] L â\89\98 K.â\93\98[I] â\86\92 ð\9d\90\94â\9dªfâ\9d« → ⇩*[Ⓣ,f] L ≘ K.ⓘ[I].
+lemma drops_inv_gen: â\88\80b,f,I,L,K. â\87©*[b,f] L â\89\98 K.â\93\98[I] â\86\92 ð\9d\90\94â\9d¨fâ\9d© → ⇩*[Ⓣ,f] L ≘ K.ⓘ[I].
* /2 width=1 by drops_inv_TF/
qed-.
(* Basic_2A1: includes: drop_inv_T *)
-lemma drops_inv_F: â\88\80b,f,I,L,K. â\87©*[â\92»,f] L â\89\98 K.â\93\98[I] â\86\92 ð\9d\90\94â\9dªfâ\9d« → ⇩*[b,f] L ≘ K.ⓘ[I].
+lemma drops_inv_F: â\88\80b,f,I,L,K. â\87©*[â\92»,f] L â\89\98 K.â\93\98[I] â\86\92 ð\9d\90\94â\9d¨fâ\9d© → ⇩*[b,f] L ≘ K.ⓘ[I].
* /2 width=1 by drops_inv_TF/
qed-.
(* Basic_1: was: drop_S *)
(* Basic_2A1: was: drop_fwd_drop2 *)
-lemma drops_isuni_fwd_drop2: â\88\80b,f,I,X,K. ð\9d\90\94â\9dªfâ\9d« → ⇩*[b,f] X ≘ K.ⓘ[I] → ⇩*[b,↑f] X ≘ K.
+lemma drops_isuni_fwd_drop2: â\88\80b,f,I,X,K. ð\9d\90\94â\9d¨fâ\9d© → ⇩*[b,f] X ≘ K.ⓘ[I] → ⇩*[b,↑f] X ≘ K.
/3 width=7 by drops_after_fwd_drop2, pr_after_isu_isi_next/ qed-.
(* Inversion lemmas with uniform relocations ********************************)
qed-.
(* Basic_2A1: includes: drop_split *)
-lemma drops_split_trans: â\88\80b,f,L1,L2. â\87©*[b,f] L1 â\89\98 L2 â\86\92 â\88\80f1,f2. f1 â\8a\9a f2 â\89\98 f â\86\92 ð\9d\90\94â\9dªf1â\9d« →
+lemma drops_split_trans: â\88\80b,f,L1,L2. â\87©*[b,f] L1 â\89\98 L2 â\86\92 â\88\80f1,f2. f1 â\8a\9a f2 â\89\98 f â\86\92 ð\9d\90\94â\9d¨f1â\9d© →
∃∃L. ⇩*[b,f1] L1 ≘ L & ⇩*[b,f2] L ≘ L2.
#b #f #L1 #L2 #H elim H -f -L1 -L2
[ #f #H0f #f1 #f2 #Hf #Hf1 @(ex2_intro … (⋆)) @drops_atom
]
qed-.
-lemma drops_split_div: â\88\80b,f1,L1,L. â\87©*[b,f1] L1 â\89\98 L â\86\92 â\88\80f2,f. f1 â\8a\9a f2 â\89\98 f â\86\92 ð\9d\90\94â\9dªf2â\9d« →
+lemma drops_split_div: â\88\80b,f1,L1,L. â\87©*[b,f1] L1 â\89\98 L â\86\92 â\88\80f2,f. f1 â\8a\9a f2 â\89\98 f â\86\92 ð\9d\90\94â\9d¨f2â\9d© →
∃∃L2. ⇩*[Ⓕ,f2] L ≘ L2 & ⇩*[Ⓕ,f] L1 ≘ L2.
#b #f1 #L1 #L #H elim H -f1 -L1 -L
[ #f1 #Hf1 #f2 #f #Hf #Hf2 @(ex2_intro … (⋆)) @drops_atom #H destruct
(* Properties with application **********************************************)
-lemma drops_tls_at: â\88\80f,i1,i2. @â\9dªi1,fâ\9d« ≘ i2 →
+lemma drops_tls_at: â\88\80f,i1,i2. @â\9d¨i1,fâ\9d© ≘ i2 →
∀b,L1,L2. ⇩*[b,⫰*[i2]f] L1 ≘ L2 →
⇩*[b,⫯⫰*[↑i2]f] L1 ≘ L2.
/3 width=3 by drops_eq_repl_fwd, pr_pat_inv_succ_dx_tls/ qed-.
-lemma drops_split_trans_bind2: â\88\80b,f,I,L,K0. â\87©*[b,f] L â\89\98 K0.â\93\98[I] â\86\92 â\88\80i. @â\9dªO,fâ\9d« ≘ i →
+lemma drops_split_trans_bind2: â\88\80b,f,I,L,K0. â\87©*[b,f] L â\89\98 K0.â\93\98[I] â\86\92 â\88\80i. @â\9d¨O,fâ\9d© ≘ i →
∃∃J,K. ⇩[i]L ≘ K.ⓘ[J] & ⇩*[b,⫰*[↑i]f] K ≘ K0 & ⇧*[⫰*[↑i]f] I ≘ J.
#b #f #I #L #K0 #H #i #Hf
elim (drops_split_trans … H) -H [ |5: @(pr_after_nat_uni … Hf) |2,3: skip ] /2 width=1 by pr_after_isi_dx/ #Y #HLY #H