edited by
9,441 views
45 votes
45 votes

Which one of the following is false?

  1. The set of all bijective functions on a finite set forms a group under function composition
  2. The set $\{1, 2, \dots p-1\}$ forms a group under multiplication mod $p$, where $p$ is a prime number
  3. The set of all strings over a finite alphabet forms a group under concatenation
  4. 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$
edited by

4 Answers

Best answer
44 votes
44 votes

$(a)$ Let set = ${1, 2, 3, 4}$

We can have identity function as $\left \{ \left ( 1,1 \right ),\left ( 2,2 \right ),\left ( 3,3 \right ),\left ( 4,4 \right ) \right \}$

Since function is bijective and mapping to same set, we can have an inverse for any function by inverting the relation (changing the mapping $a \to b\text{ to } b \to a$)

Since the function maps to the same set, it must be closed and associative also. So, all four properties of group satisfied. So, $(a)$ is true. 

$(b)$ Let $p = 5$. So, set $=$ $\left \{ 1,2,3,4 \right \}$

Identity element is $1$. 

$$ \begin{array}{|c|c|c|c|c|}\hline *& 1 &2 &3& 4\\\hline 1& 1& 2& 3& 4\\\hline 2& 2& 4& 1& 3\\\hline 3& 3& 1& 4& 2\\\hline 4& 4& 3& 2& 1\\\hline \end{array}$$This forms a group. Similarly for any p, we get a group. So, $(b)$ is also true. 

$(c)$ is false as string concatenation operation is a monoid (doesn't have inverse to become a group).

http://en.wikipedia.org/wiki/Concatenation

$(d)$ is True.

http://www.math.niu.edu/~beachy/abstract_algebra/study_guide/32.html

edited by
34 votes
34 votes

$A.$  TRUE

Define a set $S_{3}=$ Set of all bijections from $\{1,2,3\}$ to $\{1,2,3\}$ 

$f_{1}: 1\rightarrow 1, 2\rightarrow 2,3\rightarrow 3$

$f_{2}: 1\rightarrow 2, 2\rightarrow 1,3\rightarrow 3$

$f_{3}: 1\rightarrow 3, 2\rightarrow 2,3\rightarrow 1$

$f_{4}: 1\rightarrow 1, 2\rightarrow 3,3\rightarrow 2$

$f_{5}: 1\rightarrow 2, 2\rightarrow 3,3\rightarrow 1$

$f_{6}: 1\rightarrow 3, 2\rightarrow 1,3\rightarrow 2$

 

$S_{3}=\{f_{1},f_{2},f_{3},f_{4},f_{5},f_{6}\}$

Consider the composition of functions on $S_{3}$

Few Ex:  $f_{2}(f_{5})=f_{4}$   $f_{5}(f_{2})=f_{3}$

Now,

1. $S_{3}$ is closed under composition

2. There is an identity element of $S_{3}:f_{1}$

3. Is there an inverse for every element of $S_{3}?$ Yes!!

$f_{2}(f_{2})=f_{1},f_{3}(f_{3})=f_{1},f_{4}(f_{4})=f_{1},f_{5}(f_{6})=f_{1}$

4. Composition of functions is associative.


$B.$ TRUE

Go through the Best answer.


$C.$ FALSE

Inverse is not possible $\times$


$D.$ TRUE

First assume that H is a subgroup of G. We wish to show that $gh^ {−1} ∈ H$ whenever g and h are in H. Since h is in H, its inverse $h^{−1}$ must also be in H. Because of the closure of the group operation, $gh^{−1} ∈ H.$

0 votes
0 votes

In option (c)

the set of all strings over a finite alphabet ∑ doesn’t forms a group under concatenation because the inverse of a string doesn’t exist with respect to concatenation.

 

–3 votes
–3 votes

The answer is, option (C) The set of all strings over a finite alphabet forms a group under concatenation

Answer:

Related questions

26 votes
26 votes
8 answers
2
Kathleen asked Oct 9, 2014
6,014 views
Let $A$ and $B$ be sets and let $A^c$ and $B^c$ denote the complements of the sets $A$ and $B$. The set $(A-B) \cup (B-A) \cup (A \cap B)$ is equal to$A \cup B$$A^c \cup ...
40 votes
40 votes
5 answers
3