初等部分構造の集合論での応用

初等部分構造の集合論での応用

渕野 昌 (Saka´ e Fuchino)

[email protected]

2009 年 10 月 (June 7, 2021 (11:34) 版 )

目次

1. 構造と充足関係 . . . . 1

2. 部分構造，初等的部分構造 . . . . 4

3. Downward L¨ owenheim-Skolem 定理 . . . . 7

4. H (χ) . . . . 10

5. 絶対性と H (χ) で成り立つ集合論の公理 . . . . 13

6. 初等部分構造の集合論での応用 . . . . 16

7. ω-covering な初等部分構造 . . . . 20

8. Fodor-type Reflection Principle とその拡張 . . . . 22

9. さらに勉強を進めたい人のために . . . . 23

参考文献 . . . . 24

1 ^{構造と充足関係}

str-satisf

A = h A, R

, R

, ... i が，構造 (structure) であるとは，

*

本稿は， 2009 年 9 月に筑波大学大学院数理物質科学研究科数学専攻で開講された集中講義の講義録 です．この講義の内容は， 1997 年 8 月 4 日 – 6 日に静岡県三保の東海大学研修館において開催された数学 基礎論サマースクールで行なった講義の講義録 (https://fuchino.ddo.jp/notes/elementary.pdf) をベースとして作成しました．本稿の，このヴァージョンはまだ最終稿ではなく，書きかけの部分や 作成途中の “ゴミ” を含んでいる可能性もあります．間違いの指摘やコメントなど歓迎します．

このテキストの最新版は https://fuchino.ddo.jp/notes/elementary09.pdf としてダウンロー ドできます．

このテキストは，2009 年以降ほとんど修正なしに放置していたものです．筆者は，2020 年の暮に

必要があって Python の勉強を始めたところ，2021 年 01 月に pyt erf 氏から，いくつかの質問／指

摘を受け，これを期に，第 4 節と，第 6 節の一部で，前から気になっていた細部の修正と説明の補足

を書き加えました．氏に感謝します．

(1.1) A は集合（A を A のサポートとよぶことにする）;

(1.2) 各 i = 1, 2, ... に対し， m

∈ N があって， R

⊆ A

（つまり， R

は A 上の

m

-項関係）

となっていること，とする．上のような構造は， relational structure と呼ばれ，より 一般には，構造は， A 上の関数や定数（特定された A の元）を含むこともあるもの として導入される．しかし，このノートでは，主に， h A, E, ... i という形の（関係の みを構造として持つ） relational structure で， E = {h x, y i ∈ A

: x ∈ y } となって いるようなものが考察される．以下では，このような構造を考察するときには，簡単

のために，これを h A, ∈ , ... i と記すことにする．

R

, R

,... に対応する記号 R

, R

,... を用意して， L = { R

, R

, ... } を A の言語 (language) とよぶ．また A は L -構造 ( L -structure) であるともいう．以下では，簡 単のために L は常に高々可算であると仮定する．

L - 構造 A = h A, ... i に関する命題のうち， L - 構造の一つ一つの元を調べることの みによって（たとえば， A の部分集合の全体を調べたりしなくても）その真偽の確定 するようなものは，以下で導入する， （一階の）述語論理の論理式と呼ばれるものを 用いてあらわすことができる．

まず，変数の可算無限集合 V ar を固定しておき

，これを用いて L -論理式 ( L - formulae or L -formulas) を次のように帰納的に定義する :

(1.3) x, y ∈ V ar のとき， ‘x = y’ は L - 論理式である ;

(1.4) R が L の m 項関係記号で， x

,..., x

∈ V ar のとき， ‘R(x

, ..., x

)’ は

L -論理式である;

(1.5) φ, ψ が L - 論理式なら， “(φ ∧ ψ)”, “(φ ∨ ψ)”, “( ¬ φ)” “(φ → ψ)”, “(φ ↔ ψ)”

も L -論理式である

;

(1.6) φ が L -論理式で x ∈ V ar のとき，‘ ∀ xφ’, ‘ ∃ xφ’ も L -論理式である;

(1.7) 以上のみ

．

(1.3) と (1.4) で導入される L - 論理式は， 原始論理式 (atomic formulas) あるいは， L - 原始論理式とよばれる．

1)

より厳密には，V ar は，これから考えることになる構造や， ‘ ∧ ’, ‘ ∨ ’ などの他の記号の全体の集 合と共通部分を持たないようにとっておく必要がある．

2)

“(φ ∧ ψ)” などとして “” で囲ってあらわしたのは，ここで考察している論理式が，たとえば (φ ∧ ψ) は，記号 ‘(’, 記号列 φ, 記号 ‘ ∧ ’, 記号列 ψ, 記号 ‘)’ を繋げて得られる記号列である（にすぎない）こ とを強調したかったからである．

3)

この最後の条件のより直観的な意味は，上の (1.3)–(1.6) の構成法をくりかえし適用することに

よって 得られる表現のみが L -論理式である，ということである．

上のような L - 論理式の帰納的定義に対応して， L - 論理式に関する概念を帰納的に 導入することができる．例えば， L -論理式 φ にあらわれるの自由変数 (free variables)

の集合 F ree(φ) は次のようにして帰納的に定義することができる :

(1.8) φ が x = y の形のときには， F ree(φ) = { x, y } とする ;

