---

Step * 1 1 1 of Lemma bag-to-list_wf


1. T : Type
2. valueall-type(T)
3. b : Base
4. b1 : Base
5. b = b1 ∈ pertype(λas,bs. ((as ∈ T List) ∧ (bs ∈ T List) ∧ permutation(T;as;bs)))
6. b ∈ T List
7. b1 ∈ T List
8. permutation(T;b;b1)
9. cmp : comparison({x:T| x ↓∈ b} )
10. cmp ∈ comparison({x:T| (x ∈ b)} )
11. Linorder({x:T| (x ∈ b)} ;a,b.0 ≤ (cmp a b))
12. ∀a:T. ((a ∈ b) ⇐⇒ (a ∈ b1))
13. b ∈ {x:T| (x ∈ b)}  List
14. b1 ∈ {x:T| (x ∈ b)}  List
⊢ bag-to-list(cmp;b) = bag-to-list(cmp;b1) ∈ (T List)
BY
{ (Unfold `bag-to-list` 0
   THEN (InstLemma `permutation-sorted-by-unique` [⌜{x:T| (x ∈ b)} ⌝;⌜λa,b. (0 ≤ (cmp a b))⌝]⋅ THENM BHyp -1 )
   THEN Try (Complete (Auto))
   THEN Try ((GenConclAtAddr [2] THEN D -2 THEN Unhide THEN Auto THEN Unfold `sorted-by` 0 THEN Reduce 0 THEN Auto))) }

1
1. T : Type
2. valueall-type(T)
3. b : Base
4. b1 : Base
5. b = b1 ∈ pertype(λas,bs. ((as ∈ T List) ∧ (bs ∈ T List) ∧ permutation(T;as;bs)))
6. b ∈ T List
7. b1 ∈ T List
8. permutation(T;b;b1)
9. cmp : comparison({x:T| x ↓∈ b} )
10. cmp ∈ comparison({x:T| (x ∈ b)} )
11. Linorder({x:T| (x ∈ b)} ;a,b.0 ≤ (cmp a b))
12. ∀a:T. ((a ∈ b) ⇐⇒ (a ∈ b1))
13. b ∈ {x:T| (x ∈ b)}  List
14. b1 ∈ {x:T| (x ∈ b)}  List
15. ∀[sa,sb:{x:T| (x ∈ b)}  List].
      (sa = sb ∈ ({x:T| (x ∈ b)}  List)) supposing 
         (sorted-by(λa,b. (0 ≤ (cmp a b));sa) and 
         sorted-by(λa,b. (0 ≤ (cmp a b));sb) and 
         permutation({x:T| (x ∈ b)} ;sa;sb))
⊢ permutation({x:T| (x ∈ b)} ;comparison-sort(cmp;b);comparison-sort(cmp;b1))

---

Latex:

---

Latex:

1.  T  :  Type
2.  valueall-type(T)
3.  b  :  Base
4.  b1  :  Base
5.  b  =  b1
6.  b  \mmember{}  T  List
7.  b1  \mmember{}  T  List
8.  permutation(T;b;b1)
9.  cmp  :  comparison(\{x:T|  x  \mdownarrow{}\mmember{}  b\}  )
10.  cmp  \mmember{}  comparison(\{x:T|  (x  \mmember{}  b)\}  )
11.  Linorder(\{x:T|  (x  \mmember{}  b)\}  ;a,b.0  \mleq{}  (cmp  a  b))
12.  \mforall{}a:T.  ((a  \mmember{}  b)  \mLeftarrow{}{}\mRightarrow{}  (a  \mmember{}  b1))
13.  b  \mmember{}  \{x:T|  (x  \mmember{}  b)\}    List
14.  b1  \mmember{}  \{x:T|  (x  \mmember{}  b)\}    List
\mvdash{}  bag-to-list(cmp;b)  =  bag-to-list(cmp;b1)


By

---

Latex:
(Unfold  `bag-to-list`  0
  THEN  (InstLemma  `permutation-sorted-by-unique`  [\mkleeneopen{}\{x:T|  (x  \mmember{}  b)\}  \mkleeneclose{};\mkleeneopen{}\mlambda{}a,b.  (0  \mleq{}  (cmp  a  b))\mkleeneclose{}]\mcdot{}
  THENM  BHyp  -1 
  )
  THEN  Try  (Complete  (Auto))
  THEN  Try  ((GenConclAtAddr  [2]
                        THEN  D  -2
                        THEN  Unhide
                        THEN  Auto
                        THEN  Unfold  `sorted-by`  0
                        THEN  Reduce  0
                        THEN  Auto)))

---

Home Index