Answer to Question #209917 in Discrete Mathematics for Sach

Question

Show that the following relations are Partial order relations.

(a) R on the set of integers Z, defined by, R = {(a, b) | a ≤ b}

(b) R on the set of integers Z, defined by, R = {(a, b) | a ≥ b}

(c) R on the set of positive integers N, defined by, R = {(a, b) | a divides b} [Note: It is divisibility

relation]

(d) R on the Power set of a set S, defined by, R = {(A, B) | A is a subset of B} [Note: It is set inclu￾sion relation]

Answer 1

Let us show that the following relations are partial order relations.

(a) $R$ on the set of integers $\Z$ , defined by, $R = \{(a, b) | a ≤ b\}.$

Since $a\le a$ for any $a\in\Z,$ we conclude that $(a, a)\in R$ for any $a\in\Z,$ and hence the relation $R$ is reflexive. If $(a,b)\in R$ and $(b,a)\in R,$ then $a\le b$ and $b\le a$, and hence $a=b.$ It follows that $R$ is an antisymmetric relation. If $(a,b)\in R$ and $(b,c)\in R,$ then $a\le b$ and $b\le c$, and thus $a\le c.$ Therefore, $R$ is a transitive relation. We conclude that $R$ is a partial order relation.

(b) $R$ on the set of integers $\Z$ , defined by, $R = \{(a, b) | a ≥ b\}.$

Since $a\ge a$ for any $a\in\Z,$ we conclude that $(a, a)\in R$ for any $a\in\Z,$ and hence the relation $R$ is reflexive. If $(a,b)\in R$ and $(b,a)\in R,$ then $a\ge b$ and $b\ge a$, and hence $a=b.$ It follows that $R$ is an antisymmetric relation. If $(a,b)\in R$ and $(b,c)\in R,$ then $a\ge b$ and $b\ge c$, and thus $a\ge c.$ Therefore, $R$ is a transitive relation. We conclude that $R$ is a partial order relation.

(c) $R$ on the set of positive integers $\N$, defined by, $R = \{(a, b) | a \text{ divides }b\}.$

Since $a| a$ for any $a\in\N,$ we conclude that $(a, a)\in R$ for any $a\in\N,$ and hence the relation $R$ is reflexive. If $(a,b)\in R$ and $(b,a)\in R,$ then $a| b$ and $b| a$. Therefore, $a\le b$ and $b\le a$, and hence $a=b.$ It follows that $R$ is an antisymmetric relation. If $(a,b)\in R$ and $(b,c)\in R,$ then $a| b$ and $b| c$, and thus $a| c.$ Therefore, $R$ is a transitive relation. We conclude that $R$ is a partial order relation.

(d) $R$ on the Power set of a set $S$, defined by, $R = \{(A, B) | A \text{ is a subset of } B\}.$

Since $A\subset A$ for any $A\subset S$ we conclude that $(A, A)\in R$ for any $A\subset S,$ and hence the relation $R$ is reflexive. If $(A,B)\in R$ and $(B,A)\in R,$ then $A\subset B$ and $B\subset A$, and hence $A=B.$ It follows that $R$ is an antisymmetric relation. If $(A,B)\in R$ and $(B,C)\in R,$ then $A\subset B$ and $B\subset C$, and thus $A\subset C.$ Therefore, $R$ is a transitive relation. We conclude that $R$ is a partial order relation.