カントール標準形の計算

$ω^{n} \cdot c_{n} + \dots + ω \cdot c_{1} + c_{0}$ の形の順序数について、和で低い項が吸収されること（ $ω + ω^{2} = ω^{2}$ ）と、積を右の因子の各項に分配して $(ω^{a} c + \dots) \cdot ω^{b} = ω^{a + b}$ （ $b \geq 1$ ）・ $(ω^{a} c + β) \cdot k = ω^{a} c k + β$ （ $k$ は正の整数、 $β < ω^{a}$ ）とすることを使い、和・積・有限のべきのカントール標準形の係数を求められる（例: $(ω + 1)^{2} = ω^{2} + ω + 1$ 、 $(ω \cdot 2 + 1) \cdot 2 = ω \cdot 4 + 1$ ）

前提

順序数の和と積（大学院数学数理論理学・集合論）

この技能までの道筋（8 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
写像・単射の個数と集合の濃度（大学数学集合と位相）
可算集合（大学数学集合と位相）
順序数の和と積（大学院数学数理論理学・集合論）

説明

$ω^{ω}$ より小さい $0$ でない順序数は、自然数 $n$ と自然数の係数 $c_{n}, \dots, c_{0}$ （ $c_{n} \geq 1$ ）を使って $ω^{n} \cdot c_{n} + \dots + ω \cdot c_{1} + c_{0}$ とただ 1 通りに書けます（カントール標準形）。この技能では、そのような順序数の和・積・有限回のべきを、整列順序の絵を毎回描かずに、いくつかの規則だけで標準形に直して係数を読み取れるようになります。順序数の大小比較や、整列集合の順序型の計算の基本操作として使います。

なぜそうしてよいのか

使う道具は、前提の $1 + ω = ω$ 、 $k \cdot ω = ω$ （ $k$ は正の整数、したがって $k + ω = ω$ も）、左分配法則 $α (β + γ) = α β + α γ$ 、和と積の結合法則（ $ω^{n} = ω \cdot ω \dots ω$ なので $ω^{a} \cdot ω^{b} = ω^{a + b}$ ）に加え、整列順序の絵からすぐわかる次の 2 つの事実です。(ア) 引き算: $α \leq β$ なら $β = α + δ$ となる $δ$ がある（ $β$ から先頭の $α$ の部分を除いた残りの順序型が $δ$ ）。(イ) 左の因子についての単調性: $α \leq α^{'}$ なら $α γ \leq α^{'} γ$ （ $α$ を $α^{'}$ の始切片とみれば、 $α$ を $γ$ 回並べたものは $α^{'}$ を $γ$ 回並べたものの中に順序を保って埋め込まれる）。

和の吸収 まず $k \geq 1$ と自然数 $c$ について $c + ω^{k} = ω^{k}$ 。実際 $ω^{k - 1} \geq 1$ なので (ア) で $ω^{k - 1} = 1 + δ$ と書け、左分配法則で $ω^{k} = ω \cdot (1 + δ) = ω + ω δ$ 、よって $c + ω^{k} = (c + ω) + ω δ = ω + ω δ = ω^{k}$ 。次に $e < a$ 、 $c \geq 1$ なら $ω^{e} c + ω^{a} = ω^{e} c + ω^{e} ω^{a - e} = ω^{e} (c + ω^{a - e}) = ω^{e} ω^{a - e} = ω^{a}$ 。ここから補題「 $β < ω^{a}$ なら $β + ω^{a} = ω^{a}$ 」が出ます: $β$ を標準形の項 $t_{1} + \dots + t_{r}$ （どの項の指数も $a$ 未満）に分け、右の項から順に $t_{r} + ω^{a} = ω^{a}$ 、 $t_{r - 1} + ω^{a} = ω^{a}$ 、… と吸収させればよい。さらに $c \geq 1$ なら $ω^{a} c = ω^{a} + ω^{a} (c - 1)$ （左分配法則）なので $β + ω^{a} c = (β + ω^{a}) + ω^{a} (c - 1) = ω^{a} c$ です。つまり右側に大きいべきが来ると、左にある小さいべきの項は飲み込まれて消えます。同じべき同士は $ω^{a} c + ω^{a} d = ω^{a} (c + d)$ とまとまります。

積 $α = ω^{a} c + β$ （ $c \geq 1$ 、 $β < ω^{a}$ ）とします。 $α \cdot k$ は $α$ を $k$ 個並べた和で、つなぎ目に現れる $β + ω^{a} c$ は上の補題で $ω^{a} c$ になるので $α \cdot k = ω^{a} c + \dots + ω^{a} c + β = ω^{a} c k + β$ です。 $α \cdot ω$ は、 $ω^{a} \leq α \leq ω^{a} (c + 1)$ と (イ) から $ω^{a} \cdot ω \leq α \cdot ω \leq ω^{a} (c + 1) \cdot ω = ω^{a} \cdot ((c + 1) ω) = ω^{a} \cdot ω$ と挟まれるので $α \cdot ω = ω^{a + 1}$ 。これを繰り返して $α \cdot ω^{b} = (α \cdot ω) \cdot ω^{b - 1} = ω^{a + b}$ （ $b \geq 1$ ）です。直観的には、無限回並べると先頭の項以外の「端数」は次のコピーに吸収されて見えなくなる、ということです。右の因子 $γ = ω^{b_{m}} d_{m} + \dots + ω^{b_{1}} d_{1} + d_{0}$ との積は、左分配法則で $α γ = (α ω^{b_{m}}) d_{m} + \dots + (α ω^{b_{1}}) d_{1} + α d_{0}$ と右の因子の各項に分けて計算できます。一方 $(β + γ) α = β α + γ α$ という右分配は一般に成り立たないので、左の因子を項ごとに分けてはいけません。有限のべきは $α^{2} = α \cdot α$ のように積を繰り返して求めます。

