Set Theory and Algebra Questions and Answers | Computer Science Quiz

Explanation:
A relation is said to be equivalence relation is

• Reflexive
• Symmetric, and
• Transitive

The union of two reflexive relations and two symmetric relations are reflexive and symmetric respectively. However, the union of two transitive relations need not be transitive. Therefore, the union of two equivalence relations need not be an equivalence relation.
Example:
Let R₁ and R₂ on set A = {1, 2, 3}
R₁ = {(1, 1), (2, 2,), (3, 3) (1, 2), (2, 1)} is an equivalence relation
R₂ = {(1, 1),(2, 2), (3, 3), (2, 3), (3, 2)} is an equivalence relation
R₁ ∪ R₂ = {(1, 1), (2, 2), (3, 3,), (1, 2), (2, 1), (2, 3), (3,2)} is not an equivalence relation, because (1, 2) & (2, 3) needs (1, 3) element to be in transitive relation.

Explanation: (a) Set A contains n elements. Every subset of A × A is a binary relation on set A.
∴ Number of binary relations on a set A with n elements 2^n²
(b) Number of one-to-one functions from a set A with m-elements to a set B with n – elements are nP_m So the number of one-to-one functions from a set A with n-elements to itself is nP_n = n!.

Explanation: The complement of an element x is x’ iff LUB of x and x’ is 1 (greatest element) and GLB of x and x’ is 0 (least element).
∴ The complement of the element ‘a’ in the lattice = {b, c, d, e}.

Explanation:
The relation has (1, 2) (2, 3) then add (1, 3) to the relation. Since relation have (2, 3) (3,4) then add (2, 4) to relation.
So the resultant relation is = {(1, 2), (2, 3), (3, 4), (5, 4), (1, 3), (2, 4)} Now the resultant relation have (1,2) (2, 4) then add (1, 4) to the relation
∴ {(1,2), (2,3), (3,4), (5,4), (1,3), (2,4), (1,4)}
So the transitive closure of the relation is = {(1,2), (2,3), (3,4), (5,4), (1,3), (2,4), (1,4)}

Answer: (c) At least one of sets S; is infinite
Explanation:
S = S₁ ∪ S₂ ∪ S₃ ∪ … ∪ S_n.
For S to be an infinite set, at least one of sets S_i must be infinite, since if all S_i were finite, then S will also be finite.

Answer: (b) 2^n²
Explanation:
Number of elements in A × A = n²
∴ A number of elements in the power set of A × A = 2^n².

Answer: (c) (goh)² = g² o h² for every g, h ∈ G.
Explanation:
(goh)² = (goh)o(goh)
Since group is abelian so it is commutative as well as associative.
= go (hog)h
= go (goh) oh
= (gog) o(hh) = g² o h²
So (goh)² = g² o h² for every g, h∈ G

Answer: (d) None of the above
Explanation:
A relation that is symmetric and transitive, need not be reflexive relation.

• R = { }; on the set A = {a, b}. The relation R is symmetric and transitive but not reflexive.
• R = {(a, a), (b, b)}; on the set A = {a, b}. The relation R is symmetric, transitive and also reflexive.

∴ A relation is transitive and symmetric relation but need not be reflexive relation.

Answer: (c) 8
Explanation:
If a set has n elements then its powers set has 2ⁿ elements.
Given set S = {(Φ), 1, (2, 3)}
Number of elements in S = 3
∴ The number of elements in powerset (S)
= 2³ = 8.

Answer: (d) <A, *> is a group but not an abelian group
Explanation:

• Closure Property: Multiplication of two non-singular matrices is also a non-singular matrix. Matrix multiplication over non-singular matrices follows closure properties.
• Associative Property: Multi-plication over any set of matrices is associative. (AB)C = A(BC) Where A, B, and C are non-singular matrices
• Identity Element: Identity matrix I am the identity element for matrix multiplication over matrices and I is non-singular.
• Inverse Element: For every non-singular matrix its inverse exists. So, for non¬singular matrices, inverse elements exist.
• Commutative: Matrix multiplication is not commutative
  AB ≠ BA
  Where A, B are non-singular matrices. Matrices multiplication is not commutative. So <A, *> is a group but not an abelian group

Answer: (a) A ∪ B
Explanation:
(A – B) ∪ (B – A) ∪ (A ∩ B)
Representing the above set using the Venn diagram as follows.

∴ By Venn diagram,
(A – B) ∪ (B – A) ∪ (A ∩ B) = A ∪ B

Answer: (b) 4
Explanation:
x = {2, 3, 6, 12, 24}
The Hasse diagram of (x, ≤) is

Therefore, the number of edges in the Hasse diagram = 4

Answer: (a) |X| = 1, |Y| =97
Explanation:
X and Y are set. The cardinalities of X and Y are |X| and |Y| respectively.
The number of functions from X to Y = (|Y|)^|X| Given that number of functions from X to Y = 97
∴ 97 = (|Y|)^|X|
So above implies that |X| = 1 and |Y| = 97

Answer: (c) The set of rational numbers form an abelian group under multiplication
Explanation:
0 is also a rational number and for 0, the inverse doesn’t exist under multiplication. Therefore, the set of rational numbers doesn’t form an abelian group under multiplication.

Answer: (c) f^-1(x,y) = \(\left(\frac{x+y}{2}, \frac{x-y}{2}\right)\)
Explanation:
f(x, y) = ((x + y), (x — y))
So let z₁ = x+ y ……(i)
z₂=x—y …(ii)
f(x, y) = (z₁, z₂)
So f^-1(z₁, z₂) = (x, y)
Adding (i) and (ii)
z₁ + z₂ = 2x
X = \(\frac{\mathrm{z}_{1}+\mathrm{z}_{2}}{2}\)
Subtracting (i) and (ii)
z₁ – z₂ = 2y
y = \(\mathrm{y}=\frac{\mathrm{z}_{1}-\mathrm{z}_{2}}{2}\)
So the inverse function of F is given by
f^-1(z₁ , z₂) = (x,y) = \(\left(\frac{\mathrm{z}_{1}+\mathrm{z}_{2}}{2}, \frac{\mathrm{z}_{1}-\mathrm{z}_{2}}{2}\right)\)
Since z₁ and z₂ are just dummy variables so replacing z1 and z₂ by x and y respectively
f^-1(x,y) = \(\left(\frac{x+y}{2}, \frac{x-y}{2}\right)\)

Alternate Method:

Given f(x, y) = ((x + y), (x — y))
Take some random ordered pair say (2, 3) f(2, 3) ((2 + 3), (2 — 3)) = (5, —1)
Now the correct inverse must map (5. —1) back to(2,3).
Trying the options one by one we find that only option (e) maps (5, -1) to (2, 3).

Answer: (b) R is symmetric and not transitive
Explanation:
(i) Reflexive
A ∩ A = A ≠ Φ
So; (A, A) doesn’t belong to relation R.
∴ Relation R is not reflexive.

(ii) Symmetric
If A ∩ B = Φ then B ∩ A Φ is also true
∴ relation R is a symmetric relation.

(iii) Transitive
If A ∩ B = Φ and B ∩ C = Φ. it need not be true that A ∩ C = Φ.
For example:
A = {1, 2}, B = {3, 4}, C = {1, 5, 6}
A ∩ B = Φ and B ∩ C = Φ but
A ∩ C = {1} ≠ Ø
∴ Relation R is not transitive relation.

Answer: (c) The set of all strings over a finite alphabet Σ forms a group under concatenation.
Explanation:
In option (c). the set of all strings over a finite alphabet Σ doesn’t form a group under concatenation because the inverse of a string doesn’t exist with respect to concatenation.

