In: Computer Science
Consider a set A = { 1, 2, 3, 4, 5, 6, 8}
Consider these relations,
1. R1 = { ( a, b) | a = 3b }
Can you write down the pairs ? one such pair is ( 3, 1)
2. R2 = { (a, b) | 2a = b }
Can you write down the pairs ? one such pair is (2, 4)
3. R3 = { ( a, b) | a >= 2b }
Can you write down the pairs ? one such pair is (4, 2)
4. R4 = { (a, b) | a + b < 4 }
Can you write down the pairs ?
Consider this set A = { a, b, c, d } and the following relations
R6 = { ( a, a ), ( a, b), ( b, b), ( c, d ) }
R7 = { ( a, a), ( b, b ), ( b, c ), ( c, c ), ( c, d), (d, d) }
R8 = { (a, b), (a, d), ( b, a), ( d, a) , ( b, d) , (d, b) }
R9 = { ( a, a), ( b, c) }
R10 = { ( a, b), (b, d), (a, d), ( a, a ) , (b, b), (b, d) }
5. Which of the above relations are reflexive and state why ?
6. Which of the above relations are symmetric and state why ?
7. Which of the above relations are transitive and state why ?
A relation is equivalence when the relation is : reflexive, symmetric AND Transitive.
Please NOTE it is AND. It has to be all three.
8. Is below mentioned R12 a Equivalence relation ? and state why or why not ?
Consider this set S = { 1, 2 , 3}
R12 = { ( 1, 1), ( 1, 2 ), (2, 1) , (2 , 2 ), (3, 3), (1, 3) , (3, 1) }
A = { 1, 2, 3, 4, 5, 6, 8}
1. R1 = { ( a, b) | a = 3b }
Pairs = {(3,1),(6,2)}
2. R2 = { (a, b) | 2a = b }
Pairs = {(1,2),(2,4),(3,6),(4,8)}
3. R3 = { ( a, b) | a >= 2b }
Pairs = {(2,1),(3,1),(4,1),(5,1),(6,1),(8,1),(4,2),(5,2),(6,2),(8,2),(6,3),(8,3),(8,4)}
4. R4 = { (a, b) | a + b < 4 }
Pairs = {(1,2),(2,1)}
A = { a, b, c, d }
R6 = { ( a, a ), ( a, b), ( b, b), ( c, d ) }
R7 = { ( a, a), ( b, b ), ( b, c ), ( c, c ), ( c, d), (d, d) }
R8 = { (a, b), (a, d), ( b, a), ( d, a) , ( b, d) , (d, b) }
R9 = { ( a, a), ( b, c) }
R10 = { ( a, b), (b, d), (a, d), ( a, a ) , (b, b), (b, d) }
5) A reflexive relation is one in which all (a,a) pairs are present in the set for each a in set
R7 is REFLEXIVE
6) A symmetric relation is one in which (a,b) belongs to the relation if (b,a) belongs to the relation
R8 is SYMMETRIC
7)A transitive relation is one in which for all (a,b) and (b,c) that belongs to R (a,c) also belongs to R
R8,R9,R10 are TRANSITIVE
S = { 1, 2 , 3}
R12 = { ( 1, 1), ( 1, 2 ), (2, 1) , (2 , 2 ), (3, 3), (1, 3) , (3, 1) }
it is REFLEXIVE as it has all 3 pairs {(1,1),(2,2),(3,3)}
it is SYMMERTRIC as it has both (1,2) & (2,1) as well as (1,3) & (3,1)
it is TRANSITIVE as there are no pairs for which we have both (a,b) and (b,c)
Hence it is an EQUIVALENCE RELATION