The GATE Grind

GATE 2024 CS (CS1) – Question 32

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 1 mark · Numerical answer

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

So $|A|\in\{1,2\}$ and the number of possible values is **2**.

More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions

All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →