Nuprl - Proof: topsortl-properties 1 2 2 2 2 1

(47steps total) PrintForm Definitions Lemmas graph 1 3 Sections Graphs Doc

1. the_graph: Graph
2. the_obj: GraphObject(the_graph)
3. L: Vertices(the_graph) List
4. i:Vertices(the_graph). (i L)
5. paren(Vertices(the_graph);dfsl(the_obj;L))
6. no_repeats(Vertices(the_graph)+Vertices(the_graph);dfsl(the_obj;L))
7. dfsl-traversal(the_graph;L;dfsl(the_obj;L))
8. i:Vertices(the_graph). (i L) (inr(i) dfsl(the_obj;L)) & (inl(i) dfsl(the_obj;L))
9. non-trivial-loop-free(the_graph)
10. L1,L2:Vertices(the_graph) List. L = (L1 @ L2) (s1,s2:Vertices(the_graph) List. topsortl(the_obj;L) = (s2 @ s1) & (j:Vertices(the_graph). ((j s1) L1-the_graph- > *j) & ((j s2) L2-the_graph- > *j & L1-the_graph- > *j)))
11. i:Vertices(the_graph), s1,s2:Vertices(the_graph) List. topsortl(the_obj;L) = (s1 @ [i] @ s2) (j:Vertices(the_graph). j = i i-the_graph- > *j (j s2))
12. i:Vertices(the_graph). (i topsortl(the_obj;L))
13. i,j:Vertices(the_graph). j = i i-the_graph- > *j i before j topsortl(the_obj;L)

i,j:Vertices(the_graph). j before i L j-the_graph- > *i (k:Vertices(the_graph). k before j L k-the_graph- > *i) i before j topsortl(the_obj;L)

By: Auto THEN RWO Thm* L:T List, x,y:T. x before y L (A,B:T List. L = (A @ B) & (x A) & (y B)) -3 THEN ExRepD THEN ListMemD2 -4 THEN Try (Using [`the_obj',the_obj] (BackThru Thm* For any graph the_obj:GraphObject(the_graph), x,y:V. Dec(x = y))) THEN InstHyp [s1 @ [j];s2 @ B] 10

Generated subgoals:

1 14. i: Vertices(the_graph)
15. j: Vertices(the_graph)
16. A: Vertices(the_graph) List
17. B: Vertices(the_graph) List
18. L = (A @ B)
19. (j A)
20. (i B)
21. j-the_graph- > *i
22. k:Vertices(the_graph). k before j L k-the_graph- > *i
23. s1: Vertices(the_graph) List
24. s2: Vertices(the_graph) List
25. A = (s1 @ [j / s2])
26. (j s1)
L = ((s1 @ [j]) @ s2 @ B) 1 step

2 14. i: Vertices(the_graph)
15. j: Vertices(the_graph)
16. A: Vertices(the_graph) List
17. B: Vertices(the_graph) List
18. L = (A @ B)
19. (j A)
20. (i B)
21. j-the_graph- > *i
22. k:Vertices(the_graph). k before j L k-the_graph- > *i
23. s1: Vertices(the_graph) List
24. s2: Vertices(the_graph) List
25. A = (s1 @ [j / s2])
26. (j s1)
27. s1@0,s2@0:Vertices(the_graph) List. topsortl(the_obj;L) = (s2@0 @ s1@0) & (j@0:Vertices(the_graph). ((j@0 s1@0) s1 @ [j]-the_graph- > *j@0) & ((j@0 s2@0) s2 @ B-the_graph- > *j@0 & s1 @ [j]-the_graph- > *j@0))
i before j topsortl(the_obj;L) 10 steps

About:

(47steps total) PrintForm Definitions Lemmas graph 1 3 Sections Graphs Doc

1	14. `i:` `Vertices(the_graph)` 15. `j:` `Vertices(the_graph)` 16. `A:` `Vertices(the_graph) List` 17. `B:` `Vertices(the_graph) List` 18. `L = (A @ B)` 19. `(j A)` 20. `(i B)` 21. `j-the_graph- > i` 22. `k:Vertices(the_graph). k before j L k-the_graph- > i` 23. `s1:` `Vertices(the_graph) List` 24. `s2:` `Vertices(the_graph) List` 25. `A = (s1 @ [j / s2])` 26. `(j s1)` `L = ((s1 @ [j]) @ s2 @ B)`	1 step

2	14. `i:` `Vertices(the_graph)` 15. `j:` `Vertices(the_graph)` 16. `A:` `Vertices(the_graph) List` 17. `B:` `Vertices(the_graph) List` 18. `L = (A @ B)` 19. `(j A)` 20. `(i B)` 21. `j-the_graph- > i` 22. `k:Vertices(the_graph). k before j L k-the_graph- > i` 23. `s1:` `Vertices(the_graph) List` 24. `s2:` `Vertices(the_graph) List` 25. `A = (s1 @ [j / s2])` 26. `(j s1)` 27. `s1@0,s2@0:Vertices(the_graph) List. topsortl(the_obj;L) = (s2@0 @ s1@0) & (j@0:Vertices(the_graph). ((j@0 s1@0) s1 @ [j]-the_graph- > j@0) & ((j@0 s2@0) s2 @ B-the_graph- > j@0 & s1 @ [j]-the_graph- > *j@0))` `i before j topsortl(the_obj;L)`	10 steps