## Set-Theory

 Question 1
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ______.
 A 7
Engineering-Mathematics       Set-Theory       GATE 2020
Question 1 Explanation:
Lagrange’s Theorem:
If ‘H” is a subgroup of finite group (G,*) then O(H) is the divisor of O(G).
Given that the order of group is 35. Its divisors are 1,5,7,35.
It is asked that the size of largest possible subgroup other than G itself will be 7.
 Question 2
Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is _________.
 A 41 B 42 C 43 D 44
Engineering-Mathematics       Set-Theory       Gate 2018
Question 2 Explanation:
Lagranges Theorem:
For any group ‘G’ with order ‘n’, every subgroup ‘H’ has order ‘k’ such that ‘n’ is divisible by ‘k’.
Solution:
Given order n = 84
Then the order of subgroups = {1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84}
As per the proper subgroup definition, it should be “42”.
 Question 3

Consider the set X = {a,b,c,d e} under the partial ordering

R = {(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}.

The Hasse diagram of the partial order (X,R) is shown below.

The minimum number of ordered pairs that need to be added to R to make (X,R) a lattice is _________.

 A 0 B 1 C 2 D 3
Engineering-Mathematics       Set-Theory       GATE 2017(set-02)
Question 3 Explanation:
R = {(a,a), (a,b), (a,c), (a,d), (a,e), (b,b), (b,c), (b,e), (c,c), (c,e), (d,d), (d,e), (e,e)}
As per the definition of lattice, each pair should have GLB, LUB.
The given ‘R’ has GLB, LUB for each and every pair.
So, no need to add extra pair.
Thus no. of required pair such that Hasse diagram to become lattice is “0”.
 Question 4

A function f:N+ → N+, deﬁned on the set of positive integers N+, satisﬁes the following properties:

f(n) = f(n/2)           if n is even
f(n) = f(n+5)           if n is odd

Let R = {i|∃j: f(j)=i} be the set of distinct values that f takes. The maximum possible size of R is __________.

 A 2 B 3 C 4 D 5
Engineering-Mathematics       Set-Theory       2016 set-01
Question 4 Explanation:
f(n)= f(n⁄2)          if n is even
f(n)= f(n+5)        if n is odd

We can observe that

and f(5) = f(10) = f(15) = f(20)
Observe that f(11) = f(8)
f(12) = f(6) = f(3)
f(13) = f(9) = f(14) = f(7) = f(12) = f(6) = f(3)
f(14) = f(9) = f(12) = f(6) = f(3)
f(16) = f(8) = f(4) = f(2) = f(1) [repeating]
So, we can conclude that
‘R’ can have size only ‘two’ [one: multiple of 5’s, other: other than 5 multiples]
 Question 5

A binary relation R on ℕ × ℕ is deﬁned as follows: (a,b)R(c,d) if a≤c or b≤d. Consider the following propositions:

P: R is reﬂexive
Q: Ris transitive

Which one of the following statements is TRUE?

 A Both P and Q are true. B P is true and Q is false. C P is false and Q is true. D Both P and Q are false.
Engineering-Mathematics       Set-Theory       GATE 2016 set-2
Question 5 Explanation:
For every a,b ∈ N,
a≤c ∨ b≤d
Let a≤a ∨ b≤b is true for all a,b ∈ N
So there exists (a,a) ∀ a∈N.
It is Reflexive relation.
Consider an example
c = (a,b)R(c,d) and (c,d)R(e,f) then (a,b)R(e,f)
This does not hold for any (a>e) or (b>f)
eg:
(2,2)R(1,2) as 2≤2
(1,2)R(1,1) as 1≤1
but (2,2) R (1,1) is False
So, Not transitive.
 Question 6

Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements:

I. Each compound in U\S reacts with an odd number of compounds.
II. At least one compound in U\S reacts with an odd number of compounds.
III. Each compound in U\S reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

 A Only I B Only II C Only III D None
Engineering-Mathematics       Set-Theory       GATE 2016 set-2
Question 6 Explanation:
There are set of ‘23’ different compounds.
U = 23
∃S ∋ (S⊂U)
Each component in ‘S’ reacts with exactly ‘3’ compounds of U,

If a component ‘a’ reacts with ‘b’, then it is obvious that ‘b’ also reacts with ‘a’.
It’s a kind of symmetric relation.>br> If we connect the react able compounds, it will be an undirected graph.
The sum of degree of vertices = 9 × 3 = 27
But, in the graph of ‘23’ vertices the sum of degree of vertices should be even because
(di = degree of vertex i.e., = no. of edges)
But ‘27’ is not an even number.
To make it an even, one odd number should be added.
So, there exists atleast one compound in U/S reacts with an odd number of compounds.
 Question 7
Suppose L = {p, q, r, s, t} is a lattice represented by the following Hasse diagram: For any x, y ∈ L, not necessarily distinct, x ∨ y and x ∧ y are join and meet of x, y respectively. Let L3 = {(x,y,z): x, y, z ∈ L} be the set of all ordered triplets of the elements of L. Let pr be the probability that an element (x,y,z) ∈ L3 chosen equiprobably satisfies x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z). Then
 A pr = 0 B pr = 1 C 0 < pr ≤ 1/5 D 1/5 < pr < 1
