-(**************************************************************************)
-(* ___ *)
-(* ||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_labels.ma".
-include "delayed_updating/notation/functions/downarrowright_2.ma".
-include "ground/arith/nat_plus.ma".
-include "ground/arith/nat_pred_succ.ma".
-
-(* HEAD FOR PATH ************************************************************)
-
-rec definition path_head (n) (p) on p: path ā
-match n with
-[ nzero ā š
-| ninj m ā
- match p with
- [ list_empty ā šāān
- | list_lcons l q ā
- match l with
- [ label_d k ā (path_head (n+k) q)āl
- | label_m ā (path_head n q)āl
- | label_L ā (path_head (ām) q)āl
- | label_A ā (path_head n q)āl
- | label_S ā (path_head n q)āl
- ]
- ]
-].
-
-interpretation
- "head (path)"
- 'DownArrowRight n p = (path_head n p).
-
-(* basic constructions ****************************************************)
-
-lemma path_head_zero (p):
- (š) = ā³[š]p.
-* // qed.
-
-lemma path_head_empty (n):
- (šāān) = ā³[n]š.
-* // qed.
-
-lemma path_head_d_dx (p) (n) (k:pnat):
- (ā³[ān+k]p)āš±k = ā³[ān](pāš±k).
-// qed.
-
-lemma path_head_m_dx (p) (n):
- (ā³[ān]p)āšŗ = ā³[ān](pāšŗ).
-// qed.
-
-lemma path_head_L_dx (p) (n):
- (ā³[n]p)āš = ā³[ān](pāš).
-#p #n
-whd in ā¢ (???%); //
-qed.
-
-lemma path_head_A_dx (p) (n):
- (ā³[ān]p)āš = ā³[ān](pāš).
-// qed.
-
-lemma path_head_S_dx (p) (n):
- (ā³[ān]p)āš¦ = ā³[ān](pāš¦).
-// qed.
-
-(* Basic inversions *********************************************************)
-
-lemma eq_inv_path_head_zero_dx (q) (p):
- q = ā³[š]p ā š = q.
-#q * //
-qed-.
-
-lemma eq_inv_path_empty_head (p) (n):
- (š) = ā³[n]p ā š = n.
-*
-[ #n <path_head_empty #H0
- <(eq_inv_empty_labels ā¦ H0) -n //
-| * [ #k ] #p #n @(nat_ind_succ ā¦ n) -n // #n #_
- [ <path_head_d_dx
- | <path_head_m_dx
- | <path_head_L_dx
- | <path_head_A_dx
- | <path_head_S_dx
- ] #H0 destruct
-]
-qed-.
-
-(* Constructions with path_append *******************************************)
-
-lemma path_head_refl_append (p) (q) (n):
- q = ā³[n]q ā q = ā³[n](pāq).
-#p #q elim q -q
-[ #n #Hn <(eq_inv_path_empty_head ā¦ Hn) -Hn //
-| #l #q #IH #n @(nat_ind_succ ā¦ n) -n
- [ #Hq | #n #_ cases l [ #k ] ]
- [ lapply (eq_inv_path_head_zero_dx ā¦ Hq) -Hq #Hq destruct
- | <path_head_d_dx <path_head_d_dx
- | <path_head_m_dx <path_head_m_dx
- | <path_head_L_dx <path_head_L_dx
- | <path_head_A_dx <path_head_A_dx
- | <path_head_S_dx <path_head_S_dx
- ] #Hq
- elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
- /3 width=1 by eq_f/
-]
-qed-.
-
-(* Inversions with path_append **********************************************)
-
-lemma eq_inv_path_head_refl_append (p) (q) (n):
- q = ā³[n](pāq) ā q = ā³[n]q.
-#p #q elim q -q
-[ #n #Hn <(eq_inv_path_empty_head ā¦ Hn) -p //
-| #l #q #IH #n @(nat_ind_succ ā¦ n) -n //
- #n #_ cases l [ #k ]
- [ <path_head_d_dx <path_head_d_dx
- | <path_head_m_dx <path_head_m_dx
- | <path_head_L_dx <path_head_L_dx
- | <path_head_A_dx <path_head_A_dx
- | <path_head_S_dx <path_head_S_dx
- ] #Hq
- elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
- /3 width=1 by eq_f/
-]
-qed-.