Answer: (a) 15
Explanation:
Corresponding to every partition of the set 1, 2, 3, 4, there exists a unique equivalence relation. So we count every type of unordered partition of the set of 4 elements into one block, two-block, three-block, and four block partitions. as shown below:

Total 1+7+6+1=15
So the number of equivalence relations on the set {1, 2, 3. 4} is 15.

Answer: (b) n²
Explanation:
A is a finite set with n elements. The largest equivalence relation of A is the cross. product A × A and the number of elements in the cross product A × A is n².

Answer: (c) assertion (ii) is true but assertion (i) is not true
Explanation:
A relation is said to be an equivalence relation if the relation is
(i) Reflexive
(ii) Symmetric
(iii) Transitive
Reflexive and symmetric properties are both closed under ∪ & ∩.
Transitive property is closed under n but not u. So equivalence relations are closed under ∩ hut not ∪.
Therefore R₁ ∩ R₂ is an equivalence relation but R₁ ∪ R₂ is not necessarily an equivalence relation.

Answer: (c) n^m
Explanation:
The number of functions from an m element set to an n clement set is n^m.

Answer: (b) Neither reflexive nor irreflexive but transitive
Explanation:
The relation R doesn’t contain (4, 4), so R is not reflexive relation. Since relation R contains (1, 1), (2, 2), and (3, 3). Therefore, relation R is also not irreflexive.
That R is transitive, can be checked by systematically checking for all (a. b) and (b, c) in R, whether (a, e) also exists in R. So option (b) is correct.

Answer: Given partition of A is
π₁ = {(a, b, c), (d)}
(a) The ordered pairs of the equivalence relations induced by π₁ is
R = (a, b, c) × (a, b, c) ∪ (d) × (d)
R = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c), (d, d)}
(b) The digraph of the above equivalence relation is as follows:

Answer:
Explanation:
Given a ≠ b ⇒ a * b ≠ b * a The contrapositive version of this is a*b = b*a ⇒ a = b
(a) Now since (A, *) is given to be a semigroup, * is associative
i. e. a * (a * a) = (a * a) * a
Hence a = a * a
(b) (a * b * a) * a = a * b * (a * a) = a * b * a
⇒ a*(a*b*a) = (a*a)*b*a = a * b * a
as a * a = a [proved in part a]
So (a * b * a) * a = a * (a * b * a)
Hence a * b * a = a
(c) (a * b * c) * (a * c) = a * b * (c * a * c) = a * b * c
(a * c) * (a * b * c) = (a * c * a) * b * c = a * b * c
So (a *b * c) * (a * c) = (a * c) * (a * b * c)
Hence a*b*c = a*c

Answer: (c) 2ⁿ²
Explanation:
The maximum number of elements in a binary relation on a set A with n elements = Number of elements in A × A = n²
Each element has two choices, either to appear on a binary relation or doesn’t appear on a binary relation.
∴ The number of binary relations = 2^n².

Explanation:
(a) According to Mr. X if xRy is in relation then yRx is also in relation because of symmetricity. Now because R is transitive, xRy and yRx implies xRx.
The flaw in Mr. X claim is that if xRy is present then only it implies yRx and hence xRx. However, if xRy is not present then according to symmetricity yRx is also not present. So xRx need not be present in relation. So it need not be reflexive.
For Example, Empty relation Φ is both symmetric and transitive. However, Φ is not reflexive relation.
(b) Examples of relations that are symmetric and transitive but not reflexive.
(i) Empty relation Φ is symmetric and transitive but not reflexive.
(ii) Relation R = {(a, b), (b, a), (a, a), (b, b)} over A = {a, b, c} is both symmetric and transitive but not reflexive.

Answer: (c) R is an equivalence relation having 2 equivalence classes
Explanation:
A relation R is defined as xRy iff (x + y) is even over a set of integers.
(x + y) is even iff
(i) both x and y are even
(ii) both x and y are odd
Therefore, relation R is equivalence relation because relation is
(i) Reflexive
x + x = 2x = even
So (x, x) belongs to R. So relation is reflexive.
(ii) Symmetric
If x + y = even then y + x is also even So relation is symmetric.
(iii) Transitive
If x + y = even and y + z = even
Then x + y + y + z = even + even
⇒ x + z + 2y = even
⇒ x + z = even – 2y
⇒ x + z = even
∴ Relation R is transitive.
So relation R is an equivalence relation which divides the set of integer into two equivalence classes: One is of all even and other is of odd integer.

Equivalence classes of R are
[0] = { ….. -6, -4, -2, 0, 2, 4, 6, …}
[1] = { ….. -7, -5, -3, -1, 1, 3, 5, 7, …}

Answer: (b) P(S) ∩ P(P(S)) = {Ø}
Explanation:
Φ always present in any powerset of a set and Φ is the only common element between P(S) and P(P(S))
∴ P(S) ∩ P(P(S)) = {Φ}

Answer: (b) R₁ and R₃ are equivalence relations, R₂ and R₄ are not
Explanation:
(I) Relation R₁(a, b) iff (a + b) is even over the set of integers.
(i) a + a = 2a which is even So (a, a) belongs to R₁
∴ R₁ is reflexive relation

(ii) If (a + b) is even, then (b + a) is also even
∴ R₁ is symmetric relation

(iii) If (a + b) and (b + c) are even then a + c = (a + b) + (b + c) – 2b = even + even — even = even
∴ R₁ is transitive relation.
Since R₁ is reflexive, symmetric and transitive so R₁ is an equivalence relation.

(II) RR₂(a, b) iff (a +b) is odd over set of integers,
(i) a + a = 2a which is not odd So (a, a) doesn’t belong to R₂
∴ R₂ is not reflexive relation Since R₂ is not reflexive, it is not an equivalence relation.

(III) R₃(a, b) iff a . b > 0 over set of non-zero relational numbers.
(i) a. a. > 0 for every non-zero rational number.
∴ R₃ is reflexive relation.
(ii) If a.b > 0 then b.a > 0
∴ R₃ is symmetric relation.
(iii) a.b > 0 and b.c > 0 ⇒ All a,b,c are positive or all a,b,c are negative.
So a.c > 0
∴ R₃ is transitive relation.
So R₃ is an equivalence relation.

(IV) R₄ (a, b) iff |a – b| ≤ 2 over the set of natural number
(i) |a – a| ≤ 2
0 ≤ 2
∴ R₄ is reflexive relation.

(ii) If |a — b| ≤ 2 then also |b – a| ≤ 2 ∴ R₄ is symmetric relation
(iii) If |a — b| ≤ 2 and |b — c| ≤ 2 then it is not necessary that |a — c| ≤ 2
Ex. |3 – 5| ≤ 2 and |5 — 7| ≤ 2 but |3 —7| ≤ 2
∴ R₄ is not transitive.
Since R₄ is reflexive and symmetric not transitive, so R₄ is not an equivalence relation.

Answer: (c) Both S₁ and S₂ are correct
Explanation:
S₁: Let A = set of integers
B = set of odd integers
C = set of even integers
A ∩ (B ∩ C) = Φ and Φ is finite set.
Therefore, S₁ is true.
S₂: Let two irrational number x and y are respectively \((1+\sqrt{2})\) and \((1-\sqrt{2})\).
So x + y= 1 + \(\sqrt{2}\) +1 – \(\sqrt{2}\)
= 2 which is rational number Therefore, S₂ is true. Since both S₁ and S₂ are true, option (c) is true.

Answer: (a) Only S₁ is correct
Explanation:
Given a function f: x → y and subsets E and F of A then we have f(E ∪ F) = f(E) ∪ f(F) and f(E ∩ F) ⊆ f(E) ∩ f(F)
Therefore S₁ is correct and S₂ is false.

Answer: (d) Transitive and symmetric
Explanation:
The empty relation on any set is always transitive and symmetric but not reflexive.

Answer: (a) does not form a group
Explanation:
Σ = {0, 1}
Σ* = {0,1}*
= {ε, 0, 1, 01, 10, 11, 000, …}
So (Σ*, •) is an algebraic system, where • (concatenation) is a binary operation.
So (Σ*, •) is a group if and only if the following conditions are satisfied.
1. • (Concatenation) is a closed operation.
2. • is an associative operation.
3. There is an identity.
4. Every element of Σ* has an inverse

Condition 1: * is a closed operation because for any ω₁,∈ Σ* and ω₂ ∈ Σ*, ω₁ . ω₂∈ Σ*
Condition 2: For any string x, y, z ∈ Σ*, x . (y . z) = (x . y) . z
So it is associative for example let
x = 01, y = 11, z = 00 then L.H.S. = x . (y.z)
= 01(1100) = 01(1100) = 011100 R.H.S. = (x.y).z
= (0111)00 = (0111)00 = 011100
Condition 3: The Identity is e or empty string because for any string ω ∈ Σ*,
εω = ωε = ω
Now, since ε ∈ Σ*, identity exists.
Condition 4: There is no inverse exist for Σ* because any string ω ∈ Σ*, there is no string ω^-1 such that ω . ω^-1 = ε = ω^-1 ω.
So Σ* with the concatenation operator for strings doesn’t form a group but it does form a monoid.

Answer: (d) P(x) = False for all x ∈ S such that a ≤ x and b ≤ x
Explanation:
If a ≤ x, since p(x) ⇒ p(y) whenever x ≤ y ∴ p(a) ⇒ p(x)
Now since p(a) = True, p(x) = cannot be false. ∴ (d) cannot be true.

Answer: (c) 2
Explanation:
The possible solution pairs are (a, a), (a, b), (a, e), (b, a), (b, b), (b, c), (c, a,), (c, b) and (e, c). Substitute them one by one in both equations and see which of them satisfies both the equations.
The given equations are:
(a × x)+(a × y) = C ……(i)
(b × x)+(c × y) = C ……(ii)
Substitute first (x. y) = (a, a)
LHS of equation (i) becomes (a × a) + (a × a) = a +a = b
Now RHS of equation (i) = e
Therefore LHS ≠ RHS. This means that (a, a) is not a solution pair. Similarly, try each of the remaining seven possible solution pairs. It will be found that only two pairs (b, c) and (c, b) will satisfy both equations (i) & (ii) simultaneously. Therefore choice (c) is correct.

Answer: (b) {(x, y) | y ≥ x and x,y ∈ {0, 1, 2, …..}}
Explanation:
S = {(x, y) | y = x + 1, and x, y ∈ (0, 1, 2, …}} = {(0, 1), (1, 2), (2, 3), (3, 4), …}
Now let T₁ be the reflexive closure of S.
T₁ = {(0, 0), (1, 1), (2, 2), (3, 3)…} ∪ {(0, 1), (1, 2), (2, 3), (3, 4)…}
= {(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4) …}

Let T₂ be the transitive closure of S.
(0, 1), (1, 2) ∈ S ⇒ (0, 2) ∈ T₂
(0, 2), (2, 3) ∈ S ⇒ (0, 3) ∈ T₂
(0, 3), (3, 4) ∈ S ⇒ (0, 4) ∈ T₂
and so on…..
Also (1, 2), (2, 3) ∈ S ⇒ (1, 3) ∈ T₂
(1, 3), (3, 4) ∈ S ⇒ (1, 4) ∈ T₂
(1, 4), (4, 5) ∈ S ⇒ (1, 5) ∈ T₂
and so on….
∴ T₂ = {(0, 1), (0, 2), (0, 3), …, (1, 2), (1, 3), (1, 4), …}

Now the reflexive, transitive closure of S will be T₃ = T₁ ∪ T₂ = {(0, 0),(0, 1), (0, 2),…, (1,1), (1, 2), (1, 3),…,(2, 2) (2, 3), (2, 4),…}.
Option (b) is correct.

Answer: (c) power(2, (n² + n)/2)
Explanation:
In a symmetric matrix, the lower triangle must be the mirror image of the upper triangle using the diagonal as a mirror. Diagonal elements may be anything. Therefore, when we are counting symmetric matrices we count how many ways are there to fill the upper triangle and diagonal elements. Since the first row has n elements, second (n -1) elements, third row (n – 2) elements, and so on up to the last row, one element.
Total number of elements in diagonal + upper triangle
= n + (n – 1) + (n – 2) + … + 1 = n(n + 1)/2
Now, each one of these elements can be either 0 or 1. So total number of ways we can fill these elements is
\(2 \frac{n(n+1)}{2}\) = power (2, (n² + n)/2)
Since there is no choice for lower triangle elements the answer is power (2, (n2 + n)/2) which is choice (c).

Answer: (c) 25
Explanation:

According to inclusion – exclusion formula:
| PL ∪ DS ∪ CO | = | PL | + | DS | + | CO | – | PL ∩ DS|- |PL – CO|-|DS ∩ CO| + |PL ∩ DS ∩ CO| PL = students who have taken programming. DS = Students who have taken Data structures. CO = Students who have taken Computer Organization.
So, the number of students who have taken atleast 1 of the 3 courses is given by:
= 125 + 85 + 65- 50- 35- 30 + 15 = 175
Therefore, the number of students who have not taken any of the 3 courses is = Total students – students taking at least 1 course = 200 – 175 = 25

Answer: (c) R₁R₂={1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}
Explanation:
R₁ = {(An element x in A, An element y in B) if x + y divisible by 3}
R₁ = {(1, 2), (1, 8), (3, 6), (5, 4), (7, 2), (7, 8)}
R₂ = {(An element x in B, An element y in C) if x + y is even but not divisible by 3}
R₂ = {(2, 2), (4, 4), (6, 2), (6, 4), (8, 2)}
So, R₁ o R₂ = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}.

Answer: (d) c e a b
Explanation:
Step 1:
By looking at the row for e, we see that it is a copy of the column headers. So e must be the identity element. Since right identity and left identity elements must both be the same. The column corresponding to e must be a copy of the row headers. We can now say that the operation table is:

Step 2:
From the table above we see that a*c = e
∴ c*a must also be = e (if a is the inverse of c, then c is the inverse of a)
Now the operation table looks like

Step 3:
The blank in the second column must he c (since in a Cayley table, every row and every column is a unique permutation of the row and column headers).
Now the operation table looks like

Step 4:
Now the blanks in the third row can be filled as a, e or e, a. Let us try each one in turn. If we fill a, e in the third row the operation table will look like

Now the blank in the fourth row and third column must be filled by e. However, this is not possible since e is already entered in the fourth row and second column. Therefore filling a, e in third-row blanks is wrong. So let us try filling the third-row blanks with e, a Now the operation table looks like

Now the blanks in the fourth row have to be filled with a, b The final operation table looks like

which is consistent with all the rules of a Cayley Table. The last row of this table is c, e, a, b Therefore the correct answer is (d).

Answer: (A) {1}
Explanation:
The hasse diagram of the given post is:

In a complete lattice L, every nonempty subset of L has both LUB and GLB. Now it is necessary to add {1} since GLB of {1,2} and {1, 3, 5} is {1}. The hasse diagram now becomes:

Now the above hasse diagram represents a complete lattice since every nonempty subset has both LUB and GLB. Therefore adding {1} is not only necessary but it is also sufficient to make the given lattice a complete lattice. Therefore the correct choice is (a).

Answer: (a) X = Y
Explanation:
X = (A-B) – C
= (A ∩ B’) – C
= (A ∩ B’) ∩ C’
= AB’C’
Y= (A-C)-(B-C)
= (A ∩ C) – (B ∩ C’)
= (AC’) – (BC’)
= (AC’) ∩ (BC’)’
= (AC’) ∩ (B’ + C)
= (AC’) . (B’ + C)
= AC’B’ + AC’C
= AC’B’ (Since C’C = 0)
= AB’C’ (commutative property)
∴ X =Y

Answer:(b) a lattice but not a distributive lattice
Explanation:

The poset [{a, b, c, d, e}, ≤ ] is a lattice (since every pair of elements has LUB and GLB) but it is not a distributive lattice. Because distributive lattice satisfies the following conditions. For any x, y, z,
x ∧ (y v z) — (x ∧ y) v (x ∧ z)
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
Where ∧ and ∨ are meet and join operations but for given poset [{a, b, c, d, e} ≤]
b ∧ (c ∨ d) = b ∧ a = b
(b ∧ c) ∨ (b ∧ d) = e ∨ e = e
So it is not distributive. (Also, element b has 2 complements c and d, which is not possible in a distributive lattice, since, in a distributive lattice, complement if it exists, is always unique).

