集合の濃度と可算無限・非可算無限

集合 $A$ の「大きさ」 について考えます。$A$ が有限集合のときには，$A$ の要素数を「大きさ」と考えられますが，無限集合のときは要素数を数えることができません。無限集合の中でも「要素がたくさんある」ものと「要素があまりない」ものを区別するために，集合に対して濃度という概念が定義されます。

• 単射とは $x\neq y$ ならば $f(x)\neq f(y)$ となる関数，つまり行き先がかぶらない関数のことです。単射があれば行き先の方が広い（狭くはない）というわけです。
• 定義の2と3について，$|A|\leq|B|$ かつ $|A|\geq |B|$ なら $|A|=|B|$が成立します。当たり前な気もしますが，これはベルンシュタインの定理と呼ばれ，証明はやや大変です。→ベルンシュタインの定理とその証明
  

濃度が等しいというのは全単射が存在するということです。そこで，整数全体の集合と正の整数全体の集合の間の一対一対応を作ることで証明します。

整数の方が自然数よりもたくさん（二倍くらい）あるじゃないか！と思いますが，濃度という観点から見ると両者は同じです。

証明はさきほどと同様に全単射を構成してやればOKです。簡単にできます。

直感的には有理数の方が圧倒的にたくさんありますが，濃度という観点から見ると両者は同じなのです！

有理数と実数の間には濃度の意味でギャップがあります。例5の証明にも対角線論法を使います。例4と同じ記事：カントールの定理の証明と対角線論法の末尾で証明しています。

• ここまでの結果から，$|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|<|\mathbb{R}|$ がわかりました。
• $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|$ のことを $\aleph_0$ と書くことがあります。「アレフ・ゼロ」と読みます。
• 実は，任意の無限集合 $A$ に対して $|\mathbb{N}|\leq|A|$ です。つまり，$\aleph_0$ は無限集合の濃度の中で「最小」です。
• また，$|2^{\mathbb{N}}|=|\mathbb{R}|$ です。大雑把なイメージですが，小数の2進数表示を考えると，たしかに $2^{\mathbb{N}}$ と $[0,1]$ が同じ濃度になりそうです。

• 正の整数全体の集合 $\mathbb{N}$ と濃度が等しい集合を可算集合といいます。可算集合の要素は可算無限個などと言います。可算無限とは「無限個あるけど番号をふっていける程度」の無限です。
• 上記の例から分かるように，整数は可算無限個であるのはもちろん，有理数も可算無限個です。
• 可算集合は $\mathbb{N}$ との間に全単射があるので，要素に $1$ から順番に番号をふっていくことができます。そのため可付番集合とも言います。
• 無限集合であり，可算集合でないものを非可算集合と言います。実数全体や複素数全体は非可算無限です。非可算無限とは「番号をふることすらできない」無限です。