Zorn's lemma

ツォルンの補題は、すべてのベクトル空間V が基底を持つことを示すために使用できる。^{[ 13 ]}

V = { 0 }の場合、空集合はVの基底です。ここで、V ≠ { 0 } とします。PをVのすべての線形独立な部分集合からなる集合とします。Vは零ベクトル空間ではないので、 Vには零でない要素vが存在し、P には線形独立な部分集合 { v } が含まれます。さらに、Pは集合の包含関係によって部分的に順序付けられています(包含順序を参照)。Vの最大線形独立部分集合を見つけることは、Pの最大要素を見つけることと同じです。

ツォルンの補題を適用するには、 Pの鎖T (つまり、TはPの完全順序付き部分集合) を取ります。Tが空集合の場合、{ v } はPのTの上界です。次に、Tが空でないと仮定します。T に上界が存在すること、つまり、 Tのすべての要素を含むVの線形独立な部分集合B が存在することを示す必要があります。

B をTに含まれるすべての集合の和集合とする。BがPにおけるTの上界であることを示したい。そのためには、 BがVの線形独立な部分集合であることを示せば十分である。

そうでなければ、B が線形独立でないと仮定する。すると、ベクトルv ₁ , v ₂ , ..., v _k ∈ Bとスカラーa ₁ , a ₂ , ..., a _kが存在し、すべてがゼロではないので、

${\displaystyle a_{1}\mathbf {v} _{1}+a_{2}\mathbf {v} _{2}+\cdots +a_{k}\mathbf {v} _{k}=\mathbf {0} .}$

B はTに含まれるすべての集合の和集合であるため、すべてのi = 1, ₂ , ..., kに対してv _i ∈ S _iとなるような集合S ₁ , S 2 , ..., S _k ∈ Tが存在する。Tは全順序集合であるため、集合S ₁ , S ₂ , ..., S _kのいずれかが他の集合を包含する必要があり、したがって、すべてのv ₁ , v ₂ , ..., v _{kを含む集合}S _{iが存在する。これは、} S _iに線形従属なベクトルの集合が存在することを示しており、S _{i が線形独立であること (} Pの要素であるため) に矛盾する。

ツォルンの補題の仮説は検証され、したがってPには極大要素が存在する、言い換えればVの極大線形独立部分集合Bが存在する。

最後に、 BがVの基底であることを示します。BがVの全域集合であることを示せば十分です。矛盾を導くために、Bが全域集合ではないと仮定します。すると、 Bの全域で覆われていないv ∈ Vが存在します。これは、B ∪ { v } が、 Bよりも大きいVの線形独立な部分集合であることを意味し、 Bの最大性に矛盾します。したがって、BはVの全域集合であり、Vの基底です。

注記：あまり一般的ではありませんが、選択公理を仮定したまま、超限再帰を用いてより直接的に基底を構成することも可能です。その方法については、例えば「超限再帰定理§ 例：比較のための基底構成」を参照してください。

ツォルンの補題を用いると、単位元を持つすべての非自明な環R には極大イデアルが含まれることを示すことができる。

Rのすべての真イデアル(つまり、R自身を除くRのすべてのイデアル)からなる集合をPとする。Rは非自明な集合であるため、集合Pには自明なイデアル {0} が含まれる。さらに、Pは集合の包含関係によって部分的に順序付けられている。Rの極大イデアルを見つけることは、Pの極大要素を見つけることと同じである。

ツォルンの補題を適用するには、 P内の鎖Tを取ります。T が空の場合、自明なイデアル {0} はP内のTの上界となります。次に、T が空でないと仮定します。T に上界が存在すること、つまり、T のすべての要素を含み、かつ R より小さいイデアル I ⊆ R が存在することを示す必要があります(そうでなければ、それは真のイデアルではないので、Pに含まれません)。

I をTに含まれるすべてのイデアルの和集合とする。IがPにおけるTの上界であることを示したい。まず、 IがRのイデアルであることを示す。Iがイデアルであるためには、次の 3 つの条件を満たす必要がある。

1. IはRの空でない部分集合である。
2. すべてのx、y ∈ Iに対して、和x + yはIに含まれる。
3. すべてのr ∈ Rおよびすべてのx ∈ Iに対して、積rxはIに含まれる。

#1 - IはRの空でない部分集合です。

Tには少なくとも 1 つの要素が含まれており、その要素には少なくとも 0 が含まれているため、和集合Iには少なくとも 0 が含まれており、空ではありません。T のすべての要素はRの部分集合であるため、和集合I はRの要素のみで構成されます。

#2 - すべてのx、y ∈ Iに対して、 x + yの和はIに含まれます。

