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),
length: ||as||,
null: null(as),
filter: filter(P;l),
append: as @ bs,
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
Definitions unfolded in proof :
uall: ∀[x:A]. B[x],
all: ∀x:A. B[x],
iff: P ⇐⇒ Q,
and: P ∧ Q,
implies: P ⇒ Q,
member: t ∈ T,
prop: ℙ,
rev_implies: P ⇐ Q,
nat: ℕ,
subtype_rel: A ⊆r B,
uimplies: b supposing a,
so_lambda: λ2x.t[x],
so_apply: x[s],
top: Top,
less_than: a < b,
le: A ≤ B,
or: P ∨ Q,
archive-condition: archive-condition(V;A;t;f;n;v;L),
exists: ∃x:A. B[x],
guard: {T},
cand: A c∧ B,
not: ¬A,
false: False,
cons: [a / b],
decidable: Dec(P),
uiff: uiff(P;Q),
subtract: n - m,
less_than': less_than'(a;b),
true: True,
listp: A List+,
cs-rcv-vote: Vote[a;i;v],
cs-initial-rcv: Init[v],
consensus-rcv: consensus-rcv(V;A),
isl: isl(x),
pi1: fst(t),
pi2: snd(t),
ge: i ≥ j ,
satisfiable_int_formula: satisfiable_int_formula(fmla),
squash: ↓T,
assert: ↑b
Latex:
\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:
2016_05_16-PM-00_36_53
Last ObjectModification:
2016_01_17-PM-08_02_56
Theory : event-ordering
Home
Index