src/HOL/Library/Zorn.thy
changeset 48750 a151db85a62b
parent 46980 6bc213e90401
child 51500 01fe31f05aa8
     1.1 --- a/src/HOL/Library/Zorn.thy	Thu Aug 09 22:31:04 2012 +0200
     1.2 +++ b/src/HOL/Library/Zorn.thy	Fri Aug 10 13:33:54 2012 +0200
     1.3 @@ -8,7 +8,7 @@
     1.4  header {* Zorn's Lemma *}
     1.5  
     1.6  theory Zorn
     1.7 -imports Order_Relation Main
     1.8 +imports Order_Relation
     1.9  begin
    1.10  
    1.11  (* Define globally? In Set.thy? *)
    1.12 @@ -143,7 +143,7 @@
    1.13   the subset relation!*}
    1.14  
    1.15  lemma empty_set_mem_chain: "({} :: 'a set set) \<in> chain S"
    1.16 -by (unfold chain_def chain_subset_def) auto
    1.17 +  by (unfold chain_def chain_subset_def) simp
    1.18  
    1.19  lemma super_subset_chain: "super S c \<subseteq> chain S"
    1.20    by (unfold super_def) blast
    1.21 @@ -152,13 +152,13 @@
    1.22    by (unfold maxchain_def) blast
    1.23  
    1.24  lemma mem_super_Ex: "c \<in> chain S - maxchain S ==> EX d. d \<in> super S c"
    1.25 -  by (unfold super_def maxchain_def) auto
    1.26 +  by (unfold super_def maxchain_def) simp
    1.27  
    1.28  lemma select_super:
    1.29       "c \<in> chain S - maxchain S ==> (\<some>c'. c': super S c): super S c"
    1.30    apply (erule mem_super_Ex [THEN exE])
    1.31    apply (rule someI2)
    1.32 -  apply auto
    1.33 +  apply simp+
    1.34    done
    1.35  
    1.36  lemma select_not_equals:
    1.37 @@ -286,7 +286,7 @@
    1.38      proof (simp add:Chain_def, intro allI impI, elim conjE)
    1.39        fix a b
    1.40        assume "a \<in> Field r" "?B a \<in> C" "b \<in> Field r" "?B b \<in> C"
    1.41 -      hence "?B a \<subseteq> ?B b \<or> ?B b \<subseteq> ?B a" using 2 by auto
    1.42 +      hence "?B a \<subseteq> ?B b \<or> ?B b \<subseteq> ?B a" using 2 by simp
    1.43        thus "(a, b) \<in> r \<or> (b, a) \<in> r" using `Preorder r` `a:Field r` `b:Field r`
    1.44          by (simp add:subset_Image1_Image1_iff)
    1.45      qed
    1.46 @@ -296,7 +296,7 @@
    1.47        fix a B assume aB: "B:C" "a:B"
    1.48        with 1 obtain x where "x:Field r" "B = r^-1 `` {x}" by auto
    1.49        thus "(a,u) : r" using uA aB `Preorder r`
    1.50 -        by (auto simp add: preorder_on_def refl_on_def) (metis transD)
    1.51 +        by (simp add: preorder_on_def refl_on_def) (rule transD, blast+)
    1.52      qed
    1.53      thus "EX u:Field r. ?P u" using `u:Field r` by blast
    1.54    qed
    1.55 @@ -326,8 +326,7 @@
    1.56  
    1.57  lemma trans_init_seg_of:
    1.58    "r initial_segment_of s \<Longrightarrow> s initial_segment_of t \<Longrightarrow> r initial_segment_of t"
    1.59 -by(simp (no_asm_use) add: init_seg_of_def)
    1.60 -  (metis Domain_iff UnCI Un_absorb2 subset_trans)
    1.61 +by (simp (no_asm_use) add: init_seg_of_def) (metis (no_types) in_mono order_trans)
    1.62  
    1.63  lemma antisym_init_seg_of:
    1.64    "r initial_segment_of s \<Longrightarrow> s initial_segment_of r \<Longrightarrow> r=s"
    1.65 @@ -335,20 +334,17 @@
    1.66  
    1.67  lemma Chain_init_seg_of_Union:
    1.68    "R \<in> Chain init_seg_of \<Longrightarrow> r\<in>R \<Longrightarrow> r initial_segment_of \<Union>R"
    1.69 -by(auto simp add:init_seg_of_def Chain_def Ball_def) blast
    1.70 +by(simp add: init_seg_of_def Chain_def Ball_def) blast
    1.71  
    1.72  lemma chain_subset_trans_Union:
    1.73    "chain\<^bsub>\<subseteq>\<^esub> R \<Longrightarrow> \<forall>r\<in>R. trans r \<Longrightarrow> trans(\<Union>R)"
    1.74 -apply(auto simp add:chain_subset_def)
    1.75 +apply(simp add:chain_subset_def)
    1.76  apply(simp (no_asm_use) add:trans_def)
    1.77 -apply (metis subsetD)
    1.78 -done
    1.79 +by (metis subsetD)
    1.80  
    1.81  lemma chain_subset_antisym_Union:
    1.82    "chain\<^bsub>\<subseteq>\<^esub> R \<Longrightarrow> \<forall>r\<in>R. antisym r \<Longrightarrow> antisym(\<Union>R)"
    1.83 -apply(auto simp add:chain_subset_def antisym_def)
    1.84 -apply (metis subsetD)
    1.85 -done
    1.86 +by (simp add:chain_subset_def antisym_def) (metis subsetD)
    1.87  
    1.88  lemma chain_subset_Total_Union:
    1.89  assumes "chain\<^bsub>\<subseteq>\<^esub> R" "\<forall>r\<in>R. Total r"
    1.90 @@ -403,7 +399,7 @@
    1.91  -- {*The initial segment relation on well-orders: *}
    1.92    let ?WO = "{r::('a*'a)set. Well_order r}"
    1.93    def I \<equiv> "init_seg_of \<inter> ?WO \<times> ?WO"
    1.94 -  have I_init: "I \<subseteq> init_seg_of" by(auto simp:I_def)
    1.95 +  have I_init: "I \<subseteq> init_seg_of" by(simp add: I_def)
    1.96    hence subch: "!!R. R : Chain I \<Longrightarrow> chain\<^bsub>\<subseteq>\<^esub> R"
    1.97      by(auto simp:init_seg_of_def chain_subset_def Chain_def)
    1.98    have Chain_wo: "!!R r. R \<in> Chain I \<Longrightarrow> r \<in> R \<Longrightarrow> Well_order r"
    1.99 @@ -437,7 +433,7 @@
   1.100        by(simp add: Chain_init_seg_of_Union)
   1.101      ultimately have "\<Union>R : ?WO \<and> (\<forall>r\<in>R. (r,\<Union>R) : I)"
   1.102        using mono_Chain[OF I_init] `R \<in> Chain I`
   1.103 -      by(simp (no_asm) add:I_def del:Field_Union)(metis Chain_wo subsetD)
   1.104 +      by(simp (no_asm) add:I_def del:Field_Union)(metis Chain_wo)
   1.105    }
   1.106    hence 1: "\<forall>R \<in> Chain I. \<exists>u\<in>Field I. \<forall>r\<in>R. (r,u) : I" by (subst FI) blast
   1.107  --{*Zorn's Lemma yields a maximal well-order m:*}
   1.108 @@ -475,7 +471,7 @@
   1.109      moreover have "wf(?m-Id)"
   1.110      proof-
   1.111        have "wf ?s" using `x \<notin> Field m`
   1.112 -        by(auto simp add:wf_eq_minimal Field_def Domain_unfold Domain_converse [symmetric]) metis
   1.113 +        by(simp add:wf_eq_minimal Field_def Domain_unfold Domain_converse [symmetric]) metis
   1.114        thus ?thesis using `wf(m-Id)` `x \<notin> Field m`
   1.115          wf_subset[OF `wf ?s` Diff_subset]
   1.116          by (fastforce intro!: wf_Un simp add: Un_Diff Field_def)