Theory func_ZF_1

theory func_ZF_1
imports Order Order_ZF_1a func_ZF
(* 
    This file is a part of IsarMathLib - 
    a library of formalized mathematics for Isabelle/Isar.

    Copyright (C) 2008  Slawomir Kolodynski

    This program is free software; Redistribution and use in source and binary forms, 
    with or without modification, are permitted provided that the following conditions are met:

   1. Redistributions of source code must retain the above copyright notice, 
   this list of conditions and the following disclaimer.
   2. Redistributions in binary form must reproduce the above copyright notice, 
   this list of conditions and the following disclaimer in the documentation and/or 
   other materials provided with the distribution.
   3. The name of the author may not be used to endorse or promote products 
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 
IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 
OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 
OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 
EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.*)

header{*\isaheader{func\_ZF\_1.thy}*}

theory func_ZF_1 imports Order Order_ZF_1a func_ZF

begin  

text{*In this theory we consider 
  some properties of functions related to order relations *}

section{*Functions and order*}

text{*This section deals with functions between ordered sets.*}

text{*If every value of a function on a set is bounded below by
  a constant, then the image of the set is bounded below.*}

lemma func_ZF_8_L1: 
  assumes "f:X->Y" and "A⊆X" and "∀x∈A. ⟨L,f`(x)⟩ ∈ r"
  shows "IsBoundedBelow(f``(A),r)"
proof -
  from assms have "∀y ∈ f``(A). ⟨L,y⟩ ∈ r"
    using func_imagedef by simp
  then show "IsBoundedBelow(f``(A),r)" 
    by (rule Order_ZF_3_L9)
qed

text{*If every value of a function on a set is bounded above by
  a constant, then the image of the set is bounded above.*}

lemma func_ZF_8_L2:  
  assumes "f:X->Y" and "A⊆X" and "∀x∈A. ⟨f`(x),U⟩ ∈ r"
  shows "IsBoundedAbove(f``(A),r)"
proof -
  from assms have "∀y ∈ f``(A). ⟨y,U⟩ ∈ r"
    using func_imagedef by simp
  then show "IsBoundedAbove(f``(A),r)" 
    by (rule Order_ZF_3_L10)
qed

text{*Identity is an order isomorphism.*}

lemma id_ord_iso: shows "id(X) ∈ ord_iso(X,r,X,r)"
  using id_bij id_def ord_iso_def by simp

text{*Identity is the only order automorphism 
  of a singleton.*}

lemma id_ord_auto_singleton: 
  shows "ord_iso({x},r,{x},r) = {id({x})}"
  using id_ord_iso ord_iso_def single_bij_id
  by auto 
      
text{*The image of a maximum by an order isomorphism
  is a maximum. Note that from the fact the $r$ is 
  antisymmetric and $f$ is an order isomorphism between
  $(A,r)$ and $(B,R)$ we can not conclude that $R$ is
  antisymmetric (we can only show that $R\cap (B\times B)$ is).
  *}

lemma max_image_ord_iso: 
  assumes A1: "antisym(r)" and A2: "antisym(R)" and 
  A3: "f ∈ ord_iso(A,r,B,R)" and
  A4: "HasAmaximum(r,A)"
  shows "HasAmaximum(R,B)" and "Maximum(R,B) = f`(Maximum(r,A))"
proof -
  let ?M = "Maximum(r,A)"
  from A1 A4 have "?M ∈ A" using Order_ZF_4_L3 by simp
  from A3 have "f:A->B" using ord_iso_def bij_is_fun
    by simp
  with `?M ∈ A` have I: "f`(?M) ∈ B"
    using apply_funtype by simp
  { fix y assume "y ∈ B"
    let ?x = "converse(f)`(y)" 
    from A3 have "converse(f) ∈ ord_iso(B,R,A,r)"
      using ord_iso_sym by simp
    then have "converse(f): B -> A"
      using ord_iso_def bij_is_fun by simp
    with `y ∈ B` have "?x ∈ A"
      by simp
    with A1 A3 A4 `?x ∈ A` `?M ∈ A` have "⟨f`(?x), f`(?M)⟩ ∈ R"
      using Order_ZF_4_L3 ord_iso_apply by simp
    with A3 `y ∈ B` have "⟨y, f`(?M)⟩ ∈ R"
      using right_inverse_bij ord_iso_def by auto
  } then have II: "∀y ∈ B. ⟨y, f`(?M)⟩ ∈ R" by simp
  with A2 I show "Maximum(R,B) = f`(?M)"
    by (rule Order_ZF_4_L14)
  from I II show "HasAmaximum(R,B)"
    using HasAmaximum_def by auto
