Relations (Discrete Math): if (a - b)/7 is an integer, then

[modi4help]

The relation R on A is defined as follows: for a,b belongs to A, if (a - b)/7 is an integer, then (a,b) belongs to R.
(a) Prove R is an equivalence relation given A is an arbitrary non-empty subset of the integers.
(b) Write down the equivalence classes defined by R if A = Z.
(c) Write down the equivalence classes defined by R if A = { 2^n I n belongs to Z and n is greater than or equal to 1 or n is less than or equal to 7}

 

[soroban]

Re: Relations (Discrete Math)

Hello, modi4help!

\(\displaystyle \text{The relation }\mathsf{R}\text{ on }A\text{ is defined as follows:}\)

\(\displaystyle \text{for }a,b \in A\text{, if }\frac{a - b}{7}\text{ is an integer, then }(a,b) \in \mathsf{R}.\)

\(\displaystyle \text{(a) Prove }\mathsf{R}\text{ is an equivalence relation, given }A\text{ is a non-empty subset of the integers.}\)

\(\displaystyle \text{For any }a \in A.\;a-a \:=\: 0\text{, which is divisible by 7.}\)

\(\displaystyle \text{Hence: }\:a\mathsf{R}a \quad\hdots\quad\mathsf{R}\text{ is reflexive.}\)


\(\displaystyle \text{For any }a,b \in A\text{, if }\frac{a-b}{7}\text{ is an integer, we have: }\:\frac{a-b}{7} \:=\:m\,\text{ for some integer }m.\)
. . \(\displaystyle \text{Then: }\:\frac{b-a}{7} \:=\:-m\text{, also an integer.}\)

\(\displaystyle \text{Hence: }\:a\mathsf{R}b \to b\,\mathsf{R}a \quad\hdots\quad \mathsf{R}\text{ is symmetric.}\)


\(\displaystyle \text{If }a\mathsf{R}b\text{ and }b\,\mathsf{R}c\text{, we have: }\begin{array}{ccccc}\frac{a-b}{7} \:=\: m & \Rightarrow & a-b \:=\:7m & [1] \\ \frac{b-c}{7} \:=\:n & \Rightarrow & b-c \:=\:7n & [2]\end{array}\quad\text{for integers }m,n\)

\(\displaystyle \text{Add [1] and [2]: }\;a - c \:=\:7m + 7n \quad\Rightarrow\quad a-c \:=\:7(m+n) \quad\Rightarrow\quad \frac{a-c}{7} \:=\:m+n\)

\(\displaystyle \text{Since }m+n\text{ is an integer, we have: }\:a\mathsf{R}c\)

\(\displaystyle \text{Hence: }a\mathsf{R}b \wedge b\,\mathsf{R}c \to a\mathsf{R}c \quad\hdots\quad \mathsf{R} \text{ is transitive.}\)


\(\displaystyle \text{Therefore, }\mathsf{R}\text{ is an equivalence relation.}\)

\(\displaystyle \text{(b) Write down the equivalence classes defined by }\mathsf{R}\text{ if }A = Z.\)

. . \(\displaystyle \begin{array}{c}\{a\,|\,a \,=\,7k,\:k \in Z\}\quad\;\; \\ \\[-4mm] \{a\,|\,a\,=\,7k+1,\:k\in Z\} \\ \\[-4mm] \{a\,|\,a \,=\,7k+2,\:k\in Z\} \\ \\[-4mm] \{a\,|\,a\,=\,7k+3,\:k\in Z \} \\ \\[-4mm] \{a\,|\,a\,=\,7k+4,\:k\in Z\} \\ \\[-4mm] \{a\,|\,a\,=\,7k+5,\:k\in Z\} \\ \\[-4mm] \{a\,|\,a\,=\,7k+6,\:k\in Z\} \end {array}\)

\(\displaystyle \text{(c) Write down the equivalence classes defined by }\mathsf{R}\text{ if }A \:=\: \{ 2^n \:|\: n \in Z,\; 1 \leq n \leq 7\}\)

\(\displaystyle \text{We have: }\;A \;=\;\{2, 4, 8, 16, 32, 64, 128\}\)


\(\displaystyle \text{There are five pairs satisfying }\mathsf{R}.\)

. . \(\displaystyle (2,16),\;(2,128),\;(4,32),\;(8,64),\;(16,128)\)