src/HOL/Real/HahnBanach/ZornLemma.thy
changeset 8104 d9b3a224c0e6
parent 7978 1b99ee57d131
child 8272 1329173b56ed
equal deleted inserted replaced
8103:86f94a8116a9 8104:d9b3a224c0e6
     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);