GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
357 views

Let $f \: \circ \: g$ denote function composition such that $(f \circ g)(x) = f(g(x))$. Let $f: A \rightarrow B$ such that for all $g \: : \: B \rightarrow A$ and $h \: : \: B \rightarrow A$ we have $f \: \circ \: g = f \: \circ \: h \: \Rightarrow g = h$. Which of the following must be true?

  1. $f$ is onto (surjective)
  2. $f$ is one-to-one (injective)
  3. $f$ is both one-to-one and onto (bijective)
  4. the range of $f$ is finite
  5. the domain of $f$ is finite
asked in Set Theory & Algebra by Veteran (76k points)   | 357 views

2 Answers

+7 votes
Best answer
i think domain of F must be finite.
morover i think domain of F i.e, A shud be singleton set.
bcoz it is given that for all g and h possible between B and A, f∘g=f∘h⇒g=h..
if domain of F contains more than 1 element in domain,  f∘g=f∘h is possible but, g will not be equal to h
example:
suppose
A,B are set of all integers
g(x)= {x| for all integers x}
h(x)= {1 | for any integer x}
f(x) = {2| for any integer x}
if we see here,
f∘g=f∘h
f∘g = {(x,2)| for all integers x belongs to B}
f∘h = {(x,2) | for all integers x belongs to B}
but actually g and h are not equal.
so domain of f cant contain more than 1 element to ensure "if  f∘g=f∘h then g=h."
if A contains only one element, there is no other way for g and h except to map to that one element.
i mean number of functions possible from B-->A will be only one function if A is singleton set so, g and h will be equal obviously if f∘g=f∘h.
so i think E is the answer
answered by Veteran (11.5k points)  
selected by
i think you are missing the term "for all possible g(x) and f(x)"
u took only specific case..
I was trying to counter the statement by giving an example. That means there exists a case where f(x) domain is not finite, and the condition in the question is satisfied. So, for all possible  g(x) and f(x) we can't say that f's domain is finite.
if you take domain of f as not finite, there will be a possibility that, fog=foh and g!=h..like i quoted in the example.
A,B are set of all integers
g(x)= {x| for all integers x}
h(x)= {1 | for any integer x}
f(x) = {2| for any integer x}
if we see here,
f∘g=f∘h
f∘g = {(x,2)| for all integers x belongs to B}
f∘h = {(x,2) | for all integers x belongs to B}
but actually g and h are not equal.

this is the problem when domain of f is not singleton set.
you should prove that for all possible functions g and h, with domain of f being NOT finite, the given condition gets satisfied. my counter example to your statement is above example.
there exists a function whose domain is not finite and given condition is not satisfied.

if you want to counter example mine, you should prove that there exists two functions g and h, such that fog=gof and g!=h with domain of 'f' being singleton set.
Consider the line in question - Which of the following must be true?

I want to say that Domain of f is finite, need not be the case always. There may exist another case too when domain of f is not finite. Hence, Domain of f must be finite always is not true.

Moreover, if I suppose that domain of f is finite, range must also be finite, and if I also suppose that A is singleton f must be one-one also. But only a single option is correct.

It may be the case that I am mistaken somewhere, you can take a look how I think by my answer below. And we can wait for official answer key by TIFR since they release it along with the question paper.

Thank you for your time and energy...
final thing i want to say is,
if you say that there exists one g and h such that , given condition is satisfied with f being not finite,it is not sufficient. you should prove that the condition is satisfied for all possible g and h, from B-->A with A being not finite,  is needed.!
if there are 3 functions possible from from B-->A, for all 3 functions, this condition must be satisfied. but you are showing only one such function from B-->A. take all the possibilites and check if every function is satisfying it or not bcoz of the word "FOR ALL".
and yes lets wait for official key :)
+1 vote

We can tackle this question by elimination. 

| Domain | >= | Range |

So, if domain is finite, then range must be finite. both d and e must be true. So, domain is not finite since the question has a single option correct. 

Moreover, we can take an example to counter the statement that domain or range is finite. Example is -> 

Example 1-

if A = B = Set of all real no.s, and if g(x) = x-1, h(x) = x+1, f(x) = x (domain, range of all three functions not finite)

then the condition that f o g = f o h => g=h will also be satisfied. How?

The condition can be written as if g not equal h, then f o g not eq f o h.

In this case, let's assume f o g = f o h are equal even if g is not equal to h.

=>   x + 1 = x -1

=> 1 = -1 ( which is false always)

Hence, our assumption was wrong. Therefore, in this example the condition f o g = f o h => g=h is satisfied.

The options that remain are a,b,c.

Example 2-  

if A = Singleton Set, B = any set may or may not be singleton. From B -> A, only one function is possible because all the elements of the domain (B ) must be mapped to that single element in A only. Then, g = h is always true in this case. So, f o g = f o h => g=h will always be true. 

But, f from A -> B has a single element in the domain, so will be mapped to single element in B. Hence, for f is not onto. So, f is not a bijection also. Hence, option a and c are wrong. d and e were prooved wrong by the previous example.

So, the correct option is b. f must be one-one.

answered by Active (1k points)  
edited by

$$\begin{align*} \forall g:\text{B}\rightarrow \text{A} \end{align*}$$

  • means all the elements of $B$ can be mapped to any subset of $A$ with function $g()$

similarly,

$$\begin{align*} \forall h:\text{B}\rightarrow \text{A} \end{align*}$$

  • means all the elements of $B$ can be mapped to any subset of $A$ with function $h()$

 

You are saying $g()$ is invertible. that means verything in $B$ is mapped to every thing in $A$ in a one-to-one fasion. In this case $g()$ is only one of the functions out of many possibilities of $g()$ from $B$ to $A$. and the question is asking for all possibilities of $g()$ fro $B$ to $A$.

Please explain your solution. Why you approched like that ?

It was intuitive since Inverse of a function is a unique and that function is a bijection whose inverse exists.

And also inverse is a bijection.
"Inverse of a function is a unique and that function is a bijection whose inverse exists."..definition of inverse.thats ok !

.Now ,in your case, you taking only one possibility of $g()$.from $B$ to $A$. I am asking why ? even after question asking for all possible $g()$ ??
@Debashish he seems to be very straight. Implication is being satisfied for all x.

f°g = f°h => g = h means f is invertible. When f is invertible, it must be bijective.

What do you think?

could you explain this situation ?

Thank you. Got it.
you could have gone through the explanation provided already and answer has been selected as well:)
Hi

I have edited my answer, taking reference to the example you mentioned in the comments above.
Answer:

Related questions



Top Users Mar 2017
  1. rude

    4768 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2734 Points

  5. Debashish Deka

    2592 Points

  6. 2018

    1544 Points

  7. Vignesh Sekar

    1422 Points

  8. Akriti sood

    1342 Points

  9. Bikram

    1312 Points

  10. Sanjay Sharma

    1126 Points

Monthly Topper: Rs. 500 gift card

21,508 questions
26,832 answers
61,091 comments
23,146 users