GATE1996-2.4

26 votes
3.3k views

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$.

retagged
0
option (b) and (c) are false. For (b) you can check manually by taking p=5 or whatever you like. And for option (c), there does not exist inverse for any given string because you can't concatenate two strings to form 'null' i.e identity element of the group.

(d) is True.

For option (a), even I am not sure. If somebody knows, please comment regarding option (a)
0
B is true. You can construct the Cayley table and see.
2

B is definitely true, Please notice that it is given multiplication under mod p (Xp)

FunFact--> it is even Abilian Group..

3 Answers

30 votes

Best answer

$(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
8

For option 'a', just giving a more explanatory proof, consider

$f(x) = x$

Let $g(x)$ be any other function such that $g(x) = x'$

Now $fog(x) = f(x') = x'$ and  $gof(x) = g(x) = x'$

Hence $fog(x) = gof(x) = g(x)$ , hence $f$ stands as identity element.

For inverse, it is much obvious, since we are taking all bijective functions on a finite so for $g: X \rightarrow Y$ we must have a function $h: Y \rightarrow X$ and so $goh(x) = hog(x) = f(x) = x$

Associativity $fo(goh) = (fog)oh$ and closure is also obvious.

1
f such that f(x) = x is the identity element shown for option a.
1
I agree, corrected my comment :)
0

i agree, option (c) is false,

but explain option (d) here, is it  Proposition 3.2.2

in the source link?

12
yes. Actually its basic group definition. For any element $b$, $b^{-1}$ must be there (inverse property). Now $a$ and $b^{-1}$ means $a*b^{-1}$ must be there (closure property).
0

hence $f$ stands as identity element

what is  $f$ ??

if i have 2 sets A{1,2,3}->B{a,b,c} with bijection function {<1,a><2,b><3,c>} then what will be the identity element?

0
For d option, it is not saying that s is subset of G,if my group is such that the given condition is followed but it is not subset of G,so how can it be subgroup?
0
how to look this table? how 1 come?
0
THANKS
0
Arjun Sir, how you can say about option (a) by taking a mapping of a function but not a composition of a function.sir can u plz give the generalize answer.
0
i am bit confused in option c .? anyone please help
0
String concatenation cannot have inverse.

because it cannot cannot satisfy commutativity property

like at$\neq$ta
0
f such that f(x) = x is the identity element shown for option a.

Can anyone explain this?
0

The set of all bijective functions on a finite set forms a group under function composition.

what is meaning of  under function composition. here ,

can you explain with example.

1 vote

$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.$

–2 votes

Related questions

20 votes
4 answers
1
3k views
Which of the following statements is FALSE? The set of rational numbers is an abelian group under addition The set of integers in an abelian group under addition The set of rational numbers form an abelian group under multiplication The set of real numbers excluding zero is an abelian group under multiplication
17 votes
6 answers
2
1.3k 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 B^c$ $A \cap B$ $A^c \cap B^c$
24 votes
3 answers
3
4.4k views
Let $R$ be a non-empty relation on a collection of sets defined by $_{A}R_ B$ if and only if $A \cap B = \phi$. Then, (pick the true statement) $A$ is reflexive and transitive $R$ is symmetric and not transitive $R$ is an equivalence relation $R$ is not reflexive and not symmetric
25 votes
4 answers
4
3.2k views
Let $R$ denote the set of real numbers. Let $f:R\times R \rightarrow R \times R$ be a bijective function defined by $f(x,y) = (x+y, x-y)$. The inverse function of $f$ is given by $f^{-1} (x,y) = \left( \frac {1}{x+y}, \frac{1}{x-y}\right)$ $f^{ -1} (x,y) = (x-y , x+y)$ $f^{-1} (x,y) = \left( \frac {x+y}{2}, \frac{x-y}{2}\right)$ $f^{-1}(x,y)=\left [ 2\left(x-y\right),2\left(x+y\right) \right ]$