---

Step * of Lemma interleaved_split

∀[T:Type]
  ∀L:T List
    ∀[P:T ⟶ ℙ]
      ((∀x:T. Dec(P[x]))
      ⇒ (∃L1,L2:T List
           (interleaving(T;L1;L2;L)
           ∧ (∀x:T. ((x ∈ L1) ⇐⇒ (x ∈ L) ∧ P[x]))
           ∧ (∀x:T. ((x ∈ L2) ⇐⇒ (x ∈ L) ∧ (¬P[x]))))))
BY
{ InductionOnList }

1
1. [T] : Type
⊢ ∀[P:T ⟶ ℙ]
    ((∀x:T. Dec(P[x]))
    ⇒ (∃L1,L2:T List
         (interleaving(T;L1;L2;[])
         ∧ (∀x:T. ((x ∈ L1) ⇐⇒ (x ∈ []) ∧ P[x]))
         ∧ (∀x:T. ((x ∈ L2) ⇐⇒ (x ∈ []) ∧ (¬P[x]))))))

2
1. [T] : Type
2. u : T
3. v : T List
4. ∀[P:T ⟶ ℙ]
     ((∀x:T. Dec(P[x]))
     ⇒ (∃L1,L2:T List
          (interleaving(T;L1;L2;v) ∧ (∀x:T. ((x ∈ L1) ⇐⇒ (x ∈ v) ∧ P[x])) ∧ (∀x:T. ((x ∈ L2) ⇐⇒ (x ∈ v) ∧ (¬P[x]))))))
⊢ ∀[P:T ⟶ ℙ]
    ((∀x:T. Dec(P[x]))
    ⇒ (∃L1,L2:T List
         (interleaving(T;L1;L2;[u / v])
         ∧ (∀x:T. ((x ∈ L1) ⇐⇒ (x ∈ [u / v]) ∧ P[x]))
         ∧ (∀x:T. ((x ∈ L2) ⇐⇒ (x ∈ [u / v]) ∧ (¬P[x]))))))

---

Latex:

---

Latex:
\mforall{}[T:Type]
    \mforall{}L:T  List
        \mforall{}[P:T  {}\mrightarrow{}  \mBbbP{}]
            ((\mforall{}x:T.  Dec(P[x]))
            {}\mRightarrow{}  (\mexists{}L1,L2:T  List
                      (interleaving(T;L1;L2;L)
                      \mwedge{}  (\mforall{}x:T.  ((x  \mmember{}  L1)  \mLeftarrow{}{}\mRightarrow{}  (x  \mmember{}  L)  \mwedge{}  P[x]))
                      \mwedge{}  (\mforall{}x:T.  ((x  \mmember{}  L2)  \mLeftarrow{}{}\mRightarrow{}  (x  \mmember{}  L)  \mwedge{}  (\mneg{}P[x]))))))


By

---

Latex:
InductionOnList

---

Home Index