「集合と写像」4.3 ツォルンの補題

この記事では,選択公理と同値な命題として知られる「ツォルンの補題」と呼ばれる命題を,選択公理を仮定して証明する.



帰納的半順序集合

ツォルンの補題の主張を述べるために,半順序集合が帰納的であることの定義を紹介する.

定義 4.3.1 帰納的半順序集合

\({}(X,\leq)\) が半順序集合(半順序集合の定義はこの記事を参照)であるとする.\({}(X,\leq)\) が帰納的であるとは,空でない任意の全順序部分集合が上界を持つことである.

すなわち,\({}Y(\not=\emptyset)\subset{}X\) について,任意の \(a,b\in{}Y\) に対して \(a\leq{}b\) または \(b\leq{}a\) であるならば,ある \(x\in{}X\) が存在して任意の \(y\in{}Y\) に対して \(y\leq{}x\) が成り立つとき,\({}(X,\leq)\) を帰納的半順序集合という.

 

以下,定義をわかりやすくするために例を挙げる.例 4.3.3 のような状況は典型的である.

例 4.3.2 帰納的半順序集合の例1

定義から,\({}(X,\leq)\) が最大元をもつとき,この最大元は任意の空でない部分集合の上界である.すなわち,\(X\) の空でない任意の部分集合 \(Y\) の任意の元 \(y\) に対し,\(y\leq{}(X\)の最大限\()\) が成立する.したがって,当然 \(X\) の空でない全順序部分集合には上界が存在し,\({}(X,\leq)\) は帰納的である.

たとえば,元をひとつしか持たない半順序集合 \({}(\{0\},\leq)\) は帰納的である.

 

例 4.3.3 帰納的半順序集合の例2

\(X\) を任意に与えられた集合とする.\(X\) のべき集合 \(\mathfrak{P}(X)=\{Y\mid{}Y\subset{}X\}\) に,包含関係による順序を与える(この例では,順序の記号は省略する).このとき,\(X\) は \(\mathfrak{P}(X)\) で最大なので,例 4.3.2 により帰納的半順序集合であるが,この例はより”洗練された”性質を持つ例である.最小上界,すなわち上限を与えることができるのである.

\({}\mathfrak{P}(X)\) の空でない全順序部分集合 \(\{Y_{\lambda}\}_{\lambda\in\Lambda}\) を与えたとする.このとき,\(\displaystyle\bigcup_{\lambda\in\Lambda}{}Y_{\lambda}\) は \(\{Y_{\lambda}\}_{\lambda\in\Lambda}\) の上界である.しかも,最小の上界,つまり上限である.このことは,各 \(Y_{\lambda}\) に対して \(Y_{\lambda}\subset{}Y\) であれば,\(y\in{}\displaystyle\bigcup_{\lambda\in\Lambda}Y_{\lambda}\) はある \(\lambda\in\Lambda\) について \(y\in{}Y_{\lambda}\) ゆえ \(y\in{}Y\) となることからわかる.

 

例 4.3.4 帰納的でない例

上界をもたない全順序集合は,帰納的半順序集合ではない.たとえば,\(\mathbb{R}\) について通常の順序を考えると,\(\mathbb{R}\) は \(\mathbb{R}\) の全順序部分集合だが上界をもたない.

 



ツォルンの補題の主張と証明の流れ

次に,ツォルンの補題の主張を述べる.その後,ツォルンの補題の選択公理による証明を述べるのだが,多少手間がかかる上に技術的な手続きが続くため,証明のスケッチを先に述べておくことにする.証明は,次の節にまわす.

ツォルンの補題は以下のような主張である.なお,半順序集合 \({}(X,\leq)\) の元 \(\omega\) が極大であることの定義は,任意の \(X\) の元 \(x\) に対して \(\omega\not<x\) であること,すなわち \(\omega\leq{}x\Rightarrow{}\omega=x\) なることである.

 

定理 4.3.5 ツォルンの補題

