同値関係と商集合

2項関係 binary relation

集合 $X$ の元の対に関する条件を $X$ の2項関係(binary relation)といい,$R$ で表します.

グラフ graph

2項関係 $R$ によって定義される $X \times X$ の部分集合,\[\{(x,y) \in X \times X\ |\ R\}\]を,$R$ のグラフ(graph)といいます.

同値 equivalent

$R$ と $R'$ を $X$ の2項関係,$C,C' \subset X \times X$ を,そのグラフであるとき,$C=C'$ ならば $R$ と $R'$ は同値(equivalent)といいます.

同値関係 equivalence relation

$(x,y) \in X \times X$ が $R$ を満たすことを,\[x \sim_{R} y\]もしくは,\[R(x,y)((x,y) \in X \times X)\]と表します.ここで,$X \times X$ を $A$ とします.

このとき,$R$ が以下の3つの条件を満たすとき,$R$ は $X$ 上の同値関係(equivalence relation)といいます.\[\forall x \in A[R(x,x)]\tag{1}\]\[\forall x,y \in A[R(x,y) \to R(y,x)]\tag{2}\]\[\forall x,y,z \in A[R(x,y) \land R(y,z) \to R(x,z)]\tag{3}\]なお,上記の条件$(1),(2),(3)$を反射律(reflexive law),対称律(symmetry law),推移律(transitive law)といいます.

同値類 equivalence class

集合 $A$ 上の反射的,対称的,推移的な2項関係 $R(x,y)(x,y \in A)$ は同値関係といい,\[x \sim_{R} y\]もしくは,\[x \simeq y\]と表します.

このとき,$A$ は $\sim_{R}$ ,$\simeq$ によって類別,分割されます.

ここで,$x \in A$ について,\[[x]:=\{y \in A\ |\ y \simeq x\}\]を,$x$ を代表元(representative)とする同値類(equivalence class)といいます.

商集合 quotient set

同値類の考え方から,\[[x]=[y] \Longleftrightarrow x \simeq y\]となります.

同値類の全体の集合は,\[A \backslash \simeq := \{[x]\ |\ x \in A\}\]と表し,$A$ の $\simeq$ による商集合(quotient set)といいます.


Mathematics is the language with which God has written the universe.





















文脈自由文法 - 同値関係と商集合 - 正規文法 - 形式文法と有限オートマトン - 文と言語と文法