src/HOL/Hahn_Banach/Zorn_Lemma.thy
changeset 61539 a29295dac1ca
parent 58889 5b7a9633cfa8
child 61879 e4f9d8f094fe
equal deleted inserted replaced
61538:bf4969660913 61539:a29295dac1ca
     8 imports Main
     8 imports Main
     9 begin
     9 begin
    10 
    10 
    11 text \<open>
    11 text \<open>
    12   Zorn's Lemmas states: if every linear ordered subset of an ordered
    12   Zorn's Lemmas states: if every linear ordered subset of an ordered
    13   set @{text S} has an upper bound in @{text S}, then there exists a
    13   set \<open>S\<close> has an upper bound in \<open>S\<close>, then there exists a
    14   maximal element in @{text S}.  In our application, @{text S} is a
    14   maximal element in \<open>S\<close>.  In our application, \<open>S\<close> is a
    15   set of sets ordered by set inclusion. Since the union of a chain of
    15   set of sets ordered by set inclusion. Since the union of a chain of
    16   sets is an upper bound for all elements of the chain, the conditions
    16   sets is an upper bound for all elements of the chain, the conditions
    17   of Zorn's lemma can be modified: if @{text S} is non-empty, it
    17   of Zorn's lemma can be modified: if \<open>S\<close> is non-empty, it
    18   suffices to show that for every non-empty chain @{text c} in @{text
    18   suffices to show that for every non-empty chain \<open>c\<close> in \<open>S\<close> the union of \<open>c\<close> also lies in \<open>S\<close>.
    19   S} the union of @{text c} also lies in @{text S}.
       
    20 \<close>
    19 \<close>
    21 
    20 
    22 theorem Zorn's_Lemma:
    21 theorem Zorn's_Lemma:
    23   assumes r: "\<And>c. c \<in> chains S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S"
    22   assumes r: "\<And>c. c \<in> chains S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S"
    24     and aS: "a \<in> S"
    23     and aS: "a \<in> S"
    28   proof
    27   proof
    29     fix c assume "c \<in> chains S"
    28     fix c assume "c \<in> chains S"
    30     show "\<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y"
    29     show "\<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y"
    31     proof cases
    30     proof cases
    32 
    31 
    33       txt \<open>If @{text c} is an empty chain, then every element in
    32       txt \<open>If \<open>c\<close> is an empty chain, then every element in
    34         @{text S} is an upper bound of @{text c}.\<close>
    33         \<open>S\<close> is an upper bound of \<open>c\<close>.\<close>
    35 
    34 
    36       assume "c = {}"
    35       assume "c = {}"
    37       with aS show ?thesis by fast
    36       with aS show ?thesis by fast
    38 
    37 
    39       txt \<open>If @{text c} is non-empty, then @{text "\<Union>c"} is an upper
    38       txt \<open>If \<open>c\<close> is non-empty, then \<open>\<Union>c\<close> is an upper
    40         bound of @{text c}, lying in @{text S}.\<close>
    39         bound of \<open>c\<close>, lying in \<open>S\<close>.\<close>
    41 
    40 
    42     next
    41     next
    43       assume "c \<noteq> {}"
    42       assume "c \<noteq> {}"
    44       show ?thesis
    43       show ?thesis
    45       proof
    44       proof