src/HOL/Hahn_Banach/Zorn_Lemma.thy
 author wenzelm Sat Nov 04 15:24:40 2017 +0100 (20 months ago) changeset 67003 49850a679c2c parent 61879 e4f9d8f094fe permissions -rw-r--r--
more robust sorted_entries;
```     1 (*  Title:      HOL/Hahn_Banach/Zorn_Lemma.thy
```
```     2     Author:     Gertrud Bauer, TU Munich
```
```     3 *)
```
```     4
```
```     5 section \<open>Zorn's Lemma\<close>
```
```     6
```
```     7 theory Zorn_Lemma
```
```     8 imports Main
```
```     9 begin
```
```    10
```
```    11 text \<open>
```
```    12   Zorn's Lemmas states: if every linear ordered subset of an ordered set \<open>S\<close>
```
```    13   has an upper bound in \<open>S\<close>, then there exists a maximal element in \<open>S\<close>. In
```
```    14   our application, \<open>S\<close> is a set of sets ordered by set inclusion. Since the
```
```    15   union of a chain of sets is an upper bound for all elements of the chain,
```
```    16   the conditions of Zorn's lemma can be modified: if \<open>S\<close> is non-empty, it
```
```    17   suffices to show that for every non-empty chain \<open>c\<close> in \<open>S\<close> the union of \<open>c\<close>
```
```    18   also lies in \<open>S\<close>.
```
```    19 \<close>
```
```    20
```
```    21 theorem Zorn's_Lemma:
```
```    22   assumes r: "\<And>c. c \<in> chains S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S"
```
```    23     and aS: "a \<in> S"
```
```    24   shows "\<exists>y \<in> S. \<forall>z \<in> S. y \<subseteq> z \<longrightarrow> z = y"
```
```    25 proof (rule Zorn_Lemma2)
```
```    26   show "\<forall>c \<in> chains S. \<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y"
```
```    27   proof
```
```    28     fix c assume "c \<in> chains S"
```
```    29     show "\<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y"
```
```    30     proof cases
```
```    31       txt \<open>If \<open>c\<close> is an empty chain, then every element in \<open>S\<close> is an upper
```
```    32         bound of \<open>c\<close>.\<close>
```
```    33
```
```    34       assume "c = {}"
```
```    35       with aS show ?thesis by fast
```
```    36
```
```    37       txt \<open>If \<open>c\<close> is non-empty, then \<open>\<Union>c\<close> is an upper bound of \<open>c\<close>, lying in
```
```    38         \<open>S\<close>.\<close>
```
```    39     next
```
```    40       assume "c \<noteq> {}"
```
```    41       show ?thesis
```
```    42       proof
```
```    43         show "\<forall>z \<in> c. z \<subseteq> \<Union>c" by fast
```
```    44         show "\<Union>c \<in> S"
```
```    45         proof (rule r)
```
```    46           from \<open>c \<noteq> {}\<close> show "\<exists>x. x \<in> c" by fast
```
```    47           show "c \<in> chains S" by fact
```
```    48         qed
```
```    49       qed
```
```    50     qed
```
```    51   qed
```
```    52 qed
```
```    53
```
```    54 end
```