This is an assignment question which I had - the instructor did NOT post solutions to these problems. Although they were not tested/marked, I would like assistance on these.
The following questions are about binary relations on the set A = {1, 2,..., n}.
(1) Suppose R is a relation on A containing r elements. Find an upper bound M on the number of elements in the reflexive closure of R, and prove that your bound is as good as possible by giving an example of a relation R whose reflexive closure has exactly M elements.
(2) Show that the transitive closure of the relation $R_1 = \{(1, 2),(2, 3),..., (n - 1, n), (n, 1)\}$ is the universal relation $A \times A$.
(3) What is the transitive closure of the relation $R_2 = \{(1, 2), (2, 3),..., (n - 1, n)\}$?
(4) Prove that $R_1$ is the smallest binary relation whose transitive closure is $A \times A$.