非専門的シンギュラリティー研究所

無限に動き続けるシステムを表す方法を AI なども使って考えていきます。

証明路開発支援システム(22)

証明路開発支援システム

整列可能定理(2)

証明で使っている議論はだいたい以下のようになります。これを式の変形でできないかということを考えていきます。

順序数全体を $\mathbf{Ord}$ とします。 $\mathbf{Ord}$ は集合ではありません。
集合ではない場合も集合や関数の記法が使えるとします。
部分集合が定義できます。
べき集合が定義できます。
選択関数が定義できます。
関数の帰納的定義ができます。
式によって関数が定義できます。
関数の制限が定義できます。
関数の像が定義できます。
集合の関数による像は集合になります。
集合の部分集合は集合になります。
$\restriction$ は関数の制限、 $\mathrm{ran}$ は関数の値域を表します。

以下の証明の中で $\gamma$ の定義を $\gamma = \min \{ \alpha \mid X \subsetneq \alpha \}$ と変更します(証明がうまくできなかったため)。

集合 $A \ne \varnothing$ に対して順序数 $\gamma$ と全単射 $f: \gamma \to A$ が存在する。

[証明]

$a_0 \in A$ をとります。
選択公理より選択関数 $c: \mathfrak{P}(A) \setminus \{\varnothing\} \to A$ があります。
を定義します。
- 各順序数 $\alpha$ に対して集合 $G(\alpha)$ を
  $G(\alpha) = \begin{cases} c(A \setminus \mathrm{ran}(G \restriction \alpha)) & (A \setminus \mathrm{ran}(G \restriction \alpha) \ne \varnothing のとき) \\ a_0 & (それ以外のとき) \end{cases}$
  と定義できます。
の像をとします。
- $B = \{ G(\alpha) \mid \alpha \in \mathbf{Ord} \}$
- $B$ は集合です。
を定義します。
- $B$ の各元 $b$ に対して順序数 $g(b)$ を
  $g(b) = \min \{ \alpha \mid G(\alpha) = b \}$
  と定義します。
の像をとします。
- $X = \{ g(b) \mid b \in B \}$
- $X$ は順序数からなる集合となります。
$\gamma = \min \{ \alpha \mid X \subsetneq \alpha \}$ とおきます。
するととの定義よりが成り立ちます。
- を示します。
  - をとります。を示します。
    - $g(b) = \min \{ \alpha \mid G(\alpha) = b \}$ より $b = G(g(b))$
    - $g(b) \in X$ より $g(b) \in \gamma$
    - $G(g(b)) = b$ より $b \in \mathrm{ran}(G \restriction \gamma)$
- を示します。
  - としてを示します。
    - $a \in \mathrm{ran}(G \restriction \gamma)$ より順序数 $\alpha$ が存在して $a = G(\alpha)$
    - よって $a = G(\alpha) \in B$
はとなる順序数で最小のものです。
- ならばであることを示します。
  - $B = \mathrm{ran}(G \restriction \delta)$ とします。
  - ならばであることを示します。
    - $\alpha \in X$ をとると $b \in B$ が存在して $\alpha = g(b)$
    - $B \subseteq \mathrm{ran}(G \restriction \delta)$ より $\beta \in \delta$ が存在して $b = G(\beta)$
    - $\alpha$ は $b = G(\alpha)$ となる最小のものなので $\alpha \in \beta$
    - よって $\alpha \in \delta$
  - よって $X \subsetneq \delta$
- $\gamma$ は $X \subsetneq \gamma$ となる最小のものなので $\gamma \le \delta$
を示します。
- なのでと仮定して矛盾を導きます。
  - $B = \mathrm{ran}(G \restriction \gamma)$ なので $A \setminus \mathrm{ran}(G \restriction \gamma) \ne \varnothing$ となります。
  - $G$ の定義より
    $G(\gamma) = c(A \setminus \mathrm{ran}(G \restriction \gamma))$
  - $c$ が $\mathfrak{P}(A) \setminus \{\varnothing\}$ の選択関数であるから
    $G(\gamma) \in A \setminus \mathrm{ran}(G \restriction \gamma) = A \setminus B$
  - これは $B$ の定義( $G(\gamma) \in B$ )に反します。
