GATE CS 2025 Set 1 | Question 49

MSQ · 2 marks

\(A = \{0, 1, 2, 3, \ldots\}\) is the set of non-negative integers. Let \(\mathrm{F}\) be the set of functions from \(A\) to itself. For any two functions, \(f_1, f_2 \in \mathrm{F}\), we define

\[(f_1 \odot 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 \((\mathrm{F}, \odot)\)?

  1. Option A: \((\mathrm{F}, \odot)\) is an Abelian group.
  2. Option B: \((\mathrm{F}, \odot)\) is an Abelian monoid. (correct)
  3. Option C: \((\mathrm{F}, \odot)\) is a non-Abelian group.
  4. Option D: \((\mathrm{F}, \odot)\) is a non-Abelian monoid.

Answer

(B)

Explanation

Check the axioms for pointwise addition of functions from \(A\) to \(A\).

  • Closure: \(f_1(n) + f_2(n)\) is again a non-negative integer, so \(f_1 \odot f_2 \in \mathrm{F}\).
  • Associativity and commutativity come straight from ordinary addition at each \(n\).
  • Identity: the zero function \(z(n) = 0\) is in \(\mathrm{F}\), and \(f \odot z = f\).
  • Inverses fail: for the constant function \(f(n) = 1\), the inverse would need \(g(n) = -1\), which is not in \(A\).

So \((\mathrm{F}, \odot)\) is a commutative (Abelian) monoid but not a group. (A) and (C) are wrong because it is not a group; (D) is wrong because \(\odot\) is commutative.

Answer: B