xとyがIの要素であると仮定します。すると、x がJの要素であり、yがKの要素であるような2 つのイデアルJ、K ∈ Tが存在します。T は全順序であるため、J ⊆ KまたはK ⊆ Jであることがわかります。一般性を失うことなく、最初のケースを仮定します。xとy は両方ともイデアルKの要素であるため、それらの和x + yはKの要素であり、これはx + yがIの要素であることを示しています。

#3 - すべてのr ∈ Rおよびすべてのx ∈ Iに対して、積rxはIに含まれる。

xがIの要素であると仮定します。すると、 x がJに含まれるようなイデアルJ ∈ Tが存在します。r ∈ Rの場合、rxはJの要素であり、したがってIの要素です。したがって、IはRのイデアルです。

ここで、 I が真のイデアルであることを示します。イデアルがRと等しいのは、それが 1 を含む場合に限ります。（それがRであれば 1 を含むことは明らかです。一方、それが 1 を含み、rがRの任意の要素である場合、r 1 = rはイデアルの要素であり、したがってイデアルはRと等しくなります。）したがって、I がRと等しい場合、それは 1 を含み、それはTの要素の 1 つが1 を含み、したがってRと等しくなることを意味しますが、RはPから明示的に除外されています。

ツォルンの補題の仮説は検証され、したがってPには極大元が存在する、言い換えればRには極大イデアルが存在する。

ツォルンの補題は超フィルターの補題を導き、超フィルターの補題はチホノフの定理（選択公理とともに）を導きます。しかし、以下のように（暗黙のうちに超フィルターを使用することで）ツォルンの補題から直接チホノフの定理を証明することもできます。^{[ 14 ]}

させて${\displaystyle X_{i}}$は必ずしもハウスドルフ空間ではないコンパクト空間の族である。我々は、ある族が${\displaystyle F}$閉部分集合の${\displaystyle X:=\prod _{i}X_{i}}$有限交差特性を持つものは、空でない交差を持つ。${\displaystyle P}$部分集合のすべての族の集合である${\displaystyle X}$有限交差特性（必ずしも閉部分集合ではない）を持つ。${\displaystyle P}$セットの包含関係で順序付けられます。${\displaystyle C\subset P}$は鎖であり、明らかに${\displaystyle C}$有限交差特性を持つため、和集合は${\displaystyle P}$したがって、ツォルンの補題により、最大要素が存在する。${\displaystyle M}$で${\displaystyle P}$含む${\displaystyle F}$。 全ての閉集合の共通部分が${\displaystyle M}$空ではない交差点があります。フォルティオリ、${\displaystyle F}$空でない共通部分を持つ。

