商集合 - pogi-log

商集合

商集合(quotient set)

割り算を一般化したような概念？

おそらく一般的な使い方は集合$ S があったときに同値関係$ \sim の演算子を適用して、同値関係が成り立つものを集めた集合

以下のような擬似Pythonコードのアルゴリズム

code:memo.py

# 同値関係~の演算子が定義されていて、x ~ yが真になるものを集めるイメージ

def equivalence_class(x, S, sim):

return {y for y in S if sim(x, y)}

# 商集合を作るアルゴリズム

# Sが集合以外のデータ構造をも考慮しているため

# 厳密には集合用のアルゴリズムではない

def quotient_set(S, sim):

classes = []

visited = set()

for x in S:

if x not in visited:

cls = equivalence_class(x, S, sim)

classes.append(cls)

visited.update(cls)

return classes

集合$ S を同値関係$ \sim で割っている？的な捉え方もあるため、

$ S/\sim \ :=\ \{ [x] \mid x \in S\}

という表記をして商集合(quotient)と言われるものも定義できる。$ S/\sim を集合$ S の関係$ 〜に関する商集合と読む。

同値類: 同値関係でまとめた集合

剰余類: 算術的文脈の呼称、同値類の特例

Setoid: 集合＋同値関係の構造（型理論で重要？）

ホモトピー集合: 空間をホモトピー同値で割った商集合

確認用

Q. 商集合