読者です 読者をやめる 読者になる 読者になる

北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

しりとりの圏は「全単射でも同型とは限らない」の例になりそう

math

第一回「層・圏・トポス  現代的集合像を求めて」勉強会出てきました。現役の数学科の方も居て、久々に楽しい時間を過ごしました。やっぱ数学は最大の娯楽ですね!

層・圏・トポス―現代的集合像を求めて
竹内 外史
4535781095

さて、その中で出た話。全単射な射があれば同型になりそうな気がしてしまいますが、

monoでepiでもisoとは限らない

[圏論による論理学]第2章(P.55-75)

と言うのが実情です。id:m-hiyamaさんが紹介なさっている、しりとりの圏が、実はその例に該当するようです*1

一応証明しますよ

以下、射を「あ◯...◯い」(「◯...◯」は任意の文字列とする。長さ0文字も可。)、 domとcodを「あ」「い」とするが、任意の射と対象について同じことが言えます(dom = codでもOK)。

「あ◯...◯い」がmono(単射)であること

任意の対象「う」から「あ」への、「あ◯...◯い○う×...×あ = あ◯...◯い○う△...△あ」を満たす任意の2つの射「う×...×あ」「う△...△あ」について、仮定より「う×...×◯...◯い = う△...△◯...◯い」となる。これから、「×...× = △...△」*2なので、「う×...×あ = う△...△あ」となる。

以上よりmonoの性質を満たす。

「あ◯...◯い」がepi(全射)であること

任意の対象「い」から「う」への、「い×...×う○あ◯...◯い = い△...△う○あ◯...◯い」を満たす任意の2つの射「い×...×う」「い△...△う」について、monoであることの証明と同様の議論で「い×...×う = い△...△う」となる。

以上よりepiの性質を満たす。

「あ」と「い」がiso(同型)ではないこと

仮に「あ」と「い」がisoとなるとする。この仮定の下では、ある「あ◯...◯い」と「い△...△あ」が存在して、「い△...△あ○あ◯...◯い = あ」を満たす。*3

ところが、この式を計算すると「あ◯...◯△...△い = あ」となるが、この式は決して成立せず、矛盾する*4

以上の背理法により、「あ」と「い」はisoとならない。

*1:空前のしりとりブームが来てるのは偶然??

*2:これはちょっと自明じゃないかな。lengthが等しいことはすぐ出るから、それから結論出していいのかなあ。

*3:∵あが恒等射

*4:◯と△が空文字列でも、「あい = あ」