集合論

出典: フリー教科書『ウィキブックス(Wikibooks)』
集合 から転送)

数学>集合論

集合とはなにか?[編集]

集合(set)とは、物の集まりであって、何か物を持ってきたときにそこに属すのか属さないのかどちらかに必ず定まるもののことである。例えば、「標高8500m以上の山」「都道府県であって、人口500万人未満のもの」「すべての二等辺三角形」「正の奇数すべて」などは集合である。ただし、「頭がいい人」のような、何が属して何が属さないのかが曖昧なものは集合とは呼ばないことにする。

集合に属している物のことを (element)と呼ぶ。先ほどの例から、「標高8500m以上の山」という集合では、「エベレスト、K2、カンチェンジュンガ、ローツェの4つの元がある」などと言う。「正の奇数すべて」の集合は、「1,3,5,...という無限個の元から成っている」と言える。元が集合に属していることを「」という記号で表す。例えば、自然数の全体という集合をとすると、と書ける。

なお、元が1つもない集合も集合とみなすことにする。そのような集合を空集合 (empty set、null set)と呼び、で表す。

記法と演算[編集]

外延的記法と内包的記法[編集]

集合をあらわすには、その集合に属している元をすべて書き表すのが最も簡単だ。例えば「1桁の素数」という集合なら

と書ける。このような書き方を外延的記法という。

しかし、集合の元の数が多くなってくると外延的記法は難しくなってくる。例えば、人口500万人未満の都道府県は38個もあるので全部列挙していたら大変だ。それどころか、正の奇数すべての集合の元は無限個あるので、全部書き表すことは不可能で、{1,3,5,7,...}と書くしかない。しかし、このような書き方は、どのような集合なのか誤解を招きやすい。ある人は、「奇数の素数と1」という集合{1,3,5,7,11,13,17,...}の意味でこのように書くかもしれない。

そこで、ある集合の元が満たすべき性質を書くことで集合をあらわすことを考える。そのような記法を内包的記法という。内包的記法では、集合の元を代表する文字と満たすべき条件を縦棒を挟んで並べて書く。例えば、正の奇数の集合は

と書ける。

部分集合[編集]

集合Sのすべての元が集合Tに属しているとき、SはTの部分集合 (subset)であるといい、と表す。空集合は任意の集合の部分集合である。また、S自身もSの部分集合である。S自身以外の部分集合をSの真部分集合といい、TがSの真部分集合であることをとあらわす。

元が集合に属しているという関係と、元がひとつだけの集合が別の集合の部分集合であるという関係とは似て非なるものである。すなわち、とは、同値ではあるが表していることは異なる。この違いにはよく注意すべきである。

かつを満たすときと書き、この2つの集合は等しいという。何をくだらないことを定義するのか、と思ってはいけない。数学ではしばしばまったく別の方法で定義した2つの集合X,Yが実は同じ集合であることを証明すべきときがある。そのようなときには、かつを示せばよいのである。

冪集合

集合があるとき、その集合の部分集合の集合というものを考えることができる。これをその集合の冪(べき)集合という。きちんと集合の記法で書けば、

のことを、Xの冪集合という。

この例を見てもわかるように、有限個の元から成る集合(厳密な定義は後の節を参照)Xの冪集合の元の個数は、Xの元の個数の2の冪である(この例でいえば、23=8個)ので、のことをと書くこともある。またとも書かれる。

集合算[編集]

集合と集合の元をあわせた集合和集合(sum)ないしは合併(union)といい、と表す。例えば、である。

集合から集合の元を除いた集合差集合(difference set)といい、またはと表す。例えば、である。

集合と集合の共通する元の集合積集合(intersection)ないしは共通部分(meet)といい、と表す。例えば、である。

これらに関しては、次の性質(ド・モルガンの法則)が成り立つ。SとTをXの部分集合とすると、

また、次の性質(吸収法則)もよく知られている。

集合と集合の元の組の集合直積(direct product)といい、と表す。例えば、である。

写像[編集]

