10.10 同値関係

定義 10.10.1

集合 \(A\) 上の二項関係 \(R\) が対称性 (symmetry) を持つとは、全ての \(x, y \in A\) で次の関係が成り立つことを言う:

\[ x \mathrel{R} y \ \ \longrightarrow \ \ y \mathrel{R}x \]

反射性、対称性、推移性を持つ二項関係を同値関係 (equivalence relation) と呼ぶ。

\(n\) を法とする合同関係は同値関係の重要な例である:

反射性: 全ての整数 \(x\) で \(x \equiv x \ \ (\text{mod } n)\) が成り立つ。
対称性: 整数 \(x\), \(y\) が \(x \equiv y \ \ (\text{mod } n)\) を満たすなら \(y \equiv x \ \ (\text{mod } n)\) が成り立つ。
推移性: 整数 \(x\), \(y\), \(z\) が \(x \equiv y \ \ (\text{mod } n)\) かつ \(y \equiv z \ \ (\text{mod } n)\) を満たすなら \(x \equiv z \ \ (\text{mod } n)\) が成り立つ。

また、この他にも誰もが知っている同値関係が一つある: 等価関係そのものは同値関係である。

全域関数 \(f\) が始域の各要素にラベルを割り当てていると考えれば、「\(f\) の下で同じラベルを持つ」という関係は合同関係である。正確に表現するなら、任意の全域関数 \(f\) に対して \(f\) の始域上の同値関係 \(\equiv_{f}\) を次のように定義できる:

定義 10.10.2

全域関数 \(f\) に対して、\(\operatorname{domain}(f)\) 上の二項関係 \(\equiv_{f}\) を次の規則で定義する:

\[ a \equiv_{f} b \ \ \overset{\text{def}}{\longleftrightarrow}\ \ f(a) = f(b) \]

この二項関係 \(\equiv_{f}\) は反射性、対称性、推移性を等価関係から引き継ぐので同値関係である。この観察からも \(n\) を法とする合同関係が同値関係だと示せる: 剰余補題 (補題 9.6.1) より、\(n\) を法とする合同関係は \(a\) を \(n\) で割った剰余を表す関数 \(r(a)\) に対する \(\equiv_{r}\) に等しい。

実は、「二項関係 \(R\) が同値関係」と「\(R\) が何らかの全域関数 \(f\) に対する \(\equiv_{f}\) に等しい」は同値である (問題 10.58)。そのため、任意の同値関係は何らかのラベル付け規則で「同じラベルを持つ」関係だと理解しても問題ない。

10.10.1 同値類

同値関係は分割と密接な関係を持つ。なぜなら、同値関係による各要素の像を集めた集合族が分割となるからである。

定義 10.10.3

\(R\colon A \to A\) を同値関係とする。任意の要素 \(a \in A\) に対して、\(a\) と \(R\) 関係にある \(A\) の要素全体の集合を同値類 (equivalence class) と呼び、\([a]_{R}\) と表記する。つまり、次のように \([a]_{R}\) を定める:

\[ [a]_{R} ::= \left\{ x \in A \; | \; a \mathrel{R} x \right\} \]

言い換えれば、\([a]_{R}\) は像 \(R(a)\) である。

例えば、\(A = \mathbb{Z}\) であり、\(a \mathrel{R} b\) が \(a \equiv b \ \ (\text{mod } 5)\) を意味するとしよう。このとき次の等式が成り立つ:

\[ [7]_{R} = \left\{ \ldots,\ -3,\ 2,\ 7,\ 12,\ 17,\ 22,\ \ldots \right\} \]

また、\([7]_{R}\) の要素は全て同じ同値類を持つ: つまり \([7]_{R} = [-3]_{R} = [2]_{R} = [12]_{R} = \cdots\) が成り立つ。

\(A\) 上の同値関係と \(A\) の分割の間にも双方向の対応関係が存在する。具体的には、任意の分割の各ブロックを同値類とみなせば同値関係が自明に得られる。逆に、次の定理も成り立つ:

定理 10.10.4

\(A\) 上の同値関係の同値類を集めた集合族は \(A\) の分割である。

この定理の証明は公理を使った議論の簡単な練習問題 (問題 10.57) とする。ここでは例を一つ示す。\(5\) を法とする合同関係は、整数全体の集合を次に示す \(5\) 個の同値類に分割する:

\[ \begin{aligned} \left\{ \ldots,\ -5,\ 0,\ 5,\ 10,\ 15,\ 20,\ \ldots \right\} \\ \left\{ \ldots,\ -4,\ 1,\ 6,\ 11,\ 16,\ 21,\ \ldots \right\} \\ \left\{ \ldots,\ -3,\ 2,\ 7,\ 12,\ 17,\ 22,\ \ldots \right\} \\ \left\{ \ldots,\ -2,\ 3,\ 8,\ 13,\ 18,\ 23,\ \ldots \right\} \\ \left\{ \ldots,\ -1,\ 4,\ 9,\ 14,\ 19,\ 24,\ \ldots \right\} \end{aligned} \]

整数 \(x\), \(y\) に対して「\(x\) と \(y\) が同じ同値類に属する」と「\(x \equiv y \ \ (\text{mod } 5)\) が成り立つ」は同値である。例えば \(6\) と \(16\) は同じ同値類に属するので \(6 \equiv 16 \ \ (\text{mod } 5)\) であり、\(2 \equiv 9 \ \ (\text{mod } 5)\) なので \(2\) と \(7\) は異なる同値類に属する。

ソーシャルな言葉を使えば次のように説明できる。もし SNS で「いいね」が同値関係だったとしたら、その SNS は全体がいくつかのグループに分割される。そして各グループの任意のメンバーは他のメンバー全員を「いいね」し、他のグループに属するアカウントを誰も「いいね」しない。