どうせなら厳密なほうがいい

第33話 順序数の積の計算

「まずは2×ωだね。あれ、これって2ωと同じもの？」

「積の記号を省略するのはあまり好きではないな…同じもの、と見てもよいけど」

「OK、とにかく計算だね。と、その前に積の計算方法、少し変えていい？」

「どういうふうに？」

「まず、積の定義がこう」

α,β∈ONに対して、α×β∈ONを次のように定義する。

ord(A,＜)=α

ord(B,≪)=β

となるように、A,＜,B,≪を決め、A×B上の関係◁を

x◁y:↔

∀x,y∈A×B(

x[R]＜y[R]

∨

(x[R]=y[R]∧x[L]≪y[R])

)

とする。このとき、

α×β:=ord(A×B,◁)

「でも、αとβと∈をそのままAとBとそれぞれの大小関係に流用しても良いことが解ってるから、いきなりα×β上、あ、これは直積ね、の大小関係を考えちゃいたい」

「紛らわしいから、順序数の積と直積の記号を少し変えようか」

順序数の積

α×β

直積

A✕B

「これなら、わざとらしく書けば十分伝わるね。それで、湾はどう積を定義する？」

「定義、になるのかな？むしろ積の性質だと思うけど」

「もともとの定義に同値な別の論理式を新しい定義と思い直すのはよくあることだよ。さて、湾の積の定義を書いてみよう」

「よし」

α,β∈ONに対し、α×β∈ONを次のように定義する。

α✕β上の関係◁を

x◁y:↔

∀x,y∈A×B(

x[R]∈y[R]

∨

(x[R]=y[R]∧x[L]∈y[L])

)

とする。このとき、

α×β=ord(α✕β,◁)

藍は入念にチェックする。

「よし、これは積の定義としっかり同値だ。なぜなら、次のように代入したから」

Aにα

＜に∈

Bにβ

≪に∈

「そして、順序数は自身に∈で順序同型になるのはさっきやったから、OKだ」

「やったね。これで2×ωを計算するよ」

「どうぞ」

2✕ω={

(0,0),(1,0),

(0,1),(1,1),

(0,2),(1,2),

(0,3),(1,3),

…

}

「直積は横✕縦ってしっかり覚えてないと書き方混乱するね」

「そうかも。しかも順序数の場合は順序が大事だから、ここで混乱すると後が大変だ」

「とにかくこの順番で書いておけば、そのまま大小関係になってるね。右の項の小さい順に並んでて、右の項が同じときは左の項の小さい順に並んでるからね」

「よし。一応いつものように並べて」

「うん」

(0,0)◁(1,0)◁(0,1)◁(1,1)◁(0,2)◁(1,2)◁(0,3)◁(1,3)◁…

「形に注目すると、この順序数は何に見える？」

「まあ明らかにωだよね」

「その通り。一応Gで対応させると？」

「こうだよ」

G((0,0))=0

G((1,0))=1

G((0,1))=2

G((1,1))=3

G((0,2))=4

…

「これは順序対(a,b)に対してこうなるね」

G((a,b))=a+2b

「そういうことだね。これでここに現れるGの値は自然数全部かつそれだけなことがわかったので、2×ωは計算終了だ。湾、ゴールして」

「よし」

2×ω=ω

「それにしても見れば見るほど不安になる式だね」

「そうでしょ。これはω×2とは異なるのをさっと見よう」

ω✕2={

(0,0),(1,0),(2,0),(3,0),(4,0),…

(0,1),(1,1),(2,1),(3,1),(4,1),…

}

「そして、この通りに大小関係が入る」

(0,0)◁(1,0)◁(2,0)◁(3,0)◁…◁(0,1)◁(1,1)◁(2,1)◁(3,1)◁…

「これはさっきやったω+ωのときと全く同じ順序対と関係になっていることがわかるね」

「あ、本当だ！すごい。じゃあこういうことか」

ω×2=ω+ω

「なんかこれはそこまで不安にならないけど、2×ω=ωと合わせて見るとめっちゃ不安になるな…」

「積の交換法則は成り立たないことがわかったね。さて、どんどん行こう」

