Hatena::ブログ(Diary)

再帰の反復

2012-06-16

反復的集合観と公理的集合論

反復的集合観とZFCについて

  1. 素朴集合論
  2. 内包公理の放棄
  3. 整礎原理
  4. 集合によるコーディング
  5. 反復的集合観
  6. 集合観から公理へ
  7. ZFC
  8. クラス
  9. 到達不能基数

1. 素朴集合論

素朴集合論における集合のイメージを一言でいうと次のようになる。

集合とは、概念の外延である。

ここに出てくる「概念の外延」というのはいまいちよく判らない言葉だけど、おおざっぱには、概念が当てはまる対象(要素)の全体とか範囲といったことを意味する。

重要なのは、「概念」と「概念の外延」は異なるということ。

「概念の外延」は、概念そのものではなく、その概念が当てはまる対象全体によって定まる何か。ここでは元の概念が何だったのかは捨象される。そのため2つの異なる概念があっても、その概念が当てはまる対象が全く同じだとしたら概念の外延は同一になる。

素朴集合論公理

「集合とは、概念の外延である」という主張を公理化すると

  • 概念があれば、それに対して集合が考えられる(内包公理)
  • 集合(=概念の外延)の同一性はそれに含まれる対象によって定まる(外延公理)

という2つの公理にまとめられる。

(※「内包公理」は英語だと「comprehension axiom」。「内包」は「intension」の訳語にも使われるので、訳語を変えて「包括公理」とも呼ばれる)

「概念」は述語によって表現する。たとえば「xはリンゴである」という述語によって「リンゴ」という概念を表す。すると「概念があれば、それに対して集合が考えられる」は次の公理で表される。

内包公理

どんな述語P(x)を取っても、次が成り立つ。

 ¥exists s ¥forall x ¥left(x ¥in s ¥leftrightarrow P(x) ¥right)

(どんな述語P(x)についても、それに対応する集合sがある)

ここに出てくる「¥in」という2項述語は集合についての基本的な述語で「xはsに含まれる」と読む。

また次に述べる外延公理を使うと述語P(x)に対応する集合は一つしかないことが出てくるので、その集合を¥{x|P(x)¥}と書く。次の式が成り立つ。

 ¥forall x ¥left(x ¥in ¥{x|P(x)¥} ¥leftrightarrow P(x) ¥right)

一方「集合の同一性はそれに含まれる対象によって定まる」というのは次の公理で表される。

外延公理

 ¥forall s ¥forall t ¥left(s=t ¥leftrightarrow ¥forall x (x ¥in s ¥leftrightarrow x ¥in t)¥right)

(全く同じ要素を含んでいる集合は等しい)

たとえば、aとbとcだけを含んでいるような集合は、ただ一つしか存在しない(少なくとも一つ存在することは内包公理から出てくる)。その集合は¥{a,b,c¥}と書かれる。有限個の要素しか含んでいない集合は、含んでいる要素を全て列挙することでその集合を特徴づけることができる。

素朴集合論パラドクス

素朴集合論公理は非常に単純だけど、よく知られているようにさまざまなパラドクスが発生する。

例えばラッセルパラドクス

述語「x¥not¥in x」(xは自分自身に含まれない)について内包公理適用すると

¥{x|x¥not¥in x¥}

という集合が得られる。この集合は、自分自身を含まないものの集合である。

「自分自身を含まないものの集合」というのは日本語で書くと怪しげな感じがするけど、記号で書いた「x¥not¥in x」には集合や論理で基本的な「¥in」「¥neg」しか使っていない。

問題の集合をsと書く。この集合は外延公理P(x)としてx¥not¥in xを取ったものなので、

 ¥forall x ¥left(x ¥in s ¥leftrightarrow x ¥not¥in x ¥right)

であり、xsで例化すると

  s ¥in s ¥leftrightarrow s ¥not¥in s

となり、ここから矛盾が導かれる(この矛盾は直観主義論理の範囲で生じる)。

