src/HOL/Library/Abstract_Rat.thy
changeset 41528 276078f01ada
parent 36411 4cd87067791e
child 42463 f270e3e18be5
equal deleted inserted replaced
41527:924106faa45f 41528:276078f01ada
    42     let ?g = "gcd a b"
    42     let ?g = "gcd a b"
    43     let ?a' = "a div ?g"
    43     let ?a' = "a div ?g"
    44     let ?b' = "b div ?g"
    44     let ?b' = "b div ?g"
    45     let ?g' = "gcd ?a' ?b'"
    45     let ?g' = "gcd ?a' ?b'"
    46     from anz bnz have "?g \<noteq> 0" by simp  with gcd_ge_0_int[of a b] 
    46     from anz bnz have "?g \<noteq> 0" by simp  with gcd_ge_0_int[of a b] 
    47     have gpos: "?g > 0"  by arith
    47     have gpos: "?g > 0" by arith
    48     have gdvd: "?g dvd a" "?g dvd b" by arith+ 
    48     have gdvd: "?g dvd a" "?g dvd b" by arith+ 
    49     from zdvd_mult_div_cancel[OF gdvd(1)] zdvd_mult_div_cancel[OF gdvd(2)]
    49     from zdvd_mult_div_cancel[OF gdvd(1)] zdvd_mult_div_cancel[OF gdvd(2)]
    50     anz bnz
    50     anz bnz
    51     have nz':"?a' \<noteq> 0" "?b' \<noteq> 0"
    51     have nz':"?a' \<noteq> 0" "?b' \<noteq> 0"
    52       by - (rule notI, simp)+
    52       by - (rule notI, simp)+
   138 lemma Ninv_normN[simp]: "isnormNum x \<Longrightarrow> isnormNum (Ninv x)"
   138 lemma Ninv_normN[simp]: "isnormNum x \<Longrightarrow> isnormNum (Ninv x)"
   139   by (simp add: Ninv_def isnormNum_def split_def)
   139   by (simp add: Ninv_def isnormNum_def split_def)
   140     (cases "fst x = 0", auto simp add: gcd_commute_int)
   140     (cases "fst x = 0", auto simp add: gcd_commute_int)
   141 
   141 
   142 lemma isnormNum_int[simp]: 
   142 lemma isnormNum_int[simp]: 
   143   "isnormNum 0\<^sub>N" "isnormNum (1::int)\<^sub>N" "i \<noteq> 0 \<Longrightarrow> isnormNum i\<^sub>N"
   143   "isnormNum 0\<^sub>N" "isnormNum ((1::int)\<^sub>N)" "i \<noteq> 0 \<Longrightarrow> isnormNum (i\<^sub>N)"
   144   by (simp_all add: isnormNum_def)
   144   by (simp_all add: isnormNum_def)
   145 
   145 
   146 
   146 
   147 text {* Relations over Num *}
   147 text {* Relations over Num *}
   148 
   148 
   177   "Nle = (\<lambda>a b. 0\<ge>\<^sub>N (a -\<^sub>N b))"
   177   "Nle = (\<lambda>a b. 0\<ge>\<^sub>N (a -\<^sub>N b))"
   178 
   178 
   179 definition
   179 definition
   180   "INum = (\<lambda>(a,b). of_int a / of_int b)"
   180   "INum = (\<lambda>(a,b). of_int a / of_int b)"
   181 
   181 
   182 lemma INum_int [simp]: "INum i\<^sub>N = ((of_int i) ::'a::field)" "INum 0\<^sub>N = (0::'a::field)"
   182 lemma INum_int [simp]: "INum (i\<^sub>N) = ((of_int i) ::'a::field)" "INum 0\<^sub>N = (0::'a::field)"
   183   by (simp_all add: INum_def)
   183   by (simp_all add: INum_def)
   184 
   184 
   185 lemma isnormNum_unique[simp]: 
   185 lemma isnormNum_unique[simp]: 
   186   assumes na: "isnormNum x" and nb: "isnormNum y" 
   186   assumes na: "isnormNum x" and nb: "isnormNum y" 
   187   shows "((INum x ::'a::{field_char_0, field_inverse_zero}) = INum y) = (x = y)" (is "?lhs = ?rhs")
   187   shows "((INum x ::'a::{field_char_0, field_inverse_zero}) = INum y) = (x = y)" (is "?lhs = ?rhs")
   193     hence ?rhs using na nb H
   193     hence ?rhs using na nb H
   194       by (simp add: INum_def split_def isnormNum_def split: split_if_asm)}
   194       by (simp add: INum_def split_def isnormNum_def split: split_if_asm)}
   195   moreover
   195   moreover
   196   { assume az: "a \<noteq> 0" and bz: "b \<noteq> 0" and a'z: "a'\<noteq>0" and b'z: "b'\<noteq>0"
   196   { assume az: "a \<noteq> 0" and bz: "b \<noteq> 0" and a'z: "a'\<noteq>0" and b'z: "b'\<noteq>0"
   197     from az bz a'z b'z na nb have pos: "b > 0" "b' > 0" by (simp_all add: isnormNum_def)
   197     from az bz a'z b'z na nb have pos: "b > 0" "b' > 0" by (simp_all add: isnormNum_def)
   198     from prems have eq:"a * b' = a'*b" 
   198     from H bz b'z have eq:"a * b' = a'*b" 
   199       by (simp add: INum_def  eq_divide_eq divide_eq_eq of_int_mult[symmetric] del: of_int_mult)
   199       by (simp add: INum_def  eq_divide_eq divide_eq_eq of_int_mult[symmetric] del: of_int_mult)
   200     from prems have gcd1: "gcd a b = 1" "gcd b a = 1" "gcd a' b' = 1" "gcd b' a' = 1"       
   200     from az a'z na nb have gcd1: "gcd a b = 1" "gcd b a = 1" "gcd a' b' = 1" "gcd b' a' = 1"       
   201       by (simp_all add: isnormNum_def add: gcd_commute_int)
   201       by (simp_all add: isnormNum_def add: gcd_commute_int)
   202     from eq have raw_dvd: "a dvd a'*b" "b dvd b'*a" "a' dvd a*b'" "b' dvd b*a'"
   202     from eq have raw_dvd: "a dvd a'*b" "b dvd b'*a" "a' dvd a*b'" "b' dvd b*a'"
   203       apply - 
   203       apply - 
   204       apply algebra
   204       apply algebra
   205       apply algebra
   205       apply algebra
   206       apply simp
   206       apply simp
   207       apply algebra
   207       apply algebra
   208       done
   208       done
   209     from zdvd_antisym_abs[OF coprime_dvd_mult_int[OF gcd1(2) raw_dvd(2)]
   209     from zdvd_antisym_abs[OF coprime_dvd_mult_int[OF gcd1(2) raw_dvd(2)]
   210       coprime_dvd_mult_int[OF gcd1(4) raw_dvd(4)]]
   210       coprime_dvd_mult_int[OF gcd1(4) raw_dvd(4)]]
   211       have eq1: "b = b'" using pos by arith  
   211       have eq1: "b = b'" using pos by arith
   212       with eq have "a = a'" using pos by simp
   212       with eq have "a = a'" using pos by simp
   213       with eq1 have ?rhs by simp}
   213       with eq1 have ?rhs by simp}
   214   ultimately show ?rhs by blast
   214   ultimately show ?rhs by blast
   215 next
   215 next
   216   assume ?rhs thus ?lhs by simp
   216   assume ?rhs thus ?lhs by simp
   223 
   223 
   224 lemma of_int_div_aux: "d ~= 0 ==> ((of_int x)::'a::field_char_0) / (of_int d) = 
   224 lemma of_int_div_aux: "d ~= 0 ==> ((of_int x)::'a::field_char_0) / (of_int d) = 
   225     of_int (x div d) + (of_int (x mod d)) / ((of_int d)::'a)"
   225     of_int (x div d) + (of_int (x mod d)) / ((of_int d)::'a)"
   226 proof -
   226 proof -
   227   assume "d ~= 0"
   227   assume "d ~= 0"
   228   hence dz: "of_int d \<noteq> (0::'a)" by (simp add: of_int_eq_0_iff)
       
   229   let ?t = "of_int (x div d) * ((of_int d)::'a) + of_int(x mod d)"
   228   let ?t = "of_int (x div d) * ((of_int d)::'a) + of_int(x mod d)"
   230   let ?f = "\<lambda>x. x / of_int d"
   229   let ?f = "\<lambda>x. x / of_int d"
   231   have "x = (x div d) * d + x mod d"
   230   have "x = (x div d) * d + x mod d"
   232     by auto
   231     by auto
   233   then have eq: "of_int x = ?t"
   232   then have eq: "of_int x = ?t"
   234     by (simp only: of_int_mult[symmetric] of_int_add [symmetric])
   233     by (simp only: of_int_mult[symmetric] of_int_add [symmetric])
   235   then have "of_int x / of_int d = ?t / of_int d" 
   234   then have "of_int x / of_int d = ?t / of_int d" 
   236     using cong[OF refl[of ?f] eq] by simp
   235     using cong[OF refl[of ?f] eq] by simp
   237   then show ?thesis by (simp add: add_divide_distrib algebra_simps prems)
   236   then show ?thesis by (simp add: add_divide_distrib algebra_simps `d ~= 0`)
   238 qed
   237 qed
   239 
   238 
   240 lemma of_int_div: "(d::int) ~= 0 ==> d dvd n ==>
   239 lemma of_int_div: "(d::int) ~= 0 ==> d dvd n ==>
   241     (of_int(n div d)::'a::field_char_0) = of_int n / of_int d"
   240     (of_int(n div d)::'a::field_char_0) = of_int n / of_int d"
   242   apply (frule of_int_div_aux [of d n, where ?'a = 'a])
   241   apply (frule of_int_div_aux [of d n, where ?'a = 'a])
   292       let ?g = "gcd (a * b' + b * a') (b*b')"
   291       let ?g = "gcd (a * b' + b * a') (b*b')"
   293       have gz: "?g \<noteq> 0" using z by simp
   292       have gz: "?g \<noteq> 0" using z by simp
   294       have ?thesis using aa' bb' z gz
   293       have ?thesis using aa' bb' z gz
   295         of_int_div[where ?'a = 'a, OF gz gcd_dvd1_int[where x="a * b' + b * a'" and y="b*b'"]]  of_int_div[where ?'a = 'a,
   294         of_int_div[where ?'a = 'a, OF gz gcd_dvd1_int[where x="a * b' + b * a'" and y="b*b'"]]  of_int_div[where ?'a = 'a,
   296         OF gz gcd_dvd2_int[where x="a * b' + b * a'" and y="b*b'"]]
   295         OF gz gcd_dvd2_int[where x="a * b' + b * a'" and y="b*b'"]]
   297         by (simp add: x y Nadd_def INum_def normNum_def Let_def add_divide_distrib)}
   296         by (simp add: Nadd_def INum_def normNum_def Let_def add_divide_distrib)}
   298     ultimately have ?thesis using aa' bb' 
   297     ultimately have ?thesis using aa' bb' 
   299       by (simp add: Nadd_def INum_def normNum_def x y Let_def) }
   298       by (simp add: Nadd_def INum_def normNum_def Let_def) }
   300   ultimately show ?thesis by blast
   299   ultimately show ?thesis by blast
   301 qed
   300 qed
   302 
   301 
   303 lemma Nmul[simp]: "INum (x *\<^sub>N y) = INum x * (INum y:: 'a :: {field_char_0, field_inverse_zero}) "
   302 lemma Nmul[simp]: "INum (x *\<^sub>N y) = INum x * (INum y:: 'a :: {field_char_0, field_inverse_zero}) "
   304 proof-
   303 proof-
   510     have " \<exists> a b a' b'. x = (a,b) \<and> y= (a',b')" by auto
   509     have " \<exists> a b a' b'. x = (a,b) \<and> y= (a',b')" by auto
   511     then obtain a b a' b' where xy[simp]: "x = (a,b)" "y = (a',b')" by blast
   510     then obtain a b a' b' where xy[simp]: "x = (a,b)" "y = (a',b')" by blast
   512     have n0: "isnormNum 0\<^sub>N" by simp
   511     have n0: "isnormNum 0\<^sub>N" by simp
   513     show ?thesis using nx ny 
   512     show ?thesis using nx ny 
   514       apply (simp only: isnormNum_unique[where ?'a = 'a, OF  Nmul_normN[OF nx ny] n0, symmetric] Nmul[where ?'a = 'a])
   513       apply (simp only: isnormNum_unique[where ?'a = 'a, OF  Nmul_normN[OF nx ny] n0, symmetric] Nmul[where ?'a = 'a])
   515       by (simp add: INum_def split_def isnormNum_def fst_conv snd_conv split: split_if_asm)
   514       by (simp add: INum_def split_def isnormNum_def split: split_if_asm)
   516   }
   515   }
   517 qed
   516 qed
   518 lemma Nneg_Nneg[simp]: "~\<^sub>N (~\<^sub>N c) = c"
   517 lemma Nneg_Nneg[simp]: "~\<^sub>N (~\<^sub>N c) = c"
   519   by (simp add: Nneg_def split_def)
   518   by (simp add: Nneg_def split_def)
   520 
   519 
   521 lemma Nmul1[simp]: 
   520 lemma Nmul1[simp]: 
   522   "isnormNum c \<Longrightarrow> 1\<^sub>N *\<^sub>N c = c" 
   521   "isnormNum c \<Longrightarrow> 1\<^sub>N *\<^sub>N c = c" 
   523   "isnormNum c \<Longrightarrow> c *\<^sub>N 1\<^sub>N  = c" 
   522   "isnormNum c \<Longrightarrow> c *\<^sub>N (1\<^sub>N) = c" 
   524   apply (simp_all add: Nmul_def Let_def split_def isnormNum_def)
   523   apply (simp_all add: Nmul_def Let_def split_def isnormNum_def)
   525   apply (cases "fst c = 0", simp_all, cases c, simp_all)+
   524   apply (cases "fst c = 0", simp_all, cases c, simp_all)+
   526   done
   525   done
   527 
   526 
   528 end
   527 end