---

Step * 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)) ∈ bag(T)
⊢ ({x} + as) = v ∈ bag(T)
BY
{ ((EqTypeHD (-1) THENA Auto)
   THEN RepUR ``bag-append single-bag`` 0
   THEN EqTypeCD
   THEN Auto
   THEN BLemma `permutation-cons`
   THEN Auto
   THEN InstConcl [⌜firstn(y;v)⌝;⌜nth_tl(y + 1;v)⌝]⋅
   THEN 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))
⊢ 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))
\mvdash{}  (\{x\}  +  as)  =  v


By

---

Latex:
((EqTypeHD  (-1)  THENA  Auto)
  THEN  RepUR  ``bag-append  single-bag``  0
  THEN  EqTypeCD
  THEN  Auto
  THEN  BLemma  `permutation-cons`
  THEN  Auto
  THEN  InstConcl  [\mkleeneopen{}firstn(y;v)\mkleeneclose{};\mkleeneopen{}nth\_tl(y  +  1;v)\mkleeneclose{}]\mcdot{}
  THEN  Auto)

---

Home Index