各有限部分集合について${\displaystyle M'\subset M}$、 以来${\displaystyle \cap M'}$空でない、${\displaystyle \cap p_{i}(M')}$射影に対して空でない${\displaystyle p_{i}:X\to X_{i}.}$したがって、各${\displaystyle i}$セット

${\displaystyle N_{i}:=\left\{{\overline {p_{i}(A)}}\mid A\in M\right\}}$

有限交差特性を持つため、空でない交差を持ち、${\displaystyle X_{i}}$コンパクトです。

1. もし${\displaystyle M'\subset M}$は有限部分集合であり、${\displaystyle \cap M'}$は${\displaystyle M}$。
2. オープンセットの場合${\displaystyle U_{i}}$交差する$\displaystyle \cap N_{i}}$、 我々は持っています${\displaystyle p_{i}^{-1}(U_{i})}$は${\displaystyle M}$。

実際、（１）は成り立つ。${\displaystyle M=M\cup \{\cap M'\}}$最大性により、右側の集合は有限の共通部分の性質を持つ。同様に、有限部分集合の場合も同様である。${\displaystyle M'\subset M}$、 以来${\displaystyle A=\cap M'}$は${\displaystyle M}$、${\displaystyle U_{i}\cap p_{i}(A)\neq \emptyset }$または${\displaystyle p_{i}^{-1}(U_{i})\cap A\neq \emptyset }$したがって、集合は${\displaystyle M\cup \{p_{i}^{-1}(U_{i})\}}$有限交差特性を持ち、(2)最大性により${\displaystyle M}$。

さて、選択公理により、要素を見つけることができる。${\displaystyle m}$で${\displaystyle \prod _{i}(\cap N_{i})}$私たちはこれを主張します${\displaystyle m}$各閉集合に含まれる${\displaystyle A}$で${\displaystyle M}$。 以来${\displaystyle A}$閉じているので、表示するだけで十分です${\displaystyle m}$閉鎖中です${\displaystyle A}$; つまり、各基本近隣地域${\displaystyle m}$交差する${\displaystyle A}$基本的な近隣地域${\displaystyle m}$形式は${\displaystyle \cap _{j=1}^{r}p_{i_{j}}^{-1}(U_{i_{j}})}$しかし、上記の性質（２）により、${\displaystyle \left\{A,p_{i_{j}}^{-1}(U_{i_{j}})\mid j=1,\dots ,r\right\}\subset M}$これは、有限交差性の性質によって主張を与える。${\displaystyle \square }$

注記：超フィルター補題は選択公理よりも厳密に弱く、ブール素イデアル定理と同値である。一方、意外なことに、チホノフの定理は選択公理を含意する（したがって同値である）。したがって、上記の選択公理の使用を排除することはできない。（もし${\displaystyle X_{i}}$コンパクトなハウスドルフであれば、AC の使用は不要になります。実際、各${\displaystyle \cap p_{i}(M)}$上記の場合、ポイントはちょうど1つだけになります。）

ティホノフの定理の別の（おそらくより標準的な）証明方法は、まずアレクサンダーのサブベース補題を証明することですが、その補題の証明には通常、ツォルンの補題が使用されます。

させて${\displaystyle P}$は、空の鎖を含む各鎖に上限がある半順序集合とする。関数を定義する。

${\displaystyle f:P\to P}$

による${\displaystyle f(x)=x}$もし${\displaystyle x}$は最大要素であり、${\displaystyle f(x)=c(\{y\mid y>x\})}$そうでなければ、

${\displaystyle c:{\mathcal {P}}(P)-\{\emptyset \}\to P}$

は選択関数である。すなわち、${\displaystyle c(S)\in S}$最大要素に注目${\displaystyle P}$はまさに固定点である${\displaystyle f}$したがって、証明は不動点を見つけることと同等である。${\displaystyle f}$。

非公式には、繰り返し適用することによって非常に長い数列（超限数列）を構築します。${\displaystyle f}$つまり、まずいくつか選ぶ${\displaystyle x_{0}}$で${\displaystyle P}$可能だから${\displaystyle P}$は空でない。${\displaystyle x_{1}=f(x_{0})}$そして${\displaystyle x_{2}=f(x_{1})}$など。自然数をすべて使い切った場合は、続けるために、

${\displaystyle x_{\omega }=c(\{{\text{upper bounds of the chain }}\,x_{0}\leq x_{1}\leq \cdots \})}$

どこ${\displaystyle \omega =\{0,1,2,\cdots \}}$.次に${\displaystyle x_{\omega +1}=f(x_{\omega })}$など。この手順により、長さのシーケンスが得られます。${\displaystyle \alpha }$各序数について${\displaystyle \alpha }$、

${\displaystyle x_{0}\leq x_{1}\leq \cdots \leq x_{\omega }\leq x_{\omega +1}\leq \cdots }$

数列が増加している限り、マップは${\displaystyle \alpha \to P,\,\beta \mapsto x_{\beta }}$は単射です。しかし、集合はより大きな濃度の部分集合を含むことはできません。したがって、数列が長すぎると、増加することはできず、数列の項は${\displaystyle x_{\beta }=x_{\beta +1}}$は固定点である${\displaystyle f}$（つまり、最大要素${\displaystyle P}$)

形式的には、上記の数列は超限再帰を用いて定義されます。これは通常の数列の再帰的定義と全く同じですが、順序数上で実行されます。重要な違いは、順序数が極限順序数である場合があることです。${\displaystyle \omega }$制限順序数の場合${\displaystyle \alpha }$上記のように、${\displaystyle x_{\alpha }}$数列の上限となる${\displaystyle x_{\beta },\beta <\alpha }$経由${\displaystyle c}$（この種の再帰的構成の詳細については、超限再帰定理§ 例：ツォルンの補題の証明も参照してください。）最後に、十分に大きな順序数が必要です。整列定理の形の選択公理により、順序数を見つけることができます。${\displaystyle \kappa }$それは全単射である${\displaystyle P.}$取る${\displaystyle \alpha =\kappa ^{+}}$、後継基数（＝濃度がより大きい最小の順序数）${\displaystyle \kappa }$) そして、基数性の理由から、${\displaystyle \kappa ^{+}\not \hookrightarrow P,\,\beta \mapsto x_{\beta }}$;つまり、シーケンス${\displaystyle x_{\beta }}$は厳密に増加関数ではないため、その中のいくつかの項は固定点である。^{[ 18 ]}（ちなみに、これは${\displaystyle \kappa ^{+}}$ハートッグス数と呼ばれる${\displaystyle P}$）

あるいは、クラスを許可する基礎を使用している場合、たとえば、固定されたグロタンディーク宇宙を持っている場合、上記の手順は、${\displaystyle f}$固定点を持たないため、単射を構築します。

${\displaystyle \operatorname {Ord} \hookrightarrow P}$

どこ${\displaystyle \operatorname {Ord} }$は、（宇宙における）すべての順序数のクラスです。しかし、そのような単射の存在は、ブラリ＝フォルティのパラドックスとして知られる矛盾です。${\displaystyle \square }$

上記の証明は、順序数を明示的に参照することなく、整列集合の先頭部分を考慮することによって定式化できる。これはクネーザーによる議論である。 ^{[ 19 ] [ 20 ]} （詳細はブルバキ・ウィットの定理§ 証明3を参照）。

させて${\displaystyle \Gamma }$すべての整列鎖の集合とする${\displaystyle C}$で${\displaystyle P}$各${\displaystyle x}$で${\displaystyle C}$、

${\displaystyle x=s(\{y\in C\mid y<x\})}$

どこ${\displaystyle g(S)=c(\{{\text{upper bounds of }}S\})}$そして${\displaystyle s=f\circ g}$我々は、${\displaystyle \Gamma }$は、最初のセグメントによる順序付けに関して完全に順序付けられています。実際、${\displaystyle C,D}$で${\displaystyle \Gamma }$、 させて${\displaystyle S}$それらをすべての共通する最初のセグメントの和集合とすると、これも最初のセグメントになります。すると、簡単に次のことがわかります。${\displaystyle C=S}$または${\displaystyle D=S}$最後に、${\displaystyle U}$結合する${\displaystyle \Gamma }$そして私たちは見ることができる${\displaystyle U}$それ自体は${\displaystyle \Gamma }$。 以来${\displaystyle s(U)\in U}$そして${\displaystyle g(U)}$は上限です${\displaystyle U}$、

${\displaystyle f(g(U))\leq g(U).}$

つまり、${\displaystyle g(U)}$は固定点である${\displaystyle f}$。${\displaystyle \square }$

この証明は、実際にはツォルンの補題の少し強いバージョンが真であることを示している。

ハウスドルフの最大原理は、すべての半順序集合が⁠${\displaystyle P}$最大鎖を持つ${\displaystyle C\subset P}$集合の包含関係に関して。

ツォルンの補題の通常の形式はハウスドルフの最大原理から導かれる。なぜなら、もし⁠${\displaystyle P}$ゾルンの補題の仮説を満たすならば、その最大鎖は${\displaystyle C}$上限値も存在する${\displaystyle x}$⁠で⁠${\displaystyle P}$⁠ . これ⁠${\displaystyle x}$は最大要素です。なぜなら、${\displaystyle y>x}$⁠、それから⁠${\displaystyle {\widetilde {C}}=C\cup \{y\}}$はよりも厳密に大きいチェーンです${\displaystyle C}$⁠、最大性に矛盾する⁠${\displaystyle C}$⁠ . ^{[ 21 ]}

逆に、ハウスドルフの最大原理も、鎖の集合を集合包含関係によって順序付けられた半順序集合とみなすことで、ツォルンの補題から導かれる。実際、この特定のケースでは、ツォルンの補題の次の弱い形式のみが必要となる。^{[ 22 ]}

あるいは、さらに弱い形式として以下が挙げられる。

これは、各鎖の結合が弱い形式であるためです。${\displaystyle F}$は、その連鎖の最小上界です。この含意のサイクル（ツォルンの補題 ⇒ 補題 1 ⇒ 補題 2 ⇒ ハウスドルフの最大原理 ⇒ ツォルンの補題）は、これらの形式が実際にはすべて同等であることを示しています。

補題2は、ハウスドルフ最大原理§ 証明1で示されているように、選択公理から直接証明できます。

ブルバキ・ウィットの定理は、写像を考慮することで補題1の証明を与えるためにも使用できる。${\displaystyle f:P\to P}$そのため${\displaystyle f(x)=x}$もし${\displaystyle x}$最大であり、${\displaystyle f(x)>x}$そうでなければ（例えば）${\displaystyle f}$選択公理により存在する）。あるいは、半順序集合内のすべての鎖の集合は最小元を持つdcpoであるため、代わりにパタライアの定理を使用してハウスドルフの最大原理を証明することができます。したがって、ツォルンの補題です。

ゾルンの補題の弱化形は、ZF + DC (選択公理を従属選択公理に置き換えたツェルメロ・フレンケル集合論) から証明できる。ゾルンの補題は、最大要素を持たない集合は、集合の順序関係が完全であると述べることと同等であり、従属選択公理を適用して可算鎖を構成できることを観察することで直接的に表現できる。結果として、有限鎖のみを持つ任意の半順序集合は最大要素を持たなければならない。^{[ 35 ]}

より一般的には、依存選択公理をより高い順序数に強化することで、前の段落の記述をより高い濃度に一般化することができます。^{[ 35 ]}任意の大きな順序数を許容する極限では、前のセクションの選択公理を使用して、ゾルンの補題の完全な証明を復元します。