数学における二項関係
定義 1
- 二つの集合$X,Y$に対して、 $$ R := \left\{ (x,y): x \in X , y \in Y \right\} \subset X \times Y $$ を (二項) 関係と定義し、次のように表す。 $$ (x,y) \in R \iff x R y $$
- $x R y \iff y R^{-1} x$を満たす $$ R^{-1} : \left\{ (y,x): (x,y) \in R \right\} $$ を$R$の逆関係という。
- すべての$x \in X$に対して、次を満たす$ R \subset X^{2}$を反射的と言う。 $$ x R x $$
- すべての$x,y \in X$に対して、次を満たす$ R \subset X^{2}$を対称的と言う。 $$ x R y \implies y R x $$
- すべての$x,y,z \in X$に対して、次を満たす$ R \subset X^{2}$を推移的と言う。 $$ x R y \land y R z \implies x R z $$
- すべての$x,y \in X$に対して、次を満たす$ R \subset X^{2}$を反対称的と言う。 $$ x R y \land y R x \implies x = y $$
説明
二項関係は、「何かと何かが何かの関係を持つ」というような曖昧な表現ではなく、デカルト積を利用して明確に定義される。関係とは正確にデカルト積の部分集合であり、$x R y$を見て「$x$は$y$に対してどうのこうのという意味ではない」と理解しなければならない。直感的に何となく分かった気になって概念をしっかり把握せずにいると、「関係」が登場するたびに本を読むのが難しくなるだろう。
特に反射的であり、対称的であり、推移的な二項関係を同値関係という。これらの性質は数学全般で非常に重要とされる。
例
二項関係と逆関係
関数$f : X \to Y$は、すべての$x$に対して$y = f(x)$を満たす$y \in Y$が存在し、すべての$x_{1} , x_{2} \in X$に対して $$ x_{1} = x_{2} \implies f(x_{1}) = f(x_{2}) $$ を満たす二項関係だ。もちろん、その逆関数$f^{-1}$が存在すれば、$f^{-1}$は関係$f$の逆関係になる。
反射関係
反射的な関係の例として、等号$=$は$x=x$が常に成り立つ。
対称関係
対称的な関係の例として、独立$\perp$は $$ X \perp Y \implies Y \perp X $$ が常に成り立つ。
推移関係
推移的な関係の例として、不等号$<$は $$ x < y \land y < z \implies x < z $$ が常に成り立つ。
反対称関係
反対称的な関係の例として、包含関係$\subset$は $$ A \subset B \land B \subset A \implies A = B $$ が常に成り立つ。
李興天 訳, Lin You-Feng. (2011). 集合論(Set Theory: An Intuitive Approach): p137~141。 ↩︎