圏論/代数系/関係, 同値関係

2.1 $A,B$ を集合とする． 集合論的直積 $A\times B=\{(a,b)|a\in A,b\in B\}$ の（任意に定められた）部分集合 $\rho$ を $A$ の元と $B$ の元の間の関係という．

$(a,b)\in \rho$ のとき $a$ と $b$ は関係 $\rho$ にある， または関係 $\rho$ をみたすといい， このとき $\rho (a,b)$ あるいは $a\rho b$ と書く．特に $A=B$ のとき $\rho$ は $A$ の内部関係，または単に $A$ 上の関係 という．

$A$ の元と $B$ の元との間に他の関係 $\sigma$ があり，$A\times B$ の部分集合として $\sigma \subset \rho$ であるとき，$\sigma$ は $\rho$ より弱い関係， $\rho$ は $\sigma$ より強い関係という．これは $a\sigma b$ ならば $a\rho b$ でることと同等である．また $\Sigma$ が $A$ の元と $B$ の元の間の関係の族であるとき， $A\times B$ の中でのその集合論的共通部分を $\bigwedge \Sigma$ であらわす． $\sigma =\bigwedge \Sigma$ であるとき $a\sigma b$ であることとすべての $\rho \in \Sigma$ について $a\rho b$ であることとは同等である． この $\sigma$ を $\Sigma$ の交という．

2.2 $A$ は集合，$\rho$ はその上の関係とする．$\rho$ が $A$ の中で条件

反射律

すべての元 $a$ に対して $a\rho a$

対称律

各元 $a$, $b$ に対して $a\rho b$ ならば $b\rho a$

推移律

各元 $a$, $b$, $c$ に対して $a\rho b$ かつ $b\rho c$ ならば $a\rho c$

を同時にみたすとき，$\rho$ は $A$ の上で同値条件をみたす，または同値関係であるといい， $\rho$ が同値関係であるとき $a\rho b$ である $a$ と $b$ は $\rho$ について互いに同値である という．

2.3 $\rho$ が $A$ の上の同値関係のとき，各 $a\in A$ に対して

$U_{\rho }(a)=\{x\in A|x\rho a\}$

とおく．$\rho$ の反射律から各 $a\in A$ について $a\in U_{\rho }(a)$ で特に $U_{\rho }(a)\neq \phi$． また $c\in U_{\rho }(a)\cap U_{\rho }(b)$ のとき， 対称律から $a\in U_{\rho }(c)$ で， よって $x\in U_{\rho }(a)$ なら推移律から $x\in U_{\rho }(c)$ で，さらに $x\in U_{\rho }(b)$ すなわち $U_{\rho }(a)\subset U{\rho }(b)$． 同様にして $U_{\rho }(b)\subset U{\rho }(a)$ で，従って $U_{\rho }(a)=U{\rho }(b)$ となる．よって

${\mathfrak {U}}=\{X|$ ある $a\in A$ について $X=U_{\rho }(a)\}$

とおけば ${\mathfrak {U}}$ は ${\mathfrak {P}}(A)$ の部分集合 で三つの条件
$1^{\circ }\quad \$ どの $X\in {\mathfrak {U}}$ も空ではない
$2^{\circ }\quad \$ $X,Y\in {\mathfrak {U}}$ ならば $X\cap Y=\phi$ であるかまたは $X=Y$ である　
$3^{\circ }\quad \$ $\bigcup {\mathfrak {U}}=A$

をみたす．${\mathfrak {P}}(A)$ の部分集合 ${\mathfrak {U}}$ がこの三条件をみたすとき ${\mathfrak {U}}$ は $A$ の類別といい， 各 $X\in {\mathfrak {U}}$ はこの類別の同値類という．また $\rho$ から上のように定められた ${\mathfrak {U}}$ を $\rho$ から 導かれた類別という．

逆に ${\mathfrak {U}}$ が $A$ の任意の類別のとき，$a,b$ が同一の $X\in {\mathfrak {U}}$ に属するとき $a\rho b$ とすれば，$\rho$ は $A$ 上の同値関係となり，もとの ${\mathfrak {U}}$ はこれから導かれた類別となる．

2.4 2.2 の中で考察された $\rho$ についての三つの条件， 反射律， 対称律， 推移律 はすべて次の形をしているのに気がづく．

