1
$\begingroup$

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

  • 0
    I'm rather confused that the question doesn't specify what the relation actually is (I know it's clearly on the given set A).2012-10-07
  • 0
    My understanding is that R U (Diagonal Relation) = Reflexive(R).2012-10-07
  • 0
    Yes. and how can you make this as big as possible?2012-10-07
  • 0
    My guess is to take it up to n = r elements?2012-10-07
  • 0
    If all elements in the orignal relation are off the diagonal, the reflexive closure adds $r$ elements.2012-10-07
  • 0
    If the reflexive closure adds r elements, would that mean M = n + r elements?2012-10-07
  • 0
    Yes.$~~~~~~~~~~$2012-10-07
  • 0
    So the first part is done, thank you again. Would you have anything to say for parts 2, 3, and 4?2012-10-07
  • 0
    Come on, Julian, let's see a little effort on your part. What do you know about the problems? Can you tell us what "transitive closure" means? Can you share your understanding of the phrase, "universal relation"? Can you work out the transitive closure of, say, $\{{(1,2),(2,3),(3,1)\}}$?2012-10-07
  • 0
    In general, R is a subset of transitive(R). I believe transitive(R) by definition is: transitive(R) = R U R^2 U ... U R^n where A is a finite set with n elements. The transitive closure of {(1,2), (2,3), (3,1)} would be {(1,2), (2,3), (3,1), (1,3), (2,1), (3,2)}? The Universal Relation A x A for a set A is the set of (a,b) where a, b are elements of A.2012-10-07
  • 0
    Right. So, do you see how (2) is true for $n=3$? Do you see why it will be true for all $n$?2012-10-08

2 Answers 2

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

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

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