📘

「配列のすべての要素が条件を満たすなら True を返す」関数を定義するとき、空の配列を渡したら True を返すべき数学的説明

2023/05/31に公開

25件

math

プログラミング

tech

発端

@fumieval 様のツイート。

空の配列を渡したら True を返すべき

この関数に空の配列を渡したら True を返すべきである。仕様によるとか状況によるとか相談すべきとか例外を返すべきかもといった意見もあるようだが、議論の余地がないレベルで True を返すしかない。最大の理由は

「True を返さないと、空集合があらゆる集合の部分集合になるというルールに矛盾するから」

である。これは数学における集合論の定理のひとつであり、「これを認めないとそれに連なる集合論のすべてが瓦解する」というルールのひとつであって、認めない相応の理由があるとすれば「数学のもっとも基礎的なルールのひとつを覆してでも実現しなければならないことがある」という次元での話になる。

少なくとも私は 10 年以上プログラミングをしていてそんな状況に遭遇したことはない。

【2023/06/01 追記】
数式がわからないという意見がけっこう見られたので『超簡単な説明』を追記しました。数式よくわかんねぇなって思ったらそちらをご覧ください。

2023/06/01 以前にこの記事を読まれた方へのお詫び

この記事を公開したとき「空集合はあらゆる集合の部分集合である」という主張は公理^[1]である、と書いていたのですが空集合の公理、集合の包含関係の定義、論理学における含意の定義から導出可能な定理でした。申し訳ありませんでした。思い込み怖い。

「要素を持たない集合が存在する」という主張を空集合の公理と言います。数式で表すと以下です。

\exists \varnothing \forall x. \, x \notin \varnothing

すなわち空集合に対してはどのような対象 $x$ に対しても $x \notin \varnothing$ が成り立つという主張です。集合 $A$ が集合 $B$ に含まれるかどうかを判定するには

x \in A \Rightarrow x \in B

の真偽を判定すればよいです^[2]。

ここで $A = \varnothing$ の状況を考えてみると、空集合の公理から $x \in A$ の真理値は必ず ${\rm False}$ になります。含意（ $\Rightarrow$ ：ならば）の性質から前提が偽なら右辺がなんであっても全体としての真理値は ${\rm True}$ になります。したがって任意の集合 $A$ に対して

x \in \varnothing \Rightarrow x \in A

は常に ${\rm True}$ となりますから、空集合は任意の集合 $A$ の部分集合となります。証明終。

参考：『なぜ任意の集合の部分集合になるのか？　〜空集合の公理から証明する〜』

空集合があらゆる集合の部分集合になるというルールに矛盾する

細かいことは抜きにして簡単に説明する。「配列のすべての要素が条件を満たすなら True を返す」関数について考察したい。どんな「条件」かは明記されていないが、優れたプログラマであれば「どんな条件を与えても」成り立つように議論を進めてしまえばよいと気づくだろう。

「配列 $X$ が与えられたとき、すべての要素 $x \in X$ が条件 $P$ について $P(x) = {\rm True}$ となるならば ${\rm True}$ を返す」関数 $F$ を以下のように定義する^[3]。

F(X, P) := \forall x \in X. \, P(x)

数式に慣れていない人に向けて説明しておくと、右辺は「 $X$ のすべての要素 $x$ について $P(x)$ が成り立つ」という命題である。 $F(X, P)$ はこの命題が成り立てば ${\rm True}$ の値を取り、成り立たなければ ${\rm False}$ の値を取る関数である^[4]。

ここで条件 $P$ とはどんなものであるかを考えてみると、条件 $P$ は判定可能な $x$ が与えられればその条件を満たすかどうかを ${\rm True}/{\rm False}$ で返す関数であるから、判定可能な対象の全体 $\Omega$ が与えられたとき、 $\Omega$ を

\begin{aligned} A &:= \{ x \mid x \in \Omega, P(x) \} \\ A ^ c &:= \{ x \mid x \in \Omega, \lnot P(x) \} \end{aligned}

という２つの集合に分割することができる。分割とは

\begin{aligned} A \cup A ^ c = \Omega \\ A \cap A ^ c = \varnothing \end{aligned}

となっていることをいう（ $\varnothing$ は空集合である）。すなわち対象 $x$ が条件 $P$ を満たすかどうかは集合 $A$ に属しているかどうかで判定できる。

つまり本質的には条件判定 $P(x)$ とは「 $x$ が条件 $P$ によって規定される集合 $A$ に属するかどうか」を判定しているに過ぎない。したがってすべての条件 $P$ は

P(x) := x \in A

の形で定義できる^[5]。 $A$ と $P$ の対応関係がわかりづらいのでいっそ条件 $P$ は集合であるとみなして

P(x) := x \in P

と書いてよいことにしよう^[6]。

この事実を用いれば「配列のすべての要素が条件を満たすなら True を返す」関数 $F$ は以下のように書き直せる。

F(X, P) := \forall x \in X. \, x \in P

