プログラミングで数学の素養がちょっぴり役に立った話

465

概要

プログラミングでわからないことについて調べていると，多くのソースコード例が見つかるが，それが正しいことまで説明されているとは限らない．本稿では，2つの配列に含まれる要素が同じであることの判定方法が適切かどうかを，対応する命題を証明することで確かめる．

考える問題

JavaScriptを触っていて，次のようなことをしたい場面が出てきました．

2つの配列に含まれる要素が同じかどうか判定したい

配列は，数学的には有限数列と似たようなものです．本記事では，配列に関する深い知識は不要ですので，とりあえず

配列は[1, 2, 3]のように表す
array = [1, 2, 3]とするとき，array[0] = 1, array[1] = 2, array[2] = 3である

というくらいの認識で大丈夫です．

また，2つの配列に含まれる要素が同じということについて，具体例を用いて確認しておきましょう．なお，簡単のため，[1, 1, 1] のように同一の要素が複数個含まれる配列は考えないものとします．

2つの配列に含まれる要素が同じ

[1, 2, 3]と[1, 2, 3]：同じ
[1, 2, 3]と[2, 1, 3]：同じ
[1, 2, 3]と[1, 2, 4]：同じでない
[1, 2, 3]と[1, 2]：同じでない

2つの配列に含まれる要素が同じことの判定方法を軽く調べてみたところ，以下のような方法が見つかりました．

      const array1 = [1, 2, 3];
const array2 = [2, 1, 3];

// array1とarray2に含まれる要素は同じなので，以下の結果はtrueとなる
console.log(
    array1.length === array2.length
    &&
    array1.every(element => array2.includes(element))
);

何をしているかというと

2つの配列の要素の数が同じであり（&&の前），
かつ（&&），
一方の配列のすべての要素が，もう一方の配列に含まれる（&&の後）

ことを確かめています．
さて，この方法で，2つの配列に含まれる要素が同じかどうか判定できていると言えるでしょうか．

証明

先ほどの方法が正しいことを，ある1つの命題を証明することで確かめてみましょう．

集合 $A$ の要素の個数を $| A |$ で表す．
集合 $A, B$ に対して $B ∖ A = {x ∣ x \in B かつ x \notin A}$ と定める．

先ほどの

2つの配列の要素の数が同じであり，
一方の配列のすべての要素が，もう一方の配列に含まれる

を，結論も含めて数学的な主張に直すと，次のようになります．

有限集合 $A, B$ が $| A | = | B |$ かつ $A \subset B$ を満たすならば $A = B$ である．

早速証明してみましょう．

$A \subset B$ より $A \cap B = A$ であるから，
$\begin{matrix} (1) & | B | = | A \cap B | + | B ∖ A | = | A | + | B ∖ A | \end{matrix}$
である．さらに， $(1)$ と $| A | = | B |$ より $| B ∖ A | = 0$ ，すなわち $B ∖ A = \emptyset$ である．従って
$B = (A \cap B) \cup (B ∖ A) = A \cup \emptyset = A$
となり，結論を得る．