(1.9) φ が R(x

, ..., x

) のときには， F ree(φ) = { x

, ..., x

} ;

(1.10) φ が ‘(ψ ∧ η)’, ‘(ψ ∨ η)’, ‘( ¬ ψ)’ ‘(ψ → η)’, または， ‘(ψ ↔ η)’ の形をしている

ときには， F ree(φ) は，それぞれ， F ree(ψ) ∪ F ree(η), F ree(ψ) ∪ F ree(η), F ree(ψ), F ree(ψ) ∪ F ree(η), または，F ree(ψ) ∪ F ree(η) となる;

(1.11) φ が ‘ ∀ xψ’ または ‘ ∃ xφ’ の形をしているときには，F ree(ψ) \ { x } とする．

F ree(φ) = { x

, ..., x

} のとき， x

,..., x

は φ の自由変数 (free variables) である という．

F ree(φ) = ∅ のとき，つまり φ が自由変数を持たないとき， φ は閉論理式 (closed

formula) あるいは文 (sentence) であるという．閉論理式（あるいは文）が L - 論理式

であるときには， L - 閉論理式（あるいは L - 文）という言い方もすることにする．ま た （矛盾しない

） L -文の集合 T を L -理論 ( L -theory) という．

F ree(φ) ⊆ { x

, ..., x

} のとき，このことを φ = φ(x

, , ..., x

) とらわす．

A = h A, ... i を L - 構造として， φ は L - 論理式で， φ = φ(x

, , ..., x

) のとき，

“x

,..., x

を a

,..., a

∈ A と解釈したときに φ は A で成り立つ” ということを，

A | = φ[a

/x

, ..., a

/x

] あるいはもっと簡単に A | = φ[a

, ..., a

] と書いて以下により 帰納的に定義する :

(1.12) φ が ‘x

= x

’ のときには， A | = φ[a

, ..., a

] ⇔ a

= a

;

(1.13) φ が R(x

, ..., x

) のときには， A | = φ[a

, ..., a

] ⇔ (a

, ..., a

) ∈ R; ただ

し R は R に対応する A の m-項関係;

(1.14) φ が ‘(ψ ∧ η)’, ‘(ψ ∨ η)’, ‘( ¬ ψ)’ ‘(ψ → η)’, または，‘(ψ ↔ η)’ の形をしてい

るときには，それぞれ，

A | = φ[a

, ..., a

] ⇔ A | = ψ[a

, ..., a

] かつ A | = η[a

, ..., a

]

(φ が (ψ ∧ η) のとき ) A | = φ[a

, ..., a

] ⇔ A | = ψ[a

, ..., a

] または A | = η[a

, ..., a

]

(φ が (ψ ∨ η) のとき ) A | = φ[a

, ..., a

] ⇔ A | = ψ[a

, ..., a

] でないとき

(φ が ( ¬ ψ) のとき)

4)

矛盾しない，というのは，ここでは，以下で述べる論理式の解釈の意味で T のすべての要素モデ

ルとなっているような L -構造が存在する，ということである．

A | = φ[a

, ..., a

] ⇔ A | = ψ[a

, ..., a

] でないか，または A | = η[a

, ..., a

]

(φ が (ψ → η) のとき ) A | = φ[a

, ..., a

] ⇔ A | = ψ[a

, ..., a

] と A | = η[a

, ..., a

] が両方とも

成り立つか，あるいは両方とも成り立たないとき

(φ が (ψ ↔ η) のとき) (1.15) φ = φ(x

, ..., x

) が ‘ ∀ xψ(x, x

, ..., x

)’ または ‘ ∃ xφ(x, x

, ..., x

)’ の形をし

ているときには，まず必要なら x の呼びかえをして， x は x

,..., x

に含まれ ていないとしてよいが，このとき :

A | = φ[a

, ..., a

] ⇔ すべての a ∈ A に対し A | = ψ[a/x, a

/x

, ..., a

/x

] (φ が ∀ xψ のとき ) A | = φ[a

, ..., a

] ⇔ ある a ∈ A に対し A | = ψ[a/x, a

/x

, ..., a

/x

]

(φ が ∃ xψ のとき ).

演習問題 1.1. 上の ‘ | =’ の定義は well-defined なものになっている．特に， φ =

φ(x

, ..., x

) で， F ree(φ) = { x

, ..., x

} のとき，

A | = φ[a

/x

, ..., a

/x

] ⇔ A | = φ[a

/x

, ..., a

/x

] がべての a

,..., a

∈ A に対し成り立つ．

A を L - 構造として， T を L - 理論とするとき， A | = T とは， T に属すすべての閉論 理式 φ について A | = φ が成り立つこととする． A | = T が成り立つとき，構造 A は T のモデルである，とも言う．

2 部分構造，初等的部分構造

substr-ele-

substr

A = h A, R

, R

, ... i , B = h B, R

, R

, ... i を L - 構造とする． B が A の部分構造 (sub- structure) である（これを B ⊆ A と書く）とは， B ⊆ A かつ， R

= R

∩ B

がす べての i に対し成り立つこととする．

B が A の初等部分構造 (elementary substructure) または 初等部分モデル (ele- mentary submodel ) であるとは， B ⊆ A で，すべての L - 論理式 φ(x

, ..., x

) と b

