src/HOL/GCD.thy
changeset 80932 261cd8722677
parent 80771 fd01ef524169
child 80934 8e72f55295fd
equal deleted inserted replaced
80931:f6e595e4f608 80932:261cd8722677
    35 begin
    35 begin
    36 
    36 
    37 subsection \<open>Abstract bounded quasi semilattices as common foundation\<close>
    37 subsection \<open>Abstract bounded quasi semilattices as common foundation\<close>
    38 
    38 
    39 locale bounded_quasi_semilattice = abel_semigroup +
    39 locale bounded_quasi_semilattice = abel_semigroup +
    40   fixes top :: 'a  ("\<^bold>\<top>") and bot :: 'a  ("\<^bold>\<bottom>")
    40   fixes top :: 'a  (\<open>\<^bold>\<top>\<close>) and bot :: 'a  (\<open>\<^bold>\<bottom>\<close>)
    41     and normalize :: "'a \<Rightarrow> 'a"
    41     and normalize :: "'a \<Rightarrow> 'a"
    42   assumes idem_normalize [simp]: "a \<^bold>* a = normalize a"
    42   assumes idem_normalize [simp]: "a \<^bold>* a = normalize a"
    43     and normalize_left_idem [simp]: "normalize a \<^bold>* b = a \<^bold>* b"
    43     and normalize_left_idem [simp]: "normalize a \<^bold>* b = a \<^bold>* b"
    44     and normalize_idem [simp]: "normalize (a \<^bold>* b) = a \<^bold>* b"
    44     and normalize_idem [simp]: "normalize (a \<^bold>* b) = a \<^bold>* b"
    45     and normalize_top [simp]: "normalize \<^bold>\<top> = \<^bold>\<top>"
    45     and normalize_top [simp]: "normalize \<^bold>\<top> = \<^bold>\<top>"
   146 class Gcd = gcd +
   146 class Gcd = gcd +
   147   fixes Gcd :: "'a set \<Rightarrow> 'a"
   147   fixes Gcd :: "'a set \<Rightarrow> 'a"
   148     and Lcm :: "'a set \<Rightarrow> 'a"
   148     and Lcm :: "'a set \<Rightarrow> 'a"
   149 
   149 
   150 syntax
   150 syntax
   151   "_GCD1"     :: "pttrns \<Rightarrow> 'b \<Rightarrow> 'b"           ("(3GCD _./ _)" [0, 10] 10)
   151   "_GCD1"     :: "pttrns \<Rightarrow> 'b \<Rightarrow> 'b"           (\<open>(3GCD _./ _)\<close> [0, 10] 10)
   152   "_GCD"      :: "pttrn \<Rightarrow> 'a set \<Rightarrow> 'b \<Rightarrow> 'b"  ("(3GCD _\<in>_./ _)" [0, 0, 10] 10)
   152   "_GCD"      :: "pttrn \<Rightarrow> 'a set \<Rightarrow> 'b \<Rightarrow> 'b"  (\<open>(3GCD _\<in>_./ _)\<close> [0, 0, 10] 10)
   153   "_LCM1"     :: "pttrns \<Rightarrow> 'b \<Rightarrow> 'b"           ("(3LCM _./ _)" [0, 10] 10)
   153   "_LCM1"     :: "pttrns \<Rightarrow> 'b \<Rightarrow> 'b"           (\<open>(3LCM _./ _)\<close> [0, 10] 10)
   154   "_LCM"      :: "pttrn \<Rightarrow> 'a set \<Rightarrow> 'b \<Rightarrow> 'b"  ("(3LCM _\<in>_./ _)" [0, 0, 10] 10)
   154   "_LCM"      :: "pttrn \<Rightarrow> 'a set \<Rightarrow> 'b \<Rightarrow> 'b"  (\<open>(3LCM _\<in>_./ _)\<close> [0, 0, 10] 10)
   155 
   155 
   156 syntax_consts
   156 syntax_consts
   157   "_GCD1" "_GCD" \<rightleftharpoons> Gcd and
   157   "_GCD1" "_GCD" \<rightleftharpoons> Gcd and
   158   "_LCM1" "_LCM" \<rightleftharpoons> Lcm
   158   "_LCM1" "_LCM" \<rightleftharpoons> Lcm
   159 
   159 
  1065 context semiring_gcd
  1065 context semiring_gcd
  1066 begin
  1066 begin
  1067 
  1067 
  1068 sublocale Gcd_fin: bounded_quasi_semilattice_set gcd 0 1 normalize
  1068 sublocale Gcd_fin: bounded_quasi_semilattice_set gcd 0 1 normalize
  1069 defines
  1069 defines
  1070   Gcd_fin ("Gcd\<^sub>f\<^sub>i\<^sub>n") = "Gcd_fin.F :: 'a set \<Rightarrow> 'a" ..
  1070   Gcd_fin (\<open>Gcd\<^sub>f\<^sub>i\<^sub>n\<close>) = "Gcd_fin.F :: 'a set \<Rightarrow> 'a" ..
  1071 
  1071 
  1072 abbreviation gcd_list :: "'a list \<Rightarrow> 'a"
  1072 abbreviation gcd_list :: "'a list \<Rightarrow> 'a"
  1073   where "gcd_list xs \<equiv> Gcd\<^sub>f\<^sub>i\<^sub>n (set xs)"
  1073   where "gcd_list xs \<equiv> Gcd\<^sub>f\<^sub>i\<^sub>n (set xs)"
  1074 
  1074 
  1075 sublocale Lcm_fin: bounded_quasi_semilattice_set lcm 1 0 normalize
  1075 sublocale Lcm_fin: bounded_quasi_semilattice_set lcm 1 0 normalize
  1076 defines
  1076 defines
  1077   Lcm_fin ("Lcm\<^sub>f\<^sub>i\<^sub>n") = Lcm_fin.F ..
  1077   Lcm_fin (\<open>Lcm\<^sub>f\<^sub>i\<^sub>n\<close>) = Lcm_fin.F ..
  1078 
  1078 
  1079 abbreviation lcm_list :: "'a list \<Rightarrow> 'a"
  1079 abbreviation lcm_list :: "'a list \<Rightarrow> 'a"
  1080   where "lcm_list xs \<equiv> Lcm\<^sub>f\<^sub>i\<^sub>n (set xs)"
  1080   where "lcm_list xs \<equiv> Lcm\<^sub>f\<^sub>i\<^sub>n (set xs)"
  1081 
  1081 
  1082 lemma Gcd_fin_dvd:
  1082 lemma Gcd_fin_dvd:
  2849 subsection \<open>Characteristic of a semiring\<close>
  2849 subsection \<open>Characteristic of a semiring\<close>
  2850 
  2850 
  2851 definition (in semiring_1) semiring_char :: "'a itself \<Rightarrow> nat" 
  2851 definition (in semiring_1) semiring_char :: "'a itself \<Rightarrow> nat" 
  2852   where "semiring_char _ = Gcd {n. of_nat n = (0 :: 'a)}"
  2852   where "semiring_char _ = Gcd {n. of_nat n = (0 :: 'a)}"
  2853 
  2853 
  2854 syntax "_type_char" :: "type => nat" ("(1CHAR/(1'(_')))")
  2854 syntax "_type_char" :: "type => nat" (\<open>(1CHAR/(1'(_')))\<close>)
  2855 syntax_consts "_type_char" \<rightleftharpoons> semiring_char
  2855 syntax_consts "_type_char" \<rightleftharpoons> semiring_char
  2856 translations "CHAR('t)" \<rightharpoonup> "CONST semiring_char (CONST Pure.type :: 't itself)"
  2856 translations "CHAR('t)" \<rightharpoonup> "CONST semiring_char (CONST Pure.type :: 't itself)"
  2857 print_translation \<open>
  2857 print_translation \<open>
  2858   let
  2858   let
  2859     fun char_type_tr' ctxt [Const (\<^const_syntax>\<open>Pure.type\<close>, Type (_, [T]))] =
  2859     fun char_type_tr' ctxt [Const (\<^const_syntax>\<open>Pure.type\<close>, Type (_, [T]))] =