集合論ゼミ 2012 年 11 月 27 日
石井大海
早稲田大学基幹理工学部
数学科三年2012 年 11 月 27 日

帰納定理による定義
集合論の強力な武器の一つに整列集合上の再帰的定義がある．
F (x) の値を Ax での F の振舞いに依存して決めたい．それを精密化したのが次の定理：

Th. 2.9 (von Neumann 1923 & 1928a)⟨A, R⟩ : 整列クラス，τ : 集合項（集合やクラスパラメタを含んでいてもよい）とすると，次を満たすような函数 F が一意に存在す
る1 ．
(∀x ∈ A)F (x) = τ (F ↿ Ax )2(1)
τ (x, F ↿ Ax ) としてもよいが，整列性から A ∼ Dom(F ↿ Ax ) の最小元として取れるのでこれで十分である．
(1) から F の取り得る値が判るが，具体的に函数を定義するクラス項を与えないとしっかりした存在証明にならない！
12

このような帰納的定義を “course of value recursion” と云う，らしい．
ω などには「その一つ前」がないので，切片の上に定義している．

証明の概要a.

F , F ′ を A の始切片上で定義され (1) を満たす函数とする．
このとき F , F ′ が両立することを超限帰納法により示す．

b.

すると，特に A は A 自身の切片なので，定理の主張する Fが一意に定まることが判る．

c.

T を A の切片上で定義された函数 f で (1) を満たすもの全体とする（これらの函数は特に集合）．I .6.30(ii) より ∪T は集合となるので，F = ∪T とする．これが (1) を満たすことを示す．

d.

Dom(F ) = A を示す．Dom(F ) ̸= A とし，h を Dom(F ) の直後の元まで定義域を拡張した函数とする．このとき h ∈ Tを示して矛盾を導く．

(a) の証明.
F , F ′ を A の始切片上で定義されて (1) を満たす函数とし，これらが両立する事を超限帰納法により示す．よって，∀x ∈ A に対し，
yRx → (y ∈ Dom(F ) ∩ Dom(F ′ ) → F (y ) = F ′ (y ))を帰納法の仮定とし，

x ∈ Dom(F ) ∩ Dom(F ′ ) → F (x) = F ′ (x)を示せばよい．x ∈ Dom(F ) ∩ Dom(F ) とすると，F , F ′ の定義域が切片であることから yRx → y ∈ Dom(F ) ∩ Dom(F ′ ) が成立する．よって帰納法の仮定より yRx → F (y ) = F ′ (y ) となる．
よって，F ↿ Ax = F ′ ↿ Ax(2)が成立する．仮定から F , F ′ は (1) を満たすので，(2)F (x) = τ (F ↿ Ax ) = τ (F ′ ↿ Ax ) = F ′ (x) よって F (x) = F ′ (x) となり示された．

(b) の証明.
A は特に A 自身の始切片であるので，(a) から A 上に定義された函数はみな両立し，それらはドメインが一致するので，従って Fは存在すれば一意に定まる事が判る．

(c) の証明.
T を A の始切片上の集合である函数 f で (1) を満たすもの全体のクラスとする．即ち，f ∈ T とx ∈ Dom(f ) → f (x) = τ (f ↿ Ax )(3)は同値である．(a) より T の任意の二元は両立するので，
I .6.30(ii) より ∪T は函数となる．そこで F = ∪T と置いて，まずこれが (1) を満たすことを見る．x ∈ Dom(F ) とすると定義より (∃f ∈ T )x ∈ Dom(f ) とでき，特に T の定義から Dom(f ) はA の始切片である．従って Ax ⊆ Dom(f ) となる．F = ∪T ⊇ f
なので，F (x) = f (x) かつ F ↿ Ax = f ↿ Ax を得る．よって，
F (x) = f (x) = τ (f ↿ Ax ) = τ (F ↿ Ax ) となり (1) が成立する．