qed

text{*Maximum is a fixpoint of order automorphism.*}

lemma max_auto_fixpoint: 
  assumes "antisym(r)" and "f ∈ ord_iso(A,r,A,r)"
  and "HasAmaximum(r,A)"
  shows "Maximum(r,A) = f`(Maximum(r,A))"
  using assms max_image_ord_iso by blast      

text{*If two sets are order isomorphic and 
  we remove $x$ and $f(x)$, respectively, from the sets, 
  then they are still order isomorphic.*}

lemma ord_iso_rem_point: 
  assumes A1: "f ∈ ord_iso(A,r,B,R)" and A2: "a ∈ A"
  shows "restrict(f,A-{a}) ∈ ord_iso(A-{a},r,B-{f`(a)},R)"
proof -
  let ?f0 = "restrict(f,A-{a})"
  have "A-{a} ⊆ A" by auto
  with A1 have "?f0 ∈ ord_iso(A-{a},r,f``(A-{a}),R)"
    using ord_iso_restrict_image by simp
  moreover 
  from A1 have "f ∈ inj(A,B)" 
    using ord_iso_def bij_def by simp
  with A2  have "f``(A-{a}) = f``(A) - f``{a}"
    using inj_image_dif by simp
  moreover from A1 have "f``(A) = B" 
    using ord_iso_def bij_def surj_range_image_domain 
    by auto
  moreover 
  from A1 have "f: A->B"
    using ord_iso_def bij_is_fun by simp
  with A2 have "f``{a} = {f`(a)}"
    using singleton_image by simp
  ultimately show ?thesis by simp
qed
  
text{*If two sets are order isomorphic and 
  we remove maxima from the sets, then they are still
  order isomorphic. *}

corollary ord_iso_rem_max: 
  assumes A1: "antisym(r)" and "f ∈ ord_iso(A,r,B,R)" and
  A4: "HasAmaximum(r,A)" and  A5: "M = Maximum(r,A)"
  shows "restrict(f,A-{M}) ∈ ord_iso(A-{M}, r, B-{f`(M)},R)"
  using assms Order_ZF_4_L3 ord_iso_rem_point by simp


text{*Lemma about extending order isomorphisms by adding one point
  to the domain.*}

lemma ord_iso_extend:  assumes A1: "f ∈ ord_iso(A,r,B,R)" and
  A2: "MA ∉ A" "MB ∉ B" and
  A3: "∀a∈A. ⟨a, MA⟩ ∈ r"  "∀b∈B. ⟨b, MB⟩ ∈ R" and
  A4: "antisym(r)"  "antisym(R)" and
  A5: "⟨MA,MA⟩ ∈ r <-> ⟨MB,MB⟩ ∈ R"  
  shows "f ∪ {⟨ MA,MB⟩} ∈ ord_iso(A∪{MA} ,r,B∪{MB} ,R)"
