（問題）
次の集合は可算集合であるかどうかを確かめよ。
(1) 実数全体の集合 R
(2) 素数全体の集合 P
(3) 無理数全体の集合 I
（考察）
自然数全体と濃度が等しい集合を可算集合といいます。
Z, Q は可算集合です。
また、事実としては R は可算集合ではありません。
まずは、このことを確認しましょう。
そのことを用いて (3) を示します。
(2) は「可算集合の部分集合は有限集合か可算集合である。」
を用います。
素数が無限に存在することも確認します。
（解答例）
(1) R は可算集合ではない。
（証明）
(2) 素数全体の集合 P は可算集合である。
素数全体の集合は N の部分集合です。
N は可算集合で、「可算集合の部分集合は有限集合か可算集合」です。
素数は無限に存在するので、P は可算集合となります。
(3) 無理数全体の集合 I は可算集合ではない。
有理数全体の集合 Q は可算集合であり、
Q ∪ I =R です。
もし、I が可算集合ならば、可算集合の和集合も可算集合なので、
Q ∪ I =R も可算集合となり、(1) に矛盾します。
（確認）
「素数が無限に存在する。」を背理法を用いて示します。
素数が有限個しか存在しないと仮定し、
p1,...,pn をすべての素数とします。
このとき、それらの和に 1 を加えた数を m とします。
m = p1...pn + 1
m の 1 より大きい最小の約数を q とすれば、
最小性より q は素数となります, が
p1, ... ,pn は
すべての素数なので、 q は ある pi と一致
し、 p1...pn を割り切ります。
よって、1 = m - p1...pn を割り切ることになります。
q は １より大きな数なので、矛盾がおこります。
（問題）
素数全体の集合 P と 無理数全体の集合 I の濃度を比較せよ。
（解答例）
素数全体の集合 P と 無理数全体の集合 I の濃度を比較します。
上で示したように、素数全体の集合 P は可算集合です。
無理数全体の集合 I は可算集合ではありません。
よって、 | P | ≠ | I | です。
一方, 写像 f : P → I (p → √p ) は単射なので、
| P | ≦ | I | です。 よって、| P | < | I | を得ます。