可算集合

可算性は、いわば集合の大きさにあたる考え方です。無限集合では要素の個数を数えられません。要素の個数は、意外なことに…無限だからです。集合の大きさは、濃度ともいいます。

無限集合の大きさ

有限集合の大きさを決めるのは簡単で、要素の個数を数えればよいのです。たとえば、集合 M = {a, b, c, d, e} の大きさは5で、|M| = 5 と書きます。

無限集合では、ずっと難しくなります。無限集合の大きさは、どうすれば比べられるでしょうか。そもそも比べられるのでしょうか。それとも、無限集合はどれも「同じ大きさ」なのでしょうか。

例として、自然数の集合と、偶数の自然数の集合を考えます。集合 ℕ = {1, 2, 3, 4, 5, 6, …} と S = {2, 4, 6, …} です。自然数の集合のほうが偶数の集合より大きい、と言いたくなります。自然数はすべての偶数を含み、そのうえ奇数という要素も含んでいるからです。

つまり、S ⊂ ℕ と書けます。集合 S は集合 ℕ の真部分集合です（S は N と一致しません）。さらに、S ⊂ ℕ なら集合 ℕ のほうが大きい、ともいえそうです。なにしろ、集合 S より多くの要素を含んでいるのですから。

集合の大きさを部分集合の関係ではかれない理由の1つは、どちらの集合も他方の部分集合でなくても、集合の大きさがちがうことがあるからです。これは有限集合でも示せます。A = {1, 3, 4, 9} と B = {b, u, r, z, m} を考えます。|A| = 4、|B| = 5 です。集合 B は集合 A より大きいのに、A ⊂ B は成り立ちません。無限集合なら、偶数と奇数の集合がその例です。どちらの集合も他方の部分集合ではありません。

したがって、部分集合の関係は、一方の集合が他方より大きいかどうかを決めるのにはあまり向いていません。

全単射

別の方法を考えてみましょう。2つの集合 A と B があるとします。2つの集合の間に全単射（1対1の対応）があるとき、2つの集合は同じ大きさだといえます。これはどういうことでしょうか。集合 A から要素を1つ、集合 B から要素を1つとって、組 (a, b) をつくります。これらの要素を集合からとりのぞき、同じことを続けます。両方の集合を「空」にできたら、全単射が見つかったことになります。

有限集合の例です。A = {a, b, c}、B = {1, 2, 3} とします。1つ目の組は (a, 1)、次は (b, 2)、最後に (c, 3) とできます。両方の集合の要素をすべて使いきったので、全単射が見つかりました。大切なのは、全単射はこれだけではないのです。(a, 3), (b, 1), (c, 2) も正しい答えです。

無限集合では、少しおもしろくなります。奇数の自然数と偶数の自然数で試してみましょう。直感的には、同じだけあるはずです。やってみます。最初の奇数を最初の偶数に対応させて、(1, 2) とします。次に、2番目の奇数と2番目の偶数で (3, 4) です。以下同じように続けます。すると、組 (1, 2), (3, 4), (5, 6), (7, 8), … が得られます。どの奇数 l も偶数 l + 1 に対応し、どの偶数 s も奇数 s − 1 に対応している、と書けます。つまり、どの奇数にもどの偶数にも、その数を含む組があります。したがって、奇数の集合と偶数の集合は同じ大きさです。

偶数と自然数

今度は同じ方法で、自然数の集合と偶数の集合を比べてみましょう。集合 ℕ = {1, 2, 3, 4, 5, 6, …} と S = {2, 4, 6, …} です。直感的には、自然数の集合のほうが大きいと思えます。

