無限集合

同義語：infinite set

概要

前提知識: 有限集合, 全単射, 自然数, 数学的帰納法

自然数全体と偶数全体を
$$ \begin{array}{ccccccc} 0 & 1 & 2 & 3 & 4 & \cdots\\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \\ 0 & 2 & 4 & 6 & 8 & \cdots \end{array} $$
と $n\mapsto2n$ で対応させると、どの自然数にもちょうど 1 つの偶数が、どの偶数にもちょうど 1 つの自然数が対応する。すなわち $n\mapsto2n$ は自然数全体から偶数全体への全単射である。偶数全体は自然数全体の一部分（奇数を取り除いたもの）なのに、1 対 1 に対応がつく意味で「同じ個数」の元をもつ。有限集合ではこのようなことは決して起こらない。元が $5$ 個の集合から $1$ 個取り除けば、残りは $4$ 個で、元の集合と 1 対 1 には対応しない。有限でない集合を 無限集合 という。本記事では、自然数全体が無限集合であること、無限集合の特徴づけ、そして「一部分と同じ大きさになれる」という性質が無限集合の特徴づけになることは可算選択公理から従うが、選択公理を含まない集合論だけからは証明できないことを述べる。

定義

$n\in\mathbb{N}$ に対して $I_n:=\{1,2,\dots,n\}$（$I_0=\emptyset$）とする。集合 $X$ が有限集合であるとは、ある $n$ について全単射 $I_n\to X$ が存在することであった（有限集合の記事の定義「有限集合と元の個数」）。

無限集合の定義

有限集合でない集合を 無限集合（infinite set）という。すなわち $X$ が無限集合であるとは、どの $n\in\mathbb{N}$ についても全単射 $I_n\to X$ が存在しないことをいう。

冒頭の現象に名前を付けておく。集合 $X$ とその部分集合 $A$ の間に全単射があるとき、$X$ と $A$ は対等（基数）であるという。$A\subset X$ かつ $A\neq X$ のとき $A$ を $X$ の真部分集合という。

Dedekind無限な集合

集合 $X$ が、ある真部分集合と対等であるとき、$X$ は Dedekind 無限（Dedekind-infinite）であるという。Dedekind 無限でない集合を Dedekind 有限という。

$X$ が Dedekind 無限であることは、単射だが全射でない写像 $X\to X$ が存在することと同値である。実際、全単射 $h\colon X\to A$（$A\subsetneq X$）は $X\to X$ の単射で全射でないものとみなせ、逆に単射 $\sigma\colon X\to X$ が全射でなければ、$\sigma$ は $X$ から真部分集合 $\sigma(X)$ への全単射である。Dedekind はこの性質を無限集合の定義として用いた。本記事では定義としては def-infset を採り、2 つの定義の関係を thm-infset-dedekind で調べる。

直感

無限集合には 2 つの見方がある。1 つは「数え終わらない」ことであり、def-infset はこれを表す。もう 1 つは「一部分と同じ大きさになれる」ことであり、Dedekind 無限の定義はこれを表す。後者はしばしば「無限のホテル」（Hilbert のホテルと呼ばれる）のたとえで説明される。部屋番号が $0,1,2,\dots$ の客室が無限にあるホテルが満室でも、$n$ 号室の客に $n+1$ 号室へ移ってもらえば $0$ 号室が空き、新しい客を泊められる。$n$ 号室の客に $2n$ 号室へ移ってもらえば、奇数番号の部屋が全部空き、無限に多くの新しい客を泊められる。前者は $n\mapsto n+1$、後者は $n\mapsto2n$ が単射だが全射でないことを言い換えたものである。部屋が有限個のホテルでは、全員が別の部屋に移れば必ず全部の部屋が埋まる（有限集合の記事の系「単射・全射と元の個数」の 3）。
2 つの見方は、選択公理を仮定する通常の数学では一致する（thm-infset-dedekind）。ただしその証明には無限個の選択が 1 回だけ入り込む。

例と反例

代表的な無限集合

