Answer to Question #255384 in Discrete Mathematics for Zain

Question

For each of the following relations, determine whether they are reflexive, symmetric, anti- symmetric, and/or transitive, and give a brief justification for each property. a) R ⊆ Z × Z where xRy iff x = y 2 b) The empty relation: R ⊆ A × A, where A is a non-empty set and R = ∅.

Answer 1

For each of the following relations, let us determine whether they are reflexive, symmetric, anti- symmetric, and/or transitive.

a) $R ⊆ \Z × \Z$ where $xRy$ iff $x = y^ 2$

Since $2^2=4\ne 2,$ we conclude that the pair $(2,2)\notin R,$ and hence $R$ is not a reflexive relation.

Since $4=2^2,$ we conclude $(4,2)\in R.$ On the other hand, $2\ne 4^2,$ and hence $(2,4)\notin R.$ It follows that the relation is not symmetric.

If $(x,y)\in R$ and $(y,x)\in R,$ then $x=y^2$ and $y=x^2.$ Therefore, $x=x^4,$ and hence $x=0$ or $x=1.$ If $x=0,$ then $y=0.$ If $x=1,$ then $y=1.$ It follows that If $(x,y)\in R$ and $(y,x)\in R,$

then $x=y=0$ or $x=y=1,$ and hence the relation is antisymmetric.

Taking into account that $(16,4)\in R$ and $(4,2)\in R,$ but $(16,2)\notin R,$ we conclude that the relation $R$ is not transitive.

b) The empty relation: $R ⊆ A × A$ , where $A$ is a non-empty set and $R = ∅$.

Let $a\in A.$ Since $(a,a)\notin\emptyset= R,$ we conclude that the relation $R$ is not reflexive.

Since the statement $[(x,y)\in\emptyset= R]$ is false, the implication $[(x,y)\in R]\to[(y,x)\in R]$ is true, and hence this relation is symmetric.

Taking into account that the statement $[(x,y)\in R\text{ and }(y,x)\in R]$ is false, the implication $[(x,y)\in R\text{ and }(y,x)\in R]\to [x=y]$ is true, and hence this relation is antisymmetric.

Since the statement $[(x,y)\in R\text{ and }(y,z)\in R]$ is false, the implication $[(x,y)\in R\text{ and }(y,z)\in R]\to [(x,z)\in R]$ is true, and hence this relation is transitive.