諸事情により，Disjoint-set の和の数学的な定義が欲しかった．
ここで， Disjoint-set と呼んでいるのは，Union-find とかに出てくるデータ構造で， \(\{\{1, 2\}, \{3, 4, 5\}, \{6, 7\}\}\) とか \(\{\{2, 6\}, \{8\}\}\) とか \(\{\{1, 2, 6, 7\}, \{3, 4, 5\}, \{8\}\}\) みたいなやつ．
要するに，
- 集合の集合で，
- それぞれの集合は重なりがない
みたいな感じ．
コンピュータサイエンスだと, disjoint-set data structure とか言うけど， 数学的には「商集合」と言ったりする．
問題
これらの和を定義したい．
例えば， \(A = \{\{1, 2\}, \{3, 4, 5\}, \{6, 7\}\}\) と \(B = \{\{2, 6\}, \{8\}\}\) を足すとする．
\(\{1, 2\} \in A\) と \(\{2, 6\} \in B\) と \(\{6, 7\} \in A\) の間には重なりがあるので， これらの集合は \(\{1, 2, 6, 7\}\) にまとめられる．
それ以外の， \(\{3, 4, 5\} \in A\) と \(\{8\} \in B\) は， 他の集合と重なりがないので， そのまま返される．
そうして，最終的には \(\{\{1, 2, 6, 7\}, \{3, 4, 5\}, \{8\}\}\) が得られる．
．．．みたいな感じにしたい．
それで，
色々考えたけど，綺麗な定義が思いつかなかった．
そこで，Stack exchange で聞いてみた．
．．．ら，一瞬 (40 分くらい) で返事が返って来た！
びっくり！
答え
- 入力の商集合は，それぞれ同値関係を使って定義できる． \(R_1\) と \(R_2\) と呼ぼう．
- キミが出力に欲しいのは， 「\(R_1\) と \(R_2\) を含む，最小の同値関係」 だね．
- おわり．
すげ〜簡潔だった．
場合分けの証明を LaTeX で書く
Case splitting proof in LaTeX
