src/HOL/BNF_Wellorder_Embedding.thy
changeset 61799 4cf66f21b764
parent 60758 d8d85a8172b5
child 63092 a949b2a5f51d
equal deleted inserted replaced
61798:27f3c10b0b50 61799:4cf66f21b764
    58 subsection \<open>(Well-order) embeddings, strict embeddings, isomorphisms and order-compatible
    58 subsection \<open>(Well-order) embeddings, strict embeddings, isomorphisms and order-compatible
    59 functions\<close>
    59 functions\<close>
    60 
    60 
    61 text\<open>Standardly, a function is an embedding of a well-order in another if it injectively and
    61 text\<open>Standardly, a function is an embedding of a well-order in another if it injectively and
    62 order-compatibly maps the former into an order filter of the latter.
    62 order-compatibly maps the former into an order filter of the latter.
    63 Here we opt for a more succinct definition (operator @{text "embed"}),
    63 Here we opt for a more succinct definition (operator \<open>embed\<close>),
    64 asking that, for any element in the source, the function should be a bijection
    64 asking that, for any element in the source, the function should be a bijection
    65 between the set of strict lower bounds of that element
    65 between the set of strict lower bounds of that element
    66 and the set of strict lower bounds of its image.  (Later we prove equivalence with
    66 and the set of strict lower bounds of its image.  (Later we prove equivalence with
    67 the standard definition -- lemma @{text "embed_iff_compat_inj_on_ofilter"}.)
    67 the standard definition -- lemma \<open>embed_iff_compat_inj_on_ofilter\<close>.)
    68 A {\em strict embedding} (operator @{text "embedS"})  is a non-bijective embedding
    68 A {\em strict embedding} (operator \<open>embedS\<close>)  is a non-bijective embedding
    69 and an isomorphism (operator @{text "iso"}) is a bijective embedding.\<close>
    69 and an isomorphism (operator \<open>iso\<close>) is a bijective embedding.\<close>
    70 
    70 
    71 definition embed :: "'a rel \<Rightarrow> 'a' rel \<Rightarrow> ('a \<Rightarrow> 'a') \<Rightarrow> bool"
    71 definition embed :: "'a rel \<Rightarrow> 'a' rel \<Rightarrow> ('a \<Rightarrow> 'a') \<Rightarrow> bool"
    72 where
    72 where
    73 "embed r r' f \<equiv> \<forall>a \<in> Field r. bij_betw f (under r a) (under r' (f a))"
    73 "embed r r' f \<equiv> \<forall>a \<in> Field r. bij_betw f (under r a) (under r' (f a))"
    74 
    74 
   149         EMB: "iso r r' f" and EMB': "iso r' r'' f'"
   149         EMB: "iso r r' f" and EMB': "iso r' r'' f'"
   150 shows "iso r r'' (f' o f)"
   150 shows "iso r r'' (f' o f)"
   151 using assms unfolding iso_def
   151 using assms unfolding iso_def
   152 by (auto simp add: comp_embed bij_betw_trans)
   152 by (auto simp add: comp_embed bij_betw_trans)
   153 
   153 
   154 text\<open>That @{text "embedS"} is also preserved by function composition shall be proved only later.\<close>
   154 text\<open>That \<open>embedS\<close> is also preserved by function composition shall be proved only later.\<close>
   155 
   155 
   156 lemma embed_Field:
   156 lemma embed_Field:
   157 "\<lbrakk>Well_order r; embed r r' f\<rbrakk> \<Longrightarrow> f`(Field r) \<le> Field r'"
   157 "\<lbrakk>Well_order r; embed r r' f\<rbrakk> \<Longrightarrow> f`(Field r) \<le> Field r'"
   158 by (auto simp add: embed_in_Field)
   158 by (auto simp add: embed_in_Field)
   159 
   159 
   452 
   452 
   453 
   453 
   454 subsection \<open>Given any two well-orders, one can be embedded in the other\<close>
   454 subsection \<open>Given any two well-orders, one can be embedded in the other\<close>
   455 
   455 
   456 text\<open>Here is an overview of the proof of of this fact, stated in theorem
   456 text\<open>Here is an overview of the proof of of this fact, stated in theorem
   457 @{text "wellorders_totally_ordered"}:
   457 \<open>wellorders_totally_ordered\<close>:
   458 
   458 
   459    Fix the well-orders @{text "r::'a rel"} and @{text "r'::'a' rel"}.
   459    Fix the well-orders \<open>r::'a rel\<close> and \<open>r'::'a' rel\<close>.
   460    Attempt to define an embedding @{text "f::'a \<Rightarrow> 'a'"} from @{text "r"} to @{text "r'"} in the
   460    Attempt to define an embedding \<open>f::'a \<Rightarrow> 'a'\<close> from \<open>r\<close> to \<open>r'\<close> in the
   461    natural way by well-order recursion ("hoping" that @{text "Field r"} turns out to be smaller
   461    natural way by well-order recursion ("hoping" that \<open>Field r\<close> turns out to be smaller
   462    than @{text "Field r'"}), but also record, at the recursive step, in a function
   462    than \<open>Field r'\<close>), but also record, at the recursive step, in a function
   463    @{text "g::'a \<Rightarrow> bool"}, the extra information of whether @{text "Field r'"}
   463    \<open>g::'a \<Rightarrow> bool\<close>, the extra information of whether \<open>Field r'\<close>
   464    gets exhausted or not.
   464    gets exhausted or not.
   465 
   465 
   466    If @{text "Field r'"} does not get exhausted, then @{text "Field r"} is indeed smaller
   466    If \<open>Field r'\<close> does not get exhausted, then \<open>Field r\<close> is indeed smaller
   467    and @{text "f"} is the desired embedding from @{text "r"} to @{text "r'"}
   467    and \<open>f\<close> is the desired embedding from \<open>r\<close> to \<open>r'\<close>
   468    (lemma @{text "wellorders_totally_ordered_aux"}).
   468    (lemma \<open>wellorders_totally_ordered_aux\<close>).
   469 
   469 
   470    Otherwise, it means that @{text "Field r'"} is the smaller one, and the inverse of
   470    Otherwise, it means that \<open>Field r'\<close> is the smaller one, and the inverse of
   471    (the "good" segment of) @{text "f"} is the desired embedding from @{text "r'"} to @{text "r"}
   471    (the "good" segment of) \<open>f\<close> is the desired embedding from \<open>r'\<close> to \<open>r\<close>
   472    (lemma @{text "wellorders_totally_ordered_aux2"}).
   472    (lemma \<open>wellorders_totally_ordered_aux2\<close>).
   473 \<close>
   473 \<close>
   474 
   474 
   475 lemma wellorders_totally_ordered_aux:
   475 lemma wellorders_totally_ordered_aux:
   476 fixes r ::"'a rel"  and r'::"'a' rel" and
   476 fixes r ::"'a rel"  and r'::"'a' rel" and
   477       f :: "'a \<Rightarrow> 'a'" and a::'a
   477       f :: "'a \<Rightarrow> 'a'" and a::'a