数学集合の同一を満たす意外な関係式 - potisanのプログラミングメモ

本題

集合の同一性について驚いたのでメモします。

関係式①： $\{1,2,3\}=\{1,1,1,2,3,3\}$ 。

感覚的には $\{1,2,3\}\neq\{1,1,1,2,3,3\}$ ですが、上記は集合の同一の定義より成立します。

集合の同一の定義は「 $A=B \Leftrightarrow A\subseteq B \land B\subseteq A$ 」です。部分集合 $A\subseteq B$ の定義は「 $A\subseteq B \Leftrightarrow Aの任意の元はBの適当な元と等しい$ 」なので、「 $A=B \Leftrightarrow A、Bの任意の元はそれぞれB、Aの適当な元と等しい$ 」です。部分集合が「同一個数の元」という制限を含まないので、 $A$ も $B$ も好きな数の元を持てます。なので上の関係式①が成り立ちます。

上記の性質を適用すると集合の元の個数 $|A|$ にも次の関係式が成り立ちます。

関係式②： $|\{1,2,3\}|=|\{1,1,1,2,3,3\}|=3$

何だか落ち着きませんが、上の関係式①が成り立つ以上は成り立たざるを得ません。この式を眺めていると「集合の元」の定義が気になってきますが、いったん忘れて平たい言葉で説明するなら集合の元の個数は「外延記法したときの異なる値の個数」あるいは「集合を最も短く外延記法したときの元の個数」といえるのかと思います。

高校数学ではこの性質は無かったことにされていましたが、高校生時代の自分なら混乱から抜け出せなかったと思うので理由は察せられました。

余談1：C++やC#の例

プログラミング言語における集合でも上の性質が使われています。C++のstd::set<T>もC#のHashSet<T>も同一の要素を追加すると淡々と上書きされます（または何もされません）。 $\{1,2,3\}=\{1,1,1,2,3,3\}$ の性質を利用して、メモリサイズが最小になる $\{1,2,3\}$ を維持しています。

余談2：多重集合

順不同で同じ値を区別する場合は多重集合(multiset、bag、mset)を使うそうです。多重集合を $[...]$ で囲って書くとき、 $[1,2,3]=[3,1,2] \neq [1,1,1,2,3,3]$ です。