+(**************************************************************************)
+(* ___ *)
+(* ||M|| *)
+(* ||A|| A project by Andrea Asperti *)
+(* ||T|| *)
+(* ||I|| Developers: *)
+(* ||T|| The HELM team. *)
+(* ||A|| http://helm.cs.unibo.it *)
+(* \ / *)
+(* \ / This file is distributed under the terms of the *)
+(* v GNU General Public License Version 2 *)
+(* *)
+(**************************************************************************)
+
+include "delayed_updating/syntax/path_structure.ma".
+include "delayed_updating/substitution/lift_eq.ma".
+
+(* LIFT FOR PATH ***********************************************************)
+
+(* Constructions with structure ********************************************)
+
+lemma lift_d_empty_dx (n) (p) (f):
+ (āp)āš±āØ(ā[pāš±āØnā©]f)@āØnā©ā© = ā[f](pāš±āØnā©).
+#n #p elim p -p
+[| * [ #m * [| #l ]] [|*: #p ] #IH ] #f
+[ //
+| <list_cons_shift <list_cons_comm <list_cons_comm //
+| <lift_d_lcons_sn <lift_d_lcons_sn //
+| <lift_L_sn <lift_L_sn <lift_lcons <IH //
+| <lift_A_sn <lift_A_sn <lift_lcons <IH //
+| <lift_S_sn <lift_S_sn <lift_lcons <IH //
+]
+qed.
+
+lemma lift_L_dx (p) (f):
+ (āp)āš = ā[f](pāš).
+#p elim p -p
+[| * [ #m * [| #l ]] [|*: #p ] #IH ] #f
+[ //
+| //
+| <lift_d_lcons_sn //
+| <lift_L_sn <lift_lcons //
+| <lift_A_sn <lift_lcons //
+| <lift_S_sn <lift_lcons //
+]
+qed.
+
+lemma lift_A_dx (p) (f):
+ (āp)āš = ā[f](pāš).
+#p elim p -p
+[| * [ #m * [| #l ]] [|*: #p ] #IH ] #f
+[ //
+| //
+| <lift_d_lcons_sn //
+| <lift_L_sn <lift_lcons //
+| <lift_A_sn <lift_lcons //
+| <lift_S_sn <lift_lcons //
+]
+qed.
+
+lemma lift_S_dx (p) (f):
+ (āp)āš¦ = ā[f](pāš¦).
+#p elim p -p
+[| * [ #m * [| #l ]] [|*: #p ] #IH ] #f
+[ //
+| //
+| <lift_d_lcons_sn //
+| <lift_L_sn <lift_lcons //
+| <lift_A_sn <lift_lcons //
+| <lift_S_sn <lift_lcons //
+]
+qed.
+
+lemma structure_lift (p) (f):
+ āp = āā[f]p.
+#p elim p -p
+[| * [ #m * [| #l ]] [|*: #p ] #IH ] #f
+[ //
+| //
+| //
+| <lift_L_sn <lift_lcons //
+| <lift_A_sn <lift_lcons //
+| <lift_S_sn <lift_lcons //
+]
+qed.
+
+lemma lift_structure (p) (f):
+ āp = ā[f]āp.
+#p elim p -p
+[| * [ #m * [| #l ]] [|*: #p ] #IH ] #f
+[ //
+| //
+| //
+| <structure_L_sn <lift_L_sn <lift_lcons //
+| <structure_A_sn <lift_A_sn <lift_lcons //
+| <structure_S_sn <lift_S_sn <lift_lcons //
+]
+qed.