シンクロニシティかな？
- 次男と足し算の話をしていて、
- 息切れしたシリーズ「イデアルと論理」を思い出した、
- まだ書いてないシリーズ「ホッピングボール・マシン」にも関係するしな。
と、そんな話題。
足し算を使って作り出せる数
なんか2つの正整数、例えば6と8を選びます。6と8から足し算を何度か使って作り出せる数を考えます。例えば：
- 6 （足し算を0回）
- 6 + 6 = 12
- 6 + 8 = 14
- 8 + 8 + 8 = 24
適当な数、たとえば22が、「6、8、足し算」から作り出せるでしょうか？ といったクイズを次男と考えていました。
足し算と引き算を使って作り出せる数
次に、足し算だけでなくて、引き算も使っていいとしたらどうでしょう。例えば：
- 6 - 6 = 0
- 8 + 8 - 6 = 10
- 6 - 8 = -2
マイナスの整数が出てきてしまうし、そうでなくても引き算まで入ると話が複雑になり、次男にはちょっと無理がありました。
整数のイデアルと半環イデアル
だいぶ前に、「イデアルと論理 (4)：割り算の話」というエントリを書きました。ここで解こうとしていた問題は、映画『ダイハード3』に出てきた「升で水を量る問題」です。方程式で書くなら、「4n + 7m = 9」を満たす整数n, mを求める話です。このテの問題を系統的に調べる手段として、「イデアルと論理 (5)：イデアル登場（ほんとだよ）」で整数のイデアルの話をしたのですが、「升で水を量る問題」と「イデアル」の関係を述べないままに息切れしました。（ちなみに、「イデアルと論理」シリーズで言いたかった内容自体は「古典論理は可換環論なんだよ」にまとめて書いてあります。）
上で出てきた「6と8から、足し算と引き算で作り出せる数」の全体は整数のイデアルに他なりません。一方、「足し算だけで作り出せる数」の全体のほうは半環イデアル（an ideal in semiring*1）と呼ばれます。
引き算を使わなくても、大差ない
概念や用語はまーいいとして、適当に2つの正整数を選んで、足し算だけで作り出せる数と足し算／引き算を使って作り出せる数を比べてみてください。いくつかの例にあたれば、あんまり差がないことに気がつくでしょう。
もちろん、足し算だけでは負の数は作れないし、6と8から2を作ることも無理です。ですが、大きな数xに関しては、「xを、6と8と足し算だけで作り出せるか？」と「xを、6と8と足し算／引き算を使って作り出せるか？」に違いはなくなります。
もう少し正確に言うと； a > 0, b > 0 に対して、N > 0 があって*2、次の2つの集合は一致します。
- { x | x ≧N で、xは、aとbと足し算だけで作り出せる}
- { x | x ≧N で、xは、aとbと足し算／引き算で作り出せる}
要するに、小さい数は無視して十分大きな数に関して言えば、足し算／引き算で作り出せる数は足し算だけ（引き算はなし）でも作り出せるってことです。
ホッピングボール・マシンの構造推測問題
いま述べた整数の性質は、ホッピングボール・マシンの構造推測問題の基本的な道具としても使います。
僕は、なんか持って回った証明しか思いつかなかったんですが、短くて簡略な方法で示せるのかも知れません。興味と時間がある方は考えてみてください。
