Proof of Nuprl Lemma : reliable-env-property2

Step * 1 1 2 1 1 2 1 1 1 of Lemma reliable-env-property2

1. [M] : Type ─→ Type
2. Continuous+(P.M[P])
3. S : InitialSystem(P.M[P])@i
4. n2m : ℕ ─→ pMsg(P.M[P])@i
5. l2m : Id ─→ pMsg(P.M[P])@i
6. env : pEnvType(P.M[P])@i
7. pRun(S;env;n2m;l2m) ∈ pRunType(P.M[P])
8. reliable-env(env; pRun(S;env;n2m;l2m))@i
9. ∀tn:run-msg-commands(pRun(S;env;n2m;l2m))
     ∃e:runEvents(pRun(S;env;n2m;l2m))
      let t,n = tn
      in (run-info(pRun(S;env;n2m;l2m);e)

         = intransit-to-info(n2m;l2m;pRun(S;env;n2m;l2m);env;run-event-step(e);run-command(pRun(S;env;n2m;l2m);t;n))

∈ (ℤ × Id × pMsg(P.M[P])))
∧ (run-event-loc(e) = (fst(snd(run-command(pRun(S;env;n2m;l2m);t;n)))) ∈ Id)
10. t : ℕ@i
11. x : Id@i
12. λc.fst(c) = x ∈ component(P.M[P]) ─→ 𝔹
13. \\%12 : ↑is-run-event(pRun(S;env;n2m;l2m);t;x)@i
14. P : Process(P.M[P])@i
15. (P ∈ run-event-state-when(pRun(S;env;n2m;l2m);<t, x>))@i
16. 0 < t
17. v1 : ℤ × Id@i
18. ms : pMsg(P.M[P])@i

19. let info,S = pRun(S;env;n2m;l2m) t in let ev,z,m = outl(info) in <ev, m> = <v1, ms> ∈ (ℤ × Id × pMsg(P.M[P]))@i

20. v2 : Process(P.M[P])@i
21. G : LabeledDAG(Id × pCom(P.M[P]))@i
22. Process-apply(P;ms) = <v2, G> ∈ (Process(P.M[P]) × pExt(P.M[P]))@i
23. n : ℕlg-size(G)@i
24. v3 : Id@i
25. v4 : pCom(P.M[P])@i
26. lg-label(G;n) = <v3, v4> ∈ (Id × pCom(P.M[P]))@i
27. (com-kind(v4) ∈ ``msg choose new``)@i
28. ga : LabeledGraph(pInTransit(P.M[P]))
29. gb : LabeledGraph(pInTransit(P.M[P]))

30. (snd(snd((pRun(S;env;n2m;l2m) t)))) = lg-append(ga;lg-append(add-cause(<t, x>;G);gb)) ∈ LabeledGraph(pInTransit(P.M[\000CP]))

31. H : LabeledDAG(pInTransit(P.M[P]))@i
32. add-cause(<t, x>;G) = H ∈ LabeledDAG(pInTransit(P.M[P]))@i
33. n < lg-size(H)@i
⊢ ∃m:ℕlg-size(lg-append(ga;lg-append(H;gb)))
   (lg-label(lg-append(ga;lg-append(H;gb));m) = lg-label(H;n) ∈ pInTransit(P.M[P]))
BY
{ (With ⌈n + lg-size(ga)⌉ (D 0)⋅ THEN Try (Complete (Auto))) }

1
.....wf.....
1. M : Type ─→ Type
2. Continuous+(P.M[P])
3. S : InitialSystem(P.M[P])@i
4. n2m : ℕ ─→ pMsg(P.M[P])@i
5. l2m : Id ─→ pMsg(P.M[P])@i
6. env : pEnvType(P.M[P])@i
7. pRun(S;env;n2m;l2m) ∈ pRunType(P.M[P])
8. reliable-env(env; pRun(S;env;n2m;l2m))@i
9. ∀tn:run-msg-commands(pRun(S;env;n2m;l2m))
     ∃e:runEvents(pRun(S;env;n2m;l2m))
      let t,n = tn
      in (run-info(pRun(S;env;n2m;l2m);e)

         = intransit-to-info(n2m;l2m;pRun(S;env;n2m;l2m);env;run-event-step(e);run-command(pRun(S;env;n2m;l2m);t;n))

∈ (ℤ × Id × pMsg(P.M[P])))
∧ (run-event-loc(e) = (fst(snd(run-command(pRun(S;env;n2m;l2m);t;n)))) ∈ Id)
10. t : ℕ@i
11. x : Id@i
12. λc.fst(c) = x ∈ component(P.M[P]) ─→ 𝔹
13. ↑is-run-event(pRun(S;env;n2m;l2m);t;x)@i
14. P : Process(P.M[P])@i
15. (P ∈ run-event-state-when(pRun(S;env;n2m;l2m);<t, x>))@i
16. 0 < t
17. v1 : ℤ × Id@i
18. ms : pMsg(P.M[P])@i

19. let info,S = pRun(S;env;n2m;l2m) t in let ev,z,m = outl(info) in <ev, m> = <v1, ms> ∈ (ℤ × Id × pMsg(P.M[P]))@i

30. (snd(snd((pRun(S;env;n2m;l2m) t)))) = lg-append(ga;lg-append(add-cause(<t, x>;G);gb)) ∈ LabeledGraph(pInTransit(P.M[\000CP]))

