src/HOL/Real/HahnBanach/ZornLemma.thy
author wenzelm
Sat Dec 16 21:41:51 2000 +0100 (2000-12-16)
changeset 10687 c186279eecea
parent 9035 371f023d3dbd
child 13515 a6a7025fd7e8
permissions -rw-r--r--
tuned HOL/Real/HahnBanach;
wenzelm@7917
     1
(*  Title:      HOL/Real/HahnBanach/ZornLemma.thy
wenzelm@7917
     2
    ID:         $Id$
wenzelm@7917
     3
    Author:     Gertrud Bauer, TU Munich
wenzelm@7917
     4
*)
wenzelm@7917
     5
wenzelm@9035
     6
header {* Zorn's Lemma *}
wenzelm@7917
     7
wenzelm@9035
     8
theory ZornLemma = Aux + Zorn:
wenzelm@7917
     9
wenzelm@10687
    10
text {*
wenzelm@10687
    11
  Zorn's Lemmas states: if every linear ordered subset of an ordered
wenzelm@10687
    12
  set @{text S} has an upper bound in @{text S}, then there exists a
wenzelm@10687
    13
  maximal element in @{text S}.  In our application, @{text S} is a
wenzelm@10687
    14
  set of sets ordered by set inclusion. Since the union of a chain of
wenzelm@10687
    15
  sets is an upper bound for all elements of the chain, the conditions
wenzelm@10687
    16
  of Zorn's lemma can be modified: if @{text S} is non-empty, it
wenzelm@10687
    17
  suffices to show that for every non-empty chain @{text c} in @{text
wenzelm@10687
    18
  S} the union of @{text c} also lies in @{text S}.
wenzelm@10687
    19
*}
wenzelm@7917
    20
wenzelm@10687
    21
theorem Zorn's_Lemma:
wenzelm@10687
    22
  "(\<And>c. c \<in> chain S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S) \<Longrightarrow> a \<in> S
wenzelm@10687
    23
  \<Longrightarrow> \<exists>y \<in> S. \<forall>z \<in> S. y \<subseteq> z \<longrightarrow> y = z"
wenzelm@9035
    24
proof (rule Zorn_Lemma2)
wenzelm@8104
    25
  txt_raw {* \footnote{See
wenzelm@9035
    26
  \url{http://isabelle.in.tum.de/library/HOL/HOL-Real/Zorn.html}} \isanewline *}
wenzelm@10687
    27
  assume r: "\<And>c. c \<in> chain S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S"
wenzelm@10687
    28
  assume aS: "a \<in> S"
wenzelm@10687
    29
  show "\<forall>c \<in> chain S. \<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y"
wenzelm@9035
    30
  proof
wenzelm@10687
    31
    fix c assume "c \<in> chain S"
wenzelm@10687
    32
    show "\<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y"
wenzelm@9035
    33
    proof cases
wenzelm@7917
    34
 
wenzelm@10687
    35
      txt {* If @{text c} is an empty chain, then every element in
wenzelm@10687
    36
      @{text S} is an upper bound of @{text c}. *}
wenzelm@7917
    37
wenzelm@10687
    38
      assume "c = {}" 
wenzelm@9035
    39
      with aS show ?thesis by fast
wenzelm@7917
    40
wenzelm@10687
    41
      txt {* If @{text c} is non-empty, then @{text "\<Union>c"} is an upper
wenzelm@10687
    42
      bound of @{text c}, lying in @{text S}. *}
wenzelm@7917
    43
wenzelm@9035
    44
    next
wenzelm@10687
    45
      assume c: "c \<noteq> {}"
wenzelm@9035
    46
      show ?thesis 
wenzelm@9035
    47
      proof 
wenzelm@10687
    48
        show "\<forall>z \<in> c. z \<subseteq> \<Union>c" by fast
wenzelm@10687
    49
        show "\<Union>c \<in> S" 
wenzelm@9035
    50
        proof (rule r)
wenzelm@10687
    51
          from c show "\<exists>x. x \<in> c" by fast  
wenzelm@9035
    52
        qed
wenzelm@9035
    53
      qed
wenzelm@9035
    54
    qed
wenzelm@9035
    55
  qed
wenzelm@9035
    56
qed
wenzelm@7917
    57
wenzelm@10687
    58
end