Journal InTime

_ しばらくお待ちください

_ 暗号とネットワークセキュリティ

午前中暇だったので、ゆうぞうさんの蔵書をあさって発見。 private keyを非公開鍵と訳すのはわかりやすいですね。 これ欲しいけど高いなあ。松江でだれか持ってないかな。

PoEAAと一緒にパクって帰ろうかと思ったけど、ひどく怒られそうなのでやめておいた。

_ Conceptual Mathematics読書会

今日は、Article IIを原君が担当。ペースがなかなか上がらないので英語の音読をやめることに。結局ペースはあまり上がらず、Article IIの1で力尽きた。

演習で証明の問題が出てきて、やっと勉強会っぽい雰囲気になってきた。

p.43の

Exercise 3:
If f has an inverse, then f satisfies the two cancellation laws:
  (a) If f . h = f . k, then h = k.
  (b) If h . f = k . f, then h = k.
Warning: The following `cancellation law' is not correct, even if f has an inverse.
  (c) (wrong): If h . f = f . k, then h = k.

という演習で(c)の反例を考えていたら、小学生の時に先生から聞いた次のようなクイズを思い出した。

目の前に二本の別れ道があり、一方は天国に、他方は地獄に続いている。どちらの道にも鬼がいるが、一方の鬼は正直者で必ず正しい答えを返し、もう一方の鬼は嘘吐きで必ず間違った答えを返す。どちらの鬼が正直者かあなたは知らない。この状況で、どちらか一方の鬼に一回だけ質問をして、天国に続く道がどちらかを知るには、どのような質問をすればよいか。

この問題は、次のような問題に置き換えることができる。

BOOLを二つの要素trueとfalseをもつ集合とする。honestをBOOL上のidentity map、
lierをBOOL上のendomapであり、trueをfalseに、falseをtrueに移すものとする。
f . honest = g . lierとなる二つの写像fとgを示せ。
ここで、fとgはhonest又はlierのいずれかとする。

何かあまり面白くないし、よく考えるとこの答えは(c)の反例じゃなくて、cancellation lawが成り立つ例だな。

yesmanをBOOL上のendomapであり、trueとfalseをいずれもtrueに移すものとし、nomanをBOOL上のendomapであり、trueとfalseをいずれもfalseに移すものとすると、

yesman . lier = lier . noman, but yesman /= noman

というわけで、これが(c)の反例。