二項関係
\(A\)が集合であるとします。このとき、積集合\(A \times A\)の部分集合を\(A\)上の二項関係または関係といいます。
\(R\)が\(A\)上の二項関係、すなわち積集合\(A \times A\)の部分集合であるとします。\((x, y) \in R\)のとき、\(x\)と\(y\)は関係\(R\)で結ばれているといいます。他にも\(x\)と\(y\)は\(R\)関係があると言ったりもします。
そしてこのことを普通、\(x {\sim} y\)や\(xRy\)、\(R(x, y)\)などと表します。
例えば、\(A = \{1, 2, 3\}\)上の関係\(R = \{(1, 1), (2, 3)\}\)があるとしましょう。この場合、\(1 {\sim} 1\)と\(2 {\sim} 3\)のみになります。
同値関係
以下の３つの条件を満たすとき、\(A\)上の関係\(R\)が\(A\)上の同値関係であるといいます。
\(\begin{align} &1) \: 反射律： \; Aの任意の元xに対して \, x {\sim} x \\ &2) \: 対称律： \; x {\sim} y \, ならば \, y {\sim} x\\ &3) \: 推移律： \; x {\sim} y \, かつ \, y {\sim} z \, ならば \, x {\sim} z\end{align}\)
例を挙げながらこれらの定義を確認しましょう。
\(A = \{1, 2, 3\}\)上の関係\(R_1 = \{(1, 1), (2, 2), (3, 3)\}\)は反射律を満たします（同値関係でもある）。
\(A = \{1, 2, 3\}\)上の関係\(R_2 = \{(1, 3), (3, 1)\}\)は対称律を満たします（推移律も満たす）。
\(A = \{1, 2, 3\}\)上の関係\(R_3 = \{(1, 2), (2, 3), (1, 3)\}\)は推移律を満たします。
\(A = \{1, 2, 3, 4\}\)上の関係、
は同値関係です。
類別（分割）と類
次に、集合\(A\)の部分集合の族（集合）\(\mathscr{F} = \{A_i \: ; i \in I\}\)が以下の３つの条件を満たすとき、\(\mathscr{F}\)を\(A\)の類別または分割といいます。
\(\begin{align}&1) \; A_i \neq \emptyset \\ &2) \; A = \bigcup_{i \in I}{A_i} \\ &3) \; i, j \in I \, ならば \, A_i \cap A_j = \emptyset\end{align}\)
また、各\(A_i\)のことを類別\(\mathscr{F}\)による類といいます。
例えば、\(A = \{1, 2, 3, 4, 5\}\)に対して\(\mathscr{F} = \{\{1\}, \{2, 4\}, \{3,5\}\}\)は\(A\)の類別です。
同値類
\(R\)を集合\(A\)上の同値関係とします。ある元\(a {\in} A\)に着目して、\(a\)と\(R\)関係のある元\(x {\in} A\)全部の集合を\(X_{a \in A}\)として求めます。
このようにして元\(a {\in} A\)ごとに得られた集合\(X_{a {\in} A}\)の集合を\(\mathscr{F}\)とします。
このとき\(\mathscr{F}\)は\(A\)の類別であり、\(\mathscr{F}\)の類を同値関係\(R\)の同値類といいます。
例えば、\(A = \{1, 2, 3, 4, 5\}\)上の同値関係、
に対して\(\mathscr{F} = \{\{1\}, \{2, 4\}, \{3,5\}\}\)が求まります。すると確かに\(\mathscr{F}\)は\(A\)の類別であり、同値類は\(\{1\}\)と\(\{2, 4\}\)と\(\{3,5\}\)になります。
また、ある元\(a {\in} A\)と\(R\)関係のある元\(x {\in} A\)全部の集合は「元\(a\)の\(A\)における同値類」と呼ばれ、次のように表します。
商集合
\(R\)が\(A\)上の同値関係のとき、\(R\)の同値類全部の集合を\(A\)の\(R\)による商集合といい、\(A \backslash R\)とかきます。
前項で挙げた例の場合を考えてみます。\(A = \{1, 2, 3, 4, 5\}\)上の関係、
に対して、同値類は\(\{1\}\)と\(\{2, 4\}\)と\(\{3,5\}\)です。したがって、\(A \backslash R = \{\{1\}, \{2, 4\}, \{3,5\}\}\)です。
