この記事は、[Math & Coding] 集合・位相入門 #5の予習用の個人的メモでです。
第3章 順序集合、Zornの補題
§1 順序集合
A) 順序関係
- 自然数の剰余が「順序」であるという観点、最大公約数、最小公倍数という用語の 最大、最小 が順序という概念とちゃんと整合している
- 自然数だとあまり意味を感じないが、例えばガウス整数 $\mathbb{Z}[i]$の「剰余」を考える場合、普通の順序はそこにはないので、剰余だけで最大、最小が定義できることに意味がある
- 順序集合 $A, B$ に対して、$A\times{}B$ や $A^B$ に「自然に」順序が導入できるか考えたい
- 包含関係を順序としてとらえるという観点は重要。あまり気にせず「自然数の集合の濃度が『最小の』無限濃度である」といった言い回しを使いがちだが、感覚的に『最小』という事実をうまく数学として定式化できるとよい
B) 順序集合、部分順序集合
- 集合に『構造』を与える、部分集合にも同じ『構造』が当て嵌まって、入れ子にできる。という議論は数学のあらゆる分野で行われている
- 部分集合とその『商集合』はセットものなので、順序集合についても『商集合』としての順序集合をかんがえることができるか？
- 順序写像の商集合自体は考えられるが、直接的に部分順序集合から商集合を考えるのは難しいか
C) 最大（小）元、極大（小）元、上限、下限
- 例2の $ M = \lbrace x \in Q ,|, 0 < x, x^2 < 2 \rbrace $ が上限を持たないことの証明で数式 $a^{\prime} = (3a+4)/(2a+3)$ が突然登場しており、この有理式がどこから来たのかは考えるべき
$\sqrt{2}$にどんどん近づく有理数列を得る場合の定番として、連分数展開がある。
\sqrt{2} = 1+ \cfrac{1}{2+\cfrac{1}{2 + \cfrac{1}{2 + \cdots}}}
この連分数展開を漸化式で表現すると
\begin{array}{lll}
a_0 & = & 1 \\
a_1 & = & 1 + \cfrac{1}{2} \\
a_2 & = & 1 + \cfrac{1}{2 + \cfrac{1}{2}} \\
& = & 1 + \cfrac{1}{1 + \left(1 + \cfrac{1}{2}\right)} \\
& = & 1 + \cfrac{1}{1 + a_1} \\
&{\cdots}& \\
a_{n+1} &=& 1 + \cfrac{1}{1 + a_n}
\end{array}
このとき、$n$ が偶数なら $a_n < \sqrt{2} $, $n$ が奇数なら $\sqrt{2} < a_n$ となっている（要証明）。というわけで、$b_n = a_{2n}$ とすることで、単調増加で $\sqrt{2}$ に近づく有理数列を得ることができる。この $b_n$ の漸化式が
\begin{array}{lll}
b_{n+1} & = & a_{2n+2} \\
& = & 1 + \cfrac{1}{1+a_{2n+1}} \\
& = & 1 + \cfrac{1}{1 + \left(1 + \cfrac{1}{1 + a_{2n}}\right)} \\
& = & 1 + \cfrac{1}{2 + \cfrac{1}{1 + a_{2n}}} \\
& = & 1 + \cfrac{1}{\cfrac{3 + 2a_{2n}}{1 + a_{2n}}} \\
& = & 1 + \cfrac{1 + a_{2n}}{3 + 2a_{2n}} \\
& = & \cfrac{4 + 3a_{2n}}{3 + 2a_{2n}} \\
& = & \cfrac{4 + 3b_n}{3 + 2b_n} \\
\end{array}
を得る。
この漸化式が『最も早く』$\sqrt{2}$に近づく有理数であったりする。もちろん”これでなければいけない”ということはない。
D) 順序同型
- 注記に空集合 $\emptyset$ には順序を考えていなかった、との記載があるが、順序集合の定義から空集合が除外されているわけではない。感覚的に「順序」であると考えることが難しいだけ
§2 整列集合とその比較定理
A) 整列集合
- 自然数の集合が整列集合であることを帰納法を用いて証明しているが、これは正当化されるのか？
- 自然数に対する命題 $P(n)$ とは、つまり自然数の部分集合と同じである。
- 自然数の部分集合 $A$ について、$1\in A \land \forall n \in \mathbb{N}(n \in A \Rightarrow n + 1 \in A)$ であれば、$A = \mathbb{N}$ であることが帰納法ということではないか？
- 書籍の証明にあるように、帰納法を用いて、自然数が整列集合であることが言えると同時に、自然数が整列集合であることをもって、帰納法が成立していることが言えるのではないか？
- つまり、自然数の部分集合 $A \subseteq \mathbb{N}$ について $1\in A, \forall n \in \mathbb{N}(n \in A \Rightarrow n + 1 \in A)$ が成立していたとすると、$A \not= \mathbb{N}$ であれば、$\mathbb{N} \setminus A$ は空ではなく、最小値 $n_0 \in \mathbb{N} \setminus A $ が 存在している。$1 \in A$ であるので、$n_0 > 1$、その最小性から $n_0 - 1 \in A $ しかし、$\forall n \in \mathbb{N}(n \in A \Rightarrow n + 1 \in A)$ の前提から、$n_0 \in A$ となり矛盾を得る。
次のような『証明』はどうだろうか？
$A \subseteq \mathbb{N}$ を自然数の空でない部分集合とする。この集合の最小元を求めたい。
自然数列 $1, 2, \dots $ の代わりに $N_k =\lbrace 1, 2, \dots, k \rbrace$ なる単調増加の部分集合列 $N_1 \subseteq N_2 \subseteq \cdots \subseteq N_k \subseteq \cdots $ を考える。$\bigcup_{k\in\mathbb{N}}N_k = \mathbb{N}$ は認めてよいだろう（多分）
自然数の大小関係自体を議論する道具立てとして、集合の共通部分や和集合を考えることで、その存在を集合論的に担保することができる。たとえば $N_n \cap N_m = N_{\min(n,m)}$ や $N_n \cup N_m = N_{\max(n,m)}$ のようなことを考えている。有限個の自然数に対する「大きい」「小さい」は良いとして、それを自然数の無限個の要素からなる集合について考えると、それは今まさに『最小元が存在するか』を議論しようとしているので「大きい」「小さい」では語彙が足りていない。しかし、「共通部分集合」という語彙を集合論から持ってくることができる。（はず）
$A$ は空集合ではないので、$\bigcup_{k\in\mathbb{N}}(A\cap{}N_k) ,\big(= A \cap \big(\bigcup_{k\in\mathbb{N}}N_k\big) = A \cap \mathbb{N} = A \big)$は空ではない。よって、$A\cap{}N_k \not= \emptyset$ となるような $k$ が少なくとも１つは存在している。
これは、単純に $1, 2, 3, \dots $ と先に行けば、いずれは $A$ に含まれるような自然数 $k$ が存在している。ということを集合論的な道具立てで述べているにすぎない。
そこで、$K= \lbrace k \in \mathbb{N} ,|, A\cap{}N_k \not= \emptyset \rbrace$ とすると、$K \not= \emptyset$
$N_1 \subseteq N_2 \subseteq \cdots \subseteq N_k \subseteq \cdots $ と徐々に $\mathbb{N}$ を侵食していく集合列を考えて、$A$を交わる自然数 $k$ を考えている。いったん $k \in K$ がみつかれば、当然 $k^{\prime} \geq k$ なる自然数に対して $k^{\prime} \in K$ である。つまり『どこかから先はずっと$A$と交わる』。ここで言う『どこか』が知りたい。
都合がよいことに $N_k$ は集合であるので、共通部分集合 $N_{\star} = \bigcap_{k\in{}K}N_k$ を考えることができる。感覚的には $ N_1 \subseteq N_2 \subseteq \cdots \subseteq N_k \subseteq \cdots $ の一部（無限個ある）の共通部分なので、ある $m$ をもって、$N_m = N_{\star} = \bigcap_{k\in{}K}N_k$ となりそう。
$m$ の具体的な求め方としては、$m = \max(N_{\star})$ を採用すればよいだろう。
- $K$ は空集合ではなく、すべての $k$ に対して、$1\in{}N_k$であるので、$1 \in \bigcap_{k\in{}K}N_k$、特に$\bigcap_{k\in{}K}N_k$は空ではない。
- すべての $k$ に対して $N_k$ は有限集合であるので、$\bigcap_{k\in{}K}N_k$ も有限集合となり、最大限 $m$ が存在している（ここが怪しい？）
この $m$ について、次のことが言える
a) $m \in K$ である
b) $m$ よりも小さい $s \in \mathbb{N}$ について $ s \notin K$
a) の証明
$m$ は $N_{\star}$ の最大元、よって $m+1 \notin N_{\star} = \bigcap_{k\in{}K}N_k$
よってある $k \in K$ をもって、$m+1 \notin N_k = \lbrace 1, 2, \dots k\rbrace$
よってある $k \in K$ をもって $m+1 \gt k$ すなわち $m \geq k$
以前議論したように、$k \in K$ であれば、$k$ から先の自然数についてはすべて $A$ と交わるので $A \cap N_m \not= \emptyset$
これは $m \in K$ を意味している
b) の証明
$s \lt m$ について、$s \in K$ であると仮定すると、当然 $N_{\star} \subseteq N_s = \lbrace 1, 2, \dots s\rbrace$ となりこれは $m$ が $N_{\star}$ の最大元である（よって$N_{\star}$の元である）ことに反してしまう。
ゆえに $s \notin K$
a) はすなわち $\lbrace 1,2, \dots m\rbrace \cap A \not= \emptyset$ であり、b) はすなわち $\lbrace 1,2, \dots m-1\rbrace \cap A = \emptyset$ ということである
これは $m$ が $A$ の最小元であることを意味している。
（証明終）