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 |