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