Set Theory – GATE CSE Engineering MathematicsPractice Questions & PYQs

The symmetric difference, denoted by $(R-S) \cup (S-R)$, contains elements present in either $R$ or $S$, but not in both. The union $(R \cup S)$ contains elements present in $R$ only, $S$ only, or in both. By subtracting the symmetric difference from the union, we remove the elements that are exclusively in $R$ or exclusively in $S$.

This operation effectively leaves only the elements common to both sets, which is the definition of the intersection:
$(R \cup S) - [(R-S) \cup (S-R)] = R \cap S$
This identity holds because $(R \cup S)$ is the disjoint union of $(R-S)$, $(S-R)$, and $(R \cap S)$. Removing the first two sets leaves exactly $(R \cap S)$.

A relation on a set A is a subset of the Cartesian product $A \times A$. If the set A has $n$ elements, then $A \times A$ has $n^2$ ordered pairs. The total number of possible relations on A is the number of subsets of $A \times A$, which is $2^{n^2}$.

A relation R is defined as reflexive if for every element $a \in A$, the pair $(a, a)$ is in R. These pairs correspond to the main diagonal of the relation matrix.

For a set with $n$ elements, there are $n$ such diagonal pairs. For a relation to be reflexive, all of these $n$ pairs must be included in the relation. This means we have no choice for these $n$ pairs; their inclusion is mandatory.

For the remaining $n^2 - n$ off-diagonal pairs, each one can either be included in the relation or not. This gives us 2 choices for each of these off-diagonal pairs.

Therefore, the total number of possible reflexive relations is $2^{n^2 - n}$.

Given a set with 5 elements, we have $n=5$. The number of reflexive relations is:
$2^{5^2 - 5} = 2^{25 - 5} = 2^{20}$.

The given expression is $(P\cap Q\cap R)\cup (P^{C} \cap Q \cap R)\cup Q^{C} \cup R^{C}$.
First, factor out $(Q\cap R)$ from the first two terms to obtain $(P\cup P^{C})\cap (Q\cap R)\cup Q^{C}\cup R^{C}$.
Since $(P\cup P^{C}) = U$, the expression simplifies to $U \cap (Q\cap R) \cup Q^{C}\cup R^{C}$, which is $(Q\cap R)\cup Q^{C}\cup R^{C}$.
Apply De Morgan's Law, $Q^{C}\cup R^{C} = (Q\cap R)^{C}$, transforming the expression into $(Q\cap R)\cup (Q\cap R)^{C}$.
Finally, by the complement law $A \cup A^{C} = U$, where $A = (Q\cap R)$, the expression equals $U$.

A subset $S \subseteq \mathbb{C}$ is a subfield if it contains $0, 1$ and is closed under addition, subtraction, multiplication, and inversion.
S1 ($\mathbb{R}$) is a well-known subfield of $\mathbb{C}$.
S2, the Gaussian rationals $\mathbb{Q}(i) = \{a + bi \mid a, b \in \mathbb{Q}\}$, is a subfield because it is closed under operations, and for any non-zero $a+bi$, the inverse $\frac{a}{a^{2+}b^2} - i\frac{b}{a^{2+}b^2}$ remains in $\mathbb{Q}(i)$ since $a, b, a^{2+}b^2 \in \mathbb{Q}$.
S3 is not a subfield because it is not closed under addition: for $z_1 = 0.8$ and $z_2 = 0.8$, $z_1, z_2 \in S3$, but $z_1 + z_2 = 1.6$, and $1.6^2 + 0^2 > 1$.
S4 is not a subfield because it is not closed under multiplication: $i \cdot i = -1$, which cannot be expressed as $ia$ for any $a \in \mathbb{R}$.
Thus, only S1 and S2 satisfy the requirements.