第二問

(ω+1)×(ω+1)

「これもω+1とω+1の直積をいきなり考えていいのかな」

「やってみればわかる」

「よし」

ω+1={0,1,2,3,…,ω}

なので、

(ω+1)✕(ω+1)={

(0,0),(1,0),(2,0),…,(ω,0),

(0,1),(1,1),(2,1),…,(ω,1),

(0,2),(1,2),(2,2),…,(ω,2),

…

(0,ω),(1,ω),(2,ω),…,(ω,ω)

}

「なんか正方形は感じるけど、若干気持ち悪いな…」

「ただ、これで順序数の構造はよくとらえられてるよ。まず、いつも通り一列に並べてから、論理に頼りつつGを求めていこう」

「うん」

(0,0)◁(1,0)◁(2,0)◁…◁(ω,0)◁(0,1)◁(1,1)◁(2,1)◁…◁(ω,1)◁(0,2)◁(1,2)◁(2,2)◁…◁(ω,2)◁…

◁(0,ω)◁(1,ω)◁(2,ω)◁…◁(ω,ω)

「何か思うことは？」

「そうだな、不安になるところが一つ」

「うん」

「テンテンテンの省略、二種類あるよね」

「二種類というと？」

「横軸の省略と、縦軸の省略。一列に並べると区別できないけど」

「それはとても良い指摘。Gの計算ではよく気をつけよう」

「それから、(0,1)が(ω,0)の後続になってるね。これはω×2を計算したときとは全然ちがう」

「いいね。湾の観察眼は安心感があるよ」

「そうかな？」

「Gの計算、できる？」

「よし」

G((0,0))=0

G((1,0))=1

…

ここでG((n,0))=nだから

…

G((ω,0))=ω

「まずはこんな感じかな」

「そう。定義に戻ればはっきりするね」

G((ω,0))={n|(n,0)◁(ω,0)}

「よし。そして、次はこうだ」

G((0,1))=ω+1

「なぜ？」

「表を見れば明らかだけど」

「私ならこうとでもしておくかな」

∵∀x∈(ω+1)×(ω+1)

(ω,0)=max(x|x[R]=0)∧(0,1)=min(x|x[R]≠0)

「(ω,0)と(0,1)の間には順序対がないことがこれでわかる」

「これは上下で挟んでる感じだね」

「2つに切ってるようにもみえるかな」

「さて、次はこう」

G((1,1))=ω+2

G((2,1))=ω+3

…

G((n,1))=ω+(n+1)

「そうだね」

藍は頷きながら湾の筆先を見ている。

「だから、G((ω,1))がこう」

G((ω,1))={ω+(x+1)|(x,1)◁(ω,1)}

∵G((ω,1))={G((x,1))|(x,1)◁(ω,1)}∧G((n,1))=ω+(n+1)

「ちょっと待って。それはおかしいよ、湾」

「あれ？」

「たとえばそれには空集合が属していない」

「あっ」

「右の項が0になるような順序対全部でω+1だからその要素を追加してあげよう。正しくは、こう」

G((ω,1))={ω+(x+1)|(x,1)◁(ω,1)}∪(ω+1)

「ははー、なるほど。結構テクニカルだね」

「面倒だけど、こう書いたらわかりやすいかな」

G((ω,1))={G((x,1))|(x,1)◁(ω,1)}∪{G((x,0))|x∈ω+1}

「しっかり、今まで挙げたやつ全部数えないといけないってことか」

「そう。そして、G((ω,1))は？」

「ω+(n+1)のnを自然数の範囲でどんどん増やしていけばいいから、こうだね」

G((ω,1))=ω+ω=ω×2

「これ間違えないのはなかなか」

「ω×2+1にはならないよ。なぜなら、(ω,1)の一つ前はないからね」

「よし」

「そして、その後続が、こう」

G((2,0))=ω×2+1

G((2,1))=ω×2+2

…

「混乱してきたから、今までの全部並べる」

G((0,0))=0

G((1,0))=1

G((2,0))=2

…

G((ω,0))=ω

G((0,1))=ω+1

G((1,1))=ω+2

G((2,1))=ω+3

…