帰納的半順序集合には,少なくともひとつ極大元が存在する.

 

気持ちとしては,上界をとる作業を続ければ(無限集合でも)どっかで終わるよね,ということをいっている.この「無限集合でも」をさしはさむのに,本質的に選択公理を使うというわけである.

この補題の証明の流れを説明しよう.以下しばらくインフォーマルな説明を行うので,わからない部分は適宜とばしてもらえばよいと思う.

 

\({}(X,\leq)\) が帰納的半順序集合であるとし,順序は全て \(\leq\) を考えているとする.

なにか元をひとつあたえたとする.この元より大きい元をなにかひとつ与える.これを無限回くりかえして極大元に達する.この操作を実現したい.そのために「この元より大きい元」を与える操作を,いい感じに定式化したい.そのために,選択公理をつかう.

\(X\) 上の選択関数をひとつ与え,\(f\) とする.定式化は,\(X\) の全順序部分集合 \(W\) の上界を与えるような形で行う.\(X\) の全順序部分集合 \(W\) について,\(W\) の各元より大きい元の集合,つまり \(W\) の上界であって \(W\) の元でないものの集合 \(V\) を考える.\(V=\emptyset\) であれば,\(W\) の上界は極大元になる.われわれが興味があるのは,\(V\) が空でない場合でない場合に行うべきことである.\(V\) が空でない場合,\(V\) に対して \(f(V)\) は \(V\) の元であるので,\(W\) に \(f(V)\) を付け加えればよい.つまり,\(W\cup\{f(V)\}\) として \(W\) を大きくすればよい.このようにして,\(W\) を大きくすることを考える.

最初に与えるべき集合は,\(W=\emptyset\) の場合を考えることで,\(\{f(X)\}\) であるとわかる.ここから出発して,上記の操作を繰り返して得られる集合たちを考える.

そのために,この操作を(有限回とは限らない回数も含めて)繰り返して得られる集合たちが満たす条件を,証明の最初に与える.この集合たちは \({}(X,\leq)\) の整列部分集合となるので,ここで整列集合の概念を用いることになる.条件を満たす \(W\) たちの和集合をとることによって,元を無限回付け加える操作が達成される1)無限個の集合の和集合を考えることは,通常,公理として認められているので,それを使っている.\(W\) たちの和集合は全順序部分集合となり,その上界(これは仮定により存在がわかっている)が極大元であることを示すことで証明は完了する.

 



ツォルンの補題の証明

もう一度主張を述べておくと,「帰納的半順序集合には,少なくともひとつ極大元が存在する」である.これを,選択公理を仮定して証明する.

(この証明は大学で学ぶ数学の基礎的な部分で登場するものとしては長くて煩雑なので,不慣れな方々は頑張ってください.一応,説明はちょっとくどいくらいに詳しくしたつもりです.)

証明

\({}(X,\leq)\) を帰納的半順序集合とし,\(f\) を \(X\) 上の選択関数,すなわち,\(X\) の空でない部分集合 \(Y\) に対し,その元を与える(\(f(Y)\in{}Y\)である)ものとする.

\(X\) の整列部分集合 \(W\) とその元 \(a\) に対し,\(W\langle{}a\rangle\) の各元より大きい元すべての集まりを \(\Delta(W,a)\) とする.すなわち,

\[\Delta(W,a)=\{x\in{}X\mid{}b\in{}W\langle{}a\rangle\Rightarrow{}b<x\}\]

とする.\(X\) の空でない整列部分集合 \(W\)が任意の \(a\in{}W\) に対して

\[f(\Delta(W,a){})=a\]

をみたす時,\(f\) -列であるという.

