src/HOL/Library/Zorn.thy
changeset 46008 c296c75f4cf4
parent 44890 22f665a2e91c
child 46752 e9e7209eb375
equal deleted inserted replaced
46007:493d9c4d7ed5 46008:c296c75f4cf4
    56 text{*This is theorem @{text increasingD2} of ZF/Zorn.thy*}
    56 text{*This is theorem @{text increasingD2} of ZF/Zorn.thy*}
    57 
    57 
    58 lemma Abrial_axiom1: "x \<subseteq> succ S x"
    58 lemma Abrial_axiom1: "x \<subseteq> succ S x"
    59   apply (auto simp add: succ_def super_def maxchain_def)
    59   apply (auto simp add: succ_def super_def maxchain_def)
    60   apply (rule contrapos_np, assumption)
    60   apply (rule contrapos_np, assumption)
    61   apply (rule_tac Q="\<lambda>S. xa \<in> S" in someI2, blast+)
    61   apply (rule someI2)
       
    62   apply blast+
    62   done
    63   done
    63 
    64 
    64 lemmas TFin_UnionI = TFin.Pow_UnionI [OF PowI]
    65 lemmas TFin_UnionI = TFin.Pow_UnionI [OF PowI]
    65 
    66 
    66 lemma TFin_induct:
    67 lemma TFin_induct:
    67   assumes H: "n \<in> TFin S"
    68   assumes H: "n \<in> TFin S" and
    68   and I: "!!x. x \<in> TFin S ==> P x ==> P (succ S x)"
    69     I: "!!x. x \<in> TFin S ==> P x ==> P (succ S x)"
    69     "!!Y. Y \<subseteq> TFin S ==> Ball Y P ==> P(Union Y)"
    70       "!!Y. Y \<subseteq> TFin S ==> Ball Y P ==> P (Union Y)"
    70   shows "P n" using H
    71   shows "P n"
    71   apply (induct rule: TFin.induct [where P=P])
    72   using H by induct (blast intro: I)+
    72    apply (blast intro: I)+
       
    73   done
       
    74 
    73 
    75 lemma succ_trans: "x \<subseteq> y ==> x \<subseteq> succ S y"
    74 lemma succ_trans: "x \<subseteq> y ==> x \<subseteq> succ S y"
    76   apply (erule subset_trans)
    75   apply (erule subset_trans)
    77   apply (rule Abrial_axiom1)
    76   apply (rule Abrial_axiom1)
    78   done
    77   done
   158   by (unfold super_def maxchain_def) auto
   157   by (unfold super_def maxchain_def) auto
   159 
   158 
   160 lemma select_super:
   159 lemma select_super:
   161      "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c): super S c"
   160      "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c): super S c"
   162   apply (erule mem_super_Ex [THEN exE])
   161   apply (erule mem_super_Ex [THEN exE])
   163   apply (rule someI2 [where Q="%X. X : super S c"], auto)
   162   apply (rule someI2)
       
   163   apply auto
   164   done
   164   done
   165 
   165 
   166 lemma select_not_equals:
   166 lemma select_not_equals:
   167      "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c) \<noteq> c"
   167      "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c) \<noteq> c"
   168   apply (rule notI)
   168   apply (rule notI)
   183   apply (erule TFin_induct)
   183   apply (erule TFin_induct)
   184    apply (simp add: succ_def select_super [THEN super_subset_chain[THEN subsetD]])
   184    apply (simp add: succ_def select_super [THEN super_subset_chain[THEN subsetD]])
   185   apply (unfold chain_def chain_subset_def)
   185   apply (unfold chain_def chain_subset_def)
   186   apply (rule CollectI, safe)
   186   apply (rule CollectI, safe)
   187    apply (drule bspec, assumption)
   187    apply (drule bspec, assumption)
   188    apply (rule_tac [2] m1 = Xa and n1 = X in TFin_subset_linear [THEN disjE],
   188    apply (rule_tac [2] m1 = Xa and n1 = X in TFin_subset_linear [THEN disjE])
   189      best+)
   189       apply blast+
   190   done
   190   done
   191 
   191 
   192 theorem Hausdorff: "\<exists>c. (c :: 'a set set): maxchain S"
   192 theorem Hausdorff: "\<exists>c. (c :: 'a set set): maxchain S"
   193   apply (rule_tac x = "Union (TFin S)" in exI)
   193   apply (rule_tac x = "Union (TFin S)" in exI)
   194   apply (rule classical)
   194   apply (rule classical)