$ \newcommand{\exi}{\exists\,} \newcommand{\all}{\forall} \newcommand{\equ}{\!=\!} \newcommand{\nequ}{\!\neq\!} \newcommand{\amp}{\;\&\;} \renewcommand{\Set}[2]{\left\{\;#1\mathrel{}\middle|\mathrel{}#2\;\right\}} \newcommand{\parenth}[1]{\left(\;#1\;\right)} $

Zornの補題

Zornの補題を証明する。
まずは用語の定義から。
$\left( X, \leq \right)$ を順序集合とする。
$c \in X, T \subset X$ とする。
$c$ は、$T$のupper bound(上界) $:\Leftrightarrow$ $\all a \in T \; a \leq c$
$T$ は、totally ordered(全順序) $:\Leftrightarrow$ $\all a, b \in T \; a \leq b \lor a \geq b$

${\rm TotOrd}\left( X \right) :\equiv \Set{ T \subset X }{ T {\rm は全順序} }$

$c \in S \subset X$ とする。
$c$ は、$S$のmaximal element(極大元) $:\Leftrightarrow \all a \in S \; \parenth{ c \leq a \Rightarrow c \equ a }$

$S \subset X$ とする。
$S$ は、inductive(帰納的) $:\Leftrightarrow \all T \in {\rm TotOrd}\left( S \right) \exi c \in S \; c {\rm は} T {\rm の上界}$

Zornの補題
$\left( X, \leq \right)$ は順序集合とする。
$\all S \subset X \; \parenth{ S{\rm は帰納的} \Rightarrow \all p \in S \; p \!\leq\! \exi c \in S \; c {\rm は} S {\rm の極大元} }$ が成り立つ。
  • $p \in S$ を任意に取る。
  • ${\frak X} :\equiv \Set{ T \in {\rm TotOrd}\left( S \right) }{ p \in T }$ ( $\neq$ 明らかに、$\left\{ p \right\} \in {\frak X}$ である。 $\phi$)と置く。
  • $F : {\frak X} \rightarrow {\frak P}\left( S \right), T \mapsto \Set{ c \in S \backslash T }{ c {\rm は} T {\rm の上界} }$ と置く。
  • $\phi \in F\left( {\frak X} \right) \Rightarrow p \leq \exi c \in S \; c {\rm は} S {\rm の極大元}$
    • 仮定 $\phi \in F\left( {\frak X} \right)$ により、$\exi T \in {\frak X} \; F(T) \equ \phi$ が成り立つ。
    • $S$は帰納的であり、かつ、$T \in {\rm TotOrd}\left( S \right)$なので、$\exi c \in T \; c {\rm は} T {\rm の上界}$。
    • $p \in T$なので、$p \leq c$である。
    • $c$は$S$の極大元である。
      • $c \leq a \in S$ なる $a$を任意に取る。
      • 上界cと $c \leq a$ により、 $a {\rm は} T {\rm の上界}$。
      • $a \not\in \phi$ $\equ$ F(T)=φより。 $F\left( T \right)$ もあわせることにより、$a \not\in S \backslash T$ つまり、$a \in T$。
      • 上界cより、$a \leq c$ である。よって、$c \equ a$ となる。
    • よって、空集合を含むならば定理成立が成り立つ。
  • $\phi \in F\left( {\frak X} \right)$
    • [背理法] $\phi \not\in F\left( {\frak X} \right)$ つまり、 $\all T \in {\frak X} \; F\left( T \right) \neq \phi$ を仮定する。
    • [背理法]の仮定と選択公理により、$\exi \left( c_T \right)_{T \in {\frak X}} \in \prod\limits_{T \in {\frak X}} \; F\left( T \right)$ が成り立つ。
    • $G:{\frak X} \rightarrow {\frak X}, T \mapsto T$ $\coprod$ $c_T \not\in T$なので$\cup$ではなく$\coprod$を使える。 $\left\{ c_T \right\}$ が定義できる。
      • $T \in {\frak X}$ を任意に取る。
      • $p \in T \subset T \coprod \left\{ c_T \right\} \subset S$ である。
      • $T \in {\rm TotOrd}\left( S \right)$ かつ $c_T {\rm は} T {\rm の上界}$ なので、 $T \coprod \left\{ c_T \right\} \in {\rm TotOrd\left( S \right)}$ である。
    • ${\mathbb X} :\equiv \Set{ {\cal S} \subset {\frak X} }{ \begin{array}{@{}c@{}l@{}} ({\rm i})& \left\{ p \right\} \in {\cal S} \\ ({\rm ii})& \all T \in {\cal S} \; G\left( T \right) \in {\cal S} \\ ({\rm iii})& \phi \neq \all {\cal T} \in {\rm TotOrd}\left( {\cal S} \right) \; \bigcup {\cal T} \in {\cal S} \end{array} }$ と置く。
      ($\left( {\frak X}, \subset \right)$ を順序集合として考えている。)
    • ${\frak X} \in {\mathbb X}$ である(つまり、${\mathbb X} \neq \phi$ である)。
      • ${\rm (i)}$$\left\{ p \right\} \in {\frak X}$ である事は、${\frak X}$ の定義から明らか。
      • ${\rm (ii)}$$\all T \in {\frak X} \; G\left( T \right) \in {\frak X}$ の成立は既に示した。
      • ${\rm (iii)}$$\phi \neq {\cal T} \in {\rm TotOrd}\left( {\frak X} \right)$ を任意に取る($\bigcup {\cal T} \in {\frak X}$ を示す)。
      • ${\cal T} \subset {\frak X}$ と ${\frak X}$ の定義より、$\all T \in {\cal T} \; p \in T \subset S$ である。
      • 従って、${\cal T} \neq \phi$ より、$p \in \bigcup {\cal T} \subset S$ である。
      • $\bigcup {\cal T} \in {\rm TotOrd}\left( S \right)$ が成り立つ。
        • $a_1, a_2 \in \bigcup {\cal T}$ を任意に取る。
          $a_i \in T_i \in {\cal T} \; \left( i \in \{1, 2\} \right)$ とする。
        • $T_1, T_2 \in {\cal T} \in {\rm TotOrd}\left( {\frak X} \right)$ なので、 $T_1 \subset T_2 \lor T_1 \supset T_2$ である。
        • どちらでも同様なので、$T_1 \subset T_2$ とする。
        • $a_1, a_2 \in T_2 \in {\cal T} \subset$ ${\frak X} \subset {\rm TotOrd}\left( S \right)$ なので、 $a_1 \leq a_2 \lor a_1 \geq a_2$ が成り立つ。
      • よって、$\bigcup {\cal T} \in {\frak X}$ である。
    • ${\cal R} :\equiv \bigcap {\mathbb X} \; \left( \subset {\frak X} \right)$ と置く。
    • ${\cal R} \in {\mathbb X}$ である。
      • ${\rm (i)}$ $\all {\cal S} \in {\mathbb X} \; \{p\} \in {\cal S}$ なので、 $\{p\} \in \bigcap {\mathbb X} \equ {\cal R}$ である。
      • ${\rm (ii)}$ $T \in {\cal R}$ を任意に取る。
      • 任意の ${\cal S} \in {\mathbb X}$ に対して、$T \in {\cal R} \equ \bigcap {\mathbb X} \subset {\cal S}$ により $G(T) \in {\cal S}$ となる。
      • よって、$G(T) \in \bigcap {\mathbb X} \equ {\cal R}$ である。
      • ${\rm (iii)}$ $\phi \neq {\cal T} \in {\rm TotOrd}\left( {\cal R} \right)$ を任意に取る。
      • 任意の ${\cal S} \in {\mathbb X}$ に対して、 $\phi \neq {\cal T} \subset {\cal R} \equ \bigcap {\mathbb X} \subset {\cal S}$ により $\bigcup {\cal T} \in {\cal S}$ となる。
      • よって、$\bigcup {\cal T} \in \bigcap {\mathbb X} \equ {\cal R}$ となる。
    • ${\cal R} \in {\rm TotOrd}\left( {\cal R} \right)$ (つまり、${\cal R}$は全順序)である。
      • ここの証明が、本証明で一番長いです。
      • $H : {\cal R} \rightarrow {\frak P}\left( {\cal R} \right), T \mapsto \Set{ U \in {\cal R} }{ T \subset U \lor T \supset U }$ と置く。
      • ${\cal R}^\prime :\equiv \Set{ T \in {\cal R} }{ H(T) \equ {\cal R} }$ と置く。
      • ${\cal R}^\prime \in {\rm TotOrd}\left( {\cal R} \right)$ が成り立つ。
        • $T_1, T_2 \in {\cal R}^\prime$ を任意に取る。
        • $T_1 \in {\cal R}^\prime \subset {\cal R}$ $\equ$ $T_2 \in {\cal R}^\prime$ $H(T_2)$ である。 よって $H$の定義 、 $T_1 \subset T_2 \lor T_1 \supset T_2$ である。
      • ${\cal R}^\prime \equ {\cal R}$ が成り立つ。
        • $\subset$ は明らか。
        • $\supset$
          ${\cal R}^\prime \in {\mathbb X}$ が成り立つ。
          • ${\rm (i)}$ $\{p\} \in {\cal R}$ である事は既に知っている。つまり、$\{p\}$は$H$の定義域に属する。
          • $H\left(\left\{ p \right\}\right) \equ {\cal R}$ が成り立つ。
            • $\subset$ $H\left(\left\{ p \right\}\right) \subset {\cal R}$ は$H$の定義から明らか。
            • $\supset$ $U \in {\cal R}$ を任意に取る。
            • $U \in {\cal R} \subset {\frak X}$ $\rightarrow$ ${\frak X}$の定義 $p \in U \rightarrow \{p\} \subset U \rightarrow U \in H\left(\left\{ p \right\}\right)$ となる。
          • よって、$\{p\} \in {\cal R}^\prime$ である。
          • ${\rm (iii)}$ $\phi \neq {\cal T} \in {\rm TotOrd}\left( {\cal R}^\prime \right)$ を任意に取る。
          • まず、$\phi \neq {\cal T} \subset {\cal R}^\prime \subset {\cal R}$ なので、 RはXの要素${\rm (iii)}$より、$\bigcup {\cal T} \in {\cal R}$ である。
          • $H\left(\bigcup {\cal T} \right) \equ {\cal R}$ が成り立つ。
            • $\subset$ $H\left( \bigcup {\cal T} \right) \subset {\cal R}$ は$H$の定義から明らか。
            • $\supset$ $U \in {\cal R}$ を任意に取る。
            • $\begin{array}{@{}l@{}r@{}l@{}l@{}l@{}l@{}} (一)& \exi T \in {\cal T} \; U \subset T & \Rightarrow & U \subset & \bigcup {\cal T} & \\ (二)& \all T \in {\cal T} \; U \not\subset T & \Rightarrow & & \bigcup {\cal T} & \subset U \end{array}$ が成り立つ。
              • (一)$U \subset T \subset \bigcup {\cal T}$ である。
              • (二)$T \in {\cal T}$ を任意に取る。
              • $U \in {\cal R}$ $\equ$ $T \in {\cal T} \subset {\cal R}^\prime$ $H\left( T \right)$ なので、 $T \subset U \lor T \supset U$ である。
              • 従って、(二)の仮定により、$T \subset U$ である。
              • よって、$\bigcup {\cal T} \subset U$ である。
            • 従って、 排中律 $\exi T \in {\cal T} \; U \subset T$ または
              $\all T \in {\cal T} \; U \not\subset T$ である。
              により、 $U \subset \bigcup {\cal T} \lor U \supset \bigcup {\cal T}$ である。
            • よって、$U \in H\left( \bigcup {\cal T} \right)$ である。
          • よって、$\bigcup {\cal T} \in {\cal R}^\prime$ である。
          • ${\rm (ii)}$$T \in {\cal R}^\prime$ を任意に取る。
          • まず、$T \in {\cal R}^\prime \subset {\cal R}$ なので、 RはXの要素${\rm (ii)}$より、$G\left( T \right) \in {\cal R}$ である。
          • $H\left( G\left( T \right) \right) \equ {\cal R}$ が成り立つ。
            • $\subset$ $H\left( G\left( T \right) \right) \subset {\cal R}$ は$H$の定義から明らか。
            • $\supset$
              $H\left( G\left( T \right) \right) \in {\mathbb X}$ が成り立つ。
              • ${\rm (i)}$ まず、RはXの要素より、$\{p\} \in {\cal R}$ である。
              • $T \in {\cal R}^\prime \subset {\cal R} \subset {\frak X}$ なので、${\frak X}$ の定義より、$p \in T$ である。
              • 従って、$\{p\} \subset T \subset T \coprod \{ c_T \} \equ G\left(T\right)$ である。
              • よって、$\{p\} \in H\left(G\left(T\right)\right)$ である。
              • ${\rm (iii)}$ $\phi \neq {\cal T} \in {\rm TotOrd}\left( H\left( G\left( T \right) \right) \right)$ を任意に取る。
              • まず、$\phi \neq {\cal T} \subset H\left( G\left( T \right) \right) \subset {\cal R}$ なので、 RはXの要素より、$\bigcup {\cal T} \in {\cal R}$ である。
              • $\begin{array}{@{}l@{}r@{}l@{}l@{}l@{}l@{}} (一)& \exi T^\prime \in {\cal T} \; G\left(T\right) \subset T^\prime & \Rightarrow & G\left(T\right) \subset & \bigcup {\cal T} & \\ (二)& \all T^\prime \in {\cal T} \; G\left(T\right) \not\subset T^\prime & \Rightarrow & & \bigcup {\cal T} & \subset G\left(T\right) \end{array}$ が成り立つ。
                • (一) $G\left(T\right) \subset T^\prime \subset \bigcup {\cal T}$ である。
                • (二) $T^\prime \in {\cal T}$ を任意に取る。
                • $T^\prime \in {\cal T} \subset H\left( G\left( T \right) \right)$ だから、 $T^\prime \subset G\left(T\right) \lor T^\prime \supset G\left(T\right)$ である。
                • 従って、(二)の仮定により、$T^\prime \subset G\left(T\right)$ である。
                • よって、$\bigcup {\cal T} \subset G\left(T\right)$ である。
              • 従って、 排中律 $\exi T^\prime \in {\cal T} \; G\left(T\right) \subset T^\prime$ または、
                $\all T^\prime \in {\cal T} \; G\left(T\right) \not\subset T^\prime$ である。
                により、$G(T) \subset \bigcup {\cal T} \lor G(T) \supset \bigcup {\cal T}$ である。
              • よって、$\bigcup {\cal T} \in H\left( G\left( T \right) \right)$ である。
              • ${\rm (ii)}$ $U \in H\left( G\left( T \right) \right)$ を任意に取る($G\left(U\right) \in H\left( G\left( T \right) \right)$ を示す)。
              • $U \in H\left( G\left( T \right) \right) \subset {\cal R}$ だから、 RはXの要素より、$G\left(U\right) \in {\cal R}$ である。
              • $G(U) \subset T \lor G(T) \subset U$ の場合:
                • どちらでも同様なので、$G(U) \subset T$ とする。
                • $G(U) \subset T \subset T \coprod \{c_T\} \equ G(T)$ だから、 $G(U) \in H\left( G\left( T \right) \right)$ となる。
              • $G(U) \not\subset T \land G(T) \not\subset U$ の場合:
                • $U \in H\left( G\left( T \right) \right)$ だから、 $U \subset G(T) \lor U \supset G(T)$ である。
                • 場合分けの仮定$G(T) \not\subset U$ より、$U \subset G(T)$ である。
                • $G(U) \in {\cal R}$ $\equ$ 仮定$T \in {\cal R}^\prime$ $H(T)$ だから、 $G(U) \subset T \lor G(U) \supset T$ となる。
                • 場合分けの仮定$G(U) \not\subset T$ より、$G(U) \supset T$ である。
                • $T \subset U$ の場合:
                  • $T \subset U$ $\subset$ U⊆G(T) $G(T) \equ T \coprod \{ c_T \}$ だから、 $T \equ U \lor U \equ G(T)$ である。
                  • $T \equ U$ の場合:
                    • $G(U) \equ G(T)$ $\in$ $H$の定義から自明に成立。 $H\left( G\left( T \right) \right)$ である。
                  • $U \equ G(T)$ の場合:
                    • $G(T) \equ U \subset G(U)$ だから、 $G(U) \in H\left( G\left( T \right) \right)$ である。
                • $T \not\subset U$ の場合:
                  • $U \subset T \cup U$ $\subset$ G(U)⊇T $G(U) \cup U \equ G(U)$ だから、 $U \equ T \cup U \lor T \cup U \equ G(U)$ である。
                  • 従って、$G(U)$ $\equ$ 場合分けの仮定 $T \not\subset U$ $T \cup U$ $\subset$ U⊆G(T) $T \cup G(T) \equ G(T)$ である。
                  • よって、$G(U) \in H\left( G\left( T \right) \right)$ である。
                • よって、いづれにしても、$G(U) \in H\left( G\left( T \right) \right)$ である。
              • よって、いづれにしても、$G(U) \in H\left( G\left( T \right) \right)$ である。
            • よって、$H\left( G\left( T \right) \right) \supset \bigcap {\mathbb X} \equ {\cal R}$ である。
          • よって、$G(T) \in {\cal R}^\prime$ である。
        • よって、${\cal R}^\prime \supset \bigcap {\mathbb X} \equ {\cal R}$ である。
      • よって、${\cal R} \equ {\cal R}^\prime \in {\rm TotOrd}\left( {\cal R} \right)$ である。
    • $R :\equiv \bigcup {\cal R} \; \left( \subset S \right)$ と置く。
    • $R \equ \bigcup {\cal R}$ $\in$ RはXの要素,Rは全順序,${\mathbb X}$の条件${\rm (iii)}$ ${\cal R}$ だから、RはXの要素,${\mathbb X}$の条件${\rm (ii)}$より、$G(R) \in {\cal R}$ である。
    • 従って、$G(R) \subset \bigcup {\cal R} \equ R$ である。
    • しかし、$R \subsetneq R \coprod \{ c_R \}$ $\equ$ $G$の定義 $G(R)$ であるので、これらは矛盾している。
    • よって、背理法により、$\phi \in F\left( {\frak X} \right)$ である。
  • よって、空集合を含むならば定理成立,空集合を含むより、 $p \leq \exi c \in S \; c {\rm は} S {\rm の極大元}$ である。
証明終