proof -
  let ?g = "f ∪ {⟨ MA,MB⟩}"
  from A1 A2 have
    "?g : A∪{MA} -> B∪{MB}" and
    I: "∀x∈A. ?g`(x) = f`(x)" and II: "?g`(MA) = MB"
    using ord_iso_def bij_def inj_def func1_1_L11D
    by auto
  from A1 A2 have "?g ∈ bij(A∪{MA},B∪{MB}) "
    using ord_iso_def bij_extend_point by simp
  moreover have "∀x ∈ A∪{MA}. ∀ y ∈ A∪{MA}.
    ⟨x,y⟩ ∈ r <-> ⟨?g`(x), ?g`(y)⟩ ∈ R"
  proof -
    { fix x y
      assume "x ∈ A∪{MA}" and "y ∈ A∪{MA}"
      then have "x∈A ∧ y ∈ A ∨ x∈A ∧ y = MA ∨
	x = MA ∧ y ∈ A ∨ x = MA ∧ y = MA"
	by auto
      moreover
      { assume "x∈A ∧ y ∈ A"
	with A1 I have "⟨x,y⟩ ∈ r <-> ⟨?g`(x), ?g`(y)⟩ ∈ R" 
	  using ord_iso_def by simp }
      moreover
      { assume "x∈A ∧ y = MA"
	with A1 A3 I II have "⟨x,y⟩ ∈ r <-> ⟨?g`(x), ?g`(y)⟩ ∈ R" 
	  using ord_iso_def bij_def inj_def apply_funtype
	  by auto }
      moreover
      { assume "x = MA ∧ y ∈ A"
	with A2 A3 A4 have "⟨x,y⟩ ∉ r"
	  using antisym_def by auto
	moreover
	{ assume A6: "⟨?g`(x), ?g`(y)⟩ ∈ R"
	  from A1 I II `x = MA ∧ y ∈ A` have 
	    III: "?g`(y) ∈ B"  "?g`(x) = MB"
	    using ord_iso_def bij_def inj_def apply_funtype
	    by auto
	  with A3 have "⟨?g`(y), ?g`(x)⟩ ∈ R" by simp
	  with A4 A6 have "?g`(y) = ?g`(x)" using antisym_def
	    by auto
	  with A2 III have False by simp
	} hence "⟨?g`(x), ?g`(y)⟩ ∉ R" by auto
	ultimately have "⟨x,y⟩ ∈ r <-> ⟨?g`(x), ?g`(y)⟩ ∈ R" 
	by simp }
      moreover
      { assume "x = MA ∧ y = MA"
	with A5 II have "⟨x,y⟩ ∈ r <-> ⟨?g`(x), ?g`(y)⟩ ∈ R" 
	  by simp }
      ultimately have "⟨x,y⟩ ∈ r <-> ⟨?g`(x), ?g`(y)⟩ ∈ R" 
	by auto
    } thus ?thesis by auto
  qed 
  ultimately show ?thesis using ord_iso_def
    by simp
qed

text{*A kind of converse to @{text "ord_iso_rem_max"}: if two
  linearly ordered sets sets are order isomorphic 
  after removing the maxima, then they are order isomorphic.*}

lemma rem_max_ord_iso: 
  assumes A1: "IsLinOrder(X,r)"  "IsLinOrder(Y,R)" and 
  A2: "HasAmaximum(r,X)"  "HasAmaximum(R,Y)"
  "ord_iso(X - {Maximum(r,X)},r,Y - {Maximum(R,Y)},R) ≠ 0"
  shows "ord_iso(X,r,Y,R) ≠ 0"
proof -
  let ?MA = "Maximum(r,X)"
  let ?A = "X - {?MA}"
  let ?MB = "Maximum(R,Y)"
  let ?B = "Y - {?MB}"
  from A2 obtain f where "f ∈ ord_iso(?A,r,?B,R)"
    by auto
  moreover have "?MA ∉ ?A" and "?MB ∉ ?B"
    by auto
  moreover from A1 A2 have 
    "∀a∈?A. ⟨a,?MA⟩ ∈ r" and "∀b∈?B. ⟨b,?MB⟩ ∈ R"
    using IsLinOrder_def Order_ZF_4_L3 by auto
  moreover from A1 have "antisym(r)" and "antisym(R)"
    using IsLinOrder_def by auto
  moreover from A1 A2 have "⟨?MA,?MA⟩ ∈ r <-> ⟨?MB,?MB⟩ ∈ R"
    using IsLinOrder_def Order_ZF_4_L3 IsLinOrder_def 
      total_is_refl refl_def by auto
  ultimately have 
    "f ∪ {⟨ ?MA,?MB⟩} ∈ ord_iso(?A∪{?MA} ,r,?B∪{?MB} ,R)"
    by (rule ord_iso_extend)
  moreover from A1 A2 have 
    "?A∪{?MA} = X" and "?B∪{?MB} = Y"
  using IsLinOrder_def Order_ZF_4_L3 by auto
  ultimately show "ord_iso(X,r,Y,R) ≠ 0"
    using ord_iso_extend by auto
