kivantium活動日記

プログラムを使っていろいろやります

(-1)×(-1)=+1について

(-1)×(-1)=+1は中学数学で最初にぶつかる壁です。「マイナスにマイナスを掛けるとプラスになる」という現象はとても不思議でなかなか納得できなかったのを覚えています。

というわけで今回は(-1)×(-1)=+1について考えてみようと思います。

感覚的な説明

中学数学では「西に時速(+1)kmで動くことは東に時速(-1)kmで動くことである」「(+1)時間前とは(-1)時間後である」というような対になる行動を負の数で表すことが多いです。
これを用いると「東に時速(-1)kmで動いている旅人は(-1)時間後にどこにいるか?」という問題の解答が「東に+1kmの地点」であることから(-1)×(-1)=+1を説明することができます。西に時速1kmで動いている人は1時間前には東に1kmの地点にいます。これは(-1)×(-1)=+1を表しています。このような説明なら自然で中学生でも納得できるでしょう。
f:id:kivantium:20150727220040p:plain

分配法則による説明

もう一つ分かりやすいのが分配法則による説明です。
{\displaystyle (-1)\times (1+(-1)) = (-1)\times1 + (-1)\times(-1) = 0}
{\displaystyle (1 + (-1)\times1) + (-1)\times(-1) = 1}
{\displaystyle (-1)\times(-1) = 1}

これなら計算だけで理由が説明できるのでさっきの意味による説明のような曖昧さを排除することができます。

ラムダ計算による説明

以上の2つの説明は簡単で良いのですが、「東に時速(-1)kmってなんだよ、そもそも時速って何さ?」「分配法則って本当に成り立つの?」などなどいろいろツッコミどころが存在します。
ツッコミを避けるためには、「事実として認めて良さそうなこと」を事前に公理として示しておき、それらから自然に成立することを説明する必要があります。

ここではラムダ計算を使った説明を試みようと思います。

ラムダ計算の簡単な説明

ラムダ計算は自分も勉強中なので不正確な説明だとは思いますが無謀にも説明を試みてみようと思います。マサカリは大歓迎です。Wikipediaを見るのもいいでしょう。

ラムダ計算は関数によってあらゆる計算を表現しようとする体系です。ラムダ計算チューリングマシンと等価な表現力を持つ強力なモデルでLispを始めとする関数型プログラミング言語にも影響を与えました。

「引数を受け取り2を加えた値を返す」という関数は通常の表記ではf(x)=x+2のように書きますが、ラムダ計算では\lambda x. x + 2のように書きます。\lambdaの後ろに引数名、ピリオド、処理内容を続けるというイメージです。このような式をラムダ式と言います。
(\lambda x. x + 2)\:3と書けば引数xを3で置き換えた3+2 になります。

引数を複数取る関数は「関数を返す関数」として定義されます。例えば、f(x, y)=x+yラムダ式で書くと\lambda x. (\lambda y. x+y)のようになります。省略して\lambda xy. x+yのように書くことも多いです。
(\lambda xy. x+y)\:3\:\:2と書けばxに3を、yに2を代入した3+2となります。

(\lambda xy. x+y)\:3\:\:23+2のように関数を適用してラムダ式を書き換えることをβ-簡約といいます。

ラムダ計算については詳しい説明がネット上にいろいろあるので興味があったら調べてみてください。

チャーチ数と演算

ラムダ式の例として(\lambda xy. x+y)\:3\:\:2のようなものを出しましたが、本来ラムダ式は関数のみから構成されるので+や3などといった概念は含まれていません。そこで、関数を用いて数字や演算を定義する必要があります。
ラムダ式を用いて数字を表現する方法として有名なのがチャーチ数です。チャーチ数ではゼロを表すzと次の数を表すsを用いて自然数を次のように表現します。
 0 := \lambda sz. z \\
1 := \lambda sz. sz \\
2 := \lambda sz. s(sz) \\
3 := \lambda sz. s(s(sz))
zにsを適用する回数が自然数を表現しています。
このように表現された自然数に対して演算を定義することができます。
足し算を表すPLUS関数は
\mathrm{PLUS} := \lambda mnsz. ms(nsz)
掛け算を表すMULT関数は
\mathrm{MULT} := \lambda mns. n(ms)
のように表せます。

ラムダ式を用いてデータ構造を表現することもできます。
(M, N)のような組は \lambda f. M \: Nのように組の要素にアクセスする関数fを受け取ってMとNに適用する関数として表されます。
fの例としては組の1番目の要素にアクセスする関数fst(P)
 \mathrm{fst}(P) := P(\lambda xy. x)
や、組の2番目の要素にアクセスする関数snd(P)
 \mathrm{snd}(P) :=P(\lambda xy. y)
があります。

整数の表現

自然数はチャーチ数として表現できましたが、(-1)×(-1)を考えるためにはこれを整数に拡張する必要があります。
Representing Negative and Complex Numbers Using Lambda Calculusによれば、k=x-yとなるような(x, y)の組を使って整数を表すことが出来るということなので、以下ではこれに従います。

これを使えば(-1)は(0, 1)なので
 \lambda f. f(\lambda sz. z)(\lambda sz. sz)
と表せます。
この時、整数に対する掛け算MULT_Zは
\mathrm{MULT\_Z} := \lambda mnf. f \: (\mathrm{PLUS}(\mathrm{MULT} \: \mathrm{fst}(m) \: \mathrm{fst}(n))(\mathrm{MULT} \: \mathrm{snd}(m) \: \mathrm{snd}(n)))
\:\:\:\:\:\:\:\:\ (\mathrm{PLUS} \: (\mathrm{MULT} \: \mathrm{fst}(m) \: \mathrm{snd}(n)) \:(\mathrm{MULT} \: \mathrm{snd}(m) \: \mathrm{fst}(n)))
と定義されます。