2. 内包公理放棄

素朴集合論では矛盾が生じてしまうので、どこかを手直ししないといけない。

  • 外延公理は「集合とはどんなものか」についての公理
  • 内包公理は「どんな集合が存在するか」についての公理

ラッセルパラドクスも他の集合論パラドクスも「何かおかしな集合の存在について考えると矛盾する」という話なので、内包公理を捨てることにする(実際には他の選択肢も考えられるが話の都合上こうなる)。

すると「どんな集合が存在するか」について内包公理とは違う考え方が必要になる。

3. 整礎原理

まず次の考え方をとることにする。

自分自身を含むような集合は存在しない。

これを採用するのは、必ずしもパラドクスを避けるためではない。

たとえば「集合とは要素を集めたものである」という見方を取ると、論理的な順序としてまず要素があってからそれらを含んでいる集合が存在しているので、集合が自分自身を含んでいるのはそもそもおかしいことになる(一方、概念と集合の存在を結びつける内包公理の見方では、ある概念がその概念自身にも当てはまることがあるのだから、ある集合がその集合自身に含まれていても別におかしくはない)。

また別の理由として、自分自身を含む集合を認めると集合の同一性が外延公理だけでは決まらない(のが嫌だ)というものがある。

自分自身だけを含むような集合としてaとbを取ったとする。

a=¥{a¥}

b=¥{b¥}

が成り立っている。このとき、aとbは等しいだろうか。

内包公理のもとでは、aの存在もbの存在も何らかの概念P(x),Q(x)によっている。

a=¥{x|P(x)¥}

b=¥{x|Q(x)¥}

したがってP(x),Q(x)を見ることでaとbが等しいかどうかを調べることができる。

しかし内包公理を取らない立場では、aとbが等しいかどうかを判断するためには何らかの新しい原理が必要になる。そして、そのような新たな原理を積極的に提案するよりも初めから自分自身を含むような集合を排除して考えようということになる(この場合必ずしも自分自身を含む集合は存在しないと強く主張する必要はなくて、そういうものは排除した範囲で考えようという立場かもしれない)。

いずれにしても自分自身を含む集合を認めないなら、同様の理由で

a ¥in b ¥in aとかa ¥in b ¥in c ¥in aとなるような集合も認められない。もっと一般的に

a_1 ¥ni a_2 ¥ni a_3 ¥ni a_4 ¥ni a_5 ¥ni ¥ldots

となるようなものは認められない(自分自身を含む集合はa¥ni a¥ni a¥ni ¥ldotsとなりこれに反している)。「まず要素があってから集合がある」という考え方によればこのような集合は存在しないし、このような集合の同一性は外延公理だけでは決まらないので。

このような集合が存在しないことを整礎原理と呼ぶことにする。

整礎原理
a_1 ¥ni a_2 ¥ni a_3 ¥ni a_4 ¥ni a_5 ¥ni ¥ldotsとどこまでも続くような集合は存在しない。

整礎原理は、どんな集合が存在するのかについては積極的に主張していないけれど、ここから集合の間に成立している秩序が見えてくる。

まず自分自身を含んでいたり包含関係が循環することがないため、「¥in」について順序関係が成立することになる。つまり包含関係「¥in」に基づく「より単純な集合」¥leftrightarrow「より複雑な集合」という相対的な位置づけを与えることができる。しかも包含関係「¥in」を内側にたどっていくと必ずどこかで終わるので、「より単純な集合」¥leftrightarrow「より複雑な集合」のうち、「より単純な集合」の方向はどこかで終点に至る。

整礎原理の成り立つ集合世界では、もっとも単純な集合から始まってだんだん複雑な集合に向かっていくという整然とした秩序が存在する(この秩序は集合の要素数の大小関係とは異なる。たとえば0¥in N ¥in ¥{N¥})。

もっとも単純な集合は、要素を何も含まない空集合¥emptyである。空集合¥emptyはもちろん存在してほしい。

