Step
*
of Lemma
sublist_filter
∀[T:Type]. ∀L1,L2:T List. ∀P:T ⟶ 𝔹.  (L2 ⊆ filter(P;L1) 
⇐⇒ L2 ⊆ L1 ∧ (∀x∈L2.↑(P x)))
BY
{ ((InductionOnList THEN InductionOnList) THEN Reduce 0) }
1
1. [T] : Type
⊢ ∀P:T ⟶ 𝔹. ([] ⊆ [] 
⇐⇒ [] ⊆ [] ∧ (∀x∈[].↑(P x)))
2
1. [T] : Type
2. u : T
3. v : T List
4. ∀P:T ⟶ 𝔹. (v ⊆ filter(P;[]) 
⇐⇒ v ⊆ [] ∧ (∀x∈v.↑(P x)))
⊢ ∀P:T ⟶ 𝔹. ([u / v] ⊆ [] 
⇐⇒ [u / v] ⊆ [] ∧ (∀x∈[u / v].↑(P x)))
3
1. [T] : Type
2. u : T
3. v : T List
4. ∀L2:T List. ∀P:T ⟶ 𝔹.  (L2 ⊆ filter(P;v) 
⇐⇒ L2 ⊆ v ∧ (∀x∈L2.↑(P x)))
⊢ ∀P:T ⟶ 𝔹. ([] ⊆ if P u then [u / filter(P;v)] else filter(P;v) fi  
⇐⇒ [] ⊆ [u / v] ∧ (∀x∈[].↑(P x)))
4
1. [T] : Type
2. u : T
3. v : T List
4. ∀L2:T List. ∀P:T ⟶ 𝔹.  (L2 ⊆ filter(P;v) 
⇐⇒ L2 ⊆ v ∧ (∀x∈L2.↑(P x)))
5. u1 : T
6. v1 : T List
7. ∀P:T ⟶ 𝔹. (v1 ⊆ filter(P;[u / v]) 
⇐⇒ v1 ⊆ [u / v] ∧ (∀x∈v1.↑(P x)))
⊢ ∀P:T ⟶ 𝔹
    ([u1 / v1] ⊆ if P u then [u / filter(P;v)] else filter(P;v) fi  
⇐⇒ [u1 / v1] ⊆ [u / v] ∧ (∀x∈[u1 / v1].↑(P x)))
Latex:
Latex:
\mforall{}[T:Type].  \mforall{}L1,L2:T  List.  \mforall{}P:T  {}\mrightarrow{}  \mBbbB{}.    (L2  \msubseteq{}  filter(P;L1)  \mLeftarrow{}{}\mRightarrow{}  L2  \msubseteq{}  L1  \mwedge{}  (\mforall{}x\mmember{}L2.\muparrow{}(P  x)))
By
Latex:
((InductionOnList  THEN  InductionOnList)  THEN  Reduce  0)
Home
Index