---

Step * 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, as> = remove-nth(y;v) ∈ (T × bag(T))
⊢ ({x} + as) = v ∈ bag(T)
BY
{ (RepUR ``remove-nth`` (-1)⋅ THEN SplitPair (-1)) }

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)) ∈ bag(T)
⊢ ({x} + as) = v ∈ bag(T)

---

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,  as>  =  remove-nth(y;v)
\mvdash{}  (\{x\}  +  as)  =  v


By

---

Latex:
(RepUR  ``remove-nth``  (-1)\mcdot{}  THEN  SplitPair  (-1))

---

Home Index