GATE 2024 CS (CS1) – Question 32
Let $A$ and $B$ be non-empty finite sets such that there exist one-to-one and onto functions (i) from $A$ to $B$ and (ii) from $A\times A$ to $A\cup B$. The number of possible values of $|A|$ is __________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 2
Explanation
Let $|A|=|B|=n$ (a bijection $A\to B$ exists, so the sizes are equal).
A bijection $A\times A\to A\cup B$ requires $|A\cup B|=|A\times A|=n^2$.
Also $n\le|A\cup B|\le 2n$ (it contains $A$, and has at most $|A|+|B|$ elements). Hence $n\le n^2\le 2n$, so $n\ge1$ and $n\le2$.
- $n=1$: need $|A\cup B|=1$, take $A=B=\{x\}$. Works.
- $n=2$: need $|A\cup B|=4$, take $A,B$ disjoint. Works.
So $|A|\in\{1,2\}$ and the number of possible values is **2**.
More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions
- GATE 2024 CS (CS2) Q34
- GATE 2023 CS Q49
- GATE 2021 CS (CS1) Q53
- GATE 2020 CS Q27
- GATE 2019 CS Q31
- GATE 2019 CS Q64
All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →