GATE 2025 CS1 Q.49: solution and answer

GATE 2025 · CS1Q.49 · 2 marks · MSQ

$A = {0, 1, 2, 3, \dots}$ is the set of non-negative integers. Let $F$ be the set of functions from $A$ to itself. For any two functions $f_{1}, f_{2} \in F$ , we define

(f_{1} ⊙ f_{2}) (n) = f_{1} (n) + f_{2} (n)

for every number $n$ in $A$ . Which of the following is/are CORRECT about the mathematical structure $(F, ⊙)$ ?

(A)
$(F, ⊙)$ is an Abelian group.
(B)
$(F, ⊙)$ is an Abelian monoid.
(C)
$(F, ⊙)$ is a non-Abelian group.
(D)
$(F, ⊙)$ is a non-Abelian monoid.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Only (B) is correct: $(F, ⊙)$ is an Abelian monoid, but not a group.

Official answer: BSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

Closure: for $f_{1}, f_{2} \in F$ , the value $f_{1} (n) + f_{2} (n)$ is a sum of two non-negative integers, hence a non-negative integer, so $f_{1} ⊙ f_{2} \in F$ .
Associativity: $((f_{1} ⊙ f_{2}) ⊙ f_{3}) (n) = (f_{1} (n) + f_{2} (n)) + f_{3} (n) = f_{1} (n) + (f_{2} (n) + f_{3} (n)) = (f_{1} ⊙ (f_{2} ⊙ f_{3})) (n)$ for every $n$ , because addition of integers is associative.
Identity: the zero function $e (n) = 0$ lies in $F$ and $(f ⊙ e) (n) = f (n) + 0 = f (n) = (e ⊙ f) (n)$ . So $(F, ⊙)$ is a monoid.
Commutativity: $f_{1} (n) + f_{2} (n) = f_{2} (n) + f_{1} (n)$ for every $n$ , so $f_{1} ⊙ f_{2} = f_{2} ⊙ f_{1}$ and the monoid is Abelian. This rules out (C) and (D), which both call the structure non-Abelian.
Inverses: an inverse of $f$ would be a function $g \in F$ with $f (n) + g (n) = 0$ for all $n$ , i.e. $g (n) = - f (n)$ . Since $g (n)$ must be non-negative, this is possible only when $f (n) = 0$ for every $n$ .
Take $f (n) = 1$ for all $n$ . Then $g (n) = - 1 \in / A$ , so $f$ has no inverse in $F$ and $(F, ⊙)$ is not a group. This rules out (A).
So $(F, ⊙)$ is an Abelian monoid that is not a group, and only (B) is correct.

KEY IDEA

Pointwise addition of functions from the non-negative integers to themselves is closed, associative, commutative and has the zero function as identity. Inverses would need negative values, so it is a commutative monoid and not a group.

WATCH OUT FOR

Treating $(F, ⊙)$ as an Abelian group because addition of integers has inverses. The inverse $- f (n)$ is not a non-negative integer, so it lies outside $F$ for any non-zero $f$ .

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 7 Groups questions, with notes

GATE 2025 CS1 Q.49: solution and answer

Answer and solution

More Groups questions