”すべての元 $a,b,c,d,\cdots ,x,y$ について（これらの変数のいくつかは同一のものであってもよい）， もし $a\rho b$，$c\rho d$，$\cdots$（これらを仮設式という）であるならば $x\rho y$ (これを終結式という）である．”

関係に関する条件がこの形をしているとき，この条件は 含意型であるという．

[注] 特別な場合として反射律のように仮設式の集合が空であってもかまわない． この場合終結式が無条件に成立つことを意味する．

補題　

$\alpha$ が集合 $A$ の上の関係に関する含意型の条件，$\Sigma$ は $A$ の上の関係のある族とする． もしすべての $\rho \in \Sigma$ が $\alpha$ をみたすなら $\sigma \in \bigwedge \Sigma$ も $\alpha$ をみたす．

証明　 $A$ の元$a,b,c,d,\cdots$ に対して $\sigma$ が $\alpha$ の各仮設式 $a\sigma b$ 等を成立させたとする． このときすべての $\rho \in \Sigma$ について $a\rho b$ 等が成立ち， よってすべての $\rho \in \Sigma$ に対して終結式 $x\rho y$ が成立つ． 従って $x\sigma y$ で $\sigma$ は $\alpha$ をみたす．（証明終）

系　 $\Sigma$ が集合 $A$ 上の同値関係の集合ならば $\bigwedge \Sigma$ も同値関係である．

2.5 $\rho$ と $\sigma$ が共に集合 $A$ 上の同値関係で， $\rho$ が $\sigma$ より強ければ $a,x\in A$ について $x\sigma a$ ならば $x\rho a$ となり，よって $U_{\sigma }(a)\subset U_{\rho }(a)$． 従って $\sigma$ による同値類はすべて $\rho$ による一つの同値類の部分集合となる． 一般に $A$ の二つの類別 ${\mathfrak {U}},{\mathfrak {B}}$ があり，${\mathfrak {U}}$ の各同値類が ${\mathfrak {B}}$ の一つの同値類に含まれるとき，${\mathfrak {U}}$ は ${\mathfrak {B}}$ より 細かい， ${\mathfrak {B}}$ は ${\mathfrak {U}}$ より 粗いという． 同値関係は強いほど対応する類別は粗くなり， 特に 2.4 の系に現れる $\bigwedge \Sigma$ を $\sigma$ とすれば， $U_{\sigma }(a)=\bigcap \{U_{\rho }(a)|\rho \in \Sigma \}$ が成り立つ．

2.6 同一関係 $=$ はすべての同値関係の中で最も弱いものであり， またすべての元 $a,b$ に対して $a\upsilon b$ とした全称関係 $\upsilon$ はどのような関係よりも強い同値関係である．さらに一般に

定理　 $\tau$ を集合 $A$ の上の任意に与えられた関係とするとき， $\tau$ より強い同値関係の中で最も弱いもの $\sigma$ が 存在する．

証明 $\Sigma$ を $\tau$ より強い同値関係全体の集合とすれば、 全称関係は $\Sigma$ に入るから $\Sigma$ は空ではない． $\sigma =\wedge \Sigma$ とすればよい。（証明終）

また同じことであるが，$a\sigma b$ の条件として $a=b$ であるかまたは

$\tau$ 鎖条件： 元 $x_{1},x_{2},\cdots ,x_{n-1}$ が存在し， さらに $x_{0}=a,x_{n}=b$ として、

各 $k=1,2,\cdots ,n$ に対して $x_{k-1}\tau x_{k}$ であるかまたは $x_{k}\tau x_{k-1}$ である

がみたされることにすればよい． このような $x_{1},x_{2},\cdots ,x_{n-1}$ を $a$ と $b$ とを結ぶ $\tau$ 鎖 という． 上のように定めた $\sigma$ が同値関係であること、また $\sigma$ が $\tau$ より強い同値関係であれば，$\tau$鎖で結ばれる二元 $a,b$ に対して $a\sigma b$ に対して $a\sigma b$ でなければならないことは明らかである． 上の $\sigma$ を $\tau$ から生成された同値関係という．

2.7　 $n$ を正の整数とするとき、$a,b\in Z$ に対して $a-b$ が $n$ の倍数であるという関係 $a\equiv b{\pmod {n}}$ は同値条件である． $m$ も正の整数のとき，関係 $a\equiv b{\pmod {m}}$ が $a\equiv b{\pmod {n}}$ より強くなるのは $m$ が $n$ の約数のときに限る．

同様に実数 $a,b$ に対して $a-b$ が整数であるという関係 $a\equiv b{\pmod {1}}$， $a-b$ が有理数であるという関係 $a\equiv b{\pmod {Q}}$， $a-b$ が代数的数であるという関係 $q\equiv b{\pmod {Alg.no.}}$ 等は $R$ 上の同値関係で、この順に強くなっている．

集合 $X,Y$ に対して $X\triangle Y=(X\cup Y)-(X\cap Y)$ を $X$ と $Y$ の対称差 という。 $X\triangle Y$ が有限であるという関係 $X\equiv Y{\pmod {\mathfrak {a}}}$， $X\triangle Y$ がある無限濃度 ${\mathfrak {m}}$ より小さいという関係 $X\equiv Y{\pmod {\mathfrak {m}}}$ は同値関係で，特に後者は ${\mathfrak {m}}$ が大きいほど強くなる．