日本語に直せば「配列 $X$ のすべての要素 $x$ が $P$ の要素でもあるならば True を返す」関数である。そしてこの関数は「集合の包含関係」の定義そのものである。

集合 $A$ が集合 $B$ の部分集合となることの定義は、 $A$ に属するすべての要素が $B$ の要素でもあること、つまり

\forall x \in A. \, x \in B

が成り立つことである。この真偽を判定する命題関数を $G$ とすれば

G(A, B) := \forall x \in A. \, x \in B

である。すなわち $G(A, B) = {\rm True}$ であれば $A$ は $B$ の部分集合であり、 $G(A, B) = {\rm False}$ であれば $A$ は $B$ の部分集合ではない。これは $F(X, P)$ の記号をそれぞれ順に $G, A, B$ に置き換えただけでまったく同じものである。

さてここで $G$ の引数 $A$ に空集合 $\varnothing$ を与えたときにどうなるかということであるが、空集合は $B$ がどんな集合であってもその部分集合になる（という定理がある）ので、常に

G(\varnothing, B) = {\rm True}

となる。ゆえに「配列のすべての要素が条件を満たすなら True を返す」関数 $F$ は空の配列 $\varnothing$ が与えられたとき、その条件 $P$ がなんであっても

F(\varnothing, P) = {\rm True}

となる。Q.E.D.

「細かいこと抜きにして」の「細かいこと」

上記の議論はプログラミングにおける「配列」と数学における「集合」を同一視して議論を進めている。「細かいことを抜きにして」と言ったのはこの「同一視」の説明を省いているからである。

プログラミングの文脈で特にそれ以上の文脈を指定しないで単に「配列」と言えば大抵は

同じ型のデータが順序を持って複数並べられた構造

のことを指す^[7]。

たとえば大抵のプログラミング言語で [1, 2, 3, 4, 5] とか ['a', 'b', 'c', 'd', 'e'] のように表記されるデータのことであって、数字の配列は数列、文字の配列は文字列と言ったりもする。空の配列とはひとつも要素のない配列、つまり [] のことを指す。

プログラミングにおける配列は順序を持ち要素の重複を許す^[8]が、数学の集合は順序を持たず要素の重複を考慮しないので異なる構造である。

しかし配列の各要素に対して条件を適用して [True, False, True, False, True] のような状態になって、あとは論理積を取るだけという状態になれば、論理積には順序の交換法則が成り立つので順序は無視できる^[9]。また、数学の集合は重複を許さないわけではなく考慮しないだけである（重複があろうがなかろうが議論の結果に影響しない）。ゆえに条件を適用したあとはもとの「配列」がどのような構造であったとしても集合と同一視できる構造になる。

重複について不安が残るなら以下のように考えてもよい。Boolean 型の配列、たとえば [True, False, True, False, True] のすべての要素で論理積を取ったときに結果 T/F のどちらになるかを知りたければ、その配列から重複を削除して得られる（数学的な）集合に対して T/F を定めても結果は変わらない。Boolean 型の配列から重複を削除して得られる集合は以下の４パターンしかない。

重複削除後の集合	どんなときに得られるか	重複削除前の例
$\{ \}$	空の配列	`[]`
$\{ {\rm True} \}$	True しかない配列	`[True, True, True]`
$\{ {\rm False} \}$	False しかない配列	`[False, False]`
$\{ {\rm True}, {\rm False} \}$	True と False が混在する配列	`[True, False, True]`

これらの集合に対してそれぞれ出力を決めればよい。

\begin{aligned} &F(\{ \}) &:= {\rm True} \\ &F(\{ {\rm True} \}) &:= {\rm True} \\ &F(\{ {\rm False} \}) &:= {\rm False} \\ &F(\{ {\rm True}, {\rm False} \}) &:= {\rm False} \\ \end{aligned}

厳密に議論するにはこの辺にも言及しながら説明するべきなのだが、辻褄合わせのためだけに読みにくい記事を書いても意味がないので簡略的な説明にした。

状況によって変えるのは自然ではない

$F(X, P)$ の戻り値は $X$ が空集合のとき ${\rm True}$ にすると取り決めておけば、条件 $P$ によらず定まる。もしも「状況によって変える」ならばプログラムのどこかで「条件 $P$ による場合分けを行う」必要がある。

しかし条件 $P$ とは大抵の場合は関数である。プログラムは関数の内部構造を見て場合分けしたりすることはできない^[10]ので、「空の配列が与えられたときに ${\rm True}$ にすべきか ${\rm False}$ にすべきか」を振り分けるために使える情報は条件 $P$ の名前くらいしかない。

名前とは人間が勝手に付け加えた構造^[11]なので、名前による場合分けは人間が手作業で行うしかなく、数が増えてくると人間が対応付けを間違って論理バグを仕込むのがオチである。

「空の配列が与えられたときに ${\rm True}$ にする」というルールは与えられた集合 $X$ の性質のみから定まり、それ以上の情報を必要としないのでシンプルかつ自然なルールである。このルールを採用する限り、場合分けが必要になったとしても「 $X$ の長さを判定する」という決まった処理で対処できるので、間違えることもない。

