Nuprl Lemma : lg-search-minimal
∀[T:Type]. ∀[G:LabeledGraph(T)]. ∀[P:T ─→ 𝔹].
∀[n:ℕlg-size(G)]. outl(lg-search(G;x.P[x])) ≤ n supposing ↑P[lg-label(G;n)] supposing lg-exists(G;x.↑P[x])
Proof
Definitions occuring in Statement :
lg-search: lg-search(G;x.P[x]),
lg-exists: lg-exists(G;x.P[x]),
lg-label: lg-label(g;x),
lg-size: lg-size(g),
labeled-graph: LabeledGraph(T),
int_seg: {i..j-},
outl: outl(x),
assert: ↑b,
bool: 𝔹,
uimplies: b supposing a,
uall: ∀[x:A]. B[x],
so_apply: x[s],
le: A ≤ B,
function: x:A ─→ B[x],
natural_number: $n,
universe: Type
Lemmas :
search_property,
lg-size_wf,
lg-label2_wf,
eq_int_wf,
search_wf,
int_seg_wf,
bool_wf,
eqtt_to_assert,
assert_of_eq_int,
less_than_transitivity1,
le_weakening,
less_than_irreflexivity,
eqff_to_assert,
equal_wf,
bool_cases_sqequal,
subtype_base_sq,
bool_subtype_base,
assert-bnot,
neg_assert_of_eq_int,
decidable__le,
less_than_wf,
outl_wf,
assert_wf,
exists_wf,
labeled-graph_wf
Latex:
\mforall{}[T:Type]. \mforall{}[G:LabeledGraph(T)]. \mforall{}[P:T {}\mrightarrow{} \mBbbB{}].
\mforall{}[n:\mBbbN{}lg-size(G)]. outl(lg-search(G;x.P[x])) \mleq{} n supposing \muparrow{}P[lg-label(G;n)]
supposing lg-exists(G;x.\muparrow{}P[x])
Date html generated:
2015_07_23-AM-11_04_55
Last ObjectModification:
2015_01_28-PM-11_35_08
Home
Index