我々は、関数という概念を既に知っている。fが関数(function)であるとは、xという数に対して別の数f(x)がただひとつ定まることであった。ここでは、関数の概念を一般化した写像という概念を考える。すなわち、集合XとYについて、任意のに対してがただひとつ定まるとき、この対応fはXからYへの写像 (mapping)であるといい、

と書くことにする。2つの写像について、

と定める。

2つの写像があるとき、写像が定まる。これをfとgの合成 (composite)といい、と書く。

像と逆像[編集]

写像とXの部分集合Sがあるとき、Yの部分集合をfによるSの (image)といい、と書く。

写像とYの部分集合Tがあるとき、Xの部分集合をfによるTの逆像 (inverse image)といい、と書く。

特にのときにはを単にと書くこともしばしばある。しかし、この記号は少し紛らわしいので注意すべきである。はどちらも集合であるのに対して、は集合の元だがは集合である。

単射と全射[編集]

写像(対偶を取れば、)を満たすとき、fは単射 (injection)であるという。また、を満たすとき、fは全射 (surjection)であるという。全射かつ単射であることを全単射 (bijection)であるという。

 集合Xと部分集合Sが与えられているとする。このとき、をi(x)=xで定めると、これは単射である。このiを包含写像という。特にS=Xのとき、iは全単射である。このとき恒等写像 (identity mapping)と呼び、特にと書く。

特に空集合は任意の集合の部分集合なので、空集合からは任意の集合へ包含写像を考えることができる(実質的には何も定めていない写像だが、集合論的に考えることはできる、ということである)。これを特に空写像という。

逆写像[編集]

写像があって、かつを満たすとき、gはfの逆写像 (inverse mapping)であるといい、と書く。

命題 写像に逆写像が存在することと、写像fが全単射であることは同値である。

(証明)fに逆写像が存在するとは、Yの任意の要素yに対してただ一つのXの元xが存在してを満たすことであり、これはfが全単射であることにほかならない。//

この命題があるため、写像が全単射であることを証明するために、全射かつ単射であることを示すより、具体的に逆写像を構成してしまったほうが簡単な場合がしばしばある。

より細かくみると、次が成り立つ。

命題*[1] Xが空集合でないとき、写像が単射であることは、を満たす写像fの左逆写像、またはレトラクトという)が存在することと同値である。また、写像が全射であることは、を満たす写像fの右逆写像、またはセクションという)が存在することと同値である。

(証明)
(単射性)fが単射のとき、に対してを満たすxが存在すれば(ただ一つなので)そのxとし、を満たすxが存在しなければ適当なXの元とすることで写像rが定まり、このrを満たす。
逆に、fに左逆写像rが存在するとき、ならばであり、すなわちなので、fは単射であることがわかる。
(全射性)fが全射のとき、を任意にとるとを満たすxが存在するのでその中から適当に一つを選び(ここで選択公理を用いる)それをとすることで写像sが定まり、このsを満たす。
逆に、fに右逆写像sが存在するとき、任意のに対しを満たすXの元であるから、fは全射であることがわかる。//

普遍性[編集]

単射・全射については以下の命題も成り立つ。

命題 写像が単射で、を満たすとき、

(証明)
を任意にとると、であり、gが単射なので、である。よってである。

命題 写像が全射で、を満たすとき、

(証明)
を任意にとると、fが全射なので、なるがある。なので、である。よって、である。

これらの命題は、単射や全射という概念を、集合の元という概念を用いずに特徴づけているという点で重要な命題である。

写像の制限[編集]

写像と集合があるとき、に対してと定めることで、写像が自然に定まる。このようにして定めた写像をfSへの制限といい、であらわす。

はじめはfはほとんど同じもののように感じるかもしれないが、区別したほうが便利である。たとえば、を考えると、fは全射でも単射でもないが、は単射である。

写像の制限は、包含写像を使って表すことができる。を包含写像とすると、

である。

同値関係と商集合[編集]

同値関係[編集]