超簡単な説明

記事を公開してから数式が理解できないという意見がけっこう見られたので超簡単に説明する。

まず条件 $P$ が与えられると、この世のものは「条件 $P$ を満たすか満たさないか」に分けられる^[12]。つまり判定対象となりうるものをすべて集めた集合 $\Omega$ は $P(x) = {\rm True}$ となるものを集めた集合 $A$ と $P(x) = {\rm False}$ になるものを集めた集合 $B$ に二分される。

「すべての要素が条件 $P$ を満たす配列 $X$ 」がどういうものか考えてみると、これは $P(x) = {\rm True}$ となるものをすべて集めた集合 $A$ から適当にいくつかの要素を取り出して作られた部分集合 $X \subset A$ である（あらゆる「すべての要素が条件 $P$ を満たす配列」はこのようにして作れる）。

実際に「 $X$ が $A$ の部分集合になること」は「 $X$ のすべての要素が条件 $P$ を満たすこと」の必要十分条件である。つまり $X$ のすべての要素が条件 $P$ を満たすかどうか確かめるには、 $X$ が集合 $A$ の部分集合であるかどうかを確かめればよい。

空の配列とは空集合 $\varnothing$ のことである。空集合は任意の集合の部分集合であるから、当然 $\varnothing \subset A$ であり、ゆえに条件 $P$ がどのような条件であったとしても $X$ が空集合であるならば「 $X$ のすべての要素が条件 $P$ を満たす」という命題の真理値は ${\rm True}$ になる。

おしまい

脚注

数学的な理論を構築するとき一番はじめに定めるもっとも根本的なルールのこと。公理の真偽は（別の公理系を用いない限り、あるいは用いたとしても）証明できない場合がある。 ↩︎
以下の記事では $\forall x \in A. \, x \in B$ と書いていますが、同じことです。 ↩︎
Vacuous truthという論理学の決まりがあって、この時点で $\forall x \in X. \, P(x)$ という命題は、 $P$ がなんであっても $X$ が空集合のときは ${\rm True}$ にすると取り決められている。したがって本来は以降の議論をするまでもなく ${\rm True}$ に決まっているのだが、これを ${\rm True}$ にすべき理由は「空集合はあらゆる集合の部分集合になる」という定理に帰着できることを示す。 ↩︎
プログラマの脳を刺激するために付け加えておくと、 $F$ は関数 $P$ を引数に取る高階関数である。 ↩︎
判定不能命題のときもこの形で定義できるの？という質問があったが多分できないので、本記事の証明の流れに沿うことはできない。判定不能命題のときは $P$ が何であるかには触れずに vacuous truth に帰着させるような形式的な証明を構築すればよいと思う（そのレベルの議論する人が vacuous truth なんか納得できねぇよ、とは言わないと思う）。 ↩︎
数学的には一項の関係という概念であり、実際にこのように表記してよい。 ↩︎
「配列」という概念自体がプログラミング言語によって微妙に異なるし「空の配列」もどのような実装になっているかは言語ごとに思想が異なる。この点を指摘して「文脈が曖昧である」と言っているならまぁ理解できなくはないが、それ以上議論が進まないので建設的な指摘ではない。 ↩︎
数学の言葉で言えば直積集合である。 ↩︎
多くのプログラミング言語においては論理積の短絡評価が行われるので False を見つけた時点で他の値を評価せずに結果を False にする仕様になっている。その意味で「論理積をとる順序を変えたら動いたり動かなかったりするプログラム」は作れるし、ベテランのプログラマは意図的に作ることもあるが、今回の文脈では重要ではない。 ↩︎
ものすごいハックをすればできるのかもしれないが普通はできない。 ↩︎
同じ機能を持った条件 $P$ にも異なる名前をつけることができるので、条件 $P$ の本質はその機能（条件 $P$ が規定する集合）であり、名前は重要な情報ではない。 ↩︎
排中律という論理学の定理。 ↩︎

Discussion

892nske 2023/06/02

「配列のすべての要素が条件を満たすなら True を返す」関数Aと「配列にひとつでも条件を満たさない要素があるなら True を返す」関数Bを考えます。空でない配列に対してはA、Bどちらかの関数の返り値がTrueになりもう片方はFalseになるが、空配列に対してはどちらもTrueが返ってくるということですかね。

Josh Nobus 2023/06/03

いえ、関数Bのほうは False です。

関数Aのほうの定義は

F(X, P) := \forall x \in X. \, P(x)

で関数Bの定義は

G(X, P) := \exists x \in X. \, \lnot P(x)

であり、

\lnot F(X, P) = \lnot ( \forall x \in X. \, P(x)) = \exists x \in X. \, \lnot P(x) = G(X, P)

となるので、

G(\varnothing, P) = \lnot F(\varnothing, P) = \lnot {\rm True} = {\rm False}

