計算機科学のブログ

関係同値関係結合律

本の表紙

情報系のための離散数学
 楽天ブックス
Yahoo!ショッピング
au PAY マーケット

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第5章(関係)、章末問題、5.1の解答を求めてみる。

任意の

(a, d) \in S \circ (Q \circ R)

に対して、あるCの元cが存在して、

(a, c) \in Q \circ R \land (c, d) \in S

また、あるBの元bが存在して、

(a, b) \in R \land (b, c) \in Q

このとき、

(b, d) \in S \circ Q

なので、

(a, d) \in (S \circ Q) \circ R

よって、

S \circ (Q \circ R) \subset (S \circ Q) \circ R

任意の

(a, d) \in (S \circ Q) \circ R

に対して、あるBの元bが存在して、

\begin{array}{l} (a, b) \in R \\ (b, d) \in S \circ Q \end{array}

また、あるCの元cが存在して、

\begin{array}{l} (b, c) \in Q \\ (c, d) \in S \end{array}

このとき、

(a, c) \in Q \circ R

なので、

(a, d) \in S \circ (Q \circ R)

よって、

(S \circ Q) \circ R \subset S \circ (Q \circ R)

ゆえに、

S \circ (Q \circ R) = (S \circ Q) \circ R