読者です 読者をやめる 読者になる 読者になる

選択公理つづき

■定理 9 集合 A があり、集合Λの各要素λに対して A の部分集合で

整列集合であるような Wλが定まっているとし、

各 Wλは≦(λ)で順序づけられているとする。

(つまり a, b ∈ Wλに対して b が a 以上であることは a ≦(λ)b であらわされる。)

またλ,μをΛの異なる要素とすれば、Wλ, Wμのいずれか一方は他方の切片

になっていっるとする。そのとき W = ∪Wλ(λ∈Λ)は整列集合である。

かつ、任意の Wλは W 全体と一致するか W の切片となる。

[ 注 1 .∪Wλ (λ∈Λ)とは、λがΛの要素であるような集合 Wλすべての

合併集合のこと。

 注 2 Wμが Wλの切片であるということは、Wλのある要素 a によって

Wμ= Wλ と表され、かつ Wμ内では ≦(λ)と≦(μ) は両立している、

つまり x, y ∈ Wμに対し x ≦(λ)y ⇔ x ≦(μ)y.]

証明 まず x, y ∈ W のとき

(*) x ∈ Wλ, y ∈ Wλ

であるようなλ∈Λが存在することを示す。

 x ∈ Wμ, y ∈ Wν であるようなμ,ν∈Λが存在することは明らか。

仮定より、ある a ∈ Wνに対して Wμ = Wν となっているとしてよい。

このとき x, y ∈ Wνとなっているのでλ=νとすれば(*)が満たされる。

(*)が成り立つようなλに対し x ≦(λ)y であるとき、

W における関係 ≦ を x ≦ y で定めてよい。

実際、λ≠λなるλ∈Λ に対し x ∈ Wλ, y ∈ Wλであるとしても、

WλとWλは一方が他方の切片ゆえ

 x ≦(λ)y ⇔ x ≦(λ)y となるから、x, y の順序関係は(*)を満たすような

λ∈Λ の取り方によらない。

さて実際に ≦ が W における順序関係であるというためには

x, y, z ∈ W に対し (i) x ≦ x , (ii) x ≦ y かつ y ≦ x ⇒ x = y,

(iii) x ≦ y かつ y ≦ z ⇒ x ≦ z,

の3条件を確かめなければならないが、(i),(ii) は明らか。

(iii) は、x ∈ Wλ, y ∈ Wμ, z ∈ Wν であるとき、λ,μ,νのうちの少なくとも1つ、

たとえばλについて x, y, z ∈ Wλであることが簡単な考察でわかるから、

(iii)が成り立つことがわかる。

さて W が順序関係 ≦ によって整列集合となることを示そう。

すなわち W の空集合でない任意の部分集合 M をとるとき

min M が存在することを示す。

M∩Wλが空集合でないようなλがある。M∩Wλは整列集合 Wλの

部分集合だから min M∩Wλ= a が存在する。

x をM の任意の要素とすると、x ∈ Wλ なら x ∈ M∩Wλだから

a ≦ x. x が Wλの要素でないとする。

x ∈ Wμであるようなμ∈Λがある。

λ≠μで、Wμ⊂Wλではありえないから、仮定より Wλが Wμの切片と

なっている。

a ∈ Wλ, x ∈ Wμ- Wλだから、a ≦ x. したがって a = min M となり、

W は整列集合である。

 任意の Wλが W 全体であるかその切片であることを示す。

Wλが W の部分集合として定理 3の(2)を満たすこと、すなわち

 x ∈ Wλ, y ∈ W, x y ⇒ y ∈ Wλ

であることをいえばよい。x, y をともに含むような Wν (ν∈Λ)がある。

このとき λ=νであるか、Wνが Wλの切片であるか、WλがWνの切片であるか

のいずれかである。

はじめの2つの場合は明らかに y ∈ Wλ.

最後の場合でも Wλが Wνの部分集合として定理 3の(2)を満たすから

y ∈ Wλ. これで定理が証明された。 □

 最初のほうで順序集合の最大元・最小元を定義したが、

順序集合には他にもいくつか重要な概念がある。

 以下 A を順序集合とし、Bをその部分集合とする。

B も A の順序によって順序集合となる。

◆ A の要素 a で、B のどんな要素 x に対しても x ≦ a となるものが存在するとき、

a を B の A における上界といい、B は A において上に有界であるという。

B が A において上に有界であるとき、B の A における上界すべての集合をBとする。

α = minBが存在するとき、αを B の A における上限といい、α= supB であらわす。

