Binary Relations - Set Theory

Question

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$.

Answer 1

(1): Reflexive closure: all we have to ensure is that for all $a\in A$, we have $aRa'$ (shorthand for $(a,a)\in R'$) for the extended $R'\supseteq R$. It gives at most $+n$ elements, i.e. $M=r+n$ will be. Find the desired example to achieve this.

(2,3): For any $a,b\in A$, show that if $a<b$ then $(a,b)\in \bar R_i$ (where $\bar R_i$ denotes the transitive closure of the given $R_i$, $i=1,2$). Then, if $a\ge b$ for (2), we also have $a\,\bar R_1\, n\, R_1\, 1$.

(4): Well, $R_1$ is one of the smallest (any permutation of $A$ would give a similar smallest relation). I think, it wants to say minimum $n$ pairs are needed to generate the whole $A\times A$ by transitive closure..

Answer 2

(4) Suppose that $R$ has fewer than $n$ elements; then $\operatorname{dom}R$ and $\operatorname{ran}R$ have fewer than $n$ elements, so there is some $a\in A$ that is not in $\operatorname{dom}R\cap\operatorname{ran}R$. In other words, there is some $a\in A$ that does not appear both as a first component and as a second component in $R$.

If $a\notin\operatorname{dom}R$, there is no pair of the form $\langle a,x\rangle$ in $R$; show that the transitive closure $\bar R$ of $R$ will also contain no pair of the form $\langle a,x\rangle$ and therefore cannot be $A\times A$. Then make a similar argument to cover the case in which $a\notin\operatorname{ran}R$.