search
Log In
4 votes
676 views

Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m < n$ and $R^m = R^n$.

in Set Theory & Algebra
edited by
676 views

2 Answers

7 votes
 
Best answer

For every non-empty set $A$, if $R$ is a binary relation on $A$ then-

$R^0$ is an identity relation on A which is defined as - $R^0= \{(x,x) \mid x \in A \}$

Also, if a relation has a cycle of length $n$ then its $n^{th}$ power is reflexive an identity relation. So for first component, $R_3$ is reflexive and hence $R_0=R_3.$ 
Similarly, for second component $R_0=R_5.$  LCM of $3$ and $5$ is $15.$ 
So $m=1$ and $n=12.$

$\text{LCM}$ of $3$ and $5$ is $15.$ So, $m = 0 \ and \ n=15.$
Check this for having some intuition behind $R^0$.

PS: Here, $R_1 = R4; R_2 = R_6$ and we get $m=1, n=12.$ But question asks for smallest $m,n.$


selected by
0
+Saumya29

R1={(a,b),(b,c),(c,a)}

R2={(a,c),(b,a),(c,b)}

R3={(a,a),(b,b),(c,c)}

R4={(a,b),(b,c),(c,a)}

so for 1st digraph m=1 and n=4 R1=R4 this what you want to say.?
0
yes exactly
1

Part (B)

For clear understanding and solution for part (B) just watch Kamala krithivasan mam video lectures on Relations.

1

@Soumya29   1,12 cannot be answer.

It should be 0,15

1
Thanks, @warrior and @Rahul. I edited my comment.
0
nice explanation debashish sir
0
How m=1 and n=12 is a solution
1

I didn't understand this part " LCM of 3 and 5 is 15. So, m=0 and n=15"

can someone please explain , how to get m and n

1

@Sherrinford This should help you.

@Soumya29 You need to edit your answer as $R_2 $ not equal to $R_6$ but $R_1 $ equal to $R_6$

0

I did not get how (1,12) is a solution.

The first component repeats after every 3rd step.

And the second component repeats after every 5th step.

Both the component together form our relation. So they will be equal to original relation after every 15th step.

So (0,15) is one solution.

The other solution should be (1,16), (2,17) and so on....as it repeats after every 15th step.

In the below video also it is said that it repeats after every 15th step....

So how (1,12) is a solution, Please someone explain.

 

21 votes

First component repeats after every 3rd power of R,

R0 -> R1 -> R2 -> R0

R0 = R3 = R6 = ........

Second component repeats after every 5th power of R,

R0 -> R1 -> R2 -> R3 -> R4 -> R0

R0 = R5 = R10 = ........

The relation R is the combination of two components.

So R will repeat after every LCM(3,5) = 15th power of R.

Thus R0 = R15 = R30 = ........

So, m = 0 & n = 15.

For more information, watch this lecture:

1
Not 15th power but 15k power of R where k=0,1,2......

Related questions

17 votes
6 answers
1
1.5k views
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$
asked Sep 26, 2014 in Set Theory & Algebra Kathleen 1.5k views
16 votes
3 answers
2
2.2k views
The binary relation $R = \{(1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)\}$ on the set $A=\{1, 2, 3, 4\}$ is reflexive, symmetric and transitive neither reflexive, nor irreflexive but transitive irreflexive, symmetric and transitive irreflexive and antisymmetric
asked Sep 26, 2014 in Set Theory & Algebra Kathleen 2.2k views
19 votes
3 answers
3
3.7k views
Let $R_1$ and $R_2$ be two equivalence relations on a set. Consider the following assertions: $R_1 \cup R_2$ is an equivalence relation $R_1 \cap R_2$ is an equivalence relation Which of the following is correct? Both assertions are true Assertions (i) is true but assertions (ii) is not true Assertions (ii) is true but assertions (i) is not true Neither (i) nor (ii) is true
asked Sep 26, 2014 in Set Theory & Algebra Kathleen 3.7k views
12 votes
3 answers
4
3.3k views
Suppose $A$ is a finite set with $n$ elements. The number of elements in the largest equivalence relation of A is $n$ $n^2$ $1$ $n+1$
asked Sep 26, 2014 in Set Theory & Algebra Kathleen 3.3k views
...