# Consider the following sets, where n > 2: S1: Set of all n x n matrices with entries from the set {a, 6, c} S2: Set of all functions from the set {0,1

57 views
in Algebra
closed

Consider the following sets, where n > 2:
S1: Set of all n x n matrices with entries from the set {a, 6, c}

S2: Set of all functions from the set {0,1, 2, ..., n2 — 1} to the set {0,1,2}

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

1. There does not exist an injection from S1 to S2.
2. There exists a bijection from S1 to S2
3. There exists a surjection from S1 to S2.
4. There does not exist a bijection from S1 to S2

by (59.9k points)
selected

Answer: Option 2 and Option 3

Concept:

Injection:

It is Mapping/function between two sets A and B (f: A→ B) such that every element in A mapped to a unique element in B. ( one-one function )

Surjection:

It is Mapping/function between two sets A and B (f: A→ B) such that every element in B has a pre-image in A.(onto Function).

Bijection:

It is Mapping/function between two sets A and B such that every element in A is mapped to exactly one element in B and every element in B has an exactly one pre-image in A.

Explanation:

S1: Set of all n x n matrices with entries from the set {a, b, c}

So in an n× n Matrix total number of the position will be n2 and these positions can be filled from any element from the set { a, b, c}

Hence the total number of matrices possible = ${3^{{n^2}}}$

S2:Set of all functions from the set {0,1, 2, ..., n2 — 1} to the set {0,1,2}

number of all functions in S2 will be ${3^{{n^2}}}$.

Option 1:There does not exist an injection from S1 to S2.

This is not correct. Since the cardinality of both the sets S1 and S2 is equal. So we can draw one-to-one mapping between Set S1 and S2.

Option 2: There exists a bijection from S1 to S2.

This is correct. Since the cardinality of both the sets S1 and S2 is equal. and hence Bijective function/mapping possible between Set S1 and S2.

Option 3: There exists a surjection from S1 to S2.

This is correct. Since Bijection possible and hence Surjection also possible. Bijection implies Surjection but not vice versa.

Option 4:There does not exist a bijection from S1 to S2.

This is not correct.