+theorem lift1_free:
+ \forall (hds: PList).(\forall (i: nat).(\forall (t: T).(eq T (lift1 hds
+(lift (S i) O t)) (lift (S (trans hds i)) O (ctrans hds i t)))))
+\def
+ \lambda (hds: PList).(PList_ind (\lambda (p: PList).(\forall (i:
+nat).(\forall (t: T).(eq T (lift1 p (lift (S i) O t)) (lift (S (trans p i)) O
+(ctrans p i t)))))) (\lambda (i: nat).(\lambda (t: T).(refl_equal T (lift (S
+i) O t)))) (\lambda (h: nat).(\lambda (d: nat).(\lambda (hds0:
+PList).(\lambda (H: ((\forall (i: nat).(\forall (t: T).(eq T (lift1 hds0
+(lift (S i) O t)) (lift (S (trans hds0 i)) O (ctrans hds0 i t))))))).(\lambda
+(i: nat).(\lambda (t: T).(eq_ind_r T (lift (S (trans hds0 i)) O (ctrans hds0
+i t)) (\lambda (t0: T).(eq T (lift h d t0) (lift (S (match (blt (trans hds0
+i) d) with [true \Rightarrow (trans hds0 i) | false \Rightarrow (plus (trans
+hds0 i) h)])) O (match (blt (trans hds0 i) d) with [true \Rightarrow (lift h
+(minus d (S (trans hds0 i))) (ctrans hds0 i t)) | false \Rightarrow (ctrans
+hds0 i t)])))) (xinduction bool (blt (trans hds0 i) d) (\lambda (b: bool).(eq
+T (lift h d (lift (S (trans hds0 i)) O (ctrans hds0 i t))) (lift (S (match b
+with [true \Rightarrow (trans hds0 i) | false \Rightarrow (plus (trans hds0
+i) h)])) O (match b with [true \Rightarrow (lift h (minus d (S (trans hds0
+i))) (ctrans hds0 i t)) | false \Rightarrow (ctrans hds0 i t)])))) (\lambda
+(x_x: bool).(bool_ind (\lambda (b: bool).((eq bool (blt (trans hds0 i) d) b)
+\to (eq T (lift h d (lift (S (trans hds0 i)) O (ctrans hds0 i t))) (lift (S
+(match b with [true \Rightarrow (trans hds0 i) | false \Rightarrow (plus
+(trans hds0 i) h)])) O (match b with [true \Rightarrow (lift h (minus d (S
+(trans hds0 i))) (ctrans hds0 i t)) | false \Rightarrow (ctrans hds0 i
+t)]))))) (\lambda (H0: (eq bool (blt (trans hds0 i) d) true)).(eq_ind_r nat
+(plus (S (trans hds0 i)) (minus d (S (trans hds0 i)))) (\lambda (n: nat).(eq
+T (lift h n (lift (S (trans hds0 i)) O (ctrans hds0 i t))) (lift (S (trans
+hds0 i)) O (lift h (minus d (S (trans hds0 i))) (ctrans hds0 i t)))))
+(eq_ind_r T (lift (S (trans hds0 i)) O (lift h (minus d (S (trans hds0 i)))
+(ctrans hds0 i t))) (\lambda (t0: T).(eq T t0 (lift (S (trans hds0 i)) O
+(lift h (minus d (S (trans hds0 i))) (ctrans hds0 i t))))) (refl_equal T
+(lift (S (trans hds0 i)) O (lift h (minus d (S (trans hds0 i))) (ctrans hds0
+i t)))) (lift h (plus (S (trans hds0 i)) (minus d (S (trans hds0 i)))) (lift
+(S (trans hds0 i)) O (ctrans hds0 i t))) (lift_d (ctrans hds0 i t) h (S
+(trans hds0 i)) (minus d (S (trans hds0 i))) O (le_O_n (minus d (S (trans
+hds0 i)))))) d (le_plus_minus (S (trans hds0 i)) d (bge_le (S (trans hds0 i))
+d (le_bge (S (trans hds0 i)) d (lt_le_S (trans hds0 i) d (blt_lt d (trans
+hds0 i) H0))))))) (\lambda (H0: (eq bool (blt (trans hds0 i) d)
+false)).(eq_ind_r T (lift (plus h (S (trans hds0 i))) O (ctrans hds0 i t))
+(\lambda (t0: T).(eq T t0 (lift (S (plus (trans hds0 i) h)) O (ctrans hds0 i
+t)))) (eq_ind nat (S (plus h (trans hds0 i))) (\lambda (n: nat).(eq T (lift n
+O (ctrans hds0 i t)) (lift (S (plus (trans hds0 i) h)) O (ctrans hds0 i t))))
+(eq_ind_r nat (plus (trans hds0 i) h) (\lambda (n: nat).(eq T (lift (S n) O
+(ctrans hds0 i t)) (lift (S (plus (trans hds0 i) h)) O (ctrans hds0 i t))))
+(refl_equal T (lift (S (plus (trans hds0 i) h)) O (ctrans hds0 i t))) (plus h
+(trans hds0 i)) (plus_comm h (trans hds0 i))) (plus h (S (trans hds0 i)))
+(plus_n_Sm h (trans hds0 i))) (lift h d (lift (S (trans hds0 i)) O (ctrans
+hds0 i t))) (lift_free (ctrans hds0 i t) (S (trans hds0 i)) h O d (eq_ind nat
+(S (plus O (trans hds0 i))) (\lambda (n: nat).(le d n)) (eq_ind_r nat (plus
+(trans hds0 i) O) (\lambda (n: nat).(le d (S n))) (le_S d (plus (trans hds0
+i) O) (le_plus_trans d (trans hds0 i) O (bge_le d (trans hds0 i) H0))) (plus
+O (trans hds0 i)) (plus_comm O (trans hds0 i))) (plus O (S (trans hds0 i)))
+(plus_n_Sm O (trans hds0 i))) (le_O_n d)))) x_x))) (lift1 hds0 (lift (S i) O
+t)) (H i t)))))))) hds).
+