\(f\) -列が欲しい性質をもっていることを,ここで確認しておこう.\(W\) が \(f\) -列であるとする.このとき,\(W\) の最小元を \(a_0\) とすると,\(a_0=f(\Delta(W,a_0){})=f(X)\) となる.\(W\setminus\{a_0\}\not=\emptyset\) のとき,\(W\setminus\{a_0\}\) の最小限を \(a_1\) とすると,\(a_1=f(\Delta(W,a_1){})=f(\{x\in{}X\mid{}a_0<x\})\) である.\(f\) -列 \(W\) が与えられたとき,\(Y=\{x\in{}X\mid{}b\in{}W\Rightarrow{}b<x\}\) に対し \(Y\not=\emptyset\) のとき,\(w=f(Y)\) とおくと \(W\cup\{w\}\) が \(f\) -列になるような条件を与えているのである.

以上のような状況から,以下のようなことが成り立つと推察できる.

  1. \(f\) -列は存在する.
  2. 2つの \(f\) -列 \(W_1,\ W_2\) が任意に与えられたとき,これらは一致するか片方が他方の切片である.
  3. \(f\) -列全ての和集合は \(f\) -列である.
  4. これは全順序部分集合ゆえ上界がとれ,それが極大元になっている.

 

実際に,これらはすべて成立している.その証明を書けば,ツォルンの補題の選択公理からの証明は完了する.

1:\(f\) -列は存在する,を示す.\(\{f(X)\}\) は \(X\) の部分集合で \(f\) -列である.実際,

\begin{align*}
\Delta(\{f(X)\},f(X){})&=\{x\in{}X\mid{}b\in\{f(X)\}\langle{}f(X)\rangle\Rightarrow{}b<x\}\\
&=\{x\in{}X\mid{}b\in\emptyset\Rightarrow{}b<x\}\\
&=\{x\in{}X\}=X
\end{align*}

であり,したがって

\[f(X)=f(\Delta(\{f(X)\},f(X){}){})\]

である.

 

2:2つの \(f\) -列 \(W_1,\ W_2\) が任意に与えたとき,これらは一致するか片方が他方の切片であることを示す.整列集合の比較可能定理(ここを参照)を用いる.比較可能定理により,必要ならば \(W_1,\ W_2\) を入れ替えることにより,\(W_1\)は \(W_2\),またはその切片と順序同型であるとしてよい.この同型写像を \(\varphi:W_1\to{}W_2\) とする2)\(\varphi\) の像は \(W_2\) の部分集合ゆえ,このような書き方でもよい..このとき,\(\varphi(w)=w\) が各 \(w\in{}W_1\) に対して成り立つことを示す.

\(V=\{w\in{}W_1\mid{}\varphi(w)\not=w\}\) とする.\(V\not=\emptyset\) とすると,\(W_1\) の整列性から \(V\) の最小元が存在する.それを \(v\) とおく.\(V\) と \(v\) の定義から,

\[W_1(v)=W_2(\varphi(v){})\]

である.したがって,

\begin{align*}
\Delta(W_1,v)&=\{x\in{}X\mid{}b\in{}W_1\langle{}v\rangle\Rightarrow{}b<x\}\\
&=\{x\in{}X\mid{}b\in{}W_2\langle{}\varphi(v)\rangle\Rightarrow{}b<x\}\\
&=\Delta(W_2,\varphi(v){})
\end{align*}

である.これと \(W_1,\ W_2\) が \(f\) -列であることから,

\begin{align*}
v&=f(\Delta(W_1,v){})\\
&=f(\Delta(W_2,\varphi(v){}){})\\
&=\varphi(v)
\end{align*}

である.これは \(v\not=\varphi(v)\) と矛盾する.以上により \(V=\emptyset\) でなければならず,結果として各 \(w\in{}W_1\) に対して \(\varphi(w)=w\) である.

 

\(f\) -列全体の集合を \(F\) とする.さらに,\(Z=\displaystyle\bigcup_{W\in{}F}W\) とおく.\(Z\) はすべての \(f\) -列の和集合である.3:\(Z\) は \(f\) -列である,を示す.その証明は3つに分けることにする.

3.1:\(Z\) は \(X\) の整列部分集合である.
3.2:任意の \(f\) -列は \(Z\) と,または \(Z\) の切片と一致する.
3.3:\(Z\) は \(f\) -列である.

 