です。 $G(\varnothing, P) = {\rm True}$ としてしまうとこの結果に矛盾してしまいます。

lions28 2023/06/03

１つ気になったので質問させてください
関数に空の配列を渡したらアラートやエラーを吐き出すべきという主張に対しては上の集合の概念で反論可能でしょうか？
上の説明は「この世のものは「条件Pを満たすか満たさないか」に分けられる」という前提に基づいていると思われますが、TrueでもFalseでもない出力であるエラー出力はその範囲外であるように思われます。
とすると、「プログラミング上で空の配列を渡したらどうすべきか」という問いに対して果たして集合論で議論することは妥当か？という疑念が発生しそうなのでそこらへんの考えをお聞きしたいです。

Josh Nobus 2023/06/03

関数に空の配列を渡したらアラートやエラーを吐き出すべきという主張に対しては上の集合の概念で反論可能でしょうか？

いいえ。ここで説明した体系の中にはアラートやエラーという概念が登場しないので、この記事の中にあるような集合論の説明を用いてアラートやエラーの是非について言及することはできないです。

ただ「アラートやエラーを吐き出すべき」という主張が数学的な根拠に基づかない（基礎的な定理や公理に帰着できない）のであれば、それはただのお気持ち表明ですから、正しさという観点でどちらを信用するか考えたら比べるべくもないと思います。冒頭の「議論の余地がないレベル」とはそういう意味です。

個人的な感想としては、オッカムの剃刀ではないですが、論理学と集合論を用いて十分に説明できることにエラーという余計な概念を付け加えてしまったがためにどんな答えになるのかわからなくなってしまうのでは本末転倒だと思います。

証明するにしても、アラートやエラーを付け加えて拡張した論理体系を作って証明してくれればよいと思うのですが、それで「既存の論理学や集合論とは異なる結論になりました」と言って、誰がそんな論理体系を使うのかという話にもなります。そんな根本的な部分に変更を加えてしまうと、これまで過去の天才たちが積み上げてきた「数学」という膨大なライブラリのすべてを見直す必要が出てきてしまうからです。

そんなわけで、数学の体系を拡張したり再構築したりするときは、よっぽどの理由がない限り過去の重要な結果を壊さないように作られます。たとえば複素数は実数の拡張ですが、それによって実数が持っていた性質を壊したりしませんよね。したがってアラートやエラーを扱えるように拡張された論理体系においても、記事中の $F(X, P)$ の $X$ に空の配列を与えたときは ${\rm True}$ を返すように理論構築が成されるのでは？とは思います。

上の説明は「この世のものは「条件Pを満たすか満たさないか」に分けられる」という前提に基づいていると思われますが、TrueでもFalseでもない出力であるエラー出力はその範囲外であるように思われます。

エラーは種類が多いので一般化した議論が難しいですし、エラーを含む理論を構築するならどうなるかという話なので決まった答えもないと思いますが、少なくとも lions28 さんがいま懸念されている範囲であれば、エラー出力を返しているのは記事中の $F(X, P)$ のうち条件判定を行う関数である $P$ の機能であって、その結果を集約する $F$ の機能ではないですよね。Python コードではこんな感じ↓

def is_odd(x):
    # 例外が入るのはここ↓
    if not isinstance(x, int):
        raise TypeError(f"x must be instance of 'int' but actual type '{type(x)}'.")
    return x % 2 == 1

# こっち↓は変えなくていい
def F(X, P):
    ret = True
    for x in X:
        ret = ret and P(x)
    return ret

# 配列全体の判定
print( F(X, is_odd) )

ゆえに「条件判定不可能なデータを含む配列 $X$ が与えられたから $F(X, P)$ の評価値としては例外を返す」なら分かる（それにしたって False の場合の挙動と何が違うの？という感じではある）のですが、空の配列とは条件判定不可能なデータを含まない配列ですから、 $F$ がわざわざ例外を返すように理論を書き換える必要性はないと思います。

それでもエラーを raise したい、という場合もあると思うのですが、それは別に $F$ の機能を書き換えなくても $F$ に与える前に空の配列かどうかチェックして空だったら raise すればよいですよね。汎用的な高階関数である $F$ を書き換えると $F$ を使って作られたすべての配列チェック関数に影響を及ぼすので、「エラーにしたい場合もある」くらいの主張なら個別にエラーで弾けばよいと思います。

# こっち↓は変えなくていい
def F(X, P):
    ret = True
    for x in X:
        ret &= P(x)
    return ret

# 例外が入るのはここ↓
if len(X) == 0:
    raise ValueError(f"X must have at least one element.")

print( F(X, is_odd) )

実装がこうできてしまう以上、数学的にも理論構築の際に同様の回避策を取れてしまうと思います。というわけでご質問にある範囲なら「空の配列に対して $F(X, P)$ という関数がエラーを吐かなければならない（それ以外の挙動になりえない）」という根拠にするには薄いんじゃないかと思います。

lions28 2023/06/04

