関数allに空リストを入れたときの戻り値をどう定義するべきか

イントロ

　twitterで下記のような話題を見かけた。

https://gyazo.com/fa237867220646df12ae1981ddaac20b https://twitter.com/fumieval/status/1663161595009314819

　このぐらい基本的な関数は組み込み関数や標準ライブラリといった形で提供されている可能性が高く、自分で実装する前に使っている言語のマニュアルを読んだ方がよい……という直感が働くかどうかも、良いプログラマかどうかの一つの境目だ。例えばPython、Rust、Javaには同様の関数が存在していて、trueを返すようになっている。普通はこれを使っておけば良い。

　とはいえ、そのような機能のない言語を使っている場合や、言語そのものを開発している場合には自分でall()を実装する必要があるだろう。この場合も、上記の慣習に倣ったほうが良いと思う。この慣習は論理学から来ているため、そこから外れた実装をすると、ユーザーから論理学的な類推を奪うことになるからだ。all([])がfalseを返すライブラリは、or(true, true)がfalseを返すかもしれない。ライブラリの作者は、orのことを自然言語におけるチキン or ビーフのようなものと考えているかもしれない。そのような可能性を考慮しながらライブラリを使うのは不便である。

Vacuous truth

　では、all([])がtrueを返すという慣習は、論理学のどのような議論と対応しているのだろうか。これについては、Vacuous truth(VT)に基づいているという説明がよくなされる。VTというのは、命題「AならばB」は、Aが偽のとき真になるというものである。例えば「1が偶数ならば円周率は割り切れる」という命題は真である。VTはしばしば直感に反するため、何故VTが成り立つのかが話題になることがあるが、議論の方向が逆で、論理学ではVTが成り立つように「ならば」を定義する、と言ったほうが正しい。

　何故そのように「ならば」を定義するのか？　これは真理値表を書いてみるのが分かりやすい。Aが偽のときの「AならばB」を定義する方法は、下記の4通りが考えられる。

table: 「AならばB」の真理値表の候補全パターン

A B 候補1 候補2 候補3 候補4

true true true true true true

true false false false false false

false true true true false false

false false true false true false

候補2は「AならばB」が「B」に一致してしまい、不適切である。

例えば「整数nが4の倍数ならばnは偶数である」は真だが「整数nは偶数である」は偽である。

反例: n=1は整数だが偶数ではない。

候補3は「AならばB」が「A=B」に一致してしまい、不適切である。

例えば「整数nが4の倍数ならばnは偶数である」は真だが「整数nは4の倍数」=「整数nは偶数」は偽である。

反例: n=2は4の倍数ではないが、偶数ではある。

候補4は「AならばB」が「AかつB」に一致してしまい、不適切である。

例えば「整数nが4の倍数ならばnは偶数である」は真だが「整数nは偶数かつ4の倍数」は偽である。

反例: n=1は整数だが偶数ではないし、4の倍数でもない。

　よって候補1以外は「AならばB」という状況を適切に扱えないことが分かる。上記の説明は高校数学程度の「ならば」の性質を既知としているため循環論法的だし、候補1が適切であることの説明にはなっていないが、それでも消去法で「ならば」になりそうなのがVTを満たす候補1しか残らないことは納得できると思う。

all()とVTの関係

　さて、VTが成り立つように「ならば」が定義されているとして、それとall()に何の関係があるのか？　ここからが本題である。実は筆者はこの関係がいまいちよく分かっておらず、「VTだからall([])=true」のような説明では納得できなかったために本エントリを書いた。下記は私が行間を埋めてみた例であり、同様の疑問を抱いた方への参考になれば良いと思う。

　はじめに、関数all([])はリストを取って真理値を返すが、リストは値の重複を許す。一方、集合の要素は重複を許さないため、一旦リストを集合の言葉で書き直そう。まず集合$ A_0 = \emptyset, A_1 = \{1\}, \dots, A_n = \{ 1, 2, \dots n \} を定義する。これと、自然数を取ってリストの成分を返す関数$ L(n) の組み合わせでリストを表現する。$ A_n は有限集合だからサイズ$ n のリストを表現するには$ L(1), L(2), \dots, L(n) が定まっていればよく、それを要素組で表現する。例えば、$ L = (1,1,2) は、$ L(1)=1, L(2)=1, L(3)=2 となるように$ L(n) を取ったことを意味する。

　そのような$ L(n) は無数に存在するため、上記の記法だけでは$ L(n) は一意には定まらない。例えば$ L=(1, 1, 2) からは$ L(5) は決まらないので、$ L(5) = 0 となっても$ L(5) = 500 となってもよい。これは何でも良いのだが、議論を簡単にするため、指定されていない$ n については$ L(n) = 0 と約束する。例えば、次のようになる。

$ L=(1) のとき、$ L(1) = 1, L(2)=0, \dots, L(n)=0

$ L=() のとき、$ L(1) = 0, L(2)=0, \dots, L(n)=0

　そうすると、例えばl = [1, 1, 2]は$ (A_3, (1,1,2)) と表現できるし、l = []は$ (\emptyset, ()) と表現できる。これを使えば、リスト$ (A, L) をとって、そのすべての要素が条件$ {\rm Cond} を満たすとき、またそのときに限り真を返す関数$ f_{\rm all} を次のように定義できる。

$ f_{\rm all} : (A, L) \mapsto \forall n \in A : {\rm Cond}(L(n))

　これで冒頭のツイートに出てきた関数を論理学の言葉に翻訳することができた。あとは$ f_{\rm all}(\emptyset, ()) の挙動が分かれば良いわけだが、これは下記が同値であることを使えばよい。

(あ) $ \forall n \in A : {\rm Cond}(L(n))

(い) $ \forall n \in \mathbb N : n \in A \Rightarrow {\rm Cond}(L(n))

(あ)と(い)の同値性はほとんど自明だが一応証明しておく。

(あ)を仮定すると、$ n \in \mathbb N に対して、$ n \in A ならば仮定より$ {\rm Cond}(L(n)) が言えるので(い)が成り立つ。

(い)を仮定すると、$ n \in A \subset \mathbb N だから、仮定より$ n \in A \Rightarrow {\rm Cond}(L(n)) が成り立つ。

これと$ n \in A から$ {\rm Cond}(L(n)) が言えるので(あ)が成り立つ。

よって、$ f_{\rm all} (\emptyset, ()) = \forall n \in \mathbb N : n \in \emptyset \Rightarrow {\rm Cond}(L(n)) である。

すべての自然数$ n について、$ n \in \emptyset は偽だから、VTより$ n \in \emptyset \Rightarrow {\rm Cond}(L(n)) は真である。