,...

, b

∈ B に対し， B | = φ[b

, ..., b

] ⇔ A | = φ[b

, ..., b

] が成り立つことである． B が

A の初等部分構造のとき，これを B ≺ A とあらわす．

例 2.1. hQ , ≤i と hN , ≤i を考える．明らかに hN , ≤i ⊆ hQ , ≤i である．

hN , ≤i | = ∃ x ∀ y(x ≤ y) だが，一方， hQ , ≤i 6| = ∃ x ∀ y(x ≤ y) だから， hN , ≤i は ( Q , ≤ ) の初等的部分構造ではない．一方， hQ , ≤i ≺ hR , ≤i である（演習） ．

例 2.2. hN , ≤i と hN \ { 0 } , ≤i を考える．明らかに hN \ { 0 } , ≤i ⊆ hN , ≤i である．

hN \ { 0 } , ≤i | = ∀ y(x ≤ y)[1/x] だが， hN , ≤i では 1 は最小元ではないから，

hN , ≤i 6| = ∀ y(x ≤ y)[1/x] となり， hN \ { 0 } , ≤i は hN , ≤i の初等的部分構造ではない ことがわかる．

A = h A, R

, R

, ... i で， X ⊆ A のとき， A ↾ X で構造 h X, R

∩ X

, R

∩ X

, ... i をあらわす． A ↾ X ⊆ A であるが，上の例でもわかるように， A ↾ X ≺ A となると は限らない．

A ↾ X ≺ A となるような X の構成法については，命題 3.1 を参照．

A と B を L - 構造とするとき，すべての L - 文 φ に対し， A | = φ ⇔ B | = φ が 成り立つとき， A と B は初等同値 (elementary equivalent ) であるといい，これを A ≡ B であらわす．

演習問題 2.3. A ⊆ B で A ≡ B だが， A ≺ B ではないような例をあげよ．

演習問題 2.4. ≺ は推移的である．つまり， A ≺ B かつ， B ≺ C なら A ≺ C が成 り立つ．

演習問題 2.5. A ≺ C で A ⊆ B ≺ C なら，A ≺ B である．

定理 2.6.

chain

γ を極限順序数として， h A

: α < γ i を次の (2.1), (2.2) を満たす L -構造 A

= h A

, R

, R

, ... i , α < γ の列とする：

(2.1) α < β < γ なら A

≺ A

.

(2.2) δ < γ が極限順序数なら， A

= S

α<δ

A

となっている

． このとき A

= S

α<γ

A

, R

= S

α<γ

R

,... として， A

= h A

, R

, R

, ... i とすれば，

A

は L - 構造となる．さらに，次が成り立つ : (a) すべての α < γ に対し， A

≺ A

となる．

5)

構造の列 h A

: α < γ i が，(2.1),(2.2) を満たすとき， h A

: α < γ i は連続な初等的連鎖

(continuous elementary chain) であるという．

同様に h A

: α < γ i が

(2.1)’ α < β < γ なら A

⊆ A

と (2.2) を満たすとき， h A

: α < γ i は（ ⊆ に関する）連続な上昇列 (continuously increasing

sequence) である，という．

(b) B を A

≺ B がすべての α < γ に対して成り立つような L - 構造とするとき，

A

≺ B となる．

証明． A

⊆ A

となることは明らか． (a) の証明には，次の (2.3) を L - 論理式 φ の 構成に関する帰納法により示すことができればよい :

(2.3) すべての α < γ と， a

, ..., a

∈ A

に対し，

A

| = φ[a

, ..., a

] ⇔ A

| = φ[a

, ..., a

] が成り立つ．

φ が x = y または R(x

, ..., x

) の形をしているときには，(2.3) が成り立つこと は明らか．また φ が (ψ ∧ η), (ψ ∨ η), ( ¬ ψ), (ψ ← η) または (ψ ↔ η) の形をしてい

て， (2.3) が ψ と η に対して成立するときには，このことから (2.3) が φ に対しても

成立することも容易に示せる（演習）．

φ が ∃ xψ で ψ については (2.3) がすでに証明されているとして， (2.3) が φ につ いても成り立つことを示す :

“ ⇒ ”: A

| = φ[a

, ..., a

] とすると， a ∈ A

で A

| = ψ[a/x, a

/x

, ..., a

/x

] とな るものが存在する．このとき帰納法の仮定から， A

| = ψ[a/x, a

/x

, ..., a

/x

] とな るから， A

| = φ[a

, ..., a

] がわかる．

“ ⇐ ”: A

| = φ[a

, ..., a

] とすると， a ∈ A

で A

| = ψ[a/x, a

/x

, ..., a

/x

] と なるものが存在する． γ は極限順序数だったから， A

の定義から，ある β < γ で a ∈ A

となるものがとれる． α < β となっているとしてよいが，このとき仮定から A

| = ψ[a/x, a

/x

, ..., a

/x

] となる．したがって， A

| = φ[a

, ..., a

] であるから，

(2.1) により， A

| = φ[a

, ..., a

] となる．

φ が ∀ xψ の場合も同様に証明できる（演習） ．

(b) は (a) と同様に証明できる（演習） ． ( 定理 2.6)

系 2.7.

chain2

h A

: α < γ i を A の部分構造の連続な上昇列で，

(2.4) A

