順序数の基本的な性質の証明(その1)

2020/09/25

今日の目標

順序数を定義して基本的な性質を証明する。

「集合の濃度」の定義の落とし穴

mizuha
集合の濃度ってどう定義する?
kureha
同値類で割るんじゃないの?
全ての集合の集合 $V$ に同値関係 $\sim$ を
「$X_1 \sim X_2 \defiff \text{$X_1$ から $X_2$ への全単射が存在する}$」
って定義して
$\abs X = \iset{Y \in V}{X \sim Y}$
mizuha
「すべての集合の集合」の存在を仮定したら
矛盾が起きるんじゃなかった?
kureha
あっ

カントールの定理

任意の集合 $A$ に対し、べき集合 $\mathcal{P}(A)$ から $A$ への単射は存在しない。

カントールのパラドックス

「全ての集合 $X$ に対し $X \in V$」となる集合 $V$ は存在しない。

証明

そのような集合が存在すると仮定すると $\mathcal{P}(V) \subseteq V$ となり、$\mathcal{P}(V)$ から $V$ への単射(包含写像)が存在してしまう。これはカントールの定理に矛盾。

kureha
えっ じゃあどうすんの
mizuha
有限集合 $X$ の濃度(要素数)は
「$[n]$ と $X$ の全単射が存在するような(唯一の)自然数 $n$ 」
って定義したよね
mizuha
事前に集合から自然数を構成してたから
有限集合のときはこれでよかったけど
一般の集合に対して濃度を定義するには
自然数だけじゃ足りない
mizuha
自然数を拡張しよう
mizuha
ということで今日は「順序数」について考えます

ちょっと脱線

kureha
あれ?
集合の濃度をどんな風に定義したところで
結局 $X \mapsto \abs{ X }$ が
始域が $V$ の写像になってまずいのでは
mizuha
それを「写像」として見るのがまずいだけで
任意の集合 $X$ から新しい集合 $\abs{X}$ を定義すること自体は
(集合の公理系に従って正しく定義できてるなら)問題ない
mizuha
例えば
集合 $X$ に対して 新しい集合 $X \times X$ を
$X \times X = \iset{(x, y)}{x \in X \land y \in X}$
って定義するのは問題ない
mizuha
でも だからといって写像
$f: V \rightarrow V, \ f(X) = X \times X$ を
作っちゃうのはまずい
kureha
「集合 $X$ から別の集合 $X’$ を作れること」と
「$X \mapsto X’$ になる写像が存在すること」の間には
ギャップがあるって事か
mizuha
私たちの「写像」の定義では
あくまで始域も終域も集合ってことにしてるからね
mizuha
集合っぽいけど集合じゃないものがあるんだから
写像っぽいけど写像じゃないものがあるのも
当然と言えば当然
mizuha
(もしかして「写像」の定義をうまく拡張すれば
 そのギャップを無くせたりするのかな……?)

狭義整列順序の復習

定義

集合 $X$ 上の二項関係 $\lt$ が狭義整列順序であるとは、

(1)

$\lt$ は狭義半順序

(2)

$X$ の任意の空でない部分集合は $\lt$ に関する最小元を持つ

をともに満たすことをいう。

mizuha
$A \subseteq X$ の $\lt$ に関する最小元というのは
任意の $a \in A \setminus \cbr{m}$ に対して $m \lt a$ となる
$m \in A$ のことで
mizuha
狭義整列順序は狭義全順序になるのでした
mizuha
詳細はこちら ↓

自然数の拡張?

kureha
自然数ってどんな感じで拡張するの?
mizuha
集合から自然数を構成したときを思い出すと $$0 \in 1 \in 2 \in 3 \in \cdots$$ ってなってたでしょ?
kureha
自然数 $n, m$ に対しては
$n \lt m$ と $n \in m$ が同値だったもんね
mizuha
ところで
「どんな自然数 $n$ に対しても $n \in x$」
になる集合 $x$ があるよね
kureha
$\NN$ か
mizuha
そう
そして $S(x) = x \cup \cbr{x}$ と書くとすると
$\NN \in S(\NN)$ になる
mizuha
更に $S(\NN) \in S(S(\NN))$ になって……
$$0 \in 1 \in 2 \in \cdots \in \NN \in S(\NN) \in S(S(\NN)) \in \cdots$$
kureha
ああ なんか雰囲気はわかった

順序数の定義

記法

集合 $x$ に対し、$x$ 上の二項関係 $\in_x$ を $$\phantom{ \qquad (a, b \in x)} a \in_x b \defiff a \in b \qquad (a, b \in x)$$ で定める。

mizuha
$\in$ を $x$ 上に限定した二項関係
定義

集合 $x$ が順序数であるとは

推移律

各集合 $a, b$ に対し「$b \in a \in x$ ならば $b \in x$」が成り立つ

整列性

$\in_x$ は $x$ 上の狭義整列順序

をともに満たすことをいう。

注意

集合 $x$ が推移律を満たすことは次と同値。

各 $a \in x$ に対し $a \subseteq x$ である。

例)自然数全体の集合は順序数

mizuha
順序数の例として $\NN$ が順序数であることをみよう
mizuha
自然数 $n$ に対し $s(n) = n \cup \cbr{n}$ と定義したのでした
補題1

