### Nuprl Lemma : concat-lifting-list-member

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

Proof

Definitions occuring in Statement :  concat-lifting-list: `concat-lifting-list(n;bags)` uncurry-gen: `uncurry-gen(n)` 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`
Definitions unfolded in proof :  bag-member: `x ↓∈ bs` rev_implies: `P `` Q` squash: `↓T` iff: `P `⇐⇒` Q` uiff: `uiff(P;Q)` so_apply: `x[s]` so_lambda: `λ2x.t[x]` top: `Top` false: `False` exists: `∃x:A. B[x]` satisfiable_int_formula: `satisfiable_int_formula(fmla)` implies: `P `` Q` not: `¬A` uimplies: `b supposing a` or: `P ∨ Q` decidable: `Dec(P)` all: `∀x:A. B[x]` ge: `i ≥ j ` nat: `ℕ` guard: `{T}` and: `P ∧ Q` lelt: `i ≤ j < k` int_seg: `{i..j-}` prop: `ℙ` uall: `∀[x:A]. B[x]` member: `t ∈ T` sq_type: `SQType(T)` subtype_rel: `A ⊆r B` cand: `A c∧ B` uncurry-gen: `uncurry-gen(n)` concat: `concat(ll)` bag-union: `bag-union(bbs)` single-bag: `{x}` subtract: `n - m` lt_int: `i <z j` funtype: `funtype(n;A;T)` btrue: `tt` ifthenelse: `if b then t else f fi ` true: `True` lifting-gen-list-rev: `lifting-gen-list-rev(n;bags)` concat-lifting-list: `concat-lifting-list(n;bags)` bfalse: `ff` nequal: `a ≠ b ∈ T ` le: `A ≤ B` less_than: `a < b` assert: `↑b` bnot: `¬bb` it: `⋅` unit: `Unit` bool: `𝔹` gt: `i > j` sq_stable: `SqStable(P)` istype: `istype(T)` less_than': `less_than'(a;b)` rev_uimplies: `rev_uimplies(P;Q)`
Rules used in proof :  functionIsTypeImplies independent_pairEquality baseClosed imageMemberEquality imageElimination lambdaFormation_alt isect_memberFormation_alt universeEquality functionIsType inhabitedIsType addEquality productEquality productIsType sqequalRule voidElimination isect_memberEquality_alt int_eqEquality lambdaEquality_alt dependent_pairFormation_alt independent_functionElimination approximateComputation independent_isectElimination natural_numberEquality unionElimination dependent_functionElimination independent_pairFormation productElimination dependent_set_memberEquality_alt rename setElimination applyEquality because_Cache functionEquality hypothesis hypothesisEquality thin isectElimination sqequalHypSubstitution extract_by_obid introduction cut sqequalReflexivity computationStep sqequalTransitivity sqequalSubstitution universeIsType intWeakElimination equalitySymmetry equalityTransitivity cumulativity instantiate intEquality closedConclusion baseApply equalityIsType4 isectIsType Error :memTop,  equalityIstype sqequalBase functionExtensionality_alt promote_hyp equalityElimination applyLambdaEquality hyp_replacement minusEquality multiplyEquality

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));bag(B))].  \mforall{}[b:B].
(b  \mdownarrow{}\mmember{}  concat-lifting-list(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{}  b  \mdownarrow{}\mmember{}  uncurry-gen(n)  m  (\mlambda{}x.f)  lst))

Date html generated: 2020_05_20-AM-08_03_32
Last ObjectModification: 2020_02_04-PM-02_19_59

Theory : bags

Home Index