≺ A がすべての α + 1 < γ となる α に対して成り立つ

とする．このとき， h A

: α < γ i は連続な初等的連鎖となり， A

を定理 2.6 でのよ うに定義すると， A

≺ A が成り立つ．

証明．定理 2.6 を用いて γ に関する帰納法で，

(2.5) h A

: α < γ i が (2.4) を満たす A の部分構造の連続な上昇列なら， h A

:

α < γ i は， A の初等部分モデルの連続な初等的連鎖となる．

を証明すればいい．

3 Downward L¨ owenheim-Skolem ^定理

downw-losko

A = h A, R

, R

, ... i をふたたび L - 構造とする． f が A 上の関数であるとは，ある n ∈ ω に対し， f : A

→ A となっていることとする． A 上の関数の族 F に対し，

X ⊆ A が F に関して閉じている (X ⊆ A is closed with respect to F ) とは，任意の f ∈ F に対し， f を n 変数として， f

X

⊆ X が成り立つこととする．

命題 3.1. L -構造 A に対し，A 上の関数族 F で以下の (3.1), (3.2) を満たすものが

存在する :

(3.1) F は可算 ;

(3.2) 任意の X ⊆ A に対し， X が F に関して閉じているなら A ↾ X ≺ A となる．

証明． v を A 上の整列順序として a

を A の v に関する最小元とする．各 L - 論理 式 φ(x

, x

, ..., x

) に対し， f

: A

→ A を

(3.3) f

(a

, ..., a

) =

( A | = φ[a, a

, ..., a

] となるような a ∈ A で v に関し最初なもの ; a

, 上のようなものが存在しないとき

として定義する．ここで F = { f

: φ は L-論理式 } とすると，この F が求めるよ うなものであることを示す． L は可算だったから， F が可算となることはよい． F が (3.2) も満たすことを示す :

X ⊆ A が F で閉じているとして，B = A ↾ X とする．B ≺ A が示すべきこと だが，このために，

(3.4) b

,..., b

∈ X なら， A | = φ[b

, ..., b

] ⇔ B | = φ[b

, ..., b

]

がすべての φ に対し成り立つことを φ の構成に関する帰納法で示す．

φ が x = y または R(x

, ..., x

) の形をしているときには， (3.4) が成り立つこと は明らか．また φ が (ψ ∧ η), (ψ ∨ η), ( ¬ ψ), (ψ ← η) または (ψ ↔ η) の形をしてい

て， (3.4) が ψ と η に対して成立するときには，このことから (3.4) が φ に対しても

成立することも，容易に示せる（演習）．

φ = φ(x

, ..., x

) がある L - 論理式 ψ = ψ(x, x

, ..., x

) に対して， ∃ xψ と書ける とき， ψ については (3.4) が成り立つことがすでに判っているとして，φ について も， (3.4) が成り立つことを示す :

(3.4) の “ ⇒ ”: A | = φ[b

, ..., b

] とする．つまり， A | = ∃ xψ[b

, ..., b

] とする．こ のときには，b

, ..., b

に対して，f

の定義 (3.3) で，一番目の場合が成立している．

したがって， A | = ψ[f

(b

, ..., b

)/x, b

/x

, ..., b

/x

] となるが， X に対する仮定から

f

(b

, ..., b

) ∈ X となるから， 帰納法の仮定により， B | = ψ[f

(b

, ..., b

)/x, b

/x

, ..., b

/x

]

となる．したがって，B | = φ[b

, ..., b

] である．

(3.4) の “ ⇐ ” は容易に示せる（演習）．また φ が ∀ ψ の場合も同様に示せる（演 習）．

( 命題 3.1) 命題 3.1 の系として，次の Downward L¨ owenheim-Skolem の定理と呼ばれている定 理が得られる．定理を一般的な形で述べるために，まずいくつかの用語を導入する．

κ を非可算な正則基数として， X を集合とする．このとき，

[X]

= { x ⊆ X : | x | < κ } とする． [X]

, [X]

, も同様に定義する

．

C ⊆ [X]

が closed unbounded （略して club ）であるとは，次の (3.5), (3.6) が 成立することとする:

(3.5) γ < κ で x

∈ C , α < γ が ⊆ に関する上昇列であるとき

, S

α<γ

x

∈ C が 成り立つ (closed);

(3.6) 任意の x ∈ [X]

に対し， y ∈ C で x ⊆ y となるものが存在する (unbounded) ．

[X]

や [X]

の club な部分集合についても同様に定義する．

補題 3.2. (a) C が [X]

の club な部分集合であるとき， C は [X]

の club な部分 集合でもある．

(b) C が [X]

の club な部分集合のとき， C ∩ [X]

は [C]

の club な部分集合で ある．

証明．演習． ( 補題 3.2)

定理 3.3.

losko

( 下方 L¨ owenheim-Skolem 定理 ) A = h A, ... i を（非可算な） L - 構造と して，κ ≦ | A | を非可算な正則基数とする．このとき

C = { x ∈ [A]

: A ↾ x ≺ A }

は [A]

の closed unbounded な部分集合となる．

証明． C が (3.5) を満たすことは，定理 2.6 によりよい

． C が (3.6) も満たすこと を示すために， F を命題 3.1 でのようにとる． x ∈ [A]

に対し， y ∈ [A]

で x ⊆ y

6)

