---

Step * 1 1 1 1 of Lemma bag-member-decomp


1. T : Type
2. x : T
3. as : T List
4. v1 : T List
5. permutation(T;as;v1)
6. v : T List
7. bs : T List
8. permutation(T;v;bs)
9. L : (T × bag(T)) List
10. L
= map(λn.remove-nth(n;v);upto(||v||))
∈ pertype(λas,bs. ((as ∈ (T × bag(T)) List) ∧ (bs ∈ (T × bag(T)) List) ∧ permutation(T × bag(T);as;bs)))
11. L ∈ (T × bag(T)) List
12. map(λn.remove-nth(n;v);upto(||v||)) ∈ (T × bag(T)) List
13. permutation(T × bag(T);L;map(λn.remove-nth(n;v);upto(||v||)))
14. (<x, as> ∈ L)
15. ∀a:T × bag(T). ((a ∈ L) ⇐⇒ (a ∈ map(λn.remove-nth(n;v);upto(||v||))))
16. y : ℕ||v||
17. (y ∈ upto(||v||))
18. x = v[y] ∈ T
19. as = (firstn(y;v) @ nth_tl(y + 1;v)) ∈ pertype(λas,bs. ((as ∈ T List) ∧ (bs ∈ T List) ∧ permutation(T;as;bs)))
20. as ∈ T List
21. firstn(y;v) @ nth_tl(y + 1;v) ∈ T List
22. permutation(T;as;firstn(y;v) @ nth_tl(y + 1;v))
⊢ v = (firstn(y;v) @ [x / nth_tl(y + 1;v)]) ∈ (T List)
BY
{ (InstLemma `append_firstn_lastn_sq` [⌜v⌝;⌜y + 1⌝]⋅ THENA Auto) }

1
1. T : Type
2. x : T
3. as : T List
4. v1 : T List
5. permutation(T;as;v1)
6. v : T List
7. bs : T List
8. permutation(T;v;bs)
9. L : (T × bag(T)) List
10. L
= map(λn.remove-nth(n;v);upto(||v||))
∈ pertype(λas,bs. ((as ∈ (T × bag(T)) List) ∧ (bs ∈ (T × bag(T)) List) ∧ permutation(T × bag(T);as;bs)))
11. L ∈ (T × bag(T)) List
12. map(λn.remove-nth(n;v);upto(||v||)) ∈ (T × bag(T)) List
13. permutation(T × bag(T);L;map(λn.remove-nth(n;v);upto(||v||)))
14. (<x, as> ∈ L)
15. ∀a:T × bag(T). ((a ∈ L) ⇐⇒ (a ∈ map(λn.remove-nth(n;v);upto(||v||))))
16. y : ℕ||v||
17. (y ∈ upto(||v||))
18. x = v[y] ∈ T
19. as = (firstn(y;v) @ nth_tl(y + 1;v)) ∈ pertype(λas,bs. ((as ∈ T List) ∧ (bs ∈ T List) ∧ permutation(T;as;bs)))
20. as ∈ T List
21. firstn(y;v) @ nth_tl(y + 1;v) ∈ T List
22. permutation(T;as;firstn(y;v) @ nth_tl(y + 1;v))
23. v ~ firstn(y + 1;v) @ nth_tl(y + 1;v)
⊢ v = (firstn(y;v) @ [x / nth_tl(y + 1;v)]) ∈ (T List)

---

Latex:

---

Latex:

1.  T  :  Type
2.  x  :  T
3.  as  :  T  List
4.  v1  :  T  List
5.  permutation(T;as;v1)
6.  v  :  T  List
7.  bs  :  T  List
8.  permutation(T;v;bs)
9.  L  :  (T  \mtimes{}  bag(T))  List
10.  L  =  map(\mlambda{}n.remove-nth(n;v);upto(||v||))
11.  L  \mmember{}  (T  \mtimes{}  bag(T))  List
12.  map(\mlambda{}n.remove-nth(n;v);upto(||v||))  \mmember{}  (T  \mtimes{}  bag(T))  List
13.  permutation(T  \mtimes{}  bag(T);L;map(\mlambda{}n.remove-nth(n;v);upto(||v||)))
14.  (<x,  as>  \mmember{}  L)
15.  \mforall{}a:T  \mtimes{}  bag(T).  ((a  \mmember{}  L)  \mLeftarrow{}{}\mRightarrow{}  (a  \mmember{}  map(\mlambda{}n.remove-nth(n;v);upto(||v||))))
16.  y  :  \mBbbN{}||v||
17.  (y  \mmember{}  upto(||v||))
18.  x  =  v[y]
19.  as  =  (firstn(y;v)  @  nth\_tl(y  +  1;v))
20.  as  \mmember{}  T  List
21.  firstn(y;v)  @  nth\_tl(y  +  1;v)  \mmember{}  T  List
22.  permutation(T;as;firstn(y;v)  @  nth\_tl(y  +  1;v))
\mvdash{}  v  =  (firstn(y;v)  @  [x  /  nth\_tl(y  +  1;v)])


By

---

Latex:
(InstLemma  `append\_firstn\_lastn\_sq`  [\mkleeneopen{}v\mkleeneclose{};\mkleeneopen{}y  +  1\mkleeneclose{}]\mcdot{}  THENA  Auto)

---

Home Index