Consider the following sets, where \(n≥2\): \(S_1\): Set of all \(n×n\)…
2021
Consider the following sets, where \(n≥2\):
\(S_1\): Set of all \(n×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 \(\{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\).
Attempted by 104 students.
Show answer & explanation
Correct answer: B, C
Key idea: both sets are finite and have the same number of elements, namely 3^(n^2).
Count S1: An n×n matrix has n^2 entries and each entry can be a, b, or c, so |S1| = 3^(n^2).
Count S2: A function from {0,1,...,n^2−1} to {0,1,2} chooses one of three values for each of the n^2 domain points, so |S2| = 3^(n^2).
Explicit bijection: Fix a mapping a↦0, b↦1, c↦2. For a matrix, list its entries in row-major order to get n^2 symbols; define the function value at index i to be the mapped value of the i-th entry. This map is one-to-one and onto between S1 and S2.
Conclusion: There exists a bijection between S1 and S2, so a surjection and an injection between them also exist. The statements claiming no bijection or no injection are false.