またこの空集合を元にして、¥bigl{¥empty ¥bigr} ,¥: ¥bigl{¥bigl{¥empty ¥bigr}¥bigr},¥: ¥bigl{¥bigl{¥bigl{¥empty ¥bigr}¥bigr}¥bigr},¥: ¥bigl{¥bigl{¥bigl{¥bigl{¥empty ¥bigr}¥bigr}¥bigr}¥bigr},¥ldotsとか¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr},¥: ¥bigl{¥empty,¥bigl{¥empty¥bigr},¥bigl{¥bigl{¥empty¥bigr}¥bigr}¥bigr},¥:¥bigl{¥empty,¥bigl{¥empty¥bigr},¥bigl{¥bigl{¥empty¥bigr}¥bigr},¥bigl{¥bigl{¥bigl{¥empty¥bigr}¥bigr}¥bigr}    ¥bigr},¥ldots  といった集合も存在していてほしい。

4. 集合によるコーディング

空集合を素材にして作られるこれらの集合は一見つまらないものにも見えるけど、実際はそうではない。

こうした集合さえあればそれを使って自然数コーディングすることができる(たとえばLispでリストを使って自然数を表現するとかラムダ式自然数を表現したりするのと同様なことだと思えばいい)。通常、次のようにコーディングされる(「どうコーディングされるのか」よりも「コーディングが可能」ということが重要)。

¥begin{array}{ccl}0 & ¥equiv & ¥empty ¥¥ 1 & ¥equiv & ¥bigl{0¥bigr} ¥¥ 2 &¥equiv & ¥bigl{0,1¥bigr} ¥¥ 3 & ¥equiv & ¥bigl{0,1,2¥bigr} ¥¥ 4 & ¥equiv & ¥bigl{0,1,2,3¥bigr} ¥¥ & ¥vdots & ¥end{array}

さらに

  • 組(タプル)¥bigl(a,b ¥bigr)は、¥bigl{¥bigl{a¥bigr},¥bigl{a,b¥bigr}¥bigr}で表すことができる(a=cかつb=dのときに限って¥bigl{¥bigl{a¥bigr},¥bigl{a,b¥bigr}¥bigr}=¥bigl{¥bigl{c¥bigr},¥bigl{c,d¥bigr}¥bigr}が成り立つので)。
  • 関係や関数は組の集合で表すことができる。

5. 反復的集合観

空集合を起点としてそこからより複雑な集合を考えていくだけで非常にたくさんの集合の存在が出てくることになる。この考えをより系統的に表してみる。

  • 段階0: 何もない。
  • 段階1: 段階0までの集合を要素とするあらゆる集合を考えて、それらを追加する。
  • 段階2: 段階1までの集合を要素とするあらゆる集合を考えて、それらを追加する。
  • 以下同様。

これは次のように言い換えられる。

  • V_0: 何もなし
  • V_1: V_0全体を一つの集合と考えて、V_0のあらゆる部分集合を追加する。
  • V_2: V_1全体を一つの集合と考えて、V_1のあらゆる部分集合を追加する。
  • 以下同様。

