Consider the following sets, where n >= 2: S_1: Set of all n x n matrices with entries from the set {a, b, c} S_2: Set of all functions from the set {0, 1, 2, ..., n^2-1} to the set {a, b, c} Which of the following choice(s) is/are correct? A. There does not exist a bijection from S_1 to S_2 B. There exists a surjection from S_1 to S_2 C. There exists a bijection from S_1 to S_2 D. There does not exist an injection from S_1 to S_2

GATE 2021 · Discrete Mathematics · Functions · medium

Answer: B, C

1. Compute |S_1|: n^2 independent entries each choosing from {a,b,c}: |S_1| = 3^(n^2).
2. Compute |S_2|: Domain has n^2 elements, codomain has 3 elements: |S_2| = 3^(n^2).
3. Conclude which statements hold: |S_1| = |S_2| => a bijection exists (C is TRUE). A bijection is also a surjection (B is TRUE). A bijection is also an injection, so D is FALSE. A is FALSE (bijection does exist).