[X]

= [X ]

, [X]

= [X ]

\ [X]

である．

7)

つまり任意の α < β < γ に対し，x

⊆ x

が成立するとき．

8)

演習問題 2.5 に注意する．

かつ y は F に関して閉じているようなものがとれるが

，このとき， A ↾ y ≺ A だ

から y ∈ C である． (定理 3.3)

A = h A, ... i を L - 構造として， F を命題 3.1 でのようにとる．このとき， x ⊆ A に 対し ˜ h

(x) で x を含む A の部分集合のうち F に関し閉じているもののうち ⊆ に 関し最小のものをあらわすことにする． ˜ h

(x) は x の F に関するスコーレム閉包 (Skolem closure of X with respect to F ) とよばれる． A ↾ ˜ h

(x) ≺ A となるが，簡 単のために ˜ h

(x) で L - 構造 A ↾ ˜ h

(x) もあらわすことにする．

定理 3.3 と類似の次の結果もよく使われることになる:

補題 3.4.

losko-a

A = h A, ... i を L - 構造として， κ > ℵ

を正則基数とし， κ ⊆ A となってい るとする．このとき，任意の a ∈ [A]

に対し，

C = { α < κ : B = h B, ... i ≺ A で a ⊆ B, B ∩ κ = α となるものが存在する }

は [κ]

の closed unbounded な部分集合を含む（特に C 6 = ∅ である）．

証明． F を命題 3.1 でのようにとる，このとき，

C ⊇ { α < κ : ˜ h

(α ∪ a) ∩ κ = α }

となるが，右辺が [κ]

で closed unbounded であることは容易に示せる（演習）．

( 補題 3.4) A = h A, ..., ◁i で， ◁ が A の well-ordering のとき，命題 3.1 の証明での v とし て ◁ をとると，命題 3.1 の F は A 上定義可能な関数からなるものとなる．このよ うなとき， F は built-in Skolem functions である，という．

定理 3.5. A = h A, ... i を built-in Skolem functions F を持つ構造とするとき，すべ ての X ⊆ A に対し，B ≺ A で，B = h B, ... i として， X ⊆ B となるようなものの うち ⊆ に対して最小のものが存在する．

証明． B ≺ A で， B = h B, ... i , X ⊆ B とすると， B の elementarity から， B は F に関して閉じているので， ˜ h

(X) ⊆ B が成り立つ

．したがって， ˜ h

(X) は X を 含む A の初等部分構造のうち，最小のものである． ( 定理 3.5)

9)

x

, n ∈ ω を帰納的に，x

= x; x

= x

∪ { f (a

, ..., a

) : a

, ..., a

∈ x

, f ∈ F} ととり，

y = S

n∈ω

x

とすると F は可算だから， | y | < κ となるが，y が F に関し閉じていることは容易に 示せる．

10)

演習問題 2.5 により， ˜ h

(X) ≺ B でもある．

4 H (χ)

calHchi

集合 x が推移的 (transitive) であるとは，任意の y ∈ x と z ∈ y に対し z ∈ x が成 り立つことである．集合 x の推移的閉包 (transitive closure) trcl(x) を，

(4.1) trcl(x) = T

{ u : u は推移的で x ∈ u } として定義する

．

補題 4.1. x ∈ y なら， trcl(x) ⊆ trcl(y) となる．

証明． x ⊆ trcl(y) となるが， trcl(y) は推移的だから， (4.1) から trcl(x) ⊆ trcl(y) が

帰結できる． ( 補題 4.1)

χ を無限基数とするとき，継承的に濃度が < χ (hereditarily of cardinality < χ) な集 合の全体 H (χ) を

H (χ) = { x : | trcl(x) | < χ }

により定義する．次の補題から， H (χ) は集合になることがわかる．

補題 4.2. χ を無限基数とするとき， H (χ) ⊆ V

となる．

証明． χ に関する帰納法で証明する． χ = ℵ

のときには， x ∈ H (χ) として，ある n ∈ ω に対し， | trcl(x) | = n となるが， n に関する帰納法で x ∈ V

が証明できる

（演習）

．

χ > ℵ

として， χ が極限基数で， χ より小さい無限基数に対しては補題が成り

立っているとする．このときには，

H (χ) = [

κ<χ, κは基数

H (κ) ⊆ [

κ<χ, κは基数

V

= V

となるから，χ に対しても補題が成り立つことがわかる．

11)

trcl(x) の定義の右辺にあらわれるクラスが空集合でないことを見るためには，trcl(x) が以下の

ようにして構成できることを示せばよい: n ∈ ω に対し， tc

(x) を帰納的に tc

(x) = { x } , tc

(x) = tc

(x) ∪ { z : ある y ∈ tc

(x) に対し z ∈ y } としてとると，trcl(x) = S

n∈ω

tc

(x) となる（演習）．

ここでの trcl(x) ではなく，trcl(x) \ { x } を x の transitive closure とする流儀もあるが，ここでは，

後で， trcl(x) から x が一意に復元できることを保証する必要があるため，ここでのような定義を採用

している．[4] では，trcl(x) \ { x } は trcl

(s) と呼ばれている．trcl

(x) が x を reconstruct できな いことは，例えば ω の任意の無限部分集合 S に対し，trcl

(S) = ω となることから明らかである．

これに対し， x は trcl(x) の ∈ -rank が最大の唯一の要素，として指定することができる．

12)

