Nuprl Lemma : process-ordered-message_wf
∀[M:Type]. ∀[nL:n:ℕ × {L:({n + 1...} × M) List| sorted-by(λx,y. fst(x) < fst(y);L)} ]. ∀[km:ℕ × M].
(process-ordered-message(nL;km) ∈ {tr:({fst(nL)...} × M) List × n:{fst(nL)...} × (({n + 1...} × M) List)|
let out,n',L' = tr in
sorted-by(λx,y. fst(x) < fst(y);L')
∧ (0 < ||out|| ⇒ (((fst(km)) = (fst(nL)) ∈ ℤ) ∧ (hd(out) = km ∈ (ℕ × M))))
∧ (((fst(nL)) = (fst(km)) ∈ ℤ)
⇒ ([km / (snd(nL))] = (out @ L') ∈ (({fst(nL)...} × M) List)))
∧ (fst(nL) < fst(km)
⇒ (insert-ordered-message(snd(nL);km)
= (out @ L')
∈ (({(fst(nL)) + 1...} × M) List)))
∧ (fst(km) < fst(nL)
⇒ ((↑null(out)) ∧ (L' = (snd(nL)) ∈ (({(fst(nL)) + 1...} × M) List))))} )
Proof
Definitions occuring in Statement :
process-ordered-message: process-ordered-message(nL;km),
insert-ordered-message: insert-ordered-message(L;x),
sorted-by: sorted-by(R;L),
hd: hd(l),
length: ||as||,
append: as @ bs,
null: null(as),
cons: [a / b],
list: T List,
int_upper: {i...},
nat: ℕ,
assert: ↑b,
less_than: a < b,
spreadn: spread3,
uall: ∀[x:A]. B[x],
pi1: fst(t),
pi2: snd(t),
implies: P ⇒ Q,
and: P ∧ Q,
member: t ∈ T,
set: {x:A| B[x]} ,
lambda: λx.A[x],
product: x:A × B[x],
add: n + m,
natural_number: $n,
int: ℤ,
universe: Type,
equal: s = t ∈ T
Lemmas :
eval_list_sq,
insert-ordered-message_wf,
decidable__le,
false_wf,
not-le-2,
less-iff-le,
condition-implies-le,
add-associates,
minus-add,
minus-one-mul,
add-swap,
add-commutes,
zero-add,
add_functionality_wrt_le,
le-add-cancel2,
le_wf,
subtype_rel_set,
list_wf,
int_upper_wf,
top_wf,
sorted-by_wf,
l_member_wf,
less_than_wf,
subtype_rel_list,
value-type-has-value,
set-value-type,
list-value-type,
set_wf,
nil_wf,
le_weakening,
length_of_nil_lemma,
list_ind_nil_lemma,
null_nil_lemma,
less_than_transitivity1,
less_than_irreflexivity,
equal_wf,
less_than_transitivity2,
le_weakening2,
length_wf,
nat_wf,
hd_wf,
cons_wf,
append_wf,
subtype_rel_product,
int_upper_subtype_int_upper,
sq_stable__le,
assert_wf,
null_wf3,
list-cases,
product_subtype_list,
list_ind_cons_lemma,
length_of_cons_lemma,
reduce_hd_cons_lemma,
non_neg_length,
length_wf_nat,
int-value-type,
decidable__lt,
null_cons_lemma,
add-mul-special,
zero-mul,
add-zero,
le-add-cancel,
decidable__equal_int,
not-equal-2,
int_upper_subtype_nat,
not-ge-2,
equal-wf-T-base,
subtype_base_sq,
set_subtype_base,
int_subtype_base,
lt_int_wf,
bool_wf,
eqtt_to_assert,
assert_of_lt_int,
eqff_to_assert,
bool_cases_sqequal,
bool_subtype_base,
assert-bnot,
sorted-by-cons,
has-value_wf_base,
member_wf,
list-subtype,
lelt_wf,
split-maximal-consecutive_wf,
cons_wf_listp,
listp_wf,
last_wf,
listp_properties,
squash_wf,
true_wf,
iff_weakening_equal,
sorted-by-append,
l_all_iff,
l_all_wf2,
last_member
Latex:
\mforall{}[M:Type]. \mforall{}[nL:n:\mBbbN{} \mtimes{} \{L:(\{n + 1...\} \mtimes{} M) List| sorted-by(\mlambda{}x,y. fst(x) < fst(y);L)\} ]. \mforall{}[km:\mBbbN{} \mtimes{} M].
(process-ordered-message(nL;km) \mmember{} \{tr:(\{fst(nL)...\} \mtimes{} M) List
\mtimes{} n:\{fst(nL)...\}
\mtimes{} ((\{n + 1...\} \mtimes{} M) List)|
let out,n',L' = tr in
sorted-by(\mlambda{}x,y. fst(x) < fst(y);L')
\mwedge{} (0 < ||out|| {}\mRightarrow{} (((fst(km)) = (fst(nL))) \mwedge{} (hd(out) = km)))
\mwedge{} (((fst(nL)) = (fst(km))) {}\mRightarrow{} ([km / (snd(nL))] = (out @ L')))
\mwedge{} (fst(nL) < fst(km)
{}\mRightarrow{} (insert-ordered-message(snd(nL);km) = (out @ L')))
\mwedge{} (fst(km) < fst(nL) {}\mRightarrow{} ((\muparrow{}null(out)) \mwedge{} (L' = (snd(nL)))))\} )
Date html generated:
2015_07_23-PM-00_28_09
Last ObjectModification:
2015_02_04-PM-03_11_43
Home
Index