qed
  
section{*Projections in cartesian products*}

text{*In this section we consider maps arising naturally
  in cartesian products. *}

text{*There is a natural bijection etween $X=Y\times \{ y\}$ (a "slice")
  and $Y$. 
  We will call this the @{text "SliceProjection(Y×{y})"}. 
  This is really the ZF equivalent of the meta-function @{text "fst(x)"}.
  *}

definition
  "SliceProjection(X) ≡ {⟨p,fst(p)⟩. p ∈ X }"

text{*A slice projection is a bijection between $X\times\{ y\}$ and $X$.*}

lemma slice_proj_bij: shows 
  "SliceProjection(X×{y}): X×{y} -> X"
  "domain(SliceProjection(X×{y})) = X×{y}"
  "∀p∈X×{y}. SliceProjection(X×{y})`(p) = fst(p)"
  "SliceProjection(X×{y}) ∈ bij(X×{y},X)"
proof -
  let ?P = "SliceProjection(X×{y})"
  have  "∀p ∈ X×{y}. fst(p) ∈ X" by simp
  moreover from this have 
    "{⟨p,fst(p)⟩. p ∈ X×{y} } : X×{y} -> X"
    by (rule ZF_fun_from_total)
  ultimately show 
    I: "?P: X×{y} -> X" and II: "∀p∈X×{y}. ?P`(p) = fst(p)"
    using ZF_fun_from_tot_val SliceProjection_def by auto
  hence
    "∀a ∈ X×{y}. ∀ b ∈ X×{y}. ?P`(a) = ?P`(b) --> a=b"
    by auto
  with I have "?P ∈ inj(X×{y},X)" using inj_def 
    by simp
  moreover from II have "∀x∈X. ∃p∈X×{y}. ?P`(p) = x" 
    by simp
  with I have "?P ∈ surj(X×{y},X)" using surj_def
    by simp
  ultimately show "?P ∈ bij(X×{y},X)"
    using bij_def by simp
  from I show "domain(SliceProjection(X×{y})) = X×{y}"
    using func1_1_L1 by simp
qed
  
section{*Induced relations and order isomorphisms *}

text{*When we have two sets $X,Y$, function $f:X\rightarrow Y$ and
  a relation $R$ on $Y$ we can define a relation $r$ on $X$
  by saying that $x\ r\ y$ if and only if $f(x) \ R \ f(y)$. 
  This is especially interesting when $f$ is a bijection as all reasonable
  properties of $R$ are inherited by $r$. This section treats mostly the case
  when $R$ is an order relation and $f$ is a bijection.
  The standard Isabelle's @{text "Order"} theory 
  defines the notion of a space of order isomorphisms
  between two sets relative to a relation. We expand that material
  proving that order isomrphisms preserve interesting properties
  of the relation.*}

text{*We call the relation created by a relation on $Y$ and a mapping
  $f:X\rightarrow Y$ the @{text "InducedRelation(f,R)"}.*}

definition
  "InducedRelation(f,R) ≡ 
  {p ∈ domain(f)×domain(f). ⟨f`(fst(p)),f`(snd(p))⟩ ∈ R}"

text{*A reformulation of the definition of the relation induced by
  a function.*}

lemma def_of_ind_relA: 
  assumes "⟨x,y⟩ ∈ InducedRelation(f,R)"
  shows "⟨f`(x),f`(y)⟩ ∈ R"
  using assms InducedRelation_def by simp

text{*A reformulation of the definition of the relation induced by
  a function, kind of converse of @{text "def_of_ind_relA"}.*}

lemma def_of_ind_relB: assumes "f:A->B" and 
  "x∈A"  "y∈A" and "⟨f`(x),f`(y)⟩ ∈ R"
  shows "⟨x,y⟩ ∈ InducedRelation(f,R)"
  using assms func1_1_L1 InducedRelation_def by simp