同様に B の A における下界、B が A において下に有界であること、

B の A における下限 infB も定義される。

B が A において上にも下にも有界であるとき、単に B は A において有界であるという。

 A の部分集合 B に対し、supB も infB も存在するとは限らない。

◇ A の要素 a, b について、a ≦ b かつ a ≠ b のとき、a b で表し「 a は b より小さい」「 b は a より大きい」というのだった。

◆ B の要素 a で、a x であるような B の要素 x が存在しないとき、a を B の極大元という。

 これは最大元の定義と似ている。

 αが B の最大元であるというのは、α∈ B で、B のどんな要素 x に対しても x ≦α

となることだった。もし B が全順序集合なら、極大元も最大元と意味は同じになる。

しかし B が全順序集合でないなら、極大元 a に対し

a ≦ y でも y ≦ a でもない B の要素 y があるかも知れず、

その場合 a は最大元とはならないのである。

 そして B の要素 b で、x b であるような B の要素 x が存在しないとき、

b を B の極小元という。 

 順序集合において、極大元も極小元も存在するとは限らない。

◆ 順序集合 A の要素 a, b に対し、a b で a x b となるような A の要素 x が

存在しないとき、A の中で b は a の直後の要素、a は b の直前の要素という。

◆ 順序集合 A は、その空集合でない任意の全順序部分集合が A の中に上限をもつとき、

帰納的であるといわれる。

定理10 A を帰納的な順序集合とし、Φは A から A への写像で、A の

すべての要素 x に対してΦ(x) ≧ x となるものとする。

そのときΦ(a) = a となるような A の要素 a が(少なくとも1つ)存在する。

証明 A の1つの要素 x0 を任意に固定しておき、A の部分集合 W で次の条件 (i)-(iv) を

満たすものを考える。

(i) W は( A の部分順序集合として)整列集合である。

(ii) min W = x0.

(iii) W の要素 x が W の中に直前の要素 x* をもつならば x = Φ(x*).

(iv) W の要素 x (≠x0) が W の中に直前の要素をもたなければ、

W の x による切片 Wx = { y | y ∈ W, y x }

の A における上限が x に一致する : x = sup Wx.

以上の4条件を満たすような A の部分集合は、実際存在する。

たとえば x0 のみからなる集合 { x0 } は (i)-(iv) を満たす

( (iii),(iv) については前提がそもそも成り立たない)。

そこで条件 (i)-(iv) を満たすような A の部分集合の全体を Ω とする。

いま注意したことによって Ω は空集合ではない。

次に W, W∈Ω とすれば、W = Wであるか、

またはそのいずれか一方が他方の切片と一致することを示そう。

W, W は (i) より整列集合だから、定理 8より W W であるか、

またはそのいずれか一方が他方の切片に順序同型である。

いずれの場合も同様であるから、たとえば「W Wb ⇒ W = Wb 」を示そう。

f : W → Wb を順序同型写像とする。このとき W の任意の要素 x に対し

f(x) = x であることを示せば、W = Wb が結論される。

これを超限帰納法で示す。

まず x0 = min W = min W= min Wb だから f(x0) = x0 は明らか。

次に x0 以外の W の任意の要素 x をとり、y x であるような

W のすべての要素 y に対し f(y) = y であると仮定する。

そのとき、もし x が W の中に直前の要素 x* をもてば、

f が順序同型写像であることから、f(x*) は Wb の中で、したがってまた Wの中で

f(x) の直前の要素であることがわかる。

仮定から f(x*) = x* だから、条件 (iii) によって

 f(x) = Φ(f(x*)) = Φ(x*) = x.

x が W の中に直前の要素をもたなければ、同じく f が順序同型写像であることから、

f(x) は Wb の中に、したがってまた Wの中に直前の要素をもたない。

かつ明らかに Wx の f による像は (Wb)f(x) = Wf(x) であるが、

仮定より Wx の任意の要素 y について f(y) = y となるので Wx = Wf(x).

したがって条件 (iv) から

 f(x) = sup Wf(x) = sup Wx = x.

以上より W = Wb が証明された。

これで、Ωに属する2つの集合は、一致するか、またはそのいずれか一方が他方の

切片と一致することがわかった。

 すると定理 9より、Ωに属するすべての集合の合併集合 W0 は整列集合となる。

かつ、同じく定理 9より、Ωに属するどの集合 W も、W0 と一致するか、W0 の切片となる。

このことから W0 は条件 (i)-(iv) を満たすことが分かる。