これは(a-b)(x-y)=(ax+by)-(ay+bx)に対応した定義です。

(-1)×(-1)の計算

ここまでの準備で(-1)×(-1)を計算する準備が整いました。示すべきことは
\mathrm{MULT\_Z}(\lambda f. f(\lambda sz. z)(\lambda sz. sz))(\lambda f. f(\lambda sz. z)(\lambda sz. sz))
にβ-簡約を繰り返していけば \lambda f. f(\lambda sz. sz)(\lambda sz. z)になることです。ではやっていきます。

まず、 \mathrm{MULT\_Z}を書き換えます。 \lambda f. f(\lambda sz. z)(\lambda sz. sz)は(-1)と略して書きます。
 \lambda f. f(\mathrm{PLUS}(\mathrm{MULT} \: \mathrm{fst}(-1) \: \mathrm{fst}(-1))(\mathrm{MULT} \: \mathrm{snd}(-1) \: \mathrm{snd}(-1)))
\:\:\:\:\:\:\:\:\ (\mathrm{PLUS} \: (\mathrm{MULT} \: \mathrm{fst}(-1) \: \mathrm{snd}(-1)) \:(\mathrm{MULT} \: \mathrm{snd}(-1) \: \mathrm{fst}(-1)))

 \mathrm{fst}(-1)を簡約します。
 (\lambda f. f(\lambda sz. z) (\lambda sz. sz)) (\lambda xy. x)
 (\lambda xy. x) (\lambda sz. z) (\lambda sz. sz)
 \lambda sz. z

 \mathrm{snd}(-1)を簡約します。
 (\lambda f. f(\lambda sz. z) (\lambda sz. sz)) (\lambda xy. y)
 (\lambda xy. y) (\lambda sz. z) (\lambda sz. sz)
 \lambda sz. sz

この結果を代入します。
 \lambda f. f(\mathrm{PLUS}(\mathrm{MULT} \: (\lambda sz. z) \: (\lambda sz. z))(\mathrm{MULT} \: (\lambda sz. sz) \: (\lambda sz. sz))
\:\:\:\:\:\:\:\:\ \mathrm{PLUS} \: (\mathrm{MULT} \: (\lambda sz. z) \: (\lambda sz. sz)) \:(\mathrm{MULT} \: (\lambda sz. sz) \: (\lambda sz. z))

次に4つの掛け算を計算します。
 \mathrm{MULT} \: (\lambda sz. z) \: (\lambda sz. z)
 (\lambda mns. n(ms)) (\lambda sz. z) (\lambda sz. z)
 \lambda s. (\lambda sz. z) ( (\lambda sz. z) \: s)
 \lambda sz. z

 \mathrm{MULT} \: (\lambda sz. sz) \: (\lambda sz. sz)
 (\lambda mns. n(ms)) (\lambda sz. sz) (\lambda sz. sz)
 \lambda s. (\lambda sz. sz) ( (\lambda sz. sz) \: s)
 \lambda s. (\lambda sz. sz) (\lambda z. sz)
 \lambda sz. (\lambda z. sz) \: z
 \lambda sz. sz

 \mathrm{MULT} \: (\lambda sz. z) \: (\lambda sz. sz)
 (\lambda mns. n(ms)) (\lambda sz. z) (\lambda sz. sz)
 \lambda s. (\lambda sz. sz) ( (\lambda sz. z) \: s)
 \lambda s. (\lambda sz. sz) (\lambda z. z)
 \lambda sz. (\lambda z. z) \: z
 \lambda sz. z

 \mathrm{MULT} \: (\lambda sz. sz) \: (\lambda sz. z)
 (\lambda mns. n(ms)) (\lambda sz. sz) (\lambda sz. z)
 \lambda s. (\lambda sz. z) ( (\lambda sz. sz) \: s)
 \lambda sz. z

これらの結果を代入します。
 \lambda f. f(\mathrm{PLUS}(\lambda sz. z)(\lambda sz. sz))(\mathrm{PLUS}(\lambda sz. z)(\lambda sz. z))

足し算を計算します。
 \mathrm{PLUS}(\lambda sz. z)(\lambda sz. sz)
 (\lambda mnsz. ms(nsz))(\lambda sz. z)(\lambda sz. sz)
 \lambda sz. (\lambda sz. z)\: s\: ( (\lambda sz. sz)\: s\: z)
 \lambda sz. ( (\lambda sz. sz) \: s \: z)
 \lambda sz. sz

 \mathrm{PLUS}(\lambda sz. z)(\lambda sz. z)
 (\lambda mnsz. ms(nsz))(\lambda sz. z)(\lambda sz. z)
 \lambda sz. (\lambda sz. z)\: s\:( (\lambda sz. z)\: s\: z)
 \lambda sz. ( (\lambda sz. z)s \: z)
 \lambda sz. z

最後に代入します。
 \lambda f. f(\lambda sz. sz)(\lambda sz. z)

目標の1が出てきました。

このようにラムダ計算自然数・整数・演算を定義することで自然に(-1)×(-1)=1が導出できました。

以上ラムダ計算による(-1)×(-1)=1の説明でした。

ペアノの公理系もどきによる説明

後日執筆予定