$\mathbb{N}$ は無限集合である（prop-infset-naturals）。
整数全体 $\mathbb{Z}$、有理数全体 $\mathbb{Q}$、実数全体 $\mathbb{R}$ は、無限集合 $\mathbb{N}$ を含むので無限集合である（prop-infset-superset の 1）。
素数全体は無限集合である。これは素数の記事の定理「素数の無限性」（Euclid の証明）の内容である。
実数の区間 $(0,1)=\{x\in\mathbb{R}\mid 0< x<1\}$ は、$n\mapsto1/(n+2)$ が $\mathbb{N}$ から $(0,1)$ への単射なので、無限集合 $\{1/(n+2)\mid n\in\mathbb{N}\}$ を含み、無限集合である。$(0,1)$ は有界であり、「無限集合」は「どこまでも大きい数を含む」ことを意味しない。
自然数全体から $\{0,1\}$ への写像全体の集合 $\{0,1\}^{\mathbb{N}}$ は、$n$ だけで値 $1$ をとる写像 $\delta_n$ たちが相異なるので無限集合である。

無限のホテルの写像

$s\colon\mathbb{N}\to\mathbb{N}$、$s(n)=n+1$ は単射で、像は $\mathbb{N}\setminus\{0\}$ である。$d\colon\mathbb{N}\to\mathbb{N}$、$d(n)=2n$ は単射で、像は偶数全体である。どちらも $\mathbb{N}$ からその真部分集合への全単射を与えるので、$\mathbb{N}$ は Dedekind 無限である。整数全体でも $m\mapsto2m$ は $\mathbb{Z}$ から偶数全体（真部分集合）への全単射である。

反例：無限集合はすべて可算とは限らない

$\mathbb{N}$ から $X$ への全単射が存在する集合 $X$ を可算無限集合という（可算集合。可算無限集合は $\mathbb{N}$ と対等なので無限集合である）。$\mathbb{N}$、$\mathbb{Z}$、$\mathbb{Q}$ は可算無限である（可算集合の記事の例「整数と偶数の番号付け」「有理数全体の可算性」）。しかし $\mathbb{R}$ と $\{0,1\}^{\mathbb{N}}$ は無限集合であるが可算でない（可算集合の記事の定理「実数全体の非可算性」、Cantorの対角線論法）。この例は「無限集合は $\mathbb{N}$ と対等である」という含意を破っており、無限集合の間にもさらに大きさの違いがあることを示す。無限集合の大きさの比較は基数と非可算集合の記事で扱う。

反例：無限集合では元の個数の引き算ができない

$X$ が無限で $F\subset X$ が有限なら $X\setminus F$ は無限である（prop-infset-superset の 2）。一方、無限集合から無限個の元を除くと、残りは無限のことも（$\mathbb{N}$ から奇数を除いた偶数全体）、有限のことも（$\mathbb{N}$ から $3$ 以上の数を除いた $\{0,1,2\}$）、空のことも（$\mathbb{N}$ から $\mathbb{N}$ を除いた $\emptyset$）ある。有限集合での「元の個数の引き算」は、無限集合では意味をもたない。有限集合 $X$ とその部分集合 $A,B$ について「$A$ と $B$ が対等なら $X\setminus A$ と $X\setminus B$ は対等」が成り立つ（どちらも元の個数が $|X|-|A|$）。この含意は、$X=\mathbb{N}$、$A=\mathbb{N}$、$B=\{\text{奇数}\}$（$A$ と $B$ は $n\mapsto2n+1$ で対等）で破れる。$X\setminus A=\emptyset$ で $X\setminus B$ は偶数全体であり、両者は対等でない。破れている仮定は「$X$ が有限である」ことである。

性質

自然数全体は無限である

自然数全体の無限性

$\mathbb{N}$ は無限集合である。

後者写像は単射だが全射でない

$\mathbb{N}$ が有限集合であったとする。$s\colon\mathbb{N}\to\mathbb{N}$、$s(n)=n+1$ は単射である（$m+1=n+1$ なら $m=n$）。有限集合からそれ自身への単射は全射である（有限集合の記事の系「単射・全射と元の個数」の 3）ので、$s$ は全射であり、$0=s(n)=n+1$ となる自然数 $n$ がある。しかし $n+1\ge1$ なのでこれは不可能である。よって $\mathbb{N}$ は有限でない。$\square$

可算集合の記事の注意「自然数全体は無限である」は、有限個の自然数の最大値に $1$ を足した数が像から漏れることによる別の証明を与えている。

無限であることの特徴づけ

無限集合の基本性質