(i) はいま述べた。

(ii) min W0 = x0 は明らかである。

(iii) W0 の要素 x が W0 の中に直前の要素 x* をもつとする。

x ∈ W, x* ∈ WであるようなΩの要素 W, Wがある。

W = Wの場合、x, x* はともに W に含まれる。

W = Wb の場合、x ∈ Wb で x* x だから x* ∈ Wb となり

x, x* はともに Wに含まれる。

Wb = Wの場合、x が Wb に含まれないとしても x* は Wb に含まれ、

このとき x, x* はともに W に含まれる。

結局、x, x* をともに含むようなΩの要素 V が必ずあることになる。

V は (iii) を満たすから、x = Φ(x*) が成り立ち、W0 も (iii) を満たすことになる。

(iv) W0 の要素 x (≠x0) が W0 の中に直前の要素をもたないとする。

W0x = { y | y ∈ W0, y x } の A における上限が x であることを示せばよい。

まず W0 が整列集合であることから明らかに W0x も整列集合であり、

A が帰納的だから、 W0x は A の中に上限をもつ。

そして x は W0x の A における上界だから、sup W0x ≦ x.

x を含むようなΩの要素 V があり、V は W0 の部分集合だから、x は V の中に

直前の要素をもたない。V は (iv)を満たすから sup Vx = x.

Vx ⊂ W0x より sup Vx ≦ sup W0x,

つまり x ≦ sup W0x.

したがって W0x = x であり、WO は (iv) を満たす。

 W0 が (i)-(iv) を満たすことがわかったので W0 ∈ Ω.

W0 は(包含関係 ⊂ の意味で)Ω の最大元である。

W0 は整列集合で、A が帰納的だから、sup W0 = a が存在する。

a ∈ W0 でなければならない。というのも、a が W0 に属さないとすると、

W0 に a を付け加えた集合を W0= W0∪{ a } としたとき、

次のように W0が(i)-(iv)を満たすことになってしまう。

(i) a を最大元とする W0が整列集合であるのは明らか。

(ii) min W0= x0 なのも明らか。

(iii) 検証すべきは a が W0の中に直前の要素 a* をもつ場合だが

このとき a* ∈ W0 で、a* x a であるような x ∈ W0 は存在しない。

これは a* が W0 の最大元であることを意味している。

順序集合に最大元があればそれは上限でもあるので、それは a の決め方に反する。

(iv) 上でいったように a は W0の中に直前の要素をもたず、

sup W0 = a を示せばよいが、W0 = W0 であるからこれは明らか。

 つまり W0は (i)-(iv) を満たし、W0がΩに属することになるが、

これは W0 がΩの最大元であることに反する。

よって a ∈ W0 であり、a = max W0.

 この a について、Φ(a) = a であることを示そう。

Φの定義から Φ(a) ≧ a だから、Φ(a) a であると仮定して矛盾を導く。

しかし Φ(a) a なら Φ(a) は W0 に属さず、W0 に Φ(a) を付け加えた

 W0= W0∪{ Φ(a) } が (i)-(iv) を満たすことが上と同様にしてわかり、

やはり矛盾が生じる。

 以上より Φ(a) = a. □

次の定理を証明するのに選択公理を使う。

定理 11 A を極大元をもたない順序集合とすれば、A から A への写像Ψで、

A のすべての要素 x に対して Ψ(x) x となるものが存在する。

証明 空集合でない A の部分集合をすべてあつめた集合をΩとする。

選択公理によって、Ωで定義された写像 ψで、Ωのすべての要素 M に対して

ψ(M) ∈ M となるものが存在する。

つまりψは、Ωに属する各集合 M に対して、M の要素を1つ指定するもので、

そこで指定された要素を ψ(M) とかいている。

いま A の要素 x に対して、Mx = { y | y ∈ A, y x } とおく。

A には極大元がないのだから、A のどの要素 x に対しても Mx は空集合でない。

実際 Mx が空集合なら、y x であるような A の要素 y が無いことになり、

それは x が A の極大元であることを意味しているからである。

Mx はつねに空集合でないのだから、Mx ∈ Ω.

そこで A の任意の要素 x に対して Ψ(x) = ψ(Mx) と定めると、

Ψ は A から A への写像で、Ψ(x) は Mx のある要素なのだから、

Mx の定義によって Ψ(x) x. □

ツォルンの補題 帰納的な順序集合は(少なくとも1つ)極大元をもつ。

証明 a ≧ b は「 a b または a = b 」の意味なのだから、