逆に，V

= S

n∈ω

V

のすべての元が H ( ℵ

) に属すことも n に関する帰納法で示せるから，

V

= H ( ℵ

) である．

χ = κ

のときには， H (χ) 6⊆ V

だったとして， x ∈ H (χ) \ V

をこのような もののうち ∈ -rank が最初のものとする．このとき，y ∈ x なら，補題 4.1 により，

trcl(y) ⊆ trcl(x) だから， y ∈ H (χ) となり，最小性から y ∈ V

となる．したがっ て， x ⊆ V

となるが， | x | ≤ | trcl(x) | < χ により， χ は正規基数だから， α < χ で x ⊆ V

となるものがある．したがって，x ∈ V

⊆ V

となるが，これは x のとり

かたに矛盾する． ( 補題 4.2)

補題 4.3. すべての無限基数 χ に対し， H (χ) は推移的な集合である．

証明． H (χ) が集合になることは，補題 4.2 によりよい．

x ∈ H (χ) で y ∈ x とする．このとき，補題 4.1 により， trcl(y) ⊆ trcl(x) となり，

| trcl(x) | ≤ | trcl(y) | < κ により， x ∈ H (χ) である． ( 補題 4.3) H (χ) が集合になることは，次に示す H (χ) の濃度の評価からもわかる:

補題 4.4. 任意の無限基数 χ に対し， | H (χ) | = 2

である．

証明．x ∈ H (χ) とすると， | trcl(x) | < χ だが， λ = | trcl(x) | として， f : λ → trcl(x) を bijection とし， g : λ

→ 2 を g(α, β) = 1 ⇔ f (α) ∈ f (β) で定義すると， x は g によって一意に決まる．このような g は高々 2

個しかないから， | H (χ) | ≤ 2

である．

一方，基数 λ < χ と f : λ → 2 に対し，

x

= { α ∈ λ : f (α) = 1 } ∪ {{ α + 1 } : α ∈ λ, f (α) = 0 }

とすると， f 7→ x

は一対一対応となることから， | H (χ) | ≥ 2

がわかる． ( 補 題 4.4)

次の補題は，第 6 節で述べることになるような応用でよく用いられる．

補題 4.5. (a) χ を無限基数とする． h M, ∈i ≺ hH (χ), ∈i で

r ⊆ M が有限集合な

ら，r ∈ M となる．

(b) κ < χ を基数として， h M, ∈i ≺ hH (χ), ∈i で， κ ∈ M , κ ⊆ M とする．このと き， r ∈ M , で | r | ≤ κ なら r ⊆ M である．

(c) χ を無限基数とする． h M, ∈i ≺ hH (χ), ∈i で r ∈ M が有限集合なら， r ⊆ M となる．

(d) χ を非可算な基数とする． h M, ∈i ≺ hH (χ), ∈i で，r ∈ M が可算なら，r ⊆ M となる．

13)

“ hH (χ), ∈i ” という書きかたについては，2 ページを参照．

証明． (a): r = { r

, ..., r

} となっているとする．このとき，

hH (χ), ∈i | = ∃ x(“x = { x

, ..., x

} ”)[r

/x

, ..., r

/x

] となるから， h M, ∈i ≺ hH (χ), ∈i と， r

,..., r

∈ M により，

h M, ∈i | = ∃ x(“x = { x

, ..., x

} ”)[r

/x

, ..., r

/x

] が成り立つ．したがって， s ∈ M で，

h M, ∈i | = “x = { x

, ..., x

} ”[s/x, r

/x

, ..., r

/x

] となるものが存在するが，明らかに

s = r である．

(b): 仮定から，

hH (χ), ∈i | = ∃ x(“x : y → z で x は上射 ”)[κ/y, r/z]

である．したがって， h M, ∈i ≺ hH (χ), ∈i により，

h M, ∈i | = ∃ x(“x : y → z で x は上射 ”)[κ/y, r/z]

である．よって， f ∈ M で

h M, ∈i | = “x : y → z で x は上射 ”[f /x, κ/y, r/z]

となるものがとれるが，すべての α ∈ κ に対し， α ∈ M となることから， f(α) ∈ M がわかる．したがって， r = { f (α) : α ∈ κ } ⊆ M である．

(c): ω ⊆ H (χ) で有限基数は定義可能だから， ω ⊆ M である．したがって， κ = | r | (< ω) に対して (b) を適用すると，r ⊆ M がわかる．

(d): χ が非可算により，ω ∈ H (χ) である．ω は定義可能だから， ω ∈ M で，(c) の証明で注意したように ω ⊆ M である．したがって κ = | r | ( ≦ ω) に対して (b) を 適用すると， r ⊆ M がわかる． ( 補題 4.5)

14)

この主張の検証を含めて，この補題の証明の細部の検証は次の節で証明する補題 5.1 を用いて一

様なやり方で行うことができる．

5 ^絶対性と H (χ) で成り立つ集合論の公理

absol