「~」が集合A上の二項関係であるとは、任意のについて、a~bであるかまたはそうでないかが必ず定まることである。例えば、実数の集合における「=」「≦」などは二項関係である。さらに、二項関係であって次の3つを満たすもののことを同値関係 (equivalent relation)と呼ぶ。

  1. (反射律)
  2. (対称律)
  3. (推移律)

先ほど挙げた「=」は同値関係であるが、「≦」は対称律を満たさないので同値関係ではない。他に同値関係の例として、自然数の集合上の、ある自然数nで割った余りが等しいという関係「≡(mod n)」などを挙げておく。

商集合[編集]

さて、同値関係が与えられたときに、各について次の集合を考える。

すなわちC(a)とは、同値関係~によってaと同値な元全体の集合である。これを~に関するaの同値類 (equivalent class)と呼ぶ。このように定めると、次の性質が成り立つことが容易にわかる。

証明
  1. なのでよって
    なら なので 同様に
  2. 対偶 を証明する。となる が存在して かつ なので(1)より

この2番目の性質は、同値関係が与えられると、元の集合Aは、互いに交わらない部分集合族によって分割(直和分解)されることを表している。この、Aを分割する部分集合族のことを、Aを同値関係~で割った商集合 (quotient set)といい、A/~と書く。集合の言葉できちんと書くと下のようになる。

商集合は同値関係にある元を同じものとして同一視した集合であると言える。

を三次元ユークリッド空間内の有向線分全体の集合とする。この集合 に同値関係 の方向が同じでかつ長さが等しい で定める。 このとき、商集合は空間ベクトル全体の集合である。

自然な写像[編集]

集合Aと部分集合Sを考えると、SからAへは包含写像という自然な単射を考えることができた。商集合でも、次のような自然な写像を考えることができる。

この写像は明らかに全射である。この写像のことを、標準的全射とか、自然な全射という。

以下の命題が成り立つ。

命題 集合上の同値関係と写像について、次の3条件は同値である。

  1. を満たす写像がただひとつ存在する。
  2. とするとき、ならばである。
  3. とするとき、写像の集合への制限は定数写像である。
(証明)
) のとき、なので、である。
) に対して、であるから、である。
) が定数写像なので、その像をとし、を、と定める。このとき、確かにが成り立つ。このような写像がただひとつであることはが全射であることから従う。//

集合族[編集]

に対して集合が対応するとき、集合たちすべてを元とする集合を考えることができる。これをと表し、を添え字とする集合族という。このとき、添字集合といい、の添字という。 に対しであるとき、集合族部分集合族であるという。

用語[編集]

集合族を構成するすべての集合の合併をとった集合和集合といい、と表す。特にのとき、集合族の和集合をと表し、直和という。

集合族を構成するすべての集合に含まれている元の集合共通部分といい、と表す。

集合族を構成するすべての集合の直積をとった集合直積といい、と表す。直積を定義域とする写像を第-成分への射影という。

濃度[編集]

濃度の概念[編集]

この節では、集合の元の個数について考える。いま、素朴に「個数」と書いたが、この概念は自明な概念ではない。確かに、という集合の元の個数は3個である、といったことは、素朴に考えてもすぐに言うことができる。しかし、では元が「無限個」ある場合はどうしたらよいのだろうか?これは案外難しい。

そこで、個数という概念を直接定義するのではなく、2つの集合の元の個数がひとしいとはどういうことなのか、ということをまず定義することにしたい。これはそれほど難しくない。以下のようにすればよい。

定義 2つの集合AとBの間に全単射があるとき、AとBは対等であるという。

元が有限個の場合に、これまでの素朴な「個数がひとしい」という概念と一致していることは容易にわかる。

さて、この集合と集合が対等であるという関係は、同値関係である。そこで、この同値関係によるAの同値類を と書き、これをAの濃度 (cardinality)という。2つの集合が対等であるということを、2つの集合の濃度がひとしいという言葉で言い換えただけである。これによって、任意の集合に適用できる「個数」にあたる概念を手に入れることができた。もちろん(くどいかもしれないが)この濃度の概念は有限集合の場合は素朴な「個数」の概念と一致する。

