Nuprl Lemma : filter-split-length

`∀[T:Type]. ∀[P:T ⟶ 𝔹]. ∀[L:T List].  ((||filter(λx.P[x];L)|| + ||filter(λx.(¬bP[x]);L)||) = ||L|| ∈ ℤ)`

Proof

Definitions occuring in Statement :  length: `||as||` filter: `filter(P;l)` list: `T List` bnot: `¬bb` bool: `𝔹` uall: `∀[x:A]. B[x]` so_apply: `x[s]` lambda: `λx.A[x]` function: `x:A ⟶ B[x]` add: `n + m` int: `ℤ` universe: `Type` equal: `s = t ∈ T`
Definitions unfolded in proof :  uall: `∀[x:A]. B[x]` member: `t ∈ T` so_lambda: `λ2x.t[x]` so_apply: `x[s]` prop: `ℙ` implies: `P `` Q` all: `∀x:A. B[x]` top: `Top` bool: `𝔹` unit: `Unit` it: `⋅` btrue: `tt` uiff: `uiff(P;Q)` and: `P ∧ Q` uimplies: `b supposing a` ifthenelse: `if b then t else f fi ` bnot: `¬bb` bfalse: `ff` decidable: `Dec(P)` or: `P ∨ Q` false: `False` satisfiable_int_formula: `satisfiable_int_formula(fmla)` exists: `∃x:A. B[x]` not: `¬A` sq_type: `SQType(T)` guard: `{T}` assert: `↑b`
Lemmas referenced :  list_induction equal_wf length_wf filter_wf5 l_member_wf bnot_wf list_wf filter_nil_lemma length_of_nil_lemma filter_cons_lemma length_of_cons_lemma bool_wf eqtt_to_assert decidable__equal_int add-is-int-iff satisfiable-full-omega-tt intformand_wf intformnot_wf intformeq_wf itermAdd_wf itermVar_wf itermConstant_wf int_formula_prop_and_lemma int_formula_prop_not_lemma int_formula_prop_eq_lemma int_term_value_add_lemma int_term_value_var_lemma int_term_value_constant_lemma int_formula_prop_wf false_wf eqff_to_assert bool_cases_sqequal subtype_base_sq bool_subtype_base assert-bnot
Rules used in proof :  sqequalSubstitution sqequalTransitivity computationStep sqequalReflexivity isect_memberFormation introduction cut thin extract_by_obid sqequalHypSubstitution isectElimination hypothesisEquality sqequalRule lambdaEquality intEquality addEquality cumulativity applyEquality functionExtensionality setElimination rename hypothesis setEquality because_Cache independent_functionElimination dependent_functionElimination isect_memberEquality voidElimination voidEquality natural_numberEquality lambdaFormation unionElimination equalityElimination productElimination independent_isectElimination equalityTransitivity equalitySymmetry pointwiseFunctionality promote_hyp baseApply closedConclusion baseClosed dependent_pairFormation int_eqEquality independent_pairFormation computeAll instantiate axiomEquality functionEquality universeEquality

Latex:
\mforall{}[T:Type].  \mforall{}[P:T  {}\mrightarrow{}  \mBbbB{}].  \mforall{}[L:T  List].    ((||filter(\mlambda{}x.P[x];L)||  +  ||filter(\mlambda{}x.(\mneg{}\msubb{}P[x]);L)||)  =  ||L||)

Date html generated: 2017_04_17-AM-07_33_33
Last ObjectModification: 2017_02_27-PM-04_10_43

Theory : list_1

Home Index