Proof of Nuprl Lemma : three-cs-archive-invariant

Step * 1 2 1 2 1 1 2 1 of Lemma three-cs-archive-invariant

1. V : Type
2. eq : EqDecider(V)@i
3. A : Id List@i
4. t : ℕ⁺@i
5. f : (V List) ─→ V@i
6. ∀vs:V List. (f vs ∈ vs) supposing ||vs|| ≥ 1 @i
7. ∀x,y:V.  Dec(x = y ∈ V)
8. ∀s:{a:Id| (a ∈ A)}  ─→ (consensus-rcv(V;A) List). ∀v:V.
     Dec((∃a∈A. (||s a|| ≥ 1 ) ∧ (hd(s a) = Init[v] ∈ consensus-rcv(V;A))))
9. ts-reachable(three-consensus-ts(V;A;t;f)) ⊆r ({a:Id| (a ∈ A)}  ─→ (consensus-rcv(V;A) List))
10. s : ts-type(three-consensus-ts(V;A;t;f))@i
11. ts-init(three-consensus-ts(V;A;t;f)) (ts-rel(three-consensus-ts(V;A;t;f))^*) s@i
12. y : ts-reachable(three-consensus-ts(V;A;t;f))@i
13. ∀v:V. ∀a:{a:Id| (a ∈ A)} . ∀n:ℤ. ∀L:consensus-rcv(V;A) List.
      (L ≤ s a
      ⇒ archive-condition(V;A;t;f;n;v;L)
      ⇒ (∃a∈A. (||s a|| ≥ 1 ) ∧ (hd(s a) = Init[v] ∈ consensus-rcv(V;A))))@i
14. a1 : {a:Id| (a ∈ A)} @i
15. y2 : {b:Id| (b ∈ A)} @i
16. y4 : ℕ@i
17. y5 : V@i
18. ∀b:{a:Id| (a ∈ A)} . ∀i:ℕ. ∀v:V.
      ((Vote[y2;y4;y5] = Vote[b;i;v] ∈ consensus-rcv(V;A))
      ⇒

 ((∃L:consensus-rcv(V;A) List. (L ≤ s b ∧ archive-condition(V;A;t;f;i;v;L))) ∧ (¬(Vote[y2;y4;y5] ∈ s a1))))@i

19. ∀b:{a:Id| (a ∈ A)} . ((¬(b = a1 ∈ Id)) ⇒ ((y b) = (s b) ∈ (consensus-rcv(V;A) List)))@i
20. (y a1) = ((s a1) @ [Vote[y2;y4;y5]]) ∈ (consensus-rcv(V;A) List)@i
21. v : V@i
22. a : {a:Id| (a ∈ A)} @i
23. n : ℤ@i
24. L : consensus-rcv(V;A) List@i
25. L ≤ y a@i
26. archive-condition(V;A;t;f;n;v;L)@i
27. (∃a∈A. (||s a|| ≥ 1 ) ∧ (hd(s a) = Init[v] ∈ consensus-rcv(V;A)))
⇒ (∃a∈A. (||y a|| ≥ 1 ) ∧ (hd(y a) = Init[v] ∈ consensus-rcv(V;A)))
28. a = a1 ∈ Id
29. L ≤ (s a1) @ [Vote[y2;y4;y5]]
30. L = ((s a1) @ [Vote[y2;y4;y5]]) ∈ (consensus-rcv(V;A) List)
31. (((s a1) = [] ∈ (consensus-rcv(V;A) List)) ∧ (y4 = n ∈ ℤ) ∧ (v = y5 ∈ V))
∨ ((0 < n ∧ (||values-for-distinct(IdDeq;votes-from-inning(n - 1;s a1))|| ≤ (2 * t)))
∧ (↑null(filter(λr.n - 1 <z inning(r);s a1)))
∧ (((y4 = n ∈ ℤ) ∧ (v = y5 ∈ V))

    ∨ ((((2 * t) + 1) ≤ ||values-for-distinct(IdDeq;votes-from-inning(n - 1;(s a1) @ [Vote[y2;y4;y5]]))||)

      ∧ ((f values-for-distinct(IdDeq;votes-from-inning(n - 1;(s a1) @ [Vote[y2;y4;y5]]))) = v ∈ V))))

⊢ (∃a∈A. (||y a|| ≥ 1 ) ∧ (hd(y a) = Init[v] ∈ consensus-rcv(V;A)))
BY
{ (Decide v = y5 ∈ V THENA Auto) }

