推移的集合
概要
推移的集合（transitive set）とは、元がすべて部分集合でもある集合、すなわち $y\in x\in A$ ならば $y\in A$ となる集合 $A$ のことであり、$\bigcup A\subset A$ とも言い換えられる。順序数・自然数・累積階層の各段階は推移的で、任意の集合はそれを含む最小の推移的集合である推移閉包をもつ。正則性公理のもとでは、推移的でその元もすべて推移的な集合はちょうど順序数であり、整礎的で外延的な関係はすべてある推移的集合の上の所属関係と同型になる（Mostowski の崩壊定理）。推移的集合の中では有界な論理式の真偽が変わらないので、集合論のモデルを作るときの基本的な枠組みになる。
公理的集合論では、すべての対象が集合であり、集合の元もまた集合である。そのため「$x$ は $A$ の元である」と「$x$ は $A$ の部分集合である」が同じ対象について同時に問題になる。推移的集合 とは、元がすべて部分集合でもある集合、言い換えると「元の元はまた元である」集合のことである。
推移的集合は集合論のいたるところに現れる。順序数は $\in$ で整列された推移的集合として定義され、累積階層の各段階 $V_\alpha$ も推移的である。推移的集合 $M$ の中では、所属関係 $\in$ が外の世界と同じ形で見えるので、$M$ を集合論のモデルとして扱うときの基本的な枠組みになる。さらに Mostowski の崩壊定理により、整礎的で外延的な二項関係はすべて、ある推移的集合の上の $\in$ と同型になる。
この記事では、推移的集合の言い換えと作り方を確かめ、順序数を推移性だけで特徴づける定理と、Mostowski の崩壊定理を証明する。
定義
以下ではZFC公理系から選択公理を除いた体系 $\mathsf{ZF}$ で議論する。正則性公理（正則性公理）を使う箇所ではそのことを明記する。
集合 $A$ が 推移的（transitive）であるとは、$A$ の任意の元が $A$ の部分集合であること、すなわち
$$
y\in x\in A\ \Longrightarrow\ y\in A
$$
が成り立つことをいう。推移的な集合を 推移的集合（transitive set）という。
「推移的」という名は、所属関係 $\in$ を $A$ の上の関係と見たとき、$y\in x$ と $x\in A$ から $y\in A$ が出るという、推移律に似た形から来ている。$\in$ そのものが $A$ 上で推移律を満たすこと（$z\in y\in x$ かつ $x,y,z\in A$ なら $z\in x$）とは別の条件である。
集合 $A$ について、次は同値である。
- $A$ は推移的である。
- $\bigcup A\subset A$ である。
- $A\subset\mathcal P(A)$ である。
1 と 3 は定義の書き換えである（$x\in A$ なら $x\subset A$、すなわち $x\in\mathcal P(A)$）。
1 ⇒ 2：$y\in\bigcup A$ なら $y\in x$ となる $x\in A$ があり、推移性から $y\in A$ である。
2 ⇒ 1：$y\in x\in A$ なら $y\in\bigcup A\subset A$ である。$\square$
1 と 2 の同値は和集合の命題「推移的集合の和による特徴づけ」でも示されている。
例と反例
- 空集合 $\emptyset$ は元をもたないので推移的である。
- $\{\emptyset\}$、$\{\emptyset,\{\emptyset\}\}$ は推移的である。元 $\emptyset$ は何の部分集合でもあり、$\{\emptyset\}\subset\{\emptyset,\{\emptyset\}\}$ である。
- $\{\{\emptyset\}\}$ は推移的でない。$\emptyset\in\{\emptyset\}\in\{\{\emptyset\}\}$ だが $\emptyset\notin\{\{\emptyset\}\}$ である。
- $t:=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\}\}$ は推移的である（各元の元は $\emptyset$ か $\{\emptyset\}$ で、どちらも $t$ に入る）。しかし $\emptyset$ と $\{\{\emptyset\}\}$ はどちらも他方の元でないので、$t$ は $\in$ で全順序にならず、順序数ではない（順序数の注意「反例：順序数でない集合」）。
集合 $x$ の後続者 $x^+:=x\cup\{x\}$ を使い、$0:=\emptyset$、$n+1:=n^+$ と自然数を作ると（帰納的集合）、各自然数 $n$ と自然数全体 $\omega$ は推移的である。
$\omega$ について：$I:=\{n\in\omega\mid n\subset\omega\}$ とおく。$0=\emptyset\subset\omega$ なので $0\in I$。$n\in I$ なら $n\subset\omega$ かつ $n\in\omega$ なので $n^+=n\cup\{n\}\subset\omega$ であり、$\omega$ は後続者で閉じているので $n^+\in I$。$I$ は帰納的集合で $\omega$ は最小の帰納的集合なので $I=\omega$、すなわち $\omega$ の元はすべて $\omega$ の部分集合である。
各自然数について：$x$ が推移的なら $x^+$ も推移的であることを prop-ts-operations の 2 で示す。$\{n\in\omega\mid n\text{ は推移的}\}$ はこれにより帰納的集合なので $\omega$ に等しい。
- 累積階層 $V_0=\emptyset$、$V_{\alpha+1}=\mathcal P(V_\alpha)$、極限 $\lambda$ で $V_\lambda=\bigcup_{\beta<\lambda}V_\beta$ の各段階は推移的である（超限帰納法の命題「累積階層の各段階は推移的」）。
- 無限基数 $\kappa$ について、推移閉包（下の def-ts-closure）の濃度が $\kappa$ 未満の集合全体を $H(\kappa)$ と書く。$H(\kappa)$ は、正則性公理のもとで集合であり（Kun80 Chapter IV, Lemma 6.2。この記事では証明しない）、推移的である。実際 $y\in x\in H(\kappa)$ なら prop-ts-closure の 3 により $\operatorname{trcl}(y)\subset\operatorname{trcl}(x)$ なので、$\operatorname{trcl}(y)$ の濃度も $\kappa$ 未満である。Δ-システムの記事の別証明に現れる $H(\chi)$ はこの形の集合である。
推移的集合を作る操作
- 推移的集合からなる集合 $\mathcal T$ について、$\bigcup\mathcal T$ は推移的である。$\mathcal T\neq\emptyset$ なら $\bigcap\mathcal T$ も推移的である。
- $A$ が推移的なら、$A^+=A\cup\{A\}$、$\mathcal P(A)$、$\bigcup A$ も推移的である。
どの場合も、元の元がどこに属するかを定義に戻って確かめればよい。
詳細
1. $y\in x\in\bigcup\mathcal T$ なら $x\in T$ となる $T\in\mathcal T$ があり、$T$ の推移性から $y\in T\subset\bigcup\mathcal T$。$y\in x\in\bigcap\mathcal T$ なら、各 $T\in\mathcal T$ で $x\in T$ なので $y\in T$、よって $y\in\bigcap\mathcal T$。
2. $A^+$：$y\in x\in A^+$ とする。$x\in A$ なら $y\in A$、$x=A$ なら $y\in A$ であり、いずれも $y\in A^+$。
$\mathcal P(A)$：$y\in x\in\mathcal P(A)$ なら $x\subset A$ なので $y\in A$、さらに $A$ の推移性から $y\subset A$、すなわち $y\in\mathcal P(A)$。
$\bigcup A$：$y\in x\in\bigcup A$ なら $x\in z\in A$ となる $z$ がある。推移性から $x\in A$ なので $y\in\bigcup A$。$\square$
一般の集合 $a$ に対しては、$a$ を含む最小の推移的集合がある。
集合 $a$ に対し、$\omega$ 上の再帰で $\bigcup^0a:=a$、$\bigcup^{n+1}a:=\bigcup\bigl(\bigcup^na\bigr)$ と定め、
$$
\operatorname{trcl}(a):=\bigcup_{n\in\omega}\textstyle\bigcup^na=a\cup\bigcup a\cup\bigcup\bigcup a\cup\cdots
$$
を $a$ の 推移閉包（transitive closure）という。
$\operatorname{trcl}(a)$ は「$a$ の元、元の元、元の元の元、…」をすべて集めた集合である。正則性公理の定義「推移閉包」と同じものであり、そこで $\operatorname{trcl}(a)$ が $a$ を含む推移的集合で、$a$ を含むどの推移的集合にも含まれることが示されている。
- $\operatorname{trcl}(a)$ は $a$ を部分集合として含む最小の推移的集合である。
- $a$ が推移的であることと $\operatorname{trcl}(a)=a$ は同値である。
- $x\in a$ なら $\operatorname{trcl}(x)\subset\operatorname{trcl}(a)$ である。
- $\operatorname{trcl}(a)=a\cup\bigcup\{\operatorname{trcl}(x)\mid x\in a\}$ である。
1 は $\bigcup^na$ についての帰納法、2〜4 は 1 の最小性から従う。
詳細
1. $y\in x\in\bigcup^na$ なら $y\in\bigcup^{n+1}a$ なので $\operatorname{trcl}(a)$ は推移的で、$n=0$ の項から $a\subset\operatorname{trcl}(a)$。$T$ が $a$ を含む推移的集合なら、$\bigcup^na\subset T$ から prop-ts-equivalent の 2 により $\bigcup^{n+1}a\subset\bigcup T\subset T$ であり、$n$ についての帰納法で $\operatorname{trcl}(a)\subset T$。
2. $a$ が推移的なら 1 で $T=a$ として $\operatorname{trcl}(a)\subset a$、逆の包含は 1 から。逆に $\operatorname{trcl}(a)=a$ なら 1 により $a$ は推移的である。
3. $x\in a\subset\operatorname{trcl}(a)$ で $\operatorname{trcl}(a)$ は推移的なので $x\subset\operatorname{trcl}(a)$。1 を $x$ に適用して $\operatorname{trcl}(x)\subset\operatorname{trcl}(a)$。
4. 右辺を $T$ とおく。各 $\operatorname{trcl}(x)$ は推移的で、$x\in a$ について $x\subset\operatorname{trcl}(x)\subset T$ なので、$y\in x\in a$ なら $y\in T$。$y\in z\in\operatorname{trcl}(x)$ なら $y\in\operatorname{trcl}(x)$。よって $T$ は $a$ を含む推移的集合で、1 から $\operatorname{trcl}(a)\subset T$。逆の包含は 3 による。$\square$
順序数との関係
順序数は「推移的で、$\in$ によって整列された集合」と定義される。順序数 $\alpha,\beta$ について $\beta<\alpha$ は $\beta\in\alpha$ のことなので、推移性は「$\alpha$ より小さい順序数より小さいものは、また $\alpha$ より小さい」という下に閉じた性質を表している。
順序数からなる集合 $X$ について、次は同値である。
- $X$ は推移的である。
- $X$ は下に閉じている。すなわち $\alpha\in X$ で $\beta$ が順序数、$\beta<\alpha$ なら $\beta\in X$ である。
- $X$ は順序数である。
1 ⇒ 2：$\beta<\alpha\in X$ は $\beta\in\alpha\in X$ のことなので、推移性から $\beta\in X$。
2 ⇒ 1：$y\in\alpha\in X$ なら、順序数の元は順序数なので $y$ は $y<\alpha$ を満たす順序数であり、2 から $y\in X$。
1 ⇔ 3：順序数からなる推移的集合は順序数である（順序数の命題「順序数の集まりの整列性と上限」の 2）。逆に順序数は定義により推移的である。$\square$
選択公理の記事の補題「Hartogsの補題」の証明と Hartogs数の記事は、ある順序数の集合が下に閉じていることを確かめてから、この命題でそれ自身が順序数であると結論している。
正則性公理を仮定すると、整列性の条件は推移性と比較可能性だけから従う。
正則性公理を仮定する。集合 $x$ について、次は同値である。
(a) $x$ は順序数である。
(b) $x$ は推移的で、$x$ の元はすべて推移的である。
(c) $x$ は推移的で、任意の $y,z\in x$ について $y\in z$、$y=z$、$z\in y$ のいずれかが成り立つ。
(a) ⇒ (b)：順序数の元は順序数であり（順序数の命題「順序数の基本性質」の 2）、順序数は推移的である。(a) ⇒ (c) は順序数の定義に含まれる。
(c) ⇒ (a)：$x$ 上の関係 $\in$ が整列順序であることを示す。正則性公理により、$x$ の空でない部分集合 $S$ は $\in$-極小元 $m$（$m\cap S=\emptyset$ となる $m\in S$）をもつ。
- 非反射律：$y\in y$ となる $y$ があれば、$\{y\}$ の $\in$-極小元は $y$ しかないが $y\in y\cap\{y\}$ となり矛盾する。
- 推移律：$y\in z\in w$（$y,z,w\in x$）とする。比較可能性から $y\in w$、$y=w$、$w\in y$ のいずれかである。$y=w$ なら $\{y,z\}$ の元はどちらも他方を元にもつので $\in$-極小元がなく、$w\in y$ なら同様に $\{y,z,w\}$ に $\in$-極小元がない。よって $y\in w$。
- 最小元：空でない $S\subset x$ の $\in$-極小元 $m$ をとる。$s\in S$、$s\neq m$ なら比較可能性から $s\in m$ か $m\in s$ だが、$s\in m$ は極小性に反するので $m\in s$。$m$ は $S$ の最小元である。
よって $x$ は推移的で $\in$ により整列されており、順序数である。
(b) ⇒ (c)：まず、$x$ の元 $y$ も (b) を満たす。$y$ は推移的で、$y$ の元は $x$ の推移性から $x$ の元なので推移的だからである。$y,z\in x$ が比較可能でないとき「$y,z$ は食い違う」ということにする。食い違う組があると仮定し、
$$ U:=\{a\in x\mid a\text{ と食い違う }b\in x\text{ がある}\} $$
の $\in$-極小元 $a$ をとり、$V:=\{b\in x\mid a\text{ と }b\text{ は食い違う}\}$ の $\in$-極小元 $b$ をとる。
$a\subset b$ を示す。$c\in a$ とすると $c\in x$ で、$a$ の極小性から $c\notin U$、よって $c$ と $b$ は比較可能である。$c=b$ なら $b\in a$、$b\in c$ なら $a$ の推移性から $b\in a$ となり、どちらも $a,b$ が食い違うことに反する。よって $c\in b$。
$b\subset a$ を示す。$c\in b$ とすると $c\in x$ で、$b$ の極小性から $c\notin V$、よって $c$ と $a$ は比較可能である。$c=a$ なら $a\in b$、$a\in c$ なら $b$ の推移性から $a\in b$ となり、どちらも矛盾する。よって $c\in a$。
外延性から $a=b$ となるが、これは $a$ と $b$ が食い違う（とくに $a\neq b$）ことに反する。よって食い違う組はなく、(c) が成り立つ。$\square$
条件 (c) は「$x$ の元についての有界な量化」だけで書けている。このことは後の cor-ts-ordinal-absolute で使う。
Mostowski の崩壊定理
推移的集合の上の $\in$ には、二つの性質が自動的に備わる。正則性公理のもとで $\in$ は整礎的であり、また推移的集合 $M$ の元 $x$ について $x$ の元はすべて $M$ にあるので、$M$ の中で同じ元をもつ二つの元は等しい（外延的）。Mostowski の崩壊定理は、逆にこの二つの性質をもつ関係が、必ずある推移的集合の上の $\in$ として実現されることを述べる。
集合 $A$ 上の二項関係 $R$ について、
- $R$ が 整礎的（well-founded）であるとは、$A$ の空でない任意の部分集合 $S$ が $R$-極小元（$m\in S$ で、$yRm$ となる $y\in S$ がないもの）をもつことをいう。
- $R$ が 外延的（extensional）であるとは、$x,y\in A$ が「すべての $z\in A$ について $zRx\iff zRy$」を満たすなら $x=y$ となることをいう。
$A$ の部分集合 $C$ が 下に閉じている とは、$x\in C$ かつ $yRx$（$y\in A$）なら $y\in C$ となることとする。
$R$ を集合 $A$ 上の整礎的な関係とする。
- $A$ 上の関数 $\pi$ で、すべての $x\in A$ について
$$ \pi(x)=\{\pi(y)\mid y\in A,\ yRx\} $$
を満たすものがただ一つ存在する。 - 像 $M:=\pi[A]$ は推移的集合であり、$xRy$ なら $\pi(x)\in\pi(y)$ である。
- $R$ が外延的なら、$\pi$ は単射で、$x,y\in A$ について $xRy\iff\pi(x)\in\pi(y)$ が成り立つ。すなわち $\pi$ は $(A,R)$ から $(M,\in)$ への同型である。
- $R$ が外延的なとき、$(A,R)$ と $(N,\in)$ が同型になる推移的集合 $N$ は $M$ だけであり、同型写像は $\pi$ だけである。
この定理は正則性公理を使わない。$\pi$ を 崩壊写像（collapsing map）、$M$ を $(A,R)$ の Mostowski 崩壊（Mostowski collapse）という。
下に閉じた $C\subset A$ 上の関数 $\sigma$ が、すべての $x\in C$ で $\sigma(x)=\{\sigma(y)\mid yRx\}$ を満たすとき、$\sigma$ を $C$ 上の部分崩壊 と呼ぶ（$C$ は下に閉じているので右辺の $y$ はすべて $C$ に入る）。
一致。 $\sigma,\sigma'$ をそれぞれ $C,C'$ 上の部分崩壊とすると、$C\cap C'$ 上で $\sigma=\sigma'$ である。実際、$D:=\{x\in C\cap C'\mid\sigma(x)\neq\sigma'(x)\}$ が空でないとし、その $R$-極小元 $x$ をとる。$yRx$ なら $y\in C\cap C'$（両方とも下に閉じている）で、極小性から $\sigma(y)=\sigma'(y)$。よって $\sigma(x)=\{\sigma(y)\mid yRx\}=\{\sigma'(y)\mid yRx\}=\sigma'(x)$ となり矛盾する。特に、各 $C$ 上の部分崩壊は高々一つである。
存在。 部分崩壊をもつ下に閉じた集合の全体を $\mathcal D\subset\mathcal P(A)$ とする（分出公理）。各 $C\in\mathcal D$ に $C$ 上のただ一つの部分崩壊 $\sigma_C$ を対応させ、置換公理で集合 $\{\sigma_C\mid C\in\mathcal D\}$ を作り、その合併を $\pi$ とおく。一致の主張により $\pi$ は関数であり、定義域 $D^*:=\bigcup\mathcal D$ は下に閉じていて、$\pi$ は $D^*$ 上の部分崩壊である。$D^*\neq A$ と仮定し、$A\setminus D^*$ の $R$-極小元 $x$ をとる。$yRx$ なら $y\in D^*$ なので、$C:=D^*\cup\{x\}$ は下に閉じている。$\pi$ に対 $\bigl(x,\{\pi(y)\mid yRx\}\bigr)$ を付け加えた関数は $C$ 上の部分崩壊なので $C\in\mathcal D$、よって $x\in D^*$ となり矛盾する。したがって $D^*=A$ で、$\pi$ は 1 の条件を満たす。一意性は一致の主張から従う。
2。 $u\in\pi(x)\in M$ なら $u=\pi(y)$（$yRx$）なので $u\in M$。$xRy$ なら定義から $\pi(x)\in\pi(y)$。
3。 $\pi$ が単射でないとし、$E:=\{x\in A\mid x\neq y\text{ かつ }\pi(x)=\pi(y)\text{ となる }y\in A\text{ がある}\}$ の $R$-極小元 $x$ と、$x\neq y$、$\pi(x)=\pi(y)$ となる $y$ をとる。外延性から、次のどちらかが成り立つ。
- $zRx$ かつ $zRy$ でない $z$ がある。$\pi(z)\in\pi(x)=\pi(y)$ なので $\pi(z)=\pi(w)$ となる $w$（$wRy$）がある。$zRy$ でないので $w\neq z$、よって $z\in E$ で $zRx$ となり、$x$ の極小性に反する。
- $wRy$ かつ $wRx$ でない $w$ がある。$\pi(w)\in\pi(y)=\pi(x)$ なので $\pi(w)=\pi(z)$ となる $z$（$zRx$）がある。$w\neq z$ なので $z\in E$ で $zRx$ となり、同じく矛盾する。
よって $\pi$ は単射である。$\pi(x)\in\pi(y)$ なら $\pi(x)=\pi(z)$ となる $zRy$ があり、単射性から $x=z$、すなわち $xRy$ である。
4。 $\rho\colon(A,R)\to(N,\in)$ を推移的集合 $N$ への同型とする。$yRx$ なら $\rho(y)\in\rho(x)$。逆に $u\in\rho(x)$ なら $N$ の推移性から $u\in N$、すなわち $u=\rho(y)$ と書けて、$\rho(y)\in\rho(x)$ から $yRx$。よって $\rho(x)=\{\rho(y)\mid yRx\}$ であり、1 の一意性から $\rho=\pi$、$N=\rho[A]=M$ である。$\square$
$(W,<)$ を整列集合とすると、その Mostowski 崩壊はただ一つの順序数であり、崩壊写像は $(W,<)$ からその順序数への順序同型である。
整列順序は整礎的であり、全順序なので外延的でもある（$x< y$ なら $z=x$ について $z< y$ だが $z< x$ でない）。thm-ts-mostowski の 3 により $(W,<)$ は推移的集合 $M$ 上の $(M,\in)$ と同型であり、$M$ は $\in$ で整列された推移的集合、すなわち順序数である。一意性は 4 による。$\square$
これは順序数の定理「整列集合の順序数による表現」を、崩壊定理の特別な場合として捉え直したものである。
- $A=\{0,2,4,6\}\subset\mathbb N$ に通常の順序 $<$ を入れると、$\pi(0)=\emptyset=0$、$\pi(2)=\{0\}=1$、$\pi(4)=\{0,1\}=2$、$\pi(6)=3$ で、崩壊は順序数 $4$ である。
- $A=\{a,b,c,d\}$ に $aRb$、$bRc$、$aRd$、$cRd$ だけを入れる。$yRx$ となる $y$ の集合は $a,b,c,d$ についてそれぞれ $\emptyset$、$\{a\}$、$\{b\}$、$\{a,c\}$ で互いに異なるので $R$ は外延的であり、有限で輪がないので整礎的である。崩壊写像は
$$ \pi(a)=\emptyset,\quad\pi(b)=\{\emptyset\},\quad\pi(c)=\{\{\emptyset\}\},\quad\pi(d)=\{\emptyset,\{\{\emptyset\}\}\} $$
で、$M=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\{\emptyset\}\}\}\}$ は推移的だが順序数ではない（$\emptyset$ と $\{\{\emptyset\}\}$ はどちらも他方の元でない）。
推移的集合の中で見る論理式
推移的集合 $M$ を、所属関係 $\in$ をそのまま使った構造 $(M,\in)$ と見て、集合論の論理式がそこで成り立つかを考える。量化を $M$ の元に制限するので、一般には $M$ の中での真偽と本当の真偽は一致しない。しかし、$\forall y\in x$、$\exists y\in x$ という形の有界な量化だけで書かれた論理式については、推移的な $M$ の中での真偽は本当の真偽と一致する（集合論の命題「有界な論理式の真偽は推移的集合で変わらない」、内部モデルの補題「有界な論理式の絶対性」）。$x$ の元はすべて $M$ にあるので、「$x$ の元を調べる」操作が $M$ の中でも外でも同じになるからである。外延性公理も推移的な $M$ の中で自動的に成り立つ（内部モデルの系「推移的なクラスで自動的に成り立つ公理」）。
正則性公理を仮定する。$M$ を推移的集合、$x\in M$ とし、
$$
\psi(x):\quad\forall y\in x\ \forall z\in y\ (z\in x)\ \land\ \forall y\in x\ \forall z\in x\ (y\in z\lor y=z\lor z\in y)
$$
とおく。$(M,\in)$ で $\psi(x)$ が成り立つことと、$x$ が順序数であることは同値である。
$\psi$ は有界な量化だけで書かれているので、$M$ が推移的であることから、$(M,\in)$ で $\psi(x)$ が成り立つことと $\psi(x)$ が本当に成り立つことは同値である。$\psi(x)$ は thm-ts-ordinal-characterization の (c) そのものなので、$x$ が順序数であることと同値である。$\square$
順序数の定義そのもの（「$\in$ で整列されている」）は $x$ の部分集合全体についての量化を含み、有界でない。正則性公理のもとで thm-ts-ordinal-characterization がそれを有界な条件 (c) に置き換えたことで、この系が得られる。集合論のモデルを推移的集合として作ることが多いのは、こうして基本的な概念がモデルの中でも外でも同じ意味をもつからである。
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| prop-ts-ordinal-sets の「$X$ の元はすべて順序数」 | $t=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\}\}$ | 推移的だが順序数でない |
| thm-ts-ordinal-characterization (c) の「$x$ は推移的」 | $x=\{\{\emptyset\}\}$ | 元は推移的で互いに比較可能だが、順序数でない |
| thm-ts-mostowski の「$R$ は整礎的」 | 整数全体 $(\mathbb Z,<)$ | 推移的集合の上の $\in$ と同型にならない（正則性公理のもと） |
| thm-ts-mostowski 3 の「$R$ は外延的」 | $A=\{a,b\}$、$R=\emptyset$ | 崩壊写像が単射でなく、推移的集合の上の $\in$ と同型にならない |
1 行目：ex-ts-small の 4 による。
2 行目：$x$ のただ一つの元 $\{\emptyset\}$ は推移的で、比較可能性の条件は一つの元については自明に成り立つ。しかし $\emptyset\in\{\emptyset\}\in x$ かつ $\emptyset\notin x$ なので $x$ は推移的でなく、順序数でない。
3 行目：$<$ は全順序なので外延的である（cor-ts-well-order の証明と同じ理由）。推移的集合 $N$ への同型 $\rho$ があれば、正則性公理により空でない $\rho[\mathbb Z]\subset N$ は $\in$-極小元 $\rho(n)$ をもち、$\rho(n-1)\in\rho(n)$ と $\rho(n-1)\in\rho[\mathbb Z]$ に反する。
4 行目：$\pi(a)=\pi(b)=\emptyset$ である。推移的集合 $N$ の上の $\in$ は外延的であり（$x,y\in N$ の元はすべて $N$ にあるので、$N$ の中で同じ元をもてば $x=y$）、同型は外延性を保つが、$R=\emptyset$ のとき $a\neq b$ はどちらも前者をもたないので外延的でない。
正則性公理を外すと thm-ts-ordinal-characterization の (b)・(c) から (a) が従う保証はなくなる。$x=\{x\}$ を満たす集合 $x$ があったとすると、$x$ は推移的で、ただ一つの元 $x$ も推移的で、比較可能性も満たすが、$x\in x$ なので順序数ではない。正則性公理はこのような集合を排除する。
補足
推移的なクラス
集合に限らず、論理式で定まるクラス $\mathbf C$ についても「$y\in x\in\mathbf C$ なら $y\in\mathbf C$」を推移的という。順序数全体 $\mathrm{Ord}$、集合全体 $V$、構成可能宇宙 $L$ は推移的なクラスであり、内部モデルは推移的なクラスとして定義される。Mostowski の崩壊定理は、各元の前者全体が集合になる整礎的・外延的な関係をもつクラスにも同じ形で成り立つ（Kun80 Chapter III, Theorem 5.14）。この記事では集合の場合だけを証明した。
推移閉包と帰納法
推移閉包を使うと、論理式で定まるクラスにも $\in$-極小元があることが正則性公理から導かれ、すべての集合についての $\in$-帰納法が得られる（正則性公理の「推移閉包と所属関係についての帰納法」節）。崩壊定理の証明の「一致」の部分は、この $\in$-帰納法を関係 $R$ に置き換えた議論である。
参照箇所
- Kun80 Chapter I, §7, Definition 7.1（p. 16、推移的集合と例）。Chapter III, §3, Definition 3.4・Lemma 3.5（pp. 99–100、推移閉包）、§4, Theorem 4.2（p. 102、正則性公理のもとでの順序数の特徴づけ）、§5, Definition 5.9・Lemma 5.10–5.13・Theorem 5.14・Corollary 5.15（pp. 105–106、Mostowski の崩壊定理）、Chapter III の演習 (8)（p. 107、thm-ts-ordinal-characterization の同値）。Chapter IV, §6, Definition 6.1・Lemma 6.2・Lemma 6.4（pp. 130–131、$H(\kappa)$）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
