src/ZF/Ordinal.thy
changeset 13269 3ba9be497c33
parent 13243 ba53d07d32d5
child 13356 c9cfe1638bf2
equal deleted inserted replaced
13268:240509babf00 13269:3ba9be497c33
   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)