Step
*
of Lemma
length-filter-decreases
∀[T:Type]. ∀[P:T ⟶ 𝔹]. ∀[L:T List].  ((∃x∈L. ¬↑(P x)) 
⇒ ||filter(P;L)|| < ||L||)
BY
{ (InductionOnList THEN Reduce 0 THEN Try (AutoSplit) THEN Auto) }
1
1. T : Type
2. P : T ⟶ 𝔹
3. (∃x∈[]. ¬↑(P x))
⊢ 0 < 0
2
1. T : Type
2. P : T ⟶ 𝔹
3. u : T
4. v : T List
5. (∃x∈v. ¬↑(P x)) 
⇒ ||filter(P;v)|| < ||v||
6. ↑(P u)
7. (∃x∈[u / v]. ¬↑(P x))
⊢ ||filter(P;v)|| + 1 < ||v|| + 1
3
1. T : Type
2. P : T ⟶ 𝔹
3. u : T
4. ¬↑(P u)
5. v : T List
6. (∃x∈v. ¬↑(P x)) 
⇒ ||filter(P;v)|| < ||v||
7. (∃x∈[u / v]. ¬↑(P x))
⊢ ||filter(P;v)|| < ||v|| + 1
Latex:
Latex:
\mforall{}[T:Type].  \mforall{}[P:T  {}\mrightarrow{}  \mBbbB{}].  \mforall{}[L:T  List].    ((\mexists{}x\mmember{}L.  \mneg{}\muparrow{}(P  x))  {}\mRightarrow{}  ||filter(P;L)||  <  ||L||)
By
Latex:
(InductionOnList  THEN  Reduce  0  THEN  Try  (AutoSplit)  THEN  Auto)
Home
Index