GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
513 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 (92.7k points) 987 2344 3118 | 513 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: https://en.wikipedia.org/wiki/Injective_function

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 Loyal (4.4k points) 4 5 9
selected by
+7 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
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 (12.5k points) 12 52 155
why not one-one and onto ?
it need not be onto i think
suppose A is singleton set contains only one element "2"
f(x) = { x | for any x belongs to A}
here f(x) is not onto as range of f is only {2} != codomain B
but yet, " if f∘g=f∘h then g=h." is satisfied.we are able to satisfy the condition given without making f onto. hence f need not be onto

as we are keeping only 1 element in set A, it will be one-one for sure.
so i thought best answer is E

  • I satisfied $f \circ g = f \circ h$ by mapping f is the desired way. But, 

If $A$ is not singleton then we can not enforce g = h condition right ?

@debashish yeah but, what i was saying is, if A is not singleton set,
there will be a case where  f∘g=f∘h but g!=h. which shudnt happen as per given question
for all g and h between B and A, we shud be able to satisfy the condition  if f∘g=f∘h then g=h. i think this will be possible only when A is single ton set.
whats ur opinion?
My drawing is saying what you have just said

@Anusha In the example given

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}

 we considered Domain A and Range B for f(x) is Set of all integers. But 

for f(x) = {2| for any integer x}, Range B ={2} which is not a set of all integers. This is clearly contradicting to our assumption. Same is with h(x). I think we cant say anything with this example. Let me know if I'm wrong.

i said A and B are set of all integers.
it means domain and co-domain of f is set of all integers
but range is different from co-domain . range is {2} only
Hi
What if I take g(x) = x-1, h(x) = x+1, f(x) = x. The condition is satisfied still but the domain is not finite ..
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 :)
+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 Active (1.1k points) 1 2 12
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



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23642 Points

  2. Bikram

    17188 Points

  3. Habibkhan

    8734 Points

  4. srestha

    6404 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5098 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4478 Points

  9. sushmita

    4008 Points

  10. Rishi yadav

    3960 Points


Recent Badges

Popular Question Bikram
Regular Mr.OOPs
Avid Reader Venkat Sai
Popular Question jothee
Verified Human anchal Singh
Great Question Kathleen
Verified Human Ankita_ Pawar
Avid Reader kenzou
Notable Question Sumit Chaudhary 2
Nice Comment rahul sharma 5
27,380 questions
35,231 answers
84,395 comments
33,389 users