1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "delayed_updating/syntax/path_labels.ma".
16 include "delayed_updating/notation/functions/downarrowright_2.ma".
17 include "ground/arith/nat_plus.ma".
18 include "ground/arith/nat_pred_succ.ma".
20 (* HEAD FOR PATH ************************************************************)
22 rec definition path_head (m) (p) on p: path ≝
30 [ label_d n ⇒ l◗(path_head (m+n) q)
31 | label_m ⇒ l◗(path_head m q)
32 | label_L ⇒ l◗(path_head (↓o) q)
33 | label_A ⇒ l◗(path_head m q)
34 | label_S ⇒ l◗(path_head m q)
40 "head (reversed path)"
41 'DownArrowRight n p = (path_head n p).
43 (* basic constructions ****************************************************)
45 lemma path_head_zero (p):
49 lemma path_head_empty (n):
53 lemma path_head_d_sn (p) (n) (m:pnat):
54 (𝗱m◗↳[↑n+m]p) = ↳[↑n](𝗱m◗p).
57 lemma path_head_m_sn (p) (n):
58 (𝗺◗↳[↑n]p) = ↳[↑n](𝗺◗p).
61 lemma path_head_L_sn (p) (n):
62 (𝗟◗↳[n]p) = ↳[↑n](𝗟◗p).
67 lemma path_head_A_sn (p) (n):
68 (𝗔◗↳[↑n]p) = ↳[↑n](𝗔◗p).
71 lemma path_head_S_sn (p) (n):
72 (𝗦◗↳[↑n]p) = ↳[↑n](𝗦◗p).
75 (* Basic inversions *********************************************************)
77 lemma eq_inv_path_head_zero_dx (q) (p):
82 lemma eq_inv_path_empty_head (p) (n):
85 [ #m <path_head_empty #H0
86 <(eq_inv_empty_labels … H0) -m //
87 | * [ #n ] #p #n @(nat_ind_succ … n) -n // #m #_
97 (* Constructions with list_append *******************************************)
99 lemma path_head_refl_append (p) (q) (n):
100 q = ↳[n]q → q = ↳[n](q●p).
102 [ #n #Hn <(eq_inv_path_empty_head … Hn) -Hn //
103 | #l #q #IH #n @(nat_ind_succ … n) -n
104 [ #Hq | #n #_ cases l [ #m ] ]
105 [ lapply (eq_inv_path_head_zero_dx … Hq) -Hq #Hq destruct
106 | <path_head_d_sn <path_head_d_sn
107 | <path_head_m_sn <path_head_m_sn
108 | <path_head_L_sn <path_head_L_sn
109 | <path_head_A_sn <path_head_A_sn
110 | <path_head_S_sn <path_head_S_sn
112 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
117 (* Inversions with list_append **********************************************)
119 lemma eq_inv_path_head_refl_append (p) (q) (n):
120 q = ↳[n](q●p) → q = ↳[n]q.
122 [ #n #Hn <(eq_inv_path_empty_head … Hn) -p //
123 | #l #q #IH #n @(nat_ind_succ … n) -n //
125 [ <path_head_d_sn <path_head_d_sn
126 | <path_head_m_sn <path_head_m_sn
127 | <path_head_L_sn <path_head_L_sn
128 | <path_head_A_sn <path_head_A_sn
129 | <path_head_S_sn <path_head_S_sn
131 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq