Nuprl Lemma : lg-search_wf
∀[T:Type]. ∀[G:LabeledGraph(T)]. ∀[P:T ─→ 𝔹]. (lg-search(G;x.P[x]) ∈ ℕlg-size(G)?)
Proof
Definitions occuring in Statement :
lg-search: lg-search(G;x.P[x]),
lg-size: lg-size(g),
labeled-graph: LabeledGraph(T),
int_seg: {i..j-},
bool: 𝔹,
uall: ∀[x:A]. B[x],
so_apply: x[s],
unit: Unit,
member: t ∈ T,
function: x:A ─→ B[x],
union: left + right,
natural_number: $n,
universe: Type
Lemmas :
lg-size_wf,
nat_wf,
let_wf,
int_seg_wf,
unit_wf2,
eq_int_wf,
bool_wf,
eqtt_to_assert,
assert_of_eq_int,
it_wf,
eqff_to_assert,
equal_wf,
bool_cases_sqequal,
subtype_base_sq,
bool_subtype_base,
assert-bnot,
neg_assert_of_eq_int,
subtract_wf,
decidable__le,
false_wf,
not-le-2,
not-equal-2,
sq_stable__le,
add_functionality_wrt_le,
add-associates,
add-zero,
zero-add,
le-add-cancel,
condition-implies-le,
add-commutes,
minus-add,
minus-zero,
minus-one-mul,
minus-minus,
add-swap,
decidable__lt,
less-iff-le,
lelt_wf,
search_wf,
lg-label_wf,
less_than_transitivity1,
le_weakening,
labeled-graph_wf
Latex:
\mforall{}[T:Type]. \mforall{}[G:LabeledGraph(T)]. \mforall{}[P:T {}\mrightarrow{} \mBbbB{}]. (lg-search(G;x.P[x]) \mmember{} \mBbbN{}lg-size(G)?)
Date html generated:
2015_07_23-AM-11_04_52
Last ObjectModification:
2015_01_28-PM-11_34_30
Home
Index