集合論のソースを表示

[[数学]]＞集合論

このページでは、[[高等学校数学I/集合と論理]]、[[高等学校数学A/場合の数と確率]]に登場した集合について深く論じていく。

「数学基礎論」という分野に分類されていることから分かるように、大学以上の数学において基礎中の基礎となる非常な重要な概念を取り扱う。


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

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

なお、元が1つもない集合も集合とみなすことにする。そのような集合を'''空集合''' （empty set、null set）と呼び、<math>\varnothing</math>で表す。

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

<math> \{ 2,3,5,7\}</math>

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

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

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

<math> \{ x \mid x=2n-1 , n \in \mathbb{N}\}</math>

と書ける。

=== 部分集合 ===
集合Sのすべての元が集合Tに属しているとき、SはTの'''部分集合''' （subset）であるといい、<math>S \subset T</math>と表す。空集合は任意の集合の部分集合である。また、S自身もSの部分集合である。S自身以外の部分集合をSの'''真部分集合'''といい、TがSの真部分集合であることを<math>T \subsetneq S</math>とあらわす。

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

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

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

:<math>\mathcal{P}(X) = \{ S \mid S \subset X \} </math>

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

; 例
<math>\mathcal{P}(\{ 1,2,3 \} ) = \{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}</math>

この例を見てもわかるように、有限個の元から成る集合（厳密な定義は後の節を参照）Xの冪集合<math>\mathcal{P}(X)</math>の元の個数は、Xの元の個数の2の冪である（この例でいえば、2<sup>3</sup>=8個）ので、<math>\mathcal{P}(X)</math>のことを<math>2^X</math>と書くこともある。また<math>\mathfrak{P}(X)</math>とも書かれる。

=== 集合算 ===
集合<math>S</math>と集合<math>T</math>の元をあわせた集合<math>\{ x \mid x \in S \lor x \in T \}</math>を'''和集合'''（sum）ないしは'''合併'''（union）といい、<math>S \cup T</math>と表す。例えば、<math>\{1,2,3\} \cup \{3,4,5\} = \{1,2,3,4,5\}</math>である。

集合<math>S</math>から集合<math>T</math>の元を除いた集合<math>\{ x \mid x \in S \land x \notin T \}</math>を'''差集合'''（difference set）といい、<math>S - T</math>または<math>S \setminus T</math>と表す。例えば、<math>\{1,2,3\} \setminus \{3,4,5\} = \{1,2\}</math>である。

集合<math>S</math>と集合<math>T</math>の共通する元の集合<math>\{ x \mid x\in S \land x \in T \}</math>を'''積集合'''（intersection）ないしは'''共通部分'''（meet）といい、<math>S \cap T</math>と表す。例えば、<math>\{1,2,3\} \cap \{3,4,5\} = \{3\}</math>である。

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

:<math>X \setminus (S \cap T) = (X \setminus S) \cup (X \setminus T) </math>

:<math>X \setminus (S \cup T) = (X \setminus S) \cap (X \setminus T) </math>

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

:<math>(S \cap T) \cup S = S</math>

:<math>(S \cup T) \cap S = S</math>

集合<math>S</math>と集合<math>T</math>の元の組の集合<math>\{ (x,y) \mid x \in S \land y \in T \}</math>を'''直積'''（direct product）といい、<math>S \times T</math>と表す。例えば、<math>\{ 1,2 \} \times \{ 3,4 \} = \{ (1,3),(1,4),(2,3),(2,4) \}</math>である。

== 写像 ==
我々は、関数という概念を既に知っている。fが関数（function）であるとは、xという数に対して別の数f(x)がただひとつ定まることであった。ここでは、関数の概念を一般化した写像という概念を考える。すなわち、集合XとYについて、任意の<math>x \in X</math>に対して<math>f(x) \in Y</math>がただひとつ定まるとき、この対応fはXからYへの'''写像''' （mapping）であるといい、
:<math>f \colon X \to Y , x \mapsto f(x)</math>
と書くことにする。2つの写像<math>f_1,f_2 \colon X \to Y</math>について、
:<math>f_1=f_2 \Leftrightarrow \forall x \in X \ f_1(x)=f_2(x)</math>
と定める。

2つの写像<math>f \colon X \to Y</math>と<math>g \colon Y \to Z</math>があるとき、写像<math>h \colon X \to Z , x \mapsto g(f(x))</math>が定まる。これをfとgの'''合成''' （composite）といい、<math>g \circ f</math>と書く。