$\NN$ は推移律を満たす。

証明

任意の $n \in \NN$ に対し $n \subseteq \NN$ であることを $n$ についての数学的帰納法で示す。

Base Case

$0 = \varnothing \in \NN$ は自明。

Induction Step

$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$ である。

補題2

$\NN$ は整列性を持つ。

証明

$\lt$ を $\NN$ 上の通常の狭義全順序とする。 $a, b \in \NN$ に対し $a \in b$ と $a \lt b$ は同値()なので ${\lt} = {\in_\NN}$ であり、更に $\lt$ は $\NN$ 上の狭義整列順序()である。

mizuha
推移律と整列性が得られたので……
命題3

$\NN$ は順序数。

mizuha
$\NN$ を順序数として見るときは
$\omega$ と書かれることが多いです
記法

順序数 $\NN$ を $\omega$ と書く。

順序数の要素は順序数

mizuha
自然数も順序数ってことを示そう
mizuha
$\NN$ が順序数ってことがわかったから
「順序数の要素が順序数」を示せば
自然数が順序数ってことがわかる
命題4

順序数の要素は順序数である。

証明

$x$ を順序数とし、$y \in x$ として $y$ が順序数であることを示す。

$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$ を得る。

$y$ が整列性を持つこと

$x$ の推移律より $y \subseteq x$ であることに注意。

$\in_y$ が狭義全順序であること

$y \subseteq x$ なので、任意の $a, b \in y$ に対し $$a \in_y b \iff a \in_x b$$ である。いま $\in_x$ は狭義全順序なので $\in_y$ も狭義全順序。

$\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$ である。

mizuha
そして $\NN$ が順序数なので……
命題5

自然数は順序数。

順序数の「次」も順序数

記法

集合 $x$ に対し $S(x)$${} = x \cup \cbr{x}$ と書き、$x$ の後者と呼ぶ。

kureha
前に後者関数 $s$ を定義してたけど
それと同じでは……
mizuha
前に定義した $s$ は
(ペアノシステム作りたかったから)
$\NN$ から $\NN$ への写像だったけど
この $S$ は写像じゃなくて
集合 $x$ に対して新しい集合 $S(x)$ を
$x \cup \cbr{x}$ によって定義したというだけ
kureha
ああ 冒頭でもした話だね
注意

集合 $x$ に対し $x \in S(x)$ であり $x \subseteq S(x)$ でもある。

注意

集合 $a, x$ に対し、

$a \in S(x)$ ${}\iff{}$ 「$a \in x$ または $a = x$」

mizuha
$S(x)$ が本当に $x$ の「次」になってることを見よう
命題6

集合 $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$ を示す。

$a \in x$ のとき

$x \subsetneq y$ より $a \in y$ である。

$a = x$ のとき

$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$ を得る。

mizuha
さて順序数の「次」は順序数です
命題7

$x$ が順序数ならば $S(x)$ も順序数である。

証明
推移律

$b \in a \in S(x)$ として $b \in S(x)$ を示す。

$\text{(i)}$
$a \in x$ のとき

$x$ の推移律より $b \in x$ となり、$b \in S(x)$ を得る。

$\text{(ii)}$
$a = x$ のとき

$b \in x$ となり、$b \in S(x)$ を得る。

整列性
$\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$ である。

$\in_{S(x)}$ の推移律

$a, b, c \in S(x)$ が $a \in b$ かつ $b \in c$ を満たすとして $a \in c$ を示す。

$\text{(i)}$
$c \in x$ のとき

$x$ の推移律より $b \in x$ であり、再度 $x$ の推移律より $a \in x$ である。$a, b, c \in x$ が得られたので、$\in_x$ の推移律より $a \in c$ である。

$\text{(ii)}$
$c = x$ のとき

$a \in b$ と $b \in x$ と $x$ の推移律より $a \in x$ すなわち $a \in c$ である。

$\in_{S(x)}$ の整列性

$\varnothing \neq a \subseteq S(x)$ なる集合 $a$ を取り、$a$ の $\in_{S(x)}$ に関する最小元の存在を示す。

$\text{(i)}$
$a \cap x = \varnothing$ のとき

$a = a \setminus x \subseteq S(x) \setminus x = \cbr{x}$ となるが、$a \neq \varnothing$ なので $a = \cbr{x}$ である。よって $a$ は $\in_{S(x)}$ に関する最小元を持つ。

$\text{(ii)}$
$a \cap x \neq \varnothing$ のとき

$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)$ に注意。

$\text{(A)}$
$b \in x$ のとき

$b \in a \cap x$ となり、$m$ の最小性より $m \in b$ を得る。

$\text{(B)}$
$b = x$ のとき

$m \in x$ より $m \in b$ を得る。

よって $m \in_{S(x)} b$ である。

mizuha
命題6~7より……
系8

順序数 $x$ に対し $x \in y$ なる順序数 $y$ が存在し、$S(x)$ はその最小のものである。

kureha
$\omega$ が順序数だから
$S(\omega)$ も順序数で
$S(S(\omega))$ も順序数で
$S(S(S(\omega)))$ も順序数で……

mizuha
とりあえず今回はここまで
つづきはまた次回