Nuprl Lemma : fset-to-list
∀[T:Type]
∀eq:EqDecider(T)
∀[R:T ⟶ T ⟶ ℙ]
((∀a,b:T. Dec(R a b)) ⇒ Linorder(T;a,b.R a b) ⇒ (∀s:fset(T). ∃L:T List. ∀x:T. (x ∈ s ⇐⇒ (x ∈ L))))
Proof
Definitions occuring in Statement :
fset-member: a ∈ s,
fset: fset(T),
l_member: (x ∈ l),
list: T List,
deq: EqDecider(T),
linorder: Linorder(T;x,y.R[x; y]),
decidable: Dec(P),
uall: ∀[x:A]. B[x],
prop: ℙ,
all: ∀x:A. B[x],
exists: ∃x:A. B[x],
iff: P ⇐⇒ Q,
implies: P ⇒ Q,
apply: f a,
function: x:A ⟶ B[x],
universe: Type
Definitions unfolded in proof :
uall: ∀[x:A]. B[x],
all: ∀x:A. B[x],
implies: P ⇒ Q,
member: t ∈ T,
exists: ∃x:A. B[x],
prop: ℙ,
so_lambda: λ2x y.t[x; y],
so_apply: x[s1;s2],
so_lambda: λ2x.t[x],
so_apply: x[s],
and: P ∧ Q,
subtype_rel: A ⊆r B,
uimplies: b supposing a,
pi1: fst(t),
fset: fset(T),
quotient: x,y:A//B[x; y],
squash: ↓T,
true: True,
iff: P ⇐⇒ Q,
rev_implies: P ⇐ Q,
cand: A c∧ B,
linorder: Linorder(T;x,y.R[x; y]),
order: Order(T;x,y.R[x; y]),
fset-member: a ∈ s,
decidable: Dec(P),
or: P ∨ Q,
sq_type: SQType(T),
guard: {T},
false: False,
not: ¬A,
l_contains: A ⊆ B,
uiff: uiff(P;Q),
set-equal: set-equal(T;x;y)
Lemmas referenced :
sorted-by-exists2,
decidable-equal-deq,
fset_wf,
linorder_wf,
all_wf,
decidable_wf,
deq_wf,
list_wf,
exists_wf,
sorted-by_wf,
subtype_rel_dep_function,
l_member_wf,
subtype_rel_self,
set_wf,
no_repeats_wf,
l_contains_wf,
equal_wf,
set-equal_wf,
set-equal-reflex,
equal-wf-base,
member_wf,
squash_wf,
true_wf,
set-equal-l_contains,
l_contains_transitivity,
sorted-by-unique,
iff_wf,
fset-member_wf,
fset-member_witness,
assert-deq-member,
decidable__assert,
deq-member_wf,
subtype_base_sq,
int_subtype_base,
l_all_iff,
assert_witness,
assert_equal,
assert_wf
Rules used in proof :
sqequalSubstitution,
sqequalTransitivity,
computationStep,
sqequalReflexivity,
isect_memberFormation,
lambdaFormation,
cut,
introduction,
extract_by_obid,
sqequalHypSubstitution,
isectElimination,
thin,
hypothesisEquality,
independent_functionElimination,
because_Cache,
hypothesis,
dependent_functionElimination,
promote_hyp,
productElimination,
cumulativity,
sqequalRule,
lambdaEquality,
applyEquality,
functionExtensionality,
functionEquality,
universeEquality,
productEquality,
instantiate,
setEquality,
independent_isectElimination,
setElimination,
rename,
dependent_pairFormation,
equalityTransitivity,
equalitySymmetry,
pointwiseFunctionality,
pertypeElimination,
imageElimination,
natural_numberEquality,
imageMemberEquality,
baseClosed,
independent_pairFormation,
unionElimination,
intEquality,
voidElimination,
addLevel,
impliesFunctionality
Latex:
\mforall{}[T:Type]
\mforall{}eq:EqDecider(T)
\mforall{}[R:T {}\mrightarrow{} T {}\mrightarrow{} \mBbbP{}]
((\mforall{}a,b:T. Dec(R a b))
{}\mRightarrow{} Linorder(T;a,b.R a b)
{}\mRightarrow{} (\mforall{}s:fset(T). \mexists{}L:T List. \mforall{}x:T. (x \mmember{} s \mLeftarrow{}{}\mRightarrow{} (x \mmember{} L))))
Date html generated:
2017_04_17-AM-09_23_08
Last ObjectModification:
2017_02_27-PM-05_26_33
Theory : finite!sets
Home
Index