同値関係
$2$ 項関係
定義《$2$ 項関係》
$A$ を集合とする.
$A$ の元の対に関する条件を $A$ における $2$ 項関係 (binary relation) と呼び, 特定の記号や文字 $R$ などで表す.
$A$ の元 $a,$ $a'$ が $2$ 項関係 $R$ を満たすとき, $a\,R\,a'$ のように表す.
例《$2$ 項関係》
- (1)
- 集合 $A$ の元 $a,$ $a'$ に対する $a = a'$ であるという関係を相等関係 (equality) と呼ぶ.
- (2)
- $n$ を $0$ でない整数とする. 整数 $a,$ $a'$ に対して, $a-a'$ が $n$ で割り切れるとき, $a,$ $a'$ は $n$ を法として合同 (congruent modulo $n$) であるといい, $a \equiv a'\ (\text{mod}\ n)$ で表す. この関係を $n$ を法とする合同関係 (congruence relation) と呼ぶ.
同値関係
定義《同値関係》
$A$ を集合とする.
- (1)
- $A$ における $2$ 項関係 $\sim$ が次の (E1)～(E3) を満たすとき, $\sim$ は $A$ におけるの同値関係 (equivalence relation) であるという.
- (E1)
- 反射法則 (law of reflexivity): $A$ の任意の元 $a$ に対して, \[ a \sim a.\]
- (E2)
- 対称法則 (law of symmetry): $A$ の任意の元 $a,$ $a'$ に対して, \[ a \sim a' \Longrightarrow a' \sim a.\]
- (E3)
- 推移法則 (law of transitivity): $A$ の任意の元 $a,$ $a',$ $a''$ に対して, \[ a \sim a',\ a' \sim a'' \Longrightarrow a \sim a''.\]
- (2)
- $\sim$ を $A$ におけるの同値関係とする. $A$ の各元 $a$ に対して, 集合 \[\{ x \in A \mid x \sim a\}\] を $\sim$ に関する $a$ の同値類 (equivalence class) と呼ぶ. さらに, $\sim$ に関する $A$ の元 $a$ の同値類全体からなる集合を $A$ の $\sim$ による商集合 (quotient set) と呼び, $A/\!\sim$ で表す.
例《同値関係》
上記の例における (1), (2) の $2$ 項関係はいずれも同値関係である.
- (1)
- 相等関係 $=$ に関する集合 $A$ の元 $a$ の同値類は $\{ a\}$ である.
- (2)
- 合同関係 $\equiv\ (\text{mod}\ n)$ に関する整数 $r$ $(0 \leqq r < n)$ の同値類は $n$ で割った余りが $r$ である整数全体 $\{ nq+r \mid q \in \mathbb Z\}$ である. これを $r+n\mathbb Z$ で表し, $r = 0$ のときは $n\mathbb Z$ で表す.
- (3)
- 集合 $X$ の部分集合 $S,$ $S'$ に対する包含関係 $S \subset S'.$
- (4)
- 実数 $a,$ $a'$ に対する大小関係 $a \leqq a'.$
- (5)
- 整数 $a,$ $a'$ に対する $a$ が $a'$ を割り切るという関係 (整除関係といい, $a \mid a'$ で表す).
命題《写像が定める同値関係》
$f:A \to B$ を写像とする.
$A$ の元 $a,$ $a'$ に対して $f(a) = f(a')$ であるという関係は $A$ 上の同値関係である.
証明
$A$ の元 $a,$ $a',$ $a''$ に対して,
\[ f(a) = f(a)\]
であることから (E1) が成り立ち,
\[ f(a) = f(a') \Longrightarrow f(a') = f(a)\]
であることから (E2) が成り立ち,
\[ f(a) = f(a'),\ f(a') = f(a'') \Longrightarrow f(a) = f(a'')\]
であることから (E3) が成り立つ.
定義《写像が定める同値関係》
上記の命題の同値関係を $f$ が定める同値関係と呼び, $R_f$ で表す.