Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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). – Julian Park Oct 7 '12 at 21:25
My understanding is that R U (Diagonal Relation) = Reflexive(R). – Julian Park Oct 7 '12 at 21:29
Yes. and how can you make this as big as possible? – Michael Greinecker Oct 7 '12 at 21:31
My guess is to take it up to n = r elements? – Julian Park Oct 7 '12 at 21:34
If all elements in the orignal relation are off the diagonal, the reflexive closure adds $r$ elements. – Michael Greinecker Oct 7 '12 at 21:35

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.