後続者
概要
後続者（successor）とは、集合 $x$ に対し $x^{+}=x\cup\{x\}$ で定まる集合、すなわち $x$ 自身を新しい要素として付け加えて得られる集合のことである。$x$ は $x^{+}$ の要素でも部分集合でもあり、$x^{+}$ は空でないので、空集合はどの集合の後続者でもない。正則性公理のもとで $x^{+}=y^{+}$ ならば $x=y$ が成り立ち、$x,y$ がともに推移的な場合は $\bigcup x^{+}=x$ から正則性公理を使わずに同じ単射性が従う。$0=\emptyset$ から後続者を繰り返して $1=\{\emptyset\}$、$2=\{\emptyset,\{\emptyset\}\}$ と作る von Neumann の自然数の構成の土台になる。
定義
本記事は公理的集合論 ZF の枠組みで議論し、次の公理だけを使う。外延性公理（同じ要素をもつ二つの集合は等しい）、対集合公理（集合 $a,b$ に対し $a$ と $b$ だけを要素とする集合 $\{a,b\}$ が存在する）、和集合公理（集合 $A$ に対し、$A$ のどれかの要素の要素であるもの全体 $\bigcup A$ が集合として存在する）、空集合の存在、および正則性公理（空でない集合 $A$ には $a\cap A=\emptyset$ となる要素 $a\in A$ がある）である。正則性公理を使う主張はそのつど明示する。選択公理は使わない。
集合 $x$ に対し
$$x^{+}:=x\cup\{x\}$$
とおき、これを $x$ の後続者（successor）または後者という。$S(x)$ と書くこともある。
$x^{+}$ が集合として存在することは次のように確かめられる。対集合公理により $\{x\}=\{x,x\}$ が存在し、ふたたび対集合公理により $\{x,\{x\}\}$ が存在する。和集合公理により $\bigcup\{x,\{x\}\}$ が存在し、$z\in\bigcup\{x,\{x\}\}$ は「$z\in x$ または $z\in\{x\}$」、すなわち「$z\in x$ または $z=x$」と同値なので、$\bigcup\{x,\{x\}\}=x\cup\{x\}$ である。外延性公理により、この集合は $x$ から一意に定まる。
後で使う補助的な言葉を一つ用意する。
集合 $t$ が推移的（transitive）であるとは、$t$ の任意の要素が $t$ の部分集合であること、すなわち $z\in t$ ならば $z\subset t$ が成り立つことをいう。
直感
後続者は、$x$ の要素をすべて残したまま、$x$ 自身をちょうど一つ新しい要素として付け加える操作である（$x$ が $x$ の要素でないことは正則性公理による。prop-successor-proper）。加える要素が $x$ 自身であるため、$x$ は $x^{+}$ の要素であると同時に部分集合でもあるという、ふつうの「次の数」にはない二重の関係が生じる。$\emptyset$ から出発してこの操作を繰り返すと $\emptyset,\ \{\emptyset\},\ \{\emptyset,\{\emptyset\}\},\dots$ が得られ、これが von Neumann による自然数の構成である（ex-successor-naturals、Jech03 第 1 章）。
例と反例
$0:=\emptyset$、$1:=0^{+}$、$2:=1^{+}$、$3:=2^{+}$ とおくと
$$1=\emptyset\cup\{\emptyset\}=\{\emptyset\}=\{0\},$$
$$2=1\cup\{1\}=\{\emptyset\}\cup\{\{\emptyset\}\}=\{\emptyset,\{\emptyset\}\}=\{0,1\},$$
$$3=2\cup\{2\}=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}=\{0,1,2\}$$
である。この四つはどれも「自分より前のものをすべて集めた集合」$n=\{0,1,\dots,n-1\}$ の形をしている。実際に相異なる：$0=\emptyset$ は要素をもたないが $1,2,3$ はもつので $0$ は他の三つと異なる。$1\neq2$ である（$1\in2$ だが $1\notin1$。$1$ の唯一の要素は $0$ で $0\neq1$ だからである）。$2\neq3$ である（$2\in3$ だが $2\notin2$。$2$ の要素は $0$ と $1$ で、どちらも $2$ と異なる）。$1\neq3$ である（$1\in3$ だが $1\notin1$）。したがって要素の個数はそれぞれ $0,1,2,3$ 個である。また $0$ は要素をもたないので推移的であり、prop-successor-transitive を繰り返せば $1,2,3$ も推移的である。これが von Neumann による自然数の構成である（Jech03 第 1 章）。
$x:=\{1\}=\{\{\emptyset\}\}$ とおく。$1\in x$ だが $0\in1$ かつ $0\notin x$（$x$ の唯一の要素は $1$ で、$0\neq1$）なので $1\not\subset x$ であり、$x$ は推移的でない。このとき
$$x^{+}=\{1\}\cup\{\{1\}\}=\{1,\{1\}\},\qquad \bigcup x^{+}=1\cup\{1\}=\{0,1\}=2$$
となり、$\bigcup x^{+}=2\neq\{1\}=x$ である（$0\in2$ だが $0\notin\{1\}$）。prop-successor-union の推移性の仮定は落とせない。
性質 $P$「$A$ は空でない」を満たすが、性質 $Q$「ある集合 $y$ について $A=y^{+}$ である」を満たさない集合として $A:=\{1\}=\{\{\emptyset\}\}$ がある。実際 $1\in A$ なので $A$ は空でない。もし $A=y^{+}$ なる $y$ があれば prop-successor-basic により $y\in y^{+}=A=\{1\}$ なので $y=1$ であるが、$1^{+}=2=\{0,1\}$ は $0$ を要素にもち、$\{1\}$ は $0$ を要素にもたない（$0\neq1$）ので $1^{+}\neq A$ となって矛盾する。したがって含意 $P\Rightarrow Q$ は成り立たない。空集合がどの集合の後続者でもないこと（cor-successor-not-surjective）と合わせると、後続者を取る操作は空集合を値にしないだけでなく、空でない集合の中にも値にならないものがあることが分かる。この反例に正則性公理は使っていない。
性質 $P$「$x\in y$」を満たすが、性質 $Q$「$x^{+}\in y^{+}$」を満たさない組として、$x:=0=\emptyset$、$y:=\{0,2\}$（対集合公理で存在する）がある。実際 $0\in y$ である。一方 $x^{+}=1=\{0\}$、$y^{+}=\{0,2,y\}$ であり、$1\neq0$（$1$ は要素 $0$ をもつが $0$ はもたない）、$1\neq2$（$1\in2$ だが $1$ の唯一の要素は $0$ で $0\neq1$ なので $1\notin1$）、$1\neq y$（$2\in y$ だが $1$ の唯一の要素は $0$ で $0\neq2$ なので $2\notin1$）だから $x^{+}=1\notin y^{+}$ である。したがって含意 $P\Rightarrow Q$ は成り立たない。ex-successor-naturals の $0,1,2,3$ の間では、$x\in y$ となる六つの組 $(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)$ のいずれについても $x^{+}\in y^{+}$ が成り立つ（$1\in2$、$1\in3$、$2\in3$ であり、$3^{+}=\{0,1,2,3\}$ は $1,2,3$ を要素にもつ）が、一般の集合では成り立たない。この反例に正則性公理は使っていない。
性質
任意の集合 $x$ と任意の $z$ について次が成り立つ。
- $z\in x^{+}$ であることと、$z\in x$ または $z=x$ であることは同値である。
- $x\in x^{+}$。
- $x\subset x^{+}$。
- $x^{+}=x\cup\{x\}$ なので、$z\in x^{+}$ は $z\in x$ または $z\in\{x\}$ と同値であり、$z\in\{x\}$ は $z=x$ と同値である。
- 1 で $z=x$ とすればよい。
- $z\in x$ ならば 1 より $z\in x^{+}$ である。$\square$
任意の集合 $x$ について $x^{+}\neq\emptyset$ である。
prop-successor-basic の 2 より $x\in x^{+}$ であるから $x^{+}$ は要素をもつ。$\emptyset$ は要素をもたないので、外延性公理により $x^{+}\neq\emptyset$ である。$\square$
$y^{+}=\emptyset$ となる集合 $y$ は存在しない。すなわち、空集合はどの集合の後続者でもない。
そのような $y$ があれば prop-successor-nonempty に反する。$\square$
（正則性公理を使う。）任意の集合 $x$ について $x\notin x$ である。したがって $x\subsetneq x^{+}$、とくに $x\neq x^{+}$ である。
対集合公理により $\{x\}$ を作る。$x\in\{x\}$ なので $\{x\}\neq\emptyset$ であり、正則性公理により $a\cap\{x\}=\emptyset$ となる $a\in\{x\}$ がある。$\{x\}$ の要素は $x$ だけなので $a=x$、すなわち $x\cap\{x\}=\emptyset$ である。もし $x\in x$ なら $x\in x$ かつ $x\in\{x\}$ より $x\in x\cap\{x\}$ となって矛盾する。よって $x\notin x$ である。
次に prop-successor-basic の 3 より $x\subset x^{+}$ である。もし $x=x^{+}$ なら、prop-successor-basic の 2 より $x\in x^{+}=x$ となり、いま示した $x\notin x$ に反する。よって $x\neq x^{+}$ であり、包含は真である。$\square$
$x$ が推移的ならば $x^{+}$ も推移的である。
$z\in x^{+}$ とする。prop-successor-basic の 1 より $z\in x$ または $z=x$ である。$z\in x$ のときは $x$ の推移性より $z\subset x$ であり、prop-successor-basic の 3 と合わせて $z\subset x\subset x^{+}$ である。$z=x$ のときも prop-successor-basic の 3 より $z=x\subset x^{+}$ である。いずれの場合も $z\subset x^{+}$ なので、$x^{+}$ は推移的である。$\square$
$x$ が推移的ならば $\bigcup x^{+}=x$ である。この主張の証明に正則性公理は使わない。
まず任意の集合 $A,B$ について $\bigcup(A\cup B)=\left(\bigcup A\right)\cup\left(\bigcup B\right)$ である。実際、$z\in\bigcup(A\cup B)$ は「ある $a\in A\cup B$ について $z\in a$」、すなわち「ある $a\in A$ について $z\in a$、またはある $a\in B$ について $z\in a$」と同値だからである。また $\bigcup\{x\}=x$ である。これらから
$$\bigcup x^{+}=\bigcup(x\cup\{x\})=\left(\bigcup x\right)\cup x$$
を得る。$x$ が推移的なら $\bigcup x\subset x$ である。実際 $z\in\bigcup x$ とすると、ある $w\in x$ について $z\in w$ であり、推移性より $w\subset x$ なので $z\in x$ である。よって $\left(\bigcup x\right)\cup x=x$ であり、$\bigcup x^{+}=x$ である。$\square$
$x,y$ を推移的な集合とする。$x^{+}=y^{+}$ ならば $x=y$ である。この主張の証明に正則性公理は使わない。
prop-successor-union を二度使って
$$x=\bigcup x^{+}=\bigcup y^{+}=y$$
を得る。$\square$
（正則性公理を使う。）任意の集合 $x,y$ について、$x^{+}=y^{+}$ ならば $x=y$ である。
$x^{+}=y^{+}$ とする。prop-successor-basic の 2 より $x\in x^{+}=y^{+}$ であり、同じ命題の 1 より $x\in y$ または $x=y$ である。同様に $y\in y^{+}=x^{+}$ から $y\in x$ または $y=x$ である。
$x\neq y$ と仮定する。すると $x\in y$ かつ $y\in x$ である。対集合公理により $A:=\{x,y\}$ を作ると $A\neq\emptyset$ なので、正則性公理により $a\cap A=\emptyset$ となる $a\in A$ がある。$a=x$ ならば $y\in x$ かつ $y\in A$ より $y\in x\cap A$ となって $x\cap A=\emptyset$ に反する。$a=y$ ならば $x\in y$ かつ $x\in A$ より $x\in y\cap A$ となって同様に反する。$A$ の要素は $x$ と $y$ だけなので、いずれにしても矛盾である。よって $x=y$ である。$\square$
prf-successor-injective が正則性公理から取り出したのは、$x\in y$ と $y\in x$ が同時に成り立つことはない、という事実だけである。逆に、$x=\{y\}$ かつ $y=\{x\}$ となる相異なる集合 $x,y$ があったとすると
$$x^{+}=\{y\}\cup\{x\}=\{x,y\},\qquad y^{+}=\{x\}\cup\{y\}=\{x,y\}$$
となるので $x^{+}=y^{+}$ かつ $x\neq y$ となり、単射性が破れる。この計算自体に正則性公理は使っていない。正則性公理は、このような $x,y$ が存在しないことを保証する（$\{x,y\}$ が $a\cap\{x,y\}=\emptyset$ となる要素 $a$ をもたないため）。すなわち一般の集合について単射性を示すには、帰属関係の 2 巡回を排除する仮定が要る。一方 prop-successor-injective-transitive は、推移的な集合に限れば正則性公理なしで単射性が言えることを示している。なお、上のような $x,y$ はどちらも推移的でない。実際 $x$ が推移的なら、$y\in x$ より $y\subset x$ であり、$x\in y$（$y=\{x\}$ による）と合わせて $x\in x$、すなわち $x\in\{y\}$ となるので $x=y$ となり、$x\neq y$ に反する。$y$ についても同様である。したがって prop-successor-injective-transitive と矛盾しない。
補足：他の記事との分担と、使った公理のまとめ
$\emptyset$ を要素にもち後続者を取る操作で閉じている集合を帰納的集合といい、その存在を主張するのが無限公理である。帰納的集合の定義、無限公理、最小の帰納的集合 $\omega$（自然数全体）の存在、そこから導かれる数学的帰納法の原理は 帰納的集合 の記事が扱う。本記事はこれらを再掲しない。順序数論では順序数 $\alpha$ の後続者 $\alpha\cup\{\alpha\}$ を $\alpha+1$ と書き、この形の順序数を後続順序数という（Jech03 第 2 章）。順序数そのものについては 順序数 を参照。
使った公理を整理すると次のようになる。prop-successor-basic、prop-successor-nonempty、cor-successor-not-surjective、prop-successor-transitive、prop-successor-union、prop-successor-injective-transitive と二つの反例は、外延性公理・対集合公理・和集合公理（および具体例のための空集合の存在）だけで得られ、正則性公理を使わない。正則性公理を使うのは prop-successor-proper と prop-successor-injective の二つの命題、および rem-successor-cycle で「そのような $x,y$ は存在しない」と述べるところの、計三箇所である。選択公理はどこにも使わない。したがって、正則性公理を仮定しない体系でも、推移的な集合の範囲では後続者を取る操作は単射である。
