First time here? Checkout the FAQ!
+5 votes

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 (79k points)   | 458 views

3 Answers

+4 votes
Best answer
$f:A\rightarrow B$ is injective if and only if, given any functions $g,h:B\rightarrow A$ whenever $f\circ g=f\circ h,$ $f\circ g=f\circ h,then\ g=h$.

Refer to properties of Injective functions:

Let us prove $(\forall g,h:f(g(x))=f(h(x))\rightarrow g(x)=h(x))\rightarrow f\ is\ one-to-one$ is true.

This is equivalent to, $f\ is\ not\ one-to-one\rightarrow (\exists g,h:f(g(x))=f(h(x))\wedge g(x)\neq h(x))$

Let us assume LHS is true, i.e. $f\ is\ not\ one-to-one$.

Then there exists some $c,d\in A$ such that,

                                     $f(c)=f(d)=a,$ where $a$ is an arbitrary element which belongs to B

Let g and h be some functions out of all possible functions from B to A such that $g\neq h$,

                                     i.e. $g(x)=c\ and\ h(x)=d\ \exists c,d\in A\ and\ \exists x\in B$

$\therefore f(g(x))=f(c)=a\ and\ f(h(x))=f(d)=a$ and $g(x)\neq h(x)$, i.e. RHS is also true.

Thus, whenever $\forall g,h\ f\circ g=f\circ h\rightarrow g=h$ is true, $f \ is\ one-to-one$.


Domain of $f$ need not be finite. Let $f:A\rightarrow B$ be identity function and A and B be infinite sets. Assume that $f\circ g=f\circ h$ is true,

then $f(g(x))=f(h(x))\rightarrow g(x)=h(x))$ will be true $\forall g,h$ since $f$ is an identity function. So, even if domain of f is not finite, the condition holds true.
answered by Junior (671 points)  
selected by
+6 votes
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
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 = {(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)  
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! 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 = {(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 :)
+3 votes

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 Junior (985 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()$


$$\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:)

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

Related questions

Top Users Aug 2017

    4654 Points

  2. Bikram

    4012 Points

  3. akash.dinkar12

    3136 Points

  4. rahul sharma 5

    2832 Points

  5. manu00x

    2644 Points

  6. makhdoom ghaya

    2370 Points

  7. just_bhavana

    2040 Points

  8. Tesla!

    1742 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1554 Points

24,864 questions
31,941 answers
30,062 users