大変丁寧にご説明頂きありがとうございました。
仰って下さった説明には妥当性があると思いますし、納得することができました。

hinat 2023/06/03

初心者です。数式が分からなかったので超簡単な説明、の部分をお読みしての質問です。
空集合は任意の集合の部分集合、であるので、集合Bの部分集合でもあると思います。集合BはP(x)がFalseとなるxの集合であるため、空集合はFalseとなるべき、という主張も可能かと思います。
こちらについて、コメント/ご説明いただけると幸いです。

Josh Nobus 2023/06/04

一言で言えば、論理的な同値性を崩さないように「 $X \subset B$ が成り立つ」を式変形して「配列 $X$ の要素がすべて条件 $P$ を満たす」という式に帰着することができない（トートロジーではない）ので、両者の間では評価結果が一致するという保証がないためです。

これは $X \subset B$ の判定結果を見ても「配列 $X$ の要素がすべて条件 $P$ を満たす」かどうか分かるとは限らないということです。 $X$ が空集合の場合は直感的な推測と数学の結果が反する例ということになります。

「 $X \subset B$ が成り立つ」と同値なのは「配列 $X$ の要素がすべて条件 $P$ を満たさない」です。

「配列 $X$ の要素がすべて条件 $P$ を満たすとき True を返す」関数
「配列 $X$ の要素がすべて条件 $P$ を満たさないとき True を返す」関数

はどちらも空の配列を与えたときに True を返します。後者が $X \subset B$ に対応しますが、

「配列 $X$ の要素がすべて『条件 $P$ を満たさない』という条件を満たすとき True を返す」関数

だと思えば True になりますね。

hinat 2023/06/04

丁寧なご回答ありがとうございます。回らない頭で必死に考えて下記まで理解できました。

「X⊂Bが成り立つ」と同値なのは「配列Xの要素がすべて条件Pを満たさない」です。

①空集合は任意の集合の部分集合、であるので、集合Bの部分集合である
②したがって空集合からなる配列Xの要素はすべて条件Pを満たさない
③配列Xの要素がすべて条件Pを満たさないとき、関数Fの出力はFalse
④空集合に対してはFalseが返る

という風に考えてしまったのですが、どこが間違いっているかご教示いただけないでしょうか…？初心者で申し訳ありません

Josh Nobus 2023/06/04

「配列 $X$ のすべての要素が条件 $P$ を満たさない」ことと「配列 $X$ のすべての要素が条件 $P$ を満たす」ことが（空集合のときに限って）排反ではないので、両方 True になっても問題ないと言ったら伝わるでしょうか？

「配列 $X$ のすべての要素が条件 $P$ を満たさない」ことをもって「配列 $X$ のすべての要素が条件 $P$ を満たす」ことを確かめようとする、という部分は一見妥当に見えますが、空集合のときだけ両方 True になるのでおかしなことになります。

闇ぶいれこ 2023/06/04

私はtrue派ですが、いくつか質問したことがあります。

まず条件 $P$ が与えられると、この世のものは「条件 $P$ を満たすか満たさないか」に分けられる

これは本当に正しいですか？脚注でWikipediaの記事にリンクされていますが、当該記事の命題論理における説明からは上記の述語論理に関する主張は自明ではないと思いました。 $P(x)$ が必ずしも決定可能でないと思います。数理論理学における決定可能でない $P(x)$ の例をプログラミングの世界に持って行くと、エラーになったり無限ループに陥ったりする様な関数p(x)が対応しています。決定可能な $P(x)$ に限定した話だった場合、以降の論理学の議論は計算が有限時間で完了しないコードを書けるプログラミング言語の世界に持ち込めなくなるような気がしますが、主たる読者にとってその議論は有用ですか？（私は好きですが）

lions28さんへの回答の中で、

したがってアラートやエラーを扱えるように拡張された論理体系においても、記事中の $F(X,P)$ の $X$ に空の配列を与えたときは $\textnormal{True}$ を返すように理論構築が成されるのでは？

と述べられていますが、そのような理論体系こそ読者が関心を持っている体系なのではないでしょうか？また、そのような論理体系で問題なく「trueが返った方が嬉しい」という結論に至れるかと思いますので、そのような体系上で論じた方が読者にとって有用だと思いますがいかがでしょうか？

Josh Nobus 2023/06/04

これは本当に正しいですか？

正しくないです。『超簡単な説明』は雑に書いてます。『超雑な説明』と題打ったほうが実態として正しいです。

$P(x)$ が必ずしも決定可能でないと思います。

そのため『空集合があらゆる集合の部分集合になるというルールに矛盾する』では条件 $P$ で判定可能な対象の全体集合を $\Omega$ と置いています。 $P$ が決定不能な条件の場合は本記事の論法だとこの先に進めなくなると思うので議論の範囲外と思います。

本記事の中でやっている、条件 $P$ を使って集合 $A$ を作り出すことで

条件 $P$ を満たすか判定すること
集合 $A$ に属するか判定すること

