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

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

At: topsortl-properties 1 2 2 2 2 2 1 2 2

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)
14. 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)
15. i: Vertices(the_graph)
16. j: Vertices(the_graph)
17. k: Vertices(the_graph)
18. k-the_graph- > *j
19. k-the_graph- > *i
20. k':Vertices(the_graph). k' before k L k'-the_graph- > *i
21. i before k topsortl(the_obj;L)
22. Dec(k = j)

i before j topsortl(the_obj;L)

By: Analyze -1 THEN Try (RevHypSubst -1 0) THEN Using [`y',k] (BackThru Thm* l:T List, x,y,z:T. no_repeats(T;l) x before y l y before z l x before z l) THEN Try ((BackThru 13) THEN (ParallelOp -1))

Generated subgoal:

1 22. k = j
no_repeats(Vertices(the_graph);topsortl(the_obj;L)) 1 step

About:

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