Nuprl Lemma : bag-filter-equal
∀[T:Type]. ∀[p1,p2:T ⟶ 𝔹]. ∀[b:bag(T)]. uiff([x∈b|p1[x]] = [x∈b|p2[x]] ∈ bag(T);∀x:T. (x ↓∈ b ⇒ (↑p1[x] ⇐⇒ ↑p2[x])))
Proof
Definitions occuring in Statement :
bag-member: x ↓∈ bs,
bag-filter: [x∈b|p[x]],
bag: bag(T),
assert: ↑b,
bool: 𝔹,
uiff: uiff(P;Q),
uall: ∀[x:A]. B[x],
so_apply: x[s],
all: ∀x:A. B[x],
iff: P ⇐⇒ Q,
implies: P ⇒ Q,
function: x:A ⟶ B[x],
universe: Type,
equal: s = t ∈ T
Definitions unfolded in proof :
uiff: uiff(P;Q),
and: P ∧ Q,
uimplies: b supposing a,
member: t ∈ T,
all: ∀x:A. B[x],
implies: P ⇒ Q,
prop: ℙ,
uall: ∀[x:A]. B[x],
iff: P ⇐⇒ Q,
rev_implies: P ⇐ Q,
so_lambda: λ2x.t[x],
so_apply: x[s],
subtype_rel: A ⊆r B,
cand: A c∧ B,
squash: ↓T,
exists: ∃x:A. B[x],
bag-filter: [x∈b|p[x]],
sq_stable: SqStable(P)
Lemmas referenced :
bag-member_wf,
assert_witness,
equal_wf,
bag_wf,
bag-filter_wf,
subtype_rel_bag,
assert_wf,
all_wf,
iff_wf,
bool_wf,
bag-member-filter,
bag_to_squash_list,
filter-sq,
l_member_wf,
sq_stable_from_decidable,
decidable__assert,
list-member-bag-member,
set_wf,
filter_wf5,
list-subtype-bag
Rules used in proof :
sqequalSubstitution,
sqequalTransitivity,
computationStep,
sqequalReflexivity,
independent_pairFormation,
isect_memberFormation,
introduction,
cut,
lambdaFormation,
extract_by_obid,
sqequalHypSubstitution,
isectElimination,
thin,
cumulativity,
hypothesisEquality,
hypothesis,
sqequalRule,
lambdaEquality,
dependent_functionElimination,
productElimination,
independent_pairEquality,
because_Cache,
independent_functionElimination,
applyEquality,
functionExtensionality,
setEquality,
independent_isectElimination,
setElimination,
rename,
functionEquality,
universeEquality,
isect_memberEquality,
equalityTransitivity,
equalitySymmetry,
axiomEquality,
hyp_replacement,
Error :applyLambdaEquality,
imageElimination,
promote_hyp,
imageMemberEquality,
baseClosed
Latex:
\mforall{}[T:Type]. \mforall{}[p1,p2:T {}\mrightarrow{} \mBbbB{}]. \mforall{}[b:bag(T)].
uiff([x\mmember{}b|p1[x]] = [x\mmember{}b|p2[x]];\mforall{}x:T. (x \mdownarrow{}\mmember{} b {}\mRightarrow{} (\muparrow{}p1[x] \mLeftarrow{}{}\mRightarrow{} \muparrow{}p2[x])))
Date html generated:
2016_10_25-AM-10_30_19
Last ObjectModification:
2016_07_12-AM-06_46_49
Theory : bags
Home
Index