10.11 二項関係のまとめ
-
二項関係 \(R \colon A \to A\) は頂点集合が \(A\) である有向グラフに等しい。
-
反射性: \(R\) が次の関係を満たすとき、\(R\) は反射性 (reflexivity) を持つと言う:
\[ \forall x \in A.\ x \mathrel{R} x \]反射性を持つ二項関係に等しい有向グラフは全ての頂点が自己ループを持つ。
-
非反射性: \(R\) が次の関係を満たすとき、\(R\) は非反射性 (irreflexivity) を持つと言う:
\[ \operatorname{\text{\footnotesize NOT}} (\exists x \in A.\ x \mathrel{R} x) \]非反射性を持つ二項関係に等しい有向グラフには自己ループが存在しない。
-
対称性: \(R\) が次の関係を満たすとき、\(R\) は対称性 (symmetry) を持つと言う:
\[ \forall x, y \in A.\ \ x \mathrel{R} y \ \ \longrightarrow \ \ y \mathrel{R} x \]対称性を持つ二項関係に等しい有向グラフでは、辺 \(\langle x \to y \rangle\) が存在するとき逆方向の辺 \(\langle y \to x \rangle\) も存在する。
-
非対称性: \(R\) が次の関係を満たすとき、\(R\) は非対称性 (asymmetry) を持つと言う:
\[ \forall x, y \in A.\ \ x \mathrel{R} y \ \ \longrightarrow \ \ \operatorname{\text{\footnotesize NOT}} (y \mathrel{R} x) \]非対称性を持つ二項関係に等しい有向グラフでは、任意の異なる二頂点間に辺は高々 \(1\) 個しか存在しない。また自己ループも存在しない。
-
反対称性: \(R\) が次の関係を満たすとき、\(R\) は反対称性 (antisymmetry) を持つと言う:
\[ \forall x \neq y \in A.\ \ x \mathrel{R} y \ \ \longrightarrow \ \ \operatorname{\text{\footnotesize NOT}} (y \mathrel{R} x) \]この条件は次の条件と同値である:
\[ \forall x, y \in A. \ \ (x \mathrel{R} y \ \operatorname{\text{\footnotesize AND}} \ y \mathrel{R} x) \ \ \longrightarrow \ \ x = y \]反対称性を持つ二項関係に等しい有向グラフでは、任意の異なる二頂点間に辺は高々 \(1\) 個しか存在しない。ただし自己ループは存在する可能性がある。
-
推移性: \(R\) が次の関係を満たすとき、\(R\) は推移性 (transitivity) を持つと言う:
\[ \forall x, y, z \in A.\ \ (x \mathrel{R} y \ \operatorname{\text{\footnotesize AND}} \ y \mathrel{R} z) \ \ \longrightarrow \ \ x \mathrel{R} z \]推移性を持つ二項関係に等しい有向グラフでは、\(u\) から \(v\) への長さが正の路が存在するとき \(u\) から \(v\) への辺が存在する。
-
線形順序: \(R\) が次の関係を満たすとき、\(R\) を線形順序 (linear order) と呼ぶ:
\[ \forall x \neq y \in A.\ \ (x \mathrel{R} y \ \operatorname{\text{\footnotesize OR}}\ y \mathrel{R} x) \]線形順序に等しい有向グラフでは、任意の異なる二頂点間に辺が存在する。
-
狭義半順序:
\[ \begin{aligned} & \text{二項関係 \(R\) が狭義半順序 (strict partial order)} \\ & \quad \ \ \longleftrightarrow \ \ \text{\(R\) が推移性と非反射性を持つ} \\ & \quad \ \ \longleftrightarrow \ \ \text{\(R\) が推移性と非対称性を持つ} \\ & \quad \ \ \longleftrightarrow \ \ \text{\(R\) が何らかの DAG の正歩道関係} \end{aligned} \] -
弱半順序:
\[ \begin{aligned} & \text{二項関係 \(R\) が弱半順序 (weak partial order)} \\ & \quad \ \ \longleftrightarrow \ \ \text{\(R\) が推移性と反対称性と反射性を持つ} \\ & \quad \ \ \longleftrightarrow \ \ \text{\(R\) が何らかの DAG の歩道関係} \end{aligned} \] -
同値関係
\[ \begin{aligned} & \text{二項関係 \(R\) が同値関係 (equivalence relation)} \\ & \quad \ \ \longleftrightarrow \ \ \text{\(R\) が反射性と対称性と推移性を持つ} \\ & \quad \ \ \longleftrightarrow \ \ \text{\(R\) が domain\((R)\) の何らかの分割に対する} \\ & \quad \hphantom{{}\ \ \longleftrightarrow \ \ {}} \text{「同じブロックに属する」関係に等しい} \end{aligned} \]