Question

Consider the following sets, where \( n \geq 2 \):
\[ S_1:\ \text{Set of all } n \times n \text{ matrices with entries from the set } \{a,b,c\} \] \[ S_2:\ \text{Set of all functions from the set } \{0,1,2,\ldots,n^2-1\} \text{ to the set } \{0,1,2\} \] 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\).

Hint:

When two finite sets have equal cardinality, bijections, injections, and surjections between them all exist.

Answer 1

The Correct Option is B, C

Step 1: Compute the cardinality of \(S_1\).
Each entry of an \(n \times n\) matrix can independently take one of the three values \(\{a,b,c\}\).
Hence, \[ |S_1| = 3^{n^2}. \]

Step 2: Compute the cardinality of \(S_2\).
A function from a set of size \(n^2\) to a set of size \(3\) has \[ |S_2| = 3^{n^2} \] possible mappings.

Step 3: Compare cardinalities.
Since \(|S_1| = |S_2| = 3^{n^2}\), the two sets have equal finite cardinality.

Step 4: Conclusions about mappings.
Equal cardinalities imply the existence of a bijection between \(S_1\) and \(S_2\).
Hence, a surjection and an injection from \(S_1\) to \(S_2\) also exist.

Step 5: Evaluate options.
Option (B) is correct (surjection exists).
Option (C) is correct (bijection exists).
Options (A) and (D) are incorrect.

Final Answer: (B), (C)