はじめに
数学の勉強をしていると、関係 を次の等式を含むような最小の同値関係とする、という定義がよく出てきます。
しかし、この定義は関係 の具体的な構成を与えていないので、この同値関係に関する証明をしようとすると途端に行き詰まってしまいます(例えば、商空間を定義域とするような関数が well-defined であることを証明する場合など)。
この記事では、二項関係から生成される同値関係を構成的に定義し、それが本当に最小の同値関係になっていることを証明します。
また同値類を定義し、同値類と同値関係に関して成り立つ基本的な事柄に関して補足します。
二項関係から生成される関係
を任意の集合
上の二項関係であるとします。このとき、新しい
上の二項関係
を次のように定義します。
\begin{align*}
\forall x,y \in X,\, (x,y) \in R' \iff &\exists n,\, \exists x_{0}, \dots , x_{n} \in X, \\
&x = x_{0} \\
&\land y = x_{n} \\
&\land \left( \forall 0 \leq i \leq n - 1,\, x_{i} = x_{i+1} \lor (x_{i}, x_{i+1}) \in R \lor (x_{i+1}, x_{i}) \in R \right)
\end{align*}
この が
を含むような最小の同値関係であることを示します。
任意の に対して、
とすると、
、
、
とすると、
が成り立つので、
が成り立つ。
- reflexive
任意の に対して、
、
、
とすれば、
が成り立つので、
が成り立つ。
- symmetric
任意の に対して、
とすると、
が存在して、
、
、
を満たす。このとき、
の順序を逆にした列
を新たに
とすると、これは
、
、
を満たす。よって
が成り立つ。
- transitive
任意の に対して、
、
とすると、
と
が存在して条件を満たす。このとき、列
を新たに列
とすると、これは
、
、
を満たす。よって
が成り立つ。
以上より、 が
を含む同値関係であることがわかりました。次に
が
を含むような同値関係の中で最小であることを示します。
任意の を
を含む同値関係であるとする。任意の
に対して、
とすると
が存在して条件を満たす。このとき、
に関する帰納法により証明する。
のとき
のときは
が同値関係であることより
である。
のときは、
が
を含むことより
が成り立つ。
のとき
帰納法の仮定より が成り立つ。
のときと同様の議論により、
が成り立つ。よって
の transitivity により、
が成り立つ。
同値類
集合 上の任意の同値関係
が与えられているときに、任意の
に対して次にように定義される集合を
の同値類と呼びます。
\begin{equation}
[x] = \left\{ y \in X \ \middle| \ x \sim y \right\}
\end{equation}
このとき、次の事柄が成り立ちます。
\land y \in [x'] \Rightarrow [x] = [x'] ]
、
より
、
が成り立つ。すると
が同値関係であることから、
が成り立つ。
すると任意の に対して、
が成り立つ。よって
である。
これは集合 が互いに素な同値類に分解されることを示しています。
同値類と同値関係の性質
最後に基本的な事柄を確認して終わりにします。これによって、同値関係にない要素は違う同値類に属することがわかります。
= [y] \iff x \sim y ]
- only if case
であるから仮定より
が成り立つ。すると定義より
が成り立つ。
- if case
任意の に対して、仮定と
が同値関係であることより、
が成り立つ。よって
である。
