ツォルンの補題
集合論においてツォルンの補題（ツォルンのほだい、）またはクラトフスキ・ツォルンの補題（クラトフスキ・ツォルンのほだい）とは次の定理をいう。この定理は数学者マックス・ツォルンとカジミェシュ・クラトフスキに因む。
この補題で使われている用語の定義は以下のとおりである。("P", ≤) を半順序集合とする。部分集合 "T" が 全順序 であるとは、"T"の各元 "s" と "t" について、"s" ≤ "t" または "t" ≤ "s" が必ず成り立つことを言う。"T" が "P" に上界 "u" を持つとは、"T" の元 "t" がつねに "t" ≤ "u" を満たすことをいう。注意として、"u" は "P" の元であればよく、"T" の元である必要はない。"P" の元 "m" が 極大元 であるとは、"P" の元 "x" で、 "m" < "x" となるものは存在しないことをいう。
"P"が空集合でないことを明言する必要はない。というのも、空集合は自明な鎖であり、上界を持つ必要がある。このことから "P" が少なくともひとつの元を持つことが分かる。よって、以下の同値な定式化も可能である。これらの違いは微妙なものであるが、ツォルンの補題を使った証明において上界を生成するある種の和集合を考えることがあり、その際に空な鎖は空集合の和集合になり、間違いやすい境界値となる。
ZF集合論において、ツォルンの補題は整列可能定理や選択公理と同値である。すなわち、ひとつを仮定すると残りを証明することができる。この補題は関数解析学においてはハーン・バナッハの定理を、線型代数においては基底の存在を、位相空間論においては「任意のコンパクト集合の直積はまたコンパクトである」というチコノフの定理を、そして代数学においては全てのゼロでない環は極大イデアルを持ち、任意の体における代数的閉包の存在をそれぞれ証明する際に使われる。
ツォルンの補題を使って、単位元を持つ自明でない全ての環 "R" が極大イデアルを持つことを示すことができる。上記の用語でいうと、"P" は "R" の(両側)イデアルのうち "R" 自身以外からなる集合とする。これは自明なイデアル {0} を含むので空ではない。この集合は包含関係により半順序集合である。極大イデアルを見つけることは "P" の極大元を見つけることと同じである。ここで、"R" を取り除いたのは極大イデアルの定義には、"R" に等しくないことが入っているからである。
ツォルンの補題を適用するために、"P" の空でない全順序部分集合 "T" をとる。"T" に上界が存在することを示す必要がある、つまり、イデアル "I" ⊆ "R" が存在して、それは "T" のどの要素より以上であり、しかも "R" よりは厳密に小さい (そうでなければ、"P" の要素ではなくなる)ことを示す必要がある。"I" を "T" の全てのイデアルの和集合とする。"T" は少なくともひとつ元を持ち、それは 0 を含んでいるので、和集合 "I" も 0 を含み、よって空集合ではない。"I" がイデアルであることを示すため、"a" と "b" を "I" の元とすると、ふたつのイデアル "J", "K" ∈ "T" が存在し、"a" は "J" の元であり、"b" は "K" の元である。"T" は全順序であったので、"J" ⊆ "K" または "K" ⊆ "J" である。前者の場合は、"a" も "b" もともに "K" の元であり、和 "a" + "b" も "K" の元である。よって、"a" + "b" は "I" の元である。後者の場合は、"a" も "b" もともに "J" の元であるから、同様に "a" + "b" は "I" の元である。さらに、任意の "r" ∈ "R" に対して、"ar" と "ra" は "J" の元であるから、"I" の元でもある。以上により、"I" は "R" のイデアルであることが分かった。
そして、イデアルが "R" と一致することは 1 を含むことと同値である(明らかに "R" に等しければ 1 を含むし、1を含んでいたとすると任意の "R" の元 "r" に対して、"r1" = "r" もこのイデアルの元であり、"R" と等しいことが分かる)。そこで、"I" が "R" に等しいと仮定すると、それは 1 を含み、"T" のある要素が 1 を含むことになり、それは "R" と一致する。しかし、これは "P" から "R" を除いていたことに矛盾する。
ツォルンの補題の条件は確認できたので、"P" には極大元が存在する。言い換えると、"R" には極大イデアルが存在する。
この証明は環 "R" が乗法単位元 1 を持っていることに依存していることに注意しよう。これ無しではこの証明は無効であり、さらにこの言明は偽になりうる。例えば、 に通常の加法と自明な乗法(つねに ab = 0)を入れた環は極大イデアルも 1 も持たない: この環のイデアルは加法による部分群そのものである。真部分群 による商群 は可除群である。よって、有限生成にはならず、 を真に含む自明でない部分群が存在する。
選択公理を仮定したツォルンの補題の証明を概略する。補題が成り立たないと仮定する。このとき半順序集合 "P" を、全ての鎖が上界を持つにも関わらず、どの元もそれより大きな元を持つように取れる。各鎖 "T" について、それより真に大きな元 "b"("T") が存在する。なぜなら、"T" は上界を持ち、さらにそれより大きな元が存在するからである。関数 "b" を実際に定義するには選択公理を使う必要がある。
この関数 "b" を使うことで、"P" の元の列 "a" < "a" < "a" < "a" < ... を定めることができる。この列は本当に長い、添え字の範囲は単なる自然数ではなく、全ての順序数を動く。実は "P" と比較しても長すぎる。順序数の全体は真クラスを成すほど大きすぎて、普通の集合より大きくなる。そして、この長さにより集合 "P" の元を使い尽くすことで矛盾を得る。
"a"は次の超限帰納法で定義する。まず、"a" は "P" の元から勝手に選ぶ(これは "P" が空の鎖の上界を持ち、空でないことから可能である)。他の順序数 "w" については、"a" = "b"({"a": "v" < "w"}) で定める。{"a": "v" < "w"} は全順序であるので、この定義は正しい超限帰納法である。
実際には、この証明はより強い形のツォルンの補題が正しいことを示している。
はツォルンの補題に似た初期の定理である。
クラトフスキは1922年に現在の定式化に近い形で証明した(包含関係により順序付いた集合と整列した鎖の和集合の場合)。現在のものと本質的に同等の定式化(整列ではなく任意の鎖に弱めた場合)はツォルンにより独立に1935年に与えられた。彼は整列可能定理に代わる集合論の公理として提案し、代数におけるいくつかの応用を行って見せた。また、他の論文で選択公理との同値性を示すとしていたが、それは公開されることはなかった。
「ツォルンの補題」という名前はジョン・テューキーの1940年の著書「Convergence and Uniformity in Topology」で使用されたことによる。ブルバキの「Théorie des Ensembles」では1939年に「le théorème de Zorn」として同様の極大原理を引用している。「クラトフスキ・ツォルンの補題」という名前はポーランドとロシアで使われている。
ツォルンの補題は三つの主要な成果と(ZFにおいて)同値である
さらに、ツォルンの補題(または同値な命題)は数学の各分野で重要な成果を導く。例えば、
この補題はシンプソンズの「Bart’s New Friend」の回で言及された。