equal
deleted
inserted
replaced
663 assume ?B thus ?A apply(intro inFr.Base) using assms by auto |
663 assume ?B thus ?A apply(intro inFr.Base) using assms by auto |
664 next |
664 next |
665 assume ?C then obtain tr where |
665 assume ?C then obtain tr where |
666 tr_tr0: "Inr tr \<in> cont tr0" and t_tr: "inFr (ns - {root tr0}) tr t" |
666 tr_tr0: "Inr tr \<in> cont tr0" and t_tr: "inFr (ns - {root tr0}) tr t" |
667 unfolding inFrr_def by auto |
667 unfolding inFrr_def by auto |
668 def tr1 \<equiv> "hsubst tr" |
668 define tr1 where "tr1 = hsubst tr" |
669 have 1: "inFr ns tr1 t" using t_tr unfolding tr1_def using inFr_hsubst_minus by auto |
669 have 1: "inFr ns tr1 t" using t_tr unfolding tr1_def using inFr_hsubst_minus by auto |
670 have "Inr tr1 \<in> cont (hsubst tr0)" unfolding tr1_def using tr_tr0 by auto |
670 have "Inr tr1 \<in> cont (hsubst tr0)" unfolding tr1_def using tr_tr0 by auto |
671 thus ?A using 1 inFr.Ind assms by (metis root_hsubst) |
671 thus ?A using 1 inFr.Ind assms by (metis root_hsubst) |
672 qed |
672 qed |
673 |
673 |
687 lemma reg_def2: "reg f tr \<longleftrightarrow> (\<forall> ns tr'. subtr ns tr' tr \<longrightarrow> tr' = f (root tr'))" |
687 lemma reg_def2: "reg f tr \<longleftrightarrow> (\<forall> ns tr'. subtr ns tr' tr \<longrightarrow> tr' = f (root tr'))" |
688 unfolding reg_def using subtr_mono by (metis subset_UNIV) |
688 unfolding reg_def using subtr_mono by (metis subset_UNIV) |
689 |
689 |
690 lemma regular_def2: "regular tr \<longleftrightarrow> (\<exists> f. reg f tr \<and> (\<forall> n. root (f n) = n))" |
690 lemma regular_def2: "regular tr \<longleftrightarrow> (\<exists> f. reg f tr \<and> (\<forall> n. root (f n) = n))" |
691 unfolding regular_def proof safe |
691 unfolding regular_def proof safe |
692 fix f assume f: "reg f tr" |
692 fix f |
693 def g \<equiv> "\<lambda> n. if inItr UNIV tr n then f n else deftr n" |
693 assume f: "reg f tr" |
|
694 define g where "g n = (if inItr UNIV tr n then f n else deftr n)" for n |
694 show "\<exists>g. reg g tr \<and> (\<forall>n. root (g n) = n)" |
695 show "\<exists>g. reg g tr \<and> (\<forall>n. root (g n) = n)" |
695 apply(rule exI[of _ g]) |
696 apply(rule exI[of _ g]) |
696 using f deftr_simps(1) unfolding g_def reg_def apply safe |
697 using f deftr_simps(1) unfolding g_def reg_def apply safe |
697 apply (metis (lifting) inItr.Base subtr_inItr subtr_rootL_in) |
698 apply (metis (lifting) inItr.Base subtr_inItr subtr_rootL_in) |
698 by (metis (full_types) inItr_subtr) |
699 by (metis (full_types) inItr_subtr) |
1167 (is "Lr ns n \<subseteq> {?F tns K | tns K. (n,tns) \<in> P \<and> ?\<phi> tns K}") |
1168 (is "Lr ns n \<subseteq> {?F tns K | tns K. (n,tns) \<in> P \<and> ?\<phi> tns K}") |
1168 proof safe |
1169 proof safe |
1169 fix ts assume "ts \<in> Lr ns n" |
1170 fix ts assume "ts \<in> Lr ns n" |
1170 then obtain tr where dtr: "wf tr" and r: "root tr = n" and tr: "regular tr" |
1171 then obtain tr where dtr: "wf tr" and r: "root tr = n" and tr: "regular tr" |
1171 and ts: "ts = Fr ns tr" unfolding Lr_def by auto |
1172 and ts: "ts = Fr ns tr" unfolding Lr_def by auto |
1172 def tns \<equiv> "(id \<oplus> root) ` (cont tr)" |
1173 define tns where "tns = (id \<oplus> root) ` (cont tr)" |
1173 def K \<equiv> "\<lambda> n'. Fr (ns - {n}) (subtrOf tr n')" |
1174 define K where "K n' = Fr (ns - {n}) (subtrOf tr n')" for n' |
1174 show "\<exists>tns K. ts = ?F tns K \<and> (n, tns) \<in> P \<and> ?\<phi> tns K" |
1175 show "\<exists>tns K. ts = ?F tns K \<and> (n, tns) \<in> P \<and> ?\<phi> tns K" |
1175 apply(rule exI[of _ tns], rule exI[of _ K]) proof(intro conjI allI impI) |
1176 apply(rule exI[of _ tns], rule exI[of _ K]) proof(intro conjI allI impI) |
1176 show "ts = Inl -` tns \<union> \<Union>{K n' |n'. Inr n' \<in> tns}" |
1177 show "ts = Inl -` tns \<union> \<Union>{K n' |n'. Inr n' \<in> tns}" |
1177 unfolding ts regular_Fr[OF tr n[unfolded r[symmetric]]] |
1178 unfolding ts regular_Fr[OF tr n[unfolded r[symmetric]]] |
1178 unfolding tns_def K_def r[symmetric] |
1179 unfolding tns_def K_def r[symmetric] |
1220 unfolding L_def mem_Collect_eq by auto |
1221 unfolding L_def mem_Collect_eq by auto |
1221 } |
1222 } |
1222 then obtain ftr where 0: "\<And> n'. Inr n' \<in> tns \<Longrightarrow> |
1223 then obtain ftr where 0: "\<And> n'. Inr n' \<in> tns \<Longrightarrow> |
1223 K n' = Fr (ns - {n}) (ftr n') \<and> wf (ftr n') \<and> root (ftr n') = n'" |
1224 K n' = Fr (ns - {n}) (ftr n') \<and> wf (ftr n') \<and> root (ftr n') = n'" |
1224 by metis |
1225 by metis |
1225 def tr \<equiv> "Node n ((id \<oplus> ftr) ` tns)" def tr' \<equiv> "hsubst tr tr" |
1226 define tr where "tr = Node n ((id \<oplus> ftr) ` tns)" |
|
1227 define tr' where "tr' = hsubst tr tr" |
1226 have rtr: "root tr = n" and ctr: "cont tr = (id \<oplus> ftr) ` tns" |
1228 have rtr: "root tr = n" and ctr: "cont tr = (id \<oplus> ftr) ` tns" |
1227 unfolding tr_def by (simp, metis P cont_Node finite_imageI finite_in_P) |
1229 unfolding tr_def by (simp, metis P cont_Node finite_imageI finite_in_P) |
1228 have prtr: "prodOf tr = tns" apply(rule Inl_Inr_image_cong) |
1230 have prtr: "prodOf tr = tns" apply(rule Inl_Inr_image_cong) |
1229 unfolding ctr apply simp apply simp apply safe |
1231 unfolding ctr apply simp apply simp apply safe |
1230 using 0 unfolding image_def apply force apply simp by (metis 0 vimageI2) |
1232 using 0 unfolding image_def apply force apply simp by (metis 0 vimageI2) |