H (χ) は一般には ZFC のモデルではない．さらに，不完全性定理により， “ H (χ) が ZFC のモデルになるような正則基数 χ が存在する ” は ZFC から証明できない．し かし，ZFC で，非可算な正則基数 χ に対し， H (χ) は “ほとんど” ZFC のモデルに なっていることが言え（定理 5.3 を参照），さらに， “ H (χ) ≺ V ” の代用のようなも のとして用いることのできる反映原理（定理 5.5 を参照）も成り立つ．

以下では，言語 L を， L = {∈ , ... } として固定する．関係記号 ∈ が集合の要素関 係 ∈ に解釈されるような構造 A = h A, ∈ , ... i を ∈ - モデル と呼ぶことにする． ∈ - モ デル A = h A, ∈ , ... i で “ ∈ , ...” が文脈から明らかなときには， A で A をあらわすこ とにする．

φ が L - 論理式で x, y ∈ V ar のとき， ( ∃ x ∈ y)φ, ( ∀ x ∈ y)φ で，それぞれ論理式

∃ x(x ∈ y ∧ φ) および， ∀ x(x ∈ y → φ) をあらわすことにする．

L -論理式 φ が 束縛論理式 (bounded formula) であるとは， ( ∃ x ∈ y) および ( ∀ x ∈ y)φ の形のものを独立した量化子であるかのように扱って以下の帰納的定義で導入さ れる論理式の集合に φ が属すこととする :

(5.1) x, y ∈ V ar のとき， ‘x = y’ は L - 束縛論理式である ;

(5.2) R が L の m 項関係記号で，x

,..., x

∈ V ar のとき，‘R(x

, ..., x

)’ は

L - 束縛論理式である ;

(5.3) φ, ψ が L - 束縛論理式なら， “(φ ∧ ψ )”, “(φ ∨ ψ)”, “( ¬ φ)” “(φ → ψ)”, “(φ ↔

ψ)” も L - 束縛論理式である ;

(5.4) φ が L - 束縛論理式で x, y ∈ V ar のとき， “( ∀ x ∈ y)φ”, “( ∃ x ∈ y)φ” も L - 束

縛論理式である ;

(5.5) 以上のみ．

束縛論理式（にパラメタを代入したもの）の真偽の判定は，この論理式に表われるパ ラメタやそれらの要素，またそれらの要素の要素，などを調べることで実行できる．

この直観を（ (5.1) 〜 (5.4) の意味での）束縛論理式の構成に関する帰納法に乗せる ことにより，次の 補題 5.1 が証明できる．

まず，補題 5.1 で用いられる用語の定義から始める．

A = h A, ∈ , . . . i を L での ∈ - モデルとして φ = φ(x

, ..., x

) を L - 論理式とすると き， φ が A 上 絶対 (absolute) である，とは，すべての集合 a

,..., a

に対し，

(5.6) A | = φ[a

, ..., a

] ⇔ φ(a

, ..., a

)

が成り立つこととする．

補題 5.1. 任意の（ ∈ 記号を含む）言語 L に対し，すべての L -束縛論理式は，推移

的な L での ∈ - モデル M 上で絶対である．特に任意の基数 χ に対し， H (χ) 上，任 意の束縛論理式は絶対である．

証明．（(5.1)〜(5.5) の意味での） L 上の束縛論理式の構成に関する帰納法により，

φ = φ(x

, ..., x

) に対して

(5.7) M | = φ[a

, ..., a

] ⇔ φ(a

, ..., a

)

が，すべての a

,..., a

∈ M に対し成り立つことを示す．

φ が L での原始論理式のときには， (5.7) が成り立つことは， ‘ | =’ の定義から明 らかである．

また， L での束縛論理式 φ と ψ に対して (5.7) が成り立っているときには，

“(φ ∧ ψ )”, “(φ ∨ ψ)”, “( ¬ φ)” “(φ → ψ)”, “(φ ↔ ψ)” に対しても (5.7) が成り立つこ とも，‘ | =’ の定義から明らかである．

したがって， (5.4) での構成で，帰納法のステップが機能することを確かめれば十 分である．

φ = φ(x

, ..., x

) が ( ∀ x ∈ x

)ψ(x, x

, ..., x

) （ただし 1 ≦ i ≦ n ）の形をしてい て ψ に対しては (5.7) が成り立っているとする．このとき， a

,..., a

∈ M として，

M | = φ[a

, ..., a

]

⇔ すべての a ∈ a

∩ M に対して M | = ψ[a, a

, ..., a

]

⇔ すべての a ∈ a

に対して M | = ψ[a, a

, ..., a

] (M は推移的だから )

⇔ すべての a ∈ a

に対して ψ(a, a

, ..., a

) ( 帰納法の仮定 )

⇔ φ(a

, ..., a

)

φ が ( ∃ x ∈ x

)ψ(x, x

, ..., x

) の形をしているときの証明も同様にできる．

( 補題 5.1) T を L - 理論とするとき， L - 論理式 φ = φ(x

, ..., x

) が Π

である，とは，ある L -束縛論理式 η(y

, ..., y

, x

, ..., x

) がとれて，

T ` ∀ x

· · · ∀ x

(φ ↔ ∀ y

· · · ∀ y

η) となることとする

．

L - 論理式 φ = φ(x

, ..., x

) が ∆

である，とは， L - 束縛論理式 ψ = ψ(y

, ..., y

, x

, ..., x

), η = η(y

, ..., y

, x

, ..., x

) で，

15)

実際の議論では，M は対の公理を満たすことが多いが，その場合には，変数のブロック y

,..., y

は一つの変数で代用できる．

T ` ∀ x

