Structure pathTheory
signature pathTheory =
sig
type thm = Thm.thm
(* Definitions *)
val PL_def : thm
val SN_def : thm
val drop_def : thm
val el_def : thm
val every_def : thm
val exists_def : thm
val filter_def : thm
val finite_def : thm
val firstP_at_def : thm
val first_def : thm
val first_label_def : thm
val is_stopped_def : thm
val labels_def : thm
val last_thm : thm
val length_def : thm
val mem_def : thm
val nth_label_def : thm
val okpath_def : thm
val okpath_f_def : thm
val parallel_comp_def : thm
val path_TY_DEF : thm
val path_absrep_bijections : thm
val pconcat_def : thm
val pcons_def : thm
val pgenerate_def : thm
val plink_def : thm
val pmap_def : thm
val seg_def : thm
val stopped_at_def : thm
val tail_def : thm
val take_def : thm
val trace_machine_def : thm
val unfold_def : thm
(* Theorems *)
val EXISTS_path : thm
val FORALL_path : thm
val IN_PL_drop : thm
val LTAKE_labels : thm
val PL_0 : thm
val PL_downward_closed : thm
val PL_drop : thm
val PL_pcons : thm
val PL_pmap : thm
val PL_seg : thm
val PL_stopped_at : thm
val PL_take : thm
val PL_thm : thm
val SN_finite_paths : thm
val SN_finite_paths_EQ : thm
val alt_length_thm : thm
val build_pcomp_trace : thm
val drop_def_compute : thm
val drop_eq_pcons : thm
val el_def_compute : thm
val el_drop : thm
val el_pgenerate : thm
val el_pmap : thm
val every_coinduction : thm
val every_el : thm
val every_thm : thm
val exists_el : thm
val exists_induction : thm
val exists_thm : thm
val filter_every : thm
val finite_drop : thm
val finite_labels : thm
val finite_length : thm
val finite_okpath_ind : thm
val finite_path_end_cases : thm
val finite_path_ind : thm
val finite_paths_SN : thm
val finite_pconcat : thm
val finite_plink : thm
val finite_pmap : thm
val finite_seg : thm
val finite_take : thm
val finite_thm : thm
val firstP_at_thm : thm
val firstP_at_unique : thm
val firstP_at_zero : thm
val first_drop : thm
val first_label_drop : thm
val first_plink : thm
val first_pmap : thm
val first_seg : thm
val first_take : thm
val first_thm : thm
val fromPath_11 : thm
val fromPath_onto : thm
val infinite_PL : thm
val is_stopped_thm : thm
val labels_LMAP : thm
val labels_plink : thm
val labels_unfold : thm
val last_plink : thm
val last_pmap : thm
val last_seg : thm
val last_take : thm
val length_drop : thm
val length_never_zero : thm
val length_pmap : thm
val length_take : thm
val length_thm : thm
val mem_thm : thm
val not_every : thm
val not_exists : thm
val nth_label_LNTH : thm
val nth_label_LTAKE : thm
val nth_label_def_compute : thm
val nth_label_drop : thm
val nth_label_pgenerate : thm
val nth_label_pmap : thm
val nth_label_take : thm
val numeral_drop : thm
val okpath_cases : thm
val okpath_co_ind : thm
val okpath_drop : thm
val okpath_monotone : thm
val okpath_parallel_comp : thm
val okpath_plink : thm
val okpath_pmap : thm
val okpath_seg : thm
val okpath_take : thm
val okpath_thm : thm
val okpath_unfold : thm
val path_Axiom : thm
val path_bisimulation : thm
val path_cases : thm
val path_rep_bijections_thm : thm
val pconcat_eq_pcons : thm
val pconcat_eq_stopped : thm
val pconcat_thm : thm
val pcons_11 : thm
val pgenerate_11 : thm
val pgenerate_infinite : thm
val pgenerate_not_stopped : thm
val pgenerate_onto : thm
val pmap_thm : thm
val recursive_seg : thm
val simulation_trace_inclusion : thm
val singleton_seg : thm
val stopped_at_11 : thm
val stopped_at_not_pcons : thm
val tail_drop : thm
val take_def_compute : thm
val toPath_11 : thm
val toPath_onto : thm
val trace_machine_thm : thm
val trace_machine_thm2 : thm
val unfold_thm : thm
val unfold_thm2 : thm
val path_grammars : type_grammar.grammar * term_grammar.grammar
(*
[fixedPoint] Parent theory of "path"
[llist] Parent theory of "path"
[PL_def] Definition
|- ∀p. PL p = {i | finite p ⇒ i < THE (length p)}
[SN_def] Definition
|- ∀R. SN R ⇔ WF (λx y. ∃l. R y l x)
[drop_def] Definition
|- (∀p. drop 0 p = p) ∧ ∀n p. drop (SUC n) p = drop n (tail p)
[el_def] Definition
|- (∀p. el 0 p = first p) ∧ ∀n p. el (SUC n) p = el n (tail p)
[every_def] Definition
|- ∀P p. every P p ⇔ ¬exists ($~ o P) p
[exists_def] Definition
|- ∀P p. exists P p ⇔ ∃i. firstP_at P p i
[filter_def] Definition
|- ∀P.
(∀x. P x ⇒ (filter P (stopped_at x) = stopped_at x)) ∧
∀x r p.
filter P (pcons x r p) =
if P x then
if exists P p then pcons x r (filter P p) else stopped_at x
else filter P p
[finite_def] Definition
|- ∀sigma. finite sigma ⇔ LFINITE (SND (fromPath sigma))
[firstP_at_def] Definition
|- ∀P p i.
firstP_at P p i ⇔
i ∈ PL p ∧ P (el i p) ∧ ∀j. j < i ⇒ ¬P (el j p)
[first_def] Definition
|- ∀p. first p = FST (fromPath p)
[first_label_def] Definition
|- ∀x r p. first_label (pcons x r p) = r
[is_stopped_def] Definition
|- ∀p. is_stopped p ⇔ ∃x. p = stopped_at x
[labels_def] Definition
|- (∀x. labels (stopped_at x) = [||]) ∧
∀x r p. labels (pcons x r p) = r:::labels p
[last_thm] Definition
|- (∀x. last (stopped_at x) = x) ∧
∀x r p. last (pcons x r p) = last p
[length_def] Definition
|- ∀p.
length p =
if finite p then
SOME (LENGTH (THE (toList (SND (fromPath p)))) + 1)
else NONE
[mem_def] Definition
|- ∀s p. mem s p ⇔ ∃i. i ∈ PL p ∧ (s = el i p)
[nth_label_def] Definition
|- (∀p. nth_label 0 p = first_label p) ∧
∀n p. nth_label (SUC n) p = nth_label n (tail p)
[okpath_def] Definition
|- ∀R. okpath R = gfp (okpath_f R)
[okpath_f_def] Definition
|- ∀R X.
okpath_f R X =
{stopped_at x | x ∈ 𝕌(:α)} ∪
{pcons x r p | R x r (first p) ∧ p ∈ X}
[parallel_comp_def] Definition
|- ∀m1 m2 s1 s2 l s1' s2'.
parallel_comp m1 m2 (s1,s2) l (s1',s2') ⇔
m1 s1 l s1' ∧ m2 s2 l s2'
[path_TY_DEF] Definition
|- ∃rep. TYPE_DEFINITION (λx. T) rep
[path_absrep_bijections] Definition
|- (∀a. toPath (fromPath a) = a) ∧
∀r. (λx. T) r ⇔ (fromPath (toPath r) = r)
[pconcat_def] Definition
|- ∀p1 lab p2.
pconcat p1 lab p2 =
toPath
(first p1,
LAPPEND (SND (fromPath p1))
((lab,first p2):::SND (fromPath p2)))
[pcons_def] Definition
|- ∀x r p. pcons x r p = toPath (x,(r,first p):::SND (fromPath p))
[pgenerate_def] Definition
|- ∀f g.
pgenerate f g =
pcons (f 0) (g 0) (pgenerate (f o SUC) (g o SUC))
[plink_def] Definition
|- (∀x p. plink (stopped_at x) p = p) ∧
∀x r p1 p2. plink (pcons x r p1) p2 = pcons x r (plink p1 p2)
[pmap_def] Definition
|- ∀f g p. pmap f g p = toPath ((f ## LMAP (g ## f)) (fromPath p))
[seg_def] Definition
|- ∀i j p. seg i j p = take (j − i) (drop i p)
[stopped_at_def] Definition
|- ∀x. stopped_at x = toPath (x,[||])
[tail_def] Definition
|- ∀x r p. tail (pcons x r p) = p
[take_def] Definition
|- (∀p. take 0 p = stopped_at (first p)) ∧
∀n p.
take (SUC n) p =
pcons (first p) (first_label p) (take n (tail p))
[trace_machine_def] Definition
|- ∀P s l s'. trace_machine P s l s' ⇔ P (s ++ [l]) ∧ (s' = s ++ [l])
[unfold_def] Definition
|- ∀proj f s.
unfold proj f s =
toPath
(proj s,
LUNFOLD
(λs.
OPTION_MAP (λ(next_s,lbl). (next_s,lbl,proj next_s))
(f s)) s)
[EXISTS_path] Theorem
|- ∀P. (∃p. P p) ⇔ (∃x. P (stopped_at x)) ∨ ∃x r p. P (pcons x r p)
[FORALL_path] Theorem
|- ∀P. (∀p. P p) ⇔ (∀x. P (stopped_at x)) ∧ ∀x r p. P (pcons x r p)
[IN_PL_drop] Theorem
|- ∀i j p. i ∈ PL p ⇒ (j ∈ PL (drop i p) ⇔ i + j ∈ PL p)
[LTAKE_labels] Theorem
|- ∀n p l.
(LTAKE n (labels p) = SOME l) ⇔
n ∈ PL p ∧ (toList (labels (take n p)) = SOME l)
[PL_0] Theorem
|- ∀p. 0 ∈ PL p
[PL_downward_closed] Theorem
|- ∀i p. i ∈ PL p ⇒ ∀j. j < i ⇒ j ∈ PL p
[PL_drop] Theorem
|- ∀p i. i ∈ PL p ⇒ (PL (drop i p) = IMAGE (λn. n − i) (PL p))
[PL_pcons] Theorem
|- ∀x r q. PL (pcons x r q) = 0 INSERT IMAGE SUC (PL q)
[PL_pmap] Theorem
|- PL (pmap f g p) = PL p
[PL_seg] Theorem
|- ∀i j p. i ≤ j ∧ j ∈ PL p ⇒ (PL (seg i j p) = {n | n ≤ j − i})
[PL_stopped_at] Theorem
|- ∀x. PL (stopped_at x) = {0}
[PL_take] Theorem
|- ∀p i. i ∈ PL p ⇒ (PL (take i p) = {n | n ≤ i})
[PL_thm] Theorem
|- (∀x. PL (stopped_at x) = {0}) ∧
∀x r q. PL (pcons x r q) = 0 INSERT IMAGE SUC (PL q)
[SN_finite_paths] Theorem
|- ∀R p. SN R ∧ okpath R p ⇒ finite p
[SN_finite_paths_EQ] Theorem
|- ∀R. SN R ⇔ ∀p. okpath R p ⇒ finite p
[alt_length_thm] Theorem
|- (∀x. length (stopped_at x) = SOME 1) ∧
∀x r p. length (pcons x r p) = OPTION_MAP SUC (length p)
[build_pcomp_trace] Theorem
|- ∀m1 p1 m2 p2.
okpath m1 p1 ∧ okpath m2 p2 ∧ (labels p1 = labels p2) ⇒
∃p.
okpath (parallel_comp m1 m2) p ∧ (labels p = labels p1) ∧
(first p = (first p1,first p2))
[drop_def_compute] Theorem
|- (∀p. drop 0 p = p) ∧
(∀n p.
drop (NUMERAL (BIT1 n)) p =
drop (NUMERAL (BIT1 n) − 1) (tail p)) ∧
∀n p. drop (NUMERAL (BIT2 n)) p = drop (NUMERAL (BIT1 n)) (tail p)
[drop_eq_pcons] Theorem
|- ∀n p h l t. n ∈ PL p ∧ (drop n p = pcons h l t) ⇒ n + 1 ∈ PL p
[el_def_compute] Theorem
|- (∀p. el 0 p = first p) ∧
(∀n p.
el (NUMERAL (BIT1 n)) p = el (NUMERAL (BIT1 n) − 1) (tail p)) ∧
∀n p. el (NUMERAL (BIT2 n)) p = el (NUMERAL (BIT1 n)) (tail p)
[el_drop] Theorem
|- ∀i j p. i + j ∈ PL p ⇒ (el i (drop j p) = el (i + j) p)
[el_pgenerate] Theorem
|- ∀n f g. el n (pgenerate f g) = f n
[el_pmap] Theorem
|- ∀i p. i ∈ PL p ⇒ (el i (pmap f g p) = f (el i p))
[every_coinduction] Theorem
|- ∀P Q.
(∀x. P (stopped_at x) ⇒ Q x) ∧
(∀x r p. P (pcons x r p) ⇒ Q x ∧ P p) ⇒
∀p. P p ⇒ every Q p
[every_el] Theorem
|- ∀P p. every P p ⇔ ∀i. i ∈ PL p ⇒ P (el i p)
[every_thm] Theorem
|- ∀P.
(∀x. every P (stopped_at x) ⇔ P x) ∧
∀x r p. every P (pcons x r p) ⇔ P x ∧ every P p
[exists_el] Theorem
|- ∀P p. exists P p ⇔ ∃i. i ∈ PL p ∧ P (el i p)
[exists_induction] Theorem
|- (∀x. Q x ⇒ P (stopped_at x)) ∧ (∀x r p. Q x ⇒ P (pcons x r p)) ∧
(∀x r p. P p ⇒ P (pcons x r p)) ⇒
∀p. exists Q p ⇒ P p
[exists_thm] Theorem
|- ∀P.
(∀x. exists P (stopped_at x) ⇔ P x) ∧
∀x r p. exists P (pcons x r p) ⇔ P x ∨ exists P p
[filter_every] Theorem
|- ∀P p. exists P p ⇒ every P (filter P p)
[finite_drop] Theorem
|- ∀p n. n ∈ PL p ⇒ (finite (drop n p) ⇔ finite p)
[finite_labels] Theorem
|- ∀p. LFINITE (labels p) ⇔ finite p
[finite_length] Theorem
|- ∀p.
(finite p ⇔ ∃n. length p = SOME n) ∧
(¬finite p ⇔ (length p = NONE))
[finite_okpath_ind] Theorem
|- ∀R.
(∀x. P (stopped_at x)) ∧
(∀x r p.
okpath R p ∧ finite p ∧ R x r (first p) ∧ P p ⇒
P (pcons x r p)) ⇒
∀sigma. okpath R sigma ∧ finite sigma ⇒ P sigma
[finite_path_end_cases] Theorem
|- ∀p.
finite p ⇒
(∃x. p = stopped_at x) ∨
∃p' l s. p = plink p' (pcons (last p') l (stopped_at s))
[finite_path_ind] Theorem
|- ∀P.
(∀x. P (stopped_at x)) ∧
(∀x r p. finite p ∧ P p ⇒ P (pcons x r p)) ⇒
∀q. finite q ⇒ P q
[finite_paths_SN] Theorem
|- ∀R. (∀p. okpath R p ⇒ finite p) ⇒ SN R
[finite_pconcat] Theorem
|- ∀p1 lab p2. finite (pconcat p1 lab p2) ⇔ finite p1 ∧ finite p2
[finite_plink] Theorem
|- ∀p1 p2. finite (plink p1 p2) ⇔ finite p1 ∧ finite p2
[finite_pmap] Theorem
|- ∀f g p. finite (pmap f g p) ⇔ finite p
[finite_seg] Theorem
|- ∀p i j. i ≤ j ∧ j ∈ PL p ⇒ finite (seg i j p)
[finite_take] Theorem
|- ∀p i. i ∈ PL p ⇒ finite (take i p)
[finite_thm] Theorem
|- (∀x. finite (stopped_at x) ⇔ T) ∧
∀x r p. finite (pcons x r p) ⇔ finite p
[firstP_at_thm] Theorem
|- (∀P x n. firstP_at P (stopped_at x) n ⇔ (n = 0) ∧ P x) ∧
∀P n x r p.
firstP_at P (pcons x r p) n ⇔
(n = 0) ∧ P x ∨ 0 < n ∧ ¬P x ∧ firstP_at P p (n − 1)
[firstP_at_unique] Theorem
|- ∀P p n. firstP_at P p n ⇒ ∀m. firstP_at P p m ⇔ (m = n)
[firstP_at_zero] Theorem
|- ∀P p. firstP_at P p 0 ⇔ P (first p)
[first_drop] Theorem
|- ∀i p. i ∈ PL p ⇒ (first (drop i p) = el i p)
[first_label_drop] Theorem
|- ∀i p. i ∈ PL p ⇒ (first_label (drop i p) = nth_label i p)
[first_plink] Theorem
|- ∀p1 p2. (last p1 = first p2) ⇒ (first (plink p1 p2) = first p1)
[first_pmap] Theorem
|- ∀p. first (pmap f g p) = f (first p)
[first_seg] Theorem
|- ∀i j p. i ≤ j ∧ j ∈ PL p ⇒ (first (seg i j p) = el i p)
[first_take] Theorem
|- ∀p i. first (take i p) = first p
[first_thm] Theorem
|- (∀x. first (stopped_at x) = x) ∧ ∀x r p. first (pcons x r p) = x
[fromPath_11] Theorem
|- ∀a a'. (fromPath a = fromPath a') ⇔ (a = a')
[fromPath_onto] Theorem
|- ∀r. ∃a. r = fromPath a
[infinite_PL] Theorem
|- ∀p. ¬finite p ⇒ ∀i. i ∈ PL p
[is_stopped_thm] Theorem
|- (∀x. is_stopped (stopped_at x) ⇔ T) ∧
∀x r p. is_stopped (pcons x r p) ⇔ F
[labels_LMAP] Theorem
|- ∀p. labels p = LMAP FST (SND (fromPath p))
[labels_plink] Theorem
|- ∀p1 p2. labels (plink p1 p2) = LAPPEND (labels p1) (labels p2)
[labels_unfold] Theorem
|- ∀proj f s. labels (unfold proj f s) = LUNFOLD f s
[last_plink] Theorem
|- ∀p1 p2.
finite p1 ∧ finite p2 ∧ (last p1 = first p2) ⇒
(last (plink p1 p2) = last p2)
[last_pmap] Theorem
|- ∀p. finite p ⇒ (last (pmap f g p) = f (last p))
[last_seg] Theorem
|- ∀i j p. i ≤ j ∧ j ∈ PL p ⇒ (last (seg i j p) = el j p)
[last_take] Theorem
|- ∀i p. i ∈ PL p ⇒ (last (take i p) = el i p)
[length_drop] Theorem
|- ∀p n.
n ∈ PL p ⇒
(length (drop n p) =
case length p of NONE => NONE | SOME m => SOME (m − n))
[length_never_zero] Theorem
|- ∀p. length p ≠ SOME 0
[length_pmap] Theorem
|- ∀f g p. length (pmap f g p) = length p
[length_take] Theorem
|- ∀p i. i ∈ PL p ⇒ (length (take i p) = SOME (i + 1))
[length_thm] Theorem
|- (∀x. length (stopped_at x) = SOME 1) ∧
∀x r p.
length (pcons x r p) =
if finite p then SOME (THE (length p) + 1) else NONE
[mem_thm] Theorem
|- (∀x s. mem s (stopped_at x) ⇔ (s = x)) ∧
∀x r p s. mem s (pcons x r p) ⇔ (s = x) ∨ mem s p
[not_every] Theorem
|- ∀P p. ¬every P p ⇔ exists ($~ o P) p
[not_exists] Theorem
|- ∀P p. ¬exists P p ⇔ every ($~ o P) p
[nth_label_LNTH] Theorem
|- ∀n p x.
(LNTH n (labels p) = SOME x) ⇔
n + 1 ∈ PL p ∧ (nth_label n p = x)
[nth_label_LTAKE] Theorem
|- ∀n p l i v.
(LTAKE n (labels p) = SOME l) ∧ i < LENGTH l ⇒
(nth_label i p = EL i l)
[nth_label_def_compute] Theorem
|- (∀p. nth_label 0 p = first_label p) ∧
(∀n p.
nth_label (NUMERAL (BIT1 n)) p =
nth_label (NUMERAL (BIT1 n) − 1) (tail p)) ∧
∀n p.
nth_label (NUMERAL (BIT2 n)) p =
nth_label (NUMERAL (BIT1 n)) (tail p)
[nth_label_drop] Theorem
|- ∀i j p.
SUC (i + j) ∈ PL p ⇒
(nth_label i (drop j p) = nth_label (i + j) p)
[nth_label_pgenerate] Theorem
|- ∀n f g. nth_label n (pgenerate f g) = g n
[nth_label_pmap] Theorem
|- ∀i p.
SUC i ∈ PL p ⇒ (nth_label i (pmap f g p) = g (nth_label i p))
[nth_label_take] Theorem
|- ∀n p i.
i < n ∧ n ∈ PL p ⇒ (nth_label i (take n p) = nth_label i p)
[numeral_drop] Theorem
|- (∀n p.
drop (NUMERAL (BIT1 n)) p =
drop (NUMERAL (BIT1 n) − 1) (tail p)) ∧
∀n p. drop (NUMERAL (BIT2 n)) p = drop (NUMERAL (BIT1 n)) (tail p)
[okpath_cases] Theorem
|- ∀R x.
okpath R x ⇔
(∃x'. x = stopped_at x') ∨
∃x' r p. (x = pcons x' r p) ∧ R x' r (first p) ∧ okpath R p
[okpath_co_ind] Theorem
|- ∀P.
(∀x r p. P (pcons x r p) ⇒ R x r (first p) ∧ P p) ⇒
∀p. P p ⇒ okpath R p
[okpath_drop] Theorem
|- ∀R p i. i ∈ PL p ∧ okpath R p ⇒ okpath R (drop i p)
[okpath_monotone] Theorem
|- ∀R. monotone (okpath_f R)
[okpath_parallel_comp] Theorem
|- ∀p m1 m2.
okpath (parallel_comp m1 m2) p ⇔
okpath m1 (pmap FST (λx. x) p) ∧ okpath m2 (pmap SND (λx. x) p)
[okpath_plink] Theorem
|- ∀R p1 p2.
finite p1 ∧ (last p1 = first p2) ⇒
(okpath R (plink p1 p2) ⇔ okpath R p1 ∧ okpath R p2)
[okpath_pmap] Theorem
|- ∀R f g p.
okpath R p ∧ (∀x r y. R x r y ⇒ R (f x) (g r) (f y)) ⇒
okpath R (pmap f g p)
[okpath_seg] Theorem
|- ∀R p i j. i ≤ j ∧ j ∈ PL p ∧ okpath R p ⇒ okpath R (seg i j p)
[okpath_take] Theorem
|- ∀R p i. i ∈ PL p ∧ okpath R p ⇒ okpath R (take i p)
[okpath_thm] Theorem
|- ∀R.
(∀x. okpath R (stopped_at x)) ∧
∀x r p. okpath R (pcons x r p) ⇔ R x r (first p) ∧ okpath R p
[okpath_unfold] Theorem
|- ∀P m proj f s.
P s ∧ (∀s s' l. P s ∧ (f s = SOME (s',l)) ⇒ P s') ∧
(∀s s' l. P s ∧ (f s = SOME (s',l)) ⇒ m (proj s) l (proj s')) ⇒
okpath m (unfold proj f s)
[path_Axiom] Theorem
|- ∀f.
∃g.
∀x.
g x =
case f x of
(y,NONE) => stopped_at y
| (y,SOME (l,v)) => pcons y l (g v)
[path_bisimulation] Theorem
|- ∀p1 p2.
(p1 = p2) ⇔
∃R.
R p1 p2 ∧
∀q1 q2.
R q1 q2 ⇒
(∃x. (q1 = stopped_at x) ∧ (q2 = stopped_at x)) ∨
∃x r q1' q2'.
(q1 = pcons x r q1') ∧ (q2 = pcons x r q2') ∧ R q1' q2'
[path_cases] Theorem
|- ∀p. (∃x. p = stopped_at x) ∨ ∃x r q. p = pcons x r q
[path_rep_bijections_thm] Theorem
|- (∀a. toPath (fromPath a) = a) ∧ ∀r. fromPath (toPath r) = r
[pconcat_eq_pcons] Theorem
|- ∀x r p p1 lab p2.
((pconcat p1 lab p2 = pcons x r p) ⇔
(lab = r) ∧ (p1 = stopped_at x) ∧ (p = p2) ∨
∃p1'. (p1 = pcons x r p1') ∧ (p = pconcat p1' lab p2)) ∧
((pcons x r p = pconcat p1 lab p2) ⇔
(lab = r) ∧ (p1 = stopped_at x) ∧ (p = p2) ∨
∃p1'. (p1 = pcons x r p1') ∧ (p = pconcat p1' lab p2))
[pconcat_eq_stopped] Theorem
|- ∀p1 lab p2 x.
pconcat p1 lab p2 ≠ stopped_at x ∧
stopped_at x ≠ pconcat p1 lab p2
[pconcat_thm] Theorem
|- (∀x lab p2. pconcat (stopped_at x) lab p2 = pcons x lab p2) ∧
∀x r p lab p2.
pconcat (pcons x r p) lab p2 = pcons x r (pconcat p lab p2)
[pcons_11] Theorem
|- ∀x r p y s q.
(pcons x r p = pcons y s q) ⇔ (x = y) ∧ (r = s) ∧ (p = q)
[pgenerate_11] Theorem
|- ∀f1 g1 f2 g2.
(pgenerate f1 g1 = pgenerate f2 g2) ⇔ (f1 = f2) ∧ (g1 = g2)
[pgenerate_infinite] Theorem
|- ∀f g. ¬finite (pgenerate f g)
[pgenerate_not_stopped] Theorem
|- ∀f g x. stopped_at x ≠ pgenerate f g
[pgenerate_onto] Theorem
|- ∀p. ¬finite p ⇒ ∃f g. p = pgenerate f g
[pmap_thm] Theorem
|- (∀x. pmap f g (stopped_at x) = stopped_at (f x)) ∧
∀x r p. pmap f g (pcons x r p) = pcons (f x) (g r) (pmap f g p)
[recursive_seg] Theorem
|- ∀i j p.
i < j ∧ j ∈ PL p ⇒
(seg i j p = pcons (el i p) (nth_label i p) (seg (i + 1) j p))
[simulation_trace_inclusion] Theorem
|- ∀R M1 M2 p t_init.
(∀s1 l s2 t1.
R s1 t1 ∧ M1 s1 l s2 ⇒ ∃t2. R s2 t2 ∧ M2 t1 l t2) ∧
okpath M1 p ∧ R (first p) t_init ⇒
∃q. okpath M2 q ∧ (labels p = labels q) ∧ (first q = t_init)
[singleton_seg] Theorem
|- ∀i p. i ∈ PL p ⇒ (seg i i p = stopped_at (el i p))
[stopped_at_11] Theorem
|- ∀x y. (stopped_at x = stopped_at y) ⇔ (x = y)
[stopped_at_not_pcons] Theorem
|- ∀x y r p. stopped_at x ≠ pcons y r p ∧ pcons y r p ≠ stopped_at x
[tail_drop] Theorem
|- ∀i p. i + 1 ∈ PL p ⇒ (tail (drop i p) = drop (i + 1) p)
[take_def_compute] Theorem
|- (∀p. take 0 p = stopped_at (first p)) ∧
(∀n p.
take (NUMERAL (BIT1 n)) p =
pcons (first p) (first_label p)
(take (NUMERAL (BIT1 n) − 1) (tail p))) ∧
∀n p.
take (NUMERAL (BIT2 n)) p =
pcons (first p) (first_label p)
(take (NUMERAL (BIT1 n)) (tail p))
[toPath_11] Theorem
|- ∀r r'. (toPath r = toPath r') ⇔ (r = r')
[toPath_onto] Theorem
|- ∀a. ∃r. a = toPath r
[trace_machine_thm] Theorem
|- ∀P tr.
(∀n l. (LTAKE n tr = SOME l) ⇒ P l) ⇒
∃p.
(tr = labels p) ∧ okpath (trace_machine P) p ∧ (first p = [])
[trace_machine_thm2] Theorem
|- ∀n l P p init.
okpath (trace_machine P) p ∧ P (first p) ⇒
(LTAKE n (labels p) = SOME l) ⇒
P (first p ++ l)
[unfold_thm] Theorem
|- ∀proj f s.
unfold proj f s =
case f s of
NONE => stopped_at (proj s)
| SOME (s',l) => pcons (proj s) l (unfold proj f s')
[unfold_thm2] Theorem
|- ∀proj f x v1 v2.
((f x = NONE) ⇒ (unfold proj f x = stopped_at (proj x))) ∧
((f x = SOME (v1,v2)) ⇒
(unfold proj f x = pcons (proj x) v2 (unfold proj f v1)))
*)
end
HOL 4, Kananaskis-11