計算機科学のブログ

関係 グラフ、同値関係、反射律、対称律、推移律、商集合、外延的記法

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

任意のXの元aに対して、

( a , a ) ∈ G ( R )

なので反射律を満たす。

任意のX の元a、 bに対して、

( a , b ) ∈ G ( R ) ⇒ ( b , a ) ∈ G ( R )

なので対称律を満たす。

任意のXの元a、 b 、 c に対して、

( a , b ) ∈ G ( R ) ∧ ( b , c ) ∈ G ( R ) ⇒ ( a , c ) ∈ G ( R )

なので推移律を満たす。

よって、問題の関係は同値関係である。

商集合。

X / R = { { v , y } , { w , z } , { x } }