### Nuprl Lemma : bag-count-map

`∀[T1,T2:Type]. ∀[f:T1 ⟶ T2]. ∀[eq1:EqDecider(T1)]. ∀[eq2:EqDecider(T2)]. ∀[x:T2]. ∀[bs:bag(T1)]. ∀[g:T2 ⟶ T1].`
`  (#x in bag-map(f;bs)) ~ (#g x in bs) supposing (∀x:T2. ((f (g x)) = x ∈ T2)) ∧ (∀x:T1. ((g (f x)) = x ∈ T1))`

Proof

Definitions occuring in Statement :  bag-count: `(#x in bs)` bag-map: `bag-map(f;bs)` bag: `bag(T)` deq: `EqDecider(T)` uimplies: `b supposing a` uall: `∀[x:A]. B[x]` all: `∀x:A. B[x]` and: `P ∧ Q` apply: `f a` function: `x:A ⟶ B[x]` universe: `Type` sqequal: `s ~ t` equal: `s = t ∈ T`
Definitions unfolded in proof :  uall: `∀[x:A]. B[x]` member: `t ∈ T` uimplies: `b supposing a` and: `P ∧ Q` nat: `ℕ` so_lambda: `λ2x.t[x]` so_apply: `x[s]` squash: `↓T` all: `∀x:A. B[x]` subtype_rel: `A ⊆r B` guard: `{T}` iff: `P `⇐⇒` Q` rev_implies: `P `` Q` implies: `P `` Q` true: `True` sq_type: `SQType(T)` prop: `ℙ` inject: `Inj(A;B;f)`
Lemmas referenced :  bag-count-ap-map subtype_base_sq nat_wf set_subtype_base le_wf int_subtype_base bag-count_wf equal_wf iff_weakening_equal all_wf bag_wf deq_wf squash_wf true_wf
Rules used in proof :  cut introduction extract_by_obid sqequalSubstitution sqequalTransitivity computationStep sqequalReflexivity isect_memberFormation hypothesis sqequalHypSubstitution isectElimination thin hypothesisEquality productElimination instantiate cumulativity independent_isectElimination sqequalRule intEquality lambdaEquality natural_numberEquality applyEquality functionExtensionality imageElimination because_Cache dependent_functionElimination equalitySymmetry imageMemberEquality baseClosed equalityTransitivity independent_functionElimination sqequalAxiom productEquality isect_memberEquality functionEquality universeEquality lambdaFormation

Latex:
\mforall{}[T1,T2:Type].  \mforall{}[f:T1  {}\mrightarrow{}  T2].  \mforall{}[eq1:EqDecider(T1)].  \mforall{}[eq2:EqDecider(T2)].  \mforall{}[x:T2].  \mforall{}[bs:bag(T1)].
\mforall{}[g:T2  {}\mrightarrow{}  T1].
(\#x  in  bag-map(f;bs))  \msim{}  (\#g  x  in  bs)  supposing  (\mforall{}x:T2.  ((f  (g  x))  =  x))  \mwedge{}  (\mforall{}x:T1.  ((g  (f  x))  =  x))

Date html generated: 2018_05_21-PM-09_46_05
Last ObjectModification: 2017_07_26-PM-06_29_56

Theory : bags_2

Home Index