Can we show this in diagrammatic form?

Dark Mode

4,266 views

20 votes

Consider the following sets, where $n \geq 2$:

- $S_1$: Set of all $n \times n$ matrices with entries from the set $\{ a, b, c\}$
- $S_2$: Set of all functions from the set $\{0,1,2, \dots, n^2-1\}$ to the set $\{0, 1, 2\}$

Which of the following choice(s) is/are correct?

- There does not exist a bijection from $S_1$ to $S_2$
- There exists a surjection from $S_1$ to $S_2$
- There exists a bijection from $S_1$ to $S_2$
- There does not exist an injection from $S_1$ to $S_2$

30 votes

Best answer

$S_1:$ There are $n^2$ element in the matrix, we have $3$ choices for each element, so number of such matrices $=3^{n^2}.$

$S_2:$ There are $n^2$ total elements with $3$ choices for each element, so number of functions possible $=3^{n^2}.$

As the cardinality of both the sets are same, we can establish a bijection from one set to another. As bijection is possible, surjection is also possible.

So options B and C.

$S_2:$ There are $n^2$ total elements with $3$ choices for each element, so number of functions possible $=3^{n^2}.$

As the cardinality of both the sets are same, we can establish a bijection from one set to another. As bijection is possible, surjection is also possible.

So options B and C.