equal
deleted
inserted
replaced
29 show "\<exists>a\<in>A. \<forall>a'\<in>A. (a', a) \<notin> r \<union>o r'" |
29 show "\<exists>a\<in>A. \<forall>a'\<in>A. (a', a) \<notin> r \<union>o r'" |
30 proof(cases "B = {}") |
30 proof(cases "B = {}") |
31 assume Case1: "B \<noteq> {}" |
31 assume Case1: "B \<noteq> {}" |
32 hence "B \<noteq> {} \<and> B \<le> Field r" using B_def by auto |
32 hence "B \<noteq> {} \<and> B \<le> Field r" using B_def by auto |
33 then obtain a where 1: "a \<in> B" and 2: "\<forall>a1 \<in> B. (a1,a) \<notin> r" |
33 then obtain a where 1: "a \<in> B" and 2: "\<forall>a1 \<in> B. (a1,a) \<notin> r" |
34 using WF unfolding wf_eq_minimal2 by metis |
34 using WF unfolding wf_eq_minimal2 by blast |
35 hence 3: "a \<in> Field r \<and> a \<notin> Field r'" using B_def FLD by auto |
35 hence 3: "a \<in> Field r \<and> a \<notin> Field r'" using B_def FLD by auto |
36 (* *) |
36 (* *) |
37 have "\<forall>a1 \<in> A. (a1,a) \<notin> r Osum r'" |
37 have "\<forall>a1 \<in> A. (a1,a) \<notin> r Osum r'" |
38 proof(intro ballI) |
38 proof(intro ballI) |
39 fix a1 assume **: "a1 \<in> A" |
39 fix a1 assume **: "a1 \<in> A" |
57 thus ?thesis using 1 B_def by auto |
57 thus ?thesis using 1 B_def by auto |
58 next |
58 next |
59 assume Case2: "B = {}" |
59 assume Case2: "B = {}" |
60 hence 1: "A \<noteq> {} \<and> A \<le> Field r'" using * ** B_def by auto |
60 hence 1: "A \<noteq> {} \<and> A \<le> Field r'" using * ** B_def by auto |
61 then obtain a' where 2: "a' \<in> A" and 3: "\<forall>a1' \<in> A. (a1',a') \<notin> r'" |
61 then obtain a' where 2: "a' \<in> A" and 3: "\<forall>a1' \<in> A. (a1',a') \<notin> r'" |
62 using WF' unfolding wf_eq_minimal2 by metis |
62 using WF' unfolding wf_eq_minimal2 by blast |
63 hence 4: "a' \<in> Field r' \<and> a' \<notin> Field r" using 1 FLD by blast |
63 hence 4: "a' \<in> Field r' \<and> a' \<notin> Field r" using 1 FLD by blast |
64 (* *) |
64 (* *) |
65 have "\<forall>a1' \<in> A. (a1',a') \<notin> r Osum r'" |
65 have "\<forall>a1' \<in> A. (a1',a') \<notin> r Osum r'" |
66 proof(unfold Osum_def, auto simp add: 3) |
66 proof(unfold Osum_def, auto simp add: 3) |
67 fix a1' assume "(a1', a') \<in> r" |
67 fix a1' assume "(a1', a') \<in> r" |
336 using FLD unfolding Field_def by blast |
336 using FLD unfolding Field_def by blast |
337 hence "wf((r' - Id) \<union> (Field r \<times> Field r'))" |
337 hence "wf((r' - Id) \<union> (Field r \<times> Field r'))" |
338 using 1 WF' wf_Un[of "Field r \<times> Field r'" "r' - Id"] |
338 using 1 WF' wf_Un[of "Field r \<times> Field r'" "r' - Id"] |
339 by (auto simp add: Un_commute) |
339 by (auto simp add: Un_commute) |
340 } |
340 } |
341 ultimately have ?thesis by (metis wf_subset) |
341 ultimately have ?thesis using wf_subset by blast |
342 } |
342 } |
343 moreover |
343 moreover |
344 {assume Case22: "r' \<le> Id" |
344 {assume Case22: "r' \<le> Id" |
345 hence "(r Osum r') - Id \<le> (r - Id) \<union> (Field r \<times> Field r')" |
345 hence "(r Osum r') - Id \<le> (r - Id) \<union> (Field r \<times> Field r')" |
346 using Osum_minus_Id2[of r' r] by simp |
346 using Osum_minus_Id2[of r' r] by simp |
349 using FLD unfolding Field_def by blast |
349 using FLD unfolding Field_def by blast |
350 hence "wf((r - Id) \<union> (Field r \<times> Field r'))" |
350 hence "wf((r - Id) \<union> (Field r \<times> Field r'))" |
351 using 1 WF wf_Un[of "r - Id" "Field r \<times> Field r'"] |
351 using 1 WF wf_Un[of "r - Id" "Field r \<times> Field r'"] |
352 by (auto simp add: Un_commute) |
352 by (auto simp add: Un_commute) |
353 } |
353 } |
354 ultimately have ?thesis by (metis wf_subset) |
354 ultimately have ?thesis using wf_subset by blast |
355 } |
355 } |
356 ultimately show ?thesis by blast |
356 ultimately show ?thesis by blast |
357 qed |
357 qed |
358 |
358 |
359 lemma Osum_Well_order: |
359 lemma Osum_Well_order: |