計算機科学のブログ

関係 整数、法として合同、剰余、零、同値関係、反射律、対称律、推移律

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

任意の整数nに対して、

( n - n ) = 0 = m · 0 + 0

よって反射律が成り立つ。

任意の整数n、 l に対して、

n - l = m · q + 0

を満たす整数q が存在するならば、

l - n = m ( - q ) + 0

よって対称律が成り立つ。

任意の整数n 、 I 、 k に対して

n - l = m a , l - k = m b

を満たす整数a、 b が存在するなら、

n - k = ( n - l ) + ( l - k ) = m a + m b = m ( a + b )

よって、 推移律を満たす。

ゆえに、 同値関係である。