Which one of the following is false?
1996
Which one of the following is false?
- A.
The set of all bijective functions on a finite set forms a group under function composition.
- B.
The set {1, 2, ..................., p-1} forms a group under multiplication mod p where p is a prime number
- C.
The set of all strings over a finite alphabet ∑ forms a group under concatenation
- D.
A subset S≠∅ of G is a subgroup of the group <G, *> if and only if for any pair of element a, b ∈ S, a∗b^−1 ∈ S
Attempted by 19 students.
Show answer & explanation
Correct answer: C
The set of all strings over a finite alphabet ∑ forms a group under concatenation Let's check if the set of all strings (denoted as Sigma*) satisfies all group properties under the string concatenation operation:
Closure: Concatenating any two strings results in another string. (True)
Associativity: For any strings u, v, and w, (u + v) + w = u + (v + w). (True)
Identity Element: The empty string (epsilon) acts as the identity because concatenating it with any string leaves the string unchanged. (True)
Inverse Element: For a non-empty string like "abc", there is no inverse string that you can concatenate to it to revert it back to the empty string (epsilon). You cannot "undo" a concatenation or have a string of negative length.
Because inverses do not exist for elements in this set, it forms a Monoid, not a group. Therefore, Statement C is false.