Option A
The set of all bijective functions on a finite set forms a group under function composition. Let $ X $ be a finite set with $ n $ elements, i.e., $ |X| = n $. Let $ \mathrm{Bij}(X) $ denote the set of all bijective functions from $ X $ to itself. That is,
$$
\mathrm{Bij}(X) = \{ f : X \to X \mid f \text{ is bijective} \}.
$$
We consider the binary operation $ \circ $, defined as function composition: for $ f, g \in \mathrm{Bij}(X) $, define $ (f \circ g)(x) = f(g(x)) $ for all $ x \in X $.Now verify that $ (\mathrm{Bij}(X), \circ) $ satisfies the four group axioms:
1. Closure
Let $ f, g \in \mathrm{Bij}(X) $. Since $ f $ and $ g $ are both bijections, their composition $ f \circ g $ is also a bijection.Injectivity: Suppose $ (f \circ g)(x_1) = (f \circ g)(x_2) $. Then $ f(g(x_1)) = f(g(x_2)) $. Since $ f $ is injective, $ g(x_1) = g(x_2) $. Since $ g $ is injective, $ x_1 = x_2 $. So $ f \circ g $ is injective.
Surjectivity: Let $ y \in X $. Since $ f $ is surjective, there exists $ z \in X $ such that $ f(z) = y $. Since $ g $ is surjective, there exists $ x \in X $ such that $ g(x) = z $. Then $ (f \circ g)(x) = f(g(x)) = f(z) = y $. So $ f \circ g $ is surjective.
Thus, $ f \circ g \in \mathrm{Bij}(X) $, and closure holds.
2. Associativity
Function composition is always associative: for any functions $ f, g, h : X \to X $, we have
$$
(f \circ g) \circ h = f \circ (g \circ h).
$$
This holds regardless of whether the functions are bijective or not. Hence, associativity holds in $ \mathrm{Bij}(X) $.
3. Identity Element
Define $ \mathrm{id}_X : X \to X $ by $ \mathrm{id}_X(x) = x $ for all $ x \in X $. This function is clearly bijective.For any $ f \in \mathrm{Bij}(X) $, we have
$$
(f \circ \mathrm{id}_X)(x) = f(\mathrm{id}_X(x)) = f(x), \quad \text{and} \quad (\mathrm{id}_X \circ f)(x) = \mathrm{id}_X(f(x)) = f(x).
$$
So $ f \circ \mathrm{id}_X = \mathrm{id}_X \circ f = f $. Thus, $ \mathrm{id}_X $ is the identity element in $ \mathrm{Bij}(X) $.
4. Inverses
Let $ f \in \mathrm{Bij}(X) $. Since $ f $ is bijective, it has an inverse function $ f^{-1} : X \to X $, satisfying
$$
f \circ f^{-1} = f^{-1} \circ f = \mathrm{id}_X.
$$
Moreover, since $ f $ is bijective, $ f^{-1} $ is also bijective (the inverse of a bijection is a bijection). Therefore, $ f^{-1} \in \mathrm{Bij}(X) $.Since all four group axioms are satisfied, $ (\mathrm{Bij}(X), \circ) $ is a group. When $ |X| = n $, this group is called the symmetric group on $ n $ elements, denoted $ S_n $.Therefore, Option A is true.
Option B
The set $\{1, 2, \dots, p-1\}$ forms a group under multiplication modulo $p$, where $p$ is a prime number.Let $ p $ be a prime number. Define the set
$$
\mathbb{Z}_p^\times = \{1, 2, \dots, p-1\},
$$
and consider the binary operation $ \cdot_p $, defined as multiplication modulo $ p $: for $ a, b \in \mathbb{Z}_p^\times $, define
$$
a \cdot_p b = (a \cdot b) \mod p.
$$
Verify the group axioms.
1. Closure
Let $ a, b \in \mathbb{Z}_p^\times $. Since $ 1 \leq a, b \leq p-1 $, we have $ ab \not\equiv 0 \pmod{p} $, because $ p $ is prime and does not divide either $ a $ or $ b $. Therefore, $ ab \mod p \in \{1, 2, \dots, p-1\} $, so $ a \cdot_p b \in \mathbb{Z}_p^\times $.
2. Associativity
Multiplication modulo $ p $ inherits associativity from integer multiplication:
$$
(a \cdot_p b) \cdot_p c = ((ab \mod p) \cdot c) \mod p = (abc) \mod p,
$$
$$
a \cdot_p (b \cdot_p c) = (a \cdot (bc \mod p)) \mod p = (abc) \mod p.
$$
So associativity holds.
3. Identity
The element $ 1 \in \mathbb{Z}_p^\times $ satisfies $ 1 \cdot_p a = a \cdot_p 1 = a $ for all $ a \in \mathbb{Z}_p^\times $, so $ 1 $ is the identity.
4. Inverses
Let $ a \in \mathbb{Z}_p^\times $. Since $ \gcd(a, p) = 1 $ (because $ p $ is prime and $ a < p $), by Bézout’s identity, there exist integers $ x, y $ such that
$$
ax + py = 1.
$$
Reducing modulo $ p $, we get
$$
ax \equiv 1 \pmod{p}.
$$
Thus, $ x \mod p $ is the multiplicative inverse of $ a $ modulo $ p $. Since $ x \not\equiv 0 \pmod{p} $, we can take $ x' = x \mod p \in \{1, 2, \dots, p-1\} $, so $ x' \in \mathbb{Z}_p^\times $ and $ a \cdot_p x' = 1 $.Hence, every element has an inverse in $ \mathbb{Z}_p^\times $.Therefore, $ (\mathbb{Z}_p^\times, \cdot_p) $ is a group. In fact, it is cyclic of order $ p-1 $.Therefore, Option B is true.
Option C
The set of all strings over a finite alphabet forms a group under concatenation. Let $ \Sigma $ be a finite nonempty alphabet (e.g., $ \Sigma = \{a, b\} $). Let $ \Sigma^* $ denote the set of all finite-length strings over $ \Sigma $, including the empty string $ \varepsilon $.
Define the binary operation $ \cdot $ as string concatenation: for $ u, v \in \Sigma^* $, $ u \cdot v $ is the string formed by appending $ v $ to the end of $ u $.
Verify the group axioms.
1. Closure
Concatenation of two finite strings is always a finite string. So $ u \cdot v \in \Sigma^* $ for all $ u, v \in \Sigma^* $. Closure holds.
2. Associativity
String concatenation is associative: for $ u, v, w \in \Sigma^* $,
$$
(u \cdot v) \cdot w = u \cdot (v \cdot w),
$$
since both sides represent the string formed by writing $ u $, then $ v $, then $ w $, in sequence.
3. Identity
The empty string $ \varepsilon $ satisfies $ \varepsilon \cdot w = w \cdot \varepsilon = w $ for all $ w \in \Sigma^* $. So $ \varepsilon $ is the identity element.
4. Inverses : Failure
This is where the structure fails to be a group.
Suppose $ w \in \Sigma^* $ is a nonempty string. Suppose, for contradiction, that there exists $ v \in \Sigma^* $ such that
$$
w \cdot v = \varepsilon.
$$
But the length of $ w \cdot v $ is $ |w| + |v| \geq |w| > 0 $, while $ |\varepsilon| = 0 $. Contradiction.Similarly, if $ v \cdot w = \varepsilon $, same issue: length mismatch.Therefore, no nonempty string has an inverse under concatenation. Even more fundamentally, the only element with an inverse is $ \varepsilon $, since $ \varepsilon \cdot \varepsilon = \varepsilon $, so $ \varepsilon^{-1} = \varepsilon $.
Thus, inverses do not exist for most elements.Since the inverse axiom fails, $ (\Sigma^*, \cdot) $ is not a group. It is a monoid (a semigroup with identity). Therefore, Option C is false.
Option D
A subset $ S \neq \emptyset $ of a group $ \langle G, * \rangle $ is a subgroup if and only if for any pair of elements $ a, b \in S $, $ a * b^{-1} \in S $. This is known as the one-step subgroup test. We prove both directions. ($\Rightarrow$): If $ S $ is a subgroup, then $ a * b^{-1} \in S $ for all $ a, b \in S $
If $ S $ is a subgroup, then:
- $ b \in S \Rightarrow b^{-1} \in S $ (by inverse axiom in subgroup),
- $ a, b^{-1} \in S \Rightarrow a * b^{-1} \in S $ (by closure axiom in subgroup).
So the condition holds.
($\Leftarrow$): If $ S \neq \emptyset $ and $ a * b^{-1} \in S $ for all $ a, b \in S $, then $ S $ is a subgroup.We must show that $ S $ satisfies the three subgroup conditions: contains identity, closed under inverses, closed under the operation.
Step 1: Identity is in $ S $
Since $ S \neq \emptyset $, pick any $ a \in S $. Set $ b = a $. Then
$$
a * a^{-1} = e \in S.
$$
So the identity $ e $ is in $ S $.
Step 2: Inverses are in $ S $
Let $ b \in S $. Set $ a = e \in S $. Then
$$
e * b^{-1} = b^{-1} \in S.
$$
So every element in $ S $ has its inverse in $ S $.
Step 3: Closure under $ * $
Let $ a, b \in S $. From Step 2, $ b^{-1} \in S $. Now set $ c = b^{-1} \in S $, and apply the condition with $ a $ and $ c $:
$$
a * c^{-1} = a * (b^{-1})^{-1} = a * b \in S.
$$
Thus, $ a * b \in S $, so $ S $ is closed under the group operation.Therefore, $ S $ is a subgroup of $ G $.Therefore, Option D is true.
$$
\color{lime} \boxed{\text{Answer: C}}
$$
