summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

src/HOL/Hahn_Banach/Zorn_Lemma.thy

changeset 31795 | be3e1cc5005c |

parent 29252 | ea97aa6aeba2 |

child 32960 | 69916a850301 |

--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/HOL/Hahn_Banach/Zorn_Lemma.thy Wed Jun 24 21:46:54 2009 +0200 @@ -0,0 +1,57 @@ +(* Title: HOL/Hahn_Banach/Zorn_Lemma.thy + Author: Gertrud Bauer, TU Munich +*) + +header {* Zorn's Lemma *} + +theory Zorn_Lemma +imports Zorn +begin + +text {* + Zorn's Lemmas states: if every linear ordered subset of an ordered + set @{text S} has an upper bound in @{text S}, then there exists a + maximal element in @{text S}. In our application, @{text S} is a + set of sets ordered by set inclusion. Since the union of a chain of + sets is an upper bound for all elements of the chain, the conditions + of Zorn's lemma can be modified: if @{text S} is non-empty, it + suffices to show that for every non-empty chain @{text c} in @{text + S} the union of @{text c} also lies in @{text S}. +*} + +theorem Zorn's_Lemma: + assumes r: "\<And>c. c \<in> chain S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S" + and aS: "a \<in> S" + shows "\<exists>y \<in> S. \<forall>z \<in> S. y \<subseteq> z \<longrightarrow> y = z" +proof (rule Zorn_Lemma2) + show "\<forall>c \<in> chain S. \<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y" + proof + fix c assume "c \<in> chain S" + show "\<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y" + proof cases + + txt {* If @{text c} is an empty chain, then every element in + @{text S} is an upper bound of @{text c}. *} + + assume "c = {}" + with aS show ?thesis by fast + + txt {* If @{text c} is non-empty, then @{text "\<Union>c"} is an upper + bound of @{text c}, lying in @{text S}. *} + + next + assume "c \<noteq> {}" + show ?thesis + proof + show "\<forall>z \<in> c. z \<subseteq> \<Union>c" by fast + show "\<Union>c \<in> S" + proof (rule r) + from `c \<noteq> {}` show "\<exists>x. x \<in> c" by fast + show "c \<in> chain S" by fact + qed + qed + qed + qed +qed + +end