定理 11の「Ψ(x) x 」の部分を「Ψ(x) ≧ x 」と書き換えたものも

成立する。しかし Ψ(x) = x となることはないのだから、

定理 10を考え合わせると、定理 11における A は帰納的でないことになる。

すなわち順序集合 A について「 A が極大元をもたない ⇒ A は帰納的でない」

である。言い換えれば「 A が帰納的である ⇒ A は極大元をもつ」である。□

◆ 一般に順序集合 W といっても、そこに定められうる順序は1通りとは限らない。

そこでたとえば W に ≦, ⊆ と2通りの順序があるとき、

≦ を順序と考えている順序集合を ( W, ≦ ) と表し、

⊆ を順序と考えている順序集合を ( W, ⊆ ) と表すことによって区別する。

順序集合を ( W, ≦ ) のように表したとき、集合 W のことをその台集合

ということがある。

整列可能定理 A を任意の集合とするとき、A に適当な順序 ≦ を定義して、

( A, ≦ )を整列集合とすることができる。

証明 A の各部分集合には、一般に、幾通りもの順序が考えられる。

いま、A の部分集合 W とそこで定義された順序 Q との組 ( W, Q )

を考え、このような組のうち、整列集合となっているようなものの全体を

Ωとする。Ωは空集合ではない。たとえば、A のただ1個の要素 a から

なる集合 { a } にはただ1通りの順序 Q が定義されるが、

この ( { a }, Q ) は明らかに整列集合である。

次にΩの2つの要素 ( W, Q ), ( W, Q) に対し、両者が一致するとき

(すなわち W = W かつ Q = Qとなっているとき)、または

( W, Q ) が ( W, Q) の切片となっているとき、

  ( W, Q )ρ( W, Q)

として、関係ρを定義する。このρがΩにおける順序関係となっていること

はすぐにわかる。しかも、この順序関係ρについて、Ωは帰納的な順序集合

となる。実際、Ψを(ρに関する)Ωの任意の全順序部分集合とすると

定理 9からわかるように、Ψの要素 ( W, Q ) の台集合全部の合併集合

W* = ∪{ W | ( W, Q )∈Ψ } には、次のような性質をもつ順序関係 Q*

が定義される。

(i) ( W*, Q*) は整列集合である。(したがって( W*, Q*)∈Ω.)

(ii) Ψの各要素 ( W, Q ) は ( W*, Q*) と一致するか、またはその切片

となる。(したがって( W, Q )ρ( W*, Q*).)

この ( W*, Q*) がΩにおけるΨの上限となる。

したがって ( Ω, ρ ) は帰納的となる。

ゆえにツォルンの補題によって ( Ω, ρ ) には極大元 ( Wo, Qo ) が

存在する。このとき、実は Wo = A となる。実際 Wo ≠ A とすると

A - Wo から1つの要素 a をとって Wo∪{ a } = W1 とし、

a を最後の要素として Wo の順序 Qo を W1 の順序 Q1 に拡張する。

そうすれば明らかに ( W1, Q1 ) ∈ Ω で、( Wo, Qo ) は

( W1, Q1 ) の切片になる。すなわち ( W1, Q1 ) は順序ρの意味で

( Wo, Qo ) より大きなΩの要素となる。これは ( Wo, Qo ) の極大性

に反するから、Wo = A でなければならない。そこで Qo を ≦ と

すれば、≦ は A における順序で、しかも ( A, ≦ ) は整列集合となる。□

整列可能定理 ⇒ 選択公理

証明 任意の集合 A に対し、その部分集合全体をあつめた集合をΩとする。

このとき、任意の M ∈ Ω に対して Ψ(M) ∈ M となるようなΩで定義された

写像 Ψ が存在する。なぜならば、整列可能定理によって A に適当な順序

≦ を定めれば ( A, ≦ ) が整列集合であるようにできて、A の任意の

部分集合 M に対し Ψ(M) = min M と定めればよい。

いま集合 K について、K の各要素λに対し空でない集合 Aλが定められているとき、

ΠAλ (λ∈ K ) から要素を取り出せることを示したい。

そのためには各集合 Aλ からそこに属する要素 aλが指定できればよい。

ここで A = ∪Aλ (λ∈ K ) とおけば、各 Aλは A の部分集合であることから、

前半の話を適用すると、Ψ(Aλ) ∈ Aλ となるようなΩで定義された写像Ψ

があるから、aλ=Ψ(Aλ) とおけばよい。□