$X,Y$ を集合とする。

$X\subset Y$ で $X$ が無限なら、$Y$ も無限である。
$X$ が無限で $F\subset X$ が有限なら、$X\setminus F$ は無限である。
単射 $f\colon X\to Y$ があり $X$ が無限なら、$Y$ も無限である。
$X$ が無限であることと、すべての $n\in\mathbb{N}$ について単射 $I_n\to X$ が存在することは同値である。

有限集合の性質の対偶と、1 元ずつ延ばす帰納法

$Y$ が有限なら、有限集合の記事の命題「有限集合の部分集合」により $X$ も有限である。対偶をとればよい。
$X\setminus F$ が有限なら、$X=(X\setminus F)\cup F$ は有限集合 2 つの和集合なので有限である（有限集合の記事の命題「和集合の元の個数」）。これは $X$ が無限であることに反する。
$Y$ が有限なら、有限集合の記事の系「単射・全射と元の個数」の 1 により $X$ も有限である。対偶をとればよい。
$X$ が無限であるとし、$n$ に関する数学的帰納法で単射 $I_n\to X$ の存在を示す。$n=0$ なら空写像 $I_0=\emptyset\to X$ は単射である。単射 $f\colon I_n\to X$ があるとする。像 $f(I_n)$ は $I_n$ と対等なので有限であり、$X$ は無限なので $f(I_n)\ne X$ である。$x\in X\setminus f(I_n)$ を 1 つとり、$f$ を $n+1\mapsto x$ で延長すれば単射 $I_{n+1}\to X$ が得られる。
逆に、すべての $n$ で単射 $I_n\to X$ があるとする。$X$ が有限で $|X|=m$ なら、単射 $I_{m+1}\to X$ と全単射 $X\to I_m$ の合成は単射 $I_{m+1}\to I_m$ であり、有限集合の記事の補題「番号の集合の間の単射」により $m+1\le m$ となって矛盾する。よって $X$ は無限である。$\square$

4 の前半の証明では、各段階で「空でない集合 $X\setminus f(I_n)$ から元を 1 つとる」ことを 1 回ずつ行っている。示しているのは「各 $n$ について単射 $I_n\to X$ が存在する」という $n$ ごとの主張であり、帰納法の各段階で 1 つの元をとることは選択公理を必要としない。これに対し、「単射 $I_n\to X$ をすべての $n$ について同時に 1 つずつ選ぶ」ことは、無限個の選択であり、次の定理で問題になる。

Dedekind 無限との関係

無限集合と Dedekind 無限

集合 $X$ について次が成り立つ。

$X$ が Dedekind 無限であることと、単射 $\mathbb{N}\to X$ が存在すること（$X$ が可算無限な部分集合をもつこと）は同値である。
$X$ が Dedekind 無限なら、$X$ は無限集合である。
可算選択公理を仮定すると、$X$ が無限集合なら、単射 $\mathbb{N}\to X$ が存在し、したがって $X$ は Dedekind 無限である。
1 と 2 の証明には選択公理を使わない。

後者写像を埋め込む／選んだ単射の列を並べる