The definition of the partial order $(a, b) \in P$ requires that for every digit position $k$, the $k$-th digit of $a$ must be less than or equal to the $k$-th digit of $b$ (padding with leading zeros).
i. For $(101, 22)$, comparing digits gives $1 \not\leq 0$ in the hundreds place, so $(101, 22) \notin P$.
ii. For $(22, 101)$, comparing the units place gives $2 \not\leq 1$, so $(22, 101) \notin P$.
iii. For $(145, 265)$, comparing digit-by-digit: $1 \leq 2$, $4 \leq 6$, and $5 \leq 5$. All conditions hold, so $(145, 265) \in P$.
iv. For $(0, 153)$, comparing digit-by-digit: $0 \leq 1$, $0 \leq 5$, and $0 \leq 3$. All conditions hold, so $(0, 153) \in P$.
Therefore, the pairs contained in $P$ are (iii) and (iv).

Any finite language is regular, as it can be recognized by a finite automaton with a path for each string.
A. Every subset of a regular set is regular. False. Example: $\Sigma^*$ is regular, but $\{a^n b^n | n \ge 0\} \subset \Sigma^*$ is not regular.
B. Every finite subset of a non-regular set is regular. True. Any finite language is regular.
C. The union of two non-regular sets is not regular. False. Let $L_1 = \{a^n b^n | n \ge 0\}$ and $L_2 = \Sigma^* \setminus L_1$. Both $L_1$ and $L_2$ are non-regular. However, $L_1 \cup L_2 = \Sigma^*$, which is regular.
D. Infinite union of finite sets is regular. False. Example: $L = \bigcup_{n=0}^{\infty } \{a^n b^n\}$ is an infinite union of finite sets, but $L$ is non-regular.

Let $\sim$ be an equivalence relation on a set $A$. The equivalence class $[a]$ of an element $a \in A$ is defined as $\{x \in A \mid x \sim a\}$.
Since every $a \in A$ belongs to $[a]$, the union of all equivalence classes equals the original set $A$ ($\bigcup_{a \in A} [a] = A$).
Furthermore, for any two classes $[a]$ and $[b]$, if they share a common element, then transitivity and symmetry imply $[a] = [b]$, meaning the classes are pairwise disjoint.
By definition, a collection of non-empty, pairwise disjoint subsets whose union is $A$ constitutes a partition of $A$.
Therefore, the set of all equivalence classes of $A$ forms a partition of $A$.

Let S be a set with n elements.

The smallest equivalence relation on S is the identity relation, $I_S = \{(a,a) \mid a \in S\}$. This relation is reflexive, symmetric, and transitive. The number of ordered pairs in $I_S$ is $n$.

The largest equivalence relation on S is the universal relation, $S \times S = \{(a,b) \mid a,b \in S\}$. This relation is also reflexive (as $(a,a) \in S \times S$), symmetric (as $(a,b) \in S \times S \implies (b,a) \in S \times S$), and transitive (as $(a,b) \in S \times S \text{ and } (b,c) \in S \times S \implies (a,c) \in S \times S$). The number of ordered pairs in $S \times S$ is $n \times n = n^2$.

Thus, the number of ordered pairs in the largest and the smallest equivalence relations are $n^2$ and $n$, respectively.

The algorithm calculates $z[i] = (x[i] \land \neg y[i]) \lor (\neg x[i] \land y[i])$.
The term $(x[i] \land \neg y[i])$ equals $1$ if and only if $i \in X$ and $i \notin Y$, which represents the set $X - Y$.
The term $(\neg x[i] \land y[i])$ equals $1$ if and only if $i \notin X$ and $i \in Y$, which represents the set $Y - X$.
The operator $\lor$ performs the set union of these two conditions.
Therefore, $z[i] = 1$ if $i \in (X - Y) \cup (Y - X)$, which corresponds to the symmetric difference of sets $X$ and $Y$.

Define $f(i) = \sum_{j=1}^{n} \mathbb{I}(i \in X_j)$, where $\mathbb{I}$ is the indicator function.
The total sum is given by $\sum_{i=1}^{m} f(i) = \sum_{i=1}^{m} \sum_{j=1}^{n} \mathbb{I}(i \in X_j)$.
By swapping the order of summation, we obtain $\sum_{j=1}^{n} \sum_{i=1}^{m} \mathbb{I}(i \in X_j)$.
Since each subset $X_j$ has exactly 3 elements, the inner sum simplifies to $\sum_{i=1}^{m} \mathbb{I}(i \in X_j) = |X_j| = 3$.
Therefore, the total sum is $\sum_{j=1}^{n} 3 = 3n$.