各段階で得られている集合を具体的に書くとこうなる。

  • V_0: 何もなし
  • V_1: ¥empty
  • V_2: ¥empty,¥:¥bigl{¥empty¥bigr}
  • V_3: ¥empty,¥:¥bigl{¥empty¥bigr}, ¥: ¥bigl{¥bigl{¥empty¥bigr}¥bigr},¥: ¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}
  • V_4: ¥empty,¥:¥bigl{¥empty¥bigr}, ¥: ¥bigl{¥bigl{¥empty¥bigr}¥bigr},¥: ¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr} , ¥: ¥bigl{¥bigl{¥bigl{¥empty¥bigr}¥bigr}¥bigr}, ¥: ¥bigl{¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥empty,¥bigl{¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥empty,¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥bigl{¥empty¥bigr},¥bigl{¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥bigl{¥empty¥bigr},¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥bigl{¥bigl{¥empty¥bigr}¥bigr},¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥empty,¥bigl{¥empty¥bigr},¥bigl{¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥empty,¥bigl{¥empty¥bigr},¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥empty,¥bigl{¥bigl{¥empty¥bigr}¥bigr},¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥bigl{¥empty¥bigr},¥bigl{¥bigl{¥empty¥bigr}¥bigr},¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}¥bigr} , ¥: ¥bigl{¥empty,¥bigl{¥empty¥bigr},¥bigl{¥bigl{¥empty¥bigr}¥bigr},¥bigl{¥empty,¥bigl{¥empty¥bigr}¥bigr}¥bigr}
  • V_5: ¥cdots

この過程を続けていけば多く集合が得られるし、先に述べたコーディングを使えば数や関数も考えられることになる。

しかしこれを続けていくだけでは、いつまでたっても有限の集合しか得られない。そこで次のように考える。

  • 段階ω: 段階0、段階1、段階2、……のどこかで出てくる集合の全てを考える。
  • 段階ω+1: 段階ωまでの集合を要素とするあらゆる集合を追加する。
  • 段階ω+2: 段階ω+1までの集合を要素とするあらゆる集合を追加する。
  • 以下同様。

段階ωにはあらゆる自然数(をコーディングした集合)が登場しているので、段階ω+1で自然数全体の集合Nが登場することになる。整数有理数自然数を使って定義できて実数は有理数の集合(コーシー列や切断)で定義できるので、そうした集合もこれらの段階のどこかで得られる。さらに実数や複素数についての関数やそうした関数の集合も得られる。

しかしまだ先が考えられる。

  • 段階ω×2 (=ω+ω): 段階ω、段階ω+1、段階ω+2、……の集合の全てを考える。
  • 段階ω×2+1: 段階2ωまでの集合を要素とするあらゆる集合を追加する。
  • 段階ω×2+2: 段階2ω+1までの集合を要素とするあらゆる集合を追加する。
  • 以下同様。

同じく、段階ω×3、ω×4、ω×5……が考えられる。するとさらにこれらをひとまとめにする段階が考えられる。

  • 段階ω2: 段階ω、段階ω×2、段階ω×3、……の集合の全てを考える。
  • 段階ω2+1: 段階ω2までの集合を要素とするあらゆる集合を追加する。

さらにこうした段階をさらに高次に繰り返すこともでき、それらを「果てしなく」繰り返すことができる。このようにして無から膨大な量の集合が得られる。

そして、どんな集合もこれらの段階のどこかで得られるという考え方を反復的集合観と呼ぶ。

(※反復的集合観は、集合を「構築する」「構成する」「作る」という言い方と相性がいいけど、必ずしも構成的な見方をしているとは限らない。「どんな自然数も1を足すことで作ることができる」と言ったとして、必ずしも自然数を構成物とか作られた物と考えているわけではないのと似ているかもしれない。以下の文章についても同様)

6. 集合観から公理

反復的集合観に合うように集合論公理を設定していくことを考える。

反復的集合観では「はてしない段階があって、どんな集合もそれらのどこかの段階で得ることができる」と考えた。しかし集合論は段階を直接扱うわけではない。なので、各段階で生じる集合の存在を保証するように公理を設定していく(それによって間接的に段階の存在が保証される)。

巾集合公理

ある段階の次の段階であらゆる部分集合が追加されるので、巾集合の存在を保証する公理を設定する。

巾集合公理

 ¥forall s ¥exists t ¥forall x(x ¥in t ¥leftrightarrow x¥subseteq s) 

(どんな集合sについても、sの巾集合tが存在する。

sの巾集合は、2^{s}とかP(s)と書かれる)

もしも段階rに登場する集合sがあったとする。そのとき、巾集合公理で保証される集合tは段階r+1で登場する。したがって巾集合公理を成り立たせるには、ある段階rがあればその次の段階r+1もなければならないことになる。

なお巾集合公理は「sの部分集合が「もしあれば」それはtに含まれる」といっているだけで、sにどんな部分集合があるのかについては何も保証していない。どんな部分集合があるかは、他の公理によって保証する必要がある。

空集合公理

空集合公理

¥exists s ¥forall x(x ¥not¥in s)

(どんな要素も含まない集合が存在する。

この集合は空集合と呼ばれ¥emptyと書かれる)

空集合公理によって段階1があることが保証される。

対集合公理と和集合公理

対集合公理

¥forall x ¥forall y ¥exists s ¥forall z (z ¥in s ¥leftrightarrow z=x ¥vee z=y)

(xとyだけを要素とする集合sが存在する。

xとyだけを要素とする集合は¥{x,y¥}と書かれる。

x=yの場合は¥{x¥}と書かれる)

和集合公理

¥forall s ¥exists t ¥forall x (x ¥in t ¥leftrightarrow ¥exists y (x ¥in y ¥wedge y ¥in s))

(sに含まれる全ての集合の和集合tが存在する。

sの和集合は¥cup sと書かれる。

sが¥{x_1,x_2,¥ldots,x_n¥}の場合、¥cup sx_1 ¥cup x_2 ¥cup ¥cdots ¥cup x_nとも書く)

有限の段階(段階1、段階2、段階3……)では有限集合しか登場しないので、巾集合公理を使わなくても、対集合公理と和集合公理を繰り返し適用することで任意の集合を得ていくことができ、各段階の存在も保証される(段階ω以降では巾集合公理が必須になる)。

無限公理

ここまでに登場した空集合公理、対集合公理、和集合公理、巾集合公理をどれだけ繰り返し使っても、それだけでは有限集合しか保証されない(空集合も対集合も有限集合。有限集合を有限個集めた和は有限集合。有限集合の巾集合は有限集合)。したがって段階についても有限の段階(段階1、段階2、段階3……)しか要請されない。

そこで次の公理を置く。

無限公理

¥exists s (¥empty ¥in s ¥wedge ¥forall x (x ¥in s ¥to x ¥cup ¥{x¥} ¥in s))

(sは無限個の要素を含む集合。

先に述べた自然数コーディングを採用すれば、sは0,1,2……の全てを含む集合ということになる。ただしsはそれ以外の要素も含んでいるかもしれない。この公理はそれについては何も言っていない)

無限集合公理によって、無限個の要素を持つ集合の存在と、有限番目でない段階ω+1が保証される。

部分集合の存在を決める公理(分出公理選択公理)

無限集合公理によって可算濃度の集合の存在が保証される。また、和集合公理や巾集合公理によってより大きな集合を得ることもできる。しかしこれらの公理はそれらの集合の部分集合の存在についてはほとんど何も言っていない。したがって部分集合の存在を保証するための公理が必要になる。

しかしここには重大な問題がある。

連続体問題が解決していないことや選択公理の扱いについて(まれにだとしても)疑問が出されることに象徴されるように、無限集合にいったいどんな部分集合があるのかについてはっきりとした見方を持ち合わせていない。「あらゆる要素の組み合わせによる部分集合が存在するのだ」といったとしても、無限集合におけるあらゆる組み合わせというのがどういうことなのかは明確ではない。

一応は次のような公理が設定される。

分出公理

論理式¥psi(x)があり、この論理式はt自由変数に持たないとする。

このとき次は公理になる。

¥forall s ¥exists t ¥forall x (x ¥in t ¥leftrightarrow x ¥in s ¥wedge ¥psi(x))

(sの要素のうち¥phi(x)を満たすものからなる集合tが存在する。

tは¥{x¥in s | ¥phi(x)¥}と書かれる。

分出公理に出てくる述語¥psi(x)は、(t自身を除いて)任意の集合について言及してかまわない。そのため、存在する(存在が保証される)集合が多ければ多いほど分出公理も強力になっていく。

しかし任意の集合に言及できるということは、sやtよりも高い段階に属する集合について言及できるということでもある。ある集合の性質がそれよりも高い段階の集合によって規定されるというのは、反復的集合観とはいくらかズレているようにも見える。

「要素のあらゆる組み合わせによる部分集合があるんだから、どんな述語を使って部分集合を切り出しても構わないはずだ(たとえ述語に高い段階の集合への言及があっても)」という直感は、反復的集合観からは必ずしも出てこない(cf. 戸田山和久「<つくられたもの>としての集合」(「季刊哲学」5号))

あとどんな部分集合があるかを規定する別の公理として選択公理がある。

選択公理

 ¥forall s ¥left(¥forall x (x ¥in z ¥to x ¥not= ¥empty) ¥wedge ¥forall x_1 ¥forall x_2 ( x_1¥in s ¥wedge x_2 ¥in s ¥wedge x_1 ¥not= x_2 ¥to x_1 ¥cap x_2 = ¥empty) ¥¥ ¥qquad ¥to ¥exists t ¥forall x ¥exist a ( x ¥in s ¥to t ¥cap x = ¥{a¥})¥right)

集合sのどの要素も空集合でなくそれらは共通の要素を含んでいないとする。そのとき、sに含まれる各集合x¥in sから1要素ずつ取ってきた集合t(sの選択集合)が存在する。

ここでも「要素のあらゆる組み合わせによる部分集合があるなら選択集合もあるはずだ」という直感は、反復的集合観とは別のところから来ている。

置換公理

ここまでに出てきた公理によって非常にたくさんの集合の存在が保証される。

しかし「段階が果てしなく続いていく」という観点からはまだ充分ではない。無限公理と巾集合公理によって段階ω+1、ω+2、ω+3、……に現れる集合は保証されるのだけど、段階ω×2以降を保証してくれる公理がない。なので「果てしない段階」を保証してくれるような公理が必要となる。

「果てしない段階」における段階には次の2種類がある。

  1. 直前の段階に登場した集合のあらゆる組み合わせを追加する段階。
  2. それ以前の段階全体をひとまとめにする段階。

1は「段階○○+1」と書かれるもので、2は「段階ω」「段階ω×2」「段階ω2」のように直前の段階を持たないもの。

ある段階があれば巾集合公理を成り立たせるために次の段階も必要になるので、1の段階が続いていくことは保証される。なので「果てしない段階」を成り立たせるためには、2の段階を保証してくれる公理が必要になる。

そのために置換公理を導入する。

置換公理を使えば「果てしない段階」を非常に強い形で保証してくれる。しかしこれは、反復的集合観を取るなら必ず置換公理を受け入れなければならないということではない。漠然とした形の反復的集合観に比べると置換公理の主張の方がずっと強いと考えることもできる(cf. ブーロス「反復的な集合観」(飯田隆『リーディングス 数学の哲学』))。

置換公理では、段階の系列を縦断して要素を拾い上げそれらを取りまとめた集合の存在を保証する。

たとえば、自然数の集合Nは段階ω+1の集合で、その巾集合P(N)は段階ω+2の集合、P(P(N))は段階ω+3の集合、P(P(P(N)))は段階ω+4の集合、……になっている。このとき、これら全てを含んだ集合¥{N,P(N),P(P(N)),P(P(P(N))),¥ldots ¥}の存在を、置換公理は保証してくれる。この集合は段階ω+1、ω+2、ω+3、……の集合を縦断して含んでいるので、それよりも高い段階ω×2+1にならないと登場しない。このように段階の系列を縦断して要素を取りまとめることを認めると、それらのどの段階よりも高い段階が要請される。

しかし系列の縦断を無制限に認めると簡単に矛盾が発生する(もしも全ての段階のそれぞれから要素を取り上げてそれらをまとめた集合があったとしたら、その集合はどの段階に現れるのか)。

置換公理では次のように考える。

まず関数的な述語¥psi(x,y)を取る。「¥psi(x,y)関数的」というのは、xを一つ選んだときに¥psi(x,y)を満たすyは(もしあるなら)唯一つに決まるということ(また、もし仮に内包公理を認めたとしたら、この関数を表す集合¥{¥bigl<x,y¥bigr> | ¥psi(x,y)¥}の存在が出てくる)。

ここの文脈で重要な¥psi(x,y)

¥begin{array}{ccl} x & & y  ¥¥ 0 & ¥mapsto & N ¥¥ 1 & ¥mapsto & P(N) ¥¥ 2 & ¥mapsto & P(P(N)) ¥¥ 3 & ¥mapsto & P(P(P(N))) ¥¥ & ¥vdots & ¥end{array}

のように、¥psi(x,y)の対応関係が段階の階層を縦断しているようなもの。

次に任意に集合sを取り上げる。このときsの各要素を¥psi(x,y)で写したものの全てを要素とする集合がある、というのが置換公理の主張。

上の例だと、sとして¥{0,1,2,¥ldots ¥}を取れば、これを¥psi(x,y)で写した¥{N,P(N),P(P(N)),P(P(P(N))),¥ldots ¥}の存在が保証される。この集合が存在するので、段階ω×2+1以降もあることになる。

また無限の大きさ(濃度、基数)の観点から言えば、こうして得られた集合に和集合公理適用することで、これらの集合の系列のどれよりも濃度の大きい集合が得られる。

置換公理では、無制限に系列の縦断をおこなうのではなく、存在している集合sの大きさによって制限される。それでも置換公理(と和集合公理)を使ってより濃度の大きな集合が得られ、得た集合を使って再び置換公理適用すればさらに大きな集合が得られていく。これは繰り返しおこなえる。そのため置換公理を導入することで「果てしなく続いていく段階」が非常に強い形で保証されることになる。

置換公理

論理式¥psi(x,y)があり、この論理式はy_1,y_2,t自由変数に持たないとする。

このとき次が公理になる。

¥forall x ¥forall y_1 ¥forall y_2 ¥left(¥psi(x,y_1) ¥wedge ¥psi(x,y_2) ¥to x_1 = x_2 ¥right) ¥¥ ¥qquad ¥to ¥forall s ¥exists t ¥forall y ¥left( y ¥in t ¥leftrightarrow ¥exists x ¥in s ( ¥psi(x,y))¥right)

(分出公理は置換公理から導かれるので、置換公理を導入すると分出公理は不要になる)

正則性公理

反復的集合観に先立って次の整礎原理を述べた。

整礎原理
a_1 ¥ni a_2 ¥ni a_3 ¥ni a_4 ¥ni a_5 ¥ni ¥ldotsとどこまでも続くような集合は存在しない。

これを次のように公理化する。

正則性公理

 ¥forall s ¥left( s ¥not= ¥empty ¥to ¥exists x ¥in s ( x ¥cap s = ¥empty) ¥right)

(反復的集合観によれば、sに含まれるどの要素もsが現れる段階よりも低い段階で現れる。sの要素の中で最も低い段階に現れるものをxとすれば、xとsが共通要素を持つことはない。もしあればそれはxよりも低い段階に現れるsの要素になりxの取り方に反するので)

正則性公理が成り立たないとすると、空集合でないある集合sについて  ¥forall x ¥in s ( x ¥cap s ¥not= ¥empty) となるので、

¥begin{array}{ccl}x_1 & ¥in & s ¥¥ x_2 & ¥in & x_1 ¥cap s ¥¥ x_3 & ¥in & x_2 ¥cap s ¥¥ & ¥vdots & ¥end{array}

となり、 x_1 ¥ni x_2 ¥ni x_3 ¥ni x_4 ¥ni ¥ldotsという系列が得られる。

ただし正則性公理を追加したからといって、 x_1 ¥ni x_2 ¥ni x_3 ¥ni x_4 ¥ni ¥ldotsとなる集合や自分自身を含む集合の存在が証明されないことを保証しているわけではない(ある公理から何かの存在が導かれるときに非存在を主張する公理を追加しても、存在するという証明を打ち消すことはできない。単に矛盾が導かれるようになるだけ)。

元の公理系が「自分自身を含む集合はあってもいいし、なくてもいい」というものだとしたら、正則性公理の追加によって自分自身を含む集合の存在は排除される。でも元の公理系で自分自身を含む集合の存在が導かれるとしたら、そこに正則性公理を追加しても矛盾が導かれるようになるだけ。

7. ZFC

ここまで出てきた公理を列挙すると次のようになる。

これら全てからなる公理系をZFCと呼ぶ。Z=ツェルメロ、F=フレンケル、C=選択公理(Axiom of Choice)。公理系から選択公理を除いた場合「C」が取れる。

8. クラス

ZFCでは内包公理は認められない。

しかし、ある概念(を定義した述語)P(x)があるならばそれに対応する集合¥{x|P(x)¥}について語るというのは数学でごく普通におこなわれることなので、集合論でもそのような言い方を使いたい。

そのために¥{x|P(x)¥}の形の式を集合とは呼ばずにクラスと呼ぶことにする。

クラスは集合論のファーストクラスオブジェクトではなく、構文上のマクロのようなものにすぎない。集合論の基本的な述語は「=」と「∈」の二つで、クラスは

  • ¥{x|P(x)¥}=¥{x|Q(x)¥}は、 ¥forall x ¥left( x ¥in ¥{x|P(x)¥} ¥leftrightarrow x ¥in ¥{x|Q(x)¥}¥right)の省略。
  • a ¥in ¥{x|P(x)¥}は、P(a)の省略。

というような感じで扱われ、集合論の内部に実際に登場することはない。クラス用の変数も導入できるのだけど、これも集合論の体系自体には含まれない一種の省略記法として扱われる。

9. 到達不能基数

置換公理によって「果てしなく続く段階」や濃度の非常に大きな集合の存在が出てくるのだけど、さらに「その先」を考えることもできる。

濃度(無限の大きさ)について考える。

ZFCでは、濃度の小さい集合からそれよりも濃度の大きい集合を手に入れる方法として次の3つがある。

  1. 「次の大きさの濃度」を取る。
  2. 巾集合を取る。
  3. 置換公理を使って濃度の増大列からなる集合を作り、その和集合を取る。

そしてこれらに対応して次の3つの性質が考えらえる。

  1. 極限基数: 1で得られないタイプの無限
  2. 強極限基数: 2で得られないタイプの無限
  3. 正則基数: 3で得られないタイプの無限

(ZFCでは連続体仮説が成り立つかどうか決まらないために、1と2が違うのかどうかは決まらない)

最も小さい無限基数である¥aleph_0 (= ¥omega)は、この3つの性質を全て備えている。「有限基数の次の基数は有限」「有限集合の巾集合は有限」「有限基数の増大列で有限の長さのものの和集合は有限」なので。ZFCに無限公理の導入が必要だったのは、¥aleph_0 がこの性質を持っていたため。

そして¥aleph_0より大きい基数で1・3を満たす基数を弱到達不能基数、1・2・3を満たす基数を(強)到達不能基数と呼ぶ。

到達不能基数は(たとえ存在していたとしても)ZFCの道具立てでは得ることができない。逆に言えば、そんなものは初めから存在しないとみなしてもZFCの範囲では別に困らない。

もしも到達不能基数の存在を認めてその存在を公理として置けば、置換公理で保証されたよりもさらに先まで「果てしない段階」が続くことになる(そして、到達不能基数よりもさらに大きな無限の存在をいうさまざまな巨大基数公理がひかえている)。

く 2015/02/17 07:38 無限公理の記号による表現ですが、aはすべてsではないでしょうか。

lemniscuslemniscus 2015/02/17 22:44 指摘の通りですね。ありがとうございます。修正しました。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/lemniscus/20120616/1339838683
リンク元