は実は同じことなんだよ！と説明する流れは、それを知らなかった人に驚きを与えるためのエンターテインメントであって、数学的には最初から条件 $P$ を集合として定義してしまえばいいはずです。決定不能命題に対してこの $P$ がどう定義されるのかを私は知らないです。不勉強ですみません。

論理学の中で決定不能な条件をどう扱うかまで気になる人はこんな記事にとどまってないで数学書を読んでくれ、と思いますので私もそこまでリサーチするつもりはなくここからは推測ですが、この議論をもっと根源的な命題にまで還元すると結局は

{\rm False} \Rightarrow P(x)

という命題は $P(x)$ がなんであっても全体としては ${\rm True}$ となる、というルールに立脚しています。このとき $P(x)$ は評価する必要がない（渡されたのは空の配列なのだから条件 $P$ による判定は１度も行われない）ので、決定不能な命題（計算が完了しない操作）だとしても問題ないんじゃないでしょうか。１個でも要素がある配列与えたら逆に死にますが。

このときの「 $P(x)$ がなんであっても」が決定不能命題も含めて定義されているのかどうかだけチェックすれば OK な気がします。

と述べられていますが、そのような理論体系こそ読者が関心を持っている体系なのではないでしょうか？また、そのような論理体系で問題なく「trueが返った方が嬉しい」という結論に至れるかと思いますので、そのような体系上で論じた方が読者にとって有用だと思いますがいかがでしょうか？

そうですね。lions28 さんへの回答は Haskell の Maybe Bool のリストの挙動を意識して書いてる（例外には Nothing が対応）のでそれくらいの複雑さで済むなら別に記事に書いてもいいかなとは思うのですが、手元の資料では一般論としてそれで「すべてのエラーを考慮した論理体系になったのか」の裏付けが取れなかったので書いてないです。「条件 $P$ 」は数学的に「集合」として定義できるので（それで扱える大抵の条件については）どうにかなりますが「例外」はどう扱われているのかちょっと知らないです。

闇ぶいれこさんは何か知ってそうな雰囲気出してるので記事書いてくれたら読みに行きます！

闇ぶいれこ 2023/06/04

元々のゴールは all([], p) が true を返すと何が嬉しいのかを考える物だと私は理解しています。つまり vacuous truth があると何が嬉しいのかを考えるとも言い換えられます。

$\textnormal{False} \rightarrow P(x)$ という命題は $P(x)$ がなんであっても全体としては $\textnormal{True}$ となる、というルールに立脚しています。

そのルールは vacuous truth そのものなので、そこに立脚してしまうと true 派以外の人は到底納得できない説明になってしまう気がします。（true派の私も納得できていないです）

Josh Nobus 2023/06/05

そう思うならあなたが記事かけば？ってやんわり言ったつもりですが伝わらなかったでしょうか。

別に判定不能命題じゃなければこの記事の説明でいいですし、判定不能命題ならこの記事に沿った説明は諦めて他になんか適当に同値な命題探してくればいいんじゃないでしょうか。

どうせ公理まで還元していくと vacuous truth に行きついちゃうので vacuous truth が納得できないならいっそそっちが成り立つ理由の説明でも探したほうがいいんじゃないですね。

「 $A$ ならば $B$ である」の口語的な否定は「 $A$ なのに $B$ ではない」だから、この意味と整合させるには

\lnot (A \Rightarrow B) = A \land (\lnot B)

とする。両辺で否定を取れば、二重否定律とド・モルガン律より

A \Rightarrow B = (\lnot A) \lor B

となり、この真理値表を書いてみると ${\rm False} \Rightarrow B$ は $B$ の真偽によらず全体として ${\rm True}$ になることがわかる、とか。

Josh Nobus 2023/06/04

ちょっと個別に質問に回答するの疲れたのでもう回答しないです。記事の修正が必要なご指摘等は引き続き投げてもらってかまいません。

RY 2023/06/05

すべてFalseになる集合にも空集合Φって含まれるはず、という理解をしています。※集合の分割を行った場合の分割後の集合同士の共通部分として空集合がありますhttps://ja.m.wikipedia.org/wiki/%E9%9B%86%E5%90%88%E3%81%AE%E5%88%86%E5%89%B2
今回の証明の流れに沿うとFalseの場合にも同じことが言えてしまうと思います。

Josh Nobus 2023/06/05に更新

『超簡単な説明』のほうではそう感じるかもしれません（簡単にしただけ穴は増えるので）が『空集合があらゆる集合の部分集合になるというルールに矛盾する』のほうの流れでもそうなるか確認してもらえますか？思うだけでなく具体的に示してくれたら修正します。

lions28 さんへの回答を参考にしてもらえますか？

「配列 $X$ のすべての要素が条件 $P$ を満たさない」ことと「配列 $X$ のすべての要素が条件 $P$ を満たす」ことが（空集合のときに限って）排反ではないので、両方 True になっても問題ないと言ったら伝わるでしょうか？