単射 $e\colon\mathbb{N}\to X$ があるとする。写像 $\sigma\colon X\to X$ を、$x=e(n)$ と書ける $x$ には $\sigma(x):=e(n+1)$、それ以外の $x$ には $\sigma(x):=x$ と定める（$e$ は単射なので $n$ は $x$ から一意に決まる）。$\sigma$ は $e(\mathbb{N})$ の上では $e(n)\mapsto e(n+1)$ で単射、その外では恒等写像で、両者の値は $e(\mathbb{N})$ の中と外に分かれるので、$\sigma$ は単射である。$e(0)$ は $\sigma$ の像に属さない（$e(0)=e(n+1)$ となる $n$ はなく、$e(0)\in e(\mathbb{N})$ は恒等写像の部分の値でもない）ので、$\sigma$ は全射でない。よって $X$ は Dedekind 無限である。
逆に、単射 $\sigma\colon X\to X$ と、$\sigma$ の像に属さない $x_0\in X$ があるとする。$e(n):=\sigma^n(x_0)$（$\sigma$ を $n$ 回合成して $x_0$ に適用したもの、$\sigma^0(x_0)=x_0$）とおく。$m< n$ で $e(m)=e(n)$ なら、$\sigma$ の単射性を $m$ 回使って $x_0=\sigma^{n-m}(x_0)=\sigma(\sigma^{n-m-1}(x_0))$ となり、$x_0$ が $\sigma$ の像に属して矛盾する。よって $e\colon\mathbb{N}\to X$ は単射である。
単射 $e\colon\mathbb{N}\to X$ があれば、prop-infset-naturals と prop-infset-superset の 3 により $X$ は無限である。
$X$ を無限集合とする。各 $n\ge1$ について、単射 $I_n\to X$ の全体を $A_n$ とおくと、prop-infset-superset の 4 により $A_n$ は空でない。可算選択公理により、各 $n\ge1$ について $g_n\in A_n$ を同時に選べる。$g_n$ の値を
$$ g_1(1);\ g_2(1),g_2(2);\ g_3(1),g_3(2),g_3(3);\ \dots $$
の順に並べた列を $c\colon\mathbb{N}\to X$ とする（$c$ は選んだ列 $(g_n)$ から明示的に定まる）。$c$ の像 $U=\bigcup_{n\ge1}g_n(I_n)$ は無限集合である。実際、$U$ が有限で $|U|=m$ なら、$g_{m+1}(I_{m+1})\subset U$ は元の個数 $m+1$ をもつので有限集合の記事の命題「有限集合の部分集合」に反する。
$e\colon\mathbb{N}\to X$ を再帰的に、$e(k):=c(j_k)$、ただし $j_k$ は $c(j)\notin\{e(0),\dots,e(k-1)\}$ を満たす最小の $j$、と定める。$\{e(0),\dots,e(k-1)\}$ は有限で $U$ は無限なので、prop-infset-superset の 2 によりそのような $j$ は存在し、最小のものは数学的帰納法の記事の定理「自然数の整列原理」により一意に定まる。構成から $e(k)$ は $e(0),\dots,e(k-1)$ のどれとも異なるので、$e$ は単射である。1 により $X$ は Dedekind 無限である。$\square$

3 の証明で選択公理を使ったのは、無限個の単射 $g_1,g_2,\dots$ を一斉に選ぶ 1 か所だけである。その後の構成（$c$ と $e$）は、選んだ列から「最小の番号」という規則で決まり、選択を必要としない。

選択公理なしでは 2 つの定義は一致しない

thm-infset-dedekind の 2 により、有限集合は Dedekind 有限である。この向きは選択公理なしに証明できる（有限集合の記事の注意「有限集合は真部分集合と対等にならない」も参照）。逆向き「Dedekind 有限な集合は有限である」は、可算選択公理から従う（thm-infset-dedekind の 3）が、選択公理を含まない集合論 $\mathsf{ZF}$ だけからは証明できない。$\mathsf{ZF}$ が無矛盾なら、$\mathsf{ZF}$ に「無限だが Dedekind 有限な集合（可算無限な部分集合をもたない無限集合）が存在する」を加えた体系も無矛盾である。Cohen の強制法による基本モデルでは、実数の集合でそのようなものが存在する（Jech73 §5.3 と第 5 章の問題 18、第 10 章 Theorem 10.1）。可算選択公理から「無限集合は Dedekind 無限」が従うことと、選択公理がない場合に有限性の概念が分かれることは Herrlich06 の Theorem 2.14 と §4.1 Finiteness（p. 43 以降）で扱われている。選択公理の記事も参照。

無限集合の大きさ

thm-infset-dedekind の 3 は、可算選択公理のもとで、どの無限集合も $\mathbb{N}$ と対等な部分集合をもつこと、すなわち可算無限集合が「最も小さい無限集合」であることを述べている。濃度の言葉では、無限集合 $X$ について $\aleph_0\le|X|$ である（基数）。一方、冪集合は元の集合より真に大きい（Cantorの対角線論法の記事の系「冪集合は元の集合より真に大きい」）ので、無限集合の大きさには上限がない。可算無限と非可算の区別は可算集合・非可算集合の記事で扱う。Ham は Chapter 14（§14.1–14.2、pp. 269–279）で対等による集合の大きさの比較を扱い、可算無限を Definition 14.2（p. 275）で定義している。KT17 の付録 B.5（p. 339）は、有限でない集合を無限集合と呼ぶ本記事と同じ定義を採っている。