集合の関係：同値（Set Theory）

※私は数学者ではありません。自分用のまとめとしてこれを書いています。楽しむ範囲でご覧いただければ幸いです。内容の正確性については専門家のサイトや動画、あるいは専門書で必ず確認をお願いします。

*  *  *

前の記事で、集合の要素の始めとか終わり、集合の要素が小さいとか大きいという語を用いました。これらの表現は、集合の要素に何らかの関係（前後関係、大小関係など）があるという前提で用いています。この記事ではこの前提、すなわち集合の関係について考えます。

順序対と直積

2つの集合$X=\{1, 2, 3\}$と$Y=\{みかん, りんご, いちご\}$を例にとります。これらの集合から1つずつ要素を取り出して順に並べたものを順序対（order pair）といいます。たとえば、(1, みかん)のペアは順序対です。2つの集合から生成される順序対をすべて書き出したものを直積（Cartesian product）といいます。直積$X\times Y$の要素は次の9ペアです。

$(1, みかん), (1, りんご), (1, いちご),$

$(2, みかん), (2, りんご), (2, いちご),$

$(3, みかん), (3, りんご), (3, いちご)$

順序対は、名が示すとおり順序が重要です。数字の集合$X$どうしの直積 $X\times X$を例に考えましょう。わかりやすくするために右の$X$をオレンジ色にします。$X\times$Xの要素をすべて書き出すと

(1, 1), (1, 2), (1, 3),

(2, 1), (2, 2), (2, 3),

(3, 1), (3, 2), (3, 3)

(2, 1)と(1, 2)は異なります。(3, 1)と(1, 3)、(3, 2)と(2, 3)も異なります。数字のペアだと前後入れ替えても同じに思えますが、順序対では順序にこだりますので、異なると考えます。

二項関係

直積から取り出した順序対に何らかの評価を下すことを二項関係（binary relation）といいます。数の集合$X=\{1, 2, 3\}$の直積から、要素を1つずつ取り出して順序対を作りましょう。

$$(1, 2)\in X\times X$$

ここで、1つめの$X$から取り出した要素1と2つめの$X$から取り出した要素2の関係を調べてみましょう。「1は2以下である」という大小関係は、真偽を確かめられますので命題です。この命題は明らかに真です。こうした真偽の判定は、直積の他の要素についてもできます。

一般に、$X$の直積の部分集合$R\subset X\times X$を二項関係といい、$X$の直積を変域とする命題関数$(x_1, x_2)\in R$を $x_1 R x_2$と表記します。二項関係には同値、順序、整列などがあります。この記事では同値についてみます。

同値

次の３条件を満たす二項関係を同値（equivalence relation）といい、記号$\sim$で表します。

反射律：すべての$x$について、$x\sim x$が真
対称律：すべての$x_1, x_2$について、$x_1\sim x_2$が真なら$x_2\sim x_1$も真
推移律：すべての$x_1, x_2, x_3$について、$x_1\sim x_2$が真かつ$x_2\sim x_3$が
　　　　真なら$x_1\sim x_3$も真

同値の概念から同値類（equivalence class）と商集合（quotient set）を定義できます。$x_1$の同値類$[x_1]$とは、$x$ のうち、$x_1\sim x$ が真であるものすべてです。そして、商集合$X/\sim$とは、$X$の同値類すべて、すなわち

$$X/\sim=\{[x]|x\in X\}$$

です。集合$X$を同値類で取りこぼしなく分割（割り算）するイメージですので「商」集合といいます。果物の集合

$$X=\{みかん, りんご, いちご, ぶどう, すいか, なし\}$$

の同値類と商集合を考えましょう。この集合の要素のうち、最も好きなものがみかんとりんご、次に好きなものがいちご、ぶどう、すいか、そして相対的に最も好きではないものがなしだとします。このとき、みかんを代表元とする同値類は

$$[みかん]=\{みかん, りんご\}$$

同様に、いちご、なしを代表元とする同値類は

$$[いちご]=\{いちご, ぶどう, すいか\}$$
$$[なし]=\{なし\}$$

です。商集合はこれら3つの同値類から成ります。確かにこれらの同値類で集合$X$のすべての要素を取りこぼしなくカバーしています。

$$X/\sim=\{[みかん], [いちご], [なし]\}$$