12 theorems [dest] = monoD; (* FIXME [dest!!] *) |
12 theorems [dest] = monoD; (* FIXME [dest!!] *) |
13 |
13 |
14 (* |
14 (* |
15 The proof of Knaster-Tarski below closely follows the presentation in |
15 The proof of Knaster-Tarski below closely follows the presentation in |
16 'Introduction to Lattices' and Order by Davey/Priestley, pages |
16 'Introduction to Lattices' and Order by Davey/Priestley, pages |
17 93--94. Only one statement of their narration has not been rephrased |
17 93--94. All of their narration has been rephrased in terms of formal |
18 in formal Isar language elements, but left as a comment. Also note |
18 Isar language elements, except one stament only that has been left as |
19 that Davey/Priestley do not point out non-emptyness of the set ??H, |
19 a comment. Also note that Davey/Priestley do not point out |
20 (which is obvious, but not vacous). |
20 non-emptyness of the set @term{??H}, (which is obvious, but not |
|
21 vacous). |
|
22 |
|
23 Just as many textbook-style proofs, there is a strong bias towards |
|
24 forward reasoning, with little hierarchical structure. |
21 *) |
25 *) |
22 |
26 |
23 theorem KnasterTarski: "mono f ==> EX a::'a set. f a = a"; |
27 theorem KnasterTarski: "mono f ==> EX a::'a set. f a = a"; |
24 proof; |
28 proof; |
|
29 assume mono: "mono f"; |
|
30 |
25 let ??H = "{u. f u <= u}"; |
31 let ??H = "{u. f u <= u}"; |
26 let ??a = "Inter ??H"; |
32 let ??a = "Inter ??H"; |
27 |
33 |
28 assume mono: "mono f"; |
34 have "f UNIV <= UNIV"; by (rule subset_UNIV); |
29 show "f ??a = ??a"; |
35 hence "UNIV : ??H"; ..; |
|
36 thus "f ??a = ??a"; |
30 proof same; |
37 proof same; |
31 fix x; |
38 fix x; |
32 presume mem: "x : ??H"; |
39 assume mem: "x : ??H"; |
33 hence "??a <= x"; by (rule Inter_lower); |
40 hence "??a <= x"; by (rule Inter_lower); |
34 with mono; have "f ??a <= f x"; ..; |
41 with mono; have "f ??a <= f x"; ..; |
35 also; from mem; have "f x <= x"; ..; |
42 also; from mem; have "... <= x"; ..; |
36 finally (order_trans); have "f ??a <= x"; .; |
43 finally (order_trans); have "f ??a <= x"; .; |
37 hence ge: "f ??a <= ??a"; by (rule Inter_greatest); |
44 hence ge: "f ??a <= ??a"; by (rule Inter_greatest); |
38 (* text {* We now use this inequality to prove the reverse one (!) |
45 txt {* We now use this inequality to prove the reverse one (!) |
39 and thereby complete the proof that @term{??a} is a fixpoint. *}; *) |
46 and thereby complete the proof that @term{??a} is a fixpoint. *}; |
40 with mono; have "f (f ??a) <= f ??a"; ..; |
47 with mono; have "f (f ??a) <= f ??a"; ..; |
41 hence "f ??a : ??H"; ..; |
48 hence "f ??a : ??H"; ..; |
42 hence "??a <= f ??a"; by (rule Inter_lower); |
49 hence "??a <= f ??a"; by (rule Inter_lower); |
43 also; note ge; |
50 also; note ge; |
44 finally; show "f ??a = ??a"; by (rule sym); |
51 finally (order_antisym); show "f ??a = ??a"; by (rule sym); |
45 next; |
|
46 have "f UNIV <= UNIV"; by (rule subset_UNIV); |
|
47 thus "UNIV : ??H"; ..; |
|
48 qed; |
52 qed; |
49 qed; |
53 qed; |
50 |
54 |
51 |
55 |
52 end; |
56 end; |