---

Step * 1 1 3 1 of Lemma bag-member-parts


1. T : Type
2. valueall-type(T)
3. eq : EqDecider(T)
4. n : ℕ
5. ∀n:ℕn. ∀bs:bag(T).
     ((#(bs) ≤ n)
     ⇒ (∀L:bag(T) List+. uiff(L ↓∈ bag-parts(eq;bs);(bag-union(L) = bs ∈ bag(T)) ∧ (∀x∈L.¬(x = {} ∈ bag(T))))))
6. bs : bag(T)
7. #(bs) ≤ n
8. u : bag(T)
9. v : bag(T) List
10. bag-union([u / v]) = bs ∈ bag(T)
11. (∀x∈[u / v].¬(x = {} ∈ bag(T)))
⊢ ↓∃a,b:bag(T)
    (<a, b> ↓∈ bag-partitions(eq;bs)
    ∧ [u / v] ↓∈ if bag-null(a) then {}
      if bag-null(b) then {[a]}
      else let parts ⟵ bag-parts(eq;b)
           in bag-map(λL.[a / L];parts)
      fi )
BY
{ (RepUR ``bag-union concat`` (-2)
   THEN Fold `concat` (-2)
   THEN Folds ``bag-union bag-append`` (-2)
   THEN (RWO "l_all_cons" (-1) THENA Auto)
   THEN (Assert #(u + bag-union(v)) = #(bs) ∈ ℤ BY
               Auto)
   THEN (RWO "bag-size-append" (-1) THENA Auto)
   THEN (Decide ⌜#(u) ≤ 0⌝⋅ THENA Auto))⋅ }

1
1. T : Type
2. valueall-type(T)
3. eq : EqDecider(T)
4. n : ℕ
5. ∀n:ℕn. ∀bs:bag(T).
     ((#(bs) ≤ n)
     ⇒ (∀L:bag(T) List+. uiff(L ↓∈ bag-parts(eq;bs);(bag-union(L) = bs ∈ bag(T)) ∧ (∀x∈L.¬(x = {} ∈ bag(T))))))
6. bs : bag(T)
7. #(bs) ≤ n
8. u : bag(T)
9. v : bag(T) List
10. (u + bag-union(v)) = bs ∈ bag(T)
11. (¬(u = {} ∈ bag(T))) ∧ (∀x∈v.¬(x = {} ∈ bag(T)))
12. (#(u) + #(bag-union(v))) = #(bs) ∈ ℤ
13. #(u) ≤ 0
⊢ ↓∃a,b:bag(T)
    (<a, b> ↓∈ bag-partitions(eq;bs)
    ∧ [u / v] ↓∈ if bag-null(a) then {}
      if bag-null(b) then {[a]}
      else let parts ⟵ bag-parts(eq;b)
           in bag-map(λL.[a / L];parts)
      fi )

2
1. T : Type
2. valueall-type(T)
3. eq : EqDecider(T)
4. n : ℕ
5. ∀n:ℕn. ∀bs:bag(T).
     ((#(bs) ≤ n)
     ⇒ (∀L:bag(T) List+. uiff(L ↓∈ bag-parts(eq;bs);(bag-union(L) = bs ∈ bag(T)) ∧ (∀x∈L.¬(x = {} ∈ bag(T))))))
6. bs : bag(T)
7. #(bs) ≤ n
8. u : bag(T)
9. v : bag(T) List
10. (u + bag-union(v)) = bs ∈ bag(T)
11. (¬(u = {} ∈ bag(T))) ∧ (∀x∈v.¬(x = {} ∈ bag(T)))
12. (#(u) + #(bag-union(v))) = #(bs) ∈ ℤ
13. ¬(#(u) ≤ 0)
⊢ ↓∃a,b:bag(T)
    (<a, b> ↓∈ bag-partitions(eq;bs)
    ∧ [u / v] ↓∈ if bag-null(a) then {}
      if bag-null(b) then {[a]}
      else let parts ⟵ bag-parts(eq;b)
           in bag-map(λL.[a / L];parts)
      fi )

---

Latex:

---

Latex:

1.  T  :  Type
2.  valueall-type(T)
3.  eq  :  EqDecider(T)
4.  n  :  \mBbbN{}
5.  \mforall{}n:\mBbbN{}n.  \mforall{}bs:bag(T).
          ((\#(bs)  \mleq{}  n)
          {}\mRightarrow{}  (\mforall{}L:bag(T)  List\msupplus{}.  uiff(L  \mdownarrow{}\mmember{}  bag-parts(eq;bs);(bag-union(L)  =  bs)  \mwedge{}  (\mforall{}x\mmember{}L.\mneg{}(x  =  \{\})))))
6.  bs  :  bag(T)
7.  \#(bs)  \mleq{}  n
8.  u  :  bag(T)
9.  v  :  bag(T)  List
10.  bag-union([u  /  v])  =  bs
11.  (\mforall{}x\mmember{}[u  /  v].\mneg{}(x  =  \{\}))
\mvdash{}  \mdownarrow{}\mexists{}a,b:bag(T)
        (<a,  b>  \mdownarrow{}\mmember{}  bag-partitions(eq;bs)
        \mwedge{}  [u  /  v]  \mdownarrow{}\mmember{}  if  bag-null(a)  then  \{\}
            if  bag-null(b)  then  \{[a]\}
            else  let  parts  \mleftarrow{}{}  bag-parts(eq;b)
                      in  bag-map(\mlambda{}L.[a  /  L];parts)
            fi  )


By

---

Latex:
(RepUR  ``bag-union  concat``  (-2)
  THEN  Fold  `concat`  (-2)
  THEN  Folds  ``bag-union  bag-append``  (-2)
  THEN  (RWO  "l\_all\_cons"  (-1)  THENA  Auto)
  THEN  (Assert  \#(u  +  bag-union(v))  =  \#(bs)  BY
                          Auto)
  THEN  (RWO  "bag-size-append"  (-1)  THENA  Auto)
  THEN  (Decide  \mkleeneopen{}\#(u)  \mleq{}  0\mkleeneclose{}\mcdot{}  THENA  Auto))\mcdot{}

---

Home Index