search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
4 votes
644 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
644 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$

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.1k 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.1k 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
...