---

Step * 2 1 of Lemma length-filter-lower-bound


1. A : Type
2. P : A ⟶ 𝔹
3. L : A List
4. T : Type
5. k : ℕ
6. f : {i:ℕ||L||| ¬↑P[L[i]]}  ⟶ T
7. Inj({i:ℕ||L||| ¬↑P[L[i]]} ;T;f)
8. T ~ ℕk
9. a : ℕ
10. a ≤ k
11. {i:ℕ||L||| ¬↑P[L[i]]}  ~ ℕa
12. {x:ℕ||L||| ¬¬↑P[L[x]]}  ~ ℕ||L|| - a
⊢ (||L|| - k) ≤ ||filter(P;L)||
BY
{ TACTIC:Assert ⌜{x:ℕ||L||| ¬¬↑P[L[x]]}  ~ ℕ||filter(P;L)||⌝⋅ }

1
.....assertion..... 
1. A : Type
2. P : A ⟶ 𝔹
3. L : A List
4. T : Type
5. k : ℕ
6. f : {i:ℕ||L||| ¬↑P[L[i]]}  ⟶ T
7. Inj({i:ℕ||L||| ¬↑P[L[i]]} ;T;f)
8. T ~ ℕk
9. a : ℕ
10. a ≤ k
11. {i:ℕ||L||| ¬↑P[L[i]]}  ~ ℕa
12. {x:ℕ||L||| ¬¬↑P[L[x]]}  ~ ℕ||L|| - a
⊢ {x:ℕ||L||| ¬¬↑P[L[x]]}  ~ ℕ||filter(P;L)||

2
1. A : Type
2. P : A ⟶ 𝔹
3. L : A List
4. T : Type
5. k : ℕ
6. f : {i:ℕ||L||| ¬↑P[L[i]]}  ⟶ T
7. Inj({i:ℕ||L||| ¬↑P[L[i]]} ;T;f)
8. T ~ ℕk
9. a : ℕ
10. a ≤ k
11. {i:ℕ||L||| ¬↑P[L[i]]}  ~ ℕa
12. {x:ℕ||L||| ¬¬↑P[L[x]]}  ~ ℕ||L|| - a
13. {x:ℕ||L||| ¬¬↑P[L[x]]}  ~ ℕ||filter(P;L)||
⊢ (||L|| - k) ≤ ||filter(P;L)||

---

Latex:

---

Latex:

1.  A  :  Type
2.  P  :  A  {}\mrightarrow{}  \mBbbB{}
3.  L  :  A  List
4.  T  :  Type
5.  k  :  \mBbbN{}
6.  f  :  \{i:\mBbbN{}||L|||  \mneg{}\muparrow{}P[L[i]]\}    {}\mrightarrow{}  T
7.  Inj(\{i:\mBbbN{}||L|||  \mneg{}\muparrow{}P[L[i]]\}  ;T;f)
8.  T  \msim{}  \mBbbN{}k
9.  a  :  \mBbbN{}
10.  a  \mleq{}  k
11.  \{i:\mBbbN{}||L|||  \mneg{}\muparrow{}P[L[i]]\}    \msim{}  \mBbbN{}a
12.  \{x:\mBbbN{}||L|||  \mneg{}\mneg{}\muparrow{}P[L[x]]\}    \msim{}  \mBbbN{}||L||  -  a
\mvdash{}  (||L||  -  k)  \mleq{}  ||filter(P;L)||


By

---

Latex:
TACTIC:Assert  \mkleeneopen{}\{x:\mBbbN{}||L|||  \mneg{}\mneg{}\muparrow{}P[L[x]]\}    \msim{}  \mBbbN{}||filter(P;L)||\mkleeneclose{}\mcdot{}

---

Home Index