G((ω,1))=ω×2

G((0,2))=ω×2+1

G((1,2))=ω×2+2

…

「道のりが長すぎる！」

「大丈夫。下から攻めるといつまで経ってもおわらないけど、上から攻めればもうゴールは間近だ」

問

G((0,ω))を求めよ

「む、これはどうするの？」

湾の顔に疲労が浮かんできた。

「上下でサンドイッチしよう。これよりは大きくなれない、これよりは大きい、というのを求めていく。まず、(0,ω)未満は全てこういう形になる」

(a,b)◁(0,ω)→(a∈ω+1∧b∈ω)

「右の項がωを超えないもの全部を並べたイメージ」

「たしかに」

「そして、次のような関係がある」

(a,b)◁(0,ω)→((

b=0→G((a,b))=a

)∧(

a=ω→G((a,b))=ω×(b+1)

)∧(

(b≠0∧a≠ω)→G((a,b))=ω×b+(a+1)

))

「ここらへんは厳密にするなら数学的帰納法を何度も使う必要があるけどね。さて、(0,ω)未満を考えるなかで、G((a,b))はω×ωを超えない、ということと、G((a,b))でω×ω未満の順序数を全て作れるか、ということを考える。両方成功したらG((0,ω))=ω×ωがわかる。そして、ヒントはbは自然数」

a∈ω+1,b∈ωのもとで

a

ω×(b+1)

ω×b+(a+1)

の3つの式で

①ω×ωまでの全ての順序数を作れる

②ω×ωを作れない

ことを確認する。

ω×ωは積の定義から、ω✕ωの逆辞書式順序である。

よって、s∈ω,t∈ωを用いて、

(s,t)と書ける。そして、対応する順序数をH((s,t))と書くことにすると、

H((s,t))=ω×t+s

が成り立つ。さらに、次の式が成り立つ

∀s,t∈ω,∃(a,b)◁(0,ω)(H((s,t))∈G(a,b))

∵b=t,a=ωとすればよい

これで①はOK

いかなるa∈ω+1,b∈ωを選んでも

a

ω×(b+1)

ω×b+(a+1)

のいずれもω×ωは超えない。

これで②もOK

よって

G((0,ω))=ω×ω

「うう…」

湾は頭を抱えている。

「限界にきちゃったか。あと一息でゴールだから、頑張れ。マラソンなら40km地点だ」

「その2.195km絶対長いだろ」

「そうかな」

以降は後続なので、次が成り立つ。

G((1,ω))=ω×ω+1

G((2,ω))=ω×ω+2

…

G((ω,ω))=ω×ω+ω

「ふにゃ」

湾は引き続き頭を抱えている。

(ω+1)×(ω+1)=ord((ω+1)✕(ω+1),◁)=ω×ω+ω+1

「ふにゃ！？」

湾は突然頭を上げる。

「はい、よくできました」

藍はにこやかな笑顔を湾に向ける。

「いつの間にか解けている…」

「こんな図にすると直感的なんだけどね…」

藍は図を書いた

(ω+1)×(ω+1)

0          ,1           ,2          ,…ω

ω+1    ,ω+2     ,ω+3    ,…ω×2

ω×2+1,ω×2+2,ω×2+3,…ω×3

…

ω×ω   ,ω×ω+1,ω×ω+2,…ω×ω+ω

「なるほど、これとの対応表だね」

湾はページを戻して比較する

(ω+1)✕(ω+1)={

(0,0),(1,0),(2,0),…,(ω,0),

(0,1),(1,1),(2,1),…,(ω,1),

(0,2),(1,2),(2,2),…,(ω,2),

…

(0,ω),(1,ω),(2,ω),…,(ω,ω)

}

「そう。そういうこと。第三問、さすがにもう疲れて無理かな」

「表を作って確認、くらいならできるかもね」

「そうだね。イメージになっちゃうけど」

「たしかにそれはやだなあ」

「先お風呂でもはいろっか」

「一つ、見落とさなかったよ」

「何？」

「なんかε-N論法みたいなの一瞬登場してたでしょ」

湾は疲労困憊の顔の中にも輝きのある目を失わない。