src/HOL/Library/Extended_Nat.thy
changeset 62374 cb27a55d868a
parent 61631 4f7ef088c4ed
child 62376 85f38d5f8807
equal deleted inserted replaced
62373:ea7a442e9a56 62374:cb27a55d868a
    10 begin
    10 begin
    11 
    11 
    12 class infinity =
    12 class infinity =
    13   fixes infinity :: "'a"  ("\<infinity>")
    13   fixes infinity :: "'a"  ("\<infinity>")
    14 
    14 
    15 
       
    16 subsection \<open>Type definition\<close>
    15 subsection \<open>Type definition\<close>
    17 
    16 
    18 text \<open>
    17 text \<open>
    19   We extend the standard natural numbers by a special value indicating
    18   We extend the standard natural numbers by a special value indicating
    20   infinity.
    19   infinity.
    24 
    23 
    25 text \<open>TODO: introduce enat as coinductive datatype, enat is just @{const of_nat}\<close>
    24 text \<open>TODO: introduce enat as coinductive datatype, enat is just @{const of_nat}\<close>
    26 
    25 
    27 definition enat :: "nat \<Rightarrow> enat" where
    26 definition enat :: "nat \<Rightarrow> enat" where
    28   "enat n = Abs_enat (Some n)"
    27   "enat n = Abs_enat (Some n)"
    29  
    28 
    30 instantiation enat :: infinity
    29 instantiation enat :: infinity
    31 begin
    30 begin
    32 
    31 
    33 definition "\<infinity> = Abs_enat None"
    32 definition "\<infinity> = Abs_enat None"
    34 instance ..
    33 instance ..
    38 instance enat :: countable
    37 instance enat :: countable
    39 proof
    38 proof
    40   show "\<exists>to_nat::enat \<Rightarrow> nat. inj to_nat"
    39   show "\<exists>to_nat::enat \<Rightarrow> nat. inj to_nat"
    41     by (rule exI[of _ "to_nat \<circ> Rep_enat"]) (simp add: inj_on_def Rep_enat_inject)
    40     by (rule exI[of _ "to_nat \<circ> Rep_enat"]) (simp add: inj_on_def Rep_enat_inject)
    42 qed
    41 qed
    43  
    42 
    44 old_rep_datatype enat "\<infinity> :: enat"
    43 old_rep_datatype enat "\<infinity> :: enat"
    45 proof -
    44 proof -
    46   fix P i assume "\<And>j. P (enat j)" "P \<infinity>"
    45   fix P i assume "\<And>j. P (enat j)" "P \<infinity>"
    47   then show "P i"
    46   then show "P i"
    48   proof induct
    47   proof induct
   167 end
   166 end
   168 
   167 
   169 lemma eSuc_plus_1:
   168 lemma eSuc_plus_1:
   170   "eSuc n = n + 1"
   169   "eSuc n = n + 1"
   171   by (cases n) (simp_all add: eSuc_enat one_enat_def)
   170   by (cases n) (simp_all add: eSuc_enat one_enat_def)
   172   
   171 
   173 lemma plus_1_eSuc:
   172 lemma plus_1_eSuc:
   174   "1 + q = eSuc q"
   173   "1 + q = eSuc q"
   175   "q + 1 = eSuc q"
   174   "q + 1 = eSuc q"
   176   by (simp_all add: eSuc_plus_1 ac_simps)
   175   by (simp_all add: eSuc_plus_1 ac_simps)
   177 
   176 
   397 lemma i0_less [simp]: "(0::enat) < n \<longleftrightarrow> n \<noteq> 0"
   396 lemma i0_less [simp]: "(0::enat) < n \<longleftrightarrow> n \<noteq> 0"
   398   by (simp add: zero_enat_def less_enat_def split: enat.splits)
   397   by (simp add: zero_enat_def less_enat_def split: enat.splits)
   399 
   398 
   400 lemma eSuc_ile_mono [simp]: "eSuc n \<le> eSuc m \<longleftrightarrow> n \<le> m"
   399 lemma eSuc_ile_mono [simp]: "eSuc n \<le> eSuc m \<longleftrightarrow> n \<le> m"
   401   by (simp add: eSuc_def less_eq_enat_def split: enat.splits)
   400   by (simp add: eSuc_def less_eq_enat_def split: enat.splits)
   402  
   401 
   403 lemma eSuc_mono [simp]: "eSuc n < eSuc m \<longleftrightarrow> n < m"
   402 lemma eSuc_mono [simp]: "eSuc n < eSuc m \<longleftrightarrow> n < m"
   404   by (simp add: eSuc_def less_enat_def split: enat.splits)
   403   by (simp add: eSuc_def less_enat_def split: enat.splits)
   405 
   404 
   406 lemma ile_eSuc [simp]: "n \<le> eSuc n"
   405 lemma ile_eSuc [simp]: "n \<le> eSuc n"
   407   by (simp add: eSuc_def less_eq_enat_def split: enat.splits)
   406   by (simp add: eSuc_def less_eq_enat_def split: enat.splits)
   477 done
   476 done
   478 
   477 
   479 lemma eSuc_max: "eSuc (max x y) = max (eSuc x) (eSuc y)"
   478 lemma eSuc_max: "eSuc (max x y) = max (eSuc x) (eSuc y)"
   480   by (simp add: eSuc_def split: enat.split)
   479   by (simp add: eSuc_def split: enat.split)
   481 
   480 
   482 lemma eSuc_Max: 
   481 lemma eSuc_Max:
   483   assumes "finite A" "A \<noteq> {}"
   482   assumes "finite A" "A \<noteq> {}"
   484   shows "eSuc (Max A) = Max (eSuc ` A)"
   483   shows "eSuc (Max A) = Max (eSuc ` A)"
   485 using assms proof induction
   484 using assms proof induction
   486   case (insert x A)
   485   case (insert x A)
   487   thus ?case by(cases "A = {}")(simp_all add: eSuc_max)
   486   thus ?case by(cases "A = {}")(simp_all add: eSuc_max)