---

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

.....assertion..... 
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);b) ∧ permutation({x:T| (x ∈ b)} ;comparison-sort(cmp;b1);b1)
BY
{ (D 0 THEN BLemma `comparison-sort-permutation` THEN Auto) }

---

Latex:

---

Latex:
.....assertion..... 
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
15.  \mforall{}[sa,sb:\{x:T|  (x  \mmember{}  b)\}    List].
            (sa  =  sb)  supposing 
                  (sorted-by(\mlambda{}a,b.  (0  \mleq{}  (cmp  a  b));sa)  and 
                  sorted-by(\mlambda{}a,b.  (0  \mleq{}  (cmp  a  b));sb)  and 
                  permutation(\{x:T|  (x  \mmember{}  b)\}  ;sa;sb))
\mvdash{}  permutation(\{x:T|  (x  \mmember{}  b)\}  ;comparison-sort(cmp;b);b)
\mwedge{}  permutation(\{x:T|  (x  \mmember{}  b)\}  ;comparison-sort(cmp;b1);b1)


By

---

Latex:
(D  0  THEN  BLemma  `comparison-sort-permutation`  THEN  Auto)

---

Home Index