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;
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@58889
     5
section \<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@61879
    12
  Zorn's Lemmas states: if every linear ordered subset of an ordered set \<open>S\<close>
wenzelm@61879
    13
  has an upper bound in \<open>S\<close>, then there exists a maximal element in \<open>S\<close>. In
wenzelm@61879
    14
  our application, \<open>S\<close> is a set of sets ordered by set inclusion. Since the
wenzelm@61879
    15
  union of a chain of sets is an upper bound for all elements of the chain,
wenzelm@61879
    16
  the conditions of Zorn's lemma can be modified: if \<open>S\<close> is non-empty, it
wenzelm@61879
    17
  suffices to show that for every non-empty chain \<open>c\<close> in \<open>S\<close> the union of \<open>c\<close>
wenzelm@61879
    18
  also lies in \<open>S\<close>.
wenzelm@58744
    19
\<close>
wenzelm@7917
    20
wenzelm@10687
    21
theorem Zorn's_Lemma:
popescua@52183
    22
  assumes r: "\<And>c. c \<in> chains S \<Longrightarrow> \<exists>x. x \<in> c \<Longrightarrow> \<Union>c \<in> S"
wenzelm@13515
    23
    and aS: "a \<in> S"
popescua@52183
    24
  shows "\<exists>y \<in> S. \<forall>z \<in> S. y \<subseteq> z \<longrightarrow> z = y"
wenzelm@9035
    25
proof (rule Zorn_Lemma2)
popescua@52183
    26
  show "\<forall>c \<in> chains S. \<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y"
wenzelm@9035
    27
  proof
popescua@52183
    28
    fix c assume "c \<in> chains S"
wenzelm@10687
    29
    show "\<exists>y \<in> S. \<forall>z \<in> c. z \<subseteq> y"
wenzelm@9035
    30
    proof cases
wenzelm@61879
    31
      txt \<open>If \<open>c\<close> is an empty chain, then every element in \<open>S\<close> is an upper
wenzelm@61879
    32
        bound of \<open>c\<close>.\<close>
wenzelm@7917
    33
wenzelm@13515
    34
      assume "c = {}"
wenzelm@9035
    35
      with aS show ?thesis by fast
wenzelm@7917
    36
wenzelm@61879
    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
wenzelm@61879
    38
        \<open>S\<close>.\<close>
wenzelm@9035
    39
    next
wenzelm@27612
    40
      assume "c \<noteq> {}"
wenzelm@13515
    41
      show ?thesis
wenzelm@13515
    42
      proof
wenzelm@10687
    43
        show "\<forall>z \<in> c. z \<subseteq> \<Union>c" by fast
wenzelm@13515
    44
        show "\<Union>c \<in> S"
wenzelm@9035
    45
        proof (rule r)
wenzelm@58744
    46
          from \<open>c \<noteq> {}\<close> show "\<exists>x. x \<in> c" by fast
popescua@52183
    47
          show "c \<in> chains S" by fact
wenzelm@9035
    48
        qed
wenzelm@9035
    49
      qed
wenzelm@9035
    50
    qed
wenzelm@9035
    51
  qed
wenzelm@9035
    52
qed
wenzelm@7917
    53
wenzelm@10687
    54
end