---

Step * 1 2 1 2 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-reachable(three-consensus-ts(V;A;t;f))@i
11. y : ts-reachable(three-consensus-ts(V;A;t;f))@i
12. ∀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
13. a1 : {a:Id| (a ∈ A)} @i
14. e : consensus-rcv(V;A)@i
15. ∀b:{a:Id| (a ∈ A)} . ∀i:ℕ. ∀v:V.
      ((e = 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))) ∧ (¬(e ∈ s a1))))@i
16. ∀b:{a:Id| (a ∈ A)} . ((¬(b = a1 ∈ Id)) ⇒ ((y b) = (s b) ∈ (consensus-rcv(V;A) List)))@i
17. (y a1) = ((s a1) @ [e]) ∈ (consensus-rcv(V;A) List)@i
18. v : V@i
19. a : {a:Id| (a ∈ A)} @i
20. n : ℤ@i
21. L : consensus-rcv(V;A) List@i
22. L ≤ y a@i
23. archive-condition(V;A;t;f;n;v;L)@i
24. (∃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)))
25. a = a1 ∈ Id
26. L ≤ (s a1) @ [e]
27. L = ((s a1) @ [e]) ∈ (consensus-rcv(V;A) List)
⊢ (∃a∈A. (||y a|| ≥ 1 ) ∧ (hd(y a) = Init[v] ∈ consensus-rcv(V;A)))
BY
{ (DVar `s' THEN Unhide THEN 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. e : consensus-rcv(V;A)@i
16. ∀b:{a:Id| (a ∈ A)} . ∀i:ℕ. ∀v:V.
      ((e = 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))) ∧ (¬(e ∈ s a1))))@i
17. ∀b:{a:Id| (a ∈ A)} . ((¬(b = a1 ∈ Id)) ⇒ ((y b) = (s b) ∈ (consensus-rcv(V;A) List)))@i
18. (y a1) = ((s a1) @ [e]) ∈ (consensus-rcv(V;A) List)@i
19. v : V@i
20. a : {a:Id| (a ∈ A)} @i
21. n : ℤ@i
22. L : consensus-rcv(V;A) List@i
23. L ≤ y a@i
24. archive-condition(V;A;t;f;n;v;L)@i
25. (∃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)))
26. a = a1 ∈ Id
27. L ≤ (s a1) @ [e]
28. L = ((s a1) @ [e]) ∈ (consensus-rcv(V;A) List)
⊢ (∃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-reachable(three-consensus-ts(V;A;t;f))@i
11.  y  :  ts-reachable(three-consensus-ts(V;A;t;f))@i
12.  \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
13.  a1  :  \{a:Id|  (a  \mmember{}  A)\}  @i
14.  e  :  consensus-rcv(V;A)@i
15.  \mforall{}b:\{a:Id|  (a  \mmember{}  A)\}  .  \mforall{}i:\mBbbN{}.  \mforall{}v:V.
            ((e  =  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{}(e  \mmember{}  s  a1))))@i
16.  \mforall{}b:\{a:Id|  (a  \mmember{}  A)\}  .  ((\mneg{}(b  =  a1))  {}\mRightarrow{}  ((y  b)  =  (s  b)))@i
17.  (y  a1)  =  ((s  a1)  @  [e])@i
18.  v  :  V@i
19.  a  :  \{a:Id|  (a  \mmember{}  A)\}  @i
20.  n  :  \mBbbZ{}@i
21.  L  :  consensus-rcv(V;A)  List@i
22.  L  \mleq{}  y  a@i
23.  archive-condition(V;A;t;f;n;v;L)@i
24.  (\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]))
25.  a  =  a1
26.  L  \mleq{}  (s  a1)  @  [e]
27.  L  =  ((s  a1)  @  [e])
\mvdash{}  (\mexists{}a\mmember{}A.  (||y  a||  \mgeq{}  1  )  \mwedge{}  (hd(y  a)  =  Init[v]))


By

(DVar  `s'  THEN  Unhide  THEN  Auto)

---

Home Index