Bernsteinの定理[編集]

2つの集合があったとき、その2つの集合の濃度がひとしいか否かというのはしばしば気になることである。しかし、2つの集合の濃度がひとしいということを示すには、今のところは全単射を具体的に構成するしかなく、これはしばしば大変なこともある。例えば、閉区間[0,1]ととは濃度がひとしいのだが、全単射を具体的に作るのは容易ではない。

そこで役に立つのが、次に挙げる定理である。

定理(Bernstein)
集合AとBがあり、AからBへの単射と、BからAへの単射があるとき、

card A=card B

AからBへの単射があることと、BからAへの全射があることは同値であるから、定理のステートメントの「単射」をすべて「全射」と書き換えても構わない。

この定理を用いて、自然数の集合と、有理数の集合が対等であることを示してみよう。からへは自明な単射が存在するから、逆向きの単射を作ればよい。からへの単射は容易に作れるので、結局からへの単射を作ればよい。に対してと定めると、これはへの単射である。したがって、これらを合成するとからへの単射が構成でき、Bernsteinの定理よりは対等である。

 Bernsteinの定理を用いて、閉区間[0,1]とは濃度が等しいことを証明せよ。

有限集合・可算集合・非可算集合[編集]

これまで「有限」という言葉をナイーブに未定義のままで使ってきたが、ここできちんと定義しておく。

定義 とする。特にとする。集合Aが有限集合(finite set)であるとは、ある自然数nに対してAとが対等であることである。

これまでナイーブに想像していた概念と一致することを確認してほしい。有限集合でない集合のことを無限集合(infinite set)という。

有限集合であるための同値な条件はこのほかにもあるが、ここではひとつ挙げておく。

命題*[1] 集合Aが有限集合であることは、Aと対等なAの真部分集合が存在しないことと同値。

たとえば、偶数の集合は整数の集合の真部分集合だが、これらは対等である。有限集合ではこのようなことは起きない。

無限集合の中でも、特にと対等な集合は特別視して、可算集合(countable set)という(可算無限集合ということもあるが、重言である)。先ほどの議論から、は可算集合である。有限集合と可算集合を合わせて高々可算な集合といい、高々可算でない集合のことを非可算集合という。

なぜ無限集合の中で可算集合を特別視するかというと、可算集合は「最も小さい」無限集合だからである。すなわち、

命題*[1] 任意の無限集合Aは、可算な部分集合を持つ。

つまり、非可算集合とは、自然数の集合よりも大きい集合のことである。

次の命題とその証明は非常によく知られている。

命題 は非可算集合である。

(証明)
全射が存在したとすると、(の小数部分)と定めることで、全射を作ることができる。したがって、任意の写像が全射でないことを示せば十分である。

の小数第n桁目をと定める。(ただし、小数による実数の表示は一意ではないので、ここでは同じ実数について無限に9が続く表示と無限に0が続く表示がある場合は後者を採用することにする。)このとき、数列

と定め、cを、整数部分が0で、小数第n桁目がであるような実数とする。すると、明らかにcはfの値域に入っていない。よって、fは全射ではない。//

この有名な議論を、Cantorの対角線論法という。

脚注[編集]

  1. ^ 1.0 1.1 1.2 *」を付した命題は、選択公理のもとで成り立つ命題である。このページでは公理的集合論には深く立ち入らないが、気になる読者のために軽く述べておくと、現代的な集合論は集合を「ものの集まり」といった漠然とした形で定義せず、いくつかの公理を満たすものとして定義している。これを公理的集合論という。この公理は当然直感的に「成り立ちそう」な公理を集めているのだが、その中にある選択公理という公理は「怪しい」結果を招くことから歴史的に他の公理群と区別されてきた。そのため、選択公理を含まない公理系でも成り立つ命題なのか、選択公理を含む公理系でしか成り立たない命題なのかは、このように区別することがしばしばある。