Nuprl Lemma : archive-condition-append-vote
∀[V:Type]
∀A:Id List. ∀t:ℕ. ∀f:(V List) ─→ V. ∀L:consensus-rcv(V;A) List. ∀n:ℤ. ∀v,v2:V. ∀a:{b:Id| (b ∈ A)} . ∀i:ℕ.
(archive-condition(V;A;t;f;n;v;L @ [Vote[a;i;v2]])
⇐⇒ ((L = [] ∈ (consensus-rcv(V;A) List)) ∧ (i = n ∈ ℤ) ∧ (v = v2 ∈ V))
∨ ((0 < n ∧ (||values-for-distinct(IdDeq;votes-from-inning(n - 1;L))|| ≤ (2 * t)))
∧ (↑null(filter(λr.n - 1 <z inning(r);L)))
∧ (((i = n ∈ ℤ) ∧ (v = v2 ∈ V))
∨ ((((2 * t) + 1) ≤ ||values-for-distinct(IdDeq;votes-from-inning(n - 1;L @ [Vote[a;i;v2]]))||)
∧ ((f values-for-distinct(IdDeq;votes-from-inning(n - 1;L @ [Vote[a;i;v2]]))) = v ∈ V)))))
Proof
Definitions occuring in Statement :
archive-condition: archive-condition(V;A;t;f;n;v;L),
votes-from-inning: votes-from-inning(i;L),
rcvd-inning-gt: i <z inning(r),
cs-rcv-vote: Vote[a;i;v],
consensus-rcv: consensus-rcv(V;A),
id-deq: IdDeq,
Id: Id,
values-for-distinct: values-for-distinct(eq;L),
l_member: (x ∈ l),
filter: filter(P;l),
length: ||as||,
append: as @ bs,
null: null(as),
cons: [a / b],
nil: [],
list: T List,
nat: ℕ,
assert: ↑b,
less_than: a < b,
uall: ∀[x:A]. B[x],
le: A ≤ B,
all: ∀x:A. B[x],
iff: P ⇐⇒ Q,
or: P ∨ Q,
and: P ∧ Q,
set: {x:A| B[x]} ,
apply: f a,
lambda: λx.A[x],
function: x:A ─→ B[x],
multiply: n * m,
subtract: n - m,
add: n + m,
natural_number: $n,
int: ℤ,
universe: Type,
equal: s = t ∈ T
Lemmas :
archive-condition_wf,
append_wf,
consensus-rcv_wf,
cons_wf,
cs-rcv-vote_wf,
nil_wf,
or_wf,
equal-wf-T-base,
list_wf,
length_wf,
length_of_nil_lemma,
int_subtype_base,
less_than_wf,
le_wf,
values-for-distinct_wf,
Id_wf,
l_member_wf,
id-deq_wf,
subtype_rel-deq,
sq_stable__l_member,
decidable__equal_Id,
equal_wf,
set_wf,
votes-from-inning_wf,
subtract_wf,
assert_wf,
null_wf3,
filter_wf5,
rcvd-inning-gt_wf,
subtype_rel_list,
top_wf,
nat_wf,
general-append-cancellation,
length_of_cons_lemma,
hd_wf,
listp_properties,
assert_of_lt_int,
list-cases,
cons_neq_nil,
product_subtype_list,
length_wf_nat,
decidable__lt,
false_wf,
condition-implies-le,
minus-add,
minus-one-mul,
zero-add,
add-commutes,
add_functionality_wrt_le,
add-associates,
add-zero,
le-add-cancel,
lt_int_wf,
reduce_hd_cons_lemma,
tl_wf,
reduce_tl_cons_lemma,
bfalse_wf,
and_wf,
isl_wf,
btrue_wf,
btrue_neq_bfalse,
pi2_wf,
pi1_wf_top,
squash_wf,
true_wf,
le_weakening2,
sq_stable__le,
le_transitivity,
le_weakening,
cs-initial-rcv_wf,
not_wf,
exists_wf,
length-append,
equal-wf-base
\mforall{}[V:Type]
\mforall{}A:Id List. \mforall{}t:\mBbbN{}. \mforall{}f:(V List) {}\mrightarrow{} V. \mforall{}L:consensus-rcv(V;A) List. \mforall{}n:\mBbbZ{}. \mforall{}v,v2:V. \mforall{}a:\{b:Id| (b \mmember{} A)\} \000C.
\mforall{}i:\mBbbN{}.
(archive-condition(V;A;t;f;n;v;L @ [Vote[a;i;v2]])
\mLeftarrow{}{}\mRightarrow{} ((L = []) \mwedge{} (i = n) \mwedge{} (v = v2))
\mvee{} ((0 < n \mwedge{} (||values-for-distinct(IdDeq;votes-from-inning(n - 1;L))|| \mleq{} (2 * t)))
\mwedge{} (\muparrow{}null(filter(\mlambda{}r.n - 1 <z inning(r);L)))
\mwedge{} (((i = n) \mwedge{} (v = v2))
\mvee{} ((((2 * t) + 1) \mleq{} ||values-for-distinct(IdDeq;votes-from-inning(n - 1;L
@ [Vote[a;i;v2]]))||)
\mwedge{} ((f values-for-distinct(IdDeq;votes-from-inning(n - 1;L @ [Vote[a;i;v2]]))) = v)))))
Date html generated:
2015_07_17-AM-11_48_37
Last ObjectModification:
2015_01_28-AM-00_46_13
Home
Index