帰納的集合
概要
帰納的集合（inductive set）とは、空集合を要素として含み、要素 $x$ を含めばその後続者 $x\cup\{x\}$ も含む集合のことである。公理的集合論の無限公理は帰納的集合の存在を主張し、帰納的集合の共通部分はまた帰納的なので、一つの帰納的集合に含まれる帰納的集合すべての共通部分として最小の帰納的集合 $\omega$（自然数全体）が定まる。$\omega$ は任意の帰納的集合に含まれ、この最小性から数学的帰納法の原理が定理として導かれ、$\omega$ が推移的であることも従う。個々の自然数は帰納的集合でなく、$\omega$ に後続者を繰り返し付け加えた $\omega+\omega$ は $\omega$ より大きい帰納的集合である。集合とは限らないクラスについて同じ条件を考えたものを帰納的クラスといい、順序数全体（集合ではない）がその例である。
定義
集合 $x$ に対し $x^{+}:=x\cup\{x\}$ を $x$ の後続者という。
集合 $X$ が帰納的集合（inductive set）であるとは、次の二つが成り立つことをいう。
- $\emptyset\in X$。
- $x\in X$ ならば $x^{+}=x\cup\{x\}\in X$。
クラス $\mathbf{A}$ が帰納的クラス（inductive class）であるとは、$\emptyset\in\mathbf{A}$ であり、$x\in\mathbf{A}$ ならば $x^{+}\in\mathbf{A}$ が成り立つことをいう。
公理的集合論（ZF）の無限公理は「帰納的集合が少なくとも一つ存在する」という主張である（Jech03 第 1 章）。本記事では ZF の公理、特に無限公理・分出公理・正則性公理を仮定する。
直感
帰納的集合は、自然数を集合として作るための鋳型である。von Neumann の構成（Jech03 第 1 章）では $0:=\emptyset$、$1:=0^{+}=\{\emptyset\}$、$2:=1^{+}=\{\emptyset,\{\emptyset\}\}$、$\dots$ と後続者を繰り返して自然数を作る。「$\emptyset$ を含み、後続者で閉じている」という帰納的集合の条件は、自然数全体が満たすべき最小限の性質であり、自然数全体 $\omega$ はすべての帰納的集合に共通して含まれる最小の帰納的集合として定義される（prop-inductive-set-omega）。帰納的集合は $\omega$ より大きくてもよく、また集合とは限らない集まり（クラス）についても同じ条件を考えることができる。
例と反例
自然数全体 $\omega$（prop-inductive-set-omega で定義する）は帰納的集合であり、しかも最小の帰納的集合である：任意の帰納的集合 $X$ について $\omega\subset X$ が成り立つ。
$\omega$ 自身から出発して後続者を繰り返し取った集合 $\omega,\ \omega^{+},\ \omega^{++},\dots$ をすべて $\omega$ に付け加えた集合 $\omega+\omega:=\omega\cup\{\omega,\omega^{+},\omega^{++},\dots\}$ は帰納的集合である。実際 $\emptyset\in\omega$ であり、$x\in\omega$ なら $x^{+}\in\omega$、$x$ が $\omega$ に $n$ 回後続者を取った集合なら $x^{+}$ は $n+1$ 回取った集合である。$\omega\in\omega+\omega$ であり、正則性公理により $\omega\notin\omega$ なので、$\omega+\omega$ は $\omega$ を真に含む。後続者を $n$ 回取った集合全体が集合として存在することは $\omega$ 上の再帰定理による（Jech03 第 2 章。本記事では証明しない）。
順序数全体のクラス $\mathsf{Ord}$ は帰納的クラスである（$\emptyset$ は順序数であり、順序数の後続者は順序数である。Jech03 第 2 章。本記事では証明しない）。$\mathsf{Ord}$ は集合ではない（Burali–Forti の逆理）ので、帰納的「集合」ではなく帰納的「クラス」の例である。
次の例は「$\emptyset$ を含む集合は帰納的集合である」が成り立たないことを示す。$1=\{\emptyset\}$ は $\emptyset$ を含むが帰納的集合ではない。実際、条件 2 を $x=\emptyset$ に適用すると $\emptyset^{+}=\{\emptyset\}=1$ が $1$ の要素でなければならないが、$1$ の唯一の要素は $\emptyset$ であり $\emptyset\neq1$ である。より一般に、どの自然数 $n\in\omega$ も帰納的集合ではない：$n$ が帰納的集合なら prop-inductive-set-omega により $\omega\subset n$ であり、$n\in\omega$ と合わせて $n\in n$ となるが、これは正則性公理に反する。帰納的集合であるためには後続者を無限に取り続けられなければならず、有限個の自然数だけでは足りない。
性質
帰納的集合からなる空でない族 $\{X_i\}_{i\in\Lambda}$ について、共通部分 $\bigcap_{i\in\Lambda}X_i$ は帰納的集合である。
$Y:=\bigcap_{i\in\Lambda}X_i$ とおく。各 $X_i$ が $\emptyset$ を含むので $\emptyset\in Y$。$x\in Y$ なら任意の $i$ について $x\in X_i$ であり、各 $X_i$ が帰納的集合なので $x^{+}\in X_i$、よって $x^{+}\in Y$。$\Lambda\neq\emptyset$ なので $Y$ は集合として定まる。$\square$
無限公理により帰納的集合 $I$ を一つ固定し、
$$
\omega:=\bigcap\{X\subset I\mid X\text{ は帰納的集合}\}
$$
とおく。このとき $\omega$ は帰納的集合であり、任意の帰納的集合 $X$ について $\omega\subset X$ が成り立つ。特に $\omega$ は $I$ の取り方によらない。$\omega$ の要素を自然数という。
$I$ 自身が $\{X\subset I\mid X\text{ は帰納的集合}\}$ に属するので、この族は空でなく、分出公理により $\omega$ は集合として定まる。prop-inductive-set-intersection により $\omega$ は帰納的集合である。任意の帰納的集合 $X$ に対し、$X\cap I$ は帰納的集合であり（prop-inductive-set-intersection）$I$ の部分集合なので、$\omega\subset X\cap I\subset X$ である。$I'$ を別の帰納的集合として同じ構成をした $\omega'$ についても、いま示したことから $\omega\subset\omega'$ かつ $\omega'\subset\omega$ なので $\omega=\omega'$ である。$\square$
$A\subset\omega$ が帰納的集合ならば $A=\omega$ である。すなわち、自然数についての性質 $P$ が $P(\emptyset)$ を満たし、$P(n)$ ならば $P(n^{+})$ を満たすなら、すべての自然数について $P$ が成り立つ。
$A$ は帰納的集合なので prop-inductive-set-omega により $\omega\subset A$、仮定 $A\subset\omega$ と合わせて $A=\omega$。後半は $A:=\{n\in\omega\mid P(n)\}$（分出公理で集合）に前半を適用すればよい。$\square$
$X$ を帰納的集合とする。$\{x\in X\mid x\subset X\}$ は帰納的集合である。特に $\omega$ は推移的である。すなわち $n\in\omega$ ならば $n\subset\omega$ である。
$T:=\{x\in X\mid x\subset X\}$ とおく（分出公理で集合）。$\emptyset\in X$ かつ $\emptyset\subset X$ なので $\emptyset\in T$。$x\in T$ とすると $x\in X$ かつ $x\subset X$ である。$X$ は帰納的なので $x^{+}\in X$。また $x^{+}=x\cup\{x\}\subset X$ は $x\subset X$ と $x\in X$ から従う。よって $x^{+}\in T$ であり、$T$ は帰納的集合である。
$X=\omega$ のとき $T\subset\omega$ は帰納的集合なので cor-inductive-set-induction により $T=\omega$、すなわち任意の $n\in\omega$ について $n\subset\omega$ である。$\square$
任意の帰納的集合 $X$ について $X\cap\mathsf{Ord}$ は帰納的集合である。これは $\emptyset$ が順序数であることと、順序数の後続者が順序数であることから従う（Jech03 第 2 章）。順序数の理論は本記事では扱わず、この主張は引用にとどめる。
補足：帰納的集合であるかどうかの判定例
| 集まり | 帰納的か | 根拠 |
|---|---|---|
| $\omega$ | はい（最小） | prop-inductive-set-omega |
| $\omega+\omega$ | はい | ex-inductive-set-larger |
| $1=\{\emptyset\}$、一般の $n\in\omega$ | いいえ | rem-inductive-set-counterexample |
| 帰納的集合の共通部分 | はい | prop-inductive-set-intersection |
| $\{x\in X\mid x\subset X\}$（$X$ 帰納的） | はい | prop-inductive-set-transitive |
| $\mathsf{Ord}$ | 帰納的クラス（集合でない） | ex-inductive-set-ordinals |
無限公理は帰納的集合の存在だけを主張する。その存在から最小の帰納的集合 $\omega$ が定まり、数学的帰納法の原理が定理として導かれる点が、この概念の役割である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