「配列 $X$ のすべての要素が条件 $P$ を満たさない」ことをもって「配列 $X$ のすべての要素が条件 $P$
を満たす」ことを確かめようとする、という部分は一見妥当に見えますが、空集合のときだけ両方 True になるのでおかしなことになります。

RY 2023/06/05

返信ありがとうございます。
本質的には、本文中の『対象xが条件Pを満たすかどうかは集合Aに属しているかどうかで判定できる』という文言に引っかかっています。
空集合はAの部分集合でもあり、Acの部分集合でもあります。
引用部分とその対偶を考えると、空集合は条件Pを満たすかつ条件Pを満たさない、という事になるはずですが、これはなにかおかしいです。
なにか前提としているものが自明でないのかなっと思っていますが、ごめんなさい、どこをどう修正すればよいかは検討ついていません。

Josh Nobus 2023/06/05に更新

「対象 $x$ が条件 $P$ を満たすかどうかは集合 $A$ に属しているかどうかで判定できる」という文言の対象 $x$ は集合ではない（配列の話でいうと配列の要素であって配列そのものではない）です。

RY 2023/06/05

はい。そのとおりですね、空集合がPを満たすなんて書いてしまいました。言いたいのは、例えば、配列の要素数が1以下のときだけを考えたときにFalseとTrueは対称になる（入れ替えても議論が成立する）ので今回の結論が不思議だなっと思ったことです。具体的に説明する時間あれば追記するので放置ください〜。

Josh Nobus 2023/06/07

False と True を入れ替えても同じ命題の真偽を示していることにしかならないです。

「 $X \subset B$ が成り立つ」と同値なのは「配列 $X$ の要素がすべて条件 $P$ を満たさない」です。

「配列 $X$ の要素がすべて条件 $P$ を満たすとき True を返す」関数

「配列 $X$ の要素がすべて条件 $P$ を満たさないとき True を返す」関数

はどちらも空の配列を与えたときに True を返します。後者が $X \subset B$ に対応しますが、

「配列 $X$ の要素がすべて『条件 $P$ を満たさない』という条件を満たすとき True を返す」関数

だと思えば True になりますね。

RY 2023/06/08

時間空きました。
記事の内容は雑かもしれませんが下記のとおりだと思っています。記法は素朴かもしれませんが伝わると信じています。。
すべての元xがなす集合をUとする。与えられた条件Pに対して、Pを満たす元x∈Uの集合をG⊂Uとする。与えられた配列Xは集合Uの部分集合となみす(X⊂U)。「配列Xのすべての要素が条件Pを満たすなら True を返す」関数Fを下記のように定義する
F(X) = True : X ⊂ Gの場合
　　= False : それ以外の場合
このとき、配列が空の場合、集合とみなしたときのXは空集合Φ。Φの性質としてΦ⊂Gが成り立つのでFはTrueを返す。

個人的に記事は分かりやすくなぁと納得していますが、下記のようにも考えられます。
「配列Xのすべての要素が条件Pを満たすなら True を返す」を「配列Xに条件Pを満たしていない要素が一つもないなら True を返す」と解釈します。そして関数をHとして、下記のように定義します
H(X) = True : X∩Gが空集合でないかつX∩Gcが空集合の場合
　　 = False : X∩Gが空集合であるかX∩G^cが空集合でない場合
ここでG^cはGの補集合です(見にくくてごめんなさい)。ドモルガンの法則的には排中律を満たしています。
ここでXが空集合Φのとき、空集合の性質から X∩GはΦですから、関数HはFalseを返します。
自然言語の解釈を数学的にどう表現するか？するか？の問題だと思っています。

間違ってたら恥ずかしいですが、ご指摘いただければ幸いです:D　お付き合いいただきありがとうございます。

Josh Nobus 2023/06/09

「配列Xのすべての要素が条件Pを満たすなら True を返す」を「配列Xに条件Pを満たしていない要素が一つもないなら True を返す」と解釈します。

？？？

$\forall x \in X. \, P(x) = \lnot (\exists x \in X. \, \lnot P(x))$ の関係の話してます？

だったらまず $\exists x \in X. \, \lnot P(x)$ 、つまり「 $X$ の要素の中に $\lnot P(x)$ を満たす要素が存在する」は $X$ が空集合なら ${\rm False}$ になるので、結果はその否定の ${\rm True}$ になるのでは？

$H(X)$ は $X$ が空集合ならば ${\rm False}$ になるように定義されてるので、あなたの主張は「 $X$ が空集合ならば ${\rm False}$ を返すように定義すると空集合を与えたときに ${\rm False}$ を返す」という循環論法ですよね。

RY 2023/06/09

∀x∈X.P(x)
もうこう書いてしまえば議論の余地はないですよね。Xが空集合の場合はTrueになるのは承知しています。主張したいのは、自然言語から数式に落とすときに不定性があるのでは？という点です。