Answer: (c) 4 and 13
Explanation:
The set S = {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15.
The identity element for this group is e = 1 since,
∀x ∈ S, 1 . x mod 15 = x
Now let the inverse of 4 be 4^-1.
Now (4 . 4^-1) mod 15 = e = 1
Since (4 . 4) mod 15=1
∴ 4^-1 = 4 (This inverse is unique)
Similarly let the inverse of 7 be 7^-1
(7 . 7^-1) mod 15=1
putting each element of set as 7^-1 by trial and error we get
(7 . 13) mod 15 = 91 mod 15=1
∴ 7^-1 = 13
So, 4^-1 and 7^-1 are respectively 4 and 13. The correct choice is (c).

Answer: (c) R ∩ S is an equivalence relation
Explanation:
R ∩ S is an equivalence relation as can be seen from proof given below.
Let ∀x ∈ A (x, x) ∈ R and (x, x) ∈ S (since R and S are reflexive)
∴ (x, x) ∈ R n S also ∴ R ∩ S is reflexive.
Now, (x, y) ∈ R ∩ S
⇒ (x, y) ∈ R and (x, y) ∈ S
⇒ (y, x) ∈ R and (y, x) ∈ S
(Since R and S are symmetric)
⇒ (y,x) ∈ R ∩ S
∴ (x, y) ∈ R ∩ S
⇒ (y, x) ∈ R ∩ S
R ∩ S is therefore symmetric Now consider
(x, y) and (y, z) ∈ R ∩ S ⇒ (x, y) and (y, z) ∈ R and (x, y) and (y, z) ∈ S ⇒ (x, z) ∈ R and (x, z) ∈ S
(Since R and S are transitive)
⇒ (x, z) ∈ R ∩ S
∴ R ∩ S is transitive also. Since R ∩ S is reflexive, symmetric, and transitive.
∴ R ∩ S is an equivalence relation.
Note: A similar argument cannot be made from R ∪ S.

Answer: (b) f should be onto but g need not be onto
Explanation:
Consider the arrow diagram shown below:

h(a) = f . g(a) = α
h(b) = f . g(b) = β
Here f is onto but g is not onto, yet h is onto. As can be seen from the diagram if f is not onto, h cannot be onto.
∴ f should be onto, but g need not be onto.
∴ The answer is (b).

Answer: (a) a group
Explanation:
(i) The set H is closed since the multiplication of upper triangular matrices will result only in the upper triangular matrix.
(ii) Matrix multiplication is associative, i.e.
A * (B * C) = (A * B) * C.
(iii) Identity element is

and this belongs to H as I is an upper triangular as well as a lower triangular matrix.

(iv) If A ∈ H, then | A | = abc. Since it is given that abc ≠ 0, this means that |A | ≠ 0 i.e. every matrix belonging to H is non-singular and has a unique inverse.
∴ the set H along with matrix multiplication is a group.

Answer: (c) h is onto ⇒ g is onto
Explanation:
Given, h = g(f(x)) = g.f
Consider the following arrow diagram:

From the above diagram it is clear that g is not onto ⇒ h = g.f is also not onto, since the co-domain of g is the same as the co-domain of g.f. The contrapositive version of the above implication is h is onto ⇒ g is onto which also has to be true since direct = contrapositive. So option (c) is true.

Answer: (b) n+1
Explanation:
The way C is defined in the question contains only comparable subsets of A. i.e. the set C is the set of all comparable subsets of set A. Such a set is called a chain. Consider an example with set A = {1, 2} Subsets are Φ, {1}, {2} and {1, 2} Maximum cardinality of collection of distinct subsets is {Φ, {1} and {1, 2}} i.e. 3. So with n elements, the maximum cardinality is n + 1.

Answer: (d) None of these
Explanation:
I. f(x) = x + y – 3
x + a – 3 = x = a + x – 3
so a = 3
Now 3 is unique, and 3 ∈ N So I has identity.
II: f(x) = max(x, y)
max(x, a) = x = max(a, x)
In N, the only value of a which will satisfy the above equation is a = 1.
Since 3 is unique, and 3 ∈ N So II has an identity.

III. f(x) = x^y
x^a = x = a^x
Now x^a = x ⇒ a = 1, but x= a^x has no solution for a in the set N.
So III has no identity.
So only I and II have an identity.

Answer: (d) 2^xyz
Explanation:
Given | X | = x, | Y | = y and | Z | = z W = X × Y
So | W| = xy
| E | = 2|W| =2^xy
So the number of functions for Z to E = | E | ^|z|
= (2^xy)^z = 2xyz

Answer: (c) 3 does not have an inverse
Explanation:
Let A = {1, 2, 3, 5, 7, 8, 9}
Construct the table for any x, y ∈ A such that x * y = (x.y) mod 10

We know that 0 ∉ A. So it is not closed. Therefore, (a) is true.
The identity element = 1
∴ (2 . 2^-1) mod 10 = 1
From the table, we see that 2^-1does not exist. Since, (3 . 7) mod 10 = 1
∴ 7 is the inverse of 3 and 7 ∈ A.
(c) is false.
(d) is true since 8 does not have an inverse.

Answer: (a) Neither a Partial Order nor an Equivalence Relation
Explanation:
(x, y) R (u, v) iff x < u and y > v
(x, x) (x, x) since x / x and x / x
So R is not reflexive,
∴ R is neither a partial order, nor an equivalence relation.

Answer: (c) X = Y
Explanation:
Consider the following Venn diagram for X = (E ∩ F) – (F ∩ G)

Y = (E -(E ∩ G)) – (F – F)

So, X = Y
or alternatively the solution can be obtained from boolean algebra as follows:
X = (E ∩ F) – (F ∩ G)
= EF – FG
= EF ∩ (FG)’
= EF . (F’ + G’)
= EFF’ + EFG’
= EFG’
Similarly, Y = (E -(E ∩ G)) – (E – F)
= (E – EG) – (E . F’)
= E . (EG)’ – EF’
= E . (E’ + G’) – EF’
= EG’ – EF’
= EG’ . (EF’)’
= EG’ . (E’ + F)
= EE’ G’ + EFG’
= EFG’
Therefore X = Y

Answer: (b) 3n
Explanation:
The problem can be solved by considering the cases m = 4 and m = 5 etc.
Let, m = 4
S = {1, 2, 3, 4}
n = number of 3 element subsets
= ⁴C₃ = ⁴C₁ = 4
n = 4
The 4 subsets are {1, 2, 3}, {1, 2, 4}, {1, 3, 4} and {2, 3, 4}
f(1) = number of subsets having 1 as an element = 3
f(2) = number of subsets having 2 as an element = 3
f(3) = 3 and f(4) = 3
∴ \(\sum_{i=1}^{4} f(i)\) = 3 + 3 + 3 + 3=12

Both choice (a) and choice (b) are matching the answer since
3m = 3n = 12
Now let us try m = 5
S = {1, 2, 3, 4, 5}
n = number of 3 element subsets = ⁵C₃ = 10
∴ n = 10
The 10 subsets are {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}
f(1) = f(2) = f(3) = f(4) = f(5) = 6
\(\sum_{i=1}^{5} f(i)\) = 6 + 6 + 6 + 6 + 6 = 30

Clearly 3m = 3 × 5 = 15{is not matching Σf(i)} But
3n = 3 × 10 = 30 {is matching Σf(i) = 30}
∴ 3 n is the only correct answer.
The correct choice is (b).
The problem can also be solved in a more general way as follows:

\(\sum_{i=1}^{m} f(i)\) = f(1) + f(2) + ……+ f(m)
Since, f(1) = f(2) =…….= f(m) = ^(m-1)C₂
= \(\frac{\mathrm{m} \times(\mathrm{m}-1) \times(\mathrm{m}-2)}{2}\)
= \(\frac{3 \times \mathrm{m} \times(\mathrm{m}-1) \times(\mathrm{m}-2)}{1 \times 2 \times 3}\)
= 3 × ^mC₃
Since n = Number of there elements subsets of a set of m elements = ^mC₃
Therefore, \(\sum_{i=1}^{m} f(i)\) = 3 × ^mC₃ = 3n

Answer: (b) II only
Explanation:
P △ Q = PQ’ + P’Q
where △ is symmetric difference between P and Q.
I. LHS = P △ Q ∩ R = P△(QR) = P(QR)’ + P'(QR) = P(Q’ + R’) + P’QR
RHS = (P △ Q) ∩ (P △ R) = (PQ’ + P’Q) (PR’ + P’R) = PQ’R’ + P’QR
LHS ≠ RHS So statement I is false.

II. LHS = P ∩ Q △ R = P(QR’ + Q’R)
= PQR’ + PQ’R
RHS = (P ∩ Q) △ (P ∩ R) = PQ △ PR = PQ(PR)’ + (PQ)’ PR = PQ(P’ + R’) + (P’+Q’)PR = PQR’ + PQ’R
LHS = RHS
So statement II is true.

Answer: (b) 33
Explanation:
We know that, number of elements divisible by number ‘x’ in set of integer (from 1 to X) = \(\frac{X}{x}\)
So, according to inclusion exclusion formula:
n(2 or 3 or 5) = n(2) + n(3) + n(5) – n(2,3) – n(2,5) – n(3,5) – n (2,3,5))
No’s divisible by 2 in X = \(\left[\frac{123}{2}\right\rfloor\) = 61
No’s divisible by 3 in X = \(\left[\frac{123}{3}\right\rfloor\) = 41
No’s divisible by 5 in X = \(\left[\frac{123}{5}\right\rfloor\) = 24
No’s divisible by 2 and 3 = \(\left.\mid \frac{123}{2 \times 3}\right\rfloor\) = \(\left[\frac{123}{6}\right\rfloor\) = 20
No’s divisible by 3 and 5 = \(\left.\mid \frac{123}{3 \times 5}\right\rfloor\) = \(\left[\frac{123}{15}\right\rfloor\) = 8
No’s divisible by 2 and 5 = \(\)
No’s divisible by 2 and 3 and 5
The problem can be solved by considering the cases m = 4 and m = 5 etc.
= \(\left[\frac{123}{2 \times 3 \times 5}\right\rfloor\) = \(\left[\frac{123}{30}\right\rfloor\) = 4
So, n(2 or 3 or 5) = 61 + 41 +24 — 20 — 8-12 + 4 = 90
n(2 or 3 or 5) = Total number – n(2 or 3 or 5) = 123-90 = 33

Answer: (b) n² and n
Explanation:
Let S be a set of n elements say {1, 2, 3,…, n}. Now the smallest equivalence relation on S must contain all the reflexive elements {(1, 1), (2, 2), (3, 3),…, (n, n)} and its cardinality is therefore n. The largest equivalence relation on S is S × S, which has a cardinality of n × n = n².
∴ The largest and smallest equivalence relations on S have cardinalities of n² and n respectively. The correct choice is (b).

Answer: (c)
Explanation:
A partition P₁ is called a refinement of the partition P₂ if every set in P₁, is a subset of one of the sets in P₂.
π₄ is a refinement of π₂,π_3, and π₁
π₂ and n₃ are refinements of π₁
π₂ and π₃ are not comparable since neither is a refinement of the other.
So the poset diagram for (S’, <) would

Which is choice (c).

Answer: (d) (iii) and (iv)
Explanation:
In this problem
a % b means the mod function (i.e. residue when a is divided by b).
a/b means integer division (i.e. quotient when a is divided by b)
(i) (101,22):
101% 10 ≤ 22% 10 ⇒ 1 ≤ 2 which is true. (101/10, 22/10) = (10, 2) ∈ P need to check IS (10, 2) ∈ P?
10% 10 ≤ 2% 10 ⇒ 0 ≤ 2 which is True.
Then (10/10, 2/10) = (1, 0) fails since 1 < 0.
∴ (101, 22) ∉ P.

(ii) (22, 101)
22% 10 ≤ 101% 10 ⇒ 2 ≤ 1 is False.
∴ (22, 101)∉ P

(iii) (145, 265)
145% 10 ≤ 265% 10 ⇒ 5 ≤ 5 is true and (145/10, 265/10) = (14, 26) e P has to be checked.
Now consider (14, 26).
14% 10 ≤ 26% 10 ⇒ 4 ≤ 6 is true and (14/10, 26/10) = (1, 2) ∈ P has to be checked. Now consider (1, 2)
1% 10 ≤ 2% 10 ⇒ 1 ≤ 2 is true and (1/10, 2/10) = (0, 0) ∈ P which is given to be true. Therefore (145, 265) ∈ P.

(iv) (0, 153):
0% 10 ≤ 153% 10 ⇒ 0 ≤ 3 is true.
Then (0/10, 153/10) = (0, 15) should be in P. (0, 15):
0% 10 ≤ 15% 10 ⇒ 0 ≤ 5 is true.
Then (0/10, 15/10) = (0, 1) should be in P. (0, 1):
0% 10 ≤ 1% 10 ⇒ 0 ≤ 1 is true.
Then (0/10, 1/10) = (0, 0) should be in P. It is given that (0, 0) ∈ P Therefore (0, 153) ∈ P.
So (iii) and (iv) are contained in P.

Answer: (d) U
Explanation:
The given set theory expression can be converted into equivalent boolean algebra expression as follows:
(p∩q∩r) ∪ (p^c ∩ q ∩ r) ∪ q^c ∪ r^c
= p.q.r + p’.q.r + q’ + r’
= qr (p + p’) + q’ + r’
= qr + q’ + r’
= (q + q’) . (r + q’) + r’
= r + q’ + r’
= r + r’ + q’
= 1 + q’
= 1 = U

Answer: (a) (i) and (iv) only
Explanation:
In lattice, every pair in the Hasse diagram must have Least Upper Bound (LUB) and Greatest Lower Bound (GLB). In figure

For element d, e LUB (d, e) = {b, c} but LUB must be unique i.e. only 1 element present in LUB. Same for GLB (b, c) = {d, e} Hence not lattice.

GLB (b, d) = {c, e} but GLB must be unique i.e. only 1 element present in GLB. Hence not lattice. So, (ii) and (iii) are not lattice

Answer: (a) Commutativity
Explanation:
Group properties are closure, associativity existence of identity, and existence of inverse for every element. Commutativity is not required for a mathematical structure to become a group.

Answer: (d) R is neither symmetric nor antisymmetric
Explanation:
Given, R {(x, y), (x, z), (z, x), (z, y)) on set {x, y, z}, here (x, y) ∈ R and (y, x) ∉ R.
∴ R is not symmetric
Also(x, z)ER and(z, x) ∈ R.
∴ R is not an autism metric.
R is neither symmetric nor anti-symmetric.

Answer: (c) c, d are generators
Explanation:
If an element is a generator, all elements must be obtained as powers of that element.
Try a, b, c, d one by one to see which are the generators.
a = a
a² = a.a = a
a³ = a.a² = a.a = a and so on.
∴ a is not the generator,
b = b
b² = b.b = a
b³ = b.b² = b.a = b
b⁴ = b.b³ = b.b = a and so on

∴ b is not the generator c = c
c² c.c = b
c³ = c.c² = c.b = d
c⁴ = c.c³ = c.d = a
Since all of a, b, c, d have been generated as powers of c

∴ c is a generator of this group.
Similarly,
d = d
d² = d.d = b
d³ = d.d² d.b = c
d⁴ = d.d³ = d.c a
∴ d is the other generator.

Answer: (c) 2²⁰
Explanation:
A number of reflexive relations on a set with n elements = 2^{n² – n}.
Here n = 5. So, answer is 2^{5² – 5} = 2²⁰.

Answer: (a) a group
Explanation:
The structure ({n, n^th roots of unity}, ×) always forms a group. When n = 3 we get the set ({1, w, w²}, ×) which must also form a group.
or
The fact that ({1, w, w²}, × ) forms a group can also be seen by the fact that it satisfies the four group properties.

From the above operation table, we can see that the given operation is closed, on the given set.
2. Associative: “*” is an associative operation.
3. Identity: From the operation table, we can see that the identity element, is “1”.
4. Inverse: From the operation table, we can see that the inverse of 1 is 1, the inverse of w is w² and the inverse of w² is w.
So, ({1, w, w²}, *) is a group.
To be a ring, integral domain, or field, we need two binary operations to be specified, whereas here we have only one operation given. So, choice (a) is correct.

Answer: (c) 2ⁿ– 2
Explanation:
Let n = 2. There are only 2 onto functions as shown below:

For, n = 2
Option (a) 2ⁿ = 2² = 4
Option (b) 2ⁿ – 1 = 2² – 1 = 3
Option (c) 2ⁿ — 2 = 2² — 2 = 2
Option (d) 2(2ⁿ — 2) = 2(2² – 2) = 4
So only option (c) gives correct answer.
Alternate method:
The number of onto functions from a set A with m elements to set B with n elements where n < m is given by
n^{m – n}C₁(n- 1)^m+ ⁿC₂(n —2)^m … + ⁿC_{n- 1} 1^m
Here, m = n = 2
So number of onto functions = 2ⁿ—²C₁ 1^m = 2ⁿ – 2
which is choice (c).

Answer: (a) Commutative but not associative
Explanation:
x ⊕ y = x² + y²
y ⊕ x = y² + x²
As ‘+’ sign in commutative so x² + y² is equal to y² + x² so x ⊕ y is commutative.
Now check associativity
x ⊕ (y ⊕ z) = x ⊕ (y² + z²)
= x² + (y² + z²)²
= x² + y⁴ + z⁴ + 2y²z²
(x ⊕ y) ⊕ z = (x² + y²) ⊕ z
= (x² + y²)² + z²
= x⁴ + y⁴ + 2x²y² + z²
x ⊕ (y ⊕ z) t- (x ⊕ y) ⊕ z
So not associative Option (a) is correct.

Explanation:
f : {0, 1}⁴ → {0,1} ⇒ S is the set of all functions from a 16 element set to a 2 element set.
| S | =2¹⁶
N = Number of functions from S to 2 element set {0, 1} = 2²¹⁶ ]
N = 22
∴ log log N = log log 22’6 = log2²¹⁶ = 16

Answer: (a) Both S₁ and S₂ are true
Explanation:
Given the following details:
S = {1,2,3,4,. ..2014}
U < V if the minimum element in the symmetric difference of the two sets is in U.
S₁: There is a subset of S that is larger than every other subset.
S₂: There is a subset of S that is smaller than every other subset.
S₁ is true since Φ (which is a subset of S) is larger than every other subset.
i.e. ∀u v < Φ is true since the minimum element in v △ Φ = v, is in v.
(Note: v △ Φ = uΦ + v’Φ = v)
S₂ is also true since S (which is a subset of S) is smaller than every other subset, i.e. ∀u S < v is true since the minimum element in S △ v = v’, is in <S.
(Note: S △ v = Sv’ + S’v = lv’ + Ov =v’)
∴ Both S1 and S2 are correct.

Answer: (d) For any subsets S and Tof Y, f^-1(S ∩ T) = f ^-1(S) ∩ f^-1(T)
Explanation:
Example:

Let A = {1, 2}, B = {3, 4}
(a) |f (A ∪ B)| = |f(A) |+ |f(B)|
⇒ 3 = 2 + 2 is false

(b) f (A ∩ B) = f (A) ∩ f (B)
⇒ Φ = {a} is false

(c) |f(A ∩ B)| =min{|f(A)|, |f(B)|}
⇒ 0 = min (2, 2) = 2 is false

(d) Let S = {a, b}, T- {a, c}
f^-1 (S ∩ T)=f^-1(S)∩ f^-1(T)
⇒ {1, 3} = {1, 2, 3} n {1, 3, 4}
⇒ {1, 3} = {1, 3} is true

Explanation:
Order of subgroup divides the order of group (Lagrange’s theorem). So the order of L has to be 1, 3, 5, or 15. As it is given that the subgroup has at least 4 elements and it is not equal to the given group, therefore the order of the subgroup can’t be 1, 3, or 15. Hence it is 5.

Answer: (b) Only Q and R are true
Explanation:
Since it is given that ∀i f(f(i)) = i
It means f . f = I i.e. f = f’^-1 That is f is a symmetric function.
Statement P means that every symmetric function is an identity function which is false since there are many symmetric functions other than the identity function.

Example: {(0,1), (1,0), (2, 3), (3,2),…(2012,2013),(2013, 2012), (2014, 2014)} is a symmetric function but not the identity function.

Statement Q means that in every such symmetric function at least one element is mapped to itself and this is true since there is an odd number of elements in the set {0, 1, 2, … 2014}.

Statement R means that every symmetric function is onto which is true since it is impossible to make an into function symmetric. See the below diagram for an into function shown with only 3 elements:

In the above function note that (2, 1) exists in the function but not (1,2) and so it is not symmetric.

Explanation:
(i) e is identity element
(ii) x*x = e, so x = x^-1.
(iii) y*y = e, so y = y^-1.
(iv) (x*y)*(x*y) = e, so x*y = (x*y)^-1 and (y*x)*(y*x) = e, so y*x = (y*x)^-1.
Now (x*y)*(y*x) = x*(y*y)*x = x*e*x = x*x = e
So, (x*y)^-1. = (y*x)
From (i) and (ii) we get x*y* = y*x
There are only 4 distinct elements possible in this group
1. e
2. x
3. y
4. xy
All other combinations are equal to one of these four as can be seen below:
yx = xy (already proved)
xxx = xe = x
xyy = xe = x
xxy = ey = y
xyx = xxy = y
and so on…….
So the group is G = {e, x, y, x*y
⇒ |G| = 4

Answer: (a) \(\frac{h(x)}{g(x)}\)
Explanation:
g(x) = 1 – x, h(x) = \(\frac{x}{x-1}\)
\(\frac{g(h(x))}{h(g(x))}\) = \(\frac{g\left(\frac{x}{x-1}\right)}{h(1-x)}\) = \(\frac{1-\frac{x}{x-1}}{\frac{1-x}{1-x-1}}\) = \(\frac{x-1-x}{\frac{x-1}{\frac{1-x}{-x}}}\) = \(\frac{\frac{-1}{x-1}}{\frac{1-x}{-x}}\) = \(\frac{x}{(x-1)(1-x)}\) = \(\frac{-x}{(1-x)^{2}}\)
\(\frac{h(x)}{g(x)}\) = \(\frac{x}{\frac{x-1}{1-x}}\) = \(\frac{x}{(1-x)(x-1)}\) = \(\frac{-x}{(1-x)^{2}}\)
∴ \(\frac{g(h(x))}{h(g(x))}\) = \(\frac{h(x)}{g(x)}\)

Answer: (c) 1, 2, and 3 only
Explanation:
A = {5, {6}, {7}}
1. Φ ∈ 2^A is true. Any power set contains an empty set.
2. Φ ⊆ 2^A is true. Empty set is subset of any set.
3. {5, {6}}e 2^A is true, power set of A contain {5, {6}} as a 2 element subset of A.
4. {5, {6}} ⊆ 2^A is false. Power set of A not contain 5 and {6} as elements.
So {5, {6}} can not be subset of 2^A.

Answer: (d) \(\frac { 1 }{ 5 }\) < p_r < 1
Explanation:
L has 5 elements
L³ has all ordered triplets of elements of L
⇒ L³ contain 5 × 5 × 5 = 5³ = 125 elements.

If q, r, s are chosen, then only it will violate the distributive property. Number of ways to choose q, r, s in any triplet order = 3! = 3 × 2 × 1 = 6.
∴ p(satisfying distributive property)
= 1 – p(violate the distributive property)
= 1 – \(\frac{6}{5^{3}}\) = 0.952 which is between \(\frac{1}{5}\) and 1.

Answer: (d) R is symmetric but not reflexive and not transitive
Explanation:
aRb iff a and b are distinct a and b have a common divisor other than 1.
(i) R is not reflexive since a and b are distinct i.e, (a, a) ∉ R
(ii) R is symmetric If a and b are distinct and have a common divisor other than 1, then b and a also are distinct and have a common divisor other than 1.
(iii) R is not transitive
If (a, b) ∈ R and (b, c) ∈ R then (a, c) need not be in R.
Example: (2, 6) ∈ R and (6, 2) ∈ R, but (2, 2) ∉ R
∴ R is symmetric but not reflexive and not transitive.

Explanation:
Let X = {0, 1,2,…..10}
|X| = 1
|P(X)| = 2¹¹ = 2048

Explanation:

The number of onto functions from A → B where | A | = m and | B | = n is given by the formula
n^{m – n}C₁(n – 1)^{m + n}C₂(n – 2)^m +…
+ (-1)^{n – 1 n}C_{n – 1}1^m

Here, m = 4 and n = 3
Substituting in above formula we get, 3⁴ – ³C₁(3 – 1)⁴ + ³C₂ (3 – 2)⁴ = 81 – 48 + 3 = 36

Explanation:

Total possible functions = 20² = 400
Number of one-to-one functions = 20P₂ = 20 × 19
∴ Required probability = \(\frac{20 \times 19}{20 \times 20}\) = 0.95

Answer: (b) Only S₂ is True
Explanation:
X # Y = X’ + Y’
This is the NAND operation. NAND is known to be commutative but not associative. So, only S₂ is true.

Answer: (d) ∀X ∈U ∀ Y ∈U(X\Y =Y’\X’)
Explanation:
S = {1, 2, 3, 4, 5, 6}
U is the power set of S ⇒ U = P(S)
U ={{ } {1}, {2}, …{1, 2}, {1, 3}, …{1, 2, 3}, … {1, 2, 3, 4}, …{1, 2, 3, 4, 5} …{1, 2, 3, 4, 5, 6}}
| U |= 2⁶ = 64 elements.
T ∈ U ⇒ T’ ∈ U
R ∈U, T\R=T – R

(a)∀X ∈ U(| X | = | X’ |) means that every subset of S has same size as its complement. Clearly this is False.
(For example, {1} ∈ U, and complement of {1} = {2, 3, 4, 5, 6})
(b)∃X ∈ U∃Y ∈ U(|X|=5,|Y|=5 and X ∩ Y = Φ) means that there are two 5 element subsets of S which have nothing in common. This is clearly False.
Since any two 5 element subsets will have atleast 4 elements in common.
(c) ∀X ∈ U ∀ Y ∈ U(|X| = 2,|y|=3 and X\Y = Φ) means that every 2 element subset X and every 3 element subset Y will have X – Y = Φ i.e., X ⊆ Y.
This is clearly False as can be seen from the example X= {1,2}, Y = {3,4,5} where X’^Y.
(d) ∀X ∈ U ∀T ∈ U(X \Y = Y’\X’) means that for any two subsets X and Y, X\ Y = Y \ X’ i.e. X – Y = Y’ – X’.
This is clearly True since by boolean algebra LHS = X – Y = XY’.
RHS =Y’ -X’ = Y’Xand therefore LHS = RHS.

Answer: (c) Not reflexive but symmetric
Explanation:
R = {(p, q), (r, s) I p – s = q – r}
(i) Check reflexive property
∀(p, q) ∈ Z⁺ × Z⁺ ((p, q), (p, q)) ∈ R
is true iff p – q = q – p which is false. So relation R is not reflexive.
(ii) Check symmetry property
If ((p, q), (r, .s’))∈ R then ((r, s), (p, q)) ∈ R
((p, q), (r, s)) ∈ R ⇒ p – s = q – r
((r, s), (p, q)) ∈ R ⇒ r – q = s – p
If p – s = q – r is true, then r — q = s – p is also true by rearranging the equation.
∴ R is symmetric.

Explanation:
f(n) = f\(\left(\frac{n}{2}\right)\) if n is even
f(n) = f{n + 5) if n is odd
f : N⁺ → N⁺
Now f(2) = f\(\left(\frac{2}{2}\right)\) = f(1)
f(3) = f(3 + 5) = f(8) = f\(\left(\frac{8}{2}\right)\) = f(4) = f\(\left(\frac{4}{2}\right)\) = f(2) = (1)
So, f(1) = f(2) = f(3) = f(4) = f(8)
Now let us find f(5) = f(5 +5) = f(10) = f\(\left(\frac{10}{2}\right)\)
= f(5) so f(5) = f(10)
Now let us find f(9)
f(9) = f(9 +5) = f(14) = f\(\left(\frac{14}{2}\right)\) = f(7)
= f(7 + 5) = f(12) = f\(\left(\frac{12}{2}\right)\) = f(6)
= f\(\left(\frac{6}{2}\right)\) = f(3)
So f(9) = f(7) = f(6) = f(3) = f(1) = f(2) = f(4) = f(8)
For n > 10, the function will be equal to one of f(1), f(2)….f(10)
So the maximum no. of distinct values / takes is only 2.
First is f(1) = f(2) = f(3) = f(4) = f(8) = f(9) = f(7) = f(6)
Second is f(5) = f(10)
All other n values will give only one of these two values.

Answer: (b) P is true and Q are false
Explanation:
(a, b) R (c, d) if a ≤ c or b ≤ d
P : R is reflexive
Q : R is transitive
Since, (a, b) R (a, b) ⇒ a ≤ a or b ≤ b ⇒ t or t
Which is always True, R is reflexive. Now let us check transitive property
Let(a,b) R (c, d) ⇒ a ≤ c or b ≤ d
and(c, d) R {e, f) ⇒ c ≤ e or d ≤ f
Now let us take a situation
a ≤ c (True) or b ≤ d ( false)
and c ≤ e (False) or d ≤ f (True)
Now we can get neither a ≤ e nor b ≤ f So, (a, b) R (c, d) and (c, d) R (e, f) ≠ (a, b) R (e, f). So clearly R is not transitive.
So Pis true and Q is false. Choice (b) is correct.

Answer: (b) Only II
Explanation:
This is actually a graph theory Question. Let the components be represented by vertices and if component x reacts with component y then let there be an undirected edge between x and y.Now, 9 of the 23 vertices will have 3 degrees each.
Note: U \ S means U — S, which is the remaining 23 – 9 = 14 vertices.
By Handshaking theorem,
9 × 3 + degree of 14 vertices = 2e = Even. i.e., 27 + degree of 14 vertices = 2e = Even. So, the total degree of 14 vertices must be odd.
Statement I means that the degree of each of the 14 vertices is odd, which means that the total degree of 14 vertices will be even (since even number of odd numbers is always even). But we need the total degree of 14 vertices to be odd so, statement I is false.
Statement III means that everyone of the 14 vertices has even degree, which guarantees that the total degree of 14 vertices will be even. So, statement III is false. Since statement II is the negation of statement III, it must be true.

Explanation:
Since the given hasse diagram is already a lattice, three is no need to add any ordered pair. So the answer is 0.

Explanation:
Let A → -5- by 3
B → ÷ by 5
C →÷ by 7
n(A ∪ B ∪ C) = n(A)+n(B) + n(C) – n(A ∩ B) – n(A ∩ C) – n(B ∩ C) + n(A ∩ B ∩ C)
= \(\left[\frac{500}{3}\right\rfloor\) + \(\left[\frac{500}{5}\right\rfloor\) + \(\left[\frac{500}{7}\right\rfloor\) – \(\left[\frac{500}{15}\right\rfloor\) – \(\left[\frac{500}{21}\right\rfloor\) – \(\left[\frac{500}{35}\right\rfloor\) + \(\left[\frac{500}{105}\right\rfloor\) = 166 + 100 + 71 – 33 – 23 – 14 + 4 = 271

Explanation:
Given | G | =84
By Lagrang’s theorem any subgroup size is a divisior of 84.
But a proper subgroup cannot have same size as group.
So largest divisor of 84, other than 84 is 42. So, largest proper subgroup can have in size of 42.

Answer: (d) P, Q, and S only

Explanation:
P: Set of rational number → countable
Q: Set of functions from {0, 1} to N → N

0 can be assigned in N ways
1 can be assigned in N ways
There are N × N functions, the cross product of countable set in countable.
R: Set of functions from N to {0,1}

Each of these boxes can be assigned to 0 or 1 so each such function is a binary number with an infinite number of bits.
Example: 0000 is the binary number corresponding to 0 is assigned to all boxes and so on. Since each such binary number represents a subset of N (the set of natural numbers) by characteristic function method, therefore, the set of such function is the same as the power set of N which is uncountable due to Cantor’s theorem, which says that power set of a countably infinite set is always uncountably infinite.
S: Set of finite subsets of N → countably infinite since we are counting only finite subsets. So P, Q, and S are countable.

Answer: (b) R₁ only
Explanation:
R₁: ∀a, b ∈ G,a R₁ b if and only if ∃g∈ G such that a = g^-1bg
Reflexive: a = g^-1ag can be satisfied by putting g = e, identity “e” always exists in a group.
So reflexive
Symmetric: aRb ⇒ a = g^-1ag for some g
⇒ b = gag^-1 = (g^-1)^-1 ag^-1 g^-1 always exists for every g ∈ G.
So symmetric
Transitive: aRb and bRc ⇒ a = g₁^-1bg₁ and b = g₂^-1 cg2 for some g₁g₂ ∈ G.
Now a=g₁^-1g₂^-1cg₂g₁(g₂g₁)^-1 cg₂g₁
g₁ ∈ G and g₂ ∈ G ⇒ g₂g₁ ∈ G since group is closed so aRb and aRb ⇒ aRc hence transitive
Clearly R₁ is equivalence relation.
R₂ is not equivalenced it need not even be reflexive, since aR₂ a => a = a^-1 ∀a which not be true in a group.
R₁ is equivalence relation is the correct answer.

Explanation:
A = {1, 2, 3}
n = |A| = 3
Number of relations on A = 2^n² = 2^3² = 2⁹
Number of reflexive relations on A
= 2^{n² – n}  = 2^{3² – 3} = 2⁶

Explanation:
Size of group = O(G) = 35
Lagrange’s theorem says if H is a subgroup of G
then O(H) | 0(G).
So 0(H) can be 1, 5, 7 or 35.
So largest subgroup size other than G itself is 7.

Answer: (a) If a relation S is reflexive and circular, then S is an equivalence relation.
Explanation:
Let S be reflexive and circular,
Let us checking symmetry:
Symmetry:
Let xSy
Now since S is reflexive ySy true.
So xSy and ySy is true
Now by circular property we get, ySx
So xSy => ySx
So S is symmetric.
Transitive:
Let xSy and ySz
Now by circular property we get zSx and by symmetry property proved above, we get
zSx => xSz
So xSy and ySz => xSz
So S is transitive.
So S is reflexive, symmetric and transitive and hence an equivalence relation.
So option (a) is true.
Option (b): Let S be circular and symmetric. Let S be defined on set {1, 2, 3}
Now empty relation is circular and symmetric but not reflexive. So S need not be an equivalence relation.
So option (b) is false.
Option (c): Let S be transitive and circular. Let S be defined on the set {1, 2, 3}
Now empty relation again satisfies transitive and circular but is not reflexive. So S need not be an equivalence relation.
So option (c) is false.
Option (d): Reflexive and symmetric need not be transitive for example on {1, 2, 3}.
S = {(L 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)}
is reflexive and symmetric. But it is not transitive because (1, 2) and (2, 3) belong to S but (1, 3) does not.
So option (d) is false.

Answer: (c) G may not be cyclic, but H is always cyclic.
Explanation:
|G| = 6
H is subgroup, so by Lagrange’s theorem
| H | = 1, 2, 3 or 6 (Divisor’s of 6) Now it is given that 1 < | H | <6 or | H | = 2 or 3
Since 2 and 3 are both prime and since every group of prime order is cyclic, H is surely cyclic. But order of | G | =6 which is not prime. So G may or may not be cyclic. So G may not be cyclic, but H is always cyclic. Option (c) is correct.

Answer:
(a) There exists a surjection from S₁ to S₂.
(d) There exists a bijection from S₁ to S₂.
Explanation:
| S₁ | = 3ⁿ
Since each of the n2 entries in n × n matrix can be fills in 3 ways.
|S₂| = 3ⁿ2
Since | {0, 1, 2} | =3 and | {0, 1, 2, n2 — 1} | = n²)
Now the theorem says A bijection f_{A → B} exists iff |A| = |B|.
Here |S₁| = |S₂|
So, there has to be a bijection from S₁ to S₂. So, option (d) is correct. If bijection exists surely surjection also exists. So, option (a) is also correct. Option (b) and (c) are incorrect.

Explanation:
The Venn diagram for this is

Now every element x in S has only 3 options. It can be x ∈ A or x ∈ B – A or x ∈ S — B. So the number of ways to choose A and B such that A ⊆ B ⊆ S is 3¹⁰.

Answer: (a) 10
Explanation:
L is the set of 10-dimensional orthogonal vectors.
So cardinality of L ≤ 10.
i.e., Maximum cardinality of L = 10.
So, option (a) is correct.