GATE CS 2024 Set 1 Q22 — Sets, Relations and Functions

Let $A$ and $B$ be non-empty finite sets with $|A| = a$ and $|B| = b$, where $a, b \ge 1$.

Step 1: Analyze condition (i)
There exists a bijection (one-to-one and onto function) from $A$ to $B$. This implies: $$|A| = |B| \implies a = b$$

Step 2: Analyze condition (ii)
There exists a bijection from $A \times A$ to $A \cup B$. This implies: $$|A \times A| = |A \cup B|$$ $$a^2 = |A| + |B| - |A \cap B|$$ $$a^2 = 2a - |A \cap B|$$ $$|A \cap B| = 2a - a^2$$

Step 3: Find the possible values of $a$
Since $A \cap B$ is a subset of $A$, its size must satisfy $0 \le |A \cap B| \le a$. Specifically, $|A \cap B| \ge 0$: $$2a - a^2 \ge 0 \implies a(2 - a) \ge 0$$

Since $A$ is non-empty, $a \ge 1$. The only positive integers satisfying this inequality are:

• $a = 1$: Here, $|A \cap B| = 2(1) - 1^2 = 1$, which is valid (occurs when $A = B$).
• $a = 2$: Here, $|A \cap B| = 2(2) - 2^2 = 0$, which is valid (occurs when $A \cap B = \emptyset$).

Thus, the possible values for $|A|$ are $1$ and $2$. The number of possible values is $2$.