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