=== 像と逆像 ===
写像<math>f \colon X \to Y</math>とXの部分集合Sがあるとき、Yの部分集合<math>\{ f(x) \mid x \in S \}</math>をfによるSの'''像''' （image）といい、<math>f(S)</math>と書く。

写像<math>f:X \to Y</math>とYの部分集合Tがあるとき、Xの部分集合<math>\{ x \mid f(x) \in T \}</math>をfによるTの'''逆像''' （inverse image）といい、<math>f^{-1}(T)</math>と書く。

特に<math>T= \{ y \}</math>のときには<math>f^{-1}( \{ y \} )</math>を単に<math>f^{-1} (y)</math>と書くこともしばしばある。しかし、この記号は少し紛らわしいので注意すべきである。<math>f(S)</math>と<math>f^{-1}(T)</math>はどちらも集合であるのに対して、<math>f(x)</math>は集合の元だが<math>f^{-1}(y)</math>は集合である。

=== 単射と全射 ===
写像<math>f \colon X \to Y</math>が<math>f(x)=f(x') \Rightarrow x=x'</math>(対偶を取れば、<math>x \neq x' \Rightarrow f(x) \neq f(x')</math>)を満たすとき、fは'''単射''' （injection）であるという。また、<math>f(X)=Y</math>を満たすとき、fは'''全射''' （surjection）であるという。全射かつ単射であることを'''全単射''' （bijection）であるという。
<gallery>
file:Surjection.svg|全射であり単射でない
file:Injection.svg|単射であり全射でない
file:Bijection.svg|全単射
file:Total function.svg|全射でも単射でもない
</gallery>

'''例'''　集合Xと部分集合Sが与えられているとする。このとき、<math>i \colon S \to X</math>を<math>i(x)=x</math>で定めると、これは単射である。このiを'''包含写像'''という。特にS=Xのとき、iは全単射である。このとき'''恒等写像''' （identity mapping）と呼び、特に<math>\mathrm{id}_X</math>と書く。

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

==== 逆写像 ====
写像<math>f \colon X \to Y</math>と<math>g \colon Y \to X</math>があって、<math>g \circ f =\mathrm{id}_X</math>かつ<math>f \circ g =\mathrm{id}_Y</math>を満たすとき、gはfの'''逆写像''' （inverse mapping）であるといい、<math>f^{-1}</math>と書く。

'''命題'''　写像<math>f \colon X \to Y</math>に逆写像が存在することと、写像''f''が全単射であることは同値である。
:（証明）''f''に逆写像<math>f^{-1}</math>が存在するとは、''Y''の任意の要素''y''に対してただ一つの''X''の元''x''が存在して<math>y=f(x)</math>を満たすことであり、これは''f''が全単射であることにほかならない。//

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

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

'''命題'''<sup>*</sup><ref name="AC" />　''X''が空集合でないとき、写像<math>f \colon X \to Y</math>が単射であることは、<math>r \circ f=\mathrm{id}_X</math>を満たす写像<math>r \colon Y \to X</math>（''f''の左逆写像、またはレトラクトという）が存在することと同値である。また、写像<math>f \colon X \to Y</math>が全射であることは、<math>f \circ s=\mathrm{id}_Y</math>を満たす写像<math>s \colon Y \to X</math>（''f''の右逆写像、またはセクションという）が存在することと同値である。
:（証明）
:（単射性）''f''が単射のとき、<math>y \in Y</math>に対して<math>y=f(x)</math>を満たす''x''が存在すれば（ただ一つなので）その''x''を<math>r(y)</math>とし、<math>y=f(x)</math>を満たす''x''が存在しなければ適当な''X''の元<math>x_0</math>を<math>r(y)</math>とすることで写像''r''が定まり、この''r''は<math>r \circ f=\mathrm{id}_X</math>を満たす。
:逆に、''f''に左逆写像''r''が存在するとき、<math>f(x)=f(x')</math>ならば<math>r(f(x))=r(f(x'))</math>であり、すなわち<math>x=x'</math>なので、''f''は単射であることがわかる。
:（全射性）''f''が全射のとき、<math>y \in Y</math>を任意にとると<math>y=f(x)</math>を満たす''x''が存在するのでその中から適当に一つを選び（ここで選択公理を用いる）それを<math>s(y)</math>とすることで写像''s''が定まり、この''s''は<math>f \circ s=\mathrm{id}_Y</math>を満たす。
:逆に、''f''に右逆写像''s''が存在するとき、任意の<math>y \in Y</math>に対し<math>s(y) \in X</math>は<math>f(s(y))=y</math>を満たす''X''の元であるから、''f''は全射であることがわかる。//

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