- したがって $B = A$ となります。
以上より $\gamma$ が $A = \mathrm{ran}(G \restriction \delta)$ となる順序数 $\delta$ で最小のものであることがわかります。
とするとが全単射となることがの定義との最小性からわかります。
- $A = \mathrm{ran}(G \restriction \gamma)$ より $f$ は全射です。
- が単射であることを証明します。
  - $\delta = \min \{ \alpha \mid g(G(\alpha)) \ne \alpha \}$ とします。
  - を示します。
    - を示します。
      - $A \setminus \mathrm{ran}(G \restriction \delta) \ne \varnothing$ と仮定すると $g(G(\delta)) = \delta$ となることを示します。
        
        $G$ の定義より $G(\delta) \in A \setminus \mathrm{ran}(G \restriction \delta)$ となります。
        
        $\alpha < \delta$ ならば $G(\alpha) \in \mathrm{ran}(G \restriction \alpha)$ なので $G(\alpha) \ne G(\delta)$ です。
        
        よって $g(G(\delta)) = \min \{ \alpha \mid G(\alpha) = G(\delta) \} = \delta$ となります。
      - これは $g(G(\delta)) \ne \delta$ に矛盾するので $A = \mathrm{ran}(G \restriction \delta)$ となります。
    - $\gamma$ は $A = \mathrm{ran}(G \restriction \gamma)$ となる最小の順序数なので $\gamma \le \delta$
    - $\gamma \notin X$ かつ $g(G(\gamma)) \in X$ となるので $g(G(\gamma)) \ne \gamma$
    - $\delta$ は $g(G(\delta)) \ne \delta$ となる最小の順序数なので $\delta \le \gamma$
    - よって $\delta = \gamma$ となります。
  - よって $\gamma$ は $G \restriction \gamma$ が単射ではない最小の順序数となります。
  - よって $f$ は単射です。

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)

作者:池上大祐
日本評論社

新装改版集合への30講数学30講シリーズ

新装改版集合への30講数学30講シリーズ

作者:志賀浩二
朝倉書店

集合論入門 (ちくま学芸文庫)

集合論入門 (ちくま学芸文庫)

作者:赤攝也
筑摩書房

集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)

作者:内田伏一
裳華房

手を動かしてまなぶ集合と位相

手を動かしてまなぶ集合と位相

作者:藤岡敦
裳華房

新装版集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

新装版集合とはなにか―はじめて学ぶ人のために (ブルーバックス)

作者:竹内外史
講談社

グラフ理論入門(原書第4版)

グラフ理論入門(原書第4版)

作者:ウィルソン R. J.
近代科学社

可換環論の勘どころ (数学のかんどころ 32)

可換環論の勘どころ (数学のかんどころ 32)

作者:後藤四郎
共立出版

代数学２　環と体とガロア理論　第２版

代数学２　環と体とガロア理論　第２版

作者:雪江明彦
日本評論社

初等整数論入門 (ちくま学芸文庫)

初等整数論入門 (ちくま学芸文庫)

作者:銀林浩
筑摩書房

発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

作者:安福悠
オーム社

はじめての数論　原著第4版

はじめての数論　原著第4版

丸善出版

数論序説

作者:小野孝
裳華房

群論日評ベーシック・シリーズ

群論日評ベーシック・シリーズ

作者:榎本直也
日本評論社

代数学１　群論入門　第２版

代数学１　群論入門　第２版

作者:雪江明彦
日本評論社

代数学1群と環 (大学数学の入門 1)

代数学1群と環 (大学数学の入門 1)

作者:桂利行
東京大学出版会

代数系入門 (松坂和夫数学入門シリーズ 3)

代数系入門 (松坂和夫数学入門シリーズ 3)

作者:松坂和夫
岩波書店

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

数学セミナー2026年6月号　通巻776号【特集】高校生におすすめの整数論

日本評論社

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)

作者:西来路文朗,清水健一
講談社

平方剰余の相互法則: ガウスの全証明

平方剰余の相互法則: ガウスの全証明

作者:倉田令二朗
日本評論社

数論への出発増補版

数論への出発増補版

作者:藤崎源二郎
日本評論社

共立講座21世紀の数学 (20) 整数論

共立講座21世紀の数学 (20) 整数論

作者:斎藤秀司
共立出版