では、全単射を探してみましょう。どの自然数 n も、その2倍の 2n に対応させることにします。すると、組 (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … が得られます。どの自然数 n にも組 (n, 2n) があり、どの偶数 s にも組 (s/2, s) があります。全単射が見つかったので、偶数の集合と自然数の集合は同じ大きさ、つまり同じ濃度をもちます。

これは納得しにくいかもしれません。自然数のほうが偶数より多くの要素を含んでいるはずだからです。自然数はすべての偶数を含み、そのうえすべての奇数も含んでいます。それでも全単射が見つかるので、2つの集合は同じ大きさなのです。

自然数との比較

じつは、自然数の集合の大きさが、無限集合の大きさとしては最小です。ほかの集合が自然数の集合と同じ大きさかどうかは、多くの場合かなり簡単にわかります。自然数との全単射を見つければよいのです。実際には、集合 M の要素に番号をつけて、順にならべられればよいということです。

つまり、集合の要素を、どれが1番目、どれが2番目、3番目、4番目、10番目…というようにならべられれば、その集合は ℕ と同じ大きさです。このような集合を、可算集合（可付番集合）といいます。

偶数の自然数と奇数の自然数が可算であることは、すぐにわかります。1番目、2番目、3番目…の偶数や奇数を決められるからです。偶数の整数、つまり集合 S = {…, −4, −2, 0, 2, 4, …} はどうでしょうか。ならべられるでしょうか。ならべられます。先ほどと同じならべ方を使い、正の偶数のすぐあとに、その符号を変えた負の数を書けばよいのです。S = {0, 2, −2, 4, −4, 6, −6, …} となります。整数全体なども同じようにならべられます。

有理数の大きさ

もっとおもしろい例は、有理数、つまり分数です。ならべられるでしょうか。ならべられますが、少し複雑になります。行と列が無限にある表をつくります。どのマスにも分数を入れます。n 列目、m 行目のマスには分数 n/m を入れます。つまり、1列目の2行目には $\frac{1}{2}$、3列目の4行目には 3/4 が入ります。

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

では、これらの数をどうならべて、番号をつければよいでしょうか。行ごとや列ごとに番号をつけることはできません。そうすると、すぐにその行や列からぬけ出せなくなってしまうからです。そのかわりに、斜めの線にそって数をとっていきます。（1本目の斜めの線：）1/1、（2本目：）2/1, 1/2、（3本目：）3/1, 2/2, 1/3、（4本目：）4/1, 3/2, 2/3, 1/4、…。同じ値の分数がたくさん重複していますが、問題ありません。それより困るのは、負の数が入っていないことです。これは簡単に解決できます。分数を1つ書くたびに、そのすぐあとに符号を変えた負の分数を書けばよいのです。あとは、いちばん最初に0を加えるだけです。これで、すべての有理数を1列にならべられました。

まとめると、次の数列が得られます。0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

実数の大きさ

実数は自然数と同じ大きさでしょうか。これを決めるのは、有理数の場合よりさらに難しくなります。背理法を使います。実数が可算で、自然数との全単射が存在すると仮定します。つまり、実数をならべられると仮定するのです。そして、次の対応がそのならべ方だとします。

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

表には、このならべ方での最初の7つの実数が書いてあります。ならべ方はもちろん自由で、数の大きさの順になっている必要はありません。

仮定によれば、この無限の表には、すべての実数がならんでいます。（表はやはり無限で、ここには最初の7つだけを書いています。）ここで、実数でありながらこの表にのっていない数を探して（つくって）みます。そのような数が見つかれば、表にすべての実数がのっていることに矛盾し、そこから実数の集合は可算ではないと結論できます。

表にない数は、次のようにつくります。

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

まず、0,… と書きます。新しい実数は、はじめはこのような形です。小数第1位には、ならべ方の1番目の実数の小数第1位とはちがう数字を入れます（表では枠で囲んであります）。そこには数字 3 があるので、たとえば 1 を選んで、0.1… とします。

さらに続けます。小数第2位には、2番目の実数の小数第2位とはちがう数字を入れます。そこには 9 があるので、たとえば 2 にします。0.12… となります。小数第3位には、3番目の実数の小数第3位とはちがう数字を入れます。そこには 3 があるので、たとえば 7 を選びます。0, 127… となります。

以下同じように続けます。新しい数の小数第 n 位には、ならべ方の n 番目の数の小数第 n 位とはちがう数字をいつも入れます。

これで何が得られるでしょうか。ならべ方にあるどの数とも、少なくとも1つの数字がちがう数が得られます。いまの途中の結果 0.127… を考えましょう。この数は、そのようにつくったので、ならべ方の1番目の数とは少なくとも小数第1位がちがいます。2番目の数とは少なくとも小数第2位が、3番目の数とは小数第3位がちがいます。一般に、この新しい数は、ならべ方の n 番目の数と、少なくとも小数第 n 位がちがいます。

したがって、この新しくつくった数は、自然数と実数の全単射を表すはずだった表には見つかりません。つまり、実数は自然数より多いのです。実数は可算ではなく、非可算です。この方法を対角線論法といいます。

参考リンク

• Are there more odd or even numbers?（英語）