The GATE Grind

GATE 2021 CS (CS2) – Question 21

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 1 mark · Multiple select

For n≥2, S1 contains all n×n matrices over {a,b,c}, and S2 contains all functions from $\{0,1,\ldots,n^2-1\}$ to {0,1,2}. Which are correct?

  1. There is no bijection S1→S2
  2. There is a surjection S1→S2
  3. There is a bijection S1→S2
  4. There is no injection S1→S2

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) There is a surjection S1→S2; (C) There is a bijection S1→S2

Explanation

Each matrix chooses among three values independently in n² positions, so |S1|=3^(n²). Each function independently chooses one of three outputs for n² inputs, so |S2| is the same. A bijection exists by numbering matrix cells and relabelling their values; hence a surjection also exists. Select B,C.

More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions

All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →