### Nuprl Lemma : lifting-member

`∀[B:Type]. ∀[n:ℕ]. ∀[m:ℕn + 1]. ∀[A:ℕn ⟶ Type]. ∀[bags:k:ℕn ⟶ bag(A k)]. ∀[f:funtype(n - m;λx.(A (x + m));B)]. ∀[b:B].`
`  (b ↓∈ lifting-gen-list-rev(n;bags) m f`
`  `⇐⇒` ↓∃lst:k:{m..n-} ⟶ (A k). ((∀[k:{m..n-}]. lst k ↓∈ bags k) ∧ ((uncurry-gen(n) m (λx.f) lst) = b ∈ B)))`

Proof

Definitions occuring in Statement :  uncurry-gen: `uncurry-gen(n)` lifting-gen-list-rev: `lifting-gen-list-rev(n;bags)` bag-member: `x ↓∈ bs` bag: `bag(T)` funtype: `funtype(n;A;T)` int_seg: `{i..j-}` nat: `ℕ` uall: `∀[x:A]. B[x]` exists: `∃x:A. B[x]` iff: `P `⇐⇒` Q` squash: `↓T` and: `P ∧ Q` apply: `f a` lambda: `λx.A[x]` function: `x:A ⟶ B[x]` subtract: `n - m` add: `n + m` natural_number: `\$n` universe: `Type` equal: `s = t ∈ T`
Definitions unfolded in proof :  uall: `∀[x:A]. B[x]` member: `t ∈ T` int_seg: `{i..j-}` lelt: `i ≤ j < k` and: `P ∧ Q` nat: `ℕ` ge: `i ≥ j ` all: `∀x:A. B[x]` decidable: `Dec(P)` or: `P ∨ Q` uimplies: `b supposing a` not: `¬A` implies: `P `` Q` satisfiable_int_formula: `satisfiable_int_formula(fmla)` exists: `∃x:A. B[x]` false: `False` top: `Top` prop: `ℙ` guard: `{T}` iff: `P `⇐⇒` Q` squash: `↓T` rev_implies: `P `` Q` so_lambda: `λ2x.t[x]` so_apply: `x[s]` uiff: `uiff(P;Q)` bag-member: `x ↓∈ bs` subtype_rel: `A ⊆r B` sq_type: `SQType(T)` lifting-gen-list-rev: `lifting-gen-list-rev(n;bags)` true: `True` ifthenelse: `if b then t else f fi ` btrue: `tt` funtype: `funtype(n;A;T)` lt_int: `i <z j` subtract: `n - m` uncurry-gen: `uncurry-gen(n)` cand: `A c∧ B` nequal: `a ≠ b ∈ T ` bfalse: `ff` assert: `↑b` bool: `𝔹` unit: `Unit` it: `⋅` bnot: `¬bb` gt: `i > j` sq_stable: `SqStable(P)` le: `A ≤ B` less_than': `less_than'(a;b)` istype: `istype(T)`
Lemmas referenced :  uncurry-gen_wf2 nat_properties decidable__lt full-omega-unsat intformnot_wf intformless_wf itermVar_wf itermAdd_wf itermConstant_wf istype-int int_formula_prop_not_lemma istype-void int_formula_prop_less_lemma int_term_value_var_lemma int_term_value_add_lemma int_term_value_constant_lemma int_formula_prop_wf le_wf less_than_wf int_seg_wf int_seg_properties decidable__le intformand_wf intformle_wf int_formula_prop_and_lemma int_formula_prop_le_lemma bag-member_wf lifting-gen-list-rev_wf squash_wf exists_wf uall_wf equal_wf istype-universe funtype_wf subtract_wf itermSubtract_wf int_term_value_subtract_lemma add-member-int_seg1 bag_wf nat_wf decidable__equal_int intformeq_wf int_formula_prop_eq_lemma int_subtype_base set_subtype_base subtype_base_sq ge_wf add-member-int_seg2 subtract-1-ge-0 bool_wf bool_subtype_base true_wf eq_int_eq_true btrue_wf subtype_rel_self iff_weakening_equal primrec-unroll bag-member-single eq_int_eq_false bfalse_wf bag-member-combine iff_imp_equal_bool lt_int_wf iff_functionality_wrt_iff assert_wf false_wf iff_weakening_uiff assert_of_lt_int subtype_rel-equal primrec_wf add-associates minus-one-mul add-swap add-mul-special add-commutes zero-mul add-zero itermMultiply_wf int_term_value_mul_lemma eq_int_wf eqtt_to_assert assert_of_eq_int eqff_to_assert bool_cases_sqequal assert-bnot neg_assert_of_eq_int bool_cases decidable__or equal-wf-base intformor_wf int_formula_prop_or_lemma btrue_neq_bfalse apply_uncurry minus-add minus-minus one-mul apply_larger_list sq_stable__bag-member subtype_rel_dep_function int_seg_subtype istype-false not-le-2 condition-implies-le minus-one-mul-top zero-add le-add-cancel le_reflexive
Rules used in proof :  cut introduction extract_by_obid sqequalHypSubstitution sqequalSubstitution sqequalTransitivity computationStep sqequalReflexivity isectElimination thin hypothesisEquality setElimination rename dependent_set_memberEquality_alt productElimination independent_pairFormation hypothesis dependent_functionElimination addEquality natural_numberEquality unionElimination independent_isectElimination approximateComputation independent_functionElimination dependent_pairFormation_alt lambdaEquality_alt int_eqEquality isect_memberEquality_alt voidElimination sqequalRule universeIsType productIsType functionIsType because_Cache applyEquality lambdaFormation_alt imageElimination imageMemberEquality baseClosed functionEquality productEquality inhabitedIsType universeEquality isect_memberFormation_alt independent_pairEquality functionIsTypeImplies equalityIsType4 baseApply closedConclusion intEquality instantiate cumulativity equalityTransitivity equalitySymmetry intWeakElimination isectIsType equalityIsType1 multiplyEquality minusEquality promote_hyp equalityElimination equalityIsType2 hyp_replacement applyLambdaEquality

Latex:
\mforall{}[B:Type].  \mforall{}[n:\mBbbN{}].  \mforall{}[m:\mBbbN{}n  +  1].  \mforall{}[A:\mBbbN{}n  {}\mrightarrow{}  Type].  \mforall{}[bags:k:\mBbbN{}n  {}\mrightarrow{}  bag(A  k)].
\mforall{}[f:funtype(n  -  m;\mlambda{}x.(A  (x  +  m));B)].  \mforall{}[b:B].
(b  \mdownarrow{}\mmember{}  lifting-gen-list-rev(n;bags)  m  f
\mLeftarrow{}{}\mRightarrow{}  \mdownarrow{}\mexists{}lst:k:\{m..n\msupminus{}\}  {}\mrightarrow{}  (A  k)
((\mforall{}[k:\{m..n\msupminus{}\}].  lst  k  \mdownarrow{}\mmember{}  bags  k)  \mwedge{}  ((uncurry-gen(n)  m  (\mlambda{}x.f)  lst)  =  b)))

Date html generated: 2019_10_15-AM-11_04_47
Last ObjectModification: 2018_10_09-AM-10_53_21

Theory : bags

Home Index