あなたの主張は...循環論法
定義の中に入っていますから、空集合に関してFalseが返るのは自明ですよね。主張は空集合に関してFalseが返る、空集合でないXに関しては境内の条件を満たす関数が定義できる、というものでした。

ちなみに。X ⊂ Gの場合にTrueを返す関数を考えてXが空集合の場合にTrueになるのも自明では？と思いましたがどう違うのか教えてくだされば嬉しいです。

Josh Nobus 2023/06/10

もう指摘じゃなくて質問になってますよね……納得するまで丁寧に教えたらバッジの１つでも送ってくれるんでしょうか。試してみますね。

∀x∈X.P(x)
もうこう書いてしまえば議論の余地はないですよね。

記事の最初で親切にも「議論の余地がないレベル」って書いたと思います。教科書通りの翻訳です。そう書かない数学書があったらむしろ興味あるので教えてください。エビデンスカモン。

X ⊂ Gの場合にTrueを返す関数を考えてXが空集合の場合にTrueになるのも自明では？と思いましたがどう違うのか教えてくだされば嬉しいです。

うーん、私は最初に

『超簡単な説明』のほうではそう感じるかもしれません（簡単にしただけ穴は増えるので）が『空集合があらゆる集合の部分集合になるというルールに矛盾する』のほうの流れでもそうなるか確認してもらえますか？

と言ったんですけど確認しましたか？まぁ記事が読みづらかったかもしれないので要約します。

『空集合があらゆる集合の部分集合になるというルールに矛盾する』のほうの論理の流れは

$x$ が条件 $P$ を満たすことは $P(x) := x \in P$ と定義される
$X$ のすべての要素が条件 $P$ を満たすことは $F(X, P) := \forall x \in X. \, P(x)$ と定義される
1 の式を 2 の式に代入すると $F(X, P) = \forall x \in X. \, x \in P$ となる
集合の包含関係は $A \subset B := \forall x \in A. \, x \in B$ と定義され、これはたまたま 3 の式に一致している
したがって 3 の式と 4 の式から $F(X, P) = X \subset P$ であり、集合の包含関係と $F(X, P)$ の真偽の判定は同値であることが示された

です。形式的な推論（文字列の置換だけで機械的にできる推論）でできることを、記事の中ではみんながわかりやすいように自然言語を混えて書いてるだけです。前提は

$x$ が条件 $P$ を満たすことを $P(x) := x \in P$ と定義する
$X$ のすべての要素が条件 $P$ を満たすことを $F(X, P) := \forall x \in X. \, P(x)$ と定義する
集合の包含関係を $A \subset B := \forall x \in A. \, x \in B$ と定義する

の３つであって「 $X \subset P$ によって $F(X, P)$ の真偽を判定できる」という結果は前提から導出された結論であり、循環論法にはなっていません。

主張したいのは、自然言語から数式に落とすときに不定性があるのでは？という点です。

そう言われても「あなたの翻訳ミスでは？」としか……

定義として数式に落とすときの自由はもちろんありますよ。でも推論は自然言語でやると間違いが起こるからルール決めて数式でやろうぜ、ってのが現代の数学なわけで、 $H(X)$ を定義する前に

「配列Xのすべての要素が条件Pを満たすなら True を返す」を「配列Xに条件Pを満たしていない要素が一つもないなら True を返す」と解釈します。

という複雑な推論を自然言語でやるのは危険です。まぁ今回は原因はそこじゃなくてマジでただの翻訳ミスなんですけど。あなたは「配列Xに条件Pを満たしていない要素が一つもないなら True を返す」を

H(X) := (X \cap G \neq \varnothing) \land (X \cap G ^ c = \varnothing)

で定義してますが、「配列Xに条件Pを満たしていない要素が一つもないなら True を返す」を素直に翻訳するなら $H(X)$ の定義は

H(X) := (X \cap G ^ c = \varnothing)

ですよね。この定義でも十分に機能を果たします。それで、 $X \cap G \neq \varnothing$ はどっから出てきたんですか？空集合のときに ${\rm False}$ になってる理由が「あなたが自然言語のほうにはない意味や操作を勝手に付け加えたから」でしかない。このレベルの誤訳を「翻訳の不定性」で押し通して反論の根拠にするにはちょっと無理があります。

あなたが言うような関数 $H(X)$ は作れますよ。作れますけど「そういう関数が作れる」って言ってるだけでそれが「配列Xに条件Pを満たしていない要素が一つもないなら True を返す」関数の挙動として適切であることの根拠をあなたは何ひとつ示せていないんです。既存のルールから作り出したわけでも、既存のルールに帰着させてその妥当性を確かめたわけでもない。

さすがに疲れたんですけどもういいですか？見返りに何か私の知らない知識を教えてくれるとかなら歓迎するんですけど……

Josh Nobus 2023/06/12に更新

繰り返しになりますが個別の質問に回答するの疲れたのでもう回答しないです。回答する場合にも塩対応、煽り、暴言等が含まれうる旨、ご了承ください。

記事の修正が必要なご指摘等は引き続き投げてもらってかまいません。