31 assumes Sup_upper: "x \<in> A \<Longrightarrow> x \<sqsubseteq> \<Squnion>A" |
31 assumes Sup_upper: "x \<in> A \<Longrightarrow> x \<sqsubseteq> \<Squnion>A" |
32 and Sup_least: "(\<And>x. x \<in> A \<Longrightarrow> x \<sqsubseteq> z) \<Longrightarrow> \<Squnion>A \<sqsubseteq> z" |
32 and Sup_least: "(\<And>x. x \<in> A \<Longrightarrow> x \<sqsubseteq> z) \<Longrightarrow> \<Squnion>A \<sqsubseteq> z" |
33 begin |
33 begin |
34 |
34 |
35 lemma dual_complete_lattice: |
35 lemma dual_complete_lattice: |
36 "class.complete_lattice Sup Inf (op \<ge>) (op >) sup inf \<top> \<bottom>" |
36 "class.complete_lattice Sup Inf sup (op \<ge>) (op >) inf \<top> \<bottom>" |
37 by (auto intro!: class.complete_lattice.intro dual_bounded_lattice) |
37 by (auto intro!: class.complete_lattice.intro dual_bounded_lattice) |
38 (unfold_locales, (fact bot_least top_greatest |
38 (unfold_locales, (fact bot_least top_greatest |
39 Sup_upper Sup_least Inf_lower Inf_greatest)+) |
39 Sup_upper Sup_least Inf_lower Inf_greatest)+) |
40 |
40 |
41 definition INFI :: "'b set \<Rightarrow> ('b \<Rightarrow> 'a) \<Rightarrow> 'a" where |
41 definition INFI :: "'b set \<Rightarrow> ('b \<Rightarrow> 'a) \<Rightarrow> 'a" where |
83 begin |
83 begin |
84 |
84 |
85 lemma INF_foundation_dual [no_atp]: |
85 lemma INF_foundation_dual [no_atp]: |
86 "complete_lattice.SUPR Inf = INFI" |
86 "complete_lattice.SUPR Inf = INFI" |
87 proof (rule ext)+ |
87 proof (rule ext)+ |
88 interpret dual: complete_lattice Sup Inf "op \<ge>" "op >" sup inf \<top> \<bottom> |
88 interpret dual: complete_lattice Sup Inf sup "op \<ge>" "op >" inf \<top> \<bottom> |
89 by (fact dual_complete_lattice) |
89 by (fact dual_complete_lattice) |
90 fix f :: "'b \<Rightarrow> 'a" and A |
90 fix f :: "'b \<Rightarrow> 'a" and A |
91 show "complete_lattice.SUPR Inf A f = (\<Sqinter>a\<in>A. f a)" |
91 show "complete_lattice.SUPR Inf A f = (\<Sqinter>a\<in>A. f a)" |
92 by (simp only: dual.SUP_def INF_def) |
92 by (simp only: dual.SUP_def INF_def) |
93 qed |
93 qed |
94 |
94 |
95 lemma SUP_foundation_dual [no_atp]: |
95 lemma SUP_foundation_dual [no_atp]: |
96 "complete_lattice.INFI Sup = SUPR" |
96 "complete_lattice.INFI Sup = SUPR" |
97 proof (rule ext)+ |
97 proof (rule ext)+ |
98 interpret dual: complete_lattice Sup Inf "op \<ge>" "op >" sup inf \<top> \<bottom> |
98 interpret dual: complete_lattice Sup Inf sup "op \<ge>" "op >" inf \<top> \<bottom> |
99 by (fact dual_complete_lattice) |
99 by (fact dual_complete_lattice) |
100 fix f :: "'b \<Rightarrow> 'a" and A |
100 fix f :: "'b \<Rightarrow> 'a" and A |
101 show "complete_lattice.INFI Sup A f = (\<Squnion>a\<in>A. f a)" |
101 show "complete_lattice.INFI Sup A f = (\<Squnion>a\<in>A. f a)" |
102 by (simp only: dual.INF_def SUP_def) |
102 by (simp only: dual.INF_def SUP_def) |
103 qed |
103 qed |
311 |
311 |
312 lemma Sup_bot_conv (*[simp]*) [no_atp]: |
312 lemma Sup_bot_conv (*[simp]*) [no_atp]: |
313 "\<Squnion>A = \<bottom> \<longleftrightarrow> (\<forall>x\<in>A. x = \<bottom>)" (is ?P) |
313 "\<Squnion>A = \<bottom> \<longleftrightarrow> (\<forall>x\<in>A. x = \<bottom>)" (is ?P) |
314 "\<bottom> = \<Squnion>A \<longleftrightarrow> (\<forall>x\<in>A. x = \<bottom>)" (is ?Q) |
314 "\<bottom> = \<Squnion>A \<longleftrightarrow> (\<forall>x\<in>A. x = \<bottom>)" (is ?Q) |
315 proof - |
315 proof - |
316 interpret dual: complete_lattice Sup Inf "op \<ge>" "op >" sup inf \<top> \<bottom> |
316 interpret dual: complete_lattice Sup Inf sup "op \<ge>" "op >" inf \<top> \<bottom> |
317 by (fact dual_complete_lattice) |
317 by (fact dual_complete_lattice) |
318 from dual.Inf_top_conv show ?P and ?Q by simp_all |
318 from dual.Inf_top_conv show ?P and ?Q by simp_all |
319 qed |
319 qed |
320 |
320 |
321 lemma SUP_bot_conv (*[simp]*): |
321 lemma SUP_bot_conv (*[simp]*): |
405 lemma inf_SUP: |
405 lemma inf_SUP: |
406 "a \<sqinter> (\<Squnion>b\<in>B. f b) = (\<Squnion>b\<in>B. a \<sqinter> f b)" |
406 "a \<sqinter> (\<Squnion>b\<in>B. f b) = (\<Squnion>b\<in>B. a \<sqinter> f b)" |
407 by (simp add: SUP_def inf_Sup image_image) |
407 by (simp add: SUP_def inf_Sup image_image) |
408 |
408 |
409 lemma dual_complete_distrib_lattice: |
409 lemma dual_complete_distrib_lattice: |
410 "class.complete_distrib_lattice Sup Inf (op \<ge>) (op >) sup inf \<top> \<bottom>" |
410 "class.complete_distrib_lattice Sup Inf sup (op \<ge>) (op >) inf \<top> \<bottom>" |
411 apply (rule class.complete_distrib_lattice.intro) |
411 apply (rule class.complete_distrib_lattice.intro) |
412 apply (fact dual_complete_lattice) |
412 apply (fact dual_complete_lattice) |
413 apply (rule class.complete_distrib_lattice_axioms.intro) |
413 apply (rule class.complete_distrib_lattice_axioms.intro) |
414 apply (simp_all only: INF_foundation_dual SUP_foundation_dual inf_Sup sup_Inf) |
414 apply (simp_all only: INF_foundation_dual SUP_foundation_dual inf_Sup sup_Inf) |
415 done |
415 done |
456 |
456 |
457 class complete_boolean_algebra = boolean_algebra + complete_distrib_lattice |
457 class complete_boolean_algebra = boolean_algebra + complete_distrib_lattice |
458 begin |
458 begin |
459 |
459 |
460 lemma dual_complete_boolean_algebra: |
460 lemma dual_complete_boolean_algebra: |
461 "class.complete_boolean_algebra Sup Inf (op \<ge>) (op >) sup inf \<top> \<bottom> (\<lambda>x y. x \<squnion> - y) uminus" |
461 "class.complete_boolean_algebra Sup Inf sup (op \<ge>) (op >) inf \<top> \<bottom> (\<lambda>x y. x \<squnion> - y) uminus" |
462 by (rule class.complete_boolean_algebra.intro, rule dual_complete_distrib_lattice, rule dual_boolean_algebra) |
462 by (rule class.complete_boolean_algebra.intro, rule dual_complete_distrib_lattice, rule dual_boolean_algebra) |
463 |
463 |
464 lemma uminus_Inf: |
464 lemma uminus_Inf: |
465 "- (\<Sqinter>A) = \<Squnion>(uminus ` A)" |
465 "- (\<Sqinter>A) = \<Squnion>(uminus ` A)" |
466 proof (rule antisym) |
466 proof (rule antisym) |
487 |
487 |
488 class complete_linorder = linorder + complete_lattice |
488 class complete_linorder = linorder + complete_lattice |
489 begin |
489 begin |
490 |
490 |
491 lemma dual_complete_linorder: |
491 lemma dual_complete_linorder: |
492 "class.complete_linorder Sup Inf (op \<ge>) (op >) sup inf \<top> \<bottom>" |
492 "class.complete_linorder Sup Inf sup (op \<ge>) (op >) inf \<top> \<bottom>" |
493 by (rule class.complete_linorder.intro, rule dual_complete_lattice, rule dual_linorder) |
493 by (rule class.complete_linorder.intro, rule dual_complete_lattice, rule dual_linorder) |
494 |
494 |
495 lemma Inf_less_iff (*[simp]*): |
495 lemma Inf_less_iff (*[simp]*): |
496 "\<Sqinter>S \<sqsubset> a \<longleftrightarrow> (\<exists>x\<in>S. x \<sqsubset> a)" |
496 "\<Sqinter>S \<sqsubset> a \<longleftrightarrow> (\<exists>x\<in>S. x \<sqsubset> a)" |
497 unfolding not_le [symmetric] le_Inf_iff by auto |
497 unfolding not_le [symmetric] le_Inf_iff by auto |
535 unfolding SUP_def Sup_eq_top_iff by auto |
535 unfolding SUP_def Sup_eq_top_iff by auto |
536 |
536 |
537 lemma Inf_eq_bot_iff (*[simp]*): |
537 lemma Inf_eq_bot_iff (*[simp]*): |
538 "\<Sqinter>A = \<bottom> \<longleftrightarrow> (\<forall>x>\<bottom>. \<exists>i\<in>A. i < x)" |
538 "\<Sqinter>A = \<bottom> \<longleftrightarrow> (\<forall>x>\<bottom>. \<exists>i\<in>A. i < x)" |
539 proof - |
539 proof - |
540 interpret dual: complete_linorder Sup Inf "op \<ge>" "op >" sup inf \<top> \<bottom> |
540 interpret dual: complete_linorder Sup Inf sup "op \<ge>" "op >" inf \<top> \<bottom> |
541 by (fact dual_complete_linorder) |
541 by (fact dual_complete_linorder) |
542 from dual.Sup_eq_top_iff show ?thesis . |
542 from dual.Sup_eq_top_iff show ?thesis . |
543 qed |
543 qed |
544 |
544 |
545 lemma INF_eq_bot_iff (*[simp]*): |
545 lemma INF_eq_bot_iff (*[simp]*): |