数学構成論第一部(6)
公理的集合論(5) 順序と順序数(2)
$\mathbb{N}$
集合$X$が以下の条件をみたすとき, inductive setであるという.
(1) $\varnothing \in X$
(2) $x \in X \Rightarrow x \cup \{x\} \in X$
$A = \{A_{\lambda}\}_{\lambda \in \Lambda}$をinductive setの族とする.
$\bigcap_{\lambda \in \Lambda} A_{\lambda}$はinductive set.
$A$はinductive setの族であるから, $\forall \lambda \in \Lambda [\varnothing \in A_{\lambda}]$が成り立つ.
ゆえに定義から$\varnothing \in \bigcap_{\lambda \in \Lambda}A_{\lambda}$.
\begin{align}
a \in A &\Leftrightarrow \forall \lambda \in \Lambda [a \in A_{\lambda}] \\
&\Rightarrow \forall \lambda \in \Lambda [a \cup \{a\} \in A_{\lambda}] \\
&\Rightarrow a \cup \{a\}\in \bigcap_{\lambda \in \Lambda}A_{\lambda}
\end{align}
よって, $\bigcap_{\lambda \in \Lambda}A_{\lambda}$はinductive set.
$\eta$をinductive setとする.
$A = \{x \in \eta \mid \forall \zeta:\text{inductive set} [x \in \zeta]\}$とおく.
$\bigcap A$は$\eta$のとりかたによらない.
$\eta, \theta$をinductive setとし, $B = \{x \in \theta \mid \forall \zeta':\text{inductive set} [x \in \zeta']\}, N = \bigcap A, M = \bigcap B$, $K = \eta \cap \theta$とおく.
命題により, $K$はinductive setである.
$N \subset K, M \subset K, K \subset \eta, K \subset \theta$が成り立つ.
$N \subset \theta, M \subset \eta$が導ける.
定義よりそれぞれ$M \subset N, N \subset M$が導ける.
よって$N = M$であり, $\eta$のとりかたによらない.
命題により, $\eta$をinductive setとして$\mathbb{N} \coloneqq \bigcap \{x \in \eta \mid \forall \zeta:\text{inductive set} [x \in \zeta]\}$と定めると, これは$\eta$のとりかたによらずただひとつ.また, 無限公理で存在が保証される$\infty_1$は定義よりinductive setであるから, inductive setは存在し, $\mathbb{N}$も存在する.
$\varnothing \in \mathbb{N}$を$0$, $\{\varnothing\} = \varnothing \cup \{\varnothing\} \in \mathbb{N}$を$1$と略記する.
写像$\text{suc}:\mathbb{N} \to \mathbb{N}$を$n \in \mathbb{N}$に対し$\text{suc}(n) \coloneqq n \cup \{n\}$と定める.$\text{suc}(n)$を$n$のsuccessorという.
$\mathbb{N}$について, 以下が成り立つ.
(1) $\forall n \in \mathbb{N} [\text{suc}(n) \neq 0]$
(2) $\forall A \subset \mathbb{N}:\text{inductive set}[A = \mathbb{N}]$
(3) $\psi$を自由変数をひとつもつ$L_{ZFC}$-論理式とするとき,
$(\psi(0) \land \forall x \in \mathbb{N} [\psi(x) \Rightarrow \psi(\text{suc}(x))]) \Rightarrow \forall n \in \mathbb{N} [\psi(n)]$ ($n$に関するinduction)
(4) $\forall n \in \mathbb{N} [n:\text{順序数}]$
(5) $\mathbb{N}:\text{順序数}$
(6) $\text{suc}:\text{inj.}$
- 定義より$n \in \text{suc}(n)$であるから, $\text{suc}(n) \neq \varnothing = 0$が成り立つ.
- $A \subset \mathbb{N}:\text{inductive set}$をとる.このとき命題で$\eta$のとりかたによらないことがわかるので, $\eta$として$A$を選ぶと, $\mathbb{N} \subset A$が成り立ち, よって$A = \mathbb{N}$が成り立つ.
- $\Psi = \{n \in \mathbb{N} \mid \psi(n)\}$とおき, $(\psi(0) \land \forall x \in \mathbb{N} [\psi(x) \Rightarrow \psi(\text{suc}(x))])$と仮定する.
仮定より, $0 \in \Psi \land \forall x \in \Psi [\text{suc}(x) \in \Psi]$が成り立つ.
これは$\Psi:\text{inductive set}$の定義そのもの.
定義より$\Psi \subset \mathbb{N}$であるから, (2)より$\Psi = \mathbb{N}$が成り立つ. - $n$に関するinductionを用いる.$\psi(n) :\Leftrightarrow n:\text{順序数}$と定める.
case1.$\psi(0)$
$0:\text{順序数}$である.
case2.$\psi(n) \Rightarrow \psi(\text{suc}(n))$
$n \in \mathbb{N}$に対し, $n:\text{順序数}$と仮定する.
このとき, 後続順序数が順序数であることから$\text{suc}(n):\text{順序数}$.
よって, $\forall n \in \mathbb{N} [n:\text{順序数}]$が成り立つ. - $n$に関するinductionを用いて, $\forall n \in \mathbb{N} [n \subset \mathbb{N}]$を証明する.
case1.$\psi(0)$
$\bot E$により$\varnothing \subset \mathbb{N}$が成り立つ.
case2.$\psi(n) \Rightarrow \psi(\text{suc}(n))$
$n \in \mathbb{N}$に対し, $n \subset \mathbb{N}$と仮定する.
$\{n\} \subset \mathbb{N}$であるから, $\text{suc}(n) \subset \mathbb{N}$が成り立つ.
ゆえに$\mathbb{N}$は推移的集合.
また, (4)により$\forall n \in \mathbb{N} [n:\text{順序数}]$である.
命題により$\mathbb{N}$は順序数. - 集合$X$と$f, g:X \to \mathbb{N}$をとり, $\text{suc} \circ f = \text{suc} \circ g$と仮定する.
$x \in X$をとると, $f(x) \cup \{f(x)\} = g(x) \cup \{g(x)\}$が成り立つ.
$(f(x) \in g(x) \vee f(x) = g(x)) \land (g(x) \in f(x) \vee g(x) = f(x))$
$f(x) \neq g(x)$と仮定すると, $f(x) \in g(x) \land g(x) \in f(x)$が導ける.
$\mathbb{N}$は推移的集合であるから, $f(x) \in f(x)$となり, 正則性公理の言い換えにより矛盾.
ゆえに, $\text{suc}$はmonoであり, inj.
inductionを行うとき, 命題としては$x$と$n$とで変数記号を分けて書いたが, (4)のように以下混乱が起こらない場合は基本的に同じ記号を用いる.
この記事を高評価した人
この記事に送られたバッジ
投稿者
