{ 
[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),
outl: outl(x),
assert: b,
bool: ,
int_seg: {i..j
},
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
Definitions :
lg-exists: lg-exists(G;x.P[x]),
assert: b,
so_apply: x[s],
le: A B,
outl: outl(x),
lg-search: lg-search(G;x.P[x]),
all: x:A. B[x],
not: 
A,
member: t 
T,
let: let,
ifthenelse: if b then t else f fi ,
implies: P 
Q,
btrue: tt,
bfalse: ff,
prop: 
,
false: False,
isl: isl(x),
true: True,
uall: [x:A]. B[x],
uimplies: b supposing a,
exists: 
x:A. B[x],
so_lambda: 
x.t[x],
subtype: S 
T,
bool: ,
int_seg: {i..j},
nat: ,
and: P 
Q,
iff: P 
Q,
unit: Unit,
decidable: Dec(P),
or: P 
Q,
lg-label2: lg-label2(g;x),
it: 
Lemmas :
search_property,
lg-size_wf,
lg-label2_wf,
eq_int_wf,
search_wf,
int_seg_wf,
bool_wf,
iff_weakening_uiff,
uiff_transitivity,
assert_wf,
eqtt_to_assert,
assert_of_eq_int,
not_wf,
bnot_wf,
eqff_to_assert,
assert_of_bnot,
not_functionality_wrt_uiff,
decidable__le,
nat_wf,
add_wf,
outl_wf,
unit_wf,
lg-search_wf,
labeled-graph_wf
\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:
2011_08_16-PM-06_46_48
Last ObjectModification:
2011_06_18-AM-10_59_03
Home
Index