Ques 1: State whether the following statements are TRUE or FALSE:
GATE 1987
The union of two equivalence relations is also an equivalence relation.
Solution: Equivalence Relation: Relation is reflexive, symmetric, transitive.
A relation R1 is defined on a set A={a,b,c}.
R1={(a,a),(b,b),(c,c),(a,b),(b,a)} → Equivalence Relation.
A relation R2 is defined on a set A={a,b,c}.
R2={(a,a),(b,b),(c,c),(c,b),(b,c)} → Equivalence Relation.
R = (R1 U R2) = {(a,a),(b,b),(c,c),(a,b),(b,a),(c,b),(b,c)}. → Not an Equivalence Relation.
R is reflexive, symmetric but not transitive. because (a,b) and (b,c) doesn’t imply (a,c).
Ans: FALSE. (The union of two equivalence relations may or may not be an equivalence relation.)
NOTE: You can also take relation defined on different sets and then take union.
The union of two reflexive relations is always reflexive.
The union of two symmetric relations is always symmetric.
This is not true for transitivity that’s why the answer is false.
Ques 2: How many binary relations are there on a set A with n elements?
GATE 1987
Solution:
Binary relation on a set A is a subset of (AxA).
Ternary relation on a set A is a subset of (AxAxA).
now AxA will contain n2 terms
So the total no of binary relation on set A
= cardinality of power set of (A⨉A)
= ∣ p(A⨉A) ∣
=2^(n^2)
Ques 3: How many one-to-one functions are there from a set A with n elements onto itself?
GATE 1987
Solution: There are n! one to one function possible from a set of n elements to itself.
i.e., nPn=n!
Ques 4: The complement(s) of the element ′a′ in the lattice shown in below figure is (are) ____
GATE 1988
Solution:
lub(a,e)=lub(a,b)=lub(a,c)=lub(a,d)=I (Upper Bound of Lattice)
glb(a,e)=glb(a,b)=glb(a,c)=glb(a,d)=O (Lower Bound of Lattice)
So, {b,c,d,e} all are complements of a.
Ques 5: The transitive closure of the relation {(1,2),(2,3),(3,4),(5,4)}{(1,2),(2,3),(3,4),(5,4)} on the set {1,2,3,4,5}{1,2,3,4,5} is ___________.
GATE 1989
Solution: {(1,2),(2,3),(1,3) ,(3,4),(2,4),(1,4),(5,4)}
Ques 6: Let S be an infinite set and S1…,Sn be sets such that S1∪S2∪⋯∪Sn=S. Then
GATE 1993
(A) at least one of the sets Si is a finite set
(B) not more than one of the sets Si can be finite
(C) at least one of the sets Si is an infinite
(D) not more than one of the sets Si can be infinite
Ans: (C) at least one of the sets Si is an infinite
Ques 7: Let A be a finite set of size n. The number of elements in the power set of A×A is:
GATE 1993
(A) 2^2^n
(B) 2^n^2
(C) 2n
(D) 2^n
Ans: (B)
Solution:Cardinality of A×A=n^2
Cardinality of power set of A×A=2^n^2
Ques 8: Some group (G,o) is known to be abelian. Then, which one of the following is true for G?
GATE 1994
(A) g=g−1 for every g∈G
(B) g=g2 for every g∈G
(C) (goh)2=g2oh2 for every g,h∈G
(D) G is of finite order
Ans: (C)
Solution: Abelian group is commutative and associative. So,
(goh)2
=(goh)o(goh)
=(go(hog)oh)
=(go(goh)oh)
=(gog)o(hoh)
=g2oh2
So, C is correct.
Ques 9: Let R be a symmetric and transitive relation on a set A. Then
GATE 1995
(A) R is reflexive and hence an equivalence relation
(B)R is reflexive and hence a partial order
(C) R is reflexive and hence not an equivalence relation
(D) None of the above
Ans: (D) None of the above
Solution: A symmetric and Transitive relation need not be reflexive.
Let A={1,2,3} and
relation R={(1,2),(2,1),(1,1),(2,2)}.
R is symmetric and transitive but not reflexive.
Because (3,3) is not there.
Ques 10: The number of elements in the power set P(S) of the set S={{∅},1,{2,3}} is:
GATE 1995
(A) 2
(B) 4
(C) 8
(D) None of the above
Ans: (C) 8
Solution: no of element in power set is 2^(set size)
In {∅,1,{2,3}} there are 3 elements
i.e ∅,1,{2,3}
Note {2,3} is a single element
now power set 2^3=8
Note: ∅ and {∅} are not same.
first means no element whereas second means one element which is ∅.