text{*A property of order isomorphisms that is missing from
  standard Isabelle's @{text "Order.thy"}.*}

lemma ord_iso_apply_conv: 
  assumes "f ∈ ord_iso(A,r,B,R)" and
  "⟨f`(x),f`(y)⟩ ∈ R" and "x∈A"  "y∈A"
  shows "⟨x,y⟩ ∈ r"
  using assms ord_iso_def by simp

text{*The next lemma tells us where the induced relation is defined*}

lemma ind_rel_domain: 
  assumes  "R ⊆ B×B" and "f:A->B"
  shows "InducedRelation(f,R) ⊆ A×A"
  using assms func1_1_L1 InducedRelation_def
  by auto

text{*A bijection is an order homomorphisms between a relation
  and the induced one.*}

lemma bij_is_ord_iso: assumes A1: "f ∈ bij(A,B)"
  shows "f ∈ ord_iso(A,InducedRelation(f,R),B,R)"
proof -
  let ?r = "InducedRelation(f,R)"
  { fix x y assume A2: "x∈A"  "y∈A"
    have "⟨x,y⟩ ∈ ?r <-> ⟨f`(x),f`(y)⟩ ∈ R" 
    proof
      assume "⟨x,y⟩ ∈ ?r" then show "⟨f`(x),f`(y)⟩ ∈ R" 
	using def_of_ind_relA by simp
    next assume "⟨f`(x),f`(y)⟩ ∈ R"
      with A1 A2 show "⟨x,y⟩ ∈ ?r"
	using bij_is_fun def_of_ind_relB by blast 
    qed }
  with A1 show "f ∈ ord_iso(A,InducedRelation(f,R),B,R)"
    using ord_isoI by simp
qed

text{*An order isomoprhism preserves antisymmetry.*}

lemma ord_iso_pres_antsym: assumes A1: "f ∈ ord_iso(A,r,B,R)" and 
  A2: "r ⊆ A×A" and A3: "antisym(R)"
  shows "antisym(r)"
proof -
  { fix x y
    assume A4: "⟨x,y⟩ ∈ r"   "⟨y,x⟩ ∈ r"
    from A1 have "f ∈ inj(A,B)"
      using ord_iso_is_bij bij_is_inj by simp
    moreover
    from A1 A2 A4 have 
      "⟨f`(x), f`(y)⟩ ∈ R" and "⟨f`(y), f`(x)⟩ ∈ R"
      using ord_iso_apply by auto
    with A3 have "f`(x) = f`(y)" by (rule Fol1_L4)
    moreover from A2 A4 have "x∈A"  "y∈A" by auto
    ultimately have "x=y" by (rule inj_apply_equality)
  } then have "∀x y. ⟨x,y⟩ ∈ r ∧ ⟨y,x⟩ ∈ r --> x=y" by auto
  then show "antisym(r)" using imp_conj antisym_def
    by simp
qed      

text{*Order isomoprhisms preserve transitivity.*}

lemma ord_iso_pres_trans: assumes A1: "f ∈ ord_iso(A,r,B,R)" and 
  A2: "r ⊆ A×A" and A3: "trans(R)"
  shows "trans(r)"
proof -
  { fix x y z
    assume A4: "⟨x, y⟩ ∈ r"   "⟨y, z⟩ ∈ r"
    note A1
    moreover
    from A1 A2 A4 have 
      "⟨f`(x), f`(y)⟩ ∈ R ∧ ⟨f`(y), f`(z)⟩ ∈ R"
      using ord_iso_apply by auto
    with A3 have "⟨f`(x),f`(z)⟩ ∈ R" by (rule Fol1_L3)
    moreover from A2 A4 have "x∈A"  "z∈A" by auto
    ultimately have "⟨x, z⟩ ∈ r" using ord_iso_apply_conv
      by simp
  } then have  "∀ x y z. ⟨x, y⟩ ∈ r ∧ ⟨y, z⟩ ∈ r --> ⟨x, z⟩ ∈ r"
    by blast
  then show "trans(r)" by (rule Fol1_L2)
qed
     
text{*Order isomorphisms preserve totality.*}

lemma ord_iso_pres_tot: assumes A1: "f ∈ ord_iso(A,r,B,R)" and 
  A2: "r ⊆ A×A" and A3: "R  {is total on} B"
  shows "r  {is total on} A"
proof -
  { fix x y
    assume "x∈A"  "y∈A"  "⟨x,y⟩ ∉ r"  
    with A1 have "⟨f`(x),f`(y)⟩ ∉ R" using ord_iso_apply_conv
      by auto
    moreover 
    from A1 have "f:A->B" using ord_iso_is_bij bij_is_fun 
      by simp
    with A3 `x∈A`  `y∈A` have 
      "⟨f`(x),f`(y)⟩ ∈  R ∨ ⟨f`(y),f`(x)⟩ ∈  R"
      using apply_funtype IsTotal_def by simp
    ultimately have "⟨f`(y),f`(x)⟩ ∈  R" by simp
    with A1 `x∈A`  `y∈A` have "⟨y,x⟩ ∈ r" 
      using ord_iso_apply_conv  by simp
  } then have "∀x∈A. ∀y∈A. ⟨x,y⟩ ∈ r ∨  ⟨y,x⟩ ∈ r"
    by blast
  then show "r  {is total on} A" using IsTotal_def
    by simp
qed

text{*Order isomorphisms preserve linearity.*}

lemma ord_iso_pres_lin: assumes "f ∈ ord_iso(A,r,B,R)" and 
  "r ⊆ A×A" and "IsLinOrder(B,R)"
  shows "IsLinOrder(A,r)"
  using assms ord_iso_pres_antsym ord_iso_pres_trans ord_iso_pres_tot
    IsLinOrder_def by simp

text{*If a relation is a linear order, then the relation induced
  on another set by a bijection is also a linear order.*}

lemma ind_rel_pres_lin: 
  assumes A1: "f ∈ bij(A,B)" and A2: "IsLinOrder(B,R)"
  shows "IsLinOrder(A,InducedRelation(f,R))"
proof -
  let ?r = "InducedRelation(f,R)"
  from A1 have "f ∈ ord_iso(A,?r,B,R)" and "?r ⊆ A×A"
    using bij_is_ord_iso domain_of_bij InducedRelation_def 
    by auto
  with A2 show "IsLinOrder(A,?r)" using ord_iso_pres_lin 
    by simp
qed

text{*The image by an order isomorphism 
  of a bounded above and nonempty set is bounded above.*}

lemma ord_iso_pres_bound_above: 
  assumes A1: "f ∈ ord_iso(A,r,B,R)" and A2: "r ⊆ A×A" and
  A3: "IsBoundedAbove(C,r)"   "C≠0"
  shows "IsBoundedAbove(f``(C),R)"   "f``(C) ≠ 0"
proof -
  from A3 obtain u where I: "∀x∈C. ⟨x,u⟩ ∈ r"
    using IsBoundedAbove_def by auto
  from A1 have "f:A->B" using ord_iso_is_bij bij_is_fun
    by simp
  from A2 A3 have "C⊆A" using Order_ZF_3_L1A by blast
  from A3 obtain x where "x∈C" by auto
  with A2 I have "u∈A" by auto
  { fix y assume "y ∈ f``(C)"
    with `f:A->B` `C⊆A` obtain x where "x∈C" and "y = f`(x)"
      using func_imagedef by auto
    with A1 I `C⊆A`  `u∈A` have "⟨y,f`(u)⟩ ∈ R"
      using ord_iso_apply by auto
  } then have "∀y ∈ f``(C).  ⟨y,f`(u)⟩ ∈ R" by simp
  then show "IsBoundedAbove(f``(C),R)" by (rule Order_ZF_3_L10)
  from A3 `f:A->B` `C⊆A` show "f``(C) ≠ 0" using func1_1_L15A
    by simp
qed

text{*Order isomorphisms preserve the property of having a minimum.*}

lemma ord_iso_pres_has_min: 
  assumes A1: "f ∈ ord_iso(A,r,B,R)" and  A2: "r ⊆ A×A" and 
  A3: "C⊆A" and A4: "HasAminimum(R,f``(C))"
  shows "HasAminimum(r,C)"
proof -
  from A4 obtain m where 
    I: "m ∈ f``(C)" and II: "∀y ∈ f``(C). ⟨m,y⟩ ∈ R"
    using HasAminimum_def by auto
  let ?k = "converse(f)`(m)"
  from A1 have "f:A->B" using ord_iso_is_bij bij_is_fun
    by simp
  from A1 have "f ∈ inj(A,B)" using ord_iso_is_bij bij_is_inj
    by simp
  with A3 I have "?k ∈ C" and III: "f`(?k) = m" 
    using inj_inv_back_in_set by auto
  moreover
  { fix x assume A5: "x∈C"
    with A3 II `f:A->B` `?k ∈ C` III have
      "?k ∈ A"   "x∈A"  "⟨f`(?k),f`(x)⟩ ∈ R"
      using func_imagedef by auto
    with A1 have "⟨?k,x⟩ ∈ r" using ord_iso_apply_conv
      by simp
  } then have "∀x∈C.  ⟨?k,x⟩ ∈ r" by simp
  ultimately show "HasAminimum(r,C)" using HasAminimum_def by auto
qed

text{*Order isomorhisms preserve the images of relations.
  In other words taking the image of a point by a relation
  commutes with the function.*}

lemma ord_iso_pres_rel_image: 
  assumes A1: "f ∈ ord_iso(A,r,B,R)" and  
  A2: "r ⊆ A×A"  "R ⊆ B×B" and 
  A3: "a∈A"
  shows "f``(r``{a}) = R``{f`(a)}"
proof
  from A1 have "f:A->B" using ord_iso_is_bij bij_is_fun
    by simp
  moreover from A2 A3 have I: "r``{a} ⊆ A" by auto
  ultimately have I: "f``(r``{a}) = {f`(x). x ∈ r``{a} }"
    using func_imagedef by simp
  { fix y assume A4: "y ∈ f``(r``{a})" 
    with I obtain x where 
      "x ∈ r``{a}" and II: "y = f`(x)"
      by auto
    with A1 A2 have "⟨f`(a),f`(x)⟩ ∈ R" using ord_iso_apply
      by auto
    with II have "y ∈  R``{f`(a)}" by auto
  } then show  "f``(r``{a}) ⊆ R``{f`(a)}" by auto
  { fix y assume A5: "y ∈ R``{f`(a)}" 
    let ?x = "converse(f)`(y)"
    from A2 A5 have 
      "⟨f`(a),y⟩ ∈ R"  "f`(a) ∈ B"  and IV: "y∈B"
      by auto
    with A1 have III: "⟨converse(f)`(f`(a)),?x⟩ ∈ r"
      using ord_iso_converse by simp
    moreover from A1 A3 have "converse(f)`(f`(a)) = a"
      using ord_iso_is_bij left_inverse_bij by blast
    ultimately have "f`(?x) ∈ {f`(x). x ∈  r``{a} }"
      by auto
    moreover from A1 IV have "f`(?x) = y"
      using ord_iso_is_bij right_inverse_bij by blast
    moreover from A1 I have "f``(r``{a}) = {f`(x). x ∈  r``{a} }"
      using ord_iso_is_bij bij_is_fun func_imagedef by blast
    ultimately have "y ∈ f``(r``{a})" by simp
  } then show "R``{f`(a)} ⊆ f``(r``{a})" by auto
qed

text{*Order isomorphisms preserve collections of upper bounds.*}

lemma ord_iso_pres_up_bounds: 
  assumes A1: "f ∈ ord_iso(A,r,B,R)" and  
  A2: "r ⊆ A×A"  "R ⊆ B×B" and 
  A3: "C⊆A" 
  shows "{f``(r``{a}). a∈C} = {R``{b}. b ∈ f``(C)}"
proof
  from A1 have "f:A->B"
      using ord_iso_is_bij bij_is_fun by simp
  { fix Y assume "Y ∈ {f``(r``{a}). a∈C}"
    then obtain a where "a∈C" and I: "Y = f``(r``{a})"
      by auto
    from A3 `a∈C` have "a∈A" by auto
    with A1 A2 have "f``(r``{a}) = R``{f`(a)}"
      using ord_iso_pres_rel_image by simp
    moreover from A3 `f:A->B` `a∈C` have "f`(a) ∈ f``(C)"
      using func_imagedef by auto
    ultimately have "f``(r``{a}) ∈ { R``{b}. b ∈ f``(C) }"
      by auto
    with I have "Y ∈ { R``{b}. b ∈ f``(C) }" by simp
  } then show "{f``(r``{a}). a∈C} ⊆ {R``{b}. b ∈ f``(C)}"
    by blast
  { fix Y assume "Y ∈ {R``{b}. b ∈ f``(C)}"
    then obtain b where "b ∈ f``(C)" and II: "Y = R``{b}"
      by auto
    with A3 `f:A->B` obtain a where "a∈C" and "b = f`(a)"
      using func_imagedef by auto
    with A3 II have "a∈A" and "Y = R``{f`(a)}" by auto 
    with A1 A2 have "Y = f``(r``{a})"
      using ord_iso_pres_rel_image by simp
    with `a∈C` have "Y ∈ {f``(r``{a}). a∈C}" by auto
  } then show "{R``{b}. b ∈ f``(C)} ⊆ {f``(r``{a}). a∈C}"
    by auto
qed
    
text{*The image of the set of upper bounds is the set of upper bounds
  of the image.*}
  
lemma ord_iso_pres_min_up_bounds: 
  assumes A1: "f ∈ ord_iso(A,r,B,R)" and  A2: "r ⊆ A×A"  "R ⊆ B×B" and 
  A3: "C⊆A" and A4: "C≠0"
  shows "f``(\<Inter>a∈C. r``{a}) = (\<Inter>b∈f``(C). R``{b})"
proof -
  from A1 have "f ∈ inj(A,B)"
    using ord_iso_is_bij bij_is_inj by simp
  moreover note A4
  moreover from A2 A3 have "∀a∈C. r``{a} ⊆ A" by auto
  ultimately have 
    "f``(\<Inter>a∈C. r``{a}) = ( \<Inter>a∈C. f``(r``{a}) )"
    using inj_image_of_Inter by simp
  also from A1 A2 A3 have
    "( \<Inter>a∈C. f``(r``{a}) ) = ( \<Inter>b∈f``(C). R``{b} )"
    using ord_iso_pres_up_bounds by simp
  finally show "f``(\<Inter>a∈C. r``{a}) = (\<Inter>b∈f``(C). R``{b})"
    by simp
qed

text{*Order isomorphisms preserve completeness.*}

lemma ord_iso_pres_compl: 
  assumes A1: "f ∈ ord_iso(A,r,B,R)" and 
  A2: "r ⊆ A×A"  "R ⊆ B×B" and A3: "R {is complete}"
  shows "r {is complete}"
proof -
  { fix C
    assume A4: "IsBoundedAbove(C,r)"  "C≠0"
    with A1 A2 A3 have 
      "HasAminimum(R,\<Inter>b ∈ f``(C). R``{b})"
      using ord_iso_pres_bound_above IsComplete_def
      by simp
    moreover
    from A2 `IsBoundedAbove(C,r)` have I: "C ⊆ A" using Order_ZF_3_L1A
      by blast
    with A1 A2 `C≠0` have "f``(\<Inter>a∈C. r``{a}) = (\<Inter>b∈f``(C). R``{b})"
      using ord_iso_pres_min_up_bounds by simp
    ultimately have "HasAminimum(R,f``(\<Inter>a∈C. r``{a}))"
      by simp
    moreover
    from A2 have "∀a∈C. r``{a} ⊆ A" 
      by auto
    with `C≠0` have "( \<Inter>a∈C. r``{a} ) ⊆ A" using ZF1_1_L7 
      by simp
    moreover note A1 A2 
    ultimately have "HasAminimum(r, \<Inter>a∈C. r``{a} )"
      using ord_iso_pres_has_min by simp
  } then show "r {is complete}" using IsComplete_def
    by simp
qed

text{*If the original relation is complete, then the induced
  one is complete.*}

lemma ind_rel_pres_compl: assumes A1: "f ∈ bij(A,B)"
  and A2: "R ⊆ B×B" and A3: "R {is complete}"
  shows "InducedRelation(f,R) {is complete}"
proof -
  let ?r = "InducedRelation(f,R)"
  from A1 have "f ∈ ord_iso(A,?r,B,R)"
    using bij_is_ord_iso by simp
  moreover from A1 A2 have "?r ⊆ A×A"
    using bij_is_fun ind_rel_domain by simp
  moreover note A2 A3
  ultimately show "?r {is complete}"
    using ord_iso_pres_compl by simp 
qed
  

end