src/ZF/Constructible/Rank.thy
changeset 71417 89d05db6dd1f
parent 69593 3dda49e08b9d
child 72797 402afc68f2f9
equal deleted inserted replaced
71416:6a1c1d1ce6ae 71417:89d05db6dd1f
   107  apply (rule_tac x1=x and A1="Order.pred(A,y,r)" in 
   107  apply (rule_tac x1=x and A1="Order.pred(A,y,r)" in 
   108           wellordered_iso_predD [THEN notE]) 
   108           wellordered_iso_predD [THEN notE]) 
   109    apply (blast intro: wellordered_subset [OF _ pred_subset]) 
   109    apply (blast intro: wellordered_subset [OF _ pred_subset]) 
   110   apply (simp add: trans_pred_pred_eq)
   110   apply (simp add: trans_pred_pred_eq)
   111   apply (blast intro: Ord_iso_implies_eq ord_iso_sym ord_iso_trans) 
   111   apply (blast intro: Ord_iso_implies_eq ord_iso_sym ord_iso_trans) 
   112  apply (simp_all add: pred_iff pred_closed converse_closed comp_closed)
   112  apply (simp_all add: pred_iff)
   113 txt\<open>case \<^term>\<open>j<i\<close> also yields a contradiction\<close>
   113 txt\<open>case \<^term>\<open>j<i\<close> also yields a contradiction\<close>
   114 apply (frule restrict_ord_iso2, assumption+) 
   114 apply (frule restrict_ord_iso2, assumption+) 
   115 apply (frule ord_iso_sym [THEN ord_iso_is_bij, THEN bij_is_fun]) 
   115 apply (frule ord_iso_sym [THEN ord_iso_is_bij, THEN bij_is_fun]) 
   116 apply (frule apply_type, blast intro: ltD) 
   116 apply (frule apply_type, blast intro: ltD) 
   117   \<comment> \<open>thus \<^term>\<open>converse(f)`j \<in> Order.pred(A,x,r)\<close>\<close>
   117   \<comment> \<open>thus \<^term>\<open>converse(f)`j \<in> Order.pred(A,x,r)\<close>\<close>
   160 lemma (in M_ordertype) omap_iff:
   160 lemma (in M_ordertype) omap_iff:
   161      "[| omap(M,A,r,f); M(A); M(f) |] 
   161      "[| omap(M,A,r,f); M(A); M(f) |] 
   162       ==> z \<in> f \<longleftrightarrow>
   162       ==> z \<in> f \<longleftrightarrow>
   163           (\<exists>a\<in>A. \<exists>x[M]. \<exists>g[M]. z = <a,x> & Ord(x) & 
   163           (\<exists>a\<in>A. \<exists>x[M]. \<exists>g[M]. z = <a,x> & Ord(x) & 
   164                                 g \<in> ord_iso(Order.pred(A,a,r),r,x,Memrel(x)))"
   164                                 g \<in> ord_iso(Order.pred(A,a,r),r,x,Memrel(x)))"
   165 apply (simp add: omap_def Memrel_closed pred_closed) 
   165 apply (simp add: omap_def) 
   166 apply (rule iffI)
   166 apply (rule iffI)
   167  apply (drule_tac [2] x=z in rspec)
   167  apply (drule_tac [2] x=z in rspec)
   168  apply (drule_tac x=z in rspec)
   168  apply (drule_tac x=z in rspec)
   169  apply (blast dest: transM)+
   169  apply (blast dest: transM)+
   170 done
   170 done
   220 done
   220 done
   221 
   221 
   222 lemma (in M_ordertype) domain_omap:
   222 lemma (in M_ordertype) domain_omap:
   223      "[| omap(M,A,r,f);  M(A); M(r); M(B); M(f) |] 
   223      "[| omap(M,A,r,f);  M(A); M(r); M(B); M(f) |] 
   224       ==> domain(f) = obase(M,A,r)"
   224       ==> domain(f) = obase(M,A,r)"
   225 apply (simp add: domain_closed obase_def) 
   225 apply (simp add: obase_def) 
   226 apply (rule equality_iffI) 
   226 apply (rule equality_iffI) 
   227 apply (simp add: domain_iff omap_iff, blast) 
   227 apply (simp add: domain_iff omap_iff, blast) 
   228 done
   228 done
   229 
   229 
   230 lemma (in M_ordertype) omap_subset: 
   230 lemma (in M_ordertype) omap_subset: 
   352 apply (simp add: omap_def) 
   352 apply (simp add: omap_def) 
   353 apply (insert omap_replacement [of A r])
   353 apply (insert omap_replacement [of A r])
   354 apply (simp add: strong_replacement_def) 
   354 apply (simp add: strong_replacement_def) 
   355 apply (drule_tac x="obase(M,A,r)" in rspec) 
   355 apply (drule_tac x="obase(M,A,r)" in rspec) 
   356  apply (simp add: obase_exists) 
   356  apply (simp add: obase_exists) 
   357 apply (simp add: Memrel_closed pred_closed obase_def)
   357 apply (simp add: obase_def)
   358 apply (erule impE) 
   358 apply (erule impE) 
   359  apply (clarsimp simp add: univalent_def)
   359  apply (clarsimp simp add: univalent_def)
   360  apply (blast intro: Ord_iso_implies_eq ord_iso_sym ord_iso_trans, clarify)  
   360  apply (blast intro: Ord_iso_implies_eq ord_iso_sym ord_iso_trans, clarify)  
   361 apply (rule_tac x=Y in rexI) 
   361 apply (rule_tac x=Y in rexI) 
   362 apply (simp add: Memrel_closed pred_closed obase_def, blast, assumption)
   362 apply (simp add: obase_def, blast, assumption)
   363 done
   363 done
   364 
       
   365 declare rall_simps [simp] rex_simps [simp]
       
   366 
   364 
   367 lemma (in M_ordertype) otype_exists:
   365 lemma (in M_ordertype) otype_exists:
   368      "[| wellordered(M,A,r); M(A); M(r) |] ==> \<exists>i[M]. otype(M,A,r,i)"
   366      "[| wellordered(M,A,r); M(A); M(r) |] ==> \<exists>i[M]. otype(M,A,r,i)"
   369 apply (insert omap_exists [of A r])  
   367 apply (insert omap_exists [of A r])  
   370 apply (simp add: otype_def, safe)
   368 apply (simp add: otype_def, safe)
   377       ==> \<exists>f[M]. (\<exists>i[M]. Ord(i) & f \<in> ord_iso(A, r, i, Memrel(i)))"
   375       ==> \<exists>f[M]. (\<exists>i[M]. Ord(i) & f \<in> ord_iso(A, r, i, Memrel(i)))"
   378 apply (insert obase_exists [of A r] omap_exists [of A r] otype_exists [of A r], simp, clarify)
   376 apply (insert obase_exists [of A r] omap_exists [of A r] otype_exists [of A r], simp, clarify)
   379 apply (rename_tac i) 
   377 apply (rename_tac i) 
   380 apply (subgoal_tac "Ord(i)", blast intro: omap_ord_iso_otype)
   378 apply (subgoal_tac "Ord(i)", blast intro: omap_ord_iso_otype)
   381 apply (rule Ord_otype) 
   379 apply (rule Ord_otype) 
   382     apply (force simp add: otype_def range_closed) 
   380     apply (force simp add: otype_def) 
   383    apply (simp_all add: wellordered_is_trans_on) 
   381    apply (simp_all add: wellordered_is_trans_on) 
   384 done
   382 done
   385 
   383 
   386 
   384 
   387 lemma (in M_ordertype) relativized_imp_well_ord: 
   385 lemma (in M_ordertype) relativized_imp_well_ord: 
   482 lemma (in M_ord_arith) is_oadd_fun_iff:
   480 lemma (in M_ord_arith) is_oadd_fun_iff:
   483    "[| a\<le>j; M(i); M(j); M(a); M(f) |] 
   481    "[| a\<le>j; M(i); M(j); M(a); M(f) |] 
   484     ==> is_oadd_fun(M,i,j,a,f) \<longleftrightarrow>
   482     ==> is_oadd_fun(M,i,j,a,f) \<longleftrightarrow>
   485         f \<in> a \<rightarrow> range(f) & (\<forall>x. M(x) \<longrightarrow> x < a \<longrightarrow> f`x = i \<union> f``x)"
   483         f \<in> a \<rightarrow> range(f) & (\<forall>x. M(x) \<longrightarrow> x < a \<longrightarrow> f`x = i \<union> f``x)"
   486 apply (frule lt_Ord) 
   484 apply (frule lt_Ord) 
   487 apply (simp add: is_oadd_fun_def Memrel_closed Un_closed 
   485 apply (simp add: is_oadd_fun_def  
   488              relation2_def is_recfun_abs [of "%x g. i \<union> g``x"]
   486              relation2_def is_recfun_abs [of "%x g. i \<union> g``x"]
   489              image_closed is_recfun_iff_equation  
   487              is_recfun_iff_equation  
   490              Ball_def lt_trans [OF ltI, of _ a] lt_Memrel)
   488              Ball_def lt_trans [OF ltI, of _ a] lt_Memrel)
   491 apply (simp add: lt_def) 
   489 apply (simp add: lt_def) 
   492 apply (blast dest: transM) 
   490 apply (blast dest: transM) 
   493 done
   491 done
   494 
   492 
   557 lemma (in M_ord_arith) oadd_closed [intro,simp]:
   555 lemma (in M_ord_arith) oadd_closed [intro,simp]:
   558     "[| M(i); M(j) |] ==> M(i++j)"
   556     "[| M(i); M(j) |] ==> M(i++j)"
   559 apply (simp add: oadd_eq_if_raw_oadd, clarify) 
   557 apply (simp add: oadd_eq_if_raw_oadd, clarify) 
   560 apply (simp add: raw_oadd_eq_oadd) 
   558 apply (simp add: raw_oadd_eq_oadd) 
   561 apply (frule exists_oadd_fun [of j i], auto)
   559 apply (frule exists_oadd_fun [of j i], auto)
   562 apply (simp add: apply_closed is_oadd_fun_iff_oadd [symmetric]) 
   560 apply (simp add: is_oadd_fun_iff_oadd [symmetric]) 
   563 done
   561 done
   564 
   562 
   565 
   563 
   566 subsubsection\<open>Ordinal Multiplication\<close>
   564 subsubsection\<open>Ordinal Multiplication\<close>
   567 
   565 
   603      ==> M(THE z. omult_eqns(i, x, g, z))"
   601      ==> M(THE z. omult_eqns(i, x, g, z))"
   604 apply (case_tac "Ord(x)")
   602 apply (case_tac "Ord(x)")
   605  prefer 2 apply (simp add: omult_eqns_Not) \<comment> \<open>trivial, non-Ord case\<close>
   603  prefer 2 apply (simp add: omult_eqns_Not) \<comment> \<open>trivial, non-Ord case\<close>
   606 apply (erule Ord_cases) 
   604 apply (erule Ord_cases) 
   607   apply (simp add: omult_eqns_0)
   605   apply (simp add: omult_eqns_0)
   608  apply (simp add: omult_eqns_succ apply_closed oadd_closed) 
   606  apply (simp add: omult_eqns_succ) 
   609 apply (simp add: omult_eqns_Limit) 
   607 apply (simp add: omult_eqns_Limit) 
   610 done
   608 done
   611 
   609 
   612 lemma (in M_ord_arith) exists_omult:
   610 lemma (in M_ord_arith) exists_omult:
   613     "[| Ord(j);  M(i);  M(j) |]
   611     "[| Ord(j);  M(i);  M(j) |]
   640 by (simp add: is_omult_fun_def omult_eqns_def lt_def, blast) 
   638 by (simp add: is_omult_fun_def omult_eqns_def lt_def, blast) 
   641 
   639 
   642 lemma (in M_ord_arith) is_omult_fun_apply_Limit:
   640 lemma (in M_ord_arith) is_omult_fun_apply_Limit:
   643     "[| x < j; Limit(x); M(j); M(f); is_omult_fun(M,i,j,f) |] 
   641     "[| x < j; Limit(x); M(j); M(f); is_omult_fun(M,i,j,f) |] 
   644      ==> f ` x = (\<Union>y\<in>x. f`y)"
   642      ==> f ` x = (\<Union>y\<in>x. f`y)"
   645 apply (simp add: is_omult_fun_def omult_eqns_def domain_closed lt_def, clarify)
   643 apply (simp add: is_omult_fun_def omult_eqns_def lt_def, clarify)
   646 apply (drule subset_trans [OF OrdmemD], assumption+)  
   644 apply (drule subset_trans [OF OrdmemD], assumption+)  
   647 apply (simp add: ball_conj_distrib omult_Limit image_function)
   645 apply (simp add: ball_conj_distrib omult_Limit image_function)
   648 done
   646 done
   649 
   647 
   650 lemma (in M_ord_arith) is_omult_fun_eq_omult:
   648 lemma (in M_ord_arith) is_omult_fun_eq_omult:
   903    apply (simp_all add: transM [of a])
   901    apply (simp_all add: transM [of a])
   904 txt\<open>We have used equations for wellfoundedrank and now must use some
   902 txt\<open>We have used equations for wellfoundedrank and now must use some
   905     for  \<open>is_recfun\<close>.\<close>
   903     for  \<open>is_recfun\<close>.\<close>
   906 apply (rule_tac a=a in rangeI)
   904 apply (rule_tac a=a in rangeI)
   907 apply (simp add: is_recfun_type [THEN apply_iff] vimage_singleton_iff
   905 apply (simp add: is_recfun_type [THEN apply_iff] vimage_singleton_iff
   908                  r_into_trancl apply_recfun r_into_trancl)
   906                  r_into_trancl apply_recfun)
   909 done
   907 done
   910 
   908 
   911 
   909 
   912 lemma (in M_wfrank) wellfounded_imp_subset_rvimage:
   910 lemma (in M_wfrank) wellfounded_imp_subset_rvimage:
   913      "[|wellfounded(M,r); r \<subseteq> A*A; M(r); M(A)|]
   911      "[|wellfounded(M,r); r \<subseteq> A*A; M(r); M(A)|]