equal
deleted
inserted
replaced
288 by (unfold Memrel_def, blast) |
288 by (unfold Memrel_def, blast) |
289 |
289 |
290 lemma Memrel_1 [simp]: "Memrel(1) = 0" |
290 lemma Memrel_1 [simp]: "Memrel(1) = 0" |
291 by (unfold Memrel_def, blast) |
291 by (unfold Memrel_def, blast) |
292 |
292 |
|
293 lemma relation_Memrel: "relation(Memrel(A))" |
|
294 by (simp add: relation_def Memrel_def, blast) |
|
295 |
293 (*The membership relation (as a set) is well-founded. |
296 (*The membership relation (as a set) is well-founded. |
294 Proof idea: show A<=B by applying the foundation axiom to A-B *) |
297 Proof idea: show A<=B by applying the foundation axiom to A-B *) |
295 lemma wf_Memrel: "wf(Memrel(A))" |
298 lemma wf_Memrel: "wf(Memrel(A))" |
296 apply (unfold wf_def) |
299 apply (unfold wf_def) |
297 apply (rule foundation [THEN disjE, THEN allI], erule disjI1, blast) |
300 apply (rule foundation [THEN disjE, THEN allI], erule disjI1, blast) |
314 lemma Transset_induct: |
317 lemma Transset_induct: |
315 "[| i: k; Transset(k); |
318 "[| i: k; Transset(k); |
316 !!x.[| x: k; ALL y:x. P(y) |] ==> P(x) |] |
319 !!x.[| x: k; ALL y:x. P(y) |] ==> P(x) |] |
317 ==> P(i)" |
320 ==> P(i)" |
318 apply (simp add: Transset_def) |
321 apply (simp add: Transset_def) |
319 apply (erule wf_Memrel [THEN wf_induct2], blast) |
322 apply (erule wf_Memrel [THEN wf_induct2], blast+) |
320 apply blast |
|
321 done |
323 done |
322 |
324 |
323 (*Induction over an ordinal*) |
325 (*Induction over an ordinal*) |
324 lemmas Ord_induct = Transset_induct [OF _ Ord_is_Transset] |
326 lemmas Ord_induct = Transset_induct [OF _ Ord_is_Transset] |
325 |
327 |
402 |
404 |
403 lemma zero_le_succ_iff [iff]: "0 le succ(x) <-> Ord(x)" |
405 lemma zero_le_succ_iff [iff]: "0 le succ(x) <-> Ord(x)" |
404 by (blast intro: Ord_0_le elim: ltE) |
406 by (blast intro: Ord_0_le elim: ltE) |
405 |
407 |
406 lemma subset_imp_le: "[| j<=i; Ord(i); Ord(j) |] ==> j le i" |
408 lemma subset_imp_le: "[| j<=i; Ord(i); Ord(j) |] ==> j le i" |
407 apply (rule not_lt_iff_le [THEN iffD1], assumption) |
409 apply (rule not_lt_iff_le [THEN iffD1], assumption+) |
408 apply assumption |
|
409 apply (blast elim: ltE mem_irrefl) |
410 apply (blast elim: ltE mem_irrefl) |
410 done |
411 done |
411 |
412 |
412 lemma le_imp_subset: "i le j ==> i<=j" |
413 lemma le_imp_subset: "i le j ==> i<=j" |
413 by (blast dest: OrdmemD elim: ltE leE) |
414 by (blast dest: OrdmemD elim: ltE leE) |