Answer to Question #234561 in Discrete Mathematics for Reddy mounika

Question

Let X = {1,2,3,4,5,6,7} and R = {x,y/x–y is divisible by 3} in x. Show that R is an equivalence relation.
b) Let A = {1,2,3,4} and let R = {(1,1), (1,2),(2,1),(2,2),(3,4),(4,3), (3,3), (4,4)} be an equivalence relation on R. Determine A/R.
c) Draw the Hasse diagram of lattices, (L1,<) and (L2,<) where L1 = {1, 2, 3, 4, 6, 12} and
L2 = {2, 3, 6, 12, 24} and a < b if and only if a divides b.

Answer 1

a) Let $X = \{1,2,3,4,5,6,7\}$ and $R = \{(x,y)|x-y\text{ is divisible by }3\}$ in $X$. Let us show that $R$ is an equivalence relation. Since $x-x=0$ is divisible by 3 for any $x\in X$, we conclude that $(x,x)\in R$ for any $x\in X$, and hence $R$ is a reflexive relation. If $x,y\in X$ and $(x,y)\in R,$ then $x-y$ is divisible by 3. It follows that $y-x=-(x-y)$ is also divisible by 3, and hence $(y,x)\in R.$

We conclude that the relation $R$ is symmetric. If $x,y,z\in X$ and $(x,y)\in R,\ (y,z)\in R,$ then $x-y$ is divisible by 3 and $y-z$ is divisible by 3. It follows that $x-z=(x-y)+(y-z)$ is also divisible by 3, and hence $(x,z)\in R.$ We conclude that the relation $R$ is transitive. Consequently, $R$ is an equivalence relation.

b) Let $A = \{1,2,3,4\}$ and let $R = \{(1,1), (1,2),(2,1),(2,2),(3,4),(4,3), (3,3), (4,4)\}$ be an equivalence relation on $R$. Let us determine $A/R$. Taking into account that $[a]=\{x\in A\ |\ (x,a)\in R\}$ and hence $[1]=\{1,2\}=[2],\ [3]=\{3,4\}=[4],$ we conclude that $A/R=\{[a]\ |\ a\in A\}=\{[1],[3]\}.$

c) Let us draw the Hasse diagram of lattices, $(L_1,<)$ and $(L_2,<)$ where $L_1 = \{1, 2, 3, 4, 6, 12\}$ and $L_2 = \{2, 3, 6, 12, 24\}$ and a < b if and only if a divides b.

Note that a Hasse diagram is a graphical rendering of a partially ordered set displayed via the cover relation of the partially ordered set with an implied upward orientation. A point is drawn for each element of the poset, and line segments are drawn between these points according to the following two rules:

1. If $x<y$  in the poset, then the point corresponding to $x$ appears lower in the drawing than the point corresponding to $y$.

2. The line segment between the points corresponding to any two elements  $x$ and  $y$ of the poset is included in the drawing iff  $x$ covers $y$  or  $y$  covers $x$.

In our case, $x<y$ if and only if $x|y.$ Therefore, the Hasse diagrams are the following: