## Set-Theory

Question 1 |

R: ∀a,b ∈ G, aRb if and only if ∃g ∈ G such that a = gbg

R: ∀a,b ∈ G, aRb if and only if a = b-1

Which of the above is/are equivalence relation/relations?

R _{2} only | |

R _{1} and R_{2} | |

Neither R _{1} and R_{2} | |

R _{1} only |

Consider Statement R

_{1}:

Reflexive:

aR

_{1}a

⇒ a = g

^{-1}ag

Left multiply both sides by g

⇒ ga = gg

^{-1}ag

Right multiply both sides by g

^{-1}

⇒ gag

^{-1}= gg

^{-1}agg

^{-1}

⇒ gag

^{-1}= a [∴ The relation is reflexive]

Symmetric:

If aR

_{1}b, then ∃g ∈ G such that gag

^{-1}= b then a = g

^{-1}bg, which is Correct.

⇒ So, given relation is symmetric.

Transitive:

The given relation is Transitive.

So, the given relation R

_{1}is equivalence.

R

_{2}:

The given relation is not reflexive.

So, which is not equivalence relation.

Such that a ≠ a

^{-1}.

So, only R

_{1}is true.

Question 2 |

Which of the above statements is/are TRUE?

Only II | |

Only I | |

Neither I nor II | |

Both I and II |

and given A = {(x, X), x∈X and X⊆U}

Possible sets for U = {Φ, {1}, {2}, {1, 2}}

if x=1 then no. of possible sets = 2

x=2 then no. of possible sets = 2

⇒ No. of possible sets for A = (no. of sets at x=1) + (no. of sets at x=2) = 2 + 2 = 4

Consider statement (i) & (ii) and put n=2

Statement (i) is true

Statement (i) and (ii) both are true.

Answer: (C)

Video Explanation

Question 3 |

Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is _________.

41 | |

42 | |

43 | |

44 |

__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 4 |

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 _________.

0 | |

1 | |

2 | |

3 |

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 5 |

*f:N*, deﬁned on the set of positive integers N

^{+}→ 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 __________.

2 | |

3 | |

4 | |

5 |

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 6 |

*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:

*R*is transitive

Which one of the following statements is

**TRUE**?

Both P and Q are true. | |

P is true and Q is false. | |

P is false and Q is true. | |

Both P and Q are false. |

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 7 |

*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.

U\S reacts with an odd number of compounds.

U\S reacts with an even number of compounds.

ALWAYS TRUE?

Only I | |

Only II | |

Only III | |

None |

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

(d

_{i}= 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 8 |

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 L^{3} = {(x,y,z): x, y, z ∈ L} be the set of all ordered triplets of the elements of L. Let p_{r} be the probability that an element (x,y,z) ∈ L^{3} chosen equiprobably satisfies x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z). Then

pr = 0 | |

pr = 1 | |

0 < pr ≤ 1/5 | |

1/5 < pr < 1 |

^{3}are 5×5×5 i.e., 125 n(s) = 125

Let A be the event that an element (x,y,z)∈ L

^{3}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 9 |

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?

Both {f} and {g} are functionally complete | |

Only {f} is functionally complete | |

Only {g} is functionally complete
| |

Neither {f} nor {g} is functionally complete |

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 10 |

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?

R is symmetric and reflexive but not transitive | |

R is reflexive but not symmetric and not transitive | |

R is transitive but not reflexive and not symmetric | |

R is symmetric but not reflexive and not transitive |

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 11 |

The cardinality of the power set of {0, 1, 2, … 10} is _________.

2046 | |

2047 | |

2048 | |

2049 |

^{11}i.e., 2048.

Question 12 |

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 TR be the set of all elements in T which are not in R. Which one of the following is true?

∀X ∈ U (|X| = |X'|) | |

∃X ∈ U ∃Y ∈ U (|X| = 5, |Y| = 5 and X ∩ Y = ∅) | |

∀X ∈ U ∀Y ∈ U (|X| = 2, |Y| = 3 and X \ Y = ∅) | |

∀X ∈ U ∀Y ∈ U (X \ Y = Y' \ X') |

(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 common. 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 13 |

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?

Both reflexive and symmetric | |

Reflexive but not symmetric | |

Not reflexive but symmetric | |

Neither reflexive nor symmetric |

∴(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 14 |

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?

Both S1 and S2 are true | |

S1 is true and S2 is false | |

S2 is true and S1 is false | |

Neither S1 nor S2 is true |

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 15 |

Let X and Y be finite sets and f: X→Y be a function. Which one of the following statements is TRUE?

For any subsets A and B of X, |f(A ∪ B)| = |f(A)|+|f(B)| | |

For any subsets A and B of X, f(A ∩ B) = f(A) ∩ f(B) | |

For any subsets A and B of X, |f(A ∩ B)| = min{ |f(A)|,f|(B)|} | |

For any subsets S and T of Y, f ^{ -1} (S ∩ T) = f^{ -1} (S) ∩ f^{ -1} (T) |

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 16 |

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 __________.

5 | |

6 | |

7 | |

8 |

So, 15 is divided by {1, 3, 5, 15}.

As minimum is 4 and total is 15, we eliminate 1,3,15.

Answer is 5.

Question 17 |

If V_{1} and V_{2} are 4-dimensional subspace of a 6-dimensional vector space V, then the smallest possible dimension of V_{1}∩V_{2} is ______.

2 | |

3 | |

4 | |

5 |

_{1}, V

_{2}are provided. Then the V

_{1}∩V

_{2}?

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

V

_{1}∩ V

_{2}= V

_{1}+ V

_{2}- V

_{1}∪ V

_{2}= 4 + 4 + (-6) = 2

Question 18 |

Consider the set of all functions f: {0,1, … ,2014} → {0,1, … ,2014} such that f(f(i)) = i, for all 0 ≤ i ≤ 2014. Consider the following statements:

- P. For each such function it must be the case that for every i, f(i) = i.

Q. For each such function it must be the case that for some i, f(i) = i.

R. Each such function must be onto.

Which one of the following is CORRECT?

P, Q and R are true | |

Only Q and R are true | |

Only P and Q are true | |

Only R is true |

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 19 |

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**?

In any planar embedding, the number of faces is at least n/2 + 2 | |

In any planar embedding, the number of faces is less than n/2 + 2 | |

There is a planar embedding in which the number of faces is less than n/2 + 2 | |

There is a planar embedding in which the number of faces is at most n/(δ+1) |

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 20 |

A binary operation ⊕ on a set of integers is defined as x ⊕ y = x^{2 }+ y^{2}. Which one of the following statements is **TRUE** about ⊕?

Commutative but not associative | |

Both commutative and associative | |

Associative but not commutative | |

Neither commutative nor associative |

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 = x

^{2}+ y

^{2}--------(1)

Replace x, y in (1)

y⊕x = y

^{2}+ x

^{2}which is same as (1), so this is cumulative

(x⊕y)⊕z = (x

^{2}+ y

^{2}) ⊕ z

= (x

^{2}+ y

^{2}) + z

^{2}

= x

^{2}+ y

^{2}+ z

^{2}+ 2x

^{2}y

^{2}----------(2)

x⊕(y ⊕ z) = x ⊕ (y

^{2}+ z

^{2})

= x

^{2}+ (y

^{2}+ z

^{2})

^{2}

= x

^{2}+ y

^{2}+ z

^{2}+ 2y

^{2z2 ----------- (3) (2) & (3) are not same so this is not associative. }

Question 21 |

A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is: Then R is:

Neither a Partial Order nor an Equivalence Relation | |

A Partial Order but not a Total Order | |

A Total Order | |

An Equivalence Relation |

i) Symmetric

ii) Reflexive

iii) Transitive

If a relation is partial order relation then it must be

i) Reflexive

ii) Anti-symmetric

iii) Transitive

If a relation is total order relation then it must be

i) Reflexive

ii) Symmetric

iii) Transitive

iv) Comparability

Given ordered pairs are (x,y)R(u,v) if (x

Here <, > are using while using these symbol between (x,y) and (y,v) then they are not satisfy the reflexive relation. If they uses (x<=u) and (y>=u) then reflexive relation can satisfies.

So, given relation cannot be a Equivalence. Total order relation or partial order relation.

Question 22 |

Suppose A = {a,b,c,d} and Π_{1} is the following partition of A

Π_{1} = {{a,b,c}{d}}

(a) List the ordered pairs of the equivalence relations induced by Π_{1}.

(b) Draw the graph of the above equivalence relation.

(c) Let Π_{2} = {{a},{b},{C},{d}}

Π_{3} = {{a,b,c,d}}

and Π_{4} = {{a,b},{c,d}}

Draw a Poset diagram of the poset,

({Π_{1},Π_{2},Π_{3},Π_{4}}, refines⟩

Theory Explanation. |

Question 23 |

The number of elements in he power set P (S) of the set S = {(φ), 1, (2, 3)} is:

2 | |

4 | |

8 | |

None of the above |

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 __________.

2 ^{n-1} |

^{n}.

And so, no. of subsets with odd cardinality is half of total no. of subsets = 2

^{n}/n = 2

^{n-1}

Question 25 |

Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ______.

7 |

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 26 |

Let S be an infinite set and S_{1} ..., S_{n} be sets such that S_{1} ∪ S_{2} ∪ ... ∪ S_{n} = S. Then,

at least one of the set S _{i} is a finite set | |

not more than one of the set S _{i} can be finite | |

at least one of the sets S _{i} is an infinite set | |

not more than one of the sets S _{i} can be infinite | |

None of the above |

Question 27 |

Let A be a finite set of size n. The number of elements in the power set of A × A is:

2 ^{2n} | |

2 ^{n2} | |

(2 ^{n})^{2} | |

(2 ^{2})^{n} | |

None of the above |

^{2}

A = {1,2}

|A| = {∅, {1}, {2}, {1,2}}

Cardinality of power set of A = 2

^{n2}

A × A = {1,2} × {1,2}

= {(1,1), (1,2), (2,1), (2,2)}

Cardinality of A × A = n

^{2}

Cardinality of power set of A × A = 2

^{n2}

Question 28 |

If the longest chain in a partial order is of length n then the partial order can be written as a ______ of n antichains.

disjoint |

Question 29 |

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?

g is onto ⇒ h is onto | |

h is onto ⇒ f is onto | |

h is onto ⇒ g is onto | |

h is onto ⇒ f and g are onto |

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.