src/HOL/Quotient_Examples/Quotient_Rat.thy
changeset 57512 cc97b347b301
parent 49962 a8cc904a6820
child 59557 ebd8ecacfba6
equal deleted inserted replaced
57511:de51a86fc903 57512:cc97b347b301
    39 
    39 
    40 fun times_rat_raw where
    40 fun times_rat_raw where
    41   "times_rat_raw (a :: int, b :: int) (c, d) = (a * c, b * d)"
    41   "times_rat_raw (a :: int, b :: int) (c, d) = (a * c, b * d)"
    42 
    42 
    43 quotient_definition
    43 quotient_definition
    44   "(op *) :: (rat \<Rightarrow> rat \<Rightarrow> rat)" is times_rat_raw by (auto simp add: mult_assoc mult_left_commute)
    44   "(op *) :: (rat \<Rightarrow> rat \<Rightarrow> rat)" is times_rat_raw by (auto simp add: mult.assoc mult.left_commute)
    45 
    45 
    46 fun plus_rat_raw where
    46 fun plus_rat_raw where
    47   "plus_rat_raw (a :: int, b :: int) (c, d) = (a * d + c * b, b * d)"
    47   "plus_rat_raw (a :: int, b :: int) (c, d) = (a * d + c * b, b * d)"
    48 
    48 
    49 quotient_definition
    49 quotient_definition
    50   "(op +) :: (rat \<Rightarrow> rat \<Rightarrow> rat)" is plus_rat_raw 
    50   "(op +) :: (rat \<Rightarrow> rat \<Rightarrow> rat)" is plus_rat_raw 
    51   by (auto simp add: mult_commute mult_left_commute int_distrib(2))
    51   by (auto simp add: mult.commute mult.left_commute int_distrib(2))
    52 
    52 
    53 fun uminus_rat_raw where
    53 fun uminus_rat_raw where
    54   "uminus_rat_raw (a :: int, b :: int) = (-a, b)"
    54   "uminus_rat_raw (a :: int, b :: int) = (-a, b)"
    55 
    55 
    56 quotient_definition
    56 quotient_definition
    76       by (metis linorder_neqE_linordered_idom mult_eq_0_iff not_square_less_zero)
    76       by (metis linorder_neqE_linordered_idom mult_eq_0_iff not_square_less_zero)
    77     assume eq: "a * d = c * b" "e * h = g * f"
    77     assume eq: "a * d = c * b" "e * h = g * f"
    78     have "a * f * b * f * d * d \<le> e * b * b * f * d * d" using le nz(2)
    78     have "a * f * b * f * d * d \<le> e * b * b * f * d * d" using le nz(2)
    79       by (metis linorder_le_cases mult_right_mono mult_right_mono_neg)
    79       by (metis linorder_le_cases mult_right_mono mult_right_mono_neg)
    80     then have "c * f * f * d * (b * b) \<le> e * f * d * d * (b * b)" using eq
    80     then have "c * f * f * d * (b * b) \<le> e * f * d * d * (b * b)" using eq
    81       by (metis (no_types) mult_assoc mult_commute)
    81       by (metis (no_types) mult.assoc mult.commute)
    82     then have "c * f * f * d \<le> e * f * d * d" using b2
    82     then have "c * f * f * d \<le> e * f * d * d" using b2
    83       by (metis leD linorder_le_less_linear mult_strict_right_mono)
    83       by (metis leD linorder_le_less_linear mult_strict_right_mono)
    84     then have "c * f * f * d * h * h \<le> e * f * d * d * h * h" using nz(4)
    84     then have "c * f * f * d * h * h \<le> e * f * d * d * h * h" using nz(4)
    85       by (metis linorder_le_cases mult_right_mono mult_right_mono_neg)
    85       by (metis linorder_le_cases mult_right_mono mult_right_mono_neg)
    86     then have "c * h * (d * h) * (f * f) \<le> g * d * (d * h) * (f * f)" using eq
    86     then have "c * h * (d * h) * (f * f) \<le> g * d * (d * h) * (f * f)" using eq
    87       by (metis (no_types) mult_assoc mult_commute)
    87       by (metis (no_types) mult.assoc mult.commute)
    88     then have "c * h * (d * h) \<le> g * d * (d * h)" using f2
    88     then have "c * h * (d * h) \<le> g * d * (d * h)" using f2
    89       by (metis leD linorder_le_less_linear mult_strict_right_mono)
    89       by (metis leD linorder_le_less_linear mult_strict_right_mono)
    90   }
    90   }
    91   then show "\<And>x y xa ya. x \<approx> y \<Longrightarrow> xa \<approx> ya \<Longrightarrow> le_rat_raw x xa = le_rat_raw y ya" by auto
    91   then show "\<And>x y xa ya. x \<approx> y \<Longrightarrow> xa \<approx> ya \<Longrightarrow> le_rat_raw x xa = le_rat_raw y ya" by auto
    92 qed
    92 qed
   126   show "a * b = b * a"
   126   show "a * b = b * a"
   127     by partiality_descending auto
   127     by partiality_descending auto
   128   show "1 * a = a"
   128   show "1 * a = a"
   129     by partiality_descending auto
   129     by partiality_descending auto
   130   show "a + b + c = a + (b + c)"
   130   show "a + b + c = a + (b + c)"
   131     by partiality_descending (auto simp add: mult_commute distrib_left)
   131     by partiality_descending (auto simp add: mult.commute distrib_left)
   132   show "a + b = b + a"
   132   show "a + b = b + a"
   133     by partiality_descending auto
   133     by partiality_descending auto
   134   show "0 + a = a"
   134   show "0 + a = a"
   135     by partiality_descending auto
   135     by partiality_descending auto
   136   show "- a + a = 0"
   136   show "- a + a = 0"
   137     by partiality_descending auto
   137     by partiality_descending auto
   138   show "a - b = a + - b"
   138   show "a - b = a + - b"
   139     by (simp add: minus_rat_def)
   139     by (simp add: minus_rat_def)
   140   show "(a + b) * c = a * c + b * c"
   140   show "(a + b) * c = a * c + b * c"
   141     by partiality_descending (auto simp add: mult_commute distrib_left)
   141     by partiality_descending (auto simp add: mult.commute distrib_left)
   142   show "(0 :: rat) \<noteq> (1 :: rat)"
   142   show "(0 :: rat) \<noteq> (1 :: rat)"
   143     by partiality_descending auto
   143     by partiality_descending auto
   144 qed
   144 qed
   145 
   145 
   146 end
   146 end
   165 
   165 
   166 fun rat_inverse_raw where
   166 fun rat_inverse_raw where
   167   "rat_inverse_raw (a :: int, b :: int) = (if a = 0 then (0, 1) else (b, a))"
   167   "rat_inverse_raw (a :: int, b :: int) = (if a = 0 then (0, 1) else (b, a))"
   168 
   168 
   169 quotient_definition
   169 quotient_definition
   170   "inverse :: rat \<Rightarrow> rat" is rat_inverse_raw by (force simp add: mult_commute)
   170   "inverse :: rat \<Rightarrow> rat" is rat_inverse_raw by (force simp add: mult.commute)
   171 
   171 
   172 definition
   172 definition
   173   divide_rat_def: "q / r = q * inverse (r::rat)"
   173   divide_rat_def: "q / r = q * inverse (r::rat)"
   174 
   174 
   175 instance proof
   175 instance proof
   192 instance proof
   192 instance proof
   193   fix q r s :: rat
   193   fix q r s :: rat
   194   {
   194   {
   195     assume "q \<le> r" and "r \<le> s"
   195     assume "q \<le> r" and "r \<le> s"
   196     then show "q \<le> s"
   196     then show "q \<le> s"
   197     proof (partiality_descending, auto simp add: mult_assoc[symmetric])
   197     proof (partiality_descending, auto simp add: mult.assoc[symmetric])
   198       fix a b c d e f :: int
   198       fix a b c d e f :: int
   199       assume nz: "b \<noteq> 0" "d \<noteq> 0" "f \<noteq> 0"
   199       assume nz: "b \<noteq> 0" "d \<noteq> 0" "f \<noteq> 0"
   200       then have d2: "d * d > 0"
   200       then have d2: "d * d > 0"
   201         by (metis linorder_neqE_linordered_idom mult_eq_0_iff not_square_less_zero)
   201         by (metis linorder_neqE_linordered_idom mult_eq_0_iff not_square_less_zero)
   202       assume le: "a * d * b * d \<le> c * b * b * d" "c * f * d * f \<le> e * d * d * f"
   202       assume le: "a * d * b * d \<le> c * b * b * d" "c * f * d * f \<le> e * d * d * f"
   218       done
   218       done
   219   next
   219   next
   220     show "q \<le> q" by partiality_descending auto
   220     show "q \<le> q" by partiality_descending auto
   221     show "(q < r) = (q \<le> r \<and> \<not> r \<le> q)"
   221     show "(q < r) = (q \<le> r \<and> \<not> r \<le> q)"
   222       unfolding less_rat_def
   222       unfolding less_rat_def
   223       by partiality_descending (auto simp add: le_less mult_commute)
   223       by partiality_descending (auto simp add: le_less mult.commute)
   224     show "q \<le> r \<or> r \<le> q"
   224     show "q \<le> r \<or> r \<le> q"
   225       by partiality_descending (auto simp add: mult_commute linorder_linear)
   225       by partiality_descending (auto simp add: mult.commute linorder_linear)
   226   }
   226   }
   227 qed
   227 qed
   228 
   228 
   229 end
   229 end
   230 
   230 
   231 instance rat :: archimedean_field
   231 instance rat :: archimedean_field
   232 proof
   232 proof
   233   fix q r s :: rat
   233   fix q r s :: rat
   234   show "q \<le> r ==> s + q \<le> s + r"
   234   show "q \<le> r ==> s + q \<le> s + r"
   235   proof (partiality_descending, auto simp add: algebra_simps, simp add: mult_assoc[symmetric])
   235   proof (partiality_descending, auto simp add: algebra_simps, simp add: mult.assoc[symmetric])
   236     fix a b c d e :: int
   236     fix a b c d e :: int
   237     assume "e \<noteq> 0"
   237     assume "e \<noteq> 0"
   238     then have e2: "e * e > 0"
   238     then have e2: "e * e > 0"
   239       by (metis linorder_neqE_linordered_idom mult_eq_0_iff not_square_less_zero)
   239       by (metis linorder_neqE_linordered_idom mult_eq_0_iff not_square_less_zero)
   240       assume "a * b * d * d \<le> b * b * c * d"
   240       assume "a * b * d * d \<le> b * b * c * d"
   241       then show "a * b * d * d * e * e * e * e \<le> b * b * c * d * e * e * e * e"
   241       then show "a * b * d * d * e * e * e * e \<le> b * b * c * d * e * e * e * e"
   242         using e2 by (metis comm_mult_left_mono mult_commute linorder_le_cases
   242         using e2 by (metis comm_mult_left_mono mult.commute linorder_le_cases
   243           mult_left_mono_neg)
   243           mult_left_mono_neg)
   244     qed
   244     qed
   245   show "q < r ==> 0 < s ==> s * q < s * r" unfolding less_rat_def
   245   show "q < r ==> 0 < s ==> s * q < s * r" unfolding less_rat_def
   246     proof (partiality_descending, auto simp add: algebra_simps, simp add: mult_assoc[symmetric])
   246     proof (partiality_descending, auto simp add: algebra_simps, simp add: mult.assoc[symmetric])
   247     fix a b c d e f :: int
   247     fix a b c d e f :: int
   248     assume a: "e \<noteq> 0" "f \<noteq> 0" "0 \<le> e * f" "a * b * d * d \<le> b * b * c * d"
   248     assume a: "e \<noteq> 0" "f \<noteq> 0" "0 \<le> e * f" "a * b * d * d \<le> b * b * c * d"
   249     have "a * b * d * d * (e * f) \<le> b * b * c * d * (e * f)" using a
   249     have "a * b * d * d * (e * f) \<le> b * b * c * d * (e * f)" using a
   250       by (simp add: mult_right_mono)
   250       by (simp add: mult_right_mono)
   251     then show "a * b * d * d * e * f * f * f \<le> b * b * c * d * e * f * f * f"
   251     then show "a * b * d * d * e * f * f * f \<le> b * b * c * d * e * f * f * f"
   252       by (simp add: mult_assoc[symmetric]) (metis a(3) comm_mult_left_mono
   252       by (simp add: mult.assoc[symmetric]) (metis a(3) comm_mult_left_mono
   253         mult_commute mult_left_mono_neg zero_le_mult_iff)
   253         mult.commute mult_left_mono_neg zero_le_mult_iff)
   254   qed
   254   qed
   255   show "\<exists>z. r \<le> of_int z"
   255   show "\<exists>z. r \<le> of_int z"
   256     unfolding of_int_rat
   256     unfolding of_int_rat
   257   proof (partiality_descending, auto)
   257   proof (partiality_descending, auto)
   258     fix a b :: int
   258     fix a b :: int
   259     assume "b \<noteq> 0"
   259     assume "b \<noteq> 0"
   260     then have "a * b \<le> (a div b + 1) * b * b"
   260     then have "a * b \<le> (a div b + 1) * b * b"
   261       by (metis mult_commute div_mult_self1_is_id less_int_def linorder_le_cases zdiv_mono1 zdiv_mono1_neg zle_add1_eq_le)
   261       by (metis mult.commute div_mult_self1_is_id less_int_def linorder_le_cases zdiv_mono1 zdiv_mono1_neg zle_add1_eq_le)
   262     then show "\<exists>z\<Colon>int. a * b \<le> z * b * b" by auto
   262     then show "\<exists>z\<Colon>int. a * b \<le> z * b * b" by auto
   263   qed
   263   qed
   264 qed
   264 qed
   265 *)
   265 *)
   266 
   266