GATE CS 1996 Q2.4 — Monoids and Groups

To find which statement is false, let us analyze each option:

• Option A: The set of all bijective functions on a finite set forms a group under function composition.
  True. For a finite set of size $n$, this set of bijections is the symmetric group $S_n$. Composition of bijections is associative, the identity function acts as the identity element, and every bijection has a unique inverse which is also a bijection.
• Option B: The set $\{1, 2, \dots, p-1\}$ forms a group under multiplication mod $p$, where $p$ is a prime number.
  True. This is the multiplicative group of integers modulo $p$, denoted as $\mathbb{Z}_p^*$. Since $p$ is prime, every element $a \in \{1, 2, \dots, p-1\}$ is coprime to $p$, ensuring that a unique multiplicative inverse exists for every element.
• Option C: The set of all strings over a finite alphabet forms a group under concatenation.
  False. Let $\Sigma^*$ be the set of all strings over a finite alphabet $\Sigma$. Under concatenation, the identity element is the empty string $\epsilon$. However, for any non-empty string $w \in \Sigma^*$ (where $|w| \ge 1$), there is no string $x \in \Sigma^*$ such that $w \cdot x = \epsilon$, because the length of $w \cdot x$ is $|w| + |x| \ge 1$. Thus, non-empty strings do not have inverses. This algebraic structure is a monoid, not a group.
• Option D: A subset $S \neq \emptyset$ of $G$ is a subgroup of the group $\langle G, * \rangle$ if and only if for any pair of elements $a, b \in S, a * b^{-1} \in S$.
  True. This is the standard one-step subgroup test used to verify if a subset is a subgroup.

Therefore, statement C is false.