src/HOL/NumberTheory/IntFact.thy
changeset 11868 56db9f3a6b3e
parent 11701 3d51fbf81c17
child 12693 827818b891c7
equal deleted inserted replaced
11867:76401b2ee871 11868:56db9f3a6b3e
    20   zfact :: "int => int"
    20   zfact :: "int => int"
    21   setprod :: "int set => int"
    21   setprod :: "int set => int"
    22   d22set :: "int => int set"
    22   d22set :: "int => int set"
    23 
    23 
    24 recdef zfact  "measure ((\<lambda>n. nat n) :: int => nat)"
    24 recdef zfact  "measure ((\<lambda>n. nat n) :: int => nat)"
    25   "zfact n = (if n \<le> Numeral0 then Numeral1 else n * zfact (n - Numeral1))"
    25   "zfact n = (if n \<le> 0 then 1 else n * zfact (n - 1))"
    26 
    26 
    27 defs
    27 defs
    28   setprod_def: "setprod A == (if finite A then fold (op *) Numeral1 A else Numeral1)"
    28   setprod_def: "setprod A == (if finite A then fold (op *) 1 A else 1)"
    29 
    29 
    30 recdef d22set  "measure ((\<lambda>a. nat a) :: int => nat)"
    30 recdef d22set  "measure ((\<lambda>a. nat a) :: int => nat)"
    31   "d22set a = (if Numeral1 < a then insert a (d22set (a - Numeral1)) else {})"
    31   "d22set a = (if 1 < a then insert a (d22set (a - 1)) else {})"
    32 
    32 
    33 
    33 
    34 text {* \medskip @{term setprod} --- product of finite set *}
    34 text {* \medskip @{term setprod} --- product of finite set *}
    35 
    35 
    36 lemma setprod_empty [simp]: "setprod {} = Numeral1"
    36 lemma setprod_empty [simp]: "setprod {} = 1"
    37   apply (simp add: setprod_def)
    37   apply (simp add: setprod_def)
    38   done
    38   done
    39 
    39 
    40 lemma setprod_insert [simp]:
    40 lemma setprod_insert [simp]:
    41     "finite A ==> a \<notin> A ==> setprod (insert a A) = a * setprod A"
    41     "finite A ==> a \<notin> A ==> setprod (insert a A) = a * setprod A"
    52 declare d22set.simps [simp del]
    52 declare d22set.simps [simp del]
    53 
    53 
    54 
    54 
    55 lemma d22set_induct:
    55 lemma d22set_induct:
    56   "(!!a. P {} a) ==>
    56   "(!!a. P {} a) ==>
    57     (!!a. Numeral1 < (a::int) ==> P (d22set (a - Numeral1)) (a - Numeral1)
    57     (!!a. 1 < (a::int) ==> P (d22set (a - 1)) (a - 1)
    58       ==> P (d22set a) a)
    58       ==> P (d22set a) a)
    59     ==> P (d22set u) u"
    59     ==> P (d22set u) u"
    60 proof -
    60 proof -
    61   case rule_context
    61   case rule_context
    62   show ?thesis
    62   show ?thesis
    63     apply (rule d22set.induct)
    63     apply (rule d22set.induct)
    64     apply safe
    64     apply safe
    65      apply (case_tac [2] "Numeral1 < a")
    65      apply (case_tac [2] "1 < a")
    66       apply (rule_tac [2] rule_context)
    66       apply (rule_tac [2] rule_context)
    67        apply (simp_all (no_asm_simp))
    67        apply (simp_all (no_asm_simp))
    68      apply (simp_all (no_asm_simp) add: d22set.simps rule_context)
    68      apply (simp_all (no_asm_simp) add: d22set.simps rule_context)
    69     done
    69     done
    70 qed
    70 qed
    71 
    71 
    72 lemma d22set_g_1 [rule_format]: "b \<in> d22set a --> Numeral1 < b"
    72 lemma d22set_g_1 [rule_format]: "b \<in> d22set a --> 1 < b"
    73   apply (induct a rule: d22set_induct)
    73   apply (induct a rule: d22set_induct)
    74    prefer 2
    74    prefer 2
    75    apply (subst d22set.simps)
    75    apply (subst d22set.simps)
    76    apply auto
    76    apply auto
    77   done
    77   done
    85 
    85 
    86 lemma d22set_le_swap: "a < b ==> b \<notin> d22set a"
    86 lemma d22set_le_swap: "a < b ==> b \<notin> d22set a"
    87   apply (auto dest: d22set_le)
    87   apply (auto dest: d22set_le)
    88   done
    88   done
    89 
    89 
    90 lemma d22set_mem [rule_format]: "Numeral1 < b --> b \<le> a --> b \<in> d22set a"
    90 lemma d22set_mem [rule_format]: "1 < b --> b \<le> a --> b \<in> d22set a"
    91   apply (induct a rule: d22set.induct)
    91   apply (induct a rule: d22set.induct)
    92   apply auto
    92   apply auto
    93    apply (simp_all add: d22set.simps)
    93    apply (simp_all add: d22set.simps)
    94   done
    94   done
    95 
    95 
   107   apply (induct a rule: d22set.induct)
   107   apply (induct a rule: d22set.induct)
   108   apply safe
   108   apply safe
   109    apply (simp add: d22set.simps zfact.simps)
   109    apply (simp add: d22set.simps zfact.simps)
   110   apply (subst d22set.simps)
   110   apply (subst d22set.simps)
   111   apply (subst zfact.simps)
   111   apply (subst zfact.simps)
   112   apply (case_tac "Numeral1 < a")
   112   apply (case_tac "1 < a")
   113    prefer 2
   113    prefer 2
   114    apply (simp add: d22set.simps zfact.simps)
   114    apply (simp add: d22set.simps zfact.simps)
   115   apply (simp add: d22set_fin d22set_le_swap)
   115   apply (simp add: d22set_fin d22set_le_swap)
   116   done
   116   done
   117 
   117