---

Step * 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. <x, as> ↓∈ bag-decomp(v)
⊢ ({x} + as) = v ∈ bag(T)
BY
{ (RepeatFor 3 (D (-1))
   THEN RepUR ``bag-decomp`` -2
   THEN MemTypeHD (-2)
   THEN Auto
   THEN (FLemma `member-permutation` [-2] THENA Auto)
   THEN FHyp (-1) [-2]
   THEN Auto
   THEN (InstLemma `member_map` [⌜ℕ||v||⌝;⌜T × bag(T)⌝]⋅ THENA Auto)
   THEN ((RWO "-1" (-2) THENM Thin (-1)) THENA Auto)
   THEN ExRepD
   THEN Reduce (-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, as> = remove-nth(y;v) ∈ (T × 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.  <x,  as>  \mdownarrow{}\mmember{}  bag-decomp(v)
\mvdash{}  (\{x\}  +  as)  =  v


By

---

Latex:
(RepeatFor  3  (D  (-1))
  THEN  RepUR  ``bag-decomp``  -2
  THEN  MemTypeHD  (-2)
  THEN  Auto
  THEN  (FLemma  `member-permutation`  [-2]  THENA  Auto)
  THEN  FHyp  (-1)  [-2]
  THEN  Auto
  THEN  (InstLemma  `member\_map`  [\mkleeneopen{}\mBbbN{}||v||\mkleeneclose{};\mkleeneopen{}T  \mtimes{}  bag(T)\mkleeneclose{}]\mcdot{}  THENA  Auto)
  THEN  ((RWO  "-1"  (-2)  THENM  Thin  (-1))  THENA  Auto)
  THEN  ExRepD
  THEN  Reduce  (-1))

---

Home Index