'''命題'''
写像<math>g \colon Y \to Z</math>が単射で、<math>f_1,f_2 \colon X \to Y</math>が<math>g \circ f_1=g \circ f_2</math>を満たすとき、<math>f_1=f_2</math>
:（証明）<br /><math>x \in X</math>を任意にとると、<math>g(f_1(x))=g(f_2(x))</math>であり、''g''が単射なので、<math>f_1(x)=f_2(x)</math>である。よって<math>f_1=f_2</math>である。

'''命題'''
写像<math>f \colon X \to Y</math>が全射で、<math>g_1,g_2 \colon Y \to Z</math>が<math>g_1 \circ f=g_2 \circ f</math>を満たすとき、<math>g_1=g_2</math>
:（証明）<br /><math>y \in Y</math>を任意にとると、''f''が全射なので、<math>f(x)=y</math>なる<math>x \in X</math>がある。<math>g_1(f(x))=g_2(f(x))</math>なので、<math>g_1(y)=g_2(y)</math>である。よって、<math>g_1=g_2</math>である。

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

=== 写像の制限 ===
写像<math>f \colon X \to Y</math>と集合<math>S \subset X</math>があるとき、<math>x \in S</math>に対して<math>x \mapsto f(x)</math>と定めることで、写像<math>S \to Y</math>が自然に定まる。このようにして定めた写像を''f''の''S''への'''制限'''といい、<math>f|_S</math>であらわす。

はじめは''f''と<math>f|_S</math>はほとんど同じもののように感じるかもしれないが、区別したほうが便利である。たとえば、<math>f:\mathbb{R} \to \mathbb{R},x \mapsto x^2</math>と<math>S=\{ x \in \mathbb{R} \mid x \ge 0 \} \subset \mathbb{R}</math>を考えると、''f''は全射でも単射でもないが、<math>f|_S</math>は単射である。

写像の制限は、包含写像を使って表すことができる。<math>i \colon S \to X</math>を包含写像とすると、
:<math>f|_S=f \circ i</math>
である。

== 同値関係と商集合 ==
=== 同値関係 ===
「～」が集合A上の二項関係であるとは、任意の<math>a,b \in A</math>について、a～bであるかまたはそうでないかが必ず定まることである。例えば、実数の集合における「＝」「≦」などは二項関係である。さらに、二項関係であって次の3つを満たすもののことを'''同値関係''' （equivalent relation）と呼ぶ。
# <math>a \in A \Rightarrow a \sim a</math>（反射律）
# <math>a \sim b \Rightarrow b \sim a</math>（対称律）
# <math>a \sim b , b \sim c \Rightarrow a \sim c</math>（推移律）
先ほど挙げた「＝」は同値関係であるが、「≦」は対称律を満たさないので同値関係ではない。他に同値関係の例として、自然数の集合上の、ある自然数nで割った余りが等しいという関係「≡(mod n)」などを挙げておく。

=== 商集合 ===
さて、同値関係が与えられたときに、各<math>a \in A</math>について次の集合を考える。

<math>C(a)= \{ x \in A \mid x \sim a \}</math>

すなわちC(a)とは、同値関係～によってaと同値な元全体の集合である。これを～に関するaの'''同値類''' （equivalent class）と呼ぶ。このように定めると、次の性質が成り立つことが容易にわかる。
# <math> C(a)=C(b) \Leftrightarrow a \sim b</math>
# <math> C(a) \neq C(b) \Rightarrow C(a) \cap C(b) = \varnothing</math>
;証明
# <math>\Rightarrow :</math> <math>a \in C(a)</math>なので<math>a \in C(b)</math>よって<math>a \sim b</math>
#:<math> \Leftarrow :</math><math>x \sim a </math> なら <math>x \sim b</math> なので <math>C(a) \subset C(b)</math> 同様に <math> C(b) \subset C(a)</math>
# 対偶 <math> C(a) \cap C(b) \neq \varnothing \Rightarrow C(a) = C(b)</math>を証明する。<math> x\in C(a) \cap C(b)</math>となる<math>x \in A</math> が存在して <math> x \sim a</math> かつ <math> x \sim b</math> なので(1)より <math> C(x) = C(a), C(x) = C(b)</math>
この2番目の性質は、同値関係が与えられると、元の集合Aは、互いに交わらない部分集合族によって分割（直和分解）されることを表している。この、Aを分割する部分集合族のことを、Aを同値関係～で割った'''商集合''' （quotient set）といい、A/～と書く。集合の言葉できちんと書くと下のようになる。