(d) の証明.
Dom(F ) ⊂ A とする．始切片の和は始切片となるので，Dom(F ) = ∪ { Dom(f ) | f ∈ T } も始切片となる．特にDom(F ) ̸= A なので 2.4 より Dom(F ) は A の断面となる．そこで Dom(F ) = Az と置く．Az は集合なので，f も集合となる．そこで，
h = F ∪ {⟨z, τ (F )⟩}とすれば，h は明かに函数を定める．この時，h ∈ T となることを示す．h の定義域は明らかに A の始切片であるので，(∀x ∈ Dom(h))h(x) = τ (h ↿ Ax ) を示せば証明が終わる．
1.

2.

x ∈ Dom(F ) のとき．h, F は (a) より両立する．特に，
Ax ⊆ Dom(F ) ⊆ Dom(h) であるので
h(x) = F (x) = τ (F ↿ Ax ) = τ (h ↿ Ax ) となり良い．
x = z のとき．h の定義および F = h ↿ Az より，h(z) = τ (F ) = τ (h ↿ Az ) となり OK．

よって h ∈ T ．よって，h ⊆ F より z ∈ Dom(h) ⊆ Dom(F ) となり，z ∈/ Dom(F ) に矛盾．よって Dom(F ) = A．

帰納的定義におけるパラメータ I
τ が集合変数 u とクラス変数 W を含む場合，帰納的定義により得られる F のクラス項は次のようになる：{()}
Dom(f ) は ⟨A,R⟩ の始切片t ∃f ∧(∀x∈Dom(f))(f (x)=τ (f ↿Ax ,u,W ))∧t∈f
これとは変えて，定義する函数の引数に集合変数 u を追加することが出来る．そんな函数を F ′ と書くことにすると，F ′ は次を満たす A × V 上の函数．

⟨⟩(∀u ∈ V )(∀x ∈ A)F ′ (u, x) = τ ( F ′ (u, y ) y ∈ A ∧ yRx , u) (1)
このとき，F ′ を表すクラス項は次のようになる．
{()}
Dom(f ) は ⟨A,R⟩ の始切片⟨⟨u, x⟩ , z⟩ ∃f ∧(∀v ∈Dom(f))(f (v )=τ (f ↿Ax ,u))∧⟨x,z⟩∈f帰納的定義におけるパラメータ II(1) において，F ′ の値は yRx なる全ての y と u におけるF ′ (u, y ) の値に依存しているが，u ̸= u ′ なる u ′ での値には依存していない．
ここで，F ′ を y だけではなく x, y に依存して決まる集合 s の任意の元 u ∈ s での値に依存するように変更することも出来る．しかし，一般に任意の集合 u での値に依存するようにしようとすると，これは集合論の定理にはらなない．
←この意味がイマイチよくわからない……．

クラスの帰納的定義 ICor. 2.11
⟨A, R⟩ : 整列クラス, Φ : 論理式⇒ 部分クラス P ⊆ A が一意に存在し，(∀x ∈ A)(x ∈ P ↔ Φ(Ax ∩ P))
後から補足．最小元から順に元を取って考えてみると，「成り立っている間だけ取ってきた」ものが P であることがわかる．
後から補足その 2．整列集合に関する証明や直観を把むには，まず「始めから見る」ことが大事！

