数学の基礎
５．集合
任意の理論 t において、R を命題、x を変数とするとき、理論 t におけるどの記号とも異なる新しい文字 {|}
を導入して文字列 {|}
R を作り、冒頭の文字 {|}
と R の中に出てくる x をすべて鎖で結び、x のところを文字 £ で一斉に置き換えて得られる文字列を { x | R }
と表すことにします。
これはもちろん命題でも項でもありませんが、もし {|}
が項型量化記号であったとすれば項になります。そこで、このような文字列を便宜的に冪項とよぶことにしましょう。
また、A を冪項とするとき、A の冒頭の文字 {|}
とそれに繋がれていた鎖を除去し、これらの鎖で繋がれていた £ を t 項 T で置き換えて得られる文字列のことを TÎA と表すことにすれば、明らかに次の性質が成り立ちます：
(5-1a) | R が命題、x が変数ならば、{ x | R } は冪項である。 |
(5-1b) | R が命題、x が変数、T が t 項ならば、TÎ{ x | R } と (T | x) R は同一の命題である。 |
ここで定義した冪項は、もちろん正式な項ではありませんし、{|}
も正式には記号ではないですし、Î に至っては記号どころか超数学的な省略記法に過ぎません。しかし、もしも冪項が項であったとすれば、それを変数に代入したり、量化記号の推論規則を用いて「任意の冪項に対して」といった概念が表現できて大変便利です。実際、「任意の冪項 { x | R }
に対して」という表現は「任意の命題 R に対して」という表現と殆ど同じことですから、これは項を一般的に表す通常の「変数」に対して、命題を一般的に表す「命題変数」という概念を導入し、しかもそれらに量化記号を用いることを許す理論体系（いわゆる「２階の述語論理」）で考えることに匹敵します。
そこで、もとの理論における t 項とは別に、冪項を新しい種類の項に“昇格”させるため、理論 t に、新規に引数が命題の項型量化記号 {|}
と、２変項述語記号 Î と、１変項述語記号 tP を追加して、A が冪項であるという概念を tP(A)
と形式化し、更に (5-1)
も推論規則の形に形式化することにします。すなわち
( tP 導入) |
tP( { x | R } ) |
( Î 導入) |
t(T )
(T | x)R
—————
TÎ{ x | R } |
( Î 消去) |
t(T )
TÎ{ x | R }
—————
(T | x) R |
を推論規則として追加します。( tP 導入) が (5-1a)
を、( Î 導入) と ( Î 消去) が (5-1b)
を形式化したものです。
なお、t(T )
Ù tP(A)
Ù TÎA のことを改めて TÎA と書くことにすると、( tP 導入) と ( Î 導入) はそのままで、( Î 消去) のかわりに推論規則：
( Î 消去)' |
TÎ{ x | R }
—————
(T | x) R |
TÎA
———
t(T ) |
TÎA
———
tP(A) |
が成り立つことになります。こちらの方が便利なので、以後 ( Î 消去)' の方を推論規則として採用することにします。
さて、上記の理論拡大において、tP(A)
というのは、項 A が「冪項」という“実体を持った項”であることを意味しています。つまり１変項述語記号 tP は、もとの理論における存在述語記号 t とは別の、新たな存在述語記号とみなすことができます。
そこで、今後はこのように新たな存在述語記号 s の追加とともに拡大された理論のことも理論 s とよび、s(T )
を満たす項 T のことも s 項とよぶことにしましょう。
以上の約束のもとで、上述の理論 tP のことを理論 t の冪理論とよび、tP 項のことを（ t 上の）集合といい、{ x | R }
を R を満たす x の全体と読み、TÎA のことを T は A に属す、T は A の元である、あるいは A は T を元に持つと読み、TÎA の否定を TÏA とも書くことにします。
すなわち冪項を項として形式化した概念を集合とよぼうというわけですが、この“集合”という名前は、単に“モノの集まり”という日常的な概念を連想できてイメージしやすいから昔からそうよんでいるだけで、集合論の創始者Cantor
の時代のように、“集合”を本当に“モノ”の“集まり”だと思っているわけではありません。むしろ形式上の観点からは、“モノの集まり”というよりは特定の変数に注目した命題という概念を対象化したものという方がむしろ実体に即しています。
冪理論は素朴集合論を定式化したものと見なすことができますが、ここで歴史上有名なRussell
のパラドクスについて考えてみましょう。
Russell
のパラドクスとは、Ω :º { x | xÏx }
と置くと、ΩÎΩ Û ΩÏΩ となって矛盾する、というものです。
ところが上記の定式化では、ΩÎΩ を仮定すると、ΩÎ{ x | xÏx }
ですから ( Î 消去) により ΩÏΩ が得られ、これは矛盾なので、( Ø 導入) により ΩÏΩ が定理として得られますが、ここで t(Ω)
が証明できないので ΩÎ{ x | xÏx }
が導けず、従ってRussell
のパラドクスは生じません（さらに言えば、t(Ω)
と仮定すると矛盾するので Øt(Ω)
が定理になります）。
すなわち ( Î 導入) の上段に t(T )
があることが本質的で、本稿のような定式化によれば、Russell
のパラドクスというのは、本来の項である t 項と新規に導入された tP 項を区別しなかったことから生じたパラドクスであるということができます。
さて、メタ定理１〜４は冪理論についても成立します：
| メタ定理48 |
第１節で与えられた推論規則と、等号の推論規則と、ε 量化記号の推論規則と、冪理論の推論規則の全部又は一部を持つ理論では、推論規則 ( 同 一 ), ( 代 入 ) は導出可能である。もし更に ( 換 ) を推論規則に持つならば、( 増 ), ( 減 ), ( 切 断 ) も導出可能である。 |
実際、メタ定理１〜４の各証明において、用いた推論規則が上に挙げた冪理論の推論規則の場合のみを検証すれば十分です。
まずメタ定理１を検証します。( y | x)
S , ( y | x)
R をそれぞれ S' , R' と書きます。
まず、A が { z | R }
のとき、z が x と同じ変数なら ( y | x)
A は { y | R' }
です。
また z が x と異なり y と同じ変数なら、同様に ( y | x)
A は { x | R' }
です。
また z が x とも y とも異なる変数なら、同様に ( y | x)
A は { z | R' }
です。
一方、A が (S | z)
R のとき、z が x と同じ変数なら ( y | x)
A は (S' | y)
R' です。
また z が x と異なり y と同じ変数なら、同様に ( y | x)
A は (S' | x)
R' です。
また z が x とも y とも異なる変数なら、同様に ( y | x)
A は (S' | z)
R' です。
ゆえにこれらを組み合わせると、用いた推論規則が冪理論の推論規則の場合にも成り立つことがわかります。
次にメタ定理２を検証します。Γ ® (S | z)
R を Φ とし、Γ ® SÎ{ z | R }
を Ψ とします。
このとき、上記の結果を用いると、Φ ' , Ψ ' は、ある共通の変数 z' により、それぞれ Γ' ® (S' | z')
R' , Γ' ® S'Î{ z' | R' }
と書けます。
ここで Φ '*
は、メタ定理42の証明と同様に Γ'* ® (S'* | y)P"*
と書くことができます。
また Ψ '*
は Γ'* ® (T | x)[S'Î{ z' | R' }]
と書けますが、これは更に Γ'* ® S'*Î(T | x){ y | P" }
すなわち Γ'* ® S'*Î{ y | P"* }
と書くことができるので、冪理論の推論規則を適用した場合にもメタ定理２の証明がそのまま適用できることがわかります。
メタ定理３とメタ定理４については、何の変更点もなく、用いた推論規則が冪理論の推論規則の場合にもそのまま通用します。
以上でメタ定理48は証明されました。
さて、T1 ,¼,
Tn を t 項とするとき
(5-2a) Æ :º { x | ^ } |
(5-2b) [t] :º { x | Ø ^ } |
(5-2c) { T1 ,¼, Tn } :º { x | x º T1 Ú ¼ Ú x º Tn } |
と置いて、Æ を空集合、[t]
を理論 t の全体集合、{ T1 ,¼, Tn }
を元 T1 ,¼,
Tn からなる集合といいます。
また、集合 A，B に対し、"x (
xÎA Þ xÎB )
のことを A Ì B と書いて A は B の部分集合である、あるいは B は A を含むと読みます。このとき第３節メタ定理12，７，13により、任意の集合 A，B，C に対して
(5-3a) Æ Ì A Ì [t] |
(5-3b) A Ì A |
(5-3c) ( A Ì B Ù B Ì C ) Þ A Ì C |
が成り立ちます。ただし (5-3a)
は ( Æ Ì A ) Ù ( A Ì [t] )
の略で、２変項述語では一般的に用いる省略記法です。
一般に、(5-3b),(5-3c)
を満たす２項関係 Ì を擬順序関係といいます。そこで、２つの集合に対する関係 A = B を A Ì B Ù B Ì A で定義すれば、この２項関係 = は tP 上の同値関係になる、すなわち
(5-4a) A = A |
(5-4b) A = B Þ B = A |
(5-4c) ( A = B Ù B = C ) Þ A = C |
を満たすことがわかります。ただし、これは前節で導入した等号 º とは異なるので、集合の相等とよぶことにします。これは人工的に定義した２項関係ですから、( º 消去) に相当する推論規則は一般に成り立ちません。
また、集合 A，B に対し、$x (
xÎA Ù xÏB )
のことを A Ë B と書き、A Ë B Ú B Ë A のことを A ¹ B と書きます。記号 Ï の場合とは違い、Ë や ¹ は Ì や = の否定ではないことに注意します。
なお、記号 ¹ を用いると、集合 A が元を持つことを A ¹ Æ と表すことができます。
さて、集合 A と B に対し、
(5-5a) AÇB :º { x | xÎA Ù xÎB } |
(5-5b) AÈB :º { x | xÎA Ú xÎB } |
(5-5c) A \ B :º { x | xÎA Ù xÏB } |
(5-5d) CB :º { x | xÏB } |
と置いて、順に、A と B の共分、合併、差集合、補集合といいます。このとき、集合 A, B, C に対し、メタ定理22〜24、17、29、31、25により、次の関係が成り立ちます：
(5-6a) AÇB = BÇA |
(5-6b) AÈB = BÈA |
(5-6c) (AÇB)ÇC = AÇ(BÇC) |
(5-6d) (AÈB)ÈC = AÈ(BÈC) |
(5-6e) (AÇB)ÈC = (AÈC)Ç(BÈC) |
(5-6f) (AÈB)ÇC = (AÇC)È(BÇC) |
(5-6g) AÇC Ì B Þ C \ B Ì C \ A |
(5-6h) (C \ A) ÇA = Æ |
(5-6i) C \ (AÈB) = (C \ A)Ç(C \ B) |
(5-6j) CA Ç A = Æ |
(5-6k) C(AÈB) = CA Ç CB |
(5-6l) AÇÆ = Æ |
(5-6m) AÈÆ = A |
(5-6n) AÇ[t] = A |
(5-6o) AÈ[t] = [t] |
さて、項 A と、集合 I が与えられていて、iÎI Þ tP(A )
が成り立つものとします。以下、わかりやすさのために A のことを Ai と書くことにし、これを添字集合 I 上の集合族とよびます。このとき
(5-7a) ÇiÎI Ai :º { x | "i ( iÎI Þ xÎAi )} |
(5-7b) ÈiÎI Ai :º { x | $i ( iÎI Ù xÎAi )} |
と置いて、それぞれ集合族 Ai ( iÎI )
の共分、合併といいます。
特に I = Æ なら
(5-8a) ÇiÎÆ Ai = { x | "i ( iÎÆ Þ xÎAi )} = [t] |
(5-8b) ÈiÎÆ Ai = { x | $i ( iÎÆ Ù xÎAi )} = Æ |
が成り立ちます。また、別の集合 B に対し、
(5-9a) ( ÈiÎI Ai ) ÇB |
= { x | ( $i ( iÎI Ù xÎAi )) Ù xÎB } |
|
= { x | $i (( iÎI Ù xÎAi ) Ù xÎB )} ( ∵ メタ定理36 (c) ) |
|
= { x | $i ( iÎI Ù ( xÎAi Ù xÎB ))} ( ∵ メタ定理23 (a) ) |
|
= { x | $i ( iÎI Ù xÎAi ÇB )} |
|
= ÈiÎI (Ai ÇB ) |
(5-9b) ( ÇiÎI Ai ) ÈB |
= { x | ( "i ( iÎI Þ xÎAi )) Ú xÎB } |
|
Ì { x | "i (( iÎI Þ xÎAi ) Ú xÎB )} ( ∵ メタ定理36 (f) ) |
|
Ì { x | "i ( iÎI Þ ( xÎAi Ú xÎB ))} ( ∵ メタ定理30 (c) ) |
|
= { x | "i ( iÎI Þ xÎAiÈB )} |
|
= ÇiÎI (AiÈB ) |
が成り立ちます。ただし古典論理では、メタ定理39 (h),(k)
により Ì のところが = となるので
(5-9c)* ( ÇiÎI Ai )ÈB = ÇiÎI (AiÈB ) |
が成り立ちます。また集合 I が元を持てば、
(5-10a) ( ÈiÎI Ai ) ÈB |
= { x | ( $i ( iÎI Ù xÎAi )) Ú xÎB } |
|
= { x | ( $i ( iÎI Ù xÎAi )) Ú ( $i ( iÎI Ù xÎB ))} ( ∵ I ¹ Æ ) |
|
= { x | $i (( iÎI Ù xÎAi ) Ú ( iÎI Ù xÎB ))} ( ∵ メタ定理35 (e) ) |
|
= { x | $i ( iÎI Ù ( xÎAi Ú xÎB ))} ( ∵ メタ定理24 (b) ) |
|
= { x | $i ( iÎI Ù xÎAiÈB )} |
|
= ÈiÎI (AiÈB ) |
(5-10b) ( ÇiÎI Ai ) ÇB |
= { x | ( "i ( iÎI Þ xÎAi )) Ù xÎB } |
|
= { x | ( "i ( iÎI Þ xÎAi )) Ù ( "i ( iÎI Þ xÎB ))} ( ∵ I ¹ Æ ) |
|
= { x | "i (( iÎI Þ xÎAi ) Ù ( iÎI Þ xÎB ))} ( ∵ メタ定理35 (f) ) |
|
= { x | "i ( iÎI Þ ( xÎAi Ù xÎB ))} ( ∵ メタ定理30 (a) ) |
|
= { x | "i ( iÎI Þ xÎAi ÇB )} |
|
= ÇiÎI (Ai ÇB ) |
(5-10c) B \ ÈiÎI Ai |
= { x | xÎB Ù Ø$i ( iÎI Ù xÎAi )} |
|
= { x | xÎB Ù "i Ø( iÎI Ù xÎAi )} ( ∵ メタ定理37 (a) ) |
|
= { x | xÎB Ù "i ( iÎI Þ xÏAi )} ( ∵ メタ定理28 ) |
|
= { x | ( "i ( iÎI Þ xÎB )) Ù ( "i ( iÎI Þ xÏAi ))} ( ∵ I ¹ Æ ) |
|
= { x | "i (( iÎI Þ xÎB ) Ù ( iÎI Þ xÏAi ))} ( ∵ メタ定理35 (f) ) |
|
= { x | "i ( iÎI Þ ( xÎB Ù xÏAi ))} ( ∵ メタ定理30 (a) ) |
|
= { x | "i ( iÎI Þ xÎB \ Ai )} |
|
= ÇiÎI (B \ Ai ) |
(5-10d) C ÈiÎI Ai = ÇiÎI CAi |
が成り立ちます。また古典論理では、さらに次の結果が成り立ちます：
(5-11a)* (C \ A)ÈA = { x | (xÎC Ù xÏA) Ú xÎA } = { x | (xÎC Ú xÎA) Ù (xÏA Ú xÎA)} = { x | xÎC Ú xÎA } = CÈA |
(5-11b)* C \ (AÇB) = { x | xÎC Ù Ø(xÎA Ù xÎB)} = { x | xÎC Ù (xÏA Ú xÏB)} = { x | (xÎC Ù xÏA) Ú (xÎC Ù xÏB)} = (C \ A)È(C \ B) |
(5-11c)* C \ (C \ A) = { x | xÎC Ù Ø(xÎC Ù xÏA)} = { x | xÎC Ù (xÏC Ú xÎA)} = { x | (xÎC Ù xÏC) Ú (xÎC Ù xÎA)} = { x | xÎC Ù xÎA } = CÇA |
(5-11d)* CA È A = [t] |
(5-11e)* C(AÇB) = CA È CB |
(5-11f)* CCA = A |
(5-11g)* B \ ÇiÎI Ai |
= { x | xÎB Ù Ø"i ( iÎI Þ xÎAi )} |
|
= { x | xÎB Ù $i Ø( iÎI Þ xÎAi )} ( ∵ メタ定理40 (a) ) |
|
= { x | $i ( xÎB Ù Ø( iÎI Þ xÎAi ))} ( ∵ メタ定理36 (c) ) |
|
= { x | $i ( xÎB Ù ( iÎI Ù xÏAi ))} ( ∵ メタ定理39 (g) ) |
|
= { x | $i ( iÎI Ù ( xÎB Ù xÏAi ))} ( ∵ メタ定理22 (a) とメタ定理23 (a) ) |
|
= { x | $i ( iÎI Ù xÎB \ Ai )} |
|
= ÈiÎI (B \ Ai ) |
(5-11h)* C ÇiÎI Ai = ÈiÎI CAi |
さて、一般に存在述語記号 a と b が与えられたとき、a(T ) Ú b(T )
のことを aÚb(T )
と略記すると、これは項 T が a 項又は b 項という“実体を持った項”であることを意味するので、１変項述語記号 aÚb もまた存在述語記号とみなすことができます。従って、理論 aÚb というものを考えることができますが、これを理論 a と理論 b の和理論とよぶことにします。
そこで、特に理論 t とその冪理論 tP の和理論 t*
:º tÚtP のことを t 上の集合論とよぶことにしましょう。
さて、理論 t*
も、存在述語記号 t*
に伴う一つの理論ですから、t*
上の集合論 t**
というものを考えることができます。この操作はいくらでも繰り返すことができますが、これらの理論 t**¼*
を一般に t 上の高階の集合論といい、これらの高階の集合論を併せて t 上の階層理論といいます。必要に応じて次々に高階の集合論を作っていけば、かなり豊富な議論を展開することができます。
しかしながら、議論の途中でその都度高階の集合論を作っていくという操作はかなり煩わしく、できればこのような理論の拡大自体が固定された理論の中で再帰的に実行できた方が便利です。
そこで次のような考察を行ってみましょう。高階の集合論の述語 t**¼*
を一般に α や β で表すことにし（ * の個数はゼロでもよい）、α より β の方が t の肩の * の個数が多いとき α < β と書き、そうでないとき β £ α と書くことにします。
定義により、α £ β のとき、明かに α(T )
ならば β(T )
です。
さて、理論 α*
における { · | · }
のことを { · | · }
α と書き、理論 α*
における Î のことを Îα と書くことにすれば、各階層における冪理論の推論規則は次のようになります：
( α* 導入) |
α*( { x | R }α ) |
|
( Îα 導入) |
α(T )
(T | x)R
——————
TÎα{ x | R } α |
|
( Îα 消去) |
TÎα{ x | R }α
——————
(T | x) P |
TÎα A
————
α(T ) |
TÎα A
————
α*(A) |
ただし、( α*
導入) は、本当は αP( { x | R }α )
と書くべきですが、αP 項は α*
項なので、それに伴って書き換えています。
さて、階層理論における対象というのは、ベースになる t 項と、各 α に対する { x | R }
α のことに他なりません。そこで一般に、t 項のことを t 元とよび、{ x | R }
α の形の α*
項を α*
元とよび、T がある α に対する α*
元であることを、単に集合であるといって Set(T )
と書き、t 元と集合をあわせて元とよび、項 T が元であることを t'(T )
と表わすことにします。
また、ある α £ β に対して A が α 元で B が β*
元でしかも AÎβ B が成り立つとき A は B に属す、A は B の元である、あるいは B は A を元に持つといって AÎB と書くことにします。
また、A と B が共に集合で、XÎA であるような元 X について必ず XÎB が成り立つとき B は A を含むといって A Ì B 又は B É A と書くことにし、A Ì B かつ B Ì A であることを A と B は相等であるといって A =s
B と書くことにします。
また、集合 A は、A に属す集合が必ず A に含まれるとき推移的であるといって Tran(A)
と書くことにします。
なお、ここで用いた t' , Set
, Î , Ì , =s
といった“記号”は、単に言葉の省略のために用いたもので、正式な述語記号ではないことに注意します。
このとき、次のメタ定理が成り立ちます：
(5-12a) | すべての t 項を元に持つ集合が存在する。 |
(5-12b) | 任意の元 A , B に対し、これらを共に元に持つ推移的集合 C が存在する。 |
(5-12c) | 任意の集合 A に対し、A に含まれるどんな集合 X についても、それと相等なある集合 Y を元に持つ集合 B が存在する。
|
(5-12d) | 任意の集合 A と命題 R と A に現れない変数 x に対し、どんな元 X に対しても、XÎB が成り立つことと、XÎA と (X | x) R が共に成り立つことが同じことになるような集合 B が存在する。 |
その証明ですが、まず (5-12a)
は、A :º { x | Ø^ }
t が t 項をすべて元に持つ集合なので明らかです。
また (5-12b)
は、α と β が存在して、A は α 元で、B は β 元ですから、α < β のときは β を、そうでないときは α を γ と書いて、C :º { x | Ø^ }
γ と置けば十分です。
実際、A は α 元で α £ γ ですから A は γ 項です。ゆえにメタ定理８と ( Îγ 導入) により AÎγ C すなわち AÎC が得られます。
同様に、β £ γ であることを使うと BÎC が得られます。
また、XÎC が集合なら、δ*
£ γ であるようなある δ に対して X は δ*
元です。従って、X に属す任意の Y は δ 項で、従って γ 項ですから、C の定義とメタ定理８と ( Îα 導入) により C に属します。これは X Ì C を意味しています。
更に、t 元は γ 項ですから、C の定義とメタ定理８と ( Îα 導入) により C に属すので、以上により C は推移的です。
また (5-12c)
は、A がある α に対する α*
元なので、B :º { x | Ø^ }α*
と置けば十分です。
実際、X Ì A となる集合 X は、ある β に対する β*
元です。そこで Y :º { x | xÎβ X }
α と置きます。α*(Y )
ですから、メタ定理８と ( Îα*
導入) により YÎα*
B つまり YÎB が得られます。ゆえにあとは Y =s
X を示せば十分です。
そこで ZÎY と仮定すると、ZÎα Y なので、( Îα 消去) により ZÎβ X すなわち ZÎX が得られます。
逆に ZÎX と仮定すると、ZÎβ X ですが、仮定により X Ì A なので、ZÎA すなわち ZÎα A です。これは α(Z )
を意味しますから、( Îα 導入) により ZÎα Y すなわち ZÎY が得られます。
また (5-12d)
は、A がある α に対する α*
元なので、B :º { x | xÎα A Ù R }
α と置けば十分です。
実際、XÎA かつ (X | x)
R が成り立つとすると、α*(A )
なので、XÎα A かつ X はある β £ α に対する β 元で、( Ù 導入) により (X | x)[xÎα A Ù R]
が成り立ちますから、α(X )
が成り立つことに注意すれば、( Îα 導入) により XÎα B すなわち XÎB が得られます。
逆に、XÎB が成り立つとすると、α*(B )
なので、XÎα B かつ X はある β £ α に対する β 元で、( Îα 消去) により (X | x)[xÎα A Ù R]
が得られ、更に ( Ù 消去) により、XÎα A すなわち XÎA 及び、(X | x)
R が得られます。
さて、上記の (5-12)
はメタ言語で表現されたメタ定理ですが、これを形式化して公理化することにより、再帰的な集合の理論を構築することができます。すなわち、階層理論のことはすべて忘れて、任意に与えられた理論 t に対して、引数1の述語 Set
と引数2の述語 Î を追加し、
(5-13a) t' :º t Ú Set |
(5-13b) a Ì b :º "t¢ x ( xÎa Þ xÎb ) |
(5-13c) a =s b :º a Ì b Ù b Ì a |
(5-13d) Tran(a) :º "Set x ( xÎa Þ x Ì a ) |
と定義して、次の公理：
(Set-1) $Set a "t x : xÎa |
(Set-2) "t¢ a "t¢ b $Set c [ Tran(c) Ù aÎc Ù bÎc ] |
(Set-3) "Set a $Set b "Set x [ x Ì a Þ $Set y ( yÎb Ù y =s x ) ] |
(Set-4) "Set a $Set b "t¢ x [ xÎb Û ( xÎa Ù R ) ] |
を与えて理論を拡大します。ただし (Set-4)
の R は文字 a , b を含まない任意の命題です。
この (Set-1)
〜(Set-4)
は、順に (5-12a)
〜(5-12d)
をそれぞれ形式化したものですが、これらを順に全体集合の公理、推移性公理、冪集合の公理、分出公理とよぶことにします。なお、(Set-4)
は任意の命題 R を含んでいるため、正確にいえば公理ではなく推論規則です。
以上の理論拡大において、Set(T )
というのは、項 T がある α に対する α*
元という“実体を表わす項”であることを意味していたのですから、１変項述語記号 Set
は一つの存在述語記号です。
そこで、理論 t と理論 Set
の和理論である理論 t' のことを、理論 t 上の再帰的集合論とよぶことにします。
再帰的集合論においても、形式化前と同様に、t'(T )
を T は元であると読み、Set(T )
を T は集合であると読み、AÎB を A は B に属す、あるいは A は B の元であると読み、A Ì B のことを A は B に含まれると読み、A =s
B のことを、紛れがなければ単に A = B と書いて A と B は相等であると読み、Tran(A)
のことを A は推移的であると読むことにします。
また、記号 Ï , Ë , ¹ を集合論の場合と同じ意味で用います。
さて、(Set-1)
を満たす集合 a を取ると、(Set-4)
により "t¢ x [ xÎa Û ( xÎa Ù ^ ) ]
となる集合 a が存在して "t¢ x ( xÎa Û ^ )
が成り立ちます。そこで空集合を
(5-14) Æ :º εSet a "t¢ x [ xÎa Û ^ ] |
で定義します。また、同じ a に対して、(Set-4)
により "t¢ x [ xÎa Û ( xÎa Ù t(x) ) ]
となる集合 a が存在して "t¢ x [ xÎa Û t(x) ]
が成り立ちます。そこで（理論 t の）全体集合を
(5-15) [t] :º εSet a "t¢ x [ xÎa Û t(x) ] |
で定義します。また、元 a , b に対して (Set-2)
を満たす集合 c を取ると、(Set-4)
により "t¢ x [ xÎg Û ( xÎc Ù ( x º a Ú x º b ) ) ]
となる集合 g が存在して "t¢ x [ xÎg Û ( x º a Ú x º b ) ]
が成り立ちます。そこで、a と b の非順序対を
(5-16) {a, b} :º εSet g "t¢ x [ xÎg Û ( x º a Ú x º b ) ] |
で定義します。特に {a, a}
を {a}
と略記し、３個の元 a , b , c に対して {a, b, c} :º {a, b}È{c}
と定義します。個数が増えても同様です。
また、b º a に対して (Set-2)
を満たす c を取ると、(Set-4)
により "t¢ x [ xÎg Û ( xÎc Ù "Set z ( Tran(z) Þ xÎz ) ) ]
を満たす集合 g が存在しますが、ここで Tran(c)
であることに注意すれば "t¢ x [ xÎg Û "Set z ( Tran(z) Þ xÎz ) ]
が成り立ちます。そこで、集合 a の推移包を
(5-17) tran(a) :º εSet g "t¢ x [ xÎg Û "Set z ( Tran(z) Þ xÎz ) ] |
で定義します。また、特に集合 a の元がすべて集合である場合、同じ c に対して (Set-4)
により "t¢ x [ xÎg Û ( xÎc Ù $Set z ( xÎz Ù zÎa ) ) ]
を満たす集合 g が存在しますが、aÎc と Tran(c)
に注意すれば "t¢ x [ xÎg Û $Set z ( xÎz Ù zÎa ) ]
が成り立ちます。そこで、集合 a の和集合を
(5-18) Èa :º εSet g "t¢ x [ xÎg Û $Set z ( xÎz Ù zÎa ) ] |
で定義します。また、集合 a と b に対し、それらの合併とよばれる集合を
で定義します。また、集合 a に対して (Set-3)
を満たす b に対し、(Set-4)
により "t¢ y [ yÎb Û ( yÎb Ù Set( y) Ù y Ì a ) ]
を満たす集合 b が存在しますが、x Ì a を満たす集合 x と yÎb Ù y = x を満たす集合 y に対し、y Ì a なので yÎb となり、従って "Set x ( x Ì a Þ $Set y ( yÎb Ù y = x ) )
が成り立ちます。また明らかに "t¢ y ( yÎb Þ Set( y) Ù y Ì a )
が成り立つので、集合 a の冪集合を
(5-20) P (a) :º {Æ, a} È εSet b [ "Set x ( x Ì a Þ $Set y ( yÎb Ù y = x ) ) Ù "t¢ y ( yÎb Þ Set( y) Ù y Ì a ) ] |
で定義します。ここで {Æ, a}
との合併を取ったのは、a 自身と空集合を元に持たせた方が便利だからです。
次に、集合 a に対し、(Set-4)
を満たす b を取ると、b Ì a なので、(5-20)
により b = b となる集合 bÎP (a)
が存在し、"t¢ x [ xÎb Û ( xÎa Ù R ) ]
が成り立ちます。そこで a から R により分出された集合を
(5-21) { xÎa | R } :º εSet b [ bÎP (a) Ù "t¢ x ( xÎb Û ( xÎa Ù R ) ) ] |
で定義します。また、集合 a と b に対し、それらの共分と差集合を
(5-22a) aÇb :º { xÎa | xÎb } |
(5-22b) a \ b :º { xÎa | xÏb } |
で定義します。
さて、利便性のため、今後は t¢(x) Ù Set(a)
Ù xÎa のことを単に xÎa と書き、Set(a) Ù Set(b)
Ù a Ì b のことを単に a Ì b と書き、"t¢ x ( xÎa Þ R )
と $t¢ x ( xÎa Ù R )
のことを、それぞれ "xÎa :
R 及び $xÎa :
R と略記することにします。
このとき、全体集合、非順序対、和集合、合併集合、冪集合、分出された集合、空集合について、
(5-23a) xÏÆ |
(5-23b) xÎ[t] Û t(x) |
(5-23c) Tran(tran(a)) |
(5-23d) aÎtran(a) |
(5-23e) ( Tran(a) Ù xÎa ) Þ tran(x) Ì a |
(5-23f) xÎÈa Û $yÎa : xÎy |
(5-23g) xÎ{a, b ,¼, c} Û ( x º a Ú x º b Ú ¼ Ú x º c ) |
(5-23h) Æ, aÎP (a) |
(5-23i) xÎP (a) Þ x Ì a |
(5-23j) x Ì a Þ $yÎP (a) : y = x |
(5-23k) xÎ{ xÎa | R } Û ( xÎa Ù R ) |
(5-23l) { xÎa | R }ÎP (a) |
(5-23m) xÎaÈb Û ( xÎa Ú xÎb ) |
(5-23n) xÎaÇb Û ( xÎa Ù xÎb ) |
(5-23o) xÎa \ b Û ( xÎa Ù xÏb ) |
が成り立ちます。
ところで、明らかに、与えられた a , b , R 等に対して、それらの冪集合、分出された集合、空集合、全体集合、推移包、和集合、非順序対、合併、共分、差集合のそれぞれについて、それと同じ性質を持つ集合は、明らかに集合として相等です。
そこで、特に空集合と同じ性質を持つ集合、すなわち元を持たない集合をすべて空集合とよび、紛れのない限りやはり Æ で表すことにします。空集合は、明かに任意の集合に含まれます。
さて、理論 t 上の再帰的集合論では、ある１変項述語 r に対して、r 項は a の元である、という性質を持つ集合 a が存在すれば、(5-23k),(5-23l)
により、理論 r 上の冪理論 r*
の r*
項は、すべて P (a)
の元として表現できます。
ゆえに、この議論を繰り返せば、理論 r 上の階層理論における理論はすべて理論 t 上の再帰的集合論上の議論として正当化されることがわかります。
再帰的集合論において、集合 s を１個固定して、その冪集合 P (s)
上の演算 Æ , Ç , È , \
, C , Ç , È を
(5-24a) Æ :º { xÎs | ^ } |
(5-24b) aÇb :º { xÎs | xÎa Ù xÎb } |
(5-24c) aÈb :º { xÎs | xÎa Ú xÎb } |
(5-24d) a \ b :º { xÎs | xÎa Ù xÏb } |
(5-24e) Ca :º { xÎs | xÏa } |
(5-24f) ÇiÎI ai :º { xÎs | "iÎI : xÎai } |
(5-24g) ÈiÎI ai :º { xÎs | $iÎI : xÎai } |
で定義します。ただし、a , b , ai はすべて P (s)
の元とします。(5-23l)
により、それぞれの演算結果は確かに P (s)
の元になっています。
これらについても、(5-6)~(5-11)
の結果が [t]
を s に置き換えればすべて成立します。
さて、再帰的集合論には、“いくらでも多くの”集合が存在する、という性質があることがわかります。
具体的には、空集合 Æ から始めて、空集合だけからなる集合 {Æ}
、空集合だけからなる集合だけからなる集合 {{Æ}}
、…と続けていけば、これらはすべて等しくない集合です。
実際、こうして順次作っていった集合を並べて Æ , {Æ}
, {{Æ}}
,¼, a , {a}
としたとき、最後の {a}
がそれより手前のどの集合とも等しくないことを証明すれば十分です。
そこで、このことが a まで並べたものについては既に確かめられているものとし、{a}
がそれより手前の集合 b と等しいと仮定します。このとき b は一番最初の Æ であるか、２番目以降であるかいずれかですが、前者なら、{a}
は元を持ち、Æ は元を持たないので矛盾し、b が２番目以降の集合なら、b はその手前の集合 c により {c}
と書けますが、{a} º {c}
から a º c が得られ、仮定により a はそれより手前の c と等しくないのでやはり矛盾します。以上で証明されました。
さて、t 上の再帰的集合論も、存在述語記号 t' に伴う一つの理論ですから、この理論 t' の冪理論を考えることができます。
そこで、理論 t' 上の集合論 t'*
における「集合」を、紛れがないように類とよび、R を満たす t' 項の全体を太文字で { x | P }
と書き、類に属すことを意味する Î も Î と書くことにします。Ï , Ì , Ë , Ç , È についても同様に Ï , Ì , Ë , Ç , È と書き、=s
に対するものは =c
と書くことにします。
また、類 A に対して "t' x ( xÎA Û xÎa )
を満たす集合 a が存在するとき、類 A は集合であるということがあります。
集合論 t'*
において、次の２条件：
(5-25a) "Set a ( a = Æ Þ aÎA ) |
(5-25b) "Set a "t¢ b ( aÎA Þ aÈ{b}ÎA ) |
を満たすすべての類 A に属す集合と相等な集合を有限集合といいます。
定義により、空集合や、有限集合 a に任意の元 b を加えた aÈ{b}
は有限集合です。従って特に、集合 {a}
や {a, b}
も有限集合です。
また、有限集合と有限集合の合併も有限集合です。
実際、有限集合 a との合併が有限集合であるような集合の全体からなる類を A とします。
まず aÈÆ = a は有限集合ですから Æ は A に属します。
また bÎA すなわち aÈb が有限集合なら aÈ(bÈ{c}) = (aÈb)È{c}
は有限集合ですから bÈ{c}
も A に属します。
ゆえに A は条件 (5-25)
を満たすので、すべての有限集合は A に属します。これは、有限集合 a と有限集合の合併が有限集合であることを意味しています。
更に、有限集合だけからなる有限集合の和集合も有限集合です。
実際、元がすべて有限集合であると仮定するとその和集合が有限集合になるような集合の全体からなる類を A とします。
まず ÈÆ = Æ は有限集合ですから Æ は A に属します。
また、aÎA と t' 項 b に対し、aÈ{b}
の元がすべて有限集合であると仮定すると、a の元はすべて有限集合で、しかも b も有限集合です。
ゆえに È(aÈ{b}) = (Èa)
Èb の右辺は有限集合と有限集合の合併ですから有限集合で、従って aÈ{b}
は A に属します。
ゆえに A は条件 (5-25)
を満たすので、すべての有限集合は A に属します。これは、元がすべて有限集合であるような有限集合の和集合が有限集合であることを意味しています。
