equal
deleted
inserted
replaced
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) |