手順

与えられた順序数をそれぞれカントール標準形 $ω^{n} c_{n} + \dots + ω c_{1} + c_{0}$ に直し、左の因子の先頭の指数 $a$ と係数 $c$ を確認する
積 $α \cdot γ$ は、右の因子 $γ$ を項に分け、左分配法則で $α \cdot (ω^{b} d) = (α \cdot ω^{b}) \cdot d$ の和にする（左の因子は分けない）
各項を規則で計算する: $b \geq 1$ なら $α \cdot ω^{b} = ω^{a + b}$ 、正の整数 $k$ なら $(ω^{a} c + β) \cdot k = ω^{a} c k + β$ （ $β < ω^{a}$ ）
和は左から順にまとめる: 右側の先頭の指数より小さい指数の項を左側から消し（ $ω^{e} c + ω^{a} = ω^{a}$ 、 $e < a$ ）、同じ指数の係数は足す
有限のべき $α^{k}$ は $α^{k - 1} \cdot α$ として手順 2〜4 を繰り返し、最後に標準形の係数を読み取る

例題

順序数 $(ω \cdot 2 + 3) \cdot (ω + 2)$ のカントール標準形を $ω^{2} \cdot c_{2} + ω \cdot c_{1} + c_{0}$ （ $c_{2}, c_{1}, c_{0}$ は自然数）と表すとき、組 $(c_{2}, c_{1}, c_{0})$ を求めよ。

例題の解答

手順 1: 左の因子 $α = ω \cdot 2 + 3$ は標準形で、先頭の指数 $a = 1$ 、係数 $c = 2$ 、残り $β = 3 < ω$ 。

手順 2: 右の因子 $ω + 2$ を項に分け、左分配法則で $α \cdot (ω + 2) = α \cdot ω + α \cdot 2.$

手順 3: $α \cdot ω = ω^{1 + 1} = ω^{2}$ 。また $α \cdot 2 = ω \cdot (2 \cdot 2) + 3 = ω \cdot 4 + 3$ （実際 $(ω 2 + 3) + (ω 2 + 3)$ で、中央の $3 + ω 2 = ω 2$ と吸収される）。

手順 4: $ω^{2} + (ω \cdot 4 + 3)$ は、右側の先頭の指数 $1$ が左側の指数 $2$ より小さいので吸収は起きず、そのまま標準形 $ω^{2} \cdot 1 + ω \cdot 4 + 3$ 。

よって $(c_{2}, c_{1}, c_{0}) = (1, 4, 3)$ 。

答え: $(1, 4, 3)$

よくある誤り

右分配法則を使って端数まで $k$ 倍してしまう誤り。 $(ω \cdot 2 + 1) \cdot 2 = ω \cdot 4 + 2$ とするのは誤りで、つなぎ目の $1 + ω \cdot 2 = ω \cdot 2$ が吸収されるので、正しくは $ω \cdot 4 + 1$ です
多項式のように展開して係数を足してしまう誤り。 $(ω + 1)^{2} = ω^{2} + ω \cdot 2 + 1$ ではなく、 $(ω + 1) (ω + 1) = (ω + 1) ω + (ω + 1) = ω^{2} + ω + 1$ が正しい答えです
積 $α \cdot ω$ で先頭の係数を残してしまう誤り。 $(ω \cdot 3 + 2) \cdot ω = ω^{2} \cdot 3$ ではなく、 $3 \cdot ω = ω$ と同じ理由で係数も端数も消え、正しくは $ω^{2}$ です
吸収の向きを逆にしてしまう誤り。消えるのは「右に大きいべきが来るとき、その左にある小さいべきの項」だけです。 $ω + ω^{2} = ω^{2}$ は正しいですが、 $ω^{2} + ω = ω^{2}$ は誤りで、 $ω^{2} + ω$ はすでに標準形で $ω^{2}$ より大きい順序数です

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$ω$ を最小の無限順序数とし、 $+$ と $\cdot$ は順序数の和と積とする。順序数
$α = (ω \cdot 2 + 3) \cdot (ω + 2)$
のカントール標準形を
$α = ω^{2} \cdot a + ω \cdot b + c (a, b, c は 0 以上の整数)$
と表すとき、組 $(a, b, c)$ をこの順に求めよ。

カントール標準形の計算

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題