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 x A to A union B. The number of possible values of |A| is ___________.
A. 1
B. 2
C. 3
D. 4
GATE 2024 · Discrete Mathematics · Functions · medium
Answer: 2
Extract cardinality conditions from the bijections: Bijection A to B: |A| = |B| = k. Bijection A×A to A∪B: |A×A| = |A∪B|, i.e., k^2 = |A∪B|.
Bound |A∪B| and derive constraint on k: k^2 = |A∪B| <= |A|+|B| = k+k = 2k. So k^2 <= 2k => k(k-2) <= 0 => 1 <= k <= 2 (since k >= 1).
Verify both k=1 and k=2 are achievable: k=1: A={x}, B={y} disjoint, A∪B has 2 elements, A×A={(x,x)} has 1 element. 1 != 2. Not valid! k=1: A=B={x}, A∪B=A={x}, A×A={(x,x)}, |A×A|=1=|A∪B|=1. Valid! k=2: A={1,2}, B={3,4} disjoint, |A∪B|=4=k^2=4. Valid! So k=1 and k=2 both work. Number of possible values = 2.