1
1. V : Type
2. eq : EqDecider(V)@i
3. A : Id List@i
4. t : ℕ⁺@i
5. f : (V List) ─→ V@i
6. ∀vs:V List. (f vs ∈ vs) supposing ||vs|| ≥ 1 @i
7. ∀x,y:V.  Dec(x = y ∈ V)
8. ∀s:{a:Id| (a ∈ A)}  ─→ (consensus-rcv(V;A) List). ∀v:V.
     Dec((∃a∈A. (||s a|| ≥ 1 ) ∧ (hd(s a) = Init[v] ∈ consensus-rcv(V;A))))
9. ts-reachable(three-consensus-ts(V;A;t;f)) ⊆r ({a:Id| (a ∈ A)}  ─→ (consensus-rcv(V;A) List))
10. s : ts-type(three-consensus-ts(V;A;t;f))@i
11. ts-init(three-consensus-ts(V;A;t;f)) (ts-rel(three-consensus-ts(V;A;t;f))^*) s@i
12. y : ts-reachable(three-consensus-ts(V;A;t;f))@i
13. ∀v:V. ∀a:{a:Id| (a ∈ A)} . ∀n:ℤ. ∀L:consensus-rcv(V;A) List.
      (L ≤ s a
      ⇒ archive-condition(V;A;t;f;n;v;L)
      ⇒ (∃a∈A. (||s a|| ≥ 1 ) ∧ (hd(s a) = Init[v] ∈ consensus-rcv(V;A))))@i
14. a1 : {a:Id| (a ∈ A)} @i
15. y2 : {b:Id| (b ∈ A)} @i
16. y4 : ℕ@i
17. y5 : V@i
18. ∀b:{a:Id| (a ∈ A)} . ∀i:ℕ. ∀v:V.
      ((Vote[y2;y4;y5] = Vote[b;i;v] ∈ consensus-rcv(V;A))
      ⇒

 ((∃L:consensus-rcv(V;A) List. (L ≤ s b ∧ archive-condition(V;A;t;f;i;v;L))) ∧ (¬(Vote[y2;y4;y5] ∈ s a1))))@i

    ∨ ((((2 * t) + 1) ≤ ||values-for-distinct(IdDeq;votes-from-inning(n - 1;(s a1) @ [Vote[y2;y4;y5]]))||)

      ∧ ((f values-for-distinct(IdDeq;votes-from-inning(n - 1;(s a1) @ [Vote[y2;y4;y5]]))) = v ∈ V))))

32. v = y5 ∈ V
⊢ (∃a∈A. (||y a|| ≥ 1 ) ∧ (hd(y a) = Init[v] ∈ consensus-rcv(V;A)))

2
1. V : Type
2. eq : EqDecider(V)@i
3. A : Id List@i
4. t : ℕ⁺@i
5. f : (V List) ─→ V@i
6. ∀vs:V List. (f vs ∈ vs) supposing ||vs|| ≥ 1 @i
7. ∀x,y:V.  Dec(x = y ∈ V)
8. ∀s:{a:Id| (a ∈ A)}  ─→ (consensus-rcv(V;A) List). ∀v:V.
     Dec((∃a∈A. (||s a|| ≥ 1 ) ∧ (hd(s a) = Init[v] ∈ consensus-rcv(V;A))))
9. ts-reachable(three-consensus-ts(V;A;t;f)) ⊆r ({a:Id| (a ∈ A)}  ─→ (consensus-rcv(V;A) List))
10. s : ts-type(three-consensus-ts(V;A;t;f))@i
11. ts-init(three-consensus-ts(V;A;t;f)) (ts-rel(three-consensus-ts(V;A;t;f))^*) s@i
12. y : ts-reachable(three-consensus-ts(V;A;t;f))@i
13. ∀v:V. ∀a:{a:Id| (a ∈ A)} . ∀n:ℤ. ∀L:consensus-rcv(V;A) List.
      (L ≤ s a
      ⇒ archive-condition(V;A;t;f;n;v;L)
      ⇒ (∃a∈A. (||s a|| ≥ 1 ) ∧ (hd(s a) = Init[v] ∈ consensus-rcv(V;A))))@i
14. a1 : {a:Id| (a ∈ A)} @i
15. y2 : {b:Id| (b ∈ A)} @i
16. y4 : ℕ@i
17. y5 : V@i
18. ∀b:{a:Id| (a ∈ A)} . ∀i:ℕ. ∀v:V.
      ((Vote[y2;y4;y5] = Vote[b;i;v] ∈ consensus-rcv(V;A))
      ⇒

 ((∃L:consensus-rcv(V;A) List. (L ≤ s b ∧ archive-condition(V;A;t;f;i;v;L))) ∧ (¬(Vote[y2;y4;y5] ∈ s a1))))@i

    ∨ ((((2 * t) + 1) ≤ ||values-for-distinct(IdDeq;votes-from-inning(n - 1;(s a1) @ [Vote[y2;y4;y5]]))||)

      ∧ ((f values-for-distinct(IdDeq;votes-from-inning(n - 1;(s a1) @ [Vote[y2;y4;y5]]))) = v ∈ V))))

