5 |
5 |
6 header {* Zorn's Lemma *}; |
6 header {* Zorn's Lemma *}; |
7 |
7 |
8 theory ZornLemma = Aux + Zorn:; |
8 theory ZornLemma = Aux + Zorn:; |
9 |
9 |
10 text{* |
10 text {* Zorn's Lemmas states: if every linear ordered subset of an |
11 Zorn's Lemmas states: if every linear ordered subset of an ordered set |
11 ordered set $S$ has an upper bound in $S$, then there exists a maximal |
12 $S$ has an upper bound in $S$, then there exists a maximal element in $S$. |
12 element in $S$. In our application, $S$ is a set of sets ordered by |
13 In our application, $S$ is a set of sets ordered by set inclusion. Since |
13 set inclusion. Since the union of a chain of sets is an upper bound |
14 the union of a chain of sets is an upper bound for all elements of the |
14 for all elements of the chain, the conditions of Zorn's lemma can be |
15 chain, the conditions of Zorn's lemma can be modified: |
15 modified: if $S$ is non-empty, it suffices to show that for every |
16 if $S$ is non-empty, it suffices to show that for every non-empty |
16 non-empty chain $c$ in $S$ the union of $c$ also lies in $S$. *}; |
17 chain $c$ in $S$ the union of $c$ also lies in $S$. |
|
18 *}; |
|
19 |
17 |
20 theorem Zorn's_Lemma: |
18 theorem Zorn's_Lemma: |
21 "a:S ==> (!!c. c: chain S ==> EX x. x:c ==> Union c : S) |
19 "(!!c. c: chain S ==> EX x. x:c ==> Union c : S) ==> a:S |
22 ==> EX y: S. ALL z: S. y <= z --> y = z"; |
20 ==> EX y: S. ALL z: S. y <= z --> y = z"; |
23 proof (rule Zorn_Lemma2); |
21 proof (rule Zorn_Lemma2); |
24 txt_raw{* \footnote{See |
22 txt_raw {* \footnote{See |
25 \url{http://isabelle.in.tum.de/library/HOL/HOL-Real/Zorn.html}}*}; |
23 \url{http://isabelle.in.tum.de/library/HOL/HOL-Real/Zorn.html}}*}; |
|
24 assume r: "!!c. c: chain S ==> EX x. x:c ==> Union c : S"; |
26 assume aS: "a:S"; |
25 assume aS: "a:S"; |
27 assume r: "!!c. c: chain S ==> EX x. x:c ==> Union c : S"; |
|
28 show "ALL c:chain S. EX y:S. ALL z:c. z <= y"; |
26 show "ALL c:chain S. EX y:S. ALL z:c. z <= y"; |
29 proof; |
27 proof; |
30 fix c; assume "c:chain S"; |
28 fix c; assume "c:chain S"; |
31 show "EX y:S. ALL z:c. z <= y"; |
29 show "EX y:S. ALL z:c. z <= y"; |
32 proof (rule case_split); |
30 proof (rule case_split); |