順序数の基本的な性質の証明（その１）
順序数を定義して基本的な性質を証明する。
「集合の濃度」の定義の落とし穴
全ての集合の集合 $V$ に同値関係 $\sim$ を
「$X_1 \sim X_2 \defiff \text{$X_1$ から $X_2$ への全単射が存在する}$」
って定義して
$\abs X = \iset{Y \in V}{X \sim Y}$
矛盾が起きるんじゃなかった？
カントールの定理
任意の集合 $A$ に対し、べき集合 $\mathcal{P}(A)$ から $A$ への単射は存在しない。
https://sorai-note.com/math/injection-surjection/カントールのパラドックス
「全ての集合 $X$ に対し $X \in V$」となる集合 $V$ は存在しない。
証明
そのような集合が存在すると仮定すると $\mathcal{P}(V) \subseteq V$ となり、$\mathcal{P}(V)$ から $V$ への単射（包含写像）が存在してしまう。これはカントールの定理に矛盾。
「$[n]$ と $X$ の全単射が存在するような（唯一の）自然数 $n$ 」
って定義したよね
ちょっと脱線
集合の濃度をどんな風に定義したところで
結局 $X \mapsto \abs{ X }$ が
始域が $V$ の写像になってまずいのでは
任意の集合 $X$ から新しい集合 $\abs{X}$ を定義すること自体は
（集合の公理系に従って正しく定義できてるなら）問題ない
集合 $X$ に対して 新しい集合 $X \times X$ を
$X \times X = \iset{(x, y)}{x \in X \land y \in X}$
って定義するのは問題ない
$f: V \rightarrow V, \ f(X) = X \times X$ を
作っちゃうのはまずい
「$X \mapsto X’$ になる写像が存在すること」の間には
ギャップがあるって事か
あくまで始域も終域も集合ってことにしてるからね
写像っぽいけど写像じゃないものがあるのも
当然と言えば当然
そのギャップを無くせたりするのかな……？）
狭義整列順序の復習
集合 $X$ 上の二項関係 $\lt$ が狭義整列順序であるとは、
$\lt$ は狭義半順序
$X$ の任意の空でない部分集合は $\lt$ に関する最小元を持つ
任意の $a \in A \setminus \cbr{m}$ に対して $m \lt a$ となる
$m \in A$ のことで
自然数の拡張？
$n \lt m$ と $n \in m$ が同値だったもんね
「どんな自然数 $n$ に対しても $n \in x$」
になる集合 $x$ があるよね
そして $S(x) = x \cup \cbr{x}$ と書くとすると
$\NN \in S(\NN)$ になる
順序数の定義
集合 $x$ に対し、$x$ 上の二項関係 $\in_x$ を $$\phantom{ \qquad (a, b \in x)} a \in_x b \defiff a \in b \qquad (a, b \in x)$$ で定める。
集合 $x$ が順序数であるとは
各集合 $a, b$ に対し「$b \in a \in x$ ならば $b \in x$」が成り立つ
$\in_x$ は $x$ 上の狭義整列順序
をともに満たすことをいう。
集合 $x$ が推移律を満たすことは次と同値。
各 $a \in x$ に対し $a \subseteq x$ である。
例）自然数全体の集合は順序数
$\NN$ は推移律を満たす。
任意の $n \in \NN$ に対し $n \subseteq \NN$ であることを $n$ についての数学的帰納法で示す。
$0 = \varnothing \in \NN$ は自明。
$m \in s(n)$ を任意に取り $m \in \NN$ を示す。$m \in n \cup \cbr{n}$ より
$m \in n$ $\quad$ または $\quad$ $m = n$
である。前者なら帰納法の仮定より $m \in \NN$ で、後者なら $n \in \NN$ より $m \in \NN$ である。$\NN$ は整列性を持つ。
$\lt$ を $\NN$ 上の通常の狭義全順序とする。 $a, b \in \NN$ に対し $a \in b$ と $a \lt b$ は同値（※）なので ${\lt} = {\in_\NN}$ であり、更に $\lt$ は $\NN$ 上の狭義整列順序（※）である。
$\NN$ は順序数。
$\omega$ と書かれることが多いです
順序数 $\NN$ を $\omega$ と書く。
順序数の要素は順序数
「順序数の要素が順序数」を示せば
自然数が順序数ってことがわかる
順序数の要素は順序数である。
$x$ を順序数とし、$y \in x$ として $y$ が順序数であることを示す。
$b \in a \in y$ として $b \in y$ を示す。$a \in y$ と $y \in x$ と $x$ の推移律から $$a \in x$$ であり、更に $b \in a$ と $a \in x$ と $x$ の推移律から $$b \in x$$ である。以上により $b, a, y \in x$ がわかり $$b \in_x a \in_x y$$ となる。よって $x$ の整列性より $b \in_x y$ すなわち $b \in y$ を得る。
$x$ の推移律より $y \subseteq x$ であることに注意。
$y \subseteq x$ なので、任意の $a, b \in y$ に対し $$a \in_y b \iff a \in_x b$$ である。いま $\in_x$ は狭義全順序なので $\in_y$ も狭義全順序。
$\varnothing \neq z \subseteq y$ なる集合 $z$ を取り、$\in_y$ に関する $z$ の最小元が存在することを示す。
$y \subseteq x$ なので $z$ は $x$ の空でない部分集合。よって $x$ の整列性より $\in_x$ に関する $z$ の最小元が存在する。つまり
任意の $a \in z \setminus \cbr{m}$ に対し $m \in_x a$
となる $m \in z$ が存在する。この $m$ が $\in_y$ に関する $z$ の最小元でもあることを示す。$a \in z \setminus \cbr{m}$ を任意に取ると $m \in_x a$ であるが、$m \in z$ より $m \in y$ であり、また $a \in z$ より $a \in y$ なので $m \in_y a$ である。
自然数は順序数。
順序数の「次」も順序数
集合 $x$ に対し $S(x)$${} = x \cup \cbr{x}$ と書き、$x$ の後者と呼ぶ。
それと同じでは……
（ペアノシステム作りたかったから）
$\NN$ から $\NN$ への写像だったけど
この $S$ は写像じゃなくて
集合 $x$ に対して新しい集合 $S(x)$ を
$x \cup \cbr{x}$ によって定義したというだけ
集合 $x$ に対し $x \in S(x)$ であり $x \subseteq S(x)$ でもある。
集合 $a, x$ に対し、
$a \in S(x)$ ${}\iff{}$ 「$a \in x$ または $a = x$」
集合 $x$ に対し、 $$x \subsetneq y \subsetneq S(x)$$ となる集合 $y$ は存在しない。
以下 $x \subsetneq y \subseteq S(x)$ を仮定し、$S(x) \subseteq y$ を示す。つまり $a \in S(x)$ を任意に取り、$a \in y$ を示す。
$x \subsetneq y$ より $a \in y$ である。
$x \in y$ を示せばよい。$x \subsetneq y$ より、
$z \not\in x$ かつ $z \in y$
となる集合 $z$ が取れる。このとき $y \subseteq S(x)$ より $z \in S(x)$ であり、$z \in x$ または $z = x$ であるが、前者は成り立たないので $z = x$ である。$z \in y$ であったので $x \in y$ を得る。$x$ が順序数ならば $S(x)$ も順序数である。
$b \in a \in S(x)$ として $b \in S(x)$ を示す。
$x$ の推移律より $b \in x$ となり、$b \in S(x)$ を得る。
$b \in x$ となり、$b \in S(x)$ を得る。
$a \in S(x)$ とする。$a = x$ のときは $\in_x$ の非反射律より $x \not\in x$ すなわち $a \not\in a$ である。$a \in x$ のときも $\in_x$ の非反射律より $a \not\in a$ である。
$a, b, c \in S(x)$ が $a \in b$ かつ $b \in c$ を満たすとして $a \in c$ を示す。
$x$ の推移律より $b \in x$ であり、再度 $x$ の推移律より $a \in x$ である。$a, b, c \in x$ が得られたので、$\in_x$ の推移律より $a \in c$ である。
$a \in b$ と $b \in x$ と $x$ の推移律より $a \in x$ すなわち $a \in c$ である。
$\varnothing \neq a \subseteq S(x)$ なる集合 $a$ を取り、$a$ の $\in_{S(x)}$ に関する最小元の存在を示す。
$a = a \setminus x \subseteq S(x) \setminus x = \cbr{x}$ となるが、$a \neq \varnothing$ なので $a = \cbr{x}$ である。よって $a$ は $\in_{S(x)}$ に関する最小元を持つ。
$a \cap x$ は $x$ の空でない部分集合なので、$x$ の整列性より、$m \in a \cap x$ で
任意の $b \in (a \cap x) \setminus \cbr{m}$ に対し $m \in_x b$
なるものが存在する。この $m$ が $a$ の $\in_{S(x)}$ に関する最小元であることを示す。$b \in a \setminus \cbr{m}$ を任意に取る。$m \in S(x)$ と $b \in S(x)$ に注意。
$b \in a \cap x$ となり、$m$ の最小性より $m \in b$ を得る。
$m \in x$ より $m \in b$ を得る。
順序数 $x$ に対し $x \in y$ なる順序数 $y$ が存在し、$S(x)$ はその最小のものである。
$S(\omega)$ も順序数で
$S(S(\omega))$ も順序数で
$S(S(S(\omega)))$ も順序数で……
つづきはまた次回