GO Classes DPP | GATE CS | Discrete Mathematics| Functions

Answer 1

Given the set $S = \{0, 1, 2, 3, 4, 5, 6\}$.

Since $S$ is a finite set, a function from $S$ to $S$ is both injective and surjective if and only if each element in the domain maps to a unique element in the codomain, meaning the output set (range) will also be exactly $\{0, 1, 2, 3, 4, 5, 6\}$.

Let's test each option by finding the outputs for all $x \in S$:

A. $f(x) = (2x + 1) \pmod 7$

• $f(0) = (2(0) + 1) \pmod 7 = 1$

• $f(1) = (2(1) + 1) \pmod 7 = 3$

• $f(2) = (2(2) + 1) \pmod 7 = 5$

• $f(3) = (2(3) + 1) \pmod 7 = 7 \pmod 7 = 0$

• $f(4) = (2(4) + 1) \pmod 7 = 9 \pmod 7 = 2$

• $f(5) = (2(5) + 1) \pmod 7 = 11 \pmod 7 = 4$

• $f(6) = (2(6) + 1) \pmod 7 = 13 \pmod 7 = 6$

• Result: The range is $\{0, 1, 2, 3, 4, 5, 6\}$. Every element in $S$ is mapped to a unique value, so this function is both injective and surjective.

B. $f(x) = x^2 \pmod 7$

• $f(0) = 0^2 \pmod 7 = 0$

• $f(1) = 1^2 \pmod 7 = 1$

• $f(2) = 2^2 \pmod 7 = 4$

• $f(3) = 3^2 \pmod 7 = 9 \pmod 7 = 2$

• $f(4) = 4^2 \pmod 7 = 16 \pmod 7 = 2$

• Result: Stop here. $f(3) = 2$ and $f(4) = 2$. Because two different inputs give the same output, the function is not injective.

C. $f(x) = |x - 3|$

• $f(0) = |0 - 3| = 3$

• $f(1) = |1 - 3| = 2$

• $f(2) = |2 - 3| = 1$

• $f(3) = |3 - 3| = 0$

• $f(4) = |4 - 3| = 1$

• Result: $f(2) = 1$ and $f(4) = 1$. The function is not injective.

D. $f(x) = x + 1$ if $0 \leq x \leq 5$, and $f(6) = 1$

• $f(0) = 0 + 1 = 1$

• ...

• $f(6) = 1$ (given)

• Result: $f(0) = 1$ and $f(6) = 1$. The function is not injective.

Conclusion:

Option A is the only function that produces a unique output for every input, covering the entire set $S$.

The correct answer is A.