【離散数学】同値類と商集合について分かりやすく解説!

同値類と商集合

こんにちは!krです!

今回は「同値類と商集合」について分かりやすく説明していきます!

初学者におすすめの離散数学の参考書4選

同値類とは?

同値類は簡単に言えば、「自分と同じ関係のやつら全部集めたったで^^」というやつです。

簡単な例で感覚を掴みましょう。

簡単な例

例えば、次のような人物の集合$A$を考えましょう。

$$A=\{佐藤君, 鈴木さん, 高橋君, 田中さん, 伊藤君\}$$

そして、「同じクラスである」という関係を$R$とします。$R$は「反射律・対称律・推移律」を満たすので同値関係です。

ここで、佐藤君、鈴木さん、高橋君が「同じクラスである」としたら、$\{佐藤君, 鈴木さん, 高橋君\}$という集合は「同じクラスである」という関係$R$において同値なものの集合であり、この集合を関係$R$の同値類といいます。

また、田中さんと伊藤君が「同じクラスである」としたら$\{田中さん, 伊藤君\}$という集合も関係$R$の同値類です。

MEMO
関係Rにおいて同値なものの集合を「関係Rの同値類」という

代表元

例えば、$\{佐藤君, 鈴木さん, 高橋君\}$という同値類は「”佐藤君“と$R$という関係のある人の集合」と解釈することができ、このとき佐藤君のことをその同値類の「代表元」と呼びます。

同様に、「”鈴木さん“と$R$という関係のある人の集合」と考えると、代表元は鈴木さんとなり、「”高橋君“と$R$という関係のある人の集合」と考えると、代表元は高橋君となります。

つまり、誰でも代表になれるということです。

先生
先生

ここで、次のようなことが言えます。

ある関係$R$による同値類の代表元を$a$としたとき、その同値類を$[a]_R$と書く

例えば、今回の例では、

$$[佐藤君]_R = \{佐藤君, 鈴木さん, 高橋君\}$$

というように書くわけです。

商集合とは?

集合$A$は「同じクラス」という関係$R$によって2つの同値類に分けることが出来ます。それぞれの代表元を佐藤君、田中さんとすると

$$[佐藤君]_R = \{佐藤君, 鈴木さん, 高橋君\}$$

$$[田中さん]_R = \{田中さん, 伊藤君\}$$

となります。そしてこの同値類を要素とする集合を「商集合」といい、次のように$A/R$という記号で表されます。

$$A/R = \{[佐藤君]_R, [田中さん]_R\}$$

なぜ商集合というのか?

それは、以下の図のように集合$A$を分割したものの集合だからです。

画像に alt 属性が指定されていません。ファイル名: image-15.png

だから$A/R$という記号は「集合$A$を関係$R$で割ったものの集合」みたいな意味があります。

まとめ

今回の重要なポイントを以下にまとめました。同値類と商集合が似たような概念でややこしいので区別できるようにしましょう!

・同値類は「自分と同じ関係のものを全部集めたもの」

・代表元は「同値類の中の代表の要素」

・商集合は「同値類を要素とする集合」

二項関係

お疲れ様でした!

先生
先生
おすすめの参考書

初学者におすすめな参考書を調査してまとめてみました。良かったら参考にしてください。

初学者におすすめの離散数学の参考書4選

コメントを残す

CAPTCHA


PHP Code Snippets Powered By : XYZScripts.com