32. ¬(v = y5 ∈ V)
⊢ (∃a∈A. (||y a|| ≥ 1 ) ∧ (hd(y a) = Init[v] ∈ consensus-rcv(V;A)))

Latex:

1. V : Type 2. eq : EqDecider(V)@i 3. A : Id List@i 4. t : \mBbbN{}\msupplus{}@i 5. f : (V List) {}\mrightarrow{} V@i 6. \mforall{}vs:V List. (f vs \mmember{} vs) supposing ||vs|| \mgeq{} 1 @i 7. \mforall{}x,y:V. Dec(x = y) 8. \mforall{}s:\{a:Id| (a \mmember{} A)\} {}\mrightarrow{} (consensus-rcv(V;A) List). \mforall{}v:V. Dec((\mexists{}a\mmember{}A. (||s a|| \mgeq{} 1 ) \mwedge{} (hd(s a) = Init[v]))) 9. ts-reachable(three-consensus-ts(V;A;t;f)) \msubseteq{}r (\{a:Id| (a \mmember{} A)\} {}\mrightarrow{} (consensus-rcv(V;A) List)) 10. s : ts-type(three-consensus-ts(V;A;t;f))@i 11. ts-init(three-consensus-ts(V;A;t;f)) (ts-rel(three-consensus-ts(V;A;t;f))\^{}*) s@i 12. y : ts-reachable(three-consensus-ts(V;A;t;f))@i 13. \mforall{}v:V. \mforall{}a:\{a:Id| (a \mmember{} A)\} . \mforall{}n:\mBbbZ{}. \mforall{}L:consensus-rcv(V;A) List. (L \mleq{} s a {}\mRightarrow{} archive-condition(V;A;t;f;n;v;L) {}\mRightarrow{} (\mexists{}a\mmember{}A. (||s a|| \mgeq{} 1 ) \mwedge{} (hd(s a) = Init[v])))@i 14. a1 : \{a:Id| (a \mmember{} A)\} @i 15. y2 : \{b:Id| (b \mmember{} A)\} @i 16. y4 : \mBbbN{}@i 17. y5 : V@i 18. \mforall{}b:\{a:Id| (a \mmember{} A)\} . \mforall{}i:\mBbbN{}. \mforall{}v:V. ((Vote[y2;y4;y5] = Vote[b;i;v]) {}\mRightarrow{} ((\mexists{}L:consensus-rcv(V;A) List. (L \mleq{} s b \mwedge{} archive-condition(V;A;t;f;i;v;L))) \mwedge{} (\mneg{}(Vote[y2;y4;y5] \mmember{} s a1))))@i 19. \mforall{}b:\{a:Id| (a \mmember{} A)\} . ((\mneg{}(b = a1)) {}\mRightarrow{} ((y b) = (s b)))@i 20. (y a1) = ((s a1) @ [Vote[y2;y4;y5]])@i 21. v : V@i 22. a : \{a:Id| (a \mmember{} A)\} @i 23. n : \mBbbZ{}@i 24. L : consensus-rcv(V;A) List@i 25. L \mleq{} y a@i 26. archive-condition(V;A;t;f;n;v;L)@i 27. (\mexists{}a\mmember{}A. (||s a|| \mgeq{} 1 ) \mwedge{} (hd(s a) = Init[v])) {}\mRightarrow{} (\mexists{}a\mmember{}A. (||y a|| \mgeq{} 1 ) \mwedge{} (hd(y a) = Init[v])) 28. a = a1 29. L \mleq{} (s a1) @ [Vote[y2;y4;y5]] 30. L = ((s a1) @ [Vote[y2;y4;y5]]) 31. (((s a1) = []) \mwedge{} (y4 = n) \mwedge{} (v = y5)) \mvee{} ((0 < n \mwedge{} (||values-for-distinct(IdDeq;votes-from-inning(n - 1;s a1))|| \mleq{} (2 * t))) \mwedge{} (\muparrow{}null(filter(\mlambda{}r.n - 1 <z inning(r);s a1))) \mwedge{} (((y4 = n) \mwedge{} (v = y5)) \mvee{} ((((2 * t) + 1) \mleq{} ||values-for-distinct(IdDeq;votes-from-inning(n - 1;(s a1) @ [Vote[y2;y4;y5]]))||) \mwedge{} ((f values-for-distinct(IdDeq;votes-from-inning(n - 1;(s a1) @ [Vote[y2;y4;y5]]))) = v)))) \mvdash{} (\mexists{}a\mmember{}A. (||y a|| \mgeq{} 1 ) \mwedge{} (hd(y a) = Init[v])) By (Decide v = y5 THENA Auto) Home Index