はじめに
プログラミングではしばしば剰余計算 (割った余りの計算) が出てくる。このとき、やって良い操作と良くない操作の区別をつけたり、効率よく計算を行ったりするために、背景にある理屈を学ぶことは有用と思う。
同値関係
まずは剰余計算で利用する "等しい" の意味を定める。ただし、剰余計算よりも一般的な場合を扱う。
集合 \(X\) とその元 \(a, b, c \in X\) に対して
- 反射律: \(a \sim a\)
- 対象律: \(a \sim b \Rightarrow b \sim a\)
- 推移律: \(a \sim b, b \sim c \Rightarrow a \sim c\)
を満たすとき、二項関係 \(\sim\) は同値関係であるという。
同値関係の例
整数環 \(\mathbb{Z}\) に対して、ある \(0\) でない元 \(n \in \mathbb{Z}\) を一つ取る。任意の \(a, b \in \mathbb{Z}\) に対して \(a, b\) を \(n\) で割った余りが等しいとき \(a \equiv b \mod n\) と書く。このとき \(\equiv\) は同値関係となる。
反射律と対象律は明らかなので、推移律だけ示す。
\(a, b, c \in \mathbb{Z}\) が \(a \equiv b \mod n, b \equiv c \mod n\) を満たすとする。このとき、ある \(p, q \in \mathbb{Z}\) が存在して \(a = p \times n + b, b = q \times n + c\) とかける。後者を前者に代入して \(a = p \times n + q \times n + c\) より \(a = (p + q) \times n + c\) となり \(a \equiv c \mod n\) とわかった。
整数環 \(\mathbb{Z}\) に対して、通常の意味の \(=\) は同値関係である。また不等号 \(>\) や \(\geq\) は、推移律を満たすものの、反射律と対象律や対象律を満たさないので同値関係ではない。
同値類
同値関係によって等しいとみなせる要素の集まりに分割することを考える。
集合 \(X\) とその元 \(x \in X\) を一つ取り \(X\) の同値関係を \(\sim\) とする。このとき \(x\) と同値関係にある \(X\) の元全体の集合
を \(x\) の同値類という。
例えば、整数環 \(\mathbb{Z}\) に対して 3 で割った余りを考えると
など。
\(x, y \in X\) に対して、その同値類 \(C(x), C(y)\) に交わりがあれば \(C(x) = C(y)\) である。
任意の \(a \in C(x)\) に対して \(b \in C(x) \cap C(y)\) を取る。すると \(b\) は \(C(x)\) の元であるので \(a \sim b\) となる。一方で \(b\) は \(C(y)\) の元でもあるので \(a \in C(y)\) となり \(C(x) \subseteq C(y)\) が示せた。逆の包含関係も同様に示せる。
このようにして同値類の全体は集合 \(X\) を互いに交わらない部分集合に分割する。同値類全体の集合を、集合 \(X\) の同値関係 \(\sim\) による商集合といい \(X/\sim\) と書く。
\(X\) から \(X/\sim\) への上への写像
を考える。このとき \(x \in X\) に対して \(C(x)\) を対応させるとき、つまり \(f(x) = C(x)\) とするとき、写像 \(f\) を自然な射影という。写像 \(f\) は単射であるが、一般には全射ではない。
\(C(x)\) に対して \(x\) を \(C(x)\) の代表元という。