31. H : LabeledDAG(pInTransit(P.M[P]))@i
32. add-cause(<t, x>;G) = H ∈ LabeledDAG(pInTransit(P.M[P]))@i
33. n < lg-size(H)@i
⊢ n + lg-size(ga) ∈ ℕlg-size(lg-append(ga;lg-append(H;gb)))

2
1. M : Type ─→ Type
2. Continuous+(P.M[P])
3. S : InitialSystem(P.M[P])@i
4. n2m : ℕ ─→ pMsg(P.M[P])@i
5. l2m : Id ─→ pMsg(P.M[P])@i
6. env : pEnvType(P.M[P])@i
7. pRun(S;env;n2m;l2m) ∈ pRunType(P.M[P])
8. reliable-env(env; pRun(S;env;n2m;l2m))@i
9. ∀tn:run-msg-commands(pRun(S;env;n2m;l2m))
     ∃e:runEvents(pRun(S;env;n2m;l2m))
      let t,n = tn
      in (run-info(pRun(S;env;n2m;l2m);e)

         = intransit-to-info(n2m;l2m;pRun(S;env;n2m;l2m);env;run-event-step(e);run-command(pRun(S;env;n2m;l2m);t;n))

∈ (ℤ × Id × pMsg(P.M[P])))
∧ (run-event-loc(e) = (fst(snd(run-command(pRun(S;env;n2m;l2m);t;n)))) ∈ Id)
10. t : ℕ@i
11. x : Id@i
12. λc.fst(c) = x ∈ component(P.M[P]) ─→ 𝔹
13. ↑is-run-event(pRun(S;env;n2m;l2m);t;x)@i
14. P : Process(P.M[P])@i
15. (P ∈ run-event-state-when(pRun(S;env;n2m;l2m);<t, x>))@i
16. 0 < t
17. v1 : ℤ × Id@i
18. ms : pMsg(P.M[P])@i

19. let info,S = pRun(S;env;n2m;l2m) t in let ev,z,m = outl(info) in <ev, m> = <v1, ms> ∈ (ℤ × Id × pMsg(P.M[P]))@i

30. (snd(snd((pRun(S;env;n2m;l2m) t)))) = lg-append(ga;lg-append(add-cause(<t, x>;G);gb)) ∈ LabeledGraph(pInTransit(P.M[\000CP]))

31. H : LabeledDAG(pInTransit(P.M[P]))@i
32. add-cause(<t, x>;G) = H ∈ LabeledDAG(pInTransit(P.M[P]))@i
33. n < lg-size(H)@i
⊢ lg-label(lg-append(ga;lg-append(H;gb));n + lg-size(ga)) = lg-label(H;n) ∈ pInTransit(P.M[P])

Latex:

Latex:
1. [M] : Type {}\mrightarrow{} Type 2. Continuous+(P.M[P]) 3. S : InitialSystem(P.M[P])@i 4. n2m : \mBbbN{} {}\mrightarrow{} pMsg(P.M[P])@i 5. l2m : Id {}\mrightarrow{} pMsg(P.M[P])@i 6. env : pEnvType(P.M[P])@i 7. pRun(S;env;n2m;l2m) \mmember{} pRunType(P.M[P]) 8. reliable-env(env; pRun(S;env;n2m;l2m))@i 9. \mforall{}tn:run-msg-commands(pRun(S;env;n2m;l2m)) \mexists{}e:runEvents(pRun(S;env;n2m;l2m)) let t,n = tn in ... \mwedge{} (run-event-loc(e) = (fst(snd(run-command(pRun(S;env;n2m;l2m);t;n))))) 10. t : \mBbbN{}@i 11. x : Id@i 12. \mlambda{}c.fst(c) = x \mmember{} component(P.M[P]) {}\mrightarrow{} \mBbbB{} 13. \mbackslash{}\mbackslash{}\%12 : \muparrow{}is-run-event(pRun(S;env;n2m;l2m);t;x)@i 14. P : Process(P.M[P])@i 15. (P \mmember{} run-event-state-when(pRun(S;env;n2m;l2m);<t, x>))@i 16. 0 < t 17. v1 : \mBbbZ{} \mtimes{} Id@i 18. ms : pMsg(P.M[P])@i 19. let info,S = pRun(S;env;n2m;l2m) t in let ev,z,m = outl(info) in <ev, m> = <v1, ms>@i 20. v2 : Process(P.M[P])@i 21. G : LabeledDAG(Id \mtimes{} pCom(P.M[P]))@i 22. Process-apply(P;ms) = <v2, G>@i 23. n : \mBbbN{}lg-size(G)@i 24. v3 : Id@i 25. v4 : pCom(P.M[P])@i 26. lg-label(G;n) = <v3, v4>@i 27. (com-kind(v4) \mmember{} ``msg choose new``)@i 28. ga : LabeledGraph(pInTransit(P.M[P])) 29. gb : LabeledGraph(pInTransit(P.M[P])) 30. (snd(snd((pRun(S;env;n2m;l2m) t)))) = lg-append(ga;lg-append(add-cause(<t, x>G);gb)) 31. H : LabeledDAG(pInTransit(P.M[P]))@i 32. add-cause(<t, x>G) = H@i 33. n < lg-size(H)@i \mvdash{} \mexists{}m:\mBbbN{}lg-size(lg-append(ga;lg-append(H;gb))) (lg-label(lg-append(ga;lg-append(H;gb));m) = lg-label(H;n)) By Latex: (With \mkleeneopen{}n + lg-size(ga)\mkleeneclose{} (D 0)\mcdot{} THEN Try (Complete (Auto))) Home Index