Answer to Question #297363 in Discrete Mathematics for Ravi

Question

{F} 2.

Find the transitive closures of these relations on {1, 2, 3, 4}.

a) {(1, 2), (2,1), (2,3), (3,4), (4,1)}

b) {(2, 1), (2,3), (3,1), (3,4), (4,1), (4, 3)}

c) {(1, 2), (1,3), (1,4), (2,3), (2,4), (3, 4)}

d) {(1, 1), (1,4), (2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2)}

3.

Find the smallest relation containing the relation {(1, 2), (1, 4), (3, 3), (4, 1)} that is

a) reflexive and transitive.

b) symmetric and transitive.

c) reflexive, symmetric, and transitive.

4.

Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack.

a) {(0, 0), (1, 1), (2, 2), (3, 3)}

b) {(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}

c) {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}

d) {(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2),(3, 3)}

e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0),(2, 2), (3, 3)}

Answer 1

2.

a) {(1, 2), (2,1), (2,3), (3,4), (4,1)} contains an oriented cycle {(1, 2), (2,3), (3,4), (4,1)}, the transitive closure of which is the maximal relation:

{(1,1), (1, 2), (1,3), (1,4), (2,1), (2, 2), (2,3), (2,4), (3,1), (3, 2), (3,3), (3,4), (4,1), (4, 2), (4,3), (4,4)}

Therefore, the transitive closure of the initial relation will be also the maximal relation.

b) {(2, 1), (2,3), (3,1), (3,4), (4,1), (4, 3)}

The transitive closure of the relation {(2,3), (3,4), (4,1)} is the strong linear order on the set {1, 2, 3, 4}. The pairs (2, 1), (3,1) lie in the transitive closure and do not affect on the transitive closure.

But the pairs {(3,4), (4,3)} provide the equivalence of the elements 3 and 4. Therefore, the transitive closure of the initial relation is the following

{(2,3), (2,4), (2,1), (3, 4), (3,1), (4,3), (4,1)}

c) {(1, 2), (1,3), (1,4), (2,3), (2,4), (3, 4)}

The transitive closure of the relation {(1,2), (2,3), (3,4)} is the strong linear order on the set {1, 2, 3, 4}. All the other pairs {(1,3), (1,4), (2,4)} are consistent with the transitive closure. Therefore, the transitive closure of the initial relation is the following

{(1, 2), (1,3), (1, 4), (2,3), (2,4), (3,4)}

d) The relation {(1, 1), (1,4), (2,1), (2,3), (3,1), (3, 2), (3,4), (4, 2)} contains the cyclic relation

{(1,4), (4, 2), (2,3), (3,1)}, the transitive closure of which is the maximal relation:

{(1,1), (1, 2), (1,3), (1,4), (2,1), (2, 2), (2,3), (2,4), (3,1), (3, 2), (3,3), (3,4), (4,1), (4, 2), (4,3), (4,4)}

Therefore, the transitive closure of the initial relation will be also the maximal relation.

3. {(1, 2), (1, 4), (3, 3), (4, 1)}

a) the smallest relation containing the relation {(1, 2), (1, 4), (3, 3), (4, 1)} that is reflexive and transitive must contain the transitive closure of this relation and the diagonal relation, that is, the union $\{(1, 2), (1, 4), (3, 3), (4, 1), (4,2)\}\cup \{(1,1), (2,2), (3,3), (4,4)\}$ = $\{(1,1), (1, 2), (1, 4), (2,2), (3, 3), (4, 1), (4, 2), (4,4)\}$

Since the latter relation is already reflexive and transitive, it is the required minimal such relation.

b) If a relation is symmetric and transitive, then it is also reflexive:

Indeed, if $(x,y)\in R$ then $(y,x)\in R$ (symmetry) and $(x,x)\in R$ (transitivity).

Therefore, the smallest relation containing the relation {(1, 2), (1, 4), (3, 3), (4, 1)} that is symmetric and transitive, is the same as in c).

c) If a relation is reflexive, symmetric, and transitive, it is an equivalence relation. We have $4\sim 1\sim 2$ and $3\sim 3$. Therefore, the smallest relation containing the relation {(1, 2), (1, 4), (3, 3), (4, 1)} that is reflexive, symmetric, and transitive, is the following

{(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (4, 1), (4, 2), (4, 4), (3, 3)}.

4.

a) R= {(0, 0), (1, 1), (2, 2), (3, 3)}

b) R={(0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}

c) R={(0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}

d) R={(0, 0), (1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2),(3, 3)}

e) R={(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3)}

Fill the following table:

$\begin{vmatrix}Relation & a & b & c & d & e\\ Reflexive & + & - & + & + & +\\ Symmetric & + & + & + & + & -\\ Transitive & + & - & + & - & -\\ \end{vmatrix}$

Relation R in b) is not reflexive, since $(1,1)\notin R$

Relation R in e) is not symmetric, since $(1,2)\in R$ but $(2,1)\notin R$.

Relation R in b) is not transitive, since $(0,2), (2,3)\in R$ but $(0, 3)\notin R$.

Relation R in d) is not transitive, since $(2,3),(3,1)\in R$ but $(2, 1)\notin R$.

Relation R in e) is not transitive, since $(2, 0), (0, 1)\in R$ but $(2, 1)\notin R$.

Therefore, only the relations in a) and c) are equivalence relations.