Let $E$ denote the minimum value in sample $S$. The minimum value is $2^k$ if $2^k \in S$ and no $2^i \in S$ for $i < k$.
Since each $x_i$ is selected independently with probability $p_i = \frac{1}{2}$, the probability that the minimum element is $2^k$ is:
$P(\min(S) = 2^k) = P(2^k \in S) \prod_{i=1}^{k-1} P(2^i \notin S) = \frac{1}{2} \cdot \left(\frac{1}{2}\right)^{k-1} = \left(\frac{1}{2}\right)^k$
The expected value $E[\min(S)]$ is the sum of products of the values and their probabilities for $k = 1, \dots, n$:
$E[\min(S)] = \sum_{k=1}^{n} 2^k \cdot P(\min(S) = 2^k) = \sum_{k=1}^{n} 2^k \cdot \left(\frac{1}{2}\right)^k$
$E[\min(S)] = \sum_{k=1}^{n} 1 = n$

The condition $\min(p(A)) = \min(p(B))$ is satisfied if and only if the element $x \in A \cup B$ that maps to the minimum value under the permutation $p$ belongs to the intersection $A \cap B$.

For any permutation $p$, the element $u \in A \cup B$ that minimizes the mapping $p(u)$ is uniformly distributed among all $|A \cup B|$ elements of the set $A \cup B$. The probability that this element lies in $A \cap B$ is therefore $\frac{|A \cap B|}{|A \cup B|}$. Since there are $n!$ total permutations and each is equally likely, the number of permutations satisfying the condition is:

$n! \times \frac{|A \cap B|}{|A \cup B|}$

$X = (E \cap F) \cap (F \cap G)^c = (E \cap F) \cap (F^c \cup G^c) = (E \cap F \cap F^c) \cup (E \cap F \cap G^c) = E \cap F \cap G^c$.
For $Y$, simplify the first term: $E - (E \cap G) = E \cap (E^c \cup G^c) = E \cap G^c$.
Then substitute into $Y$: $Y = (E \cap G^c) - (E \cap F^c) = (E \cap G^c) \cap (E \cap F^c)^c$.
Using De Morgan's laws: $Y = (E \cap G^c) \cap (E^c \cup F) = (E \cap G^c \cap E^c) \cup (E \cap G^c \cap F)$.
This simplifies to $\emptyset \cup (E \cap F \cap G^c) = E \cap F \cap G^c$.
Since $X = E \cap F \cap G^c$ and $Y = E \cap F \cap G^c$, it follows that $X = Y$.

An identity element $z$ for a binary operation $f$ on $\mathbb{N}$ must satisfy $f(a, z) = a$ and $f(z, a) = a$ for all $a \in \mathbb{N}$.

i. For $f(x, y) = x + y - 3$, solving $f(a, z) = a + z - 3 = a$ yields $z = 3$. Since $3 \in \mathbb{N}$, $3$ is the identity.
ii. For $f(x, y) = \max(x, y)$, setting $z = 1$ gives $f(a, 1) = \max(a, 1) = a$ and $f(1, a) = \max(1, a) = a$ for all $a \in \mathbb{N}$. Thus, $1$ is the identity.
iii. For $f(x, y) = x^y$, solving $f(a, z) = a^z = a$ implies $z = 1$. However, $f(z, a) = 1^a = 1$, which is not equal to $a$ for $a > 1$, so no identity exists.
Therefore, only operations (i) and (ii) possess an identity.

