---

Step * of Lemma bag-filter-as-accum

∀[A:Type]. ∀[p:A ⟶ 𝔹]. ∀[bs:bag(A)].
  ([x∈bs|p[x]] = bag-accum(b,x.if p[x] then x.b else b fi ;{};bs) ∈ bag({x:A| ↑p[x]} ))
BY
{ (Auto THEN BagInd (-1) THEN Auto) }

1
1. A : Type
2. p : A ⟶ 𝔹
3. u : A
4. v : A List
5. [x∈v|p[x]] = bag-accum(b,x.if p[x] then x.b else b fi ;{};v) ∈ bag({x:A| ↑p[x]} )
⊢ [x∈[u / v]|p[x]] = bag-accum(b,x.if p[x] then x.b else b fi ;{};[u / v]) ∈ bag({x:A| ↑p[x]} )

2
1. A : Type
2. p : A ⟶ 𝔹
3. L : A List
4. bs : bag(A)
5. bs = L ∈ bag(A)
6. z : bag(A)
7. b : bag({x:A| ↑p[x]} )
8. x : A
9. y : A
⊢ if p[x] then x.if p[y] then y.b else b fi 
if p[y] then y.b
else b
fi 
= if p[y] then y.if p[x] then x.b else b fi 
  if p[x] then x.b
  else b
  fi 
∈ bag({x:A| ↑p[x]} )

---

Latex:

---

Latex:
\mforall{}[A:Type].  \mforall{}[p:A  {}\mrightarrow{}  \mBbbB{}].  \mforall{}[bs:bag(A)].
    ([x\mmember{}bs|p[x]]  =  bag-accum(b,x.if  p[x]  then  x.b  else  b  fi  ;\{\};bs))


By

---

Latex:
(Auto  THEN  BagInd  (-1)  THEN  Auto)

---

Home Index