クラスの帰納的定義 II
証明の概略.
P の特性函数を帰納的定義により定めればよい．まず項 τ を，
{1 Φ({ x | f (x) = 1 })τ (f ) =0 ¬Φ({ x | f (x) = 1 })とする．F (x) = τ (F ↿ Ax ) により A 上の函数 F を帰納的に定義
し，P = { x | F (x) = 1 } とおけばよい．実際，x ∈ P ↔ F (x) = 1 ↔ τ (F ↿ Ax ) = 1↔ Φ({ y | (F ↿ Ax )(y ) = 1 })↔ Φ({ y | F (y ) = 1 } ∩ Ax ) ↔ Φ(P ∩ Ax )

である．

.

条件付き帰納的定義

函数が A 全体ではなく，特定の A の切片上で定義されていれば十分な場合がある．切片が具体的に判らない場合もあるので，そういった場合の定義法を用意しておく．

Th. 2.12⟨A, R⟩ : 整列クラス, τ (f ) : 項, Φ(f ) : 論理式とする．このとき，次を満たす ⟨A, R⟩ の始切片 C と C 上の函数
H が一意的に存在する：
H(x) = τ (H ↿ Ax )(2)(∀x ∈ C ) Φ(H ↿ Ax )(3)

また，特に C ̸= A のとき（即ち C が A の断面のとき），C に含まれない最小の元を z とすると，次が成立する：¬Φ(H ↿ Az ) (i.e.¬Φ(H))(4)

すなわち，H は Φ(H ↿ Ax ) が成立する間だけ定義されている．

Proof.
まず，函数 F を通常の帰納的定義によって F (x) = τ (F ↿ Ax ) により A 全体で定める．

C := { z ∈ A | (∀x ∈ A)(xRz ∨ x = z → Φ(F ↿ Ax )) }すると，C は明らかに A の始切片となり，特に定義より(∀x ∈ C ) Φ(F ↿ Ax ) が成立する．また，A ̸= C の時は A ∼ C の最小元 z を取れば明らかに¬Φ(F ↿ Az )となる．よって， H = F ↿ C と置けばこれらは (2) ∼ (4) を満たす．一意性については前の定理と同様にして証明出来る．

Th. 2.13⟨A, <⟩ : 整列クラス

F : ⟨A, <⟩ からその中への増加函数⇒ (∀x ∈ A) x ≤ F (x)Proof.
帰納法により示す．帰納法の仮定は y < x → y ≤ F (y ) である．
これを用いて x ≤ F (x) を示す．
F の増加性から，y < x のとき F (y ) < F (x) が成立する．よって仮定と組み合わせて，y < x → y < F (x)を得る．F (x) < x とすると，特に上式で y = F (x) とすればF (x) < F (x) となり矛盾．よって全順序性から x ≤ F (x) となる．

Cor. 2.14
⟨A, <⟩ : 整列クラス B ⊆ A : strictly bdd.
⇒ ⟨A, <⟩ ̸∼= ⟨B, <⟩Proof.
y ∈ A を B の狭義上界とし，F : ⟨A, <⟩ ∼= ⟨B, <⟩ が存在したとす
る．F は自分自身の中への増加関数であるので，前定理より特にy ≤ F (y ) ∈ B ．よって y 以上の元が B に存在することになってしまい，y が B の狭義上界であることに反する．

Cor. 2.15
整列クラス ⟨A, <⟩ の自己同型は，恒等写像 I = ⟨x | x ∈ A⟩
のみである．
2. ⟨A, <⟩ ∼= ⟨B, <⟩1.

⇒ ⟨A, <⟩ から ⟨B, <⟩ への同型写像は一意的に定まる．

Proof.
1.

2.

∼F : ⟨A, <⟩ → ⟨A, <⟩ とすると，系 2.14 より x ≤ F (x)．また，F −1 も同型写像であるので x ≤ F −1 (x)．これらを合わせて x = F (x) を得る．
∼G , F : ⟨A, <⟩ → ⟨B, <⟩ とすると，∼∼
GF −1 : B → B, F −1 G : A → A などは同型となり，前の結果
から GF −1 = I , F −1 G = I となる．したがって
F = (G −1 )−1 = G ．

後から補足．これと対照的に，整列集合ではなく全順序集合の場合（例えば R, Q など）には自己同型は複数存在する．それらに位相を入れて研究したりもするらしい．

Th. 2.16⟨A, <⟩ , ⟨B, <⟩ をそれぞれ整列クラスとすると，A と B が同型であるか，または一方がもう一方の断面と同型になる．
一方の最小元をもう一方の最小元に，その直後の元を……と対応させて行けばよい．構成には条件付きの帰納的定義を使う．

同型写像 H の構成.
H(x) = B ∼ H[Ax ] の <-極小元(1)となるように函数 H を定め，x ∈ C ↔ B ∼ H[Ax ] ̸= 0 となるよ
うに C を取りたい．
{min(B ∼ Rng(f )) (B ∼ Rng(f ) ̸= 0)
τ (f ) =(2)0(B ∼ Rng(f ) = 0)

Φ(f ) . ≡ . B ∼ Rng(f ) ̸= 0(3)とおいて，条件付き帰納的定義を使えば，このような H が実際に構成出来る．

H が同型であること.
定理 1.13 によれば，全順序クラスから半順序クラスの中への増加函数は同型写像となる．よって，H が C = Dom(H) から B の中への増加函数であることを示そう．
x, y ∈ C , x < y とする．定義より H(y ) は B ∼ H[Ay ] の最小元である．よって，H(y ) ∈/ H[Ay ]．他方，x < y より x ∈ Ay であるので H(x) ∈ H[Ay ]．よって H(x) ̸= H(y ) となる．
また，H[Ax ] ⊆ H[Ay ] より H(y ) ∈/ H[Ax ] なので，H(y ) ∈ B ∼ H[Ax ]．ここで x は B ∼ H[Ax ] の最小元であり，また上の議論から H(x) ̸= H(y ) であったので， H(x) < H(y ) となる．
以上より H は整列クラス B の中への増加函数であるので，従って同型写像である．

Rng(H) が B の始切片であること.
以下，D = Rng(H) と置く．u ∈ B, v ∈ D, u < v として v ∈ Dを示せばよい．v ∈ D なので，ある x ∈ A により v = H(x) と書ける．すると u < H(x) であり，H(x) は B ∼ H[Ax ] の最小の元であったから u ∈ H[Ax ] ⊆ D となる．よって D は B の始切片である．
あとは H の定義域が A の全体であるかその真部分集合となっているかによって場合分けをすれば終わる．

Dom(H) = A の場合.
A は B の始切片 D と同型である．整列クラス B 上の始切片はB 自身であるか B の始断面であるかのどちらかなので，よって命題は但しい．

C = Dom(H) ̸= A の場合.
定理 2.12 より C は始切片であり，特に A と一致しないので Cは A の始断面となる．再び定理の結果より，¬Φ(H) が成立する．
よって Φ の定義を展開すれば，

B ∼ Rng(H) = 0となり，B = Rng(H) となるので，B は A の始断面と同型である．

比較可能定理

前定理の結果は，更に強い一意性の条件を付けることが出来る．

Prop. 2.17
⟨A, <⟩ , ⟨B, <⟩ : 整列クラス とするとき，次のいずれか一つだけが成立：
a. ⟨A, <⟩ ∼= ⟨B, <⟩b.

⟨A, <⟩ は ⟨B, <⟩ の一意な断面と同型．

c.

⟨B, <⟩ は ⟨A, <⟩ の一意な断面と同型．

証明の概略.
前の定理は，(a) ∼ (c) のうち少なくとも一つが成立すると云うこと．ここでは一意性が増えている．以下の二つの場合に分けて証明される．

(i) (a)(b) または (b)(c) が成立するか，(b)(c) の断面が一意でないとき．
この時，整列クラス ⟨C , <⟩ , ⟨D, <⟩ があり， C は D の異なる二つの始切片 D ′ , D ′′ と同型になっている．
(ii) (b)(c) が成立．
いずれの場合も，整列クラスは自身の断面と同型になることはな
いと云う命題 2.14 に矛盾することがわかる．

別証明
Proof.
前の二つの定理は，些か直観的ではないが次のように短かく証明出来る．
defy H z ⇐⇒ y ∈ A ∧ z ∈ B ∧ ⟨Ay , <⟩ ∼= ⟨Bz , <⟩と置くと，H が函数となることは容易にわかり，これが定理 2.16で必要な同型射となっている．
命題 2.17 は，(a) ∼ (c) それぞれの場合の同型射が H に含まれることがわかり，また H は明らかに各場合の同型射に含まれるので，従って H と一致することがわかる．このことから一意性が出る．

真の整列クラス I
今の定理から真の整列クラスに関して次が云える．

Cor. 2.18⟨A, <⟩ : 真の整列クラス ⟨B, <⟩ : 整列クラス{B が集合↔ ⟨A, <⟩ が ⟨B, <⟩ の断面と同型⇒
B が真のクラス ↔ ⟨A, <⟩ ∼= ⟨B, <⟩特に，真の整列クラスは同型を除いて一つしか存在しない．
これが成立するのは，整列クラスの定義に left-narrow 性を課しているからである．この条件によって，整列クラスが集合であるためには断面と同型でなくてはならず，逆も明らか．したがってその帰結として真の整列クラスが同型を除いて一意に存在することが判る．

真の整列クラス II
Rem. 2.19
left-narrow 性を外せば，即ち，
1.

R は A 上の全順序である．

2.

A の空でない部分集合は R-極小元を持つの二条件だけに限れば，これを満たすような真のクラス A には同型でないものが多数存在する．そこで上の二条件を満たす構造⟨A, R⟩ のことを弱い整列クラスと呼ぶことにする．
このとき，弱い整列クラスだが整列クラスではないものは明らかに真クラスとなる．
真の整列クラスの存在は後程示す．その存在を仮定すれば，⟨B, <⟩ : 真の整列クラス, ⟨C , <⟩ : 空でない整列クラス, B ∩ C = 0とすると，⟨B, <⟩ ⊕ ⟨C , <⟩ は弱い整列クラスだが整列クラスではない．このような順序和が同型であるのは，対応する ⟨C , <⟩ が同型の時のみである．

整列クラスの部分集合の性質

Prop. 2.20
⟨A, <⟩ : 整列クラス B ⊆ A⇒ ⟨A, <⟩ ∼= ⟨B, <⟩ ∨ (∃x ∈ A) ⟨Ax , <⟩ ∼= ⟨B, <⟩Proof.
⟨A, <⟩ ̸∼= ⟨B, <⟩ ∧ ¬(∃x ∈ A) ⟨Ax , <⟩ ∼= ⟨B, <⟩ とする．命題 2.17より (∃u ∈ B)(⟨A, <⟩ ∼= ⟨Bu , <⟩) となる．このとき Bu は u を狭義上界とする A の真の有界部分クラス．しかし定理 2.14 より Aは自身の真の有界部分クラスと同型となることはないので矛盾．
よって上のどちらかが成立する．

整列可能性 I
整列順序が活躍するのは次の二つ．
• 最小元原理（⇔ 超限帰納法）• 帰納的定義

整列順序が入れられるようなクラスがあった場合，F (x) = xn → x なる数列 {xn }∞n=1のような，曖昧な定義に対しても，適当な整列順序を固定してその最小元を取ってくるように解釈すれば，きちんとした定義になる．
また，何かクラスの上で段階的に何か構造を作っていく際に，整列順序が入れば帰納的定義が出来る．
そこで，「どのようなクラスが整列出来るか？」ということが問題になってくる．どんなクラスでも整列出来るのなら便利だが，クラス一般については後程やるとして，当面の間は集合の整列可能性だけ考えれば充分である．

整列可能性 II
ZF では任意の集合が整列可能であることは示せない．しかし．
選択公理を認めれば次の命題が成立し，特にこれは選択公理と同値になる．

Th. 2.23
任意の集合 a に対し，a を整列する関係 r が存在する．
これは選択公理ほど明らかではないので，選択公理を導入してそこから証明して始めて受け容れられる．以後はなるべく選択公理を使わずに議論を進めたいので，整列可能集合の概念を定義し，それを使うことにする．

Def. 2.24
def

集合 a が整列可能 ⇐⇒ ∃r : r は a を整列