Zornの補題
概要
Zornの補題（Zorn's lemma）とは、空でない半順序集合 $P$ の任意の鎖が $P$ の中に上界を持つなら、$P$ は極大元を持つと述べる定理である。選択公理と同値であり、Hausdorff の極大原理や Tukey の補題とも同値である。ベクトル空間の基底、極大イデアル、超フィルター、半順序の全順序への拡張など、「これ以上大きくできないもの」の存在証明に使われる。極大元は最大元とは限らず、上界が集合の外にしかない鎖や、非可算な鎖に上界がない $\omega_1$ のような例では結論は成り立たない。
Zornの補題は、「どの鎖にもその集合の中に上界がある半順序集合には極大元がある」と述べる定理であり、選択公理と（$\mathsf{ZF}$ の上で）同値である。代数学・位相空間論・関数解析で、ベクトル空間の基底、極大イデアル、超フィルターなどの「これ以上大きくできないもの」の存在を示すときに使われる。たとえば、集合 $X$ の部分集合全体を包含で順序づけた半順序集合では、鎖の和集合が上界になり、$X$ 自身が極大元である。
定義
Zornの補題（Zorn's lemma）は、「どの鎖にも上界がある半順序集合には極大元がある」と述べる定理である。以下では選択公理を仮定する（$\mathsf{ZFC}$ で考える）。
$(P,\leq)$ を半順序集合とし、$x< y$ で「$x\leq y$ かつ $x\neq y$」を表す。
- 部分集合 $C\subset P$ が、任意の $x,y\in C$ について $x\leq y$ または $y\leq x$ を満たすとき、$C$ を $P$ の鎖という。空集合も鎖である。
- $u\in P$ が $C\subset P$ の上界であるとは、すべての $x\in C$ について $x\leq u$ が成り立つことをいう。上界は必ず $P$ の元でなければならず、$C$ 自身に属する必要はない。
- $m\in P$ が極大元であるとは、$m< x$ を満たす $x\in P$ が存在しないことをいう。$m$ が最大元であるとは、すべての $x\in P$ について $x\leq m$ が成り立つことをいう。
半順序集合 $P$ が空でなく、$P$ の任意の鎖が $P$ の中に上界を持つとき、$P$ を帰納的順序集合という。
ここでは空集合も鎖に含める。$P\neq\emptyset$ なら空の鎖は $P$ の任意の元を上界に持つため、「空でない $P$ の任意の空でない鎖が上界を持つ」という定義と同値である。
集合 $X$ の部分集合全体 $\mathcal P(X)$ を包含 $\subset$ で順序づける。$\mathcal C\subset\mathcal P(X)$ を鎖とすると、和集合 $\bigcup\mathcal C$ は $X$ の部分集合で、$\mathcal C$ の各元を含むから $\mathcal C$ の上界である（$\mathcal C=\emptyset$ なら $\emptyset$ が上界）。$\emptyset\in\mathcal P(X)$ なので $\mathcal P(X)$ は空でなく、したがって帰納的順序集合である。実際、極大元は $X$ ただ一つで、これは最大元でもある。
極大元と最大元は異なる。極大元 $m$ は $m< x$ となる元 $x$ が存在しない元であり、$P$ のすべての元が $m$ 以下であるとは限らない。最大元は存在すれば一意で極大元でもあるが、比較不能な極大元は複数存在しうる。全順序集合では、極大元と最大元は一致する。
定理
帰納的順序集合は極大元を持つ。
この主張が Zornの補題 である（Jech73 §2.1, p. 9 の Maximal Principle I）。以下では 選択公理 を仮定し、どの鎖からもその上にある元を一斉に選ぶ箇所を明示して証明する。
$P$ を帰納的順序集合とする。
段階1：極大元がないと仮定し、鎖を延長する規則を作る。
$P$ に極大元がないと仮定する。鎖 $C\subset P$ に対し、その上界全体を
$$
U(C):=\{u\in P\mid (\forall x\in C)\ x\leq u\}
$$
とおく。帰納性により $U(C)\neq\emptyset$ である。さらに $u\in U(C)$ は極大元でないため、$u< v$ を満たす $v\in P$ が存在する。このとき $C$ のすべての元 $x$ について $x\leq u< v$ なので、
$$
E(C):=\{v\in P\mid (\forall x\in C)\ x< v\}
$$
は空でない。
ここで 選択公理 を一度用いる。$P$ の鎖 $C$ ごとの空でない集合 $E(C)$ から元を一つずつ選ぶ 選択関数 を取り、その値を $e(C)\in E(C)$ と書く。この一斉選択が証明中で選択公理を使う箇所である。
段階2：集合 $P$ より長い順序数をとる。
選択公理 の記事の補題「Hartogsの補題」（選択公理を使わずに示される）により、$P$ へ単射できない順序数 $\theta$ が存在する。
段階3：超限再帰で真に増加する列を作る。
$\alpha<\theta$ に対して、すでに $x_\beta$（$\beta<\alpha$）が定まったとき
$$
C_\alpha:=\{x_\beta\mid \beta<\alpha\},\qquad x_\alpha:=e(C_\alpha)
$$
と定める。ただし $C_\alpha$ が鎖であることを同時に超限帰納法で示す必要がある。$C_0=\emptyset$ は鎖である。$\alpha$ 未満のすべての $\gamma$ で $C_\gamma$ が鎖で $x_\gamma=e(C_\gamma)$ が定まっているとすると、$\beta<\gamma<\alpha$ なら $x_\beta\in C_\gamma$ で $x_\gamma\in E(C_\gamma)$ だから $x_\beta< x_\gamma$ である。よって $C_\alpha$ の任意の 2 元は添字の順に比較可能で、$C_\alpha$ は鎖であり、$x_\alpha=e(C_\alpha)$ が定まる。後続段階と極限段階を区別する必要はない。
段階4：極大元がないという仮定と矛盾させる。
段階 3 により $\beta<\alpha<\theta$ なら $x_\beta< x_\alpha$ なので $x_\beta\neq x_\alpha$ である。従って $\alpha\mapsto x_\alpha$ は $\theta$ から $P$ への単射になるが、これは $\theta$ の取り方に反する。ゆえに $P$ には極大元が存在する。$\square$
逆に Zornの補題から選択公理が導かれ、$\mathsf{ZF}$ の上で両者は同値である。この逆向きの証明は 選択公理 の記事の定理「Zornの補題との同値」にある。選択公理は $\mathsf{ZF}$ から独立なので（同じ記事の系「選択公理の独立性」）、Zornの補題も $\mathsf{ZF}$ だけからは証明できない。
使いやすい形と同値な原理
応用では、次の形で使うことが多い。
$P$ を半順序集合とし、$P$ の空でない任意の鎖が $P$ の中に上界をもつとする。このとき任意の $a\in P$ に対し、$a\leq m$ を満たす $P$ の極大元 $m$ が存在する。
$P_a:=\{x\in P\mid a\leq x\}$ に $P$ の順序を制限する。$a\in P_a$ なので $P_a\neq\emptyset$ である。$C\subset P_a$ を空でない鎖とすると、$C$ は $P$ の鎖なので $P$ の中に上界 $u$ をもち、$c\in C$ をとれば $a\leq c\leq u$ なので $u\in P_a$ である。空の鎖は $a$ を上界にもつ。よって $P_a$ は帰納的順序集合であり、thm-zorn-lemma により極大元 $m$ をもつ。$m$ は $P$ でも極大である。実際 $m< x$ となる $x\in P$ があれば $a\leq m< x$ なので $x\in P_a$ となり、$P_a$ での極大性に反する。$\square$
次の二つの原理は、どちらも Zornの補題と $\mathsf{ZF}$ の上で同値である（Jech73 §2.1 Theorem 2.1, p. 10、Mun00 §11, pp. 69–72）。一つの集合 $X$ の部分集合族 $\mathcal F$ が有限性格をもつとは、任意の $A\subset X$ について「$A\in\mathcal F$ であることと、$A$ の有限部分集合がすべて $\mathcal F$ に属すること」が同値であることをいう。
- Hausdorff の極大原理：任意の半順序集合には、包含について極大な鎖がある。選択公理からの直接の証明と、与えられた鎖を含む極大鎖がとれる強い形は Hausdorffの極大原理 にある。
- Tukey の補題：有限性格をもつ空でない族 $\mathcal F$ には、包含について極大な元がある。
$\mathsf{ZF}$ において、Zornの補題、Tukey の補題、Hausdorff の極大原理は互いに同値である。
Zorn ⇒ Tukey、Tukey ⇒ Hausdorff、Hausdorff ⇒ Zorn の順に示す。どの段も選択公理を使わない。
Zorn ⇒ Tukey。 $\mathcal F$ を有限性格をもつ空でない族とし、包含で順序づける。$\mathcal C\subset\mathcal F$ を鎖とし、$U:=\bigcup\mathcal C$ とおく（$\mathcal C=\emptyset$ なら $\mathcal F$ の任意の元が上界なので、空でないとしてよい）。$U\in\mathcal F$ を示せば、$U$ が $\mathcal C$ の上界になる。有限性格により、$U$ の任意の有限部分集合 $F=\{a_1,\dots,a_k\}$ が $\mathcal F$ に属することを示せばよい。各 $a_i$ はある $A_i\in\mathcal C$ に属し、$\mathcal C$ は鎖なので $A_1,\dots,A_k$ の中に包含について最大のもの $A_j$ がある（$k=0$ なら $F=\emptyset$ で、$\mathcal C$ の任意の元の有限部分集合なので $F\in\mathcal F$）。すると $F\subset A_j\in\mathcal F$ で、有限性格により $A_j$ の有限部分集合 $F$ は $\mathcal F$ に属する。よって $\mathcal F$ は帰納的であり、Zornの補題により極大元をもつ。
Tukey ⇒ Hausdorff。 $(P,\leq)$ を半順序集合とし、$P$ の鎖全体の族 $\mathcal F$ を考える。$\emptyset\in\mathcal F$ なので空でない。$A\subset P$ が鎖であることは「$A$ の任意の 2 元が比較可能」ということで、これは $A$ の 2 元以下からなる有限部分集合がすべて鎖であることと同値である。したがって $A$ が鎖であることと、$A$ の有限部分集合がすべて鎖であることは同値で、$\mathcal F$ は有限性格をもつ。Tukey の補題により、包含について極大な鎖がある。
Hausdorff ⇒ Zorn。 $P$ を帰納的順序集合とし、Hausdorff の極大原理により極大な鎖 $B$ をとる。仮定により $B$ は $P$ の中に上界 $c$ をもつ。$c$ が極大元であることを示す。$c< d$ となる $d\in P$ があれば、$B$ のすべての元 $b$ について $b\leq c< d$ なので、$B\cup\{d\}$ は鎖である。$d\notin B$（$d\in B$ なら $d\leq c$ となり $c< d$ に反する）なので、$B\cup\{d\}$ は $B$ を真に含む鎖となり、$B$ の極大性に反する。よって $c$ は極大元である。$\square$
Tukey の補題は、「有限個ずつ確かめられる性質」をもつ極大な集合の存在をいうのに便利である。たとえばベクトル空間の線形独立な部分集合の族は、線形独立性が有限個の元の一次結合だけで決まるので有限性格をもつ。
応用
Zornの補題の代表的な応用は、それぞれの主題の記事で証明されている。
- ベクトル空間の基底の存在：基底 の記事の定理「一般のベクトル空間の基底の存在」。線形独立な部分集合全体に Zorn を当てる。
- 極大イデアルの存在：極大イデアル の記事の定理「真イデアルを含む極大イデアルの存在」。
- 超フィルターへの拡張：超フィルター の記事の定理「超フィルターへの拡張」。
ここでは、順序そのものについての応用を一つ証明する。半順序 $\leq'$ が半順序 $\leq$ を拡張するとは、$x\leq y$ なら $x\leq' y$ が成り立つことをいう。
集合 $X$ 上の任意の半順序 $\leq$ は、$X$ 上のある全順序に拡張できる。
半順序を $X\times X$ の部分集合（反射的・反対称的・推移的な関係）とみる。
補題：全順序でない半順序は真に拡張できる。 $\leq$ を半順序とし、$a,b\in X$ が比較不能（$a\not\leq b$ かつ $b\not\leq a$）とする。
$$R:=\;\leq\;\cup\;\{(x,y)\mid x\leq a\text{ かつ }b\leq y\}$$
とおく。$R$ は $\leq$ を含み、$(a,b)\in R$ だが $(a,b)\notin\;\leq$ なので真に大きい。反射性は $\leq\subset R$ から従う。推移性：$(x,y),(y,z)\in R$ とする。両方が $\leq$ に属すれば $x\leq z$ である。$(x,y)$ が新しい対で $(y,z)\in\;\leq$ なら $x\leq a$、$b\leq y\leq z$ なので $(x,z)$ は新しい対である。$(x,y)\in\;\leq$ で $(y,z)$ が新しい対なら $x\leq y\leq a$、$b\leq z$ で同様である。両方が新しい対なら $b\leq y\leq a$ となり $a,b$ の比較不能性に反するので、この場合は起きない。反対称性：$(x,y),(y,x)\in R$ とする。両方が $\leq$ に属すれば $x=y$ である。一方が新しい対、たとえば $x\leq a$、$b\leq y$ で、$(y,x)\in R$ なら、$(y,x)\in\;\leq$ のとき $b\leq y\leq x\leq a$、$(y,x)$ が新しい対のとき $b\leq y\leq a$ となり、いずれも比較不能性に反する。よって $R$ は $\leq$ を真に拡張する半順序である。
Zorn の補題の適用。 $\leq$ を拡張する $X$ 上の半順序全体の集合 $\mathcal P$ を包含で順序づける。$\leq\;\in\mathcal P$ なので空でない。$\mathcal C\subset\mathcal P$ を空でない鎖とし、$S:=\bigcup\mathcal C$ とおく。$S$ は $\leq$ を含み反射的である。$(x,y),(y,z)\in S$ なら、それぞれ $R_1,R_2\in\mathcal C$ に属し、鎖なので大きい方 $R$ が両方を含むから、$(x,z)\in R\subset S$ である。反対称性も同様に一つの $R\in\mathcal C$ の中で確かめられる。よって $S\in\mathcal P$ で、$S$ は $\mathcal C$ の上界である（空の鎖は $\leq$ を上界にもつ）。Zornの補題により $\mathcal P$ は極大元 $\leq^*$ をもつ。$\leq^*$ が全順序でなければ、補題により $\leq^*$ を真に拡張する半順序があり、それは $\mathcal P$ に属して $\leq^*$ の極大性に反する。よって $\leq^*$ は $\leq$ を拡張する全順序である。$\square$
$X$ が有限なら、比較不能な対を一つずつ補題で解消すれば有限回で全順序に達するので、Zornの補題は要らない。この命題は順序拡張原理とも呼ばれ、Jech73 §2.3.2（p. 19）では素イデアル定理からコンパクト性定理を経由する別の証明が与えられている。
反例：仮定を外すと崩れること
Zornの補題の仮定は「$P$ が空でない」と「任意の鎖が $P$ の中に上界をもつ」の二つである。どちらを弱めても結論は成り立たない。また結論は極大元の存在だけで、最大元や一意性は主張しない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $P$ が空でない | 空の半順序集合 | 極大元の存在 |
| 上界が $P$ の中にある | $P=(0,1)$（通常の順序） | 極大元の存在 |
| 無限の鎖にも上界がある（有限の鎖だけでは足りない） | $(\mathbb N,\leq)$ | 極大元の存在 |
| 非可算な鎖にも上界がある（可算な鎖だけでは足りない） | 最小の非可算順序数 $\omega_1$ | 極大元の存在 |
| $P$ が全順序（結論の強め方） | 比較不能な 2 元 $\{a,b\}$ | 極大元が最大元であること・一意であること |
通常の順序を入れた $P=(0,1)$ を考える。$P$ 自身は鎖であり、実数全体では $1$ を上界に持つが、$1\notin P$ なので $P$ の中には上界がない。従って $P$ は帰納的順序集合ではなく、実際に極大元を持たない（$x\in P$ に対し $(x+1)/2\in P$ で $x<(x+1)/2$）。この例が破る含意は「鎖が外部の順序集合で上に有界なら極大元が存在する」であり、破れている条件は「上界が $P$ の中にあること」である。
1 行目：空集合には元がないので極大元もない。空の鎖の上界も存在しないので、空集合は帰納的でない。
3 行目：$\mathbb N$ の有限な鎖（空でないもの）は最大の元をもち、それが上界である。しかし $\mathbb N$ 自身は鎖で上界をもたず、$n< n+1$ なのでどの $n$ も極大でない。
4 行目：$\omega_1$ の元は可算順序数である。可算個の可算順序数の集合 $C$ の上限 $\sup C=\bigcup C$ は可算個の可算集合の和なので可算であり（ここで可算選択を使う）、$\omega_1$ に属する上界になる。一方、$\alpha<\omega_1$ なら $\alpha+1$ も可算で $\alpha<\alpha+1<\omega_1$ なので、$\omega_1$ に極大元はない。$\omega_1$ 自身は非可算な鎖で、$\omega_1$ の中に上界をもたない。
5 行目：$\{a,b\}$ に $a\leq a$、$b\leq b$ だけの順序を入れると、任意の鎖は高々一元で上界をもつので帰納的であり、$a,b$ はどちらも極大元である。しかし $a\not\leq b$ なので $b$ は最大元でなく、極大元は一意でない。Zornの補題の結論を「最大元がある」に強めることはできない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
