高校数学では「無限」を漠然と使います。数列 $1, 2, 3, \ldots$ は「無限に続く」、$\lim_{n \to \infty} a_n = \alpha$ では $n$ が「限りなく大きくなる」と言います。
しかし、「無限」はすべて同じ大きさなのでしょうか。自然数全体の集合と実数全体の集合は、どちらも要素が無限個ですが、同じ「大きさ」でしょうか。
大学数学では、全単射（一対一かつ上への写像）が存在するかどうかで集合の「大きさ」を比較します。
この「大きさ」を濃度と呼びます。
自然数と有理数は全単射で結べるため同じ濃度（可算無限）ですが、実数はそれより真に大きい濃度（非可算無限）を持ちます。
このことを示すのがカントールの対角線論法です。
無限には「大きさ」の階層があるという事実は、19世紀末の数学に革命をもたらしました。
高校の数学Iでは集合を学びます。集合 $A = \{1, 3, 5, 7\}$ の要素数は $4$ 個で、これを $|A| = 4$ と書きます。 有限集合であれば要素を数え上げることで「大きさ」を確定できます。
一方、高校では「無限」という言葉がさまざまな場面で登場します。
これらの場面で「無限」はすべて同じものとして扱われています。 自然数全体も、整数全体も、有理数全体も、実数全体も、すべて「無限個の要素を持つ集合」としてひとまとめにされています。 高校の範囲ではこの扱いで問題は起きません。
しかし、ここで一つの疑問が生じます。自然数は $1, 2, 3, \ldots$ と離散的に並んでいるのに対し、 実数は $0$ と $1$ の間だけでも $0.1, 0.01, 0.001, \ldots$ や $\frac{1}{3}, \sqrt{2} - 1, \frac{\pi}{4}, \ldots$ など、数直線を「隙間なく」埋め尽くしています。 直感的には、実数のほうが自然数より「ずっと多い」ように見えます。 この直感は正しいのでしょうか。そして、そもそも無限集合の「多い」「少ない」をどう定義すればよいのでしょうか。 次のセクションで、大学数学がこの問いにどう答えるかを見ていきます。
大学数学では、集合の「大きさ」を濃度（cardinality）という概念で定義します。 有限集合なら濃度は要素数そのものですが、無限集合の濃度を比較する際に「要素を数える」方法は使えません。 代わりに使うのが全単射（bijection）です。
全単射とは、二つの集合の間の「一対一の対応」のことです。 集合 $A$ と集合 $B$ の間に全単射が存在するとき、$A$ と $B$ は同じ濃度を持つと定義します。 この考え方は、有限集合では当たり前のことを述べています。椅子が5脚あり、人が5人いるとき、全員がちょうど1脚ずつ座れる ── これが全単射です。 大学数学の洞察は、この同じ原理を無限集合にも適用するところにあります。
この記事で示す核心的な事実は以下の3点です。
では、「全単射で比較する」とは具体的にどういうことか、まず有限集合で確認し、そこから無限集合に拡張していきます。
濃度の定義には「全単射」という概念が不可欠です。 ここで、写像に関する基本用語を導入します。 （写像（関数）の厳密な定義は 📖 第6章 M-6-1 で詳しく扱いますが、ここでは濃度の議論に必要な範囲で説明します。）
集合 $A$ から集合 $B$ への写像 $f: A \to B$ とは、$A$ の各要素に $B$ の要素をちょうど1つ対応させるルールのことです。 写像には、次の3つの重要な性質があります。
写像 $f: A \to B$ について：
単射（injection）：異なる要素は異なる先に移る。つまり、$a_1 \neq a_2$ ならば $f(a_1) \neq f(a_2)$
全射（surjection）：$B$ のすべての要素が $f$ の行き先になっている。つまり、任意の $b \in B$ に対して $f(a) = b$ となる $a \in A$ が存在する
全単射（bijection）：単射かつ全射。$A$ と $B$ の要素が過不足なく一対一に対応する
具体例で確認します。$A = \{1, 2, 3\}$, $B = \{a, b, c\}$ として、$f(1) = a$, $f(2) = b$, $f(3) = c$ と定めると、これは全単射です。 異なる要素は異なる先に移り（単射）、$B$ のすべての要素が使われています（全射）。
一方、$g: \{1, 2, 3\} \to \{a, b, c, d\}$ で $g(1) = a$, $g(2) = b$, $g(3) = c$ とすると、$g$ は単射ですが全射ではありません（$d$ に対応する要素がない）。 また、$h: \{1, 2, 3\} \to \{a, b\}$ で $h(1) = a$, $h(2) = b$, $h(3) = a$ とすると、$h$ は全射ですが単射ではありません（$1$ と $3$ が同じ $a$ に移る）。
有限集合 $A$ と $B$ の間に全単射が存在することと、$|A| = |B|$ であることは同値です。 これは直感と一致します。3人と3脚の椅子の間に一対一対応がある、というだけのことです。
ここで注目すべきポイントがあります。有限集合の場合、「全単射がある $\Leftrightarrow$ 要素数が等しい」は当たり前ですが、 全単射を使う定義の良い点は、要素を数えなくても大きさを比較できることです。 極端な例として、巨大な二つの集合の要素数を数えるのは大変でも、一対一対応を1つ見つければ「同じ大きさ」とわかります。
無限集合では要素を数え上げることができません。しかし全単射による比較はそのまま使えます。 これが濃度の定義の強みです。
集合 $A$ と集合 $B$ の濃度が等しい（$|A| = |B|$）とは、$A$ から $B$ への全単射が存在することと定義する。
この定義は有限集合にも無限集合にも適用できます。有限集合の場合は通常の要素数の比較と一致します。
ところが、無限集合に全単射の考え方を適用すると、有限集合では起こらない不思議な現象が生じます。 次のセクションで、その具体例を見ていきます。
まず、無限集合の不思議さを実感する例から始めます。 自然数全体 $\mathbb{N} = \{1, 2, 3, 4, \ldots\}$ と偶数全体 $E = \{2, 4, 6, 8, \ldots\}$ を考えます。 偶数は自然数の「半分」なので、直感的には $E$ のほうが「小さい」集合に思えます。
しかし、写像 $f: \mathbb{N} \to E$ を $f(n) = 2n$ と定めると、これは全単射です。
| $n$（自然数） | $f(n) = 2n$（偶数） |
|---|---|
| $1$ | $2$ |
| $2$ | $4$ |
| $3$ | $6$ |
| $4$ | $8$ |
| $\vdots$ | $\vdots$ |
単射の確認：$n_1 \neq n_2$ なら $2n_1 \neq 2n_2$ なので $f(n_1) \neq f(n_2)$ です。 全射の確認：任意の偶数 $2k \in E$ に対して $f(k) = 2k$ なので、すべての偶数に対応する自然数が存在します。 したがって $|\mathbb{N}| = |E|$ です。
「部分集合なのに全体と同じ大きさ」── これは有限集合では絶対に起こりません。 $\{1, 2, 3\}$ の真部分集合 $\{1, 2\}$ が $\{1, 2, 3\}$ と同じ要素数ということはありえません。 しかし無限集合ではこれが起こるのです。 実は、この性質（自分自身の真部分集合と全単射が存在すること）は、無限集合を特徴づける性質の一つです。
誤った推論：偶数は自然数の一部だから、偶数のほうが少ない
正しい理解：全単射 $f(n) = 2n$ が存在するので、偶数全体と自然数全体は同じ濃度を持つ。有限集合での直感（部分集合は全体より小さい）は無限集合には通用しない
次に、自然数 $\mathbb{N} = \{1, 2, 3, \ldots\}$ と整数 $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ の濃度を比較します。 整数は正と負の両方に無限に広がっているので、自然数より「2倍大きい」ように思えますが、実は全単射が構成できます。
自然数を $0$ から始める表記を使い、$\mathbb{N}_0 = \{0, 1, 2, 3, \ldots\}$ とします（$\mathbb{N}$ と $\mathbb{N}_0$ は $f(n) = n-1$ で全単射なので同じ濃度です）。 写像 $g: \mathbb{N}_0 \to \mathbb{Z}$ を次のように定めます。
$n$ が偶数のとき $g(n) = \frac{n}{2}$、$n$ が奇数のとき $g(n) = -\frac{n+1}{2}$ とします。
| $n$（自然数） | $g(n)$（整数） |
|---|---|
| $0$ | $0$ |
| $1$ | $-1$ |
| $2$ | $1$ |
| $3$ | $-2$ |
| $4$ | $2$ |
| $5$ | $-3$ |
| $6$ | $3$ |
| $\vdots$ | $\vdots$ |
自然数を順に $0, 1, -1, 2, -2, 3, -3, \ldots$ と整数に対応させています。 偶数番目で非負整数を、奇数番目で負整数を拾い上げるので、すべての整数がちょうど1回ずつ現れます。 これは全単射なので、$|\mathbb{N}| = |\mathbb{Z}|$ です。
いよいよ、直感に最も反する結果です。有理数 $\mathbb{Q}$ は数直線を「稠密に」埋めています。 任意の二つの有理数の間には別の有理数が存在します。 それにもかかわらず、$\mathbb{N}$ と $\mathbb{Q}$ は同じ濃度を持ちます。
正の有理数 $\mathbb{Q}^+$ が自然数と同じ濃度であることを示せば十分です （負の有理数と $0$ を含めても、自然数と整数で行ったのと同じ手法で全単射を構成できます）。
正の有理数を分母と分子の組 $\frac{p}{q}$（$p, q$ は正の整数）として、次のような格子状に並べます。
| $q = 1$ | $q = 2$ | $q = 3$ | $q = 4$ | $\cdots$ | |
|---|---|---|---|---|---|
| $p = 1$ | $\frac{1}{1}$ | $\frac{1}{2}$ | $\frac{1}{3}$ | $\frac{1}{4}$ | $\cdots$ |
| $p = 2$ | $\frac{2}{1}$ | $\frac{2}{2}$ | $\frac{2}{3}$ | $\frac{2}{4}$ | $\cdots$ |
| $p = 3$ | $\frac{3}{1}$ | $\frac{3}{2}$ | $\frac{3}{3}$ | $\frac{3}{4}$ | $\cdots$ |
| $p = 4$ | $\frac{4}{1}$ | $\frac{4}{2}$ | $\frac{4}{3}$ | $\frac{4}{4}$ | $\cdots$ |
この無限の表を、対角線に沿ってジグザグに走査します。 $p + q$ の値が小さいほうから、同じ値の中では $p$ が小さいほうから順にたどります。
$p + q = 2$：$\frac{1}{1}$
$p + q = 3$：$\frac{1}{2}, \frac{2}{1}$
$p + q = 4$：$\frac{1}{3}, \frac{2}{2}, \frac{3}{1}$
$p + q = 5$：$\frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}$
$\vdots$
既約分数でないもの（例えば $\frac{2}{2} = 1 = \frac{1}{1}$ のように既出の有理数と同じ値のもの）をスキップすると、 すべての正の有理数が過不足なく一列に並びます。 これがジグザグ論法（対角線走査法）です。
この並べ方により、各正の有理数に自然数 $1, 2, 3, \ldots$ を割り当てることができます。 つまり $\mathbb{N}$ と $\mathbb{Q}^+$ の全単射が構成でき、$|\mathbb{N}| = |\mathbb{Q}^+|$ です。 先ほどの整数の場合と同じ手法で $0$ と負の有理数を含めれば、$|\mathbb{N}| = |\mathbb{Q}|$ となります。
集合 $A$ が可算集合（countable set）であるとは、$A$ が有限集合であるか、または $\mathbb{N}$ との全単射が存在することをいう。
$\mathbb{N}$ と全単射が存在する無限集合を特に可算無限集合と呼び、その濃度を $\aleph_0$（アレフゼロ）と書く。
$\aleph$ はヘブライ文字の最初の文字です。カントールがこの記号を導入しました。
ここまでで、自然数、整数、有理数がすべて同じ濃度 $\aleph_0$ であることを確認しました。 有理数が数直線を稠密に埋めていても、自然数と「同じ大きさ」だったのです。 では、実数も同じでしょうか。次のセクションで、カントールの対角線論法により、実数は $\aleph_0$ より真に大きい濃度を持つことを証明します。
セクション4で、自然数と有理数の間に全単射を構成できることを見ました。 同じことが実数でもできるでしょうか。カントールは1891年に、それが不可能であることを証明しました。 ここでは、開区間 $(0, 1)$ の実数が可算でないことを示します。 （$(0, 1)$ と $\mathbb{R}$ の間には全単射が存在するので、$(0, 1)$ が非可算なら $\mathbb{R}$ も非可算です。）
背理法を使います。「$(0, 1)$ の実数がすべて一列に並べられる（可算である）」と仮定し、矛盾を導きます。 具体的には、どのように並べても必ず「リストに載っていない実数」が構成できることを示します。
示すこと：開区間 $(0, 1)$ の実数全体は可算でない。つまり $\mathbb{N}$ から $(0, 1)$ への全単射は存在しない。
証明
背理法で示します。$(0, 1)$ のすべての実数が一列に並べられると仮定します。 つまり、ある写像 $f: \mathbb{N} \to (0, 1)$ が全射であると仮定します。 このとき、$(0, 1)$ のすべての実数は $f(1), f(2), f(3), \ldots$ のどれかとして現れます。
各実数を小数で表します（小数展開が二通りある場合は、例えば $0.5000\ldots$ と $0.4999\ldots$ のうち一方に統一します）。
$f(1) = 0.a_{11}a_{12}a_{13}a_{14}\ldots$
$f(2) = 0.a_{21}a_{22}a_{23}a_{24}\ldots$
$f(3) = 0.a_{31}a_{32}a_{33}a_{34}\ldots$
$f(4) = 0.a_{41}a_{42}a_{43}a_{44}\ldots$
$\vdots$
ここで $a_{ij}$ は $f(i)$ の小数第 $j$ 位の数字（$0$ から $9$ のいずれか）です。
次に、新しい実数 $x = 0.b_1 b_2 b_3 b_4 \ldots$ を以下のルールで構成します。
各 $n$ に対して、$b_n$ を「$a_{nn}$ と異なる数字」に選びます。 具体的には、$a_{nn} \neq 5$ なら $b_n = 5$、$a_{nn} = 5$ なら $b_n = 6$ とします。 （$0$ や $9$ を避けることで、$0.999\ldots = 1.000\ldots$ のような小数表示の曖昧さを防いでいます。）
この $x$ は $(0, 1)$ の実数です（各桁が $5$ か $6$ なので、$0$ にも $1$ にもなりません）。
しかし、$x$ はリストのどの実数とも異なります。なぜなら：
したがって $x$ はリストに含まれていません。 これは $f$ が全射であるという仮定に矛盾します。
ゆえに、$(0, 1)$ のすべての実数を一列に並べることは不可能であり、$(0, 1)$ は非可算です。$\blacksquare$
この証明の名前の由来は、リストの「対角線」上の数字 $a_{11}, a_{22}, a_{33}, \ldots$ に注目し、それぞれを変えて新しい実数を構成するところにあります。 対角線上の数字を一つずつずらすだけで、リストのすべての実数と異なる実数が作れてしまう ── この鮮やかな論法がカントールの対角線論法です。
上の証明では $(0, 1)$ が非可算であることを示しました。 $(0, 1)$ と $\mathbb{R}$ の間に全単射が存在すれば、$\mathbb{R}$ も非可算であることがわかります。 実際、$f(x) = \tan\left(\pi x - \frac{\pi}{2}\right)$ は $(0, 1)$ から $\mathbb{R}$ への全単射です。 （$x$ が $0$ から $1$ に動くとき、$\tan$ の引数は $-\frac{\pi}{2}$ から $\frac{\pi}{2}$ へ動き、$\tan$ の値は $-\infty$ から $+\infty$ まで単調に増加します。） したがって $|\mathbb{R}| = |(0, 1)|$ であり、$\mathbb{R}$ は非可算です。
実数の濃度を $\mathfrak{c}$（連続体の濃度）と書きます。ここまでの結果をまとめると、
$\aleph_0 = |\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| < \mathfrak{c} = |\mathbb{R}|$
つまり、無限集合には少なくとも2段階の「大きさ」があります。 可算無限 $\aleph_0$ と、それより真に大きい非可算無限 $\mathfrak{c}$ です。
誤解1：「リストに載っていない実数 $x$ を見つけたら、リストに追加すればよいのでは？」
反論：$x$ を追加した新しいリストに対して、再び対角線論法を適用すると、また載っていない実数が見つかります。問題は「有限回の追加で完成するか」ではなく、「$\mathbb{N}$ から $(0, 1)$ への全射が存在するか」です。この証明は、どのような全射を仮定しても矛盾が生じることを示しています。
誤解2：「この論法を有理数に適用すれば、有理数も非可算だと証明できるのでは？」
反論：対角線論法で構成される $x = 0.b_1 b_2 b_3 \ldots$ は無限小数です。この $x$ が有理数である保証はありません（実際、一般には無理数になります）。有理数のリストに対して対角線論法を適用しても、見つかる $x$ が有理数でなければ矛盾は生じません。実数の場合に矛盾が生じるのは、$(0, 1)$ のすべての実数（有理数も無理数も）がリストに含まれるはずだと仮定しているからです。
誤解3：「小数展開の曖昧さ（$0.999\ldots = 1.000\ldots$）があるので、証明に穴があるのでは？」
反論：証明中で $b_n$ を $5$ か $6$ にしか選ばないため、構成された $x$ の小数表示に $0$ や $9$ が連続する部分はありません。したがって小数展開の曖昧さの問題は生じません。
ここまでで、可算無限と非可算無限という2段階の無限を確認しました。 では、非可算無限のさらに上はあるのでしょうか。次のセクションで、濃度の階層がどこまでも続くことを見ていきます。
集合 $A$ のべき集合 $\mathcal{P}(A)$ とは、$A$ のすべての部分集合を要素とする集合のことです。 例えば $A = \{1, 2\}$ のとき、
$\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$
です。$|A| = 2$ に対して $|\mathcal{P}(A)| = 4 = 2^2$ です。 一般に、有限集合 $A$ に対して $|\mathcal{P}(A)| = 2^{|A|}$ が成り立ちます。 これは、各要素について「部分集合に入れるか入れないか」の2通りの選択があるためです。
もう一つ例を見ます。$B = \{a, b, c\}$ のとき、
$\mathcal{P}(B) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$
で、$|B| = 3$ に対して $|\mathcal{P}(B)| = 8 = 2^3$ です。
重要なのは、$|\mathcal{P}(A)| > |A|$ が常に成り立つということです。 有限集合では $2^n > n$ なので当然ですが、この不等式は無限集合でも成り立ちます。 これをカントールの定理と呼びます。
任意の集合 $A$ に対して、$A$ からべき集合 $\mathcal{P}(A)$ への全単射は存在しない。つまり、
$$|A| < |\mathcal{P}(A)|$$
この定理の証明にも対角線論法と同じ発想（仮定した全射から矛盾を導く）が使われます。
示すこと：$A$ から $\mathcal{P}(A)$ への全射は存在しない。
証明の方針：全射 $f: A \to \mathcal{P}(A)$ が存在すると仮定し、$\mathcal{P}(A)$ の要素のうち $f$ の値域に含まれないものを構成します。これは対角線論法の一般化です。
証明
$f: A \to \mathcal{P}(A)$ が全射であると仮定します。 各 $a \in A$ に対して、$f(a)$ は $A$ の部分集合です。
ここで、次の集合 $D$ を考えます。
$$D = \{a \in A \mid a \notin f(a)\}$$
$D$ は $A$ の部分集合なので、$D \in \mathcal{P}(A)$ です。 $f$ が全射ならば、ある $d \in A$ が存在して $f(d) = D$ のはずです。
ここで $d \in D$ かどうかを調べます。
いずれの場合も矛盾するので、全射 $f: A \to \mathcal{P}(A)$ は存在しません。 単射 $a \mapsto \{a\}$ は常に構成できるので、$|A| < |\mathcal{P}(A)|$ です。$\blacksquare$
カントールの定理を $A = \mathbb{N}$ に適用すると、$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|$ です。 さらに $\mathcal{P}(\mathbb{N})$ にカントールの定理を適用すると $|\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))|$ です。 これを繰り返すと、
$$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$$
となり、濃度の階層はどこまでも続くことがわかります。 無限は一つではなく、無限に多くの「大きさ」があるのです。
$|\mathcal{P}(\mathbb{N})| = \mathfrak{c} = |\mathbb{R}|$ であることが知られています （$(0, 1)$ の実数と、$\mathbb{N}$ の部分集合は、二進小数表示を通じて自然に対応します）。 つまり、実数全体の濃度は自然数のべき集合の濃度に等しいのです。
ここで自然な疑問が生じます。$\aleph_0$ と $\mathfrak{c}$ の間に、別の濃度は存在するのでしょうか。 つまり、$\aleph_0 < |X| < \mathfrak{c}$ となる集合 $X$ は存在するのでしょうか。
連続体仮説：$\aleph_0$ と $\mathfrak{c}$ の間に別の濃度は存在しない。
ゲーデル（1940年）は、連続体仮説を仮定しても標準的な集合論（ZFC公理系）と矛盾しないことを証明しました。 一方、コーエン（1963年）は、連続体仮説の否定を仮定しても矛盾しないことを証明しました。 つまり、連続体仮説はZFC公理系からは証明も反証もできない独立な命題です。 これは数学の公理系に固有の限界があることを示す結果の一つです。
なぜ $\mathbb{N}$ の部分集合の全体と実数の全体が同じ濃度なのか、直感的に理解する方法があります。
$\mathbb{N}$ の部分集合 $S$ が与えられたとき、各自然数 $n$ について「$S$ に入っているなら $1$、入っていないなら $0$」として、 $0$ と $1$ の無限列 $d_1 d_2 d_3 \ldots$ を作ります。 例えば $S = \{1, 3, 4, 7, \ldots\}$ なら $1, 0, 1, 1, 0, 0, 1, \ldots$ です。
この列を $0.d_1 d_2 d_3 \ldots$ という二進小数とみなすと、$(0, 1)$ の実数が得られます。 このようにして $\mathcal{P}(\mathbb{N})$ の要素と $(0, 1)$ の実数を対応させることができるのです。 （厳密には二進小数表示の曖昧さの処理が必要ですが、それを除けばこの対応は全単射になります。）
濃度の考え方は、「無限はすべて同じ」という素朴な直感を覆し、無限の中にも精緻な構造があることを明らかにしました。 セクション3で導入した全単射による比較が、ここまでの議論のすべてを支えています。
Q1. 集合 $A$ と集合 $B$ の「濃度が等しい」とはどういう意味ですか。全単射の概念を使って説明してください。
Q2. 自然数全体 $\mathbb{N}$ と偶数全体 $E = \{2, 4, 6, \ldots\}$ は同じ濃度を持ちます。このことを示す全単射を一つ具体的に述べてください。
Q3. カントールの対角線論法で、なぜ同じ論法が有理数には使えない（有理数が非可算であることの証明にならない）のですか。
Q4. カントールの定理は何を主張する定理ですか。また、この定理から「無限の階層」についてどのような結論が得られますか。
集合 $A = \{1, 2, 3, 4\}$ のべき集合 $\mathcal{P}(A)$ の要素数を求めてください。 また、$\mathcal{P}(A)$ の要素のうち、要素数が2のものをすべて列挙してください。
$|\mathcal{P}(A)| = 2^{|A|} = 2^4 = 16$ です。
要素数が2の部分集合は、$\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}$ の $\binom{4}{2} = 6$ 個です。
べき集合の要素数が $2^n$ になる理由は、各要素について「部分集合に入れる」か「入れない」かの2通りの選択があるためです。$n$ 個の要素に対して独立に2通りの選択をするので、全体で $2^n$ 通りになります。
写像 $f: \{1, 2, 3\} \to \{a, b, c, d\}$ を $f(1) = b, f(2) = d, f(3) = a$ と定めます。 この写像が単射か全射かそれぞれ判定してください。
単射です。 $f(1) = b, f(2) = d, f(3) = a$ はすべて異なるので、異なる要素が異なる先に移っています。
全射ではありません。 $c \in \{a, b, c, d\}$ に対して $f(k) = c$ となる $k$ が存在しないためです。
自然数全体 $\mathbb{N} = \{1, 2, 3, \ldots\}$ と奇数全体 $O = \{1, 3, 5, 7, \ldots\}$ の間の全単射を一つ具体的に構成し、 それが全単射であることを証明してください。
$f: \mathbb{N} \to O$ を $f(n) = 2n - 1$ と定めます。
単射の証明：$f(n_1) = f(n_2)$ と仮定すると、$2n_1 - 1 = 2n_2 - 1$ より $n_1 = n_2$ です。対偶により、$n_1 \neq n_2$ なら $f(n_1) \neq f(n_2)$ です。
全射の証明：任意の奇数 $m \in O$ に対して、$m = 2k - 1$ となる自然数 $k$ が存在します（$k = \frac{m+1}{2}$。$m$ が奇数なので $m + 1$ は偶数であり、$k$ は正の整数です）。このとき $f(k) = 2k - 1 = m$ です。
以上より、$f$ は全単射です。$\blacksquare$
セクション4のジグザグ論法で正の有理数を自然数に対応させるとき、 $\frac{3}{5}$ は何番目に現れますか。 ただし、$p + q$ の値が小さいほうから、同じ値の中では $p$ が小さいほうから数え、 既約分数でないものはスキップするものとします。
$p + q$ の値に沿って順に並べ、スキップする分数を除きます。
$p + q = 2$：$\frac{1}{1}$ ......（1番目）
$p + q = 3$：$\frac{1}{2}, \frac{2}{1}$ ......（2番目、3番目）
$p + q = 4$：$\frac{1}{3},$ $\frac{2}{2}$$, \frac{3}{1}$ ......（4番目、スキップ、5番目）
$p + q = 5$：$\frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}$ ......（6番目、7番目、8番目、9番目）
$p + q = 6$：$\frac{1}{5},$ $\frac{2}{4}$$, \frac{3}{5}$ ...... ここまでで $\frac{3}{5}$ に到達。
$\frac{1}{5}$ は10番目、$\frac{2}{4} = \frac{1}{2}$ はスキップ、$\frac{3}{5}$ は11番目です。
無理数全体の集合を $\mathbb{R} \setminus \mathbb{Q}$ とします。 $\mathbb{R} \setminus \mathbb{Q}$ は可算集合でしょうか、非可算集合でしょうか。 理由を付けて答えてください。
ヒント：もし $\mathbb{R} \setminus \mathbb{Q}$ が可算だったとしたら、$\mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q})$ について何が言えるかを考えてください。 また、「可算集合の合併は可算」という事実を使ってよいものとします。
$\mathbb{R} \setminus \mathbb{Q}$ は非可算です。
証明（背理法）：$\mathbb{R} \setminus \mathbb{Q}$ が可算であると仮定します。 $\mathbb{Q}$ は可算（セクション4で示した通り）なので、 「可算集合の合併は可算」により、$\mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q})$ も可算になります。 しかし、$\mathbb{R}$ は非可算（セクション5で証明済み）なので矛盾です。 したがって $\mathbb{R} \setminus \mathbb{Q}$ は非可算です。$\blacksquare$
この結果は「無理数は有理数よりずっと多い」ことを意味しています。有理数は数直線を稠密に埋めていますが、濃度の観点からは、数直線の「ほとんど」は無理数で占められています。有理数の濃度 $\aleph_0$ と無理数の濃度 $\mathfrak{c}$ の間には、$\aleph_0 < \mathfrak{c}$ という真の不等式が成り立ちます。