· · · ∀ x

(φ ↔ ∃ y

· · · ∃ y

ψ) T ` ∀ x

· · · ∀ x

(φ ↔ ∀ y

· · · ∀ y

η) となるものがとれることとする

．

補題 5.2. ，ZFC

を，ZFC から出発して，いくつかの新しい関数記号や定数記号を

導入することにより得られる ZFC の conservative extension とし， L をその言語と する．

M を，推移的な L での ∈ -モデルとして，T を ZFC

からの帰結からなる L -理 論で， M | = T となるものとする．このとき，

(1) φ が，ZFC

の帰結となっている Π

-文なら，M | = φ である．

(2) すべての ∆

な L - 論理式 φ は M 上絶対的になる．

証明．（演習） ． (補題 5.2)

補題 5.2 (2) の非常に有用な応用として，次のものがある : T は ZFC の十分に大 きなフラグメントを含んでいるものとする．このとき， T で，集合 x に対する，ある 述語 Ψ(x) が，束縛論理式であらわせる性質を用いた帰納法の初めと帰納法のステッ プによって ∈ に関する超限帰納法で導入されているとする．このときには，

T ` Ψ(x) ↔ ∃ u(u は Ψ(x) かどうかを帰納的に確かめるときのプロトコルに なっていて，これにより Ψ(x) が確かめられる )

T ` Ψ(x) ↔ ∀ u(u が Ψ(x) かどうかを帰納的に確かめるときのプロトコルに なっているなら，これにより Ψ(x) が確かめられる )

とできるから， Ψ(x) は ∆

となることがわかり， T のモデルとなっているような，

推移的な ∈ - モデル上で， Ψ(x) は，絶対になることがわかる．

ZFC

で ZFC の公理系から冪集合公理を除いたものを，表わすことにする．

定理 5.3. χ を非可算な正則基数とするとき， H (χ) | = ZFC

が成り立つ．

証明．以下の証明では，補題 5.1 と， （それまでに H (χ) で成り立つことが証明され ている ZFC

の部分体系を T としたときの）補題 5.2 を断わりなく何度も使ってい ることに注意する．

補題 4.3 により， H (χ) は推移的であることに注意する．外延性の公理は， Π

- 論 理式だから

，補題 5.2, (1) により， H (χ) で成り立つ．

[ 残りは後で書く ] ( 定理 5.3)

16)

ここでも一つまえの脚注と同様に，量化子のブロック y

· · · ∃ y

または，y

· · · ∃ y

は，多くの場 合，一つの量化子で置き換えることができる．

17)

ここでは， ∅ で空の理論を表している．

補題 5.4. χ を正則な非可算基数とする．

(1) a ∈ H (χ) とするとき， H (χ) | = “ P (a) が存在する ” なら， P

(a) = P (a) である．特に， H (χ) | = “ P (a) が存在する” ⇔ 2

< χ である．

(2) γ ∈ On として， | V

| < χ なら， H (χ) | = “ V

は存在する” が成り立ち，

(V

)

= V

である．

証明． (1): b ⊆ a なら， trcl(b) \ { b } ⊆ trcla だから， b ∈ H (χ) がわかる．したがっ て， H (χ) | = c = P (a) なら， P (a) ⊆ c ⊆ P (a) である．特に，

H (χ) | = “ P (a) が存在する ” ⇔ P (a) ∈ H (χ) ⇔ 2

< κ である．

(2): V

は推移的だから， | V

| < χ なら， V

∈ H (χ) で， h V

: ξ ≤ γ i ∈ H (χ) で ある，c = h V

: ξ ≤ γ i とすると，(1) により， H (χ) | = “ c = h V

: ξ ≤ γ i ” となり，

H | = “ V

が存在する ” が言える．得に， (V

)

= V

である． ( 補題 5.4) 定理 5.5. すべての論理式

φ = φ(x

, ..., x

) と，基数 κ に対し，正則基数 χ > κ

と順序数 γ, 2

≤ γ < κ で，

(5.8) すべての a

, ..., a

∈ H (κ) に対し，

H (χ) | = “ V

| = φ[a

, ..., a

]” ⇔ φ(a

, ..., a

) となるようなものが存在する

．

証明． L´ evy-Montague Absoluteness Theorem と，補題 5.4l,(2) によりよい．

(定理 5.5) [この節はまだ書きかけです．]

6 初等部分構造の集合論での応用

application

以上の準備を使うと，与えられた無限組合せ論的な命題 φ の可能な証明方針の一つ として，次のようなものが考えられるようになる : まず正則基数 χ を十分に大きく とり， φ( · · · ) でパラメタとしてあらわれる objects がすべて H (χ) に含まれ，

hH (χ), ∈i | = φ ⇔ φ が（本当に）成り立つ

18)

ここでの “すべての論理式 φ” での “すべて” は meta-logic での “すべて” である．つまり，定理

5.5 は，一つ一つの具体的な論理式 φ に対する主張をたばねた meta-theorem となっている．

19)

ここでは，“すべての a

, ..., a

∈ H (χ) に対し”，とは 言 ˙ っ ˙ て ˙ い ˙ な ˙ いことに注意． ˙