3.1:\(Z\) は \(X\) の整列部分集合である,を示す.\(M\) を \(Z\) の空でない部分集合とする.このとき,\(Z\) の定義より,ある \(f\) -列 \(W\) があり,\(W\cap{}M\not=\emptyset\) である.そこで,\(\min(W\cap{}M)=m\) とおく.このとき,\(m\) は \(M\) の最小元である.

このことを背理法で示す.\(x<m\) なる \(x\in{}M\) が存在すると仮定する.このとき,ある \(f\) -列 \(W’\) があり,\(x\in{}W’\) である.2より,\(W,\ W’\) は一致するか片方が他方の切片である.さらに,

\[x\in(W’\cap{}M)\setminus(W\cap{}M)\subset{}W’\setminus{}W\]

なので,ある \(a\in{}W’\) があり \(W=W’\langle{}a\rangle\) となる.

このとき,\(m\in{}W\subset{}W’\) と \({}x(\in{}W’)<m\) から \(x\in{}W\) が得られる.\(x\in{}M\) であるので,\(x\in{}W\cap{}M\) であり,さらに \(x<m\) と仮定されていた.これは \(m=\min(W\cap{}M)\) と矛盾する.

したがって,\(m\) は \(M\) の最小限である.

以上より,\(Z\) の空でない任意の部分集合は最小元をもち,\(Z\) は \(X\) の整列部分集合である.

 

3.2:任意の \(f\) -列は \(Z\) と,または \(Z\) の切片と一致する,を示す.任意に \(f\) -列を与えたとし,それを \(W\) とおく.さらに,\(W\not=Z\) を仮定する.

\(Z\setminus{}W\) は,\(Z\) が \(f\) -列すべての和集合であることと \(W\not=Z\) から空でない.その最小元を \(a\) とする.このとき,\(Z\langle{}a\rangle\subset{}W\) である.

\(a\) は \(Z\) の元なので,\(a\) を 含む \(f\) -列が存在する.ひとつ与え,\(W’\) とする.\(a\in{}W’\) であるが,\(a\notin{}W\) である.これと2から,\(W\) は \(W’\) の切片であることがわかる.

\(W=W’\langle{}b\rangle\) であるとする.\(b=\min{(W’\setminus{}W)}\) であり,仮定から \(a\in{}W’\),\(a\) の定義から \(a\notin{}W\) なので,\(b\leq{}a\).

したがって

\[W’\langle{}b\rangle\subset{}W’\langle{}a\rangle\]

である.\(Z\)の定義から,

\[W’\langle{}a\rangle\subset{}Z\langle{}a\rangle\]

である.以上を合わせて,

\[Z\langle{}a\rangle\subset{}W=W’\langle{}b\rangle\subset{}W’\langle{}a\rangle\subset{}Z\langle{}a\rangle\]

なので,\[W=Z\langle{}a\rangle\]である.

 

3.3:\(Z\) は \(f\) -列である,を示す.

\(a\in{}Z\) を任意に与える.\(a\) を含む \(f\) -列をひとつ与え,\(W\) とする.

\(W=Z\) であれば,\(W\langle{}a\rangle={}Z\langle{}a\rangle\) である.

そうでない場合,ある \(b\in{}Z\) が存在して \(W=Z\langle{}b\rangle\) である.このとき,\(a\in{}W=Z\langle{}b\rangle\) より \(a\leq{}b\) であり,したがって,

\[Z\langle{}a\rangle=(Z\langle{}b\rangle)\langle{}a\rangle=W\langle{}a\rangle\]

である.

結局,どちらの場合でも,\(Z\langle{}a\rangle=W\langle{}a\rangle\) である.

よって,

\begin{align*}
\Delta(W,a)&=\{x\in{}X\mid{}b\in{}W\langle{}a\rangle\Rightarrow{}b<x\}\\
&=\{x\in{}X\mid{}b\in{}Z\langle{}a\rangle\Rightarrow{}b<x\}\\
&=\Delta(Z,a)
\end{align*}

