かけ算の定義

考

なぜ、1 * 1 = 1、1 * 0 = 0、 1 * -1 ＝ -1、 -1 * -1 = 1 なのかという議論がほんの一瞬だけ起きたので、新幹線での移動中にちょっとばかり考えてみた。が、真面目に議論しようとすると整数を定義をして、整数全般における演算子 * の定義と適用ということが必要になってくるのだが、そもそも整数の正しい定義を忘れてしまった。自然数に逆元を導入すればいいんだっけ？

じゃあ自然数だけなら

上述の命題のうち、自然数だけのもの 1 * 1 = 1、1 * 0 = 0 については、おそらく

  • x * e = e
  • x * y' = x + (x * y)

だけでよいはず。ここで、 eはNにおけるある特定の元で普段は"0（ゼロ）"といわれるもの。x' は x の後者。0' は 1 と呼び、 1' は 2 と呼ぶ。演算 + が出てきているので、こいつの定義もすると

  • x + e = x
  • x + y' = (x + y)'

となる。ついでに、自然数の定義（ペアノの公理）も書き下してみると

  • ある e ∈ N が存在する
  • 任意の x ∈ N に対して一意的に決まるNの元をxの後者と呼び、x'と書く
  • 任意の x ∈ N に対して x ≠ e
  • 任意の x,y ∈ N に対して (x ≠ y) ⇒ (x' ≠ y')
  • ((e ∈ S)∧((x ∈ N) ⇒ (x' ∈ S))) ⇒ (S = N)、ここでSはNの部分集合

であって、普段は上述のように暗黙のうちに e を 0 と呼び、 0' を 1 と呼び、 1' を 2 と呼び・・・としている。最後の条件が数学的帰納法の正当性を与えているで、演算 *,+ の定義を帰納的に行うことができている。

これをプログラムに書いてみる。

(define (suc x) (+ x 1))  ;; 後者関数
(define (pre y) (- y 1))  ;; 前者関数（後者関数の逆関数）

(define e 0)  ;; e は ゼロ
(define one (suc e))  ;; e の後者を one と呼ぶ
(define two (suc e))  ;; one の後者を two と呼ぶ
    :
    :

(define (add x y)
  (if (eq? y e) x
	(suc (add x (pre y)))))

(define (mul x y)
  (if (eq? y e) e
	(add x (mul x (pre y)))))

で、

> (add one one)
2
> (mul one one)
1

てな具合。多分、Prolog で書けば前者関数が不要になってもっとエレガントに書けると思うのだが、Prolog をかなーり忘れてしまったので Scheme で関数チックに書いた。

また次の機会に整数の議論についても考えてみるわさ。つーか、数論や代数学の教科書引けばいいんだけどね。ただ、その手の教科書は家に置きっぱなし。

（続く）