<math> A/ \sim = \{ C(a) \mid a \in A \} </math>

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

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

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

<math>\pi \colon A \to A/\sim , x \mapsto C(x)</math>

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

以下の命題が成り立つ。

'''命題'''　集合<math>A</math>上の同値関係<math>\sim</math>と写像<math>f \colon A \to B</math>について、次の3条件は同値である。
# <math>f=g \circ \pi</math>を満たす写像<math>g \colon A/\sim \to B</math>がただひとつ存在する。
# <math>a,a' \in A</math>とするとき、<math>a \sim a'</math>ならば<math>f(a)=f(a')</math>である。
# <math>a \in A</math>とするとき、写像<math>f</math>の集合<math>C(a) \subset A</math>への制限<math>f|_{C(a)}:C(a) \to B</math>は定数写像である。
:（証明）
:（<math>1.\Rightarrow 2.</math>）　<math>a \sim a'</math>のとき、<math>\pi(a)=\pi(a')</math>なので、<math>f(a)=g(\pi(a))=g(\pi(a'))=f(a')</math>である。
:（<math>2.\Rightarrow 3.</math>）　<math>a' \in C(a)</math>に対して、<math>a \sim a'</math>であるから、<math>f(a')=f(a)</math>である。
:（<math>3.\Rightarrow 1.</math>）　<math>f|_{C(a)}</math>が定数写像なので、その像を<math>b</math>とし、<math>g \colon A/\sim \to B</math>を、<math>g(C(a))=b</math>と定める。このとき、確かに<math>f=g \circ \pi</math>が成り立つ。このような写像がただひとつであることは<math>\pi</math>が全射であることから従う。//

==集合族==
<math>\forall \lambda \in \Lambda</math>に対して集合<math>A_{\lambda}</math>が対応するとき、集合<math>A_{\lambda}</math>たちすべてを元とする集合を考えることができる。これを<math>\{ A_{\lambda} \}_{\lambda \in \Lambda}</math>と表し、<math>\Lambda</math>を添え字とする'''集合族'''という。このとき、<math>\Lambda</math>を'''添字集合'''といい、<math>\lambda</math>を<math>A_{\lambda}</math>の添字という。
<math>\forall \lambda \in \Lambda</math>に対し<math>A_{\lambda} \subset X</math>であるとき、集合族<math>\{ A_{\lambda} \}_{\lambda \in \Lambda}</math>は<math>X</math>の'''部分集合族'''であるという。

=== 用語 ===
集合族<math>\{ A_{\lambda} \}_{\lambda \in \Lambda}</math>を構成するすべての集合<math>A_{\lambda}</math>の合併をとった集合<math>\{ x \mid \exists \lambda \in \Lambda , x \in A_{\lambda} \}</math>を'''和集合'''といい、<math>\bigcup_{\lambda \in \Lambda} A_{\lambda}</math>と表す。特に<math>i,j \in \Lambda, i \ne j \Rightarrow A_i \cap A_j = \varnothing</math>のとき、集合族<math>\{ A_{\lambda} \}_{\lambda \in \Lambda}</math>の和集合を<math>\coprod_{\lambda \in \Lambda} A_{\lambda}</math>と表し、'''直和'''という。

集合族<math>\{ A_{\lambda} \}_{\lambda \in \Lambda}</math>を構成するすべての集合に含まれている元の集合<math>\{ x | \forall \lambda \in \Lambda , x \in A_{\lambda} \}</math>を'''共通部分'''といい、<math>\bigcap_{\lambda \in \Lambda} A_{\lambda}</math>と表す。

集合族<math>\{ A_{\lambda} \}_{\lambda \in \Lambda}</math>を構成するすべての集合の直積をとった集合<math>\{ \{ a_{\lambda} \}_{\lambda \in \Lambda} | \forall \lambda \in \Lambda , a_{\lambda} \in A_{\lambda} \}</math>を'''直積'''といい、<math>\prod_{\lambda \in \Lambda} A_{\lambda}</math>と表す。直積<math>\prod_{\lambda \in \Lambda} A_{\lambda}</math>を定義域とする写像<math>\pi_\mu : \prod_{\lambda \in \Lambda} A_{\lambda} \to A_\mu ; \{ a_{\lambda} \}_{\lambda \in \Lambda} \mapsto a_\mu</math>を第<math>\mu</math>-成分への'''射影'''という。

== 濃度 ==
=== 濃度の概念 ===
この節では、集合の元の個数について考える。いま、素朴に「個数」と書いたが、この概念は自明な概念ではない。確かに、<math> \{ 1,2,3 \}</math>という集合の元の個数は3個である、といったことは、素朴に考えてもすぐに言うことができる。しかし、では元が「無限個」ある場合はどうしたらよいのだろうか？これは案外難しい。

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

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

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

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

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

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

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

card A=card B

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

この定理を用いて、自然数の集合<math>\mathbb{N}</math>と、有理数の集合<math>\mathbb{Q}</math>が対等であることを示してみよう。<math>\mathbb{N}</math>から<math>\mathbb{Q}</math>へは自明な単射が存在するから、逆向きの単射を作ればよい。<math>\mathbb{Q}</math>から<math>\mathbb{N} \times \mathbb{N}</math>への単射は容易に作れるので、結局<math>\mathbb{N} \times \mathbb{N}</math>から<math>\mathbb{N}</math>への単射を作ればよい。<math>(a,b) \in \mathbb{N} \times \mathbb{N}</math>に対して<math>f((a,b))=2^{a-1}(2b-1)</math>と定めると、これは<math>\mathbb{N}</math>への単射である。したがって、これらを合成すると<math>\mathbb{Q}</math>から<math>\mathbb{N}</math>への単射が構成でき、Bernsteinの定理より<math>\mathbb{N}</math>と<math>\mathbb{Q}</math>は対等である。

'''問'''　Bernsteinの定理を用いて、閉区間[0,1]と<math>\mathbb{R}</math>は濃度が等しいことを証明せよ。

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

'''定義'''　<math>[n]=\{1,2,...,n\}</math>とする。特に<math>[0]=\varnothing</math>とする。集合Aが有限集合（finite set）であるとは、ある自然数nに対してAと<math>[n]</math>が対等であることである。

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

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

'''命題<sup>*</sup><ref name="AC">「<sup>*</sup>」を付した命題は、選択公理のもとで成り立つ命題である。このページでは[[公理的集合論]]には深く立ち入らないが、気になる読者のために軽く述べておくと、現代的な集合論は集合を「ものの集まり」といった漠然とした形で定義せず、いくつかの公理を満たすものとして定義している。これを公理的集合論という。この公理は当然直感的に「成り立ちそう」な公理を集めているのだが、その中にある選択公理という公理は「怪しい」結果を招くことから歴史的に他の公理群と区別されてきた。そのため、選択公理を含まない公理系でも成り立つ命題なのか、選択公理を含む公理系でしか成り立たない命題なのかは、このように区別することがしばしばある。</ref>'''　集合Aが有限集合であることは、Aと対等なAの真部分集合が存在しないことと同値。

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

無限集合の中でも、特に<math>\mathbb{N}</math>と対等な集合は特別視して、可算集合（countable set）という（可算無限集合ということもあるが、重言である）。先ほどの議論から、<math>\mathbb{Q}</math>は可算集合である。有限集合と可算集合を合わせて高々可算な集合といい、高々可算でない集合のことを非可算集合という。

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

'''命題<sup>*</sup><ref name="AC" />'''　任意の無限集合Aは、可算な部分集合を持つ。

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

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

'''命題'''　<math>\mathbb{R}</math>は非可算集合である。

（証明）<br />
全射<math>p:\mathbb{N} \to \mathbb{R}</math>が存在したとすると、<math>n \mapsto </math>(<math>p(n)</math>の小数部分)と定めることで、全射<math>f:\mathbb{N} \to (0,1)</math>を作ることができる。したがって、任意の写像<math>f:\mathbb{N} \to (0,1)</math>が全射でないことを示せば十分である。

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

:<math>b_n=\begin{cases}0 & if \ a_n=1 \\ 1 & if \ a_n \ne 1\end{cases}</math> 

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

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

== 脚注 ==
<references/>

[[Category:数学]]