Engineering-Mathematics       Set-Theory       GATE 2015 (Set-01)
Question 7 Explanation:
Total number of elements i.e., ordered triplets (x,y,z) in L3 are 5×5×5 i.e., 125 n(s) = 125
Let A be the event that an element (x,y,z)∈ L3 satisfies x ∨(y∧z) = (x∨y) ∧ (x∨z) Since q∨(r∧s) = q∨p = q
and (q∨r)∧(q∨s)=t∧t=t q∨(r∧s)≠(q∨r)∧(q∨s)
Therefore, (x,y,z) = (q,r,s),(q,s,r),(r,q,s),(r,s,q),(s,r,q),(s,q,r)
i.e., 3! = 6 elements will not satisfy distributive law and all other (x,y,z) choices satisfy distributive law
n(A) = 125-6 = 119
∴ required probability is 119/125
⇒ 1/5
 Question 8
Consider the operations f(X, Y, Z) = X'YZ + XY' + Y'Z'  and  g(X′, Y, Z) = X′YZ + X′YZ′ + XY Which one of the following is correct?
 A Both {f} and {g} are functionally complete B Only {f} is functionally complete C Only {g} is functionally complete D Neither {f} nor {g} is functionally complete
Engineering-Mathematics       Set-Theory       GATE 2015 (Set-01)
Question 8 Explanation:
A function is functionally complete if (OR, NOT) or (AND, NOT) are implemented by it.
f(X,X,X)=X'XX'+XX'+X'X'
=0+0+X'
=X'
Similarly, f(Y,Y,Y)=Y' and f(X,Z,Z)=Z'
f(Y',Y',Z')=(Y')'Y'Z'+Y'(Y')'+(Y')'(Z')'
=YY'Z'+Y'Y+YZ
=0+0+YZ
=YZ
We have derived NOT and AND. So f(X,Y,Z) is functionally complete.
g(X,Y,Z)=X'YZ+X'YZ'+XY
g(X,X,X)=X'XX+X'XZ'+XX
=0+0+X
=X
Similarly, g(Y,Y,Y)=Y and g(Z,Z,Z)=Z
NOT is not derived. Hence, g is not functionally complete.
 Question 9
Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?
 A R is symmetric and reflexive but not transitive B R is reflexive but not symmetric and not transitive C R is transitive but not reflexive and not symmetric D R is symmetric but not reflexive and not transitive
Engineering-Mathematics       Set-Theory       GATE 2015 -(Set-2)
Question 9 Explanation:
Reflexive:
In aRb, 'a' and 'b' are distinct. So it can never be reflexive.
Symmetric:
In aRb, if 'a' and 'b' have common divisor other than 1, then bRa, i.e., 'b' and 'a' also will have common divisor other than 1. So, yes symmetric.
Transitive:
Take (3, 6) and (6, 2) elements of R. For transitivity (3, 2) must be the element of R, but 3 and 2 don't have a common divisor. So not transitive.
 Question 10
The cardinality of the power set of {0, 1, 2, … 10} is _________
 A 2046 B 2047 C 2048 D 2049
Engineering-Mathematics       Set-Theory       GATE 2015 -(Set-2)
Question 10 Explanation:
Cardinality of the power set of {0, 1, 2, … , 10} is 211 i.e., 2048.
 Question 11

Suppose U is the power set of the set S = {1, 2, 3, 4, 5, 6}. For any T ∈ U, let |T| denote the number of element in T and T' denote the complement of T. For any T, R ∈ U, let T \ R be the set of all elements in T which are not in R. Which one of the following is true?

 A ∀X ∈ U (|X| = |X'|) B ∃X ∈ U ∃Y ∈ U (|X| = 5, |Y| = 5 and X ∩ Y = ∅) C ∀X ∈ U ∀Y ∈ U (|X| = 2, |Y| = 3 and X \ Y = ∅) D ∀X ∈ U ∀Y ∈ U (X \ Y = Y' \ X')
Engineering-Mathematics       Set-Theory       GATE 2015(Set-03)
Question 11 Explanation:
As X and Y are elements of U, so X and Y are subsets of S.
(A) False. Consider X = {1,2}. Therefore, X' = {3,4,5,6}, |X| = 2 and |X'| = 4.
(B) False. Because for any two possible subsets of S with 5 elements should have atleast 4 elements in commonc. Hence X∩Y cannot be null.
(C) False. Consider X = {1,4}, Y= {1,2,3} then X\Y = {4} which is not null.
(D) True. Take any possible cases.
 Question 12
Let R be a relation on the set of ordered pairs of positive integers such that ((p,q),(r,s)) ∈ R if and only if p - s = q - r. Which one of the following is true about R?
 A Both reflexive and symmetric B Reflexive but not symmetric C Not reflexive but symmetric D Neither reflexive nor symmetric
Engineering-Mathematics       Set-Theory       GATE 2015(Set-03)
Question 12 Explanation:
Since p-q ≠ q-p
∴(p,q) R (p,q)
⇒ R is not reflexive.
Let (p,q) R (r,s) then p-s = q-r
⇒ r-q = s-p
⇒ (r,s) R (p,q)
⇒ R is symmetric.
 Question 13
Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U. Consider the following two statements:
```S1: There is a subset of S that is larger than every other subset.
S2: There is a subset of S that is smaller than every other subset.```
Which one of the following is CORRECT?
 A Both S1 and S2 are true B S1 is true and S2 is false C S2 is true and S1 is false D Neither S1 nor S2 is true
Engineering-Mathematics       Set-Theory       Gate 2014 Set -02
Question 13 Explanation:
Given: S = {1, 2, 3, …, 2014}
U⊂S, V⊂S
Let U = {1, 2, 3}
V = {2, 3, 4}
Symmetric difference:
(U – V) ∪ (V – U) = {1} ∪ {4} = {1, 4}
The minimum element in the symmetric difference is 1 and 1∈U.
S1: Let S = Universal set = {1, 2, … 2014}
This universal set is larger than every other subset.
S2: Null set is smaller than every other set.
Let U = { }, V = {1}
Symmetric difference = ({ } – {1}) ∪ ({1} – { }) = { } ∪ {1} = {1}
So, U < V because { } ∈ U.
 Question 14
Let X and Y be finite sets and f: X→Y be a function. Which one of the following statements is TRUE?
 A For any subsets A and B of X, |f(A ∪ B)| = |f(A)|+|f(B)| B For any subsets A and B of X, f(A ∩ B) = f(A) ∩ f(B) C For any subsets A and B of X, |f(A ∩ B)| = min{ |f(A)|,f|(B)|} D For any subsets S and T of Y, f -1 (S ∩ T) = f -1 (S) ∩ f -1 (T)
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 14 Explanation:
The function f: x→y.
We need to consider subsets of 'x', which are A & B (A, B can have common elements are exclusive).
Similarly S, T are subsets of 'y'.

To be a function, each element should be mapped with only one element.
(a) |f(A∪B)|=|f(A)|+|f(B)|
|{a,b,c}|∪|{c,d,e}| = |{a,b,c}| + |{c,d,e}|
|{a,b,c,d,e}| = 3+3
5 = 6 FALSE
(d) To get inverse, the function should be one-one & onto.
The above diagram fulfills it. So we can proceed with inverse.
f-1 (S∩T )=f-1 (S)∩f-1 (T)
f-1 (c)=f-1 ({a,b,c})∩f-1 ({c,d,e})
2={1,2,3}∩{2,4,5}
2=2 TRUE
 Question 15
Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L ≠ G and that the size of L is at least 4.  The size of L  is __________.
 A 5 B 6 C 7 D 8
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 15 Explanation:
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order (number of elements) of every subgroup H of G divides the order of G.
So, 15 is divided by {1, 3, 5, 15}.
As minimum is 4 and total is 15, we eliminate 1,3,15.
 Question 16
If V1 and V2 are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dimension of V1∩V2   is ______.
 A 2 B 3 C 4 D 5
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 16 Explanation:
In a 6 dimensional vector space, sub space of 4 dimensional subspaces V1, V2 are provided. Then the V1∩V2?
For eg: a two dimensional vector space have x, y axis. For dimensional vector space, it have x, y, z axis.
In the same manner, 6 dimensional vector space has x, y, z, p, q, r (assume).
Any subspace of it, with 4 dimensional subspace consists any 4 of the above. Then their intersection will be atmost 2.
[{x,y,z,p} ∩ {r,q,p,z}] = #2
V1 ∩ V2 = V1 + V2 - V1 ∪ V2 = 4+4+(-6) = 2
 Question 17
 A P, Q and R are true B Only Q and R are true C Only P and Q are true D Only R is true
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 17 Explanation:
f:{0,1,…,2014}→{0,1,…,2014} and f(f(i))=i

So f(i)should be resulting only {0, 1, …2014}
So, every element in range has a result value to domain. This is onto. (Option R is correct)
We have ‘2015’ elements in domain.
So atleast one element can have f(i) = i,
so option ‘Q’ is also True.
∴ Q, R are correct.
 Question 18
Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?
 A In any planar embedding, the number of faces is at least n/2+ 2 B In any planar embedding, the number of faces is less than n/2+ 2 C There is a planar embedding in which the number of faces is less than n/2+ 2 D There is a planar embedding in which the number of faces is at most n/(δ+1)
Engineering-Mathematics       Set-Theory       Gate 2014 Set -03
Question 18 Explanation:
Euler’s formula:
v – e + f = 2 →①
Point ① degree of each vertex is minimum ‘3’.

3×n≥2e
e≤3n/2
From ①
n-3n/2+f=2⇒
 Question 19
A binary operation ⊕ on a set of integers is defined as x ⊕ y = x+ y2. Which one of the following statements is TRUE about ⊕?
 A Commutative but not associative B Both commutative and associative C Associative but not commutative D Neither commutative nor associative
Engineering-Mathematics       Set-Theory       Gate 2013
Question 19 Explanation:
Cumulative property:
A binary relation on a set S is called cumulative if a*b = b*a ∀ x,y∈S.
Associative property:
A binary relation on set is called associative if (a*b)*c = a*(b*c) ∀ x,y∈S.
Given x⊕y = x2 + y2 --------(1)
Replace x, y in (1)
y⊕x = y2 + x2 which is same as (1), so this is cumulative
(x⊕y)⊕z = (x2 + y2) ⊕ z
= (x2 + y2) + z2
= x2 + y2 + z2 + 2x2y2 ----------(2)
x⊕(y ⊕ z) = x ⊕ (y2 + z2)
= x2 + (y2 + z2)2
= x2 + y2 + z2 + 2y2z2 ----------- (3)
(2) & (3) are not same so this is not associative.
 Question 20

Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all a ∈ A. Which of the following statements is always true for all such functions f and g?

 A g is onto ⇒ h is onto B h is onto ⇒ f is onto C h is onto ⇒ g is onto D h is onto ⇒ f and g are onto
Engineering-Mathematics       Set-Theory       Gate 2005-IT
Question 20 Explanation:
g(f(a)) is a composition function which is A→B→C.
If h: A→C is a onto function, the composition must be onto, but the first function in the composition need to be onto.
So, B→C is must be onto.
 Question 21
Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S1 and S2 in C, either S⊂ S2 or S⊂ S1. What is the maximum cardinality of C?
 A n B n + 1 C 2(n-1) + 1 D n!
Engineering-Mathematics       Set-Theory       Gate 2005-IT
Question 21 Explanation:
Consider an example:
Let A = {a, b, c}, here n = 3
Now, P(A) = {Ø, {a}, {b}, {c}, {a,b}, {b,c}, {{a}, {a,b,c}}
Now C will be contain Ø (empty set) and {a,b,c} (set itself) as Ø is the subset of every set. And every other subset is the subset of {a,b,c}.
Now taking the subset of cardinality, we an take any 1 of {a}, {b}, {c} as none of the set is subset of other.
Let's take {2}
→ Now taking the sets of cardinality 2 -{a,b}, {b,c}
→ {b} ⊂ {a,b} and {b,c} but we can't take both as none of the 2 is subset of the other.
→ So let's take {c,a}.
So, C = {Ø, {b}, {b,c}, {a,b,c}}
→ So, if we observe carefully, we can see that we can select only 1 set from the subsets of each cardinality 1 to n
i.e., total n subsets + Ø = n + 1 subsets of A can be there in C.
→ So, even though we can have different combinations of subsets in C but maximum cardinality of C will be n+1 only.
 Question 22
Let n = p2q, where p and q are distinct prime numbers. How many numbers m satisfy 1 ≤ m ≤ n and gcd (m, n) = 1? Note that gcd (m, n) is the greatest common divisor of m and n.
 A p(p - 1) B pq C (p2 - 1)(q - 1) D p(p - 1)(q - 1)
Engineering-Mathematics       Set-Theory       Gate 2005-IT
Question 22 Explanation:
n = p2q, [p, q are prime numbers]
→ No. of multiples of p in n = pq [n = p⋅p⋅q]
→ No. of multiples of q in n = p2 [n = p2q]
→ Prime factorization of n contains only p & q.
→ gcd(m,n) is to be multiple of p and (or) 1.
→ So, no. of possible m such that gcd(m,n) is 1 will be
n - number of multiples of either p (or) q
= n - p2 - pq + p
= p2q - p2 - pq + p
= p(pq - p - q + 1)
= p(p - 1)(q - 1)
 Question 23
The number of elements in he power set P (S) of the set S = {(φ), 1, (2, 3)} is:
 A 2 B 4 C 8 D None of the above
Engineering-Mathematics       Set-Theory       Gate-1995
Question 23 Explanation:
S = {(φ), 1, (2, 3)}
P(S) = {φ, {{φ}}, {1}, {{2, 3}}, {{φ}, 1}, {1, {2, 3}}, {{φ}, 1, {2, 3}}}
In P(S) it contains 8 elements.
 Question 24
The number of subsets {1, 2, ... n} with odd cardinality is __________
 A 2n-1
Engineering-Mathematics       Set-Theory       Gate-1994
Question 24 Explanation:
Total no. of subsets with n elements is 2n.
And so, no. of subsets with odd cardinality is half of total no. of subsets = 2n /n = 2n-1
 Question 25
Let S be an infinite set and S1 ..., Sn be sets such that S1 ∪ S2 ∪ ... ∪ Sn = S. Then,
 A at least one of the set Si is a finite set B not more than one of the set Si can be finite C at least one of the sets Si is an infinite set D None of the above
Engineering-Mathematics       Set-Theory       Gate-1993
Question 25 Explanation:
Given sets are finite union of sets. One set must be infinite to make whole thing to be infinite.
 Question 26
Let A be a finite set of size n. The number of elements in the power set of A × A is:
 A 22n B 2n2 C (2n)2 D (22)n
Engineering-Mathematics       Set-Theory       Gate-1993
Question 26 Explanation:

 Question 27
If the longest chain in a partial order is of length n then the partial order can be written as a ______ of n antichains.
 A disjoint
Engineering-Mathematics       Set-Theory       Gate-1991
Question 27 Explanation:
Suppose the length of the longest chain in a partial order is n. Then the elements in the poset can be partitioned into a disjoint antichains.
There are 27 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com