であり,

\[a=f(\Delta(W,a){})=f(\Delta(Z,a){})\]

である.以上より,\(Z\) は \(f\) -列である.

 

4:\(Z\) は全順序部分集合ゆえ上界がとれ,それが極大元になっている,を示す.

\(Z\) は \(X\) の整列部分集合ゆえ,全順序部分集合でもある.したがって,仮定より \(Z\) の上界が存在する.\(Z\)の上界のひとつをあたえ \(\omega\) とおく.

\(\omega\) は極大元である.これを,背理法を用いて示す.

\(\omega\) は \(X\) で極大でないと仮定する.このとき,\(\omega<\omega’\) なる \(\omega’\in{}X\) が存在する.

\[\Delta=\{x\in{}X\mid{}b\in{}Z\Rightarrow{}b<x\}\]

とおく.\(\omega’\in{}\Delta\) であるので,\(\Delta\not=\emptyset\) である.そこで,\(\zeta=f(\Delta)(\in\Delta)\) とおく.

このとき,\(Z\cap{}\Delta=\emptyset\) ゆえ,\(\zeta\notin{}Z\) である.

\(Z’=Z\cup\{\zeta\}\) を考えると,\(Z’\) は \(f\) -列である.これを示す.

\(Z\) の整列性と \(Z\) の各元より \(\zeta\) が大きいことから,\(Z\cup\{\zeta\}\) は \(X\) の整列部分集合である.

任意に \(a\in{}Z’\) を与える.\(a\in{}Z\) のときは \(\Delta(Z’,a)=\Delta(Z,a)\) であることと \(Z\) が \(f\) -列であることから

\[f(\Delta(Z’,a){})=f(\Delta(Z,a){})=a\]

である.

\(a=\zeta\) のときは,

\begin{align*}
\Delta(Z’,a)&=\{x\in{}X\mid{}b\in{}Z’\langle{}a\rangle\Rightarrow{}b<x\}\\
&=\{x\in{}X\mid{}b\in{}Z\Rightarrow{}b<x\}\\
&=\Delta
\end{align*}

であるので,

\[f(\Delta(Z’,a){})=f(\Delta)=\zeta=a\]

となる.以上より,\(Z’\) は \(f\) -列である.

\(Z\) の定義より,\(Z’\subset{}Z\) であり,したがって \(\zeta\in{}Z\) である.これは,\(\zeta\notin{}Z\) と矛盾する.以上より,\(\omega\) は \({}(X,\leq)\) において極大である.

(証明終)

 

前の記事:4.2 選択公理に関する例

 


参考書籍

この記事の内容を勉強するにあたり,定番で,筆者も使用している本を紹介します.(定価は2020年09月16日時点のものを表記しています.)

 

まずひとつ目は,内田 伏一著「集合と位相」,通称「内田」です.筆者は主にこちらを使用しています.

数学の基礎となっている集合論の内容と位相空間論の内容をまとめた本です3)普通,大学の数学科では「集合と位相」というタイトルで講義が開講されるので,それに合わせた内容になっています..なお,筆者が用いているのはこれの旧版で,増補改訂版では,演習問題の解答が拡充されているようです.

 

 

 

ふたつ目は,松坂 和夫著「集合・位相入門」,通称「松坂」です.

内田同様,位相空間まで網羅した内容となっているほか,濃度の演算や順序数の古典的な扱いにふれられています(内田では省略されている).なお,筆者は,こちらの本も旧版を使っています.

 

 

前の記事:4.2 選択公理に関する例

References   [ + ]

1. 無限個の集合の和集合を考えることは,通常,公理として認められているので,それを使っている
2. \(\varphi\) の像は \(W_2\) の部分集合ゆえ,このような書き方でもよい.
3. 普通,大学の数学科では「集合と位相」というタイトルで講義が開講されるので,それに合わせた内容になっています.