equal
deleted
inserted
replaced
8 imports Main |
8 imports Main |
9 begin |
9 begin |
10 |
10 |
11 text \<open> |
11 text \<open> |
12 Zorn's Lemmas states: if every linear ordered subset of an ordered |
12 Zorn's Lemmas states: if every linear ordered subset of an ordered |
13 set @{text S} has an upper bound in @{text S}, then there exists a |
13 set \<open>S\<close> has an upper bound in \<open>S\<close>, then there exists a |
14 maximal element in @{text S}. In our application, @{text S} is a |
14 maximal element in \<open>S\<close>. In our application, \<open>S\<close> is a |
15 set of sets ordered by set inclusion. Since the union of a chain of |
15 set of sets ordered by set inclusion. Since the union of a chain of |
16 sets is an upper bound for all elements of the chain, the conditions |
16 sets is an upper bound for all elements of the chain, the conditions |
17 of Zorn's lemma can be modified: if @{text S} is non-empty, it |
17 of Zorn's lemma can be modified: if \<open>S\<close> is non-empty, it |
18 suffices to show that for every non-empty chain @{text c} in @{text |
18 suffices to show that for every non-empty chain \<open>c\<close> in \<open>S\<close> the union of \<open>c\<close> also lies in \<open>S\<close>. |
19 S} the union of @{text c} also lies in @{text S}. |
|
20 \<close> |
19 \<close> |
21 |
20 |
22 theorem Zorn's_Lemma: |
21 theorem Zorn's_Lemma: |
23 assumes r: "\<And>c. c \<in> chains S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S" |
22 assumes r: "\<And>c. c \<in> chains S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S" |
24 and aS: "a \<in> S" |
23 and aS: "a \<in> S" |
28 proof |
27 proof |
29 fix c assume "c \<in> chains S" |
28 fix c assume "c \<in> chains S" |
30 show "\<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y" |
29 show "\<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y" |
31 proof cases |
30 proof cases |
32 |
31 |
33 txt \<open>If @{text c} is an empty chain, then every element in |
32 txt \<open>If \<open>c\<close> is an empty chain, then every element in |
34 @{text S} is an upper bound of @{text c}.\<close> |
33 \<open>S\<close> is an upper bound of \<open>c\<close>.\<close> |
35 |
34 |
36 assume "c = {}" |
35 assume "c = {}" |
37 with aS show ?thesis by fast |
36 with aS show ?thesis by fast |
38 |
37 |
39 txt \<open>If @{text c} is non-empty, then @{text "\<Union>c"} is an upper |
38 txt \<open>If \<open>c\<close> is non-empty, then \<open>\<Union>c\<close> is an upper |
40 bound of @{text c}, lying in @{text S}.\<close> |
39 bound of \<open>c\<close>, lying in \<open>S\<close>.\<close> |
41 |
40 |
42 next |
41 next |
43 assume "c \<noteq> {}" |
42 assume "c \<noteq> {}" |
44 show ?thesis |
43 show ?thesis |
45 proof |
44 proof |