81 by (simp add: inat_defs split:inat_splits) |
83 by (simp add: inat_defs split:inat_splits) |
82 |
84 |
83 |
85 |
84 subsection "Ordering relations" |
86 subsection "Ordering relations" |
85 |
87 |
|
88 instance inat :: linorder |
|
89 proof |
|
90 fix x :: inat |
|
91 show "x \<le> x" |
|
92 by (simp add: inat_defs split: inat_splits) |
|
93 next |
|
94 fix x y :: inat |
|
95 assume "x \<le> y" and "y \<le> x" thus "x = y" |
|
96 by (simp add: inat_defs split: inat_splits) |
|
97 next |
|
98 fix x y z :: inat |
|
99 assume "x \<le> y" and "y \<le> z" thus "x \<le> z" |
|
100 by (simp add: inat_defs split: inat_splits) |
|
101 next |
|
102 fix x y :: inat |
|
103 show "(x < y) = (x \<le> y \<and> x \<noteq> y)" |
|
104 by (simp add: inat_defs order_less_le split: inat_splits) |
|
105 next |
|
106 fix x y :: inat |
|
107 show "x \<le> y \<or> y \<le> x" |
|
108 by (simp add: inat_defs linorder_linear split: inat_splits) |
|
109 qed |
|
110 |
86 lemma Infty_ilessE [elim!]: "\<infinity> < Fin m ==> R" |
111 lemma Infty_ilessE [elim!]: "\<infinity> < Fin m ==> R" |
87 by (simp add: inat_defs split:inat_splits) |
112 by (simp add: inat_defs split:inat_splits) |
88 |
113 |
89 lemma iless_linear: "m < n \<or> m = n \<or> n < (m::inat)" |
114 lemma iless_linear: "m < n \<or> m = n \<or> n < (m::inat)" |
90 by (simp add: inat_defs split:inat_splits, arith) |
115 by (rule linorder_less_linear) |
91 |
116 |
92 lemma iless_not_refl [simp]: "\<not> n < (n::inat)" |
117 lemma iless_not_refl: "\<not> n < (n::inat)" |
93 by (simp add: inat_defs split:inat_splits) |
118 by (rule order_less_irrefl) |
94 |
119 |
95 lemma iless_trans: "i < j ==> j < k ==> i < (k::inat)" |
120 lemma iless_trans: "i < j ==> j < k ==> i < (k::inat)" |
96 by (simp add: inat_defs split:inat_splits) |
121 by (rule order_less_trans) |
97 |
122 |
98 lemma iless_not_sym: "n < m ==> \<not> m < (n::inat)" |
123 lemma iless_not_sym: "n < m ==> \<not> m < (n::inat)" |
99 by (simp add: inat_defs split:inat_splits) |
124 by (rule order_less_not_sym) |
100 |
125 |
101 lemma Fin_iless_mono [simp]: "(Fin n < Fin m) = (n < m)" |
126 lemma Fin_iless_mono [simp]: "(Fin n < Fin m) = (n < m)" |
102 by (simp add: inat_defs split:inat_splits) |
127 by (simp add: inat_defs split:inat_splits) |
103 |
128 |
104 lemma Fin_iless_Infty [simp]: "Fin n < \<infinity>" |
129 lemma Fin_iless_Infty [simp]: "Fin n < \<infinity>" |
123 by (simp add: inat_defs split:inat_splits) |
148 by (simp add: inat_defs split:inat_splits) |
124 |
149 |
125 |
150 |
126 |
151 |
127 lemma ile_def2: "(m \<le> n) = (m < n \<or> m = (n::inat))" |
152 lemma ile_def2: "(m \<le> n) = (m < n \<or> m = (n::inat))" |
128 by (simp add: inat_defs split:inat_splits, arith) |
153 by (rule order_le_less) |
129 |
154 |
130 lemma ile_refl [simp]: "n \<le> (n::inat)" |
155 lemma ile_refl [simp]: "n \<le> (n::inat)" |
131 by (simp add: inat_defs split:inat_splits) |
156 by (rule order_refl) |
132 |
157 |
133 lemma ile_trans: "i \<le> j ==> j \<le> k ==> i \<le> (k::inat)" |
158 lemma ile_trans: "i \<le> j ==> j \<le> k ==> i \<le> (k::inat)" |
134 by (simp add: inat_defs split:inat_splits) |
159 by (rule order_trans) |
135 |
160 |
136 lemma ile_iless_trans: "i \<le> j ==> j < k ==> i < (k::inat)" |
161 lemma ile_iless_trans: "i \<le> j ==> j < k ==> i < (k::inat)" |
137 by (simp add: inat_defs split:inat_splits) |
162 by (rule order_le_less_trans) |
138 |
163 |
139 lemma iless_ile_trans: "i < j ==> j \<le> k ==> i < (k::inat)" |
164 lemma iless_ile_trans: "i < j ==> j \<le> k ==> i < (k::inat)" |
140 by (simp add: inat_defs split:inat_splits) |
165 by (rule order_less_le_trans) |
141 |
166 |
142 lemma Infty_ub [simp]: "n \<le> \<infinity>" |
167 lemma Infty_ub [simp]: "n \<le> \<infinity>" |
143 by (simp add: inat_defs split:inat_splits) |
168 by (simp add: inat_defs split:inat_splits) |
144 |
169 |
145 lemma i0_lb [simp]: "(0::inat) \<le> n" |
170 lemma i0_lb [simp]: "(0::inat) \<le> n" |
147 |
172 |
148 lemma Infty_ileE [elim!]: "\<infinity> \<le> Fin m ==> R" |
173 lemma Infty_ileE [elim!]: "\<infinity> \<le> Fin m ==> R" |
149 by (simp add: inat_defs split:inat_splits) |
174 by (simp add: inat_defs split:inat_splits) |
150 |
175 |
151 lemma Fin_ile_mono [simp]: "(Fin n \<le> Fin m) = (n \<le> m)" |
176 lemma Fin_ile_mono [simp]: "(Fin n \<le> Fin m) = (n \<le> m)" |
152 by (simp add: inat_defs split:inat_splits, arith) |
177 by (simp add: inat_defs split:inat_splits) |
153 |
178 |
154 lemma ilessI1: "n \<le> m ==> n \<noteq> m ==> n < (m::inat)" |
179 lemma ilessI1: "n \<le> m ==> n \<noteq> m ==> n < (m::inat)" |
155 by (simp add: inat_defs split:inat_splits) |
180 by (rule order_le_neq_trans) |
156 |
181 |
157 lemma ileI1: "m < n ==> iSuc m \<le> n" |
182 lemma ileI1: "m < n ==> iSuc m \<le> n" |
158 by (simp add: inat_defs split:inat_splits) |
183 by (simp add: inat_defs split:inat_splits) |
159 |
184 |
160 lemma Suc_ile_eq: "(Fin (Suc m) \<le> n) = (Fin m < n)" |
185 lemma Suc_ile_eq: "(Fin (Suc m) \<le> n) = (Fin m < n)" |
176 by (simp add: inat_defs split:inat_splits) |
201 by (simp add: inat_defs split:inat_splits) |
177 |
202 |
178 lemma chain_incr: "\<forall>i. \<exists>j. Y i < Y j ==> \<exists>j. Fin k < Y j" |
203 lemma chain_incr: "\<forall>i. \<exists>j. Y i < Y j ==> \<exists>j. Fin k < Y j" |
179 apply (induct_tac k) |
204 apply (induct_tac k) |
180 apply (simp (no_asm) only: Fin_0) |
205 apply (simp (no_asm) only: Fin_0) |
181 apply (fast intro: ile_iless_trans i0_lb) |
206 apply (fast intro: ile_iless_trans [OF i0_lb]) |
182 apply (erule exE) |
207 apply (erule exE) |
183 apply (drule spec) |
208 apply (drule spec) |
184 apply (erule exE) |
209 apply (erule exE) |
185 apply (drule ileI1) |
210 apply (drule ileI1) |
186 apply (rule iSuc_Fin [THEN subst]) |
211 apply (rule iSuc_Fin [THEN subst]) |
187 apply (rule exI) |
212 apply (rule exI) |
188 apply (erule (1) ile_iless_trans) |
213 apply (erule (1) ile_iless_trans) |
189 done |
214 done |
190 |
215 |
|
216 |
|
217 subsection "Well-ordering" |
|
218 |
|
219 lemma less_FinE: |
|
220 "[| n < Fin m; !!k. n = Fin k ==> k < m ==> P |] ==> P" |
|
221 by (induct n) auto |
|
222 |
|
223 lemma less_InftyE: |
|
224 "[| n < Infty; !!k. n = Fin k ==> P |] ==> P" |
|
225 by (induct n) auto |
|
226 |
|
227 lemma inat_less_induct: |
|
228 assumes prem: "!!n. \<forall>m::inat. m < n --> P m ==> P n" shows "P n" |
|
229 proof - |
|
230 have P_Fin: "!!k. P (Fin k)" |
|
231 apply (rule nat_less_induct) |
|
232 apply (rule prem, clarify) |
|
233 apply (erule less_FinE, simp) |
|
234 done |
|
235 show ?thesis |
|
236 proof (induct n) |
|
237 fix nat |
|
238 show "P (Fin nat)" by (rule P_Fin) |
|
239 next |
|
240 show "P Infty" |
|
241 apply (rule prem, clarify) |
|
242 apply (erule less_InftyE) |
|
243 apply (simp add: P_Fin) |
|
244 done |
|
245 qed |
|
246 qed |
|
247 |
|
248 instance inat :: wellorder |
|
249 proof |
|
250 show "wf {(x::inat, y::inat). x < y}" |
|
251 proof (rule wfUNIVI) |
|
252 fix P and x :: inat |
|
253 assume "\<forall>x::inat. (\<forall>y. (y, x) \<in> {(x, y). x < y} \<longrightarrow> P y) \<longrightarrow> P x" |
|
254 hence 1: "!!x::inat. ALL y. y < x --> P y ==> P x" by fast |
|
255 thus "P x" by (rule inat_less_induct) |
|
256 qed |
|
257 qed |
|
258 |
191 end |
259 end |