Given $|X|=x$ and $|Y|=y$, the cardinality of the Cartesian product $W = X \times Y$ is $|W| = |X| \cdot |Y| = xy$.
The set $E$ is the power set of $W$, so its size is $|E| = 2^{|W|} = 2^{xy}$.
The number of functions from a set $Z$ (where $|Z|=z$) to a set $E$ is defined by the formula $|E|^{|Z|}$.
Substituting the known values, we obtain $(2^{xy})^z$.
Using the exponent rule $(a^b)^c = a^{bc}$, this simplifies to $2^{xyz}$.

To find the cardinality of $X$, use the Principle of Inclusion-Exclusion to count multiples of $2, 3,$ or $5$ in the range $[1, 123]$.
Single multiples: $\lfloor \frac{123}{2} \rfloor = 61$, $\lfloor \frac{123}{3} \rfloor = 41$, and $\lfloor \frac{123}{5} \rfloor = 24$. The sum is $61 + 41 + 24 = 126$.
Double multiples: $\lfloor \frac{123}{6} \rfloor = 20$, $\lfloor \frac{123}{10} \rfloor = 12$, and $\lfloor \frac{123}{15} \rfloor = 8$. The sum is $20 + 12 + 8 = 40$.
Triple multiple: $\lfloor \frac{123}{30} \rfloor = 4$.
The number of integers divisible by at least one of these is $126 - 40 + 4 = 90$.
Therefore, the number of integers not divisible by 2, 3, or 5 is $123 - 90 = 33$.

The number of integers $m$ such that $1 \leq m \leq n$ and $\gcd(m,n)=1$ is given by Euler's totient function $\phi(n)$.
For $n = p^{2}q$ where $p$ and $q$ are distinct primes, we use the property that $\phi$ is multiplicative for coprime factors, so $\phi(p^{2}q) = \phi(p^{2})\phi(q)$.
Using the formula $\phi(p^{k}) = p^{k} - p^{k-1}$, we calculate $\phi(p^{2}) = p^{2} - p = p(p - 1)$.
Since $q$ is prime, $\phi(q) = q - 1$.
Multiplying these values yields $\phi(n) = p(p - 1)(q - 1)$, which corresponds to the target expression.

A collection $C$ of subsets of $A$ where every pair $S_1, S_2$ satisfies $S_1 \subset S_2$ or $S_2 \subset S_1$ is known as a chain in the power set $\mathcal{P}(A)$. For any such chain $\emptyset = S_0 \subset S_1 \subset S_2 \subset \dots \subset S_k = A$, the inclusion property forces a strictly increasing sequence of cardinalities: $0 = |S_0| < |S_1| < |S_2| < \dots < |S_k| = n$. Since each $|S_i|$ must be an integer, the number of distinct subsets in the chain is limited by the number of possible sizes $\{0, 1, \dots, n\}$. Thus, the maximum cardinality of $C$ is the number of elements in this set of sizes, which is $n + 1$.

Using the set property $P - Q = P \cap Q^c$, we expand $X$:
$X = (A \cap B^c) \cap C^c = A \cap B^c \cap C^c$.
Similarly, for $Y = (A \cap C^c) - (B \cap C^c)$, we have:
$Y = (A \cap C^c) \cap (B \cap C^c)^c$.
Applying De Morgan's Law, $(B \cap C^c)^c = B^c \cup C$, so:
$Y = (A \cap C^c) \cap (B^c \cup C) = (A \cap C^c \cap B^c) \cup (A \cap C^c \cap C)$.
Since $C^c \cap C = \emptyset$, the second term vanishes, leaving $Y = A \cap B^c \cap C^c = X$.

Let $P$, $D$, and $C$ represent the sets of students taking Programming, Data Structures, and Computer Organization, respectively.
Using the Principle of Inclusion-Exclusion, the number of students who have taken at least one course is:
$|P \cup D \cup C| = (|P| + |D| + |C|) - (|P \cap D| + |P \cap C| + |D \cap C|) + |P \cap D \cap C|$
Substituting the given values:
$|P \cup D \cup C| = (125 + 85 + 65) - (50 + 35 + 30) + 15 = 275 - 115 + 15 = 175$
The number of students who have not taken any course is the total number of students minus those who have taken at least one:
$200 - 175 = 25$