Nuprl Lemma : fset-constrained-ac-glb-is-glb
ā[T:Type]. ā[eq:EqDecider(T)]. ā[P:fset(T) ā¶ š¹].
ā[ac1,ac2:{ac:fset(fset(T))| (āfset-antichain(eq;ac)) ā§ fset-all(ac;a.P[a])} ].
greatest-lower-bound({ac:fset(fset(T))|
(āfset-antichain(eq;ac)) ā§ fset-all(ac;a.P[a])} ;ac1,ac2.fset-ac-le(eq;ac1;ac2);ac1;ac2;glb(P;\000Cac1;ac2))
supposing āx,y:fset(T). (y ā x ā (ā(P x)) ā (ā(P y)))
Proof
Definitions occuring in Statement :
fset-constrained-ac-glb: glb(P;ac1;ac2),
fset-ac-le: fset-ac-le(eq;ac1;ac2),
fset-antichain: fset-antichain(eq;ac),
fset-all: fset-all(s;x.P[x]),
f-subset: xs ā ys,
fset: fset(T),
deq: EqDecider(T),
greatest-lower-bound: greatest-lower-bound(T;x,y.R[x; y];a;b;c),
assert: āb,
bool: š¹,
uimplies: b supposing a,
uall: ā[x:A]. B[x],
so_apply: x[s],
all: āx:A. B[x],
implies: P ā Q,
and: P ā§ Q,
set: {x:A| B[x]} ,
apply: f a,
function: x:A ā¶ B[x],
universe: Type
Definitions unfolded in proof :
uall: ā[x:A]. B[x],
member: t ā T,
uimplies: b supposing a,
greatest-lower-bound: greatest-lower-bound(T;x,y.R[x; y];a;b;c),
and: P ā§ Q,
cand: A cā§ B,
all: āx:A. B[x],
implies: P ā Q,
prop: ā,
fset-ac-le: fset-ac-le(eq;ac1;ac2),
fset-all: fset-all(s;x.P[x]),
so_lambda: Ī»2x.t[x],
subtype_rel: A ār B,
so_apply: x[s],
fset-constrained-ac-glb: glb(P;ac1;ac2),
so_lambda: Ī»2x y.t[x; y],
so_apply: x[s1;s2],
iff: P āā Q,
rev_implies: P ā Q,
uiff: uiff(P;Q),
rev_uimplies: rev_uimplies(P;Q),
not: Ā¬A,
squash: āT,
false: False,
exists: āx:A. B[x],
guard: {T},
top: Top,
true: True,
sq_stable: SqStable(P)
Lemmas referenced :
fset-ac-le_wf,
assert_witness,
fset-null_wf,
fset_wf,
fset-filter_wf,
bnot_wf,
deq-f-subset_wf,
fset-constrained-ac-glb_wf,
assert_wf,
fset-antichain_wf,
fset-all_wf,
set_wf,
all_wf,
f-subset_wf,
bool_wf,
deq_wf,
fset-all-iff,
deq-fset_wf,
iff_weakening_uiff,
fset-minimals_wf,
f-proper-subset-dec_wf,
f-union_wf,
fset-constrained-image_wf,
fset-union_wf,
uall_wf,
isect_wf,
fset-member_wf,
assert_of_bnot,
iff_wf,
member-fset-minimals,
assert-fset-null,
not_wf,
equal-wf-T-base,
member-f-union,
member-fset-constrained-image-iff,
member-fset-filter,
assert-deq-f-subset,
f-subset-union,
mem_empty_lemma,
squash_wf,
true_wf,
fset-union-commutes,
iff_weakening_equal,
fset-ac-le_transitivity,
fset-minimals-ac-le,
fset-ac-le-implies2,
f-union-subset,
equal_wf,
sq_stable_from_decidable,
decidable__assert
Rules used in proof :
sqequalSubstitution,
sqequalTransitivity,
computationStep,
sqequalReflexivity,
isect_memberFormation,
introduction,
cut,
independent_pairFormation,
hypothesis,
lambdaFormation,
extract_by_obid,
sqequalHypSubstitution,
isectElimination,
thin,
cumulativity,
hypothesisEquality,
setElimination,
rename,
because_Cache,
sqequalRule,
productElimination,
independent_pairEquality,
lambdaEquality,
applyEquality,
functionExtensionality,
setEquality,
productEquality,
independent_functionElimination,
dependent_functionElimination,
isect_memberEquality,
functionEquality,
equalityTransitivity,
equalitySymmetry,
universeEquality,
independent_isectElimination,
addLevel,
impliesFunctionality,
baseClosed,
imageElimination,
hyp_replacement,
applyLambdaEquality,
voidElimination,
voidEquality,
natural_numberEquality,
imageMemberEquality,
dependent_pairFormation
Latex:
\mforall{}[T:Type]. \mforall{}[eq:EqDecider(T)]. \mforall{}[P:fset(T) {}\mrightarrow{} \mBbbB{}].
\mforall{}[ac1,ac2:\{ac:fset(fset(T))| (\muparrow{}fset-antichain(eq;ac)) \mwedge{} fset-all(ac;a.P[a])\} ].
greatest-lower-bound(\{ac:fset(fset(T))|
(\muparrow{}fset-antichain(eq;ac)) \mwedge{} fset-all(ac;a.P[a])\} ;ac1,ac2.fset-ac-le(eq;ac1\000C;ac2);ac1;ac2;...)
supposing \mforall{}x,y:fset(T). (y \msubseteq{} x {}\mRightarrow{} (\muparrow{}(P x)) {}\mRightarrow{} (\muparrow{}(P y)))
Date html generated:
2017_04_17-AM-09_25_00
Last